2. .Несимметричные двойственные задачи. Теорема двойственности

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

И с х о д н а я з а д а ч а. Найти матрицу-столбец X = (x₁, x₂, …, x_n), которая удовлетворяет ограничениям

(1.1) AX = A₀, Х > 0

и минимизирует линейную функцию Z = СХ.

Д в о й с т в е н н а я з а д а ч а. Найти матрицу-строку Y = (y₁, y₂, …, y_m), которая удовлетворяет ограничениям

(1.2) YA ≤ С

и максимизирует линейную функцию f = YA₀

В обеих задачах C = (c₁, c₂, …, c_n) - матрица-строка, A₀ = (b₁, b₂, …, b_m) — матрица-столбец, А = (a_ij) — матрица коэффициентов системы ограничений. Связь между оптимальными планами пары двой­ственных задач устанавливает следующая теорема.

Теорема (теорема двойственности). Если из пары двойствен­ных задач одна обладает оптимальным планом, то и другая имеет ре­шение, причем для экстремальных значений линейных функций выпол­няется соотношение

min Z = max f.

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

Д о к а з а т е л ь с т в о. Предположим, что исходная задача об­ладает оптимальным планом, который получен симплексным методом. Не нарушая общности, можно считать, что окончательный базис со­стоит из т первых векторов A₁, A₂, ., A_m. Тогда последняя симплекс­ная таблица имеет вид табл. 1.1.

Таблица 1

i	Базис	С базиса	A0	C1	C2	…	Cm	Cm+1	…	cn
				A1	A2	…	Am	Am+1	…	An
1 2 . . . m	A1 A2 . . . Am	C1 C2 . . . Cm	x1 x2 . . . xm	1 0 . . . 0	0 1 . . . 0	. . . . . .	0 0 . . . 1	x1, m+1 x2, m+1 . . . xm, m+1	… … . . . …	x1n x2n . . . xmn
m+1	Zi - Cj		Z0	Z1 – C1	Z2 – C2	.	Zm – Cm	Zm+1 – Cm+1	…	Zn – Cn

Пусть D — матрица, составленная из компонент векторов оконча­тельного базиса A₁, A₂, ., A_m; тогда табл. 1.1 состоит из коэффици­ентов разложения векторов A₁, A₂, ., A_n исходной системы по векто­рам базиса, т. е. каждому вектору A_j в этой таблице соответствует та­кой вектор X_j что

(1.3) A_j = DX_j(j= 1,2, , , n).

Для оптимального плана получаем

(1.4) A₀ = DX*, где X* = (x*₁, x*₂, …, x*_m).

Обозначим через матрицу, составленную из коэффициентов раз­ложения векторов А_j (j = 1, 2, ., n), записанных в табл. 1.1. Тогда, учитывая соотношения (1.3) и (1.4), получаем:

(1.5) A = D , D-1A = ,

(1.6) A₀=DX*; D-1A₀ = X*,

(1.7) min Z= C*X*,

(1.8) = C* -C ≤ 0,

где С* = (C*₁, C*₂, …, C*_m), С = (C₁, C₂, …, C_m, C_m+1, …, C_n), a = (C*X₁ – C₁; С*Х₂ - С₂, ., C*X_n – C_n) = (Z₁ – С₁; Z₂ - C₂; ., Z_n - C_n) — вектор, компоненты которого неположительны, так как они совпадают с Z_j — C_j ≤ 0, соответствующими

оптимальному плану.

Оптимальный план исходной задачи имеет вид X* = D-1 А₀, поэтому оптимальный план двойственной задачи ищем в виде

(1.9) Y* = C*D-1.

Покажем, что Y* действительно план двойственной задачи. Для этого ограничения (1.2) запишем в виде неравенства YA - С ≤ 0, в левую часть которого подставим Y*. Тогда на основании (1.9), (1.5) и (1.8) получим

Y* А – С = С* D-1А – С = С* - С ≤ 0,

откуда находим Y*A ≤ С.

Так как Y* удовлетворяет ограничениям (1.2), то это и есть план двойственной задачи. При этом плане значение линейной функции двой­ственной задачи f (Y*) = Y*A₀. Учитывая соотношения (1.9), (1.6) и (1.7), имеем

(1.10) f (Y*) = Y*A₀ = C*D-1 A₀ = C*X* = min Z(X).

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

Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) — на любой план X исходной задачи: YAX=YA0=f (Y), YAX ≤ СХ = Z (X), отсюда следует, что для любых планов Х и Y выполняется неравенство

(1.11) f (Y) ≤ Z (X).

Этим же соотношением связаны и экстремальные значения max f (Y) ≤ min Z (Х). Из последнего неравенства заключаем, что максималь­ное значение линейной функции достигается только в случае, если max f (Y) = min Z (X), но это значение [см. (1.10)] f (Y) достигает при плане Y*, следовательно, план Y* — оптимальный план двойственной задачи.

Аналогично можно доказать, что если двойственная задача имеет решение, то исходная также обладает решением и имеет место соотно­шение max f (Y) = min Z (X).

Для доказательства второй части теоремы допустим, что линейная функция исходной задачи не ограничена снизу. Тогда из (1.11) следу­ет, что f (Y)≤Y. Это выражение лишено смысла, следовательно, двойственная задача не имеет решений.

Аналогично предположим, что линейная функция двойственной за­дачи не ограничена сверху. Тогда из (1.11) получаем, что Z (X) ³ +Y. Это выражение также лишено смысла, поэтому исходная задача не име­ет решений.

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