15. Теоремы Фаркаша.

Теорема 1 (Фаркаша или о неравенстве следствий неравенств). Пусть в пространстве заданы вектора , тогда из неравенств: (19) следует неравенство (20) тогда и только тогда, когда существуют числа (21)

Теорема 2 (Фаркаша или о неравенстве следствий равенств). Для того, чтобы (20) вытекало из равенств: необходимо и достаточно существование чисел , таких что выполняется равенство (21).

Доказательство аналогично теореме 1.

Теорема 3 (Фаркаша или о несовместимости системы). Система неравенств несовместна в том и только в том случае, когда найдутся числа , причём не все неравные нулю, что

16. Двойственный симплекс-метод. Определения. Формула приращений.

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

Двойственный план будем называть базисным, если в матрице существует подматрица , , такая, что ограничения задачи (2) принимают вид , (разбиение такие же, как и в § 1). Двойственный базисный план называется невырожденным, если . Для двойственного базисного плана вектор называется базисным псевдопланом.

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

Если , то будет планом (1) (далее базисным с той же ).

Вектор называется копланом. Ясно, что .

Если – двойственный базисный план, то базисный план можно разбить . Для невырожденного двойственного базисного плана .

Формула приращений. Пусть – двойственный базисный план, а – любой двойственный план. Тогда , где . Для соответствующего базисного коплана имеем:

(24)

(25)

17. Критерий оптимальности. Условие пустоты.

Теорема 4. Неравенство (26) достаточно, а в случае невырожденности двойственного базисного плана и необходимо для его оптимальности. Псевдоплан при этом является оптимальный планом для исходной задачи (1).

Доказательство. Достаточность. Пусть выполняется (26). Так как , то из (21) получаем , т.е. , т.е – оптимальный двойственный базисный план. Так как – базисный план (1) и , то по соотношению 2 – оптимальный план (1).

Необходимость. Пусть – оптимальный невырожденный двойственный базисный план, т.е.

(27)

Предположим противное: (26) не выполняется, т.е. (28)

Построим вектор , где (29)

, (30)

(в силу (24)). При этом будет соответствовать .

Так как и , или покомпонентно (§ 1. ):

, (31)

то найдется такое малое , что , и будет копланом, а – двойственный план задачи. При этом получим (25) ,

т.е. , что противоречит оптимальности .

Достаточное условие пустоты X. Теорема 5. Если , (32)

то .