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

UptoLike

ВУЗ: 

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

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

Рубрика: 

107 108
Рис. 7.5. Целевая функция прямой задачи не ограничена
Из рис. 7.5 видно, что прямая задача не имеет оптимального
плана вследствие неограниченности сверху ее целевой функции.
Двойственная задача (рис. 7.6) вообще не имеет допустимых планов.
Рис. 7.6. Система ограничений двойственной задачи
противоречива
ВТОРАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ
Для того чтобы планы Х
*
и У
*
пары двойственных за-
дач были оптимальными, необходимо и достаточно вы-
полнение условий:
.XсAY
;AXbY
**
**
0)()2
0)()1
=⋅−
=−⋅
Условия 1 и 2 называются условиями дополняющей
нежесткости.
Необходимость.
Пусть Х
*
и Y
*
– оптимальные планы пары
двойственных задач (7.5). Как было показано при доказательстве
леммы 1, для любых допустимых планов Х и Y выполняется со-
отношение:
.YbYAXсX
≤
≤
(7.9)
Следовательно, это соотношение справедливо и для опти-
мальных планов:
.bYAXYсX
****
≤≤ (7.10)
На основании первой теоремы двойственности для опти-
мальных планов Х
*
и Y
*
справедливо условие:
bYcХ
**
=
, (7.11)
и соотношение (7.10) превращается в равенство:
,bYAXYcX
****
==
отсюда получаем условия дополняющей нежесткости.
Достаточность. Пусть для некоторых допустимых планов
Х
*
и Y
*
выполняются условия дополняющей нежесткости. Тогда
из первого условия имеем:
,
***
AXYbY =
а из второго:
.сXAXY
***
=
Таким образом получаем:
**
сXbY = ,
и согласно лемме 2 Х
*
и Y
*
– оптимальные планы пары двойст-
венных задач, что и требовалось доказать. 
                                                                                    ВТОРАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ

                                                                        Для того чтобы планы Х* и У* пары двойственных за-
                                                                    дач были оптимальными, необходимо и достаточно вы-
                                                                    полнение условий:
                                                                                          1)     Y * ⋅ ( b − AX * ) = 0 ;
                                                                                          2)      (Y * A − с ) ⋅ X * = 0 .
                                                                        Условия 1 и 2 называются условиями дополняющей
                                                                    нежесткости.
                                                                        Необходимость. Пусть Х* и Y*– оптимальные планы пары
                                                                    двойственных задач (7.5). Как было показано при доказательстве
                                                                    леммы 1, для любых допустимых планов Х и Y выполняется со-
                                                                    отношение:
                                                                                           сX ≤ YAX ≤ Yb.                     (7.9)
                                                                        Следовательно, это соотношение справедливо и для опти-
    Рис. 7.5. Целевая функция прямой задачи не ограничена           мальных планов:
                                                                                             сX * ≤ Y * AX * ≤ Y * b.        (7.10)
    Из рис. 7.5 видно, что прямая задача не имеет оптимального
                                                                        На основании первой теоремы двойственности для опти-
плана вследствие неограниченности сверху ее целевой функции.
                                                                    мальных планов Х* и Y* справедливо условие:
Двойственная задача (рис. 7.6) вообще не имеет допустимых планов.
                                                                                                cХ * = Y * b ,               (7.11)
                                                                    и соотношение (7.10) превращается в равенство:
                                                                                               cX * = Y * AX * = Y * b ,
                                                                    отсюда получаем условия дополняющей нежесткости.
                                                                         Достаточность. Пусть для некоторых допустимых планов
                                                                    Х* и Y* выполняются условия дополняющей нежесткости. Тогда
                                                                    из первого условия имеем:
                                                                                                  Y *b = Y * AX * ,
                                                                    а из второго:
                                                                                                  Y * AX * = сX * .
                                                                    Таким образом получаем:
                                                                                                      Y * b = сX * ,
                                                                                          *       *
                                                                    и согласно лемме 2 Х и Y – оптимальные планы пары двойст-
         Рис. 7.6. Система ограничений двойственной задачи          венных задач, что и требовалось доказать.
                            противоречива
                                107                                                                             108

Страницы