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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
28
Так как в задаче присутствует только один базисный вектор A
3
, составим М -
задачу, добавив искусственные переменные в 1 и 2 ограничение.
max3
21431
→
−
−
−
+
MzMzxxx
2 94
1421
=
+
−
+
zxxx
3323
2421
=
+
+
+
−
zxxx
425
4321
=
+
+
+
xxxx
4,1,0 =≥ jx
j
.
Запишем данные в таблицу.
1 0 3 -1 -M -M
B
C
B
x
A
1
A
2
A
3
A
4
z
1
z
2
Θ
z
1
-M 9 2 4 0 -1 1 0 9/4
z
2
-M 3 -3 2 0 3 0 1 3/2
x
3
3 4 1 5 1 2 0 0 4/5
α 12
2
15 0 7
0 0
β -12 1 -6
0
-2 0 0
z
1
-M 4 1 0 2 1
1
0
z
2
-M 7/5 -17/5
0 -2/5 11/5 0 1
x
2
0 4/5 1/5 1 1/5 2/5 0 0
α 0 -1
0 -3 1
0 0
β -36/5
11/5
0 6/5 2/5
0 0
Как видно из данной таблицы , дальнейшее улучшение решения невозможно,
так как во 2-й оценочной строке не оказалось отрицательных элементов .
Следовательно, достигнуто оптимальное решение М - задачи . Но искусствен -
ные переменные
21
, zz не выведены из базиса и не равны нулю, следова-
тельно исходная задача не имеет решения, так как ее допустимое множество
пусто.
Задачи для самостоятельного решения
1. Решить М - методом задачу ЛП, предварительно приведя ее к канониче-
скому виду.
min2
5321
→
−
−
+
xxxx
32
421
−
=
+
−
xxx
5,1,0
22
3
53
43
52
542
=≥
=−
≥+
≤
+
−
jx
xx
xx
xxx
j
Линейное программирование


Так как в задаче присутствует только один базисный вектор A 3, составим М-
задачу, добавив искусственные переменные в 1 и 2 ограничение.

                            x1 +3 x 3 −x 4 −Mz1 −Mz 2 → max
                               2 x1 +4 x 2 − x 4 +z1 =9
                               −3 x1 +2 x 2 + 3 x 4 +z 2 =3
                                     x1 +5 x 2 + x 3 +2 x 4 =4
                                      x j ≥0, j =1,4 .
Запишем данные в таблицу.

                        1       0        3         -1     -M     -M
B        CB      x     A1       A2       A3        A4      z1     z2    Θ
z1       -M     9       2       4        0         -1      1      0    9/4
z2       -M     3      -3       2        0          3      0      1    3/2
x3        3     4       1       5        1          2      0      0    4/5
     α          12      2       15        0         7      0      0
     β         -12       1      -6        0         -2     0      0
z1       -M     4        1      0         2          1     1      0
z2       -M    7/5    -17/5      0      -2/5       11/5    0      1
x2        0    4/5      1/5      1       1/5        2/5    0      0
     α          0       -1       0       -3         1      0      0
     β        -36/5    11/5      0       6/5       2/5     0      0

Как видно из данной таблицы, дальнейшее улучшение решения невозможно,
так как во 2-й оценочной строке не оказалось отрицательных элементов.
Следовательно, достигнуто оптимальное решение М- задачи. Но искусствен-
ные переменные z1 , z 2 не выведены из базиса и не равны нулю, следова-
тельно исходная задача не имеет решения, так как ее допустимое множество
пусто.
                  Задачи для самостоятельного решения

1. Решить М- методом задачу ЛП, предварительно приведя ее к канониче-
   скому виду.
                       x1 +x 2 −x3 −2 x 5 → min
                          x1 −2 x 2 +x 4 =−3
                            3x 2 −x 4 +x5 ≤5
                                      x 2 + x5 ≥3
                                      x 3 −2 x 4 =2
                                      x j ≥0, j =1,5


                                              28

Страницы