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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
36
Графический анализ показывает, что двойственная задача неразрешима
из-за неограниченности целевой функции, поэтому по свойству 3 исходная
задача неразрешима из-за пустоты допустимого множества.
Пример 4. Определить, являются ли данные векторы
x
и
y
оптималь-
ными решениями данной задачи и двойственной к ней:
max810
321
→
+
+
xxx
24
321
=
+
+
xxx
02
321
=
−
+
xxx
0,0,0
321
≥
≥
≥
xxx
()
−==
2
7
,
2
9
,1,0,1 yx
Решение. Решение данной задачи осуществляется в несколько этапов :
1) подставим точку
(
)
1,0,1
=
x в ограничения исходной задачи ; так как точка
удовлетворяет ограничениям , переходим к следующему этапу;
2) построим двойственную задачу
min2
1
→
y
1
21
≥
+
yy
1024
21
≥
+
yy
8
21
≥
−
yy ;
3) подставим точку
−=
2
7
,
2
9
y
в ограничения двойственной задачи ; точка
удовлетворяет ограничениям , переходим к следующему этапу;
4) подставим точку
(
)
1,0,1
=
x
в целевую функцию исходной задачи , а точку
−=
2
7
,
2
9
y - в целевую функцию двойственной задачи ; полученные зна-
чения совпадают, поэтому по свойству 4 данные точки являются соответ-
ственно решением исходной и двойственных задач.
Пример 5. Найти решение следующей ЗЛП путем графического ана-
лиза двойственной задачи :
max5
4321
→
+
+
+
xxxx
164
431
=
+
+
xxx
446
4321
=
+
−
−
xxxx
0,0,0,0
4321
≥
≥
≥
≥
xxxx .
Решение.
Двойственная задача запишется в виде
min416
21
→
+
yy
564
21
≥
+
yy
14
2
≥
−
y
Линейное программирование


      Графический анализ показывает, что двойственная задача неразрешима
из-за неограниченности целевой функции, поэтому по свойству 3 исходная
задача неразрешима из-за пустоты допустимого множества.

      Пример 4. Определить, являются ли данные векторы x и y оптималь-
ными решениями данной задачи и двойственной к ней:
                                x1 +10 x 2 +8 x 3 → max
                                    x1 +4 x 2 +x 3 =2
                                    x1 +2 x 2 −x 3 =0
                                     x1 ≥0, x 2 ≥0, x 3 ≥0
                                                       � 9 7�
                                     x =(1,0,1), y =� ,− �
                                                        � 2 2�
      Решение. Решение данной задачи осуществляется в несколько этапов:
1) подставим точку x =(1,0,1) в ограничения исходной задачи; так как точка
   удовлетворяет ограничениям, переходим к следующему этапу;
2) построим двойственную задачу
                                        2 y1 → min
                                        y1 +y 2 ≥1
                                       4 y1 +2 y 2 ≥10
                                        y1 −y 2 ≥8 ;
                         � 9 7�
3) подставим точку y =� ,− � в ограничения двойственной задачи; точка
                          � 2 2�
   удовлетворяет ограничениям, переходим к следующему этапу;
4) подставим точку x =(1,0,1) в целевую функцию исходной задачи, а точку
       � 9 7�
   y =� ,− � - в целевую функцию двойственной задачи; полученные зна-
        � 2 2�
   чения совпадают, поэтому по свойству 4 данные точки являются соответ-
   ственно решением исходной и двойственных задач.
           Пример 5. Найти решение следующей ЗЛП путем графического ана-
      лиза двойственной задачи:
                                5 x1 +x 2 +x 3 +x 4 → max
                                   4 x1 +      x 3 +x 4 =16
                                  6 x1 −4 x 2 −x 3 +x 4 =4
                              x1 ≥0, x 2 ≥0, x 3 ≥0, x 4 ≥0 .
                                           Решение.
           Двойственная задача запишется в виде
                                     16 y1 +4 y 2 → min
                                        4 y1 +6 y 2 ≥5
                                           −4 y 2 ≥1

                                   36

Страницы