Двойственные задачи линейного программирования

Пусть решается задача нахождения максимума при ограничениях 

Ей можно сформулировать двойственную задачу. Вводятся переменные: показывающие ценность ресурса для данного производства. За единицу стоимости примем единицу выпускаемой продукции. Стоимость всех затраченных ресурсов, идущих на изготовление единицы продукции,

Считается, что она не может быть меньше стоимости окончательного продукта (дохода)

Стоимость всех имеющихся ресурсов

Необходимо минимизировать целевую функцию и найти все

Например, если прямая задача имеет вид: целевая функция необходимо найти максиму

Ограничения по ресурсам:

Решение прямой задачи: оптимальный план

Тогда двойственная задача имеет вид: целевая функция необходимо найти минимум

Ограничения:

Решим двойственную задачу.

Вводим дополнительные переменные и превращая неравенства в уравнения. Для представления уравнений в каноническом виде вводим искусственные переменные и

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

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

Решение задачи приведено в контрольном примере № 3.

Контрольный пример №3
					Двойственный симплекс метод
	Целевая функция: F=24*y1+6000*y2+200*y3									min
Ограничения:		4*y1+1200*y2+20*y3≥5000
		1.5*y1+150*y2+20*y3≥2500
		y1,y2, y3≥0
Этап 1.
Добавляем переменные y4,y5 превращая неравенства в уравнения.
Вводим искусственно y6,y7, целевую функцию F1=y6+y7, решаем задачу min(F1)
Получим следующие коэффициенты в ограничениях и целевой функции:
	Y1	Y2	Y3	Y4	Y5	Y6	Y7	B
	4	1200	20	-1	0	1	0	5000
	1,5	150	20	0	-1	0	1	2500
F	0	0	0	0	0	1	1	min
Исходная таблица (столбец с минимальным значением C и строка
с минимальным значением B/A выделены серым цветом)
	W	0	0	0	0	0	1	1
Cb	Yb	Y1	Y2	Y3	Y4	Y5	Y6	Y7	B	B/A
1	y6	4	1200	20	-1	0	1	0	5000	4,1667
1	y7	1,5	150	20	0	-1	0	1	2500	16,667
C-строка		-5,5	-1350	-40	1	1	0	0	F1=	7500
Результат 1 шага
		0	0	0	0	0 1		1
Cb	Yb	Y1	Y2	Y3	Y4	Y5	Y6	Y7	B	B/A
0	y2	0,003	1	0,0167	-0,000833	0	0,0008	0	4,1667	250
1	y7	1	0	17,5	0,125	-1	-0,125	1	1875	107,14
C-строка		-1	0	-17,5	-0,125	1	1,125	0	F1=	1875
Результат 2 шага
		0	0	0	0	0	1	1
Cb	Yb	Y1	Y2	Y3	Y4	Y5	Y6	Y7	B	B/A
0	y2	0,002	1	0	-0,000952	0,001	0,001	-1E-03	2,381	-2500
0	y3	0,057	0	1	0,007143	-0,057	-0,007	0,0571	107,14	15000
C-строка		0	0	0	0	0	1	1	F1=	0
Вся C-строка содержит неотрицательные числа. Минимум F1 найден: F1=y6+y7=0
Этап 2.		Нахождение минимума функции F=24*y1+6000*y2+200*y3
Искусственные переменные y6, y7 и соответствующие столбцы
(выделены черным цветом) в преобразованиях не участвуют
Исходная таблица (столбец с минимальным значением C и строка
с минимальным значением B/A выделены серым цветом)
		24	6000	200	0	0	0	0
Cb	Yb	Y1	Y2	Y3	Y4	Y5	Y6	Y7	B	B/A
6000	y2	0,002	1	0	-0,000952	0,001	0,001	-1E-03	2,381	1000
200	y3	0,057	0	1	0,007143	-0,057	-0,007	0,0571	107,14	1875
C-строка		-1,714	0	0	4,285714	5,7143	-4,286	-5,714	F=	35714
Результат 1 шага
		24	6000	200	0	0	0	0
Cb	Yb	Y1	Y2	Y3	Y4	Y5	Y6	Y7	B
24	y1	1	420	0	-0,4	0,4	0,4	-0,4	1000
200	y3	0	-24	1	0,03	-0,08	-0,03	0,08	50
C-строка		0	720	0	3,6	6,4	-3,6	-6,4	F=	34000
Вся C-строка содержит неотрицательные числа.
Минимум W найден. Задача решена
y1=1000 y2=0 y3=50 y4=y5=y6=y7=0 F=34000

Сравним последнюю таблицу симплекс-метода двойственной задачи

24		1	420	0	- 0.4	0.4	1000
200		0	- 24	1	0.03	- 0.08	50
С-строка		0	720	0	3.6	6.4	F=34000

с последней таблицей симплекс-метода прямой задачи, которая (без учета ограничения ) имеет вид

5000		1	0	0.4	0	- 0.03	3.6
250		0	1	- 0.4	0	0.08	6.4
0		0	0	- 420	1	24	720
С-строка		0	0	- 1000	0	- 50	W=34000

Из сравнения таблиц можно сделать вывод, что обратную задачу мы могли бы не решать, так как при решении прямой задачи содержится решение обратной задачи (и наоборот): (то есть решение уже было получено с точностью до знака). Прямая и обратная содержит одинаковые (с точностью до знака) коэффициенты вместо , с-строка с точностью до знака совпадает со свободными членами обратной задачи,

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

В заключении сформулируем основные типы прямых и обратных задач.