Вторая теорема двойственности

Теорема:Для того чтобы два допустимых решения и пары двойственных задач были их оптимальными решениями необходимо и достаточно, чтобы они удовлетворяли системе уравнений

(1)

Замечание: Теорема верна для симметричной двойственной пары, для задач в канонической и общей форме соотношения (1) верны только для ограничений в виде неравенств и для неотрицательных переменных.

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

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

Соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи:

 

Переменные исходной задачи
Первоначальные	Дополнительные
Х1 Х2 … Хj … Xn	Xn+1 Xn+2 … Xn+I … Xn+m
Ym+1 Ym+2 … Ym+j … Ym+n	Y1 Y2 … Yi … Ym
Дополнительные	Первоначальные
Переменные двойственной задачи

 

Пример.

При решении прямой задачи

F = 2x1 + 3х2 à max при ограничениях:

 

(Слайд 6)

х1 + 3х2 <= 18

2х1 + х2 <= 16

х2 <= 5

3x1 <= 21

х1, х2 >= 0

симплекс-методом получили на последнем шаге:

F= 24 – 4/5х3 – 3/5х4 при оптимальном БР Х* =(6; 4; 0; 0; 1; 3).

 

Базис	Свободный член	Переменные	Оценочное отношение
Х1	Х2	Х3	Х4	Х5	Х6
Х1				-1/5	3/5
Х5				-2/5	1/5
Х2				2/5	-1/5
Х6				3/5	-9/5
F				4/5	3/5

 

Если решить симплекс-методом двойственную задачу:

Z =18y1 + 16y2 +5y3 + 21y4 à min при ограничениях:

 

y1 + 2y2 + 3y4 >= 2

3y1 + y2 + y3 >= 3

y1, y2, y3, y4 >= 0

то получим на последнем шаге:

Z = 24 + y3 + 3y4 + 6y5 + 4y6 при оптимальном БР Y* =(4/5; 3/5; 0; 0; 0; 0).

 

Базис	Свободный член	Переменные	Оценочное отношение
Y1	Y2	Y3	Y4	Y5	Y6
Y1	4/5			2/5	-3/5	1/5	-2/5
Y2	3/5			-1/5	9/5	-3/5	1/5
Z

 

Замечание. Если в одной из взаимно двойственных задач нарушается единственность оптимального решения, то оптимальное решение другой двойственной задачи вырожденное.

С помощью теорем двойственности можно, решив симплекс-методом исходную задачу, найти оптимум и оптимальное решение ДЗ.

Метод, при котором сначала решают симплекс-методом ДЗ, а потом оптимум и оптимальное решение исходной задачи находятся с помощью теорем двойственности, называется двойственным симплекс-методом. Этот метод применяется, когда первое БР исходной задачи недопустимое или, например, число ее ограничений m больше числа переменных n.