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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
29
Так как в задаче присутствует только один базисный вектор 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
                                                               Линейное программирование


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

                            x1 +3 x 3 −x 4 −Mz1 −Mz 2 → max
                               2 x1 +4 x 2 − x 4 +z1 =9
                               −3x1 +2 x 2 + 3x 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 −x 3 −2 x5 → min
                          x1 −2 x 2 +x 4 =−3
                            3x 2 −x 4 +x 5 ≤5
                                     x 2 + x5 ≥3
                                     x3 −2 x 4 =2
                                     x j ≥0, j =1,5


                                             29

Страницы