Методы условной оптимизации: Рекомендации к выполнению лабораторных и практических работ. Шипилов С.А. - 11 стр.

                            1.5. Симплексный метод

      Метод предназначен для решения общей задачи линейного программиро-
вания, записанной в канонической форме (6).
      Векторы условий, соответствующие x n +1 ,..., x n + m , образуют базис. Пере-
менные x n +1 ,..., x n + m назовем базисными переменными. Остальные переменные
задачи – свободные.
      Если приравнять свободные переменные нулю
                                   x1 = 0, x 2 = 0, ... ; x n = 0 ,
то соответствующие базисные переменные примут значения
                               x n +1 = b1 ; x n + 2 = b2 ; ... ; x m = bm .
Вектор x с такими компонентами представляет собой угловую точку много-
гранника решений (допустимую) при условии, что bi ≥ 0 (опорный план).
      Теперь необходимо перейти к другой угловой точке с меньшим значени-
ем целевой функции. Для этого следует выбрать некоторую небазисную пере-
менную и некоторую базисную так, чтобы после того, как мы “поменяем их
местами”, значение целевой функции уменьшилось. Такой направленный пере-
бор в конце концов приведет нас к решению задачи.
      Пример
             Проиллюстрируем на нашем примере
                         f (x ) = 50 x1 +40 x2 → max
                            ⎧8 x1 + 5 x2 + x3 = 40
                            ⎪
                            ⎨5 x1 + 6 x2 + x4 = 30 .
                            ⎪⎩2 x1 + 5 x2 + x5 = 20
     Выберем в качестве базисных следующие переменные {x3 , x4 , x5 } и раз-
решим систему относительно этих переменных. Система ограничений примет
следующий вид:
                             ⎧ x3 = 40 − 8 x1 − 5 x2
                             ⎪
                             ⎨ x4 = 30 − 5 x1 − 6 x2 .
                             ⎪ x = 20 − 2 x − 5 x
                             ⎩ 5            1      2

Переменные {x1 , x2 } являются свободными. Если взять x1 = 0 и x2 = 0, то по-
лучим угловую точку (опорный план)
                           x ( 0) = (0 0 40 30 20 ) ,
                                                   Τ


                              ( )
которому соответствует f x ( 0) = 0 (т.е. продукция не выпускается).
      Значение целевой функции можно увеличить за счет увеличения x1 . При
увеличении x1 величины x3, x4 и x5 уменьшаются. Причем величина x3 раньше
может стать отрицательной. Поэтому, вводя в базис переменную x1 , одно-
временно x3 исключаем из базиса.

                                                                                11