Двойственность в задачах линейного программирования
С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной; первоначальная задача называется исходной, или прямой.
Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.
Хорошо разработанный математический аппарат линейного программирования позволяет не только получать с помощью эффективных вычислительных процедур оптимальный план, но и делать ряд экономически содержательных выводов, основанных на свойствах задачи, двойственной к исходной ЗЛП. Переменные двойственной задачи уi называют объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.
Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой.
Двойственная задача по отношению к исходной составляется согласно следующим правилам:
|
|
1. Целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи - на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид ≤, в задаче на минимум - вид ≥.
2. Матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица АТ в двойственной задаче получаются друг из друга транспонированием.
3. Число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи -коэффициенты при неизвестных в целевой функции исходной задачи.
5. Каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства ≤, соответствует переменная, связанная с условием неотрицательности. Если функциональное ограничение исходной задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.
Модель исходной (прямой) задачи в общем виде может быть записана следующим образом:
Модель двойственной задачи имеет вид:
Рассмотрим экономическую интерпретацию двойственной задачи на примере задачи оптимального использования ресурсов.
|
|
Сформулируем экономико-математическую модель двойственной задачи к следующей задаче
Фабрика имеет в своем распоряжении определенное количество ресурсов: рабочую силу, деньги, сырье, оборудование, производственные площади и т.п. Допустим, например, ресурсы трех видов: рабочая сила, сырье и оборудование - имеются в количестве соответственно 80 (чел./дней), 480 (кг) и 130 (станко/ч). Фабрика может выпускать ковры четырех видов. Информация о количестве единиц каждого ресурса, необходимых для производства одного ковра каждого вида, и доходах, получаемых предприятием от единицы каждого вида товаров, приведена в таблице.
Ресурсы | Нормы расхода ресурсов на единицу изделия | Наличие ресурсов | |||
ковер «Лужайка» | ковер «Силуэт» | ковер «Детский» | ковер «Дымка» | ||
Труд | |||||
Сырьё | |||||
Оборудование | |||||
Цена (тыс.руб.) |
Требуется найти такой план выпуска продукции, при котором будет максимальной общая стоимость продукции.
Количество неизвестных в двойственной задаче равно числу функциональных ограничений в исходной задаче. В исходной задаче три ограничения: по труду, по сырью и по оборудованию. Следовательно, в двойственной задаче - три неизвестных:
Y1 - двойственная оценка ресурса труд, или «цена» труда;
Y2 - двойственная оценка ресурса сырье, или «цена» сырья;
Y3 - двойственная оценка ресурса оборудование, или «цена» оборудования.
Целевая функция двойственной задачи формулируется на минимум. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи.
Необходимо найти такие «цены» на ресурсы (Yi), чтобы общая стоимость используемых ресурсов была минимальной.
Ограничения. Число ограничений в системе двойственной задачи равно числу переменных в исходной задаче. В исходной задаче четыре переменных, следовательно, в двойственной задаче четыре ограничения. Правыми частями в ограничениях двойственной задачи являются коэффициенты при неизвестных в целевой функции исходной задачи. Левая часть ограничения определяет стоимость ресурсов, затраченных на производство единицы продукции. Каждое ограничение соответствует определенному виду продукции.