ВУЗ:
Составители:
Рубрика:
Линейное программирование
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
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »