Двойственная задача. Теневые цены

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

Одной из важнейших «зеркальных» связей между исходной и двойственной задачами является связь «переменные решения – теневые цены ресурсов». Для того чтобы уловить эту связь, сформулируем содержательно двойственную задачу к знакомой нам задаче об оптимальном плане выпуска продукции мебельного цеха.

4.1 Постановка двойственной задачи к задаче об оптимальном плане выпуска продукции мебельного цеха

Пусть имеется покупатель на все ресурсы, используемые для выпуска продукции мебельного цеха (ДСП, стекло и труд). Таблица параметров та же, что и для исходной задачи (см. табл. 3).

Какие цены на эти ресурсы нужно назначить, чтобы продать их было выгоднее, чем производить продукцию? Какую минимальную сумму можно выручить от продажи ресурсов при этом условии?

Таблица 3 – Параметры задачи

Ресурсы	Запасы	Продукты
Шкаф	Тумба
ДСП		3,5
Стекло
Труд
Прибыль, у.е.

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

1 м ДСП — y₁,

1 м стекла — y₂,

1 дня труда рабочего цеха — y₃.

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

Теневые цены характеризуют ценность ресурсов для производителя.

Целевая функция — это, очевидно, прибыль, которую получит производитель — продавец ресурсов, если продаст по этим ценам все имеющиеся ресурсы. Таким образом, целевая функция, записанная в таблице элементов модели, — это сумма произведений искомых цен y₁, y₂, y₃ на запасы имеющихся ресурсов, приведенных в соответствующем столбце таблицы параметров задачи. Разумеется, интерес продавца ресурсов состоит в том, чтобы продать их подороже. Однако интерес покупателя в том, чтобы купить их подешевле.

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

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

Соответственно при записи ограничений в таблице элементов модели (табл. 4) использован тот же принцип. Если производитель (продавец ресурсов) хочет продать 3,5 м ДСП, 1 м стекла и 1 день труда рабочего, то он должен получить не меньше, чем прибыль от производства одного шкафа (на который, согласно данным таблицы параметров, и идут все эти ресурсы). Аналогично если он хочет продать 1 м ДСП, 2 м стекла и 1 день труда рабочего он должен получить не меньше, чем прибыль от производства одной тумбы.

Таблица 4 – Элементы модели

Переменные решения	Целевая функция
y1 — цена 1 м ДСП y2 — цена 1 м стекла y3 — цена 1дня труда рабочего цеха	(1)
Ограничения

Симметрия исходной и двойственной задач хорошо видна из исходной таблицы параметров и элементов решения этих двух задач (табл. 5).

Таблица 5 – Соответствие между исходной и двойственной задачами

Ресурсы	Запасы (bi)	Продукты	Теневые цены (yi)
Шкаф	Тумба
ДСП		3,5		y1
Стекло				y2
Труд				y3
Прибыль, у.е.
Количество единиц каждого продукта	x1	x2
	Исходная задача	Двойственная задача
Переменные решения (хj)	х1, х2	y1, y2, y3
Целевая функция (cj)	(максимум)	(минимум)
Ограничения

Как видно из этой таблицы, в исходной задаче две переменные и три ограничения; в двойственной — наоборот: три переменные и два ограничения. Исходная задача — это задача на максимум прибыли производителя продуктов; двойственная — на минимум издержек покупателя ресурсов.

Целевая функция исходной задачи формируется как сумма произведений строки переменных (количеств продуктов разного типа х₁, х₂) на строку прибылей от производства единицы каждого продута; целевая функция двойственной задачи — как сумма произведений столбца переменных (теневых цен ресурсов y₁, y₂, y₃) на столбец запасов этих ресурсов.

Аналогично ограничение на расходы каждого из используемых ресурсов в исходной задаче формируется как сумма произведений строки переменных (x₁, x₂) на расход данного ресурса при производстве единиц каждого продукта. Ограничение на выручку от продажи ресурсов, идущих на производство данного продукта в двойственной задаче, формируется как сумма произведений столбца переменных решения (y₁, y₂, y₃) на столбец расходов каждого из используемых ресурсов на производство единицы данного продукта.

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

Здесь матрица {a_ij} может быть интерпретирована как расход каждого i-го ресурса на единицу j-го продукта. Строка целевых коэффициентов c_j тогда представляет собой величину прибыли на единицу j-го продукта.

Строка переменных x_j — количество производимых единиц j-го продукта.