13. Соотношения двойственности 3,4.

(1) (2)

Соотношение 3 (теорема существования). Для существования оптимальных планов , пары взаимодвойственных задач необходимо и достаточно, чтобы были не пусты множества прямых и двойственных планов, то есть .

Необходимость. Пусть существует – оптимальный план задачи (1), – оптимальный план задачи (2), тогда и они не равны пустому множеству.

Достаточность. Пусть теперь существует произвольные планы. Подставляем в основное неравенство, получаем

.

Тогда по следствию 3 двухфазного метода (Следствие 3: для того чтобы у задачи (1) существовал оптимальный план необходимо и достаточно, чтобы её целевая функция была ограничена сверху на непустом множестве планов) у задачи (1) существует оптимальный план. А тогда (по соотношению 2) и у задачи (2) существует оптимальный план.

Соотношение 4 (достаточное условие оптимальности). Если существуют такие планы и , что (12)

То они являются оптимальными для задачи (1) и (2) соответственно.

Доказательство. Подставим в неравенство (10): . Это неравенство означает, что целевая функция задачи (1) ограничена сверху числом , а тогда равенство (12) означает, что на плане эта верхняя граница достигается. Таким образом, – оптимальный план задачи (1).

Теперь докажем оптимальность для задачи (2) .

Подставим в неравенство (10): . Это неравенство означает, что целевая функция задачи (2) ограничена сверху числом , а тогда равенство (12) означает, что на плане эта верхняя граница достигается. Таким образом, – оптимальный план задачи (2).

14. Соотношения двойственности 5,6. Следствия соотношения 6

(1) (2)

Соотношение 5 (достаточное условие пустоты).

1. Если существует последовательность двойственных планов , то ;

2. Если существует последовательность прямых планов , то .

Доказательство.

1. Пусть выполняется условие соотношения. Предполагаем противное, то есть , существует . Подставим в основное неравенство, получим: , то есть целевая функция двойственной задачи ограничена снизу числом . Противоречие доказывает условие 1 соотношения 5.

2. Пусть выполняется условие соотношения. Предполагаем противное, то есть , существует . Подставим в основное неравенство, получим: , то есть целевая функция прямой задачи ограничена снизу числом . Это противоречие. Ч.т.д.

Рассмотрим задачу линейного программирования в нормальной форме и двойственную е ней задачу (13), (14):

(13) , (14)

Определение. Говорят, что -ое основное ограничение задачи (13) активно на плане , если оно принимает вид равенства: и пассивно на нём, если .

Определение. Говорят, что - ое основное ограничение (14) активно на , если и пассивно на нём, если .

Таким образом, на конкретном плане множество всех ограничений можно разбить на активные и пассивные.

В частности, если все ограничения пассивны на некотором плане, то он является внутренней точкой множества планов.

Соотношение 6 (условие дополняющей не жёсткости). Для того чтобы планы были оптимальны для своих задач, необходимо и достаточно выполнение условий: (15), (16)

Следствие 1. Если – оптимальный план задачи (1) и ( -ая компонента оптимального плана положительна), то соответствующее основное -ое ограничение задачи (14) должно быть активным на оптимальном плане.

Следствие 2. Если -ая компонента оптимального плана задачи (14) положительна , то соответствующее ему -ое ограничение задачи (13) должно быть активным на – оптимальный план.

Следствие 3. Если -ое основное ограничение задачи (13) пассивно на – оптимальный план, то .

Следствие 4. Если -ое основное ограничение задачи (14) пассивно на – оптимальный план, то .