Симплекс-метод решения задачи линейного программирования. Исенбаева Е.Н. - 7 стр.

       4. Если для j-той крайней точки все симплексные разности Δk ≥0,
k = 1, n + m , то эта точка оптимальная. Конец решения.
       Если есть столбец, в котором симплексная разность Δk0 ≤ 0, а все
элементы столбца αik0 ≤ 0, i = 1, m , то задача ЛП решения не имеет, т.к.
целевая функция неограничена сверху.
       В остальных случаях переход к пункту 5.
       5. Находим k0 - направляющий столбец. Выбираем столбец, в
котором самая минимальная симплекс разность среди отрицательных
симплекс разностей (напомним, что решаем задачу максимизации) т.е.
                                         min Δk = Δk0                 (10)
                                            Δk < 0.
       Направляющая строка i0 выбирает из условия
                             ⎧⎪ b ⎫⎪          b i0
                       min ⎨ i ⎬ =                   = λ , i = 1, m . (11)
                              ⎪⎩ α ik 0 ⎪⎭ α i 0 k 0
       Итак, направляющий элемент αi0k0.
       Заполняем таблицу, соответствующую новому решению.
       6. Выполняем один шаг метода Гаусса, введя в базис вектор Аk0
вместо вектора Аn0, имеющего i0 – координату, равную 1. Для это ис-
пользуются следующие соотношения:
       - новые элементы направляющей строки находятся:
                                  α i0k
                                          , k = 1, n + m ;            (12)
                                 α i0k 0
       - новые элементы направляющего столбца:
                       α ik 0 = 0
                       α i 0k 0 = 1, i = 1, m , причем i ≠ i0;        (13)
т.е. в направляющем столбце все элементы равны 0, а направляющий
элемент равен 1.
       - новые значения остальных элементов матрицы:
                               αi j           i ≠ i0
                       α ij − 0 ⋅ α ik 0 ,           ;            (14)
                             α i0k 0          j ≠ k0
       - новые значения симплексных разностей:
                                   αi j
                            Δ j − 0 ⋅ α ik 0 ,;                   (15)
                                  α i0k 0
       Правильность вычислений контролируется по формулам непо-
средственного счета:
                                          ~
                      Δk = AkCБ − Ck
                      ~                     , k = 1, n + m        (16)
                      Z = BC Б
       Получаем (j + 1) крайнюю точку. Полагая j = j + 1, переходим к
пункту 4.


                                    7