Двойственная задача

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

Предположим, что нужно узнать, при каких ценах на ресурсы, используемые для производства бетонных изделий (см. таблицу «Параметры задачи» Рис. 10), будет выгоднее продать эти ресурсы, чем делать из них продукцию? Какую минимальную сумму можно получить в виде прибыли от продажи ресурсов?

Построим модель данной задачи. Обозначим через у₁, у₂, у₃ цены на единицу бетона, арматуры и стоимость труда за один рабочий день. Такие цены характеризуют степень ценности ресурса для производителя и называются теневыми ценами. Целевая функция - это с одной стороны прибыль, который может быть получен от продажи всех ресурсов по данным ценам. Он равен сумме произведений цен на значение запаса соответствующего ресурса. Но с точки зрения покупателя ресурсов значение целевой функции - это его расходы, желательно сделать меньше (купить дешевле). То есть значение целевой функции нужно минимизировать. Что касается ограничений задачи, то необходимо учесть, что производитель стремится продать ресурсы по таким ценам, чтобы прибыль была не менее того, который он получил бы при производстве продукции из этих ресурсов. Таким образом, например, ему надо продать 3,5 куб.м. бетона, 1 упаковка арматуры и 1 день труда в сумме не менее, чем прибыль от производства одного лестничного марша, то есть должно выполняться ограничения

3.5у₁+1у₂+1у₃ ≥ 200.

На Рис. 16 представлена ​​модель двойственной задачи.

Для нахождения решения в окне Поиск решения необходимо установить переключатель на минимальное значение, а в параметрах указать, что модель линейная и переменные имеют неотрицательные значения. Поиск решения дает следующий результат: теневая цена на бетон - 40, на арматуру - 0, на труд - 60. Значение затрат равна 23000 руб. и, заметим, оно в точности совпадает со значением прибыли в прямой задачи (рис. 17).

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