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