Задача линейного программирования. Горячев Л.В. - 11 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

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

Рубрика: 

11
Вектор A
2
и переменная x
2
заменяются на A
4
и x
4
соответственно. (Таблица 2):
c
0
x
1
1
x
2
2
x
1
3
x
0
4
x
0
5
x
0
6
x
1
7/10 1 1 2/10 3/10 0 −2/10 0
x
4
13/10 0 0 6/10 −1/10 1 −13/10 0
x
6
4/10 0 0 −2/10 2/10 0 −4/10 1
7/10 0 0 −8/10 −7/10 0 −2/10 0
опорный план x
2
= (71/10, 0, 0, 13/10, 0, 4/10)
(c, x
2
)=71/10
как мы видим из таблицы, все элементы z
j
− c
j
< 0, j =1, 2, 3, 4, 5, 6. Значит, полученный нами
план x
2
= (71/10, 0, 0, 13/10, 0, 4, 10) является оптимальным. Решение закончено.
Если ограничения-неравенства в задаче ЛП имеют вид ”≤”, то мы приводим задачу к канони-
ческому виду, вводя в каждое такое ограничение неотрицательную дополнительную переменную, в
результате единичный базис возникает естественным образом. Рассмотрим задачу:
2x
1
+7x
2
− max
−2x
1
+3x
2
≤ 14
x
1
+ x
2
≤ 8
x
1
,x
2
≥ 0
Вводя дополнительные переменные, приходим к канонической задаче
2x
1
+7x
2
− max
−2x
1
+3x
2
+ x
3
=14
x
1
+ x
2
+ x
4
=8
x
1
,x
2
≥ 0
В задачах на максимум для оптимальности опорного плана достаточно, чтобы z
j
− c
j
≥ 0,j=
1, 2,...,n.
Таблица 0:
c
0
x
1
1
x
2
2
x
1
3
x
0
4
x
3
14 0 −23 1 0
x
4
80 1 1 0 1
0 −7 −70 0
опорный план x
0
=(0, 0, 14, 8)
(c, x
0
)=0
Вектор, подлежащий в базис, находим, определяя
min{−2, −7} = z
2
− c
2
= −7
Вектор, исключаемый из базиса, определяется нахождением
min
x
3
x
32
,
x
4
x
42
= min
14
3
,
8
1
=
x
3
x
32
=
14
3
Следовательно, вектор A
3
в базисе заменяется на вектор A
2
, а переменная x
3
на x
2
. Таблица 1.
c
0
x
1
1
x
2
2
x
1
3
x
0
4
x
2
14/30−2/31 1/30
x
4
10/30 5/30−1/31
98/3 −207/30
опорный план x
1
=(0, 14/3, 0, 10/3)
(c, x
1
)=98/3
                                                                                                      11

Вектор A2 и переменная x2 заменяются на A4 и x4 соответственно. (Таблица 2):

                                   c0     x11      x22    x13     x04       x05    x06
                      x1    7/10   1      1       2/10   3/10     0       −2/10    0
                      x4   13/10   0      0       6/10   −1/10    1       −13/10   0
                      x6    4/10   0      0      −2/10   2/10     0       −4/10    1
                            7/10   0      0      −8/10   −7/10    0       −2/10    0

                           опорный план x2 = (71/10, 0, 0, 13/10, 0, 4/10)
                                        (c, x2 ) = 71/10

как мы видим из таблицы, все элементы zj − cj < 0, j = 1, 2, 3, 4, 5, 6. Значит, полученный нами
план x2 = (71/10, 0, 0, 13/10, 0, 4, 10) является оптимальным. Решение закончено.
   Если ограничения-неравенства в задаче ЛП имеют вид ”≤”, то мы приводим задачу к канони-
ческому виду, вводя в каждое такое ограничение неотрицательную дополнительную переменную, в
результате единичный базис возникает естественным образом. Рассмотрим задачу:

                                                2x1 + 7x2 − max
                                                −2x1 + 3x2 ≤ 14
                                                  x1 + x2 ≤ 8
                                                   x1 , x2 ≥ 0

Вводя дополнительные переменные, приходим к канонической задаче

                                          2x1 + 7x2 − max
                                        −2x1 + 3x2 + x3 = 14
                                          x1 + x2 + x4 = 8
                                             x1 , x2 ≥ 0

В задачах на максимум для оптимальности опорного плана              достаточно, чтобы zj − cj ≥ 0,   j =
1, 2, . . . , n.
    Таблица 0:
                                      c0 x11 x22 x13                x04
                              x3 14 0 −2 3         1                0
                              x4 8 0       1   1   0                1
                                      0 −7 −7 0                     0

                                   опорный план x0 = (0, 0, 14, 8)
                                            (c, x0 ) = 0
Вектор, подлежащий в базис, находим, определяя

                                    min{−2, −7} = z2 − c2 = −7

Вектор, исключаемый из базиса, определяется нахождением
                                                   
                                x3 x4            14 8     x3    14
                         min      ,      = min     ,    =     =
                               x32 x42            3 1     x32    3

Следовательно, вектор A3 в базисе заменяется на вектор A2 , а переменная x3 на x2 . Таблица 1.

                                             c0       x11   x22    x13     x04
                              x2   14/3       0      −2/3   1     1/3      0
                              x4   10/3       0      5/3    0     −1/3     1
                                            98/3      −2    0     7/3      0

                                опорный план x1 = (0, 14/3, 0, 10/3)
                                          (c, x1 ) = 98/3

Страницы