Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 17 стр.

                                                                 Линейное программирование


      Из определения следует, что число положительных координат базисной
точки не может быть более чем m. Если базисная точка содержит ровно m
положительных координат, то она называется невырожденной, в против-
ном случае - вырожденной. Задача называется невырожденной, если допус-
тимое множество не имеет вырожденных базисных точек.
      Как следует из соответствующих определений, базисные точки допус-
тимого множества ЗЛП (1) - (3) совпадают с неотрицательными базисными
решениями системы линейных уравнений (2). Таким образом, алгоритм пе-
ребора неотрицательных базисных решений системы совпадает с алгорит-
мом перебора базисных точек соответствующего допустимого множества.
Следует отметить, что в начале перебора должна быть известна исходная ба-
зисная точка. Итак, пусть имеется базисная точка допустимого множества
ЗЛП x TB =( x i , i ∈I ; x j =0, j ∈J ). Координаты x i , i ∈I , будем в дальнейшем
называть базисными, x j =0, j ∈J - небазисными. Соответственно множе-
ство I - множеством базисных индексов, J - множеством небазисных индек-
сов. В случае невырожденной задачи по каждой базисной точке восстанавли-
вается соответствующий базис, состоящий из векторов Ai , i ∈I . Обозначим
его через B. Заметим далее, что каждая итерация метода Жордана-Гаусса со-
ответствует переходу от одной базисной точки к другой при замене одной
базисной (зависимой) переменной на одну небазисную (свободную). При
этом выбору подлежит номер небазисной переменной k и жестко определяет-
ся номер базисной переменной l (смотри пункты 3а и 4а алгоритма).
Координаты новой базисной точки вычисляются следующим образом:
                         x                      x
         x BH =( xi − l a ik , i ∈I ; x k = l ; x j =0, j ∈J , j ≠k ).           (8)
                         a lk                 a lk
      Таким образом, ранее получен алгоритм, позволяющий перебрать все
базисные точки ЗЛП. Однако при поиске максимума не имеет смысла рас-
сматривать те точки, которые обеспечивают меньшее значение целевой
функции, чем уже известные. С целью внесения такого упорядочения в алго-
ритм перебора вычислим значение целевой функции в точке x BH , представ-
ленной в виде (8).
                              x            x
      Обозначим Θ = l =min i . Тогда
                              a lk  aik >0 a ik

            L ( x BH ) =∑ ( x i −Θ a ik )c i +c k Θ =∑ c i x i −Θ(∑ c i a ik −c k )
                      i∈I                           i∈I              i∈I
      Назовем оценкой вектора Ak величину ∆ k =∑ c i a ik −c k ( в матричной
                                                               i∈I

форме   ∆k =c TB B −1 Ak
                   −c k , c B - вектор коэффициентов целевой функции при
базисных переменных ). В данных обозначениях
                             L( x BH ) =L( x B ) −Θ ∆ k .             (9)


                                            19