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

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


2. Запомнить множество I N . Положить I =I N , J = J N .
3. Выбрать номер k из множества J. Заменить J на J\{k}.
4. Выбрать l ∈I такой, что a lk ≠0 . Если таких номеров l в I нет, то перейти к
п.7.
5. Если множество I N \ {l} ∪ {k} уже рассмотрено, то заменить I на I \ {l} и
перейти к п.6, иначе перейти к п.8.
6. Если I= Ø то положить I N и перейти к п.7, иначе перейти к п.4.
7. Если J=Ø, то останов - получены все возможные формулы общего ре-
шения, иначе перейти к п.3.
8. Осуществить преобразования Жордана -Гаусса с направляющим элемен-
том alk до получения в k-м столбце единичного вектора. Заменить N на N+1.
Положить I N =I N \ {l} ∪ {k} . Перейти к п.2 .
Пример 1. Найти базисные решения системы уравнений.
� x1 =2 −2 x 2
 �
   � x 3 =4 +x2
Решение. Здесь I={1,3},J={2}. Оформить процедуру решения удобно в виде
следующей таблицы, где через Aj обозначены векторы-столбцы матрицы
(столбцы коэффициентов при переменной xj).

  I      B    A1     A2        A3             alk    коммент.
  1      2      1          2        0        k=2     J1={2}
  3      4      0         -1        1    a12 =2
  2      1     1/2         1        0        k=1
  3      5     1/2         0        1    a21 -нет*   J2 ={1}
                                         a31 =1/2
  2     -4      0         1         -1   a23 -нет*   ОСТАНОВ
  1     10      1         0          2   a13 -нет*

* (выбор этого элемента порождает "старое" множество I)
На данных трех итерациях получены базисные решения системы соответст-
венно x1=(2,0,4), x2=(0,1,5), x3=(10,-4,0).
Как видно из рассмотренного примера, не все полученные в результате пере-
бора базисные решения системы линейных уравнений являются допустимы-
ми точками в соответствующей задаче линейного программирования (1) - (3),
так как не удовлетворяют условию неотрицательности (3). Процедуру пере-
бора можно модифицировать таким образом, чтобы перебирать только неот-
рицательные базисные решения. Изменения необходимо внести в 1, 3 и 4
пункты сформулированного алгоритма, которые приобретают следующий
вид.



                                         15