Реферат: Двойственный симплекс-метод и доказательство теоремы двойственности

Многие задачи линейного программирования первоначально ста­вятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования.

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.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^-1 A = ,

(1.6) A ₀ =DX*; D ^-1 A ₀ = 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,