Ф.П. Васильев - Методы оптимизации (1125241), страница 42
Текст из файла (страница 42)
Пример 1. Исходная задача: У(х) = х' — 2хз- 1п1, х е Х =(х = = (х' хз) > 0: х' — хз = 1, х' — хг = 2). Двойственная задача: «!«(Л ) = — Л '— — 2Л вЂ” зпр, Л ЕЛ=(Л =(Л', Л'): Л'+Л'> — 1, Л'+Л'< — 2). Ясно, что Х =И, А=Я. Задачи линейного программирования с противоречивыми условиями, когда Х =И или Л = И, изучались в !49; 297; 298; 644). Приведенные выше теоремы двойственности часто позволяют получить содержательную информацию о рассматриваемой задаче линейного программирования, иногда на этом пути удается провести полное исследование задачи и даже получить ее решение.
Для иллюстрации рассмотрим задачу линейного программирования, не содержащую ограничения типа неравенств. П р и м е р 2. Рассмотрим задачу У(х)=(с,х) — «!и!«хеХ=(хЕЕ": Ах=Ь)« где А — матрица размера п«х и, с ~ Е", Ь б Е". Эта задача является частным случаем задачи (1), (2), когда и, =О, и = и, гп« = О, и« = т, А, = А, Ь, = Ь, матриць> А„, А„, А„, Ь, отсутствуют.
Двойственной к ней является задача: «У(Л)= — (Ь,Л) — «зпр, Л еЛ=(Л ~Е: А "Л+с=О) Если Х ф И, У; > — оо, то, согласно теореме 6, Л ~ И, «!«' <+со и, следовательно, вектор с представим в виде с= — АТЛ, где Л„б Л. Но тогда У(х) = (с, х) = — (А" Л„х) = — (Л„Ах) = — (Л„Ь) = сопз! при всех х б Х, так что Х„=Х. Аналогично, если т еХ, то Ь = Ах и ф(Л) = — (Ь, Л) = — (Ат, Л) = — (т, АХЛ) = (т, с) = сопз! ЧЛ ЕЛ, так что «р'= (х, с) =У„Л =Л.
Как видим, задачи линеиного программирования без ограниченйй типа неравенств малосодержательны и большого интереса не представляют. 3. В заключение докажем еще одну теорему, известную в литературе под названием теоремы Фаркаша. Эта теорема имеет важные приложения в выпуклом анализе, в теории экстремальных задач и может быть легко доказана на основе приведенных выше теорем двойственности. Теорема 7. Пусть множества Х, Л определены согласно (2), (12), Х ~ И, пусть а — заданное число. Тогда для того чтобы У(х) = =(с„х )+(с, г ) >а для всех х=(х„т ) ЕХ, необходимо и достаточно, чтобы Л~И и существовала точка Л =(Л;, Л,") ЕЛ такая, что «Р(Л*)= = — (Ь„Л;) — (Ь„Л,*) > а. Д о к а з а т е л ь с т в о, Н е о б х о д и м о с т ь.
Пусть Х ф И и У(х) > а при всех хе Х. Тогда У, = !и! У(х) > а> — оо и в силу теоремы 1 задача (1), мах (2) имеет решение. Согласно теореме 2 двойственная задача (11), (12) также будет разрешима, т. е. Л фИ и найдется точка Л* е Л, для которой «!«(Л") =зпр «р(Л) = ~'= У, > а >ел Достаточность.
Пусть Х фИ, ЛфИ и точка Л'яЛ такова, что «р(Л*) > а. Тогда с помощью неравенства (15) при Л = Л* имеем У(х) > > «р(Л') > а при всех х Е Х. Теорема 7 доказана, П В приложениях чаще всего используется следу>ощий частный вариант теоремы Фаркаша. Теорема 8, Пусть А„А> — матрицы размера гц х и, и«, х и, вектор с е Е . Тогда для того чтобы (с, х) > 0 при всех х таких, что А,х < О, А,х =О, необходимо и достаточно, чтобы существовала точка Л*=(Л;, Л,), Л; Е Е"', Л; >О, Л; ЕЕ ' такая, что с = — А «Л*, — А,' Л,*. (30) 146 Гл. 3. ЭЛЕМЕНТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 4 5.
УСЛОВИЕ РАЗРЕШИМОСТИ. ТЕОРЕМЫ ДВОЙСТВЕННОСТИ 147 Доказательство. Положим Х =(хЕ.Е": Асш < О, Агш=О), Л= =(Л =(Л„Л,): Л, Е.Е ь, Леем ь, АХЛ, +АТЛ +с =О). Эти множества являются частными случаямй множеств Х, Л из (2), (12) при Ап =О, А ш —— = А,, А„ = О, А,г = А„ Ь, = О, Ь, = О, с = О, сг = с. Здесь Х уй О, так как 0 Е Х. Отсюда и из теоремы 7 при а = Ь следует утверждение теоремы 8, причем в качестве искомой точки Л" = (Л;, Л,*) можно взять любую точку Л" Е Л. Попутно отметим, что здесь тгс(Л ) = 0 = тЬ* = Л = У(0) < Лш) при всех ш Е Х, Л Е Л, Л = Л, а равенство (30) вытекает йз принадлежности точки Л* множеству Л. Теорема 8 доказана.(3 Другие теоремы двойственности для задач линейного программирования, их обобщения на случай нелинейных экстремальных задач будут приведены ниже в Э 4.9, там же будет установлена связь между двойственными переменными и множителями Лагранжа, объяснены некоторые тайны пооисхождения двойственных задач.
Различные методы решения задач линеиного программирования, основанные на теории двойственности, экономические и игровые интерпретации этой теории, ее приложения к теории линейных неравенств изложены, например, в [48; 49; 52; 76; 116; 203; 216; 231; 232; 259; 295; 297-299; 330; 356; 373; 470; 586; 612; 620; 670; 719; 746; 747; 750-752; 775; 776). Упражнении 1. Напишите двойственные задачи к задачам из упражнения 1-4 к 4 $3, 4 и решите их симплекс-методом, преобразовав их при необходимости к каноническому виду.
2. Напишите двойственные задачи для канонической и основной задач (1. 15) и (!. 21). Сформулируйте для них аналоги теорем 2-6, 3. Приведите примеры взаимодвойственных задач линейного программирования, в которых множества решений Х„ Л* непусты и, кроме того, 1) оба эти множества состоят из единственной точки, "2) оба содержат более одной точки и ограничены; 3) оба неограничены; 4) одно из них состоит из единственной точки, другое ограничена и содержит более одной точки; 5) одна из них состоит из единственной точки, другое неограничено; 6) оба множества содержат более одной точки, но одно из них ограничено, другое неограничено. 4.
Приведите примеры взаимодвойственных задач линейного программирования, в которых реализусотся случаи, описанные в утверждениях а)-г) теоремы б, 5. В теореме 4 утверждается, что любые точки х, е Х, Л" е Л' удовлетворясот условию дополняющей нежесткости, т. е, в квкдом из произведений~21) хотя бы один из сомножителей ы (возможно и оба) равны нулю. Доказать, что можно подо рать'такие х„Е Х„Л Е А, когда в каждом иэ произведений (21) лишь один сомножитель обращается в нуль (условие строгой дополняющей нежесткасти) (см. [670]).
б. Пусть в задаче (1), (2) Ь! — — О, Ьг = О, и пусть эта задача разрешима. Доказать, что тогда 7(0)=Л =ф*= 0. Указание: написать двойственнусо задачу и заметить, что ф(Л) юО 'т'Л ЕЛ, ОЕ Х. 7. Доказать, что задача (1), (2) РазРешима пРи любых с = (сс, сг), сс Е ЖИ, сг Е Есч, тогда и только тогда, когда множество (2) ограничено. 8.
Пусть множества Х, Л определены согласно (2), (12), пусть Х ф с21, Доказать, что тогда совместна одна и только одна из систем: х Е Х, 7(х) < а или Л Е Л, сй(Л) > а, Убедиться, что это утверждение равносильно теореме Фаркаша. У к а з а н и е: пользуясь неравенст.
вом (17) и теоремой 7, показать, что эти системы не могут быть одновременно совместными и одновременно несовместными. О. Доказать, чта совместна одна и только одна из следующих систем: Асх < О, Агх = О, (с, х) < 0 или АтсЛ ! + Аг Лг+ с = О, Л с > 0 (обоэначениЯ см. в теоРеме 8). Убедитьсл, что это утвервсдение равносильно теореме 8. !О.
Доказать, чта непустое мнохсество (2) неограничено тогда и только тогда, когда сущеСтзуЕт ВЕКтар С Е В чс чс, дЛя КОтарОГО 1П1 (С,Х) = -аа. еех Асх<Ь! Ага= ью Азх<ьз А, Л, +А, ЛгЧАз Лз=о, (Ь„Лс)+(Ь„Лг)+(ЬзсЛз)>0, Л, >О, Лз >О, ЛзФО или (теорема Мацкина, [54, стр. 78]). 15. Пусть А — матрица размера т х и. Доказать, что совместна одна и только одна из двух систем [54, стр. 79]: 1) Ах = О, х > О, х ~ 0 или А "Л > 0 (теорема Горлана); 2) Ах= О, х > 0 или АХЛ > 0 АХЛ фО (теорема Штимке); 3) Ах < О, х > О, х ф 0 или А Л > О, Л > 0 (теорема Вилла); 4) Ах<0, х>0 или А Л>0, АХЛ~О, Л >О. П.
Доказать, что множество Х, определенное согласно (2), непусто тогда и только тогда, когда (ьс, лс)+(ьг, лг) > О для всех л ел=(л =(лс, лг): лс е н ', лг еР ', лс >О, Атсс л + +А,Л > О, АсгЛсь АггЛг — — О). Указание; для задачи д(Л) =(Ьс, Лс) е (Ьг, Лг) с!а!, Л Е написать двоиственную задачу и воспользоваться теоремой 7. 12. Пусть множества Х, Л взяты из упражнения 11. Доказать, что тогда совместна одна и толька одна из двух систем: х Е Х или Л е Л, (Ьс, Лс) + (Ьг, Лг) <О. Убедиться, что это утверждение равносильно утверждению из упражнения ! 1.
В следующих упражнениях приведены формулировки ряда важных теорем теории линейных неравенств. доказательства этих и других важных теорем из упомянутой теории читатель нзидет, например, в [48; 54; 752]. 13. ПуСтъ А — МатрИца раЗМЕра т Х П, Ь Е Нх. ДОКаэатЬ, Чта СОВМЕСтНа ОдНа И ТОЛЬКО одна из двух систем; 1) Ах < Ь или (Ь, Л) < О, А Л = О, Л > 0 (теорема Александрова — Фанз [54, стр.
75]); 2) Ах = Ь или АХЛ = О, (Ь, Л) < 0 [54, стр. 55, 74]; 3) Ах=Ь, х>0 или А Л>0, (Ь, Л)<0 (теорема Минковского — Фаркаша, [54, стр, 55, 74]). 14. Пусть Ас — матрица размера га,. х и, Ьс Е Нх, с = 1,2, 3; пусть система А,х <ы Ьс, Агх = Ьг совместна.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
