Первая (основная) теорема двойственности

Теорема: Если одна из сопряженных задач имеет оптимальное решение , то и вторая имеет оптимальное решение _, при этом

Fmax = Zmin или F(X*) = Z(Y*).

Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы.

Пример применения 1-ой (основной) теоремы двойственности

Задача. Дана задача (рассматривали в лекции по симплекс-методу):

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

х1 + 3х2 <= 18

2х1 + х2 <= 16

х2 <= 5

3x1 <= 21

х1, х2 >= 0

и двойственная к ней:

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

y1 + 2y2 + 3y4 >= 2

3y1 + y2 + y3 >= 3

y1, y2, y3, y4 >= 0

Прямая задача была решена в лекции о симплекс-методе и был получен ответ F max = 24. если решить симплекс-методом двойственную задачу, то будет получен ответ, что Z min = 24. Т.е. заключение первой части теоремы двойственности верно.

Экономический смысл 1-ой (основной) теоремы двойственности.

План производства Х* = (х1*, х2*, …,хn*) и набор цен (оценок) ресурсов Y* = (y1*, y2*, …, ym*) оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная по известным заранее «ценам» с1, с2, .., сn, равна затратам на ресурсы по «внутренним» (определенным только из решения задачи) ценам y1, y2, …, ym. Так в рассмотренной выше задаче оптимумы F max и Z min = 24, для всех остальных планов F(X) <= 24, а Z(Y) >= 24.

Можно интерпретировать экономический смысл 1-ой (основной) теоремы двойственности и так: предприятию безразлично, производить ли продукцию на основе оптимального плана Х* = (х1*, х2*, …, хn*) и получить максимальную прибыль (выручку) F max либо продавать ресурсы по оптимальным «внутренним» ценам Y* = (y1*, y2*, …, ym*) и возместить от продажи равные ей минимальные затраты на ресурсы Z min.

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

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

(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	6	1	0	-1/5	3/5	0	0
Х5	1	0	0	-2/5	1/5	1	0
Х2	4	0	1	2/5	-1/5	0	0
Х6	3	0	0	3/5	-9/5	0	1
F	24	0	0	4/5	3/5	0	0

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

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	1	0	2/5	-3/5	1/5	-2/5
Y2	3/5	0	1	-1/5	9/5	-3/5	1/5
Z	24	0	0	1	3	6	4

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

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

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