Математическое программирование (линейное программирование). Киселева Э.В - 27 стр.

UptoLike

Рубрика: 

55 56
базис любой из свободных переменных и, следовательно, най-
денное опорное решение являлось бы оптимальным.
Итак,
5
x вводим в базис.
Далее необходимо выяснить, какую из базисных переменных
(
1
x или
2
x ) можно вывести из базиса, т.е. сделать равной нулю.
Так как
3
x и
4
x остаются свободными переменными, т.е.
0
43
== xx
, то система ограничений примет вид:
=+
=+
.xx
,xx
93
82
52
51
(*)
Если вывести из базиса
1
x
, т.е. положить
0
1
=
x
, то получим
4
5
=x , 3
2
=x , что недопустимо (0
j
x , 5,1=j ).
Если вывести из базиса
2
x
, то получим
0
2
=
x
,
3
5
=
x
,
2
1
=x , что соответствует опорному плану:
Т
X )3,0,0,0,2(
2
= ,
(
)
9
2
=XZ .
В этом случае
51
, xx
базисные переменные, а
432
,, xxx свободные переменные. Видим, что при переходе к
новому опорному плану значение целевой функции уменьши-
лось:
(
)
(
)
12
XZXZ <
.
Для ответа на вопрос, является ли опорное решение
2
X
оп-
тимальным, выразим функцию цели
543
37 xxxZ
=
через
свободные неизвестные
432
,, xxx .
С помощью второго уравнения системы ограничений мы ус-
тановили, что переменная
5
x вводится в базис вместо перемен-
ной
2
x , поэтому, выразив
5
x из второго уравнения
3
3
1
2
3
1
5
3 xxx =
и подставив его в целевую функцию
Z
, получим
98
432
+= xxxZ
.
Исключив
5
x из первого уравнения, перейдем к задаче:
min,98
432
+
=
xxxZ
.5,1,0
,3
,26
53
3
1
2
3
1
43
3
1
2
3
2
1
=
=+++
=++
jx
xxx
xxxx
j
Здесь
51
, xx базисные, а
432
,, xxx свободные переменные.
Замечаем, что в целевую функцию свободная переменная
4
x
входит с отрицательным коэффициентом –1, поэтому согласно
предыдущим рассуждениям опорный план
2
X
не является опти-
мальным. Достаточно ввести в базис свободную переменную
4
x ,
как значение функции уменьшится. Очевидно, при этом вывести
из базиса можно только переменную
1
x с помощью первого
уравнения системы ограничений.
Разделив первое уравнение на 6, выразив из него
4
x и под-
ставив его в функцию цели Z, получим задачу:
min98
3
1
3
18
1
2
9
8
1
6
1
++= xxxZ ,
,,j,x
,xxx
,xxxx
j
510
3
53
3
1
2
3
1
3
1
43
18
1
2
9
1
1
6
1
=
=+++
=++
где
54
, xx базисные переменные, а
321
,, xxx свободные пере-
менные. Положив
0
321
=
=
=
xxx , получим опорный план
Т
X )3,3/1,0,0,0(
3
= , причем
(
)
3
1
3
9=XZ .
Очевидно, что полученный опорный план является опти-
мальным, т.е.
Т
X )3,3/1,0,0,0(=
, .
3
1
9
min
=Z
Действительно, так как все коэффициенты при свободных
переменных
321
,, xxx неотрицательны в функции цели
базис любой из свободных переменных и, следовательно, най-                                    Z = x2 + 8 x3 − x4 − 9 → min,
денное опорное решение являлось бы оптимальным.
                                                                                             ⎧ x1 − 2 x 2 + 1 x3 + 6 x 4     = 2,
     Итак, x5 вводим в базис.                                                                ⎪      3       3
     Далее необходимо выяснить, какую из базисных переменных                                 ⎨
                                                                                             ⎪ + 1 x 2 + 1 x3           + x5 = 3,
( x1 или x 2 ) можно вывести из базиса, т.е. сделать равной нулю.                            ⎩      3       3
     Так как x3 и x 4 остаются свободными переменными, т.е.
                                                                                                      x j ≥ 0,     j = 1,5.
 x3 = x4 = 0 , то система ограничений примет вид:
                                                                            Здесь x1 , x5 − базисные, а x2 , x3 , x4 − свободные переменные.
                           ⎧ x1 + 2 x5 = 8,
                           ⎨                                      (*)       Замечаем, что в целевую функцию свободная переменная x 4
                           ⎩ x2 + 3 x5 = 9.                             входит с отрицательным коэффициентом –1, поэтому согласно
    Если вывести из базиса x1 , т.е. положить x1 = 0 , то получим       предыдущим рассуждениям опорный план X 2 не является опти-
x5 = 4 , x2 = −3 , что недопустимо ( x j ≥ 0 , j = 1,5 ).               мальным. Достаточно ввести в базис свободную переменную x 4 ,
    Если вывести из базиса x2 , то получим x2 = 0 , x5 = 3 ,            как значение функции уменьшится. Очевидно, при этом вывести
                                                                        из базиса можно только переменную x1 с помощью первого
x1 = 2 , что соответствует опорному плану:
                                                  ( )
                       X 2 = (2, 0, 0, 0, 3) Т , Z X 2 = −9 .
                                                                        уравнения системы ограничений.
                                                                            Разделив первое уравнение на 6, выразив из него x 4 и под-
       В      этом    случае       x1 , x5 − базисные   переменные, а   ставив его в функцию цели Z, получим задачу:
x 2 , x3 , x4 − свободные переменные. Видим, что при переходе к                            Z = 16 x1 + 89 x 2 + 8 18
                                                                                                                   1 x − 9 1 → min ,
                                                                                                                      3    3
новому опорному плану значение целевой функции уменьши-
лось:                                                                                        ⎧⎪ 16 x1 − 19 x2 + 181 x3 + x4     = 13 ,
                              ( ) ( )
                                  Z X 2 < Z X1 .
                                                                                              ⎨
                                                                                              ⎪⎩ + 13 x2 + 13 x3           + x5 = 3,
    Для ответа на вопрос, является ли опорное решение X 2 оп-                                          x j ≥ 0,    j = 1,5,
тимальным, выразим функцию цели Z = 7 x3 − x 4 − 3 x5 через
                                                                        где x4 , x5 − базисные переменные, а x1 , x 2 , x3 − свободные пере-
свободные неизвестные x 2 , x3 , x4 .
                                                                        менные. Положив x1= x2 = x3 = 0 , получим опорный план
                                                                                                                              ( )
    С помощью второго уравнения системы ограничений мы ус-
тановили, что переменная x5 вводится в базис вместо перемен-                          X 3 = (0, 0, 0, 1 / 3, 3) Т , причем Z X 3 = −9 13 .
ной x 2 , поэтому, выразив x5 из второго уравнения                          Очевидно, что полученный опорный план является опти-
                                                                        мальным, т.е.
                           x5 = 3 − 1 x2 − 1 x3
                                    3         3                                                                                1
и подставив его в целевую функцию Z , получим                                          X ∗ = (0, 0, 0, 1 / 3, 3) Т , Z min = −9 .
                                                                                                                               3
                        Z = x 2 + 8 x3 − x 4 − 9 .                          Действительно, так как все коэффициенты при свободных
    Исключив x5 из первого уравнения, перейдем к задаче:                переменных x1 , x 2 , x3 неотрицательны в функции цели
                                   55                                                                             56