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

которую будем называть симплекс-таблицей. В левом столбце                                   4. Для перехода к новому опорному плану выбираем макси-
записываются базисные переменные (БП).                                                мальную по модулю отрицательную компоненту вектора r ,
    2. С помощью шагов Жордана–Гаусса найдем первона-                                 пусть это будет rs < 0 . Анализируем коэффициенты s-го столбца
чальный опорный план, т.е. преобразуем таблицу так, чтобы сис-                        матрицы системы ограничений.
тема уравнений была приведена к базисному виду с неотрица-
тельными свободными членами. При этом функция цели
                                                                                            Если все коэффициенты ais            (       )
                                                                                                                            ′ ≤ 0 i = 1, m , то, как было ска-
должна быть выражена через свободные неизвестные. Не нару-                            зано выше, задача не имеет решения из-за неограниченности це-
шая общности, можно считать, что базисными переменными яв-                            левой функции (z min → −∞ ) .
ляются x1 , x2 ,K, xm , тогда симплекс-таблица примет вид:                                  Если среди коэффициентов a is′ есть хотя бы один положи-
                                                                                      тельный, то s-столбец выбираем разрешающим и переходим к
 БП    x1     x2     …         xm    xm+1     …     xs      …        xn     Свобод-
                                                                              ный     п. 5.
                                                                             член           5. Для выбора разрешающей строки составляем неотри-
 x1    1     0       …         0    a′1,m+1   …    a′1,s    …       a′1,n      b′1    цательные отношения
 x2    0     1       …         0    a′2,m+1   …    a′2,s    …       a′2,n      b′2
 …
 xm
       …
       0
             …
             0
                     …
                     …
                               …
                               1
                                      …
                                    a′m,m+1
                                              …
                                              …
                                                    …
                                                   a′m,s
                                                            …
                                                            …
                                                                     …
                                                                    a′m,n
                                                                               …
                                                                              b′m
                                                                                                                     bi′
                                                                                                                       ′
                                                                                                                     ais
                                                                                                                             (       )
                                                                                                                           ≥ 0 i = 1, m
 Z     0     0       …         0      r1      …     rs      …       rn–m        q
                                                                                      и выбираем среди них наименьшее:
                                                                                                                         ⎧ b′    ⎫      b′
          Коэффициенты при               Вектор r коэффициентов                                                 min ⎨ i ≥ 0⎬ = k .
        базисных неизвестных            при свободных неизвестных                                              1≤ i ≤ m ⎩ ais′   ⎭       ′
                                                                                                                                       aks
                                                                                          Таким образом, определилась разрешающая k-я строка и
    В данной таблице bi′ ≥ 0 , i = 1, m .                                             разрешающий элемент a ks  ′ .
    Полагая свободные неизвестные xm +1 = xm + 2 = K xn = 0 , по-                         6. Выполняем шаг преобразований Жордана–Гаусса с разре-
лучаем из таблицы неотрицательное базисное решение (опорный                                               ′ и переходим к п. 3.
                                                                                      шающим элементом a ks
план)
                                                                                                               ⎧ b′   ⎫
                          ⎛
                                                           T
                                                             ⎞                            Замечание. Если min ⎨ i ≥ 0⎬ достигается для нескольких
                          ⎜                                                                                       ′
                                                                                                             i ⎩ ais
                                             ′ , 0, 0, K , 0 ⎟ .
                    X 1 = ⎜ b1′ , b2′ , K , bm                                                                        ⎭
                          ⎜                     14243 ⎟⎟                              строк, то за разрешающую строку можно принять любую из них,
                          ⎝                         n−m      ⎠                        при этом в новом опорном плане значения некоторых базисных
    3. Анализируем строку коэффициентов при свободных неиз-                           переменных станут равны нулю, т.е. получаем вырожденный
вестных, т.е. вектор r = (r1 , r2 , K , rn − m ) в Z-строке.                          опорный план.
      Если   r ≥ 0 , то соответствующее опорное решение является                          Пункт 5 нуждается в дополнительном пояснении.
оптимальным, z min = − q .
    Если среди компонент вектора r имеется хотя бы одна от-
рицательная, то полученный опорный план не является опти-
мальным. Необходимо перейти к новому опорному плану.
                              61                                                                                            62