2.2 Построение и решение задачи, двойственной к исходной. Сравнение решения прямой и двойственной задач

Рассмотрим соотношение прямой и двойственной задач:

(2.2)

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

Исходная задача:

Найти максимальное значение функции F(X)=-1X₁+3X₂-5X₃ (max)

при следующих ограничениях:

0X1	+	3X2	-	2X3		=	3
-4X1	-	2X2	+	1X3		≥	-18
-3X1	+	0X2	-	2X3		≤	-15
4X1	-	1X2	+	3X3		≤	33

x_j0 (j=1...3)

Строим двойственную задачу:

Так как в прямой задаче требуется найти минимум функции, то приведем первоначальное условие к виду {F(x) = B^T x| A^T x≥C, x_j ≥0, j = 1,m}

Для достижения нужного вида домножим 2-e неравенство на -1 В результате получим следующие матрицы:

Транспонируем матрицу A:

Поменяем местами вектора B и C:

Двойственная задача будет иметь 4 переменные, так как прямая содержит 4 ограничения. В соответствии запишем двойственную задачу в виде:

F(Y)=3Y₁+18Y₂-15Y₃+33Y₄ (min)

Так как в прямой задаче есть ограничение равенство, то на у₁, соответствующая переменная двойственной задачи, не накладывается условие неотрицательности.

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

0Y1	+	4Y2	-	3Y3	+	4Y4		≥	-1
3Y1	+	2Y2	+	0Y3	-	1Y4		≥	3
-2Y1	-	1Y2	-	2Y3	+	3Y4		≥	-5

Y1	≥	0
Y2	≥	0
Y3	≥	0
Y4	≥	0

Введем дополнительные переменные Y₅, Y₆, Y₇. Ограничения примут вид:

0Y1	-	4Y2	+	3Y3	-	4Y4	+Y5	=	1
-3Y1	-	2Y2	+	0Y3	+	1Y4	+Y6	=	-3
2Y1	+	1Y2	+	2Y3	-	3Y4	+Y7	=	5

Y_i≥0 Составим симплекс-таблицу:

Базисные переменные	Свободные члены	Y1	Y2	Y3	Y4
Y5	1	0	-4	3	-4
Y6	-3	-3	-2	0	1
Y7	5	2	1	2	-3
F	0	3	18	-15	33

Для нахождения ведущей строки найдем максимальный по модулю отрицательный свободный член (-3). Ведущая строка - Y₆. В строке Y₆ так же найдем максимальный по модулю отрицательный свободный член (-3). Столбец Y₁- ведущий. Пересчитаем таблицу

Базисные переменные	Свободные члены	Y6	Y2	Y3	Y4
Y5	1	0	-4	3	-4
Y1	1	-0.333	0.667	0	-0.333
Y7	3	0.667	-0.333	2	-2.333
F	-3	1	16	-15	34

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-15). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.

Пересчитаем таблицу

Базисные переменные	Свободные члены	Y6	Y2	Y5	Y4
Y3	0.333	0	-1.333	0.333	-1.333
Y1	1	-0.333	0.667	0	-0.333
Y7	2.333	0.667	2.333	-0.667	0.333
F	2	1	-4	5	14

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке F есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке F (-4). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца. Пересчитаем таблицу

Базисные переменные	Свободные члены	Y6	Y7	Y5	Y4
Y3	1.667	0.381	0.571	-0.048	-1.143
Y1	0.333	-0.524	-0.286	0.19	-0.429
Y2	1	0.286	0.429	-0.286	0.143
F	6	2.143	1.714	3.857	14.571

Получили решение задачи:

y₁=0.333;y₂=1;y₃=1.667;F_min=-6.

Установим соответствия между переменными прямой и двойственной задач.

Исходные переменные Дополнительные переменные

прямой задачи

x₁ x₂ x₃ R1 x₄ x₅ x₆

y₅ y₆ y₇ y₁ y₂ y₃ y₄

Дополнительные переменные Исходные переменные

двойственной задачи двойственной задачи

Соответствие не означает равенство. Оптимальное решение прямой задачи получается приравниванием ее исходных переменных при соответствующим им переменным в F-строке

F_max(x)=F_min(y)=-6