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

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

Так как 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*=minZ(X ).

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

Докажем теперь, что Y* является оптимальным планом. Умножим (1.1) на любой план Y двойственной задачи, а (1.2) — на любой план X исходной задачи: YAX=YA ₀ = 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 ) £ -¥ . Это выражение лишено смысла, следовательно, двойственная задача не имеет решений.

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

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

Исходная задача. Найти минимальное значение линейной функции Z = x₂ – x₄ – 3x₅ при ограничениях

x₁ + 2x₂ - x₄ + x₅ = 1,