Математическое программирование (линейное программирование). Киселева Э.В - 26 стр.

                    6. СИМПЛЕКС-МЕТОД                                Решение. Найдем первоначальное опорное (допустимое ба-
                                                                 зисное) решение.
     На основании свойств ЗЛП, рассмотренных в предыдущей            Чтобы получить базисное решение, необходимо систему ли-
главе, можно сделать следующие выводы.                           нейных уравнений привести к базисному виду, приравняв сво-
     Если решение ЗЛП существует, то оно достигается хотя бы в   бодные неизвестные нулю.
одной вершине (опорном решении) многогранника допустимых             Замечаем, что система уравнений уже приведена к базисному
решений, следовательно, поиск оптимального решения необхо-       виду ( x1 , x2 − базисные неизвестные, x3 , x4 , x5 − свободные неиз-
димо осуществлять среди вершин многогранника (опорных ре-        вестные).
шений).                                                              Положив x3 = x4 = x5 = 0 , получаем первоначальное базис-
     Однако при больших m и n перебор всех вариантов практи-
                                                                 ное решение
                                                                                                                      ( )
чески нереален. Для решения ЗЛП был предложен симплекс-
метод, разработанный в 1947–49 гг. американским математиком                   X 1 = (8, 9, 0, 0, 0) Т , причем Z X1 = 0 .
Дж. Данцигом. Идея симплекс-метода состоит в целенаправ-              Очевидно, это базисное решение является опорным, так
ленном переборе вершин многогранника допустимых решений          как все x j ≥ 0 ( j = 1,5).
(опорных планов) в направлении «улучшения» значений целевой
функции.                                                             Итак, первый этап симплекс-метода закончен.
     Замечание. «Симплекс» в переводе с латинского значит            Выясним теперь, является ли опорное решение X 1 опти-
«простейший». В многомерной геометрии симплексом называет-       мальным. Для этого рассмотрим функцию цели Z . Обратим вни-
ся геометрическое место точек, удовлетворяющих условиям:         мание на тот факт, что она выражена только через свобод-
                                         (         )
                      n                                          ные неизвестные x3 , x4 и x5 .
                      ∑ xi = 1 , xi ≥ 0 i = 1, n .
                     i =1                                            Возникает вопрос, можно ли уменьшить значение целевой
    При малой размерности симплексом является точка, отрезок,    функции Z = 7 x3 − x 4 − 3 x5 за счет перехода к новому опорному
треугольник, тетраэдр. Первая задача, решенная симплекс-         решению, в котором в базис будет введена одна из свободных пе-
методом, имела в качестве многогранника допустимых решений       ременных: либо x3 , либо x 4 , либо x5 . Очевидно, введение в ба-
именно симплекс.                                                 зис переменной x3 нецелесообразно, так как коэффициент при
                 6.1. Идея симплекс-метода                       ней в функции цели Z равен +7 и увеличение этой переменной
                                                                 на единицу приведет к увеличению значения функции Z на 7
    Рассмотрим идею симплекс-метода на конкретном примере.
                                                                 единиц. А вводя в базис x 4 или x5 , мы можем уменьшить значе-
    Пример 6.1.    Z = 7 x3 − x 4 − 3 x5 → min,
                                                                 ние Z (поскольку коэффициенты при них отрицательны). Для оп-
                    ⎧ x1   + x3 + 6 x4 + 2 x5 = 8,               ределенности введем в базис x5 , т.е. ту из свободных перемен-
                    ⎪
                    ⎨                                            ных, которая имеет наибольший по модулю отрицательный ко-
                    ⎪⎩ + x2 + x3       + 3x5 = 9,
                                                                 эффициент ( − 3 > − 1 ) .
                            x j ≥ 0, ( j = 1,5).                     Если бы все коэффициенты в функции Z были положитель-
                                                                 ны, то уменьшить значение Z было бы невозможно введением в

                                 53                                                                  54