Численные методы. Корнюшин П.Н. - 86 стр.

                                                    86


пор, пока значение переменной y1, отличное от нуля в вершине А, не станет равным нулю; тогда
попадем в верхнюю грань и, следовательно, в вершину D.
       Изложенные геометрические соображения лежат в основе той вычислительной процедуры,
которая называется симплексным методом решения задачи линейного программирования.
       Теперь становится ясным, что для проведения необходимых вычислений при
рассмотрении какой-то вершины надо иметь алгебраические зависимости, которые выражают
базисные переменные через небазисные. Точно так же для того, чтобы определить, достигнуто ли
значение оптимума в рассматриваемой вершине, и если нет, то в какую соседнюю вершину
следует перейти, чтобы улучшить достигнутый результат, надо иметь алгебраическое выражение
для целевой функции Z через внебазисные переменные. Надо также уметь переходить от
выражения для целевой функции Z и для базисных переменных через какой-то набор базисных
переменных (определяющих некоторую вершину) к таким же выражениям через новые базисные
переменные, набор которых соответствует соседней вершине. Для всего этого существует простой
алгебраический аппарат (который укладывается в удобные для вычислений таблицы), называемый
жордановыми исключениями.


                                   4.6.3.2. Жордановы исключения

        Начнем с примера. Пусть даны линейные зависимости, выражающие переменные y1, y2, y3,
Z через переменные x1, x2:
                                      y1 = x1 − 2 x 2 + 5;
                                      y 2 = − x1 − x2 + 7;
                                                                  (4)
                                      y3 − 2 x1 − x2 + 11;
                                         Z = x1 − 5 x2 .
         Можно трактовать эти соотношения как появившиеся в результате задания трех
ограничений и целевой функции Z некоторой задачи линейного программирования. Считая x1 и x2
базисными переменными, y1, y2, y3 – внебазисными, можно также считать, что этими
соотношениями заданы выражения внебазисных переменных и целевой функции через базисные
переменные x1 и x2. Допустим, что мы хотим поменять ролями переменные x1 и y3, т.е. сделать y3
базисной, а x1 – внебазисной переменной. Как теперь будут выражаться внебазисные переменные
y1, y2, x1 и целевая функция Z через новые базисные переменные y3 и x2? Для решения этой
алгебраической задачи достаточно из третьего уравнения (4) y3=-2x1-x2+11 выразить x1 через y3 и
x2 (что даст x1=-y3/2-x2/2+11/2) и полученное выражение для x1 подставить в выражения для
остальных переменных y1, y2, Z. Сделав это, будем иметь:
                                         1     5   21
                                   y1 = − y3 − x2 + ;
                                         2     2    2
                                         1    1    3
                                    y 2 = y3 − x2 + ;
                                         2    2    2                    (5)
                                         1     1   11
                                   x1 = − y3 − x2 + ;
                                         2     2    2
                                         1    11   11
                                   Z = − y3 − x2 + .
                                         2     2    2
        Для удобства вычислений сделаем некоторые алгебраические преобразования. Перепишем
соотношения (4) и (5) в виде зависимостей через «минус-базисные» переменные, т.е. зависимости
(4) запишем не через x1, x2, а через -x1, -x2 и зависимости (5) не через y3, x2, а через -y3, -x2. Получим: