5. Двойственные злп

Пусть дана общая ЗЛП:

(1)

(2)

(3)

Задача, состоящая в определении min функции

(4)

при условиях

(5)

(6)

называется двойственной по отношению к задаче (1) - (3).

Задачи (1) - (3) и (4) - (6) образуют пару задач, называемую в линейном программировании двойственной парой.

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

1. Целевая функция исходной задачи (1) - (3) исследуется на max, а целевая функция двойственной задачи (4) - (6) – на min.

2. Матрица

, (7)

составленная из коэффициентов при неизвестных в системе (2) ограничений исходной задачи (1)-(3), и аналогичная матрица

(8)

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

3. Число переменных в двойственной задаче (4) - (6) равно числу ограничений в системе (2) исходной задачи (1) - (3), а число ограничений в системе (5) двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (4) двойственной задачи (4) - (6) являются свободные члены в системе (2) ограничений исходной задачи (1) - (3), а правыми частями в ограничениях системы (5) двойственной задачи – коэффициенты при неизвестных в целевой функции (1) исходной задачи.

5. Если переменная исходной задачи (1) - (3) может принимать только лишь неотрицательные значения, то j-ое ограничение в системе (5) двойственной задачи (4)-(6) является неравенством вида . Если же переменная может принимать как положительные, так и отрицательные значения, то j-ое ограничение в системе (5) представляет собой уравнение. Если i-ое ограничение в системе (2) является неравенством, то i-ая переменная двойственной задачи . Если же i-ое ограничение есть уравнение, то переменная может принимать как положительное, так и отрицательное значения.

Двойственные пары задач подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (2) прямой задачи и ограничения (5) двойственной задачи являются соответственно неравенствами вида и . Таким образом, переменные обеих задач могут принимать лишь неотрицательные задачи.

Связь между решениями прямой и двойственной задач

Рассмотрим пару двойственных задач, образованную основной ЗЛП и двойственной к ней.

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

(9)

при условиях

(10)

(11)

Двойственная задача:

(12)

при условиях

(13)

Лемма 1. Если X – некоторый опорный план исходной задачи (9)-(11), а Y – произвольный план двойственной задачи (12)-(13), то значение целевой функции исходной задачи на плане X всегда не превосходит значения целевой функции на плане Y, т.е.

Лемма 2. Если для некоторых планов X* и Y* задач (9)-(11), то X* - оптимальный план исходной задачи, а Y* - оптимальный план двойственной задачи.

Теоремы двойственности.

Теорема 1. Если одна из пары двойственных задач (9) -(11) или (12)-(13) имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т.е. Если же целевая функция одной из пары двойственных задач не ограничена (для исходной задачи (9)-(11) – сверху, для двойственной (12)-(13) – снизу), то другая задача вообще не имеет планов.

Теорема 2. План задачи (9) - (11) и план задачи (12)-(13) являются оптимальными планами этих задач тогда и только тогда, когда выполняется равенство

Геометрическая интерпретация двойственных задач.

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

1. обе задачи имеют планы;

2. планы имеет только одна задача;

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

Пример. Для задачи:

составить двойственную задачу и найти решение обеих задач.

Решение.

Двойственная задача имеет вид:

Как в исходной, так и в двойственной задаче, число неизвестных равно двум. Следовательно, их решение можно найти, используя геометрическую интерпретацию ЗЛП.

К ак видно из представленных выше рисунков, максимальное значение целевая функция исходной задачи принимает в точке В(2; 6). Следовательно, X*=(2; 6) является оптимальным планом, при котором .

Минимальное значение целевая функция двойственной задачи принимает в точке D(1;4). Значит, Y*=(1;4) является оптимальным планом двойственной задачи, при котором

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

Таким образом, при любом плане исходной задачи значение целевой функции не превосходит значения целевой функции двойственной задачи при её произвольном плане.

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

Переменные исходной задачи
Первоначальные	Дополнительные
Дополнительные	Первоначальные
Переменные двойственной задачи

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

Если среди векторов , составленных из коэффициентов при неизвестных в системе уравнений (10), имеется m единичных, то компоненты оптимального плана двойственной задачи совпадают с соответствующими элементами (m+1)-ой строки столбцов единичных векторов в последней симплекс-таблице, если данный коэффициент , и равны сумме соответствующего элемента этой строки и если .

Если пара двойственных задач симметричная, т.е. система ограничений исходной задачи содержит неравенства вида ≤, то компоненты оптимального плана двойственной задачи совпадают с соответствующими числами (m+1)-ой строки последней симплекс-таблицы решения исходной задачи.

Указанные числа стоят в столбцах векторов, соответствующих дополнительным переменным.

Пример. Для ЗЛП:

,

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

Решение.

Запишем исходную ЗЛП в каноническом виде.

Двойственная ЗЛП:

Решим исходную ЗЛП симплекс-методом.

i	Базис	Сб	P0	1	-1	0	0	0
				P1	P2	P3	P4	P5
1	P3	0	2	-2	1	1	0	0	*
2	P4	0	2	1	-2	0	1	0
3	P5	0	5	1	1	0	0	1
4			0	-1	1	0	0	0
1	P3	0	6	0	-3	1	2	0	**
2	P1	1	2	1	-2	0	1	0
3	P5	0	3	0	3	0	-1	1
4			2	0	-1	0	1	0
1	P3	0	9	0	0	1	1	1
2	P1	1	4	1	0	0	-2/3	2/3
3	P2	-1	1	0	1	0	-1/3	1/3
4			3	0	0	0	2/3	1/3

где * и **

Для того, чтобы найти оптимальный план двойственной задачи, установим соответствие между основными и дополнительными (базисными) переменными прямой и двойственной задач.

Прямая задача

Двойственная задача

Компоненты оптимального плана двойственной задачи расположены в последней строке последней симплекс-таблицы в столбце векторов , образующих единичный базис исходной ЗЛП.

Y*= (0, 2/3, 1/3).