Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 73 стр.

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


      3. Построить симплекс-таблицу, отвечающую симплекс-разложению
угловой точки v , т.е. формулам (3.4), (3.6).

      4. Провести анализ коэффициентов целевой функции в построенной
симплекс таблице: если среди них нет строго положительных коэффициентов,
то угловая точка v является решением задачи линейного программирования и
вычисления заканчивается. В противном случае перейти к следующему пункту
алгоритма.

      5.       Провести             анализ             элементов                        столбцов                     симплекс-таблицы,
располагающихся над строго положительными коэффициентами целевой
функции: если хотя бы для одного такого столбца среди его элементов нет
строго положительных, то решение является неограниченным, I* = -¥ и
вычисления заканчиваются. В противном случае перейти к следующему пункту
алгоритма.

    6. Определить разрешающий элемент g i k > 0 симплекс таблицы по                           *




правилу, описанному в пункте 3.3.

    7. Для угловой точки w , определенной формулой (3.9), выразить ее
базисные       переменные              u 1 , L , u k , L, u r           через             ее          внебазисные               переменные
                                                                                                        *
u r +1 ,L, u i ,L, u n . С этой целью в равенствах (3.4) в i -м уравнении выразить
           *




                                                                      u r +1 ,L, u k -1 , u k +1 ,L, u n , u i .
                                                                                                                     *
переменную       uk    через переменные                                                                                       В результате
получится

                       u k = wk - gˆkr +1 × u r +1 - L - gˆki * × u i - L - gˆkn × u n ,
                                                                                 *
                                                                                                                                       (1)

    где

                             vi *                   g i *r +1                    g i*r +1                        g i* n
                      wk =            , gˆ kr+1 =               , L, gˆ ki * =                    , L, gˆ kn =            .
                             g i* k                  g i *k                          g i *k                      g i* k

    Подставляя выражения для u k из (1) в остальные уравнения (3.4),
выразить оставшиеся базисные переменные точки w через ее внебазисные
переменные. В результате будем иметь

                                                                   73