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

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

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

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

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

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

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)
		Шкаф	Тумба
ДСП	350	3,5	1	y1
Стекло	240	1	2	y2
Труд	150	1	1	y3
Прибыль, у.е.		200	100
Количество единиц каждого продукта		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-го продукта.