Линейное программирование. Азарнова Т.В - 16 стр.

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


     Из определения следует, что число положительных координат базисной
точки не может быть более чем m. Если базисная точка содержит ровно m
положительных координат, то она называется невырожденной, в против-
ном случае - вырожденной. Задача называется невырожденной, если допус-
тимое множество не имеет вырожденных базисных точек.
     Как следует из соответствующих определений, базисные точки допус-
тимого множества ЗЛП (1) - (3) совпадают с неотрицательными базисными
решениями системы линейных уравнений (2). Таким образом, алгоритм пе-
ребора неотрицательных базисных решений системы совпадает с алгорит-
мом перебора базисных точек соответствующего допустимого множества.
Следует отметить, что в начале перебора должна быть известна исходная ба-
зисная точка. Итак, пусть имеется базисная точка допустимого множества
ЗЛП x TB =( xi , 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 ) =∑ ( xi −Θ aik )ci +c k Θ =∑ ci xi −Θ( ∑ ci aik −c k )
                     i∈I                       i∈I             i∈I
      Назовем оценкой вектора Ak величину ∆ k =∑ c i aik −c k ( в матричной
                                                         i∈I

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


                                        18