Методы условной оптимизации: Рекомендации к выполнению лабораторных и практических работ. Шипилов С.А. - 13 стр.

                    1.6. Алгоритм симплексного метода

      Формализованный алгоритм симплекс метода состоит из двух основных
этапов: 1) построение опорного плана; 2) построение оптимального плана.
      Построение опорного плана. Систему в канонической форме (6) вместе
с целевой функцией перепишем в следующем виде
                    ⎧ xn+1 = −(a11 ⋅ x1 + a12 ⋅ x2 + ... + a1n ⋅ xn ) + b1
                    ⎪ x = −(a ⋅ x + a ⋅ x + ... + a ⋅ x ) + b
                    ⎪ n+ 2         21     1       22     2              2n     n       2
                    ⎨ ................................................................. .   (8)
                    ⎪ xn+ m = −(am1 ⋅ x1 + am 2 ⋅ x2 + ... + amn ⋅ xn ) + bm
                    ⎪
                    ⎩ f ( x) = −(−c1 ⋅ x1 − c2 ⋅ x2 − K − cn ⋅ xn ) + 0
     Теперь задачу ЛП канонического вида можно представить в виде таблицы
следующего вида, называемой симплекс-таблицей.

                        -x 1            -x 2            ...             -x n
            xn+1        a11             a12             ...             a1n           b1
            xn+2.       a21.            a22.             .              a2n.          b2.
              .          .               .               .               .             .
              .          .               .               .               .             .
            xn+m        am1             am2                             amn           bn
            f(x)        -c1             -c2             ...             -cn            0

      Левый крайний столбец содержит базисные переменные, верхняя строч-
ка- свободные переменные. Соответственно справа записаны постоянные члены
уравнений, внизу- коэффициенты целевой функции от свободных переменных,
а в правом нижнем углу записано значение целевой функции при нулевых зна-
чениях свободных переменных.
      Каноническому виду задачи ЛП или соответствующей симплекс-таблице
сопоставляется точка x1= x2=…= xn=0, xn+1= b1, xn+2= b2, …, xn+m= bn. Если при
этом bn ≥ 0 (допустимый канонический вид), то точка является допустимой и,
следовательно, вершиной области допустимых решений.
         Пример
         Для рассмотренного ранее примера в случае базисных переменных
{x3 , x4 , x5 } начальная симплексная таблица будет выглядеть следующим обра-
зом:
                                          − x1        − x2
                             x3 =          8           5           40
                             x4 =          5           6           30
                             x5 =          2           5           20
                            f (x ) =      -50         -40          0

                                                                                              13