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

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


строки. Присвоить переменным исходной задачи, отвечающим выброшенным
колонкам, значения, равные нулю. В соответствии с полученной таблицей
выписать формулы (3.4), в которых учтено присвоение нулевых значений
части переменным, и выполнить пункты 2-8 алгоритма, описанного в п.4.

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

    Действительно, симплекс-таблице для угловой точки z * соответствует
система равенств

          uj +g     j r +1   u r +1 + L + g     jk   uk + L + g    jn   un + g   j m - r +1   w m - r +1 + L + g   jm   wm = v j ,

                                                        j = 1,L , r ;                                                                (3)

       w i + g r + i r +1 u r +1 + L + g r +i k u k + L + g r +i n u n + g r + i m - r +1 w m - r +1 + L + g r + i m w m = 0

                                                        i = 1, L , m - r .                                                           (4)

    Полагая в равенствах (3),(4) w s = 0, s = 1, L , m , получим

                       uj +g       j r +1   u r +1 + L + g   jk   uk +L+ g       jn   u n = v j , j = 1,L , r ,                      (5)

                    g r +i r +1 u r +1 + L + g r + i k u k + L + g r + i n u n = 0 , i = 1, L, m - r .                               (6)

    Система соотношений (5), (6) эквивалентна системе ограничений исходной
задачи. Это означает, что колонки 7-9 таблицы могут быть отброшены.
Равенства (4) и (6) соответствуют нижней половине таблицы. Если для
                                                                    82