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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
37
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*
min
.
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) . При этом
  *
z max =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 �
                                              �         � � �




                                              37

Страницы