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

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

Линейное программирование
16
2. Запомнить множество
N
I
. Положить .,
NN
JJII ==
3. Выбрать номер k из множества J. Заменить J на J\{k}.
4. Выбрать
I
l
∈
такой, что 0
≠
lk
a . Если таких номеров l в I нет, то перейти к
п .7.
5. Если множество
}{}{\ klI
N
∪
уже рассмотрено, то заменить I на
}
{
\
I
и
перейти к п .6, иначе перейти к п .8.
6. Если I= Ø то положить
N
I
и перейти к п .7, иначе перейти к п .4.
7. Если J=Ø , то останов - получены все возможные формулы общего ре-
шения, иначе перейти к п .3.
8. Осуществить преобразования Жордана -Гаусса с направляющим элемен -
том
lk
a до получения в k-м столбце единичного вектора. Заменить N на N+1.
Положить }{}{\ klII
NN
∪= . Перейти к п .2 .
Пример 1. Найти базисные решения системы уравнений.
+=
−=
23
21
4
22
xx
xx
Решение. Здесь I={1,3},J={2}. Оформить процедуру решения удобно в виде
следующей таблицы , где через A
j
обозначены векторы-столбцы матрицы
( столбцы коэффициентов при переменной x
j
).
I B A
1
A
2
A
3
a
lk
коммент.
1
3
2
4
1
0
2
-1
0
1
k=2
a
12
=2
J
1
={2}
2
3
1
5
1/2
1/2
1
0
0
1
k=1
a
21
-нет *
a
31
=1/2
J
2
={1}
2
1
-4
10
0
1
1
0
-1
2
a
23
-нет *
a
13
-нет *
ОСТАНОВ
* (выбор этого элемента порождает "старое " множество I)
На данных трех итерациях получены базисные решения системы соответст-
венно x
1
=(2,0,4), x
2
=(0,1,5), x
3
=(10,-4,0).
Как видно из рассмотренного примера, не все полученные в результате пере-
бора базисные решения системы линейных уравнений являются допустимы-
ми точками в соответствующей задаче линейного программирования (1) - (3),
так как не удовлетворяют условию неотрицательности (3). Процедуру пере-
бора можно модифицировать таким образом , чтобы перебирать только неот -
рицательные базисные решения. Изменения необходимо внести в 1, 3 и 4
пункты сформулированного алгоритма, которые приобретают следующий
вид. 
Линейное программирование


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. Осуществить преобразования Жордана -Гаусса с направляющим элемен-
том a lk до получения в k-м столбце единичного вектора. Заменить N на N+1.
Положить I N =I N \ {l} ∪ {k} . Перейти к п.2 .
Пример 1. Найти базисные решения системы уравнений.
� x1 =2 −2 x2
 �
   � x 3 =4 +x 2
Решение. Здесь 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
пункты сформулированного алгоритма, которые приобретают следующий
вид.



                                         16

Страницы