Математическое программирование (линейное программирование). Киселева Э.В - 32 стр.

планов задача имеет бесконечно много решений и оптимальный                    Пусть система ограничений Ах = b ЗЛП приведена к базис-
план Χ * является выпуклой линейной комбинацией оптималь-                 ному виду:
ных планов Х*1 и Х*2, т. е.                                                          xi + ai ,m +1 ⋅ x m+1 + L + ais x s + L + ain x n = bi ,
            Χ * = ( 1 − λ ) ⋅ Χ *1 + λ ⋅ Χ *2 ,       0 ≤ λ ≤ 1.                                 где bi ≥ 0, i = 1, m ,
    Итак, признаком существования альтернативного
                                                                          а целевая функция будет выражена через свободные переменные
оптимума при решении ЗЛП в симплексных таблицах яв-
                                                                          следующим образом:
ляется наличие хотя бы одной нулевой компоненты век-
тора r, соответствующего оптимальному плану.                                         Ζ = r1 ⋅ xm +1 + L + rs ⋅ xs + L + rn − m ⋅ xn + q → min,
    Если нулевых компонент окажется несколько, то введением               причем
в базис каждой из соответствующих переменных можно найти                                               x j ≥ 0 ( j = 1, n) .
несколько оптимальных планов Χ *1 , Χ *2 ,K , и т.д. Согласно тео-
                                                                              Положив значения всех свободных переменных, кроме xs ,
реме 5.3 общее оптимальное решение Χ * при наличии k опти-                равными нулю, будем иметь:
мальных опорных решений имеет вид:
                   k                   k                                                         xi + ais ⋅ xs = bi    (i = 1, m),
           Χ = ∑ λi ⋅ X , где
             *             *i
                                     ∑λ      i   = 1, λi ≥ 0, i = 1,k .                               Z = rs xs + q → min,
                  i =1                i =1
    Очевидно, при наличии только двух свободных переменных                где        rs < 0, ais ≤ 0 (i = 1, m) ; q – константа.
могут быть лишь два альтернативных оптимальных опорных ре-                    Так как rs < 0, то, вводя в базис переменную xs , можно
шения (две вершины). Однако уже при наличии трех свободных
переменных этих оптимумов может оказаться сколько угодно.                 уменьшить значение целевой функции.
Геометрически это соответствует случаю, когда плоскость уровня                Очевидно, что этой переменной ( xs ) можно придавать
параллельна грани многогранника и в крайнем положении будет               сколько угодно большие значения, при этом Ζ → −∞ , а значения
проходить через все вершины этой грани.                                   всех остальных переменных остаются неотрицательными. Дейст-
                                                                          вительно:
      6.2.4. Признак неограниченности целевой функции
                                                                                xi = bi − ais ⋅ xs ≥ 0 (i = 1, m), так как ais ≤ 0, xs > 0, bi ≥ 0.
    Как следует из геометрической интерпретации ЗЛП, возмож-
ны случаи, когда функция цели Z при решении задачи на мини-                    Таким образом, ни одна из переменных xi (i = 1, m) не выйдет
мум не ограничена снизу. Этот случай легко выявить при реше-              из базиса (не будет равна нулю).
нии задачи симплекс-методом.                                                   А это означает, что, увеличивая xs , мы никогда не получим
    Пусть среди компонент вектора r в симплекс-таблице, соот-
ветствующей какому-либо опорному плану, имеется хотя бы одна              опорного решения, хотя значение функции при этом будет
                                                                          уменьшаться. Следовательно, задача не имеет решения вследст-
отрицательная компонента, например rs < 0 , и при этом все ко-
                                                                          вие неограниченности снизу целевой функции Z.
эффициенты s-столбца ais ≤ 0 (i = 1, m). Покажем, что в этом                   Вывод. Признаком неограниченности снизу функ-
случае ЗЛП не имеет решения вследствие неограниченности                   ции Z в области допустимых решений является на-
функции цели Z.                                                           личие хотя бы одного столбца неположительных ко-
                             65                                                                                   66