Пример решения двойственной задачи симплексным методом.

Z = 2X1 + 6X2 + X3 (min)

 

5X1 + X2 + 4X3 ≥5,

X1 + 3X2 + 7X3 ≥3.

 

X1≥0, X2≥0, X3≥0.

Решение.

Запишем матрицу исходной задачи в виде.

5	1	4	5
1	3	7	3
2	6	1	φ min

Транспонируем составленную матрицу. В результате получим матрицу двойственной задачи:

5	1	2
1	3	6
4	7	1
5	3	f max

По полученной матрице запишем двойственную задачу.

F = 5Y1 + 3Y2  (max)

5Y1 + Y2 ≤ 2,

Y1 + 3Y2 ≤ 6,

4Y1 + 7Y2 ≤1.

 

Y1≥0, Y2≥0.

Задача записана в симметричной фоме записи. Приведем задачу к канонической форме записи, для этого введем дополнительные переменные Y3, Y4, Y5. Расширенная система задачи имеет вид:

5Y1 + Y2   + Y3  = 2

Y1 + 3Y2  + Y4 = 6

 4Y1 + 7Y2   + Y5 = 1

Условия неотрицательности примут вид:

Yj≥0 (j=1,..,5).

Заполним первую симплексную таблицу (Табл. 1), в которой переменные Y3, Y4, Y5 являются базисными, переменные Y1, Y2 свободными. Последняя строка заполняется коэффициентами целевой функции с противоположным знаком.

Таблица 1. Первая (начальная) симплексная таблица

Базис	C	Свободный член	Переменные					Оценочное отношение
			Y1	Y2	Y3	Y4	Y5
			5	3	0	0	0
Y3=	0	2	5	1	1	0	0	0,4
Y4=	0	6	1	2	0	1	0	6
Y5=	0	1	4	7	0	0	1	0,25
F		0	-5	-3	0	0	0

В полученной таблице в F-строке есть отрицательные элементы, следовательно план не является оптимальным. Производим симплексное преобразование с разрешающим элементом 4 и переходим к таблице 2.

 

 

Таблица 2. Вторая симплексная таблица.

Базис	C	Свободный член	Переменные					Оценочное отношение
			Y1	Y2	Y3	Y4	Y5
			5	3	0	0	0
Y3=	0	0,75	0	-7,75	1	0	-1,25
Y4=	0	5,75	0	0,25	0	1	-0,25
Y1=	5	0,25	1	1,75	0	0	0,25
F		1,25	0	5,75	0	0	1,25

Получаем табл. 2. в F-строке которой нет отрицательных элементов.

Следовательно, опорный план (0,25; 0; 0,75; 5,75; 0) является опти­мальным, а соответствующее ему значение 1,25 целевой функции будет макси­мальным.

Запишем соответствия между переменными двойственных задач:

   Y3  X1, Y4 X2, Y5  X3, Y1  X4, Y2  X5.

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

X1 = 0; X2 = 0; X3 = 1,25; X4 = 0; X5 = 5,75. Экстремальные значения целевых функций двойственных задач совпадают Fmax = Zmin = 1,25.