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

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


     wi      g r + i r +1   … g r+ i k   …   g r+ i n   g r +i m - r +1   …   g r+ i m   0

     …       …              … …          …   …          …                 …   …          …

     w m-r   g m r +1       … gmk        …   gmn        g m m -r +1       …   gmn        0



     В базис этой точки могут входить столбцы не только матрицы А, но и
столбцы, отвечающие вспомогательным переменным. Пусть в базис точки z *
вошли r £ m столбцов матрицы А (не теряя общности, первых r ) и m - r
столбцов, отвечающих вспомогательным переменным (не теряя общности
первым m - r переменным. В случае, когда вспомогательные переменные не
входят    в число           базисных переменных симплекс-таблица (таблица 6)
представлена лишь своей верхней половиной, из таблицы вычеркиваются
колонки 7-9. Затем таблицу следует дополнить строкой целевой функции
исходной задачи, в которой переменные u 1 ,L , u r выражены через переменные
u r +1 , L , u n . В результате будет получена симплекс-таблица, отвечающая угловой

точке v* допустимого множества исходной задачи. Далее выполнить пункты 2-
8 алгоритма, описанного в п.4. В противном случае сделать переход к
следующему пункту данного алгоритма.

     7. Выяснить наличие в колонках 2-6 в нижней половине таблицы строго
положительных коэффициентов. Если они есть, то выбрать в качестве
разрешающего элемента симплекс-таблицы любой из них и выполнить пункт 7
алгоритма, описанного в п.4. В результате одно вспомогательное переменное
перейдет из числа базисных переменных в число внебазисных переменных.
Далее вернуться на пункт 7 данного алгоритма.

     В противном случае сделать переход на следующий пункт данного
алгоритма.

     8. Отбросить нижнюю часть таблицы, колонки 7-9 и те колонки из
числа 2-6, для которых в нижней части таблицы имеются строго
отрицательные коэффициенты. Из оставшейся таблицы вычеркнуть нулевые
                                                81