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

UptoLike

ВУЗ: 

НГАСУ «Сибстрин» | Новосибирск

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

Рубрика: 

99 100
.y,y
,yy
,yy
,yyW
00
62
2
min1110
21
21
21
21
≥≥
⎩
⎨
⎧
≥+
≥−
→+=
Как в исходной, так и в двойственной задаче число неизвест-
ных равно двум. Следовательно, их решение можно найти графи-
ческим методом.
Рис. 7.1.
max
Z достигается в точке B
Рис. 7.2.
min
W достигается в точке Е
Как видно из рис. 7.1, максимальное значение целевая функ-
ция исходной задачи принимает в точке В. Следовательно,
Х
*
=(3,7) является оптимальным планом, при котором Z
max
=48.
В двойственной задаче (рис 7.2) ОДР не ограничена. Мини-
мальное значение целевая функция двойственной задачи прини-
мает в точке Е, т.е.
⎟
⎠
⎞
⎜
⎝
⎛
=
3
4
,
3
10
*
Υ
и
.48
min
=
W
Таким обра-
зом, значения целевых функций исходной и двойственной задач
при их оптимальных планах равны между собой.
Далее будет показано, что для любой пары двойственных за-
дач, имеющих оптимальные решения, экстремальные значения
целевых функций совпадают (Z
max
=W
min
).
7.4. Основные теоремы двойственности
Приступим к изучению связей между прямой и двойственной
задачами. Для определенности рассмотрим симметричную пару
двойственных задач и применительно к ней сформулируем ос-
новные утверждения теории двойственности.
Итак, пусть имеем пару двойственных задач: 
                       W = 10 y1 + 11 y 2 → min ,
                        ⎧ y1 − y 2 ≥ 2 ,
                        ⎨
                        ⎩ y1 + 2 y2 ≥ 6 ,
                        y1 ≥ 0 , y 2 ≥ 0.
    Как в исходной, так и в двойственной задаче число неизвест-
ных равно двум. Следовательно, их решение можно найти графи-
ческим методом.



                                                                                Рис. 7.2. Wmin достигается в точке Е

                                                                      Как видно из рис. 7.1, максимальное значение целевая функ-
                                                                  ция исходной задачи принимает в точке В. Следовательно,
                                                                  Х*=(3,7) является оптимальным планом, при котором Zmax=48.
                                                                      В двойственной задаче (рис 7.2) ОДР не ограничена. Мини-
                                                                  мальное значение целевая функция двойственной задачи прини-
                                                                                           *     ⎛ 10  4 ⎞
                                                                  мает в точке Е, т.е. Υ       = ⎜    , ⎟    и W min = 48 . Таким обра-
                                                                                                 ⎝ 3   3 ⎠
                                                                  зом, значения целевых функций исходной и двойственной задач
                                                                  при их оптимальных планах равны между собой.
                                                                      Далее будет показано, что для любой пары двойственных за-
                                                                  дач, имеющих оптимальные решения, экстремальные значения
                                                                  целевых функций совпадают (Zmax=Wmin).
                                                                              7.4. Основные теоремы двойственности
                 Рис. 7.1. Z max достигается в точке B                Приступим к изучению связей между прямой и двойственной
                                                                  задачами. Для определенности рассмотрим симметричную пару
                                                                  двойственных задач и применительно к ней сформулируем ос-
                                                                  новные утверждения теории двойственности.
                                                                      Итак, пусть имеем пару двойственных задач:



                                99                                                                     100

Страницы