Л8.2 Двойственные задачи линейного программирования

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

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

Z = p ₁ x ₁ + … + p_nx_n (1.3.1)

при ограничениях-неравенствах

a_{i 1} x ₁ + … + a_inx_n £ a_i; (i = ), (1.3.2)

при ограничениях-равенствах

a_{i 1} x ₁ + … + a_inx_n = a_i; (i = ),

при несвободных переменных

x_j ³ 0 (j = ), (1.3.3)

при свободных переменных

x_j ³£ 0 (j = ).

Определение 1.3.1. Задача линейного программирования, состоящая в нахождении минимального значения функции

W = a ₁ u ₁ + … + a_mu_m (1.3.4)

при несвободных переменных

u_i ³ 0 (i = ), (1.3.5)

при свободных переменных

u_i ³£ 0 (i = ),

при ограничениях-неравенствах

a _{1 j}u ₁ + … + a_mju_m ³ p_j (j = ), (1.3.6)

при ограничениях-равенствах

a _{1 j}u ₁ + … + a_mju_m = p_j; (j = )

называется двойственной по отношению к задаче (1.3.1) – (1.3.3).

Сравнивая две сформулированные задачи, видим, что двойственная задача по отношению к прямой составляется по следующим правилам:

1) максимизация целевой функции (1.3.1) прямой задачи заменяется минимизацией целевой функции (1.3.4) двойственной задачи;

2) свободные члены a ₁, …, a_m ограничений (1.3.2) прямой задачи служат коэффициентами целевой функции двойственной задачи, коэффициенты p ₁, …, p_n целевой функции (1.3.1) прямой задачи – свободными членами ограничений (1.3.6) двойственной задачи (так что число переменных двойственной задачи равно m – числу ограничений прямой задачи, а число ограничений двойственной задачи n – числу переменных прямой задачи);

3) матрицей коэффициентов ограничений двойственной задачи служит матрица A^т, получаемая транспонированием матрицы A коэффициентов ограничений прямой задачи;

4) каждому ограничению-неравенству a_{i 1} x ₁ + … + a_inx_n £ a_i (³ a_i) (i = 1, …, k) прямой задачи соответствует несвободная переменная двойственной задачи с противоположным знаком неравенства, т.е.

u_i ³ 0 (u_i £ 0) (i = );

5) каждому ограничению-равенству a_{i 1} x ₁ + … + a_inx_n = a_i; (i = ) прямой задачи –свободная переменная u_i двойственной задачи, т.е.

u_i ³£ 0 (i = );

6) каждой несвободной переменной x_j ³ 0 (j = ) прямой задачи – ограничение-неравенство a _{1 j}u ₁ + … + a_mju_m ³ p_j (£ p_j), (j = ) двойственной задачи с тем же знаком неравенства;

7) каждой свободной переменной x_j ³£ 0 (j = ) прямой задачи – ограничение-равенство a _{1 j}u ₁ + … + a_mju_m = p_j; (j = ) двойственной задачи.

Параллельная запись обеих задач выглядит так:

Прямая задача	Двойственная задача
максимизировать линейную функцию Z = p 1 x 1 + … + pnxn при ограничениях-неравенствах ai 1 x 1 + … + ainxn £ ai (i = )	минимизировать линейную функцию W = a 1 u 1 + … + amum При несвободных переменных ui ³ 0 (i = )
при ограничениях-равенствах ai 1 x 1 + … + ainxn = ai; (i = )	При свободных переменных ui ³£ 0 (i = )
при несвободных переменных xj ³ 0 (j = )	При ограничениях-неравенствах a 1 ju 1 + … + amjum ³ pj (j = )
при свободных переменных xj ³£ 0 (j = )	При ограничениях-равенствах a 1 ju 1 + … + amjum = pj; (j = )

Прямую задачу можно рассматривать как двойственную по отношению к своей двойственной, т.е. обе задачи являются взаимно двойственными.

Условия пары взаимно двойственных задач можно совместить в одной таблице. Для этого запишем ограничения прямой задачи в виде

Y_i = a_{i 1}(-x ₁) + … + a_in (-x_n) + a_i ³ 0; (i = );

0 = a_{i 1}(-x ₁) + … + a_in (-x_n) + a_i; (i = ),

а ограничения двойственной задачи – в виде

v_j = a _{1 j} u ₁ + … + a_mju_m - p_j ³ 0 (j = );

0 = a _{1 j}u ₁ + … + a_mju_m - p_j; (j = )

и совместим их в следующей таблице

			...			...
			...			...
			...			...
...	...	.	.	.	.	.	.	...
			...			...
			...			...
...	...	.	.	.	.	.	.	...
			...			...
			...			...

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

Основная (первая) теорема двойственности. Пусть рассматривается пара двойственных задач. Тогда:

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

;

2) если у одной из этих задач целевая функция не ограничена, то двойственная ей задача противоречива;

3) если одна из задач противоречива, то двойственная ей задача либо имеет неограниченную целевую функцию, либо также противоречива.

Контрольні запитання

1. Подвійність у лінійному програмуванні...

2. 1 теорема подвійності.

3. 2 теорема подвійності.

4. Економічна інтерпретація пари подвійних задач.

Рекомендована література: [1,3,8,9,10]

Тема 5.