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

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

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

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

сается ограничений задачи, то здесь необходимо учесть, что производитель стремится продать ресурсы по таким ценам, чтобы прибыль была не меньше той, которую он получил бы при производстве продукции из этих ресурсов. Таким образом, например, ему надо продать 3,5 куб.м, бетона, 1 упаковку арматуры и 1 день труда в сумме не меньше, чем прибыль от производства одного лестничного марша. То есть должно выполниться ограничение

3.5^ + ly2 +1 у3 gt; 200.

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

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

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

На каждое изделие расходуется количество комплектующих, указанное в таблице. Прибыль от производства одного телевизора составляет 90 у.е., одной стереосистемы — 50 и аудиосистемы — 45. Необходимо найти оптимальное соотношение объемов выпуска изделий, при котором прибыль от производства всей продукции будет максимальной.

1. Сформулируйте и решите двойственную задачу к задаче из пункта 2.