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

Она уже соответствует опорному плану x ( 0) = [0 0 40 30 20] (столбец
                                                                 Τ

свободных членов).
      Построение оптимального плана. Для того, чтобы опорный план был
оптимален, при минимизации целевой функции необходимо, чтобы коэффици-
енты в строке целевой функции были неположительными (в случае максимиза-
ции – неотрицательными), т.е. при поиске максимума мы должны освободиться
от отрицательных коэффициентов в строке f (x ) .
      Если критерий не выполнен, т.е. не все коэффициенты целевой функции
неотрицательны, то следует перейти от одного допустимого базисного решения
к соседнему допустимому, т.е. такому, в котором множества базисных и сво-
бодных переменных изменены на один элемент. В невырожденном случае это-
му геометрически соответствует переход от одной вершины к другой вдоль
ребра допустимой области (обе вершины принадлежат одному ребру). Этот
процесс называют также симплекс-шагом или заменой базиса. Опишем после-
довательно его этапы.
      1. Выбор разрешающего столбца. Если при поиске максимума в строке
целевой функции есть коэффициенты меньше нуля, то выбираем столбец с от-
рицательным коэффициентом в строке целевой функции в качестве разрешаю-
щего. Пусть это столбец сl номером l . Если таких столбцов несколько, реко-
мендуется выбирать минимальное сl.
      2. Выбор разрешающей строки. Для выбора разрешающей строки (раз-
решающего элемента) среди положительных коэффициентов разрешающего
столбца выбираем тот (строку), для которого отношение коэффициента в
столбце свободных членов к коэффициенту в разрешающем столбце минималь-
но:
                           br        ⎧b         ⎫
                               = min ⎨ i ail ≥ 0⎬ ,
                           arl       ⎩ ail      ⎭
      где arl – разрешающий (направляющий) элемент, r – разрешающая строка.
Если в разрешающем столбце нет положительных коэффициентов, то целевая
функция неограничена снизу (при максимизации – неограничена сверху).
       3. Замена базиса. Для перехода к следующей симплексной таблице (сле-
дующему опорному плану с большим значением целевой функции) делается
шаг модифицированного жорданова исключения с разрешающим элементом
arl , при котором базисная переменная xr становится свободной и одновременно
свободная переменная xl становится базисной.
    • На месте разрешающего элемента ставится 1 и делится на разрешающий
       элемент.
    • Остальные элементы разрешающего столбца меняют знак на противопо-
       ложный и делятся на разрешающий элемент.
    • Остальные элементы разрешающей строки делятся на разрешающий эле-
       мент.
    • Все остальные элементы симплексной таблицы вычисляются по следую-
       щей формуле:
14