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

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

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

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

                            (1)

                               (2)

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

,

они удовлетворяют следующим ограничениям:

.                    (3)

Умножим (3), соответственно, на и , и просуммируем полученные выражения:

.                          (4)

Из основной теоремы двойственности следует

.                                                  (5)

И с учетом (4) получаем:

,

.

Первое из этих выражений можем переписать в виде

,

и так как все и выражения в скобках неотрицательны, то опуская å, получим:

.

Аналогично получим:

.

Что и требовалось доказать.

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