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

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

Найти вектор двойственных оценок

(у₁, у₂, у₃),

минимизирующий общую всех ресурсов

f = 168 * y₁+ 60 *y₂+ 112 *y₃

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

2 * у1	+	у2	+	3 * y3	>=	34
		5 * у2	+	4 * у3	>=	20
2 * у1	+	4 * y2			>=	8
3 * у1	+	2 * y2	+	у3	>=	23

причем оценки ресурсов не могут быть отрицательными

у₁>= 0, у₂>= 0, у₃>= 0.

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений х(х₁,х₂,х₃) и у(у₁,у₂,у₃) пары двойственных задач необходимо и достаточно выполнение условий

х1 * (	3 * у1	+		+	y3	-	18	) = 0
х2 * (	2 * у1		у2	+	3 * у3	-	19	) = 0
х3 * (		+	4 * y2		5 * у3	-	8	) = 0
х4 * (	3 * у1	+	2 * y2	+		-	5	) = 0

у1 * (	3* х1		2* х2	+		+	3 * х4	-	168	) = 0
у2 * (		+	х2	+	4 * x3	+	2 * х4	-	60	) = 0
у3 * (	х1	+	3* х2		5* x3	+		-	112	) = 0

Ранее (см. Задачу 1) было найдено, что в решении исходной задачи х₁>0 и х₂>0. Поэтому

3* у1	+	у2	+	y3	-	18	= 0
2* у1	+	y2	+	3*у3	-	19	= 0

Если же учесть, что х₆ ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю:

y₂= 0

то приходим к системе уравнений

3 * у1	+	y3	-	18	= 0
2 * у1	+	3*у3	-	19	= 0

откуда следует у₁= 5,у₃= 3. Таким образом, получили двойственные оценки ресурсов

у₁= 5, у₂= 0, у₃= 3,

причем общая оценка всех ресурсов равна f_min= 1176

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

Задача о «расшивке узких мест производства»

При выполнении оптимальной производственной программы 1-й и 3-й ресурсы используются полностью, т.е. образуют “узкие места производства”. Будем их заказывать дополнительно. Пусть T(t₁, t₂, t₃) - вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие

H + Q^-1* T >= 0

Задача состоит в том, чтобы найти вектор

T (t₁, t₂, t₃)

максимизирующий суммарный прирост прибыли

w = 5 * t₁+ 3 * t₃

при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)

40		3/7	0	-2/7		t1		0
36	+	1/7	1	-3/7	*	0	>=	0
24		-1/7	0	3/7		t3		0

предполагая, что дополнительно можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида

t1				168
0	=<	1/3	*	60
t3				112

причем по смыслу задачи

t₁>= 0, t₃>= 0

-3 * t1	+	2 * t3	=<	280
- t1	+	3 * t3	=<	252
t1	-	3 * t3	=<	168
t1			=<	56
		t3	=<	112/3

Программа “расшивки” имеет вид

t₁= 56, t₂= 0, t₃= 112/3

и прирост прибыли составит

w = 492

Сводка результатов

Таблица 2

cj	18	19	8	5	bi	x4+i	yi	ti
	3	2	0	3	168	0	5	56
aij	0	1	4	2	60	36	0	0
	1	3	5	0	112	0	3	112/3
xj	40	24	0	0	1176			492
 j	0	0	7	10