Задача линейного программирования. Горячев Л.В. - 6 стр.

6

      Каждому k – му ограничению типа неравенства одной из пары двойственных задач отвечает
      ограничение на знак соответствующей переменной другой задачи и наоборот. Эти пары усло-
      вий называются сопряженными. Так, для вышеупомянутой пары двойственных задач пару
      условий ak1 x1 + ak2 x2 + · · · + akn bn ≤ bk и yk ≥ 0; xl ≥ 0 и a1l y1 + a2l y2 + · · · + aml ym ≥ cl
      будут сопряженными.

    5. Если в каждой паре сопряженных условий на оптимальных планах одно условие свободное,
       то другое — закрепленное.
      Доказательство непосредственно вытекает из условий дополняющей нежесткости теоремы
      Куна-Таккера.

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

                                               (c, x) − max                                            (10)

                                                  Ax = b                                               (11)
                                                   x≥0                                                 (12)
Задача имеет m+n ограничений, среди них m ограничений типа равенства и n ограничений неотри-
цательности. По определению крайняя точка удовлетворяет n линейно-независимым ограничениям
задачи как точным равенствам.
   Определение: План x = (x1 , x2 , . . . , xn ) называется опорным, если среди ограничений задачи,
которым он удовлетворяет как точным равенствам, имеется n линейно-независимых.
   Это определение фактически устанавливает эквивалентность понятий опорного плана и вер-
шины (крайней точки) многогранного множества допустимых планов. Будем предполагать, что
опорный план обращает в равенства n ограничений. Такой опорный план называется невырожден-
ным.
   Применительно к задаче ЛП в каноническом виде понятие опорного плана можно модифициро-
вать.
   Среди n ограничений, обращаемых в равенства опорным планом, m будут обязательных (11) и
остальные m − n ограничений на (13) обратятся в точные равенства на опорном плане. Без ущерба
для общности изложения допустим, что имеем невырожденный опорный план, который обращает
в точные равенства последние m − n ограничения неотрицательности (13). Тогда этому опорному
плану отвечает система линейных уравнений с матрицей коэффициентов, составленных из первых m
столбцов матрицы A и неизвестными x1 , x2 , . . . , xm . Очевидно, что любому невырожденному плану
задачи ЛП канонического вида можно поставить в соответствие m линейно-независимых векторов
столбцов матрицы A называемых базисом этого плана. Верно и обратное, любой совокупности m
линейно-независимых векторов-столбцов матрицы A, которой отвечает неотрицательное решение
системы линейных уравнений, построенной на этих столбцах, отвечает опорный план задачи. Легко
видеть, что невырожденный опорный план содержит m положительных компонент. Вырожденный
опорный план обращает в точные равенства более, чем n ограничений задачи; он имеет не менее, чем
m положительных компонент. Геометрически вырожденность опорного плана означает, что через