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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
16
1а . Получить произвольное неотрицательное базисное решение. Положить
N=1.
3а . Выбрать
J
k
∈
такое , что 0
>
∃
ik
a . Заменить J на J\{k}.
4а . Выбрать
I
l
∈
такое , что
ik
i
ai
lk
l
a
b
a
b
ik
min
0: >
= . Если таких номеров l в I нет , то
перейти к п.7.
Пример 2. Найти неотрицательные базисные решения системы уравнений.
=+++
=−++
532
254
4321
4321
xxxx
xxxx
Решение.
После эквивалентных преобразований данная система может быть переписа-
на следующим образом :
++=
−−=
214
213
2
1
4
3
4
2
7
4
11
xxx
xxx
Положим N=1. Тогда I
1
={3,4},J
1
={1,2}..
Как и в примере 1, оформим решение в виде в таблицы . Добавим столбец Θ ,
в который будем помещать отношение b
i
/a
ik
для
a
ik
>0
I b A
1
A
2
A
3
A
4
Θ a
lk
коммент .
3
4
11/4
3/4
7/2
-1/2
4
-1
1
0
0
1
11/16
-
k=2,l=3
a
32
=4
J
1
={1,2}
2
4
11/16
23/16
7/8
3/8
1
0
1/4
1/4
0
1
11/14
23/6
k=1,l=2
a
21
=7/8
J
2
={1,3}
1
4
11/14
8/7
1
0
8/7
-3/7
2/7
1/7
0
1
k=2
a
12
-нет
k=3
a
13
-нет
ОСТАНОВ
На данных итерациях получены базисные решения системы соответственно
),0,0,(),x,0,(0,x),(0,0,x
7
8
11
3
4
3
16
11
4
3
4
11
===
21
, .
Задачи для самостоятельного решения
1. Найти все базисные решения следующих систем уравнений:
а )
xxxx
1234
241
−
+
−
=
2323
1234
xxxx
+
+
+
=
;
б) xxxx
1234
3
+
+
+
=
222
1234
xxxx
−
+
−
=
; 
Линейное программирование


1а. Получить произвольное неотрицательное базисное решение. Положить
N=1.
3а. Выбрать k ∈ J такое, что ∃a ik >0 . Заменить J на J\{k}.
                                       b            b
4а. Выбрать l ∈ I такое, что l =min i . Если таких номеров l в I нет, то
                                       alk i:aik >0 aik
перейти к п.7.
Пример 2. Найти неотрицательные базисные решения системы уравнений.
           � 4 x1 +5 x 2 +x3 −x 4 =2
            �
              � 2 x1 +x 2 +x3 +3x 4 =5
Решение.
После эквивалентных преобразований данная система может быть переписа-
на следующим образом:
�                   11 7
  ��       x    3 =   − x1 −4 x2
                     4 2
     �
       � x = 3 +1 x +x
        �� 4 4 2 1             2

Положим N=1. Тогда I 1={3,4},J 1={1,2}..
Как и в примере 1, оформим решение в виде в таблицы. Добавим столбец Θ,
в который будем помещать отношение bi /aik для aik >0

 I      b     A1     A2      A3    A4     Θ          alk    коммент.
 3    11/4     7/2      4     1    0    11/16    k=2,l=3    J1={1,2}
 4     3/4    -1/2     -1     0    1      -       a 32 =4
 2    11/16    7/8      1    1/4   0    11/14    k=1,l=2    J2 ={1,3}
 4    23/16    3/8      0    1/4   1    23/6    a21 =7/8
 1    11/14     1      8/7   2/7   0                k=2     ОСТАНОВ
 4     8/7      0     -3/7   1/7   1             a12 -нет
                                                    k=3
                                                 a13 -нет

На данных итерациях получены базисные решения системы соответственно
x 1 =(0,0, 11
           4 4
              , 3 ), x 2 =(0, 16
                              11
                                 ,0, 43 ),x 3 =( 14
                                                 11
                                                    ,0,0, 78 ) .

                 Задачи для самостоятельного решения

1. Найти все базисные решения следующих систем уравнений:
      а) x 1 −2x 2 +4 x 3 −x 4 =1
         2 x 1 +3x 2 +x 3 +2x 4 =3 ;
      б) x 1 +x 2 +x 3 +x 4 =3
          2 x 1 −x 2 +x 3 −2x 4 =2 ;

                                   16

Страницы