Инструменты пользователя

Инструменты сайта


examination:mo:question7

№7 Двойственность в линейном программировании. Пара двойственных задач линейного программирования. Теорема двойственности.

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

Первая теорема двойственности.

Пусть рассматривается пара двойственных задач:

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

Доказательство: Пусть основная задача (7.1) имеет конечное решение и получена окончательная симплексная таблица:

Так как данная таблица, по предположению, соответствует оптимальному решению задачи (7.1), то Рассмотрим полученную таблицу двойственной задачи. Полагая значения переменных слева (небазисных) равными нулю: Следовательно, получено опорное решение Пусть теперь линейная форма прямой задачи неограничена, т.е. для некоторой верхней переменной, например, ys, соответствующий коэффициент qs<0, а все коэффициенты этого столбца симплексной таблицы неположительны: Тогда из таблицы для двойственной задачи: то есть система ограничений двойственной задачи противоречива. Так как из неотрицательности следует неположительность us (нельзя сделать ее положительной), то есть система несовместна.

Теорема доказана.

Вторая теорема двойственности:

Если хотя бы одно оптимальное решение одной из двойственных задач обращает i-е ограничение этой задачи в строгое неравенство, то i-я компонента (т.е. xi или ui) каждого оптимального решения второй двойственной задачи равна нулю.

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

Доказательство: они удовлетворяют следующим ограничениям: Что и требовалось доказать.

Справедлива и обратная теорема.

examination/mo/question7.txt · Последние изменения: 2014/01/15 12:19 (внешнее изменение)