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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
27
Так как в задаче нет начального базиса, составим М -задачу.
max73
321431
→
−
−
−
−
+
MzMzMzxxx
42
14321
=
+
+
+
+
zxxxx
532
2321
=
+
+
−
zxxx
13273
3431
=
+
+
+
zxxx
4,1,0 =≥ jx
j
Запишем данные в таблицу.
3 0 7 -1 -M -M -M
B
C
B
x
A
1
A
2
A
3
A
4
z
1
z
2
z
3
Θ
z
1
-M 4 1 1 2 1 1 0 0 4
z
2
-M 5 1 -2 3 0 0 1 0 5
z
3
-M 13 3 0 7 2 0 0 1
4
3
1
α 0
-3 0 -7 1
0 0 0
β -21
- 5 1
-12
- 3 0 0 0
x
1
3 4 1 1 2 1
0 0 2
z
2
-M 1 0 -3 1 -1 1 0 1
z
3
-M 1 0 -3 1 -1 0 1 1
α 12 0
3 -1 4
0 0
β -2 0
6
-2
2
0 0
x
1
3 2 1 7 0 3 0
x
3
7 1 0 -3 1 -1 0
z
3
-M 0 0 0 0 0 1
α 13 0 0 0 3 0
На данной итерации получено, что третье уравнение в системе, определяю-
щей х , является лишним . Исключая его, получаем эквивалентную систему.
Так как все Δ
j
= α
j
≥ 0, то останов , найдена оптимальная точка (2,0,1,0)x =
*
.
13
*)
(
=
x
L
. Поскольку на небазисном векторе оценка 0
2
=
∆
, то в задаче име-
ется бесчисленное множество решений.
Пример 2. Решить ЗЛП .
max3
431
→
−
+
xxx
2
94
421
=
−
+
xxx
3323
421
=
+
+
−
xxx
425
4321
=
+
+
+
xxxx
4,1,0 =≥ jx
j
Решение. 
                                                               Линейное программирование


Так как в задаче нет начального базиса, составим М-задачу.
3 x1 +7 x3 −x 4 −Mz1 −Mz 2 −Mz 3 → max
x1 +x 2 +2 x 3 +x 4 +z1 =4
x1 −2 x2 +3x3 +z 2 =5
3 x1 +7 x3 +2 x 4 +z 3 =13
x j ≥0, j =1,4
Запишем данные в таблицу.

                     3       0         7         -1       -M        -M    -M
 B        CB    x    A1      A2        A3        A4        z1        z2    z3    Θ
 z1       -M   4     1        1        2         1         1         0     0      4
 z2       -M    5    1       -2        3         0         0         1     0      5
 z3       -M   13    3        0        7         2         0         0     1     4 13
      α 0            -3      0         -7        1         0        0      0
      β-21           -5       1       -12        -3        0        0      0
x1   3  4            1        1        2         1                  0      0      2
z2 -M   1            0       -3        1         -1                 1      0      1
z3 -M   1            0       -3        1         -1                 0      1      1
   α   12            0       3         -1        4                  0      0
   β    -2           0       6         -2        2                  0      0
x1   3  2            1        7        0         3                         0
x3   7  1            0       -3        1         -1                        0
z3 -M   0            0       0         0         0                         1
   α   13            0       0         0         3                         0

На данной итерации получено, что третье уравнение в системе, определяю-
щей х , является лишним. Исключая его, получаем эквивалентную систему.
Так как все Δj = α j ≥ 0, то останов, найдена оптимальная точка x * =(2,0,1,0) .
L( x*) =13 . Поскольку на небазисном векторе оценка ∆2 =0 , то в задаче име-
ется бесчисленное множество решений.

Пример 2. Решить ЗЛП .
                                  x1 +3 x3 −x 4 → max
                                 2 x1 +4 x 2 − x 4 =9
                                 −3 x1 +2 x 2 + 3x 4 =3
                                   x1 +5 x 2 + x 3 +2 x 4 =4
                                     x j ≥0, j =1,4
          Решение.


                                            27

Страницы