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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
28
Так как в задаче нет начального базиса , составим М -задачу.
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
. Поскольку на небазисном векторе оценка 0
2
=
∆
, то в задаче име-
ется бесчисленное множество решений.
Пример 2. Решить ЗЛП .
max3
431
→
−
+
xxx
2 94
421
=
−
+
xxx
3323
421
=
+
+
−
xxx
425
4321
=
+
+
+
xxxx
4,1,0 =≥ jx
j
Решение. 
Линейное программирование


Так как в задаче нет начального базиса, составим М-задачу.
3x1 +7 x 3 −x 4 −Mz1 −Mz 2 −Mz 3 → max
x1 +x 2 +2 x3 +x 4 +z1 =4
x1 −2 x 2 +3 x3 +z 2 =5
3x1 +7 x3 +2 x4 +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 +3x 3 −x 4 → max
                              2 x1 +4 x 2 − x 4 =9
                             −3 x1 +2 x 2 + 3 x 4 =3
                                 x1 +5 x 2 +x3 +2 x 4 =4
                                   x j ≥0, j =1,4
          Решение.


                                          28

Страницы