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