Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 40
Текст из файла (страница 40)
(14> Таким образом, 7(х))4(Л), УхяХ, Л ЕЛ. (15) Последовательно переходя в неравенстве (15) сначала к нижней грани по х Е Х, затем к верхней грани по Л ЕЛ, убеждаемся, что величины 7'„ф" конечны и удовлетворяют неравенству (13), Лемма 3 доказана. П * Выясним, как выглядит задача, двоиственная по отношению к двойственной задаче (11), (12). Замечательно, что эта задача, оказывается, с точностью до эквивалентной формы совпадает с исходной задачей (1), (2). Чтобы убедиться в этом, перепишем задачу (11), (12) в равносильном виде, как задачу минимизации: — й(Л)=(Ь„Л,)+(Ь„Л,)- !пЕ, Л ЕЛ, Л=(Л =(Л„Лт): Л, ЕЕ ', Лз ЕЕ"', ( — А,",)Л, +( — А~~~)Л, < с„(16) по форме совпадающей с исходной задачей (1), (2), и затем, пользуясь тем же правилом, с помощью которого была сконструирована двойственная задача (11), (12) на основе исходной задачи (1), (2), составим двойственную к (13) задачу, Обозначив двойственные к Л = (Л„Л,) переменные через х = (х„л ), придем к следующей задаче: -(с„х,) — (с, х,) — зпР, х = (хп хз) Е М М=(х=(х„хл): х, Е Е'~, х, б Е'*, ( — А",;)тх,+( — Ат)тх,+Ь, ) О, (17) ( — Ат) х, +( — Агт)тхз+ 52=0, х, ) 0), являющейся двойственной по отношению к задаче (16).
Так как ( — А;.,'.)т = = — Аи, т', ~' =1, 2, то нетрудно видеть, что М = Х и задача (17) равносйльна задаче (1), (2). Таким образом, с учетом сделанных эквивалентных переходов от задачи (11), (12) к задаче (16), от (17) к (1), (2), можем сказать, что задача, двойственная по отношению к двойственной задаче (11), (12), совпадает с исходной задачей (1),(2), и, следовательно, задачи (1),(2) и (11), (12) образуют пару взаимодвойственных задач. Оказывается, параллельное изучение взаимодвойственных задач способствует более глубокому понима- нию природы этих задач, оказывается полезным при разработке методов их решения, обогащает теорию линейного программирования.
Связь между взаимодвойственными задачами (1), (2) и (11), (12) отражена в следующих теоремах, называемых теоремами двойственности. Теорема 2. Задача (1), (2) имеет решение тогда и только тогда, когда имеет решение двойственная к нгй задача (11), (12). Иначе говоря, взаимодвойствгнныг задачи линейного программирования либо обг одновременно разрешимы, либо ни одна из них нг имеет решения. Если задачи (1), (2) и (11), (12) разрешимы, то значения их экстремумов совпадают, т. в. Л=Ф* (16> Доказательство. Пусть задача (1), (2) имеет решение, т. е.
Х,~И. Возьмем произвольную точку х, Е Х,. Согласно лемме 2 тогда существует точка Л* е Л, для которой справедливо равенство (10). Таким образом, Л ф И, и, кроме того, 7", = 7"(х„) = й (Л*) < й '. Отсюда и из (13) следует Л = 7(х.) = чЬ(Л *) = Ф*, т. е. Л' е Л". Таким образом, из разрешимости задачи (1), (2) следует разрешимость двойственной к ней задачи (11), (12). Так как задача (1), (2) в свою очередь является двойственной к двойственной задаче (11), (12), то из разрешимости задачи (11), (12) следует разрешимость задачи (1), (2), причем ф' = ~'„. Теорема 2 доказана. П Теорема 3.
Взаимодвойствгнныв задачи(1), (2) и(11), (12) имеют решение тогда и только тогда, когда существуют точки х, = (х,„, т,), Л*=(Л*„Л;) такив, что х, Е Х, Л* Е Л, 7(х,) = ф(Л*). (19) Соотношения (19) справедливы для всех точек х. а Х„Л' Е Л* и только для них.
Доказательство. Необходимость. Пусть задачи (1), (2) и (11), (12) разрешимы, т. е. Х, ~ И, А* ~И. Возьмем л|обые точки х. е Х., Л*ЕЛ. Это означает, что х„Е Х„7"(х,)=7"„Л*ЕЛ, й (Л*) =Ф'. Но согласно теореме 2 тогда 7", = ф*, поэтому 7" (х,) = ф(Л*). Таким образом, в качестве точек х., Л*, удовлетворяющих условйям (19), можно взять любые точки из множеств Х„Л. Достаточность.
Пусть для каких-то точек х„=(х„,х„), Л*= = (Л;, Л,*) выполняются соотношения (19). Это значит, что множества Х и Л непусты и по лемме 3 тогда 7, > — со, 4 * <+со. Отсюда, из теоремы 1 и следствия к ней следует, что задачи (1), (2) и (11), (12) разрешимы, т. е, Х, ф И, Л ф И. Согласно теореме 2 тогда 7'„= 4*. Отсюда и из (19) имеем ,7, < 7'(х,) = 4~(Л*) < 4* = 7;. Это значит, что все неравенства здесь обращаются в равенства, т. е. 7(х„) = 7'„, ф(Л*) = 4~* и, следовательно, х, е Х„ Л* Е Л, Теорема 3 доказана.
П 3 а и е ч а н и е. Условия (19) равносильны условиям х, Е Х, Л' Е Л, 7" (х„) (~ ф(Л'). (20) В самом деле, совмещая неравенство из (20) с неравенством (15) при х = х„ Л = Л*, приходим к равенству 7(х,) = ф(Л*). Теорема 4. Взаимодвойстввнныг задачи(1), (2) и(11), (12) имеют решение тогда и только тогда, когда существуют точки х, = (х,„, х„), Л' = (Л;, Л;) такие, что х, Е Х Л* Е Л, х,',(А т Л; + Ат Л* + с, )' = О, 1' = 1,..., и„ ! гд "' 4!В . 142 Гл.
3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Соотношения (21) справедливы для всех точек х, е Х„Л' е Л и только для них. Равенства из (21) называются условиями дополняющей нежесткости (ср. с аналогичными условиями из $2.3, теорема 2). Доказательство. Необходимость. Пусть задачи (1), (2) и (11), (12) имеют решение. Согласно теореме 3 тогда условия (19) справедливы при всех х, Е Х„Л'еЛ. В частности, Х(х,) — ф(Л*)=0. Отсюда и из (14) заключаем, что при х=х„Л =Л' все неравенства в (14) обращаются в равенство, что с учетом ограничений (2), (12) возможно только при ч (А т Л ! + А от! Лг + с„х,„) = ~ , '(А !т! Л,* + А от Лг + с )! х,', = О.
(22) !'=1 В силу (2), (12) каждое слагаемое в сумме (22) неотрицательно, Поэтому из (22) следуют первые равенства (21). Для доказательства остальных равенств (21) воспользуемся неравенствами Х(х) — ф(Л) = (с„х!) + (с„хг) + (Ь|, Л!) + (Ьг, Л,) > >( — А";Л, — Ат,Л, х,)-1-( — А'гЛ АтгЛг хг)+ +(Ь„Л,)+(Ь,Л ) =(Ь, — Апх, — А, х„Л,)+ +(Ь,— Аг,х! — Аггхг, Л,) >О Чх ЕХ, !УЛ ЕЛ! (23) аналогичными (14) и также вытекагощими из определений (2), (12) множеств Х, Л. Из (23) при х = х„, Л = Л* с учетом равенства (19) имеем (Ь, — Апх,„— А!гхг„Л,") = ~ (Ь, — Апх,.— А, т,)'(Л;)!=О.
(24) !=! Из неотрицательности каждого слагаемого в сумме (24) следует вторая группа равенств (21). Достаточность. Пусть для каких-то точек х, = (хьо х,), Л* = = (Л;, Л;) выполнены условия (21). Тогда для них справедлйвы равенства (22), (24). Отсюда и из (2), (12) следует, что в (23) при х = х„, Л = Л" все неравенства обращаются в равенства и, следовательно, Х(х,) = гр(Л"). Таким образом, точки х„, Л* удовлетворяют условиям (19).
Согласно теореме 3 тогда х, е Х„Л* е Л*. Теорема 4 доказана. П Покажем, что двойственные переменные в задачах линейного программирования можно истолковать как обобщение понятия множителей Лагранжа, используемых в классическом анализе при исследовании задач на условный экстремум, см. гл, 2. Введем функцию Х (х,Л)=(с„х!)+(сг,хг)+(Л„А!!х!+А!гхг — Ь,)+(Л„Аг,х,+Аггтг — Ь,) (25) переменных х = (х„т ) Е Хо = (х = (х„х ): х, Е Е"', х ц Е, х! > О), Л = = (Л„Л,) Е Ло = (Л = (Л„Лг): Л, е Е"', Л, е Е~, Л, > 0). Эта функция называется функцией Лаграйжа задачи (1), (2), переменные Л =(Л„Л,) называются множителями Лагранжа, причем Л, > 0 — множители, соответствующие ограничениям типа неравенств в определении множества (2), Лг — множители, соответствующие ограничениям типа равенств, Пользуясь тождеством (Аих,, Л!) = (х,, АтЛ!), функцию (25) можно записать в виде Х (х, Л ) = ( — Ь|, Л,) + ( — Ьг, Лг) + (х > А~~! Л, + Аг"! Л, + с ) + + (хг, А",гЛ, + АгтгЛг+ сг), х Е Хо, Л Е Л .
(26) '! г 'й1,:* „ '„г' ЦЬ': ! ,! " 4 з, УслОВие РАзРешимОсти. теОРемы ДВОЙстВеннОсти 143 О п редел е н и е 1. Точка (х„Л') Е Хо хЛ называется седловой точкой функции Лагранжа, если Х (х„Л) < Х (х„Л') < Х (х, Л*) Чх Е Хо, !гЛ Е Ло. (27) Т е о р е м а 5. Взаимодвойстввнныв задачи (1), (2) и (11), (12) имеют Решение тогда и только тогда, когда сУЩествУют точки х„=(х„, тг,ХЕ Е Хо, Л* = (Л;, Л;) Е Л, образующие сгдловую точку (х„, Л") функции Лагранжа. Точка (х., Л ) е Х, х Ло будет свдловой точкой тогда и только тогда, когда х. е Х„Л 'Е Л', т, е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
