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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
36
1
21
≥
−
yy
1
21
≥
+
yy
Графический анализ этой задачи показан на следующем рисунке .
Оптимальным решением является вектор
−=
4
1
,
8
13
*
min
Y , 25
*
min
=z . На ос -
новании второй теоремы двойственности для вектора x*,являющегося реше-
нием исходной задачи должны, выполняться равенства 0)564(
*
2
*
1
*
1
=−+ yyx
0)1(
*
2
*
1
*
3
=−− yyx
0)14(
*
2
*
2
=−− yx 0)1(
*
2
*
1
*
4
=−+ yyx .
Подставляя координаты вектора
,
*
min
Y
получаем , что переменные
3
x и
4
x
исходной задачи должны обращаться в нуль. Тогда из исходной системы по-
лучаем 164
1
=
x , откуда 4
1
=
x , и 446
21
=
−
xx , откуда 5
2
=
x . Следователь-
но, решением исходной задачи является вектор )0,0,5,4(
*
max
=X . При этом
54*5
*
max
+= z =25.
Пример 6. Определить решение двойственной задачи к задаче из при-
мера 1 § 4, используя решение исходной задачи .
Решение.
В соответствии с замечанием 1 оптимальным решением двойственной
задачи является вектор
()
=
−
==
−
1
4
3
110
010
011
1,2,3
1
Bcy
T
B
, где матрица
1−
B
Рис. 8
y
1
, y
2
≥0
Y2
Y1
Y*
.
d=0
d=9
Линейное программирование


                                      y1 −y 2 ≥1
                                      y1 +y 2 ≥1
                                      y1, y2≥0
           Графический анализ этой задачи показан на следующем рисунке.


             Y2


                                                              Y1
                             .
                          Y*min
                                  d=9
                       d=0

                                    Рис. 8

                                             � 13 1 �
Оптимальным решением является вектор Ymin
                                        *
                                           =�    ,− � , z min
                                                           *
                                                               =25 . На ос-
                                              � 8 4�
новании второй теоремы двойственности для вектора x*,являющегося реше-
нием исходной задачи должны, выполняться равенства x1* (4 y1* +6 y 2* −5) =0
x 3* ( y1* −y 2* −1) =0
x 2* (−4 y 2* −1) =0              x 4* ( y1* +y 2* −1) =0 .
                                   *
Подставляя координаты вектора Ymin    , получаем, что переменные x 3 и x 4
исходной задачи должны обращаться в нуль. Тогда из исходной системы по-
лучаем 4 x1 =16 , откуда x1 =4 , и 6 x1 −4 x 2 =4 , откуда x 2 =5 . Следователь-
                                               *
но, решением исходной задачи является вектор X max =(4,5,0,0) . При этом
 *
zmax =5 * 4 +5 =25.
      Пример 6. Определить решение двойственной задачи к задаче из при-
мера 1 § 4, используя решение исходной задачи.
Решение.
      В соответствии с замечанием 1 оптимальным решением двойственной
                                          � 1 1 0� � 3�
                                           �           � � �
задачи является вектор y =c B B =(3, 2,1)� 0 1 0 � =� 4 � , где матрица B −1
                            T −1

                                             � 0 −1 1 � � 1 �
                                              �         � � �




                                              36

Страницы