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

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


                       §3. Алгоритм перебора базисных решений
                             систем линейных уравнений

      В § 2 была введена каноническая форма ЗЛП, которая в матричном ви-
де может быть переписана следующим образом:
                                     z ( x) =c T x → max                                          (1)
                                        Ax =b , (b ≥0)                                           (2)
                                              x ≥0 ,                                              (3)
где c =( c1 ,..., c n ), x =( x1 ,...., x n ), b =(b1 ,...., bm ), A =( a ij ) , i =1, m, j =1, n
     T                    T                     T


Очевидно, что решения задачи ЛП (1) - (3) находятся среди решений систе-
мы линейных уравнений Ax = b. Рассмотрим способ перебора решений дан-
ной системы для случая, когда ранг матрицы r(A) = m. Из курса линейной ал-
гебры известно, что система (2) с помощью преобразований Жордана - Гаус-
са может быть приведена к виду
                                                  ~
                                          E x +A ~  x =b ,                                        (4)
                                                                   ~
где E - единичная матрица размера m× m , матрица A имеет размеры m×(n-m)
и элементы a~ , полученные в результате преобразований Жордана-Гаусса,
                  ij

b - вектор размера m, полученный из вектора b вследствие преобразований.
Система уравнений (4) может быть переписана в координатной форме сле-
дующим образом:
               x i =bi − ∑ a~ij ~
                                x j , i ∈I , I ∪ J ={1,..., n},      (5)
                               j∈J

где I - множество индексов зависимых переменных , J - множество индексов
                            � x�
свободных переменных, x =�� ~ �� ∈ R n . Формула (5) представляет собой фор-
                             � x�
мулу общего решения системы (2). Напомним, что любое частное решение
системы может быть получено из формулы общего решения путем фиксиро-
вания любых значений свободных переменных с последующим вычислением
по формуле (5) значений зависимых переменных. В дальнейшем нас будут
интересовать частные решения вида ( xi =bi , i ∈ I , x j =0, j ∈ J ) , т.е. векто-
ры, свободные переменные которых положены равными 0. Такие векторы
называются базисными решениями системы линейных уравнений (2). Мак-
симальное количество базисных решений не превосходит величины C nm . Пе-
ребрать все базисные решения системы линейных уравнений можно, органи-
зовав перебор формул общего решения. Очевидно, что это можно осущест-
вить с использованием метода Жордана-Гаусса, например, по следующей
схеме.
                           Алгоритм перебора
1. Получить методом Жордана-Гаусса произвольную формулу общего реше-
ния вида (5). Положить N=1.

                                               15