Математическая модель задачи линейного программирования

В общем случае задача математического программирования может быть сформулирована следующим образом: найти вектор , доставляющий экстремальное значение (максимум или минимум) целевой функции , т.е.

при ограничениях

Линейное программирование (ЛП) — раздел математического программирования, в котором рассматриваются задачи оптимизации, в которых целевая функция и все функции , входящие в систему ограничений, линейны (первой степени) относительно переменных .

В случае переменных математическая постановка задачи линейного программирования может быть записана в следующем виде (т.н. стандартная форма задачи линейного программирования):

(1)

Свойство линейности модели (1) формально означает линейность всех входящих в нее функций (целевой функции и ограничений). Линейность предполагает выполнение следующих свойств:

1. Пропорциональность предполагает, что значения левых частей неравенств ограничений и целевой функции прямо пропорциональны значениям переменных;

2. Аддитивность означает, что общий вклад всех переменных в значение целевой функции и левых частей ограничений является прямой суммой вкладов от различных переменных.

Часто дополнительно предполагают, что должно быть выполнено свойство делимости, согласно которому переменные могут принимать произвольные значения из некоторой непрерывной области.

Вектор (план) , удовлетворяющий системе ограничений называется допустимым решением (планом).

Допустимый план, доставляющий целевой функции экстремальное значение, называется оптимальным решением (планом), а само экстремальное значение целевой функции — значением задачи.

Оптимальный план будем обозначать , экстремальное значение целевой функции (значение задачи) .

Отметим, что, оптимальное решение в задаче линейного программирования, вообще говоря, не обязательно существует, возможны следующие случаи:

1. Оптимального решения не существует;

2. Существует единственное оптимальное решение;

3. Имеется бесконечное множество оптимальных решений (доставляющих одно и то же значение целевой функции).

На практике встречаются задачи линейного программирования не только в указанной выше стандартной форме (1), но и в канонической форме, в которой все ограничения представлены равенствами, а также задачи в общей постановке, в которых присутствуют как ограничения типа неравенств, так и ограничения типа равенств, при этом некоторые переменные могут и не иметь ограничений на знак.

Приведение задачи линейного программирования к одному из указанных специальных видов осуществляется с помощью достаточно несложных эквивалентных преобразований. Необходимость представления задачи линейного программирования в том или ином виде часто диктуется выбранным способом решения: так, например, основным алгоритмом решения задач линейного программирования является симплекс-метод, который требует представления задачи в канонической форме.

2.2. Трактовка задачи линейного программирования как задачи о наилучшем
использовании ресурсов

Рассматривается некоторая производственная единица, которая исходя из конъюнктурных возможностей рынка, технических или технологических возможностей и имеющихся ресурсов (финансовых, временных и т.п.) может выпускать различных видов продукции (товаров), обозначаемыми индексами . Предприятие при производстве этих видов продукции вынуждено ограничиваться имеющимися видами материальных запасов, технологий, других производственных факторов (сырья, рабочей силы, оборудования и т.п.). Все эти виды факторов, необходимых для производства (и, следовательно, ограничивающих производство), называют ресурсами. Пусть число ресурсов равно , им приписывается индекс . Они ограничены и их количества равны соответственно соответствующих единиц. Вектор называется вектором ресурсов.

Известна мера полезности (экономическая выгода) производства продукции каждого вида, исчисляемая, например, по цене товара, его прибыльности, издержкам производства, степени удовлетворения потребителей и т.п. Пусть в качестве такой меры рассматривается цена реализации . Вектор называется вектором цен.

Известны также коэффициенты , показывающие сколько единиц -го ресурса необходимо для производства единицы продукции -го вида. Эти коэффициенты называются технологическими коэффициентами, а матрица , составленная из этих коэффициентов — технологической матрицей.

Через обозначим план производства, показывающий в каких количествах нужно производить указанные виды продукции.

Тогда задача нахождения производственного плана, максимизирующего объем реализации при имеющихся ограничениях является задачей линейного программирования указанного выше вида (1).

В матричном виде, учитывая введенные обозначения, эта задача может быть записана следующим образом

Дата добавления: 2014-12-29