Предварительный анализ двойственных задач

Некоторую связь между парой двойственных задач устанавливает следующая лемма.

ЛЕММА.

Для любых допустимых векторов х и у в задачах 1 и 1* выполняются неравенства

m(х)n(у) , (9)

причем это неравенство выполняется как равенство в том и только в том случае, если имеют место следующие соотношения:

(10) (11)

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

(1) (8) (4) (5)

Следствия из леммы:

1. Признак оптимальности в краткой форме

Для оптимальности допустимого вектора х в задаче 1 необходимо и достаточно существования допустимого вектора у в задаче 1^* такого, что

m(х)= n(у) (12)

При этом допустимый вектор у является оптимальным в задаче 1*.

2. Признак оптимальности в развернутой форме

Для оптимальности допустимого вектора х в задаче 1 необходимо и достаточно существование вектора у = (у₁, у₂, у₃,…у_m), удовлетворяющего следующим условиям:

а) у_i ³ 0, iÎI₂

б) åa_ijy_i + c_j = 0, jÎJ_1,

iÎI

в) åa_ijy_i + c_j,  0, jÎJ_2,

iÎI

г) åa_ijy_i + c_j, = 0, если х_j >0 для jÎJ_2,

iÎI

д) у_i = 0, если åa_ijx_j + b_i >0, iÎI₂ ,

jÎJ

тогда вектор у является оптимальным в задаче 1*.

Выполнение условий а), б) и в) признака оптимальности означают допустимость вектора y в двойственной задаче.

Условие г) эквивалентно (10).

Условие д) эквивалентно (11).

Пример. Проверить вектор на оптимальность в следующей задаче линейного программирования.

ЗАДАЧА 1. Максимизировать при условиях:

Решение. При решении задачи удобнее всего использовать признак оптимальности в развернутой форме.

Решение задачи необходимо начинать с проверки допустимости данного вектора .

Подставляя значения компонент вектора в ограничении I⁰ и 2⁰, убеждаемся, что все они выполняются. Для проверки остальных условий признака оптимальности составляем двойственную задачу:

Требуется найти вектор , удовлетворяющий условиям:

Запишем условия г) и д) признака оптимальности:

г)

( т.к. , следовательно, в первом и третьем ограничении условия 2⁰, двойственной задачи достигается равенство)

д) отсутствует, т.к. ни одно ограничение 2⁰ основной задачи не выполняется как строгое неравенство.

Из условия г) находим .

Найден вектор . Проверяем его допустимость в двойственной задаче, т.е. выясняем, выполняются ли условия I⁰ и 2⁰ двойственной задачи. Т.к. все условия выполняются, вектор y является оптимальным в двойственной,

а вектор х=(1, 0, 1, 0) - оптимальным в основной задаче.