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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
22
6,1,0
23
1
1
max232
6321
521
4321
654321
=≥
=+−
=+−
=+−+−
→
+
−
+
+
−
ix
xxxx
xxx
xxxx
xxxxxx
i
Решение.
2 -1 1 3 -2 1
B
C
B
x
A
1
A
2
A
3
A
4
A
5
A
6
Θ
x
4
3 1 -1 1 -1 1 0 0 ―
x
5
-2 1 1 -1 0 0 1 0 1
x
6
1 2 1 -3 1 0 0 1 2
j
∆
3 -6 3 -3 0 0 0
x
4
3 2 0 0 -1 1 1 0
x
1
2 1 1 -1 0 0 1 0
x
6
1 1 0 -2 1 0 -1 1
j
∆
9 0 -3 -3 0 6 0
На второй итерации получаем , что оценка Δ
2
<0, но в столбце A
2
нет поло-
жительных элементов . Это означает, что целевая функция не ограничена на
допустимом множестве, т.е.
+∞= )(
sup
xz
Ω
.
Задачи для самостоятельного решения
1. Решить симплекс- методом задачу ЛП, предварительно приведя ее к кано-
ническому виду.
22
4321
≤
+
−
+
−
xxxx
4,1,0
6242
122
4321
4321
=≥
≤+++
≤
−
+
+
jx
xxcxx
xxxbx
j
;
а в с а в с а в с а в с
1 2 3 -1 6 5 2 3 11 2 1 2 16 3 3 1
2 3 1 1 7 4 3 6 12 3 3 4 17 4 1 2
3 4 2 -1 8 6 1 5 13 5 2 -1 18 3 1 0
4 7 2 3 9 2 2 2 14 7 1 5 19 4 1 3
5 8 3 4 10 5 3 7 15 6 3 8 20 5 2 6
max
4321
→
+
−
−
axxxx
Линейное программирование


2 x1 −x 2 +x3 +3x 4 −2 x5 +x 6 → max
� −x1 +x 2 −x 3 +x 4           =1
 �
   � x1 −x 2 +      x5         =1
�    x1 −3x 2 +x 3         x 6 =2
�
x i ≥0, i =1,6
Решение.
                               2            -1             1       3       -2         1
    B         CB     x         A1           A2            A3       A4      A5         A6       Θ
    x4         3     1         -1            1            -1       1        0         0        ―
    x5        -2     1         1            -1             0       0       1          0        1
    x6         1     2         1            -3             1       0        0         1        2
         ∆j          3         -6            3            -3       0        0         0
    x4        3      2         0            0             -1       1         1        0
    x1        2      1         1            -1             0       0         1        0
    x6        1      1         0            -2             1       0        -1        1
         ∆j          9         0            -3            -3       0         6        0

На второй итерации получаем, что оценка Δ2 <0, но в столбце A2 нет поло-
жительных элементов. Это означает, что целевая функция не ограничена на
допустимом множестве, т.е. sup z ( x) =+∞ .
                                        Ω
                         Задачи для самостоятельного решения

1. Решить симплекс- методом задачу ЛП, предварительно приведя ее к кано-
                                                   ническому виду.
                        x1 −x2 −x3 +ax 4 → max

                                     −x1 +2 x 2 −x 3 +x 4 ≤2
                                    bx1 +x 2 +x 3 −2 x 4 ≤12
                                    2 x1 +cx 2 +4 x 3 +2 x 4 ≤6 ;
                                    x j ≥0, j =1,4
         а     в   с           а       в         с             а       в   с          а    в       с
1        2     3   -1     6    5       2         3        11   2       1   2     16   3    3       1
2        3     1   1      7    4       3         6        12   3       3   4     17   4    1       2
3        4     2   -1     8    6       1         5        13   5       2   -1    18   3    1       0
4        7     2   3      9    2       2         2        14   7       1   5     19   4    1       3
5        8     3   4      10   5       3         7        15   6       3   8     20   5    2       6



                                                     22

Страницы