2.2 Критерий разрешимости задачи

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

Лемма 2.1 Если функция w = сх ограничена снизу на множе­стве Q = {ж | Ах = Ь, х > 0}, то для любого х° £ Q существует б. д.р. х, такое, что сх < сж°.

Доказательство. Рассмотрим непустое множество Q0 = {ж £ Q | сх < сжо} и выберем в нем вектор ж, имеющий минимальное число ненулевых компонент. Докажем, что допустимое решение ж является базисным. Если это не так, то множество {Aj \ Xj > 0} столбцов матрицы А линейно зависимо, т.е. существует вектор у ф 0 такой, что Ау = 0 и yj = 0 в случае Xj = 0. Без ограничения общности можно считать, что d = су < 0, поскольку в противном случае мы могли бы заменить у на —у. Рассмотрим однопара-метрическое семейство векторов ж(£) = x-\-ty. При достаточно малых значениях t имеем ж(£) £ Q.

Возможны два случая.

1) Уз ^ 0 для всех j. Тогда при любом t > 0 имеем ж(£) £ Q и, следовательно, w(x(t)) = w(x) + td > const. Учитывая неравен­ство d < 0, отсюда следует, что d = 0 и w(x(t)) = w(x) при любом t. Пусть to = — mm{xj/yj \ yj > 0}. Тогда x(to) принадлежит Q° и имеет меньше ненулевых компонент, чем ж, что противоречит выбору ж.

2) yj < 0 при некотором j. В этом случае вектор x(to) при t0 = min{ — Xj/yj I < 0} принадлежит Q° и имеет меньше не­нулевых компонент, чем ж, т.е. снова получаем противоречие. Лемма доказана.

Следствие Если <5 ф 0; то существует базисное допустимое решение.

Такое утверждение непосредственно вытекает из доказанной лем­мы, если, например, положить ио = 0.

Теорема 2.1 (Критерий разрешимости). Задача ЛП (2.1)-(2.3) разрешима тогда и только тогда, когда С} ф 0 и целевая функ­ция ио ограничена снизу на множестве С}.

Доказательство. Необходимость условия данной теоремы впол­не очевидна. Докажем достаточность. Из условия теоремы и пре­дыдущей леммы следует, что множество б.д.р. непусто и, как отмечалось выше, конечно. Поэтому существует элемент упомя­нутого множества, — б.д.р. ж*, — на котором целевая функция ио принимает минимальное значение, т.е. ги(х*) < ио(х) для любого б.д.р. ж. Покажем, что ж* является оптимальным решением зада­чи. В самом деле, предположим, что существует элемент ж0 £ <5, для которого имеет место неравенство ги(х°) < ги(х*). Тогда, по Лемме 1, будет существовать б.д.р. ж, такое, что ио(х) < ш(х°) и, следовательно, ио(ж) < ио(ж*). Полученное неравенство противо­речит выбору ж*. Теорема доказана.

Из доказательства данной теоремы получаем также

Утверждение 2.2 Если задача ЛПразрешима, то существует оптимальное базисное решение.

Последнее свойство задачи ЛП, учитывая также конечность числа б.д.р., позволяет говорить об очевидном методе решения задачи, суть которого сводится к полному перебору б.д.р. и выделению среди них наилучшего (по значению целевой функции). Непрак­тичность такого способа решения станет понятной, если принять во внимание, что даже при достаточно скромных размерах за­дачи число б.д.р. становится астрономически большим. Тем не менее идея целенаправленного перебора, позволяющего избежать в большинстве случаев просмотра подавляющей части множества б.д.р., лежит в основе самого распространенного метода решения задачи ЛП, получившего название симплекс-метод.