Экономическая модель оптимального плана производства трех видов изделий, максимизирующего прибыль
Запись {£, =, ³} в ограничениях означает, что возможен один из знаков (£, = или ³).
Решение Х = (х1, х2, …, хn), при котором выполняются все ограничения, называется допустимым. Допустимое решение, при котором функция F принимает оптимальное значение (максимум или минимум), называется оптимальным.
Оптимальное распределение ресурсов. Анализ отчетов
Рассмотрим задачу планирования производства продукции при ограничениях на ресурсы.
Постановка задачи. Для производства продукции n типов требуются ресурсы m видов. Нормы расхода ресурсов на производство одной единицы продукции каждого типа заданы матрицей {aij}, где aij - количество ресурса i-го вида, необходимое для производства одной единицы продукции j-го типа. Известно количество ресурсов (bi, где i = 1, ., m) каждого вида, которое имеется в наличии у предприятия. Известны также величины прибыли (Сj), которую получит предприятие при реализации одной единицы продукции j-го типа. Требуется найти оптимальный план производства продукции, т. е. количество продукции каждого типа, которое нужно произвести, чтобы получить наибольшую прибыль.
Обозначим через xj количество продукции j-го типа, которое планируется выпустить (j = 1, ., n). Тогда математическая модель задачи будет выглядеть следующим образом:
Целевая функция задачи представляет собой общую прибыль от производства всей продукции. Ограничения выражают условие, при котором потребление ресурса i-го вида не должно превышать запаса этого ресурса (bi). Условия неотрицательности переменных вытекают из смысла переменной xj: количество продукции не может быть отрицательным.
Канонической называется следующая форма записи ЗЛП:
Чтобы привести к виду равенства ограничение вида
,
в левую часть неравенства прибавляют дополнительную переменную:
.
Аналогично, чтобы привести к каноническому виду ограничение вида
,
из левой части неравенства вычитают дополнительную переменную:
.
Дополнительные переменные вводятся в целевую функцию с коэффициентами, равными 0:
.
Таким образом, задача может быть записана в следующем каноническом виде:
Экономический смысл переменных yi (i = 1, …, m) следующий: это остатки ресурсов каждого вида. Если при оптимальном решении какой-либо ресурс будет использован полностью, то ограничение исходной задачи (13) будет выполнено в виде равенства, а yi = 0. Такое ограничение в отчетах Exсel называется связанным.
Двойственность в линейном программировании
С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача при этом называется исходной, или прямой. Связь этих задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.
Рассмотрим двойственную задачу, связанную с рассматриваемой нами задачей планирования производства продукции.