Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 61
Текст из файла (страница 61)
Отсюда ясно, что точку ЛА ~и Л„в которой может достигаться верхняя грань ч(Л) на Л„достаточно искать среди тех Л ~ Л„для которых с+А'Л) О. Поэтому двойственную задачу (34) для задачи (39) можно сформулировать так: — <Ь, Л>- зпр или <Ь, Л> — ш(; Л ~в Л = (Л е Е'. с + Атй ) О). Как видим, двойственная к (39) задача также представляет собой задачу линейного программирования. Любопытно ааметить, что если для задачи (40), в свою очередь, написать двойственную к ней задачу„то мы вернемся к исходной задаче (39). Чтобы показать это, составим функцию Лагранжа для задачи (40), взяв в качестве множителя Лагранжа переменные и =(и', ..., и") и переписав ограничения с + А "Л ~ 0 в стандартном виде: — с — А'Л ~ О.
Получим Е~(Л, и) = <Ь, Л>+<и, — с — АГЛ> = <д — Аи, Л> — <с, и> = — Ь(и, Л); здесь Л ~Л, =Е', и ж П, =(и ~в Е": и ~ 0). Тогда ф, (и) = 1пт Лг (Л, и) = ~ ьнл, ' ( — оо, Ь вЂ” АиФО, и~0'с. Ясно, что зпр ~р,(и) имеет смысл искать на множестве лишь "~по тех и я П„для которых Ь вЂ” Аи = О. В результате придем к задаче: — <с, и>- зпр, или <с, и>- 1ВХ; ия П=(и~нЕ'. и~ П„Ь вЂ” Аи = 0), совпадающей с исходной канонической задачей (39). Перейдем к рассмотрению основной аадачи линейного программирования (см.
вадачу (ЗАА5) ): <с, и>-+ (пг; и ~ П =(и ж Е": и ) О, Аи — Ь < 0), (41) 5 91 ТЕОРЕМА КУНА — ТАККЕРА. ДВОЙСТВЕННАЯ ЗАДАЧА 253 где А — матрица порядка т Х п, Ь ои Е", с ов Е'. Здесь Г, = =(и: и ~ 0), Л, =О. он Е": Л > 0), функция Лагранжа имеет вид 1 (и, Л) = <с, и> + <)о, Аи — Ь> = <с+ А'Л, и> — <Ь, Х>. Отсюда 1 — <Ь, >.>, с + А >о > О, Ь()) = 1п1 Е (и, >.) = «нпо ' $ — со, (с+ А Л)~(0, >.~Л,. Двойственная к (41) задача запишется в виде <Ь, >.> — оп1; >оон Л = (Л ои Е": Л > О, с + А'>.
> 0). (42) Это тоже задача линейного программирования. Нетрудно прове- рить, что двойственная к (42) задача совпадает с исходной задачей (41). Наконец, рассмотрим общую задачу линейного программиро- вания (см. задачу (ЗА.5)): <с, и>- (п(; ия 11 = (и=(и', ..., и"): и'~ О, )он1; Аи — Ь < О, Аи — д =0), (43) где 1 — заданное множество номеров из И, ..., и), А — матрица порядка т Х п, Л вЂ” матрица порядка з Х и, Ь он Е", д ж Е*, соиЕ". Здесь Уо (и=(й, ..., и"): й>0, 1онП.
Множители Лагранжа удобно представить в виде >. = (р, р) (1о ж Е, р ои Е'). Поскольку множители, отвечающие ограничениям типа неравенств,неотрицательны, то оо он Ло =(> = (и, и) ои Е" Х Е*: р ~ >О). Функция Лагранжа имеет вид Х,(и, >)=<с, и>+<у, Аи — Ъ>+<р, Аи — д>= = <с: Агу+Агу, и>+ <Ь, р> — <Ь, и>, и он 11о, >, Ло- Отсюда о(о(>) = ш1 1(и,>) = — (Ь,(о> — <Ь, р> при (с+ А'1о+ «о по +А'и), ~ 0 (о он 1) и (с+А'р+ А и)о = 0 (о Ф1), а оз()о)=— прп остальных д =()о, р)жЛо. Тогда двойственная к (43) задача запишется в виде <Ь, д>+ <Ь,оо>- Ы, >,=(р, р)оиЛ=(Х=()о, ц)онЕ' р>0, (с+А'~о+А'р)о~О, о~1; (с+А'р+Атоо)о=О, оФ1).
(44) В результате снова получили аадачу линейного программирования. Предлагаем читателю проверить, что двойственная к (44) задача будет совпадать с исходной задачей (43). 254 элвмвнты ВьшуБЛОГО АнАлизА »гл. » Если задача линейного программирования имеет решение, т. е. 1„) — оо, Ув Ф 8, то согласно теореме 4 функция Лагранжа этой задачи всегда имеет седловую точку. Отсюда и из установленной в теореме 6 связи между основной и двойственной задачами вытекают следующие теоремы, занимающие одно из центральных мест в теории линейного программирования.
Теорема 7. Для того чтобы точка и„е= У была решением задачи (43), необходимо и достаточно существование такой точки Ле =(р*, »»*)»в Л (здесь Л определяется условиями (44)), для которой (с,иег = — (Ь,)»*) — (Ь,)» ). (45) Теорема 8. Для того чтобы точка ивяЕ" была решени- ем задачи (43), необходимо и достаточно существование точки Л"* = (»»*, р*)»в Е Х Е* такой, что иг)0, уен1; Аи. (Ь, Аиз=Ь, »»в ) О, (с+ Аг'»»е + А~»»е)» > О, »»н 1; (,.( ~т,е+Ат„„е) 0;,е1. р» (Аи — Ь), = О, » = 1,..., и»; и„' (с + А~ре + А~9')» = О, » = 1, ..., з. Теорема 9. Задачи (43) и (44) либо обе не имеют решения, либо обе имеют ре»иение, причем в последнее» случае выполняется равенство (45), где ие — решение задачи (43), Ле = =(»»е, ре) — решение задачи (44). Теоремы 7, 8 являются переформулировкой теорем 1, 4, 6 применительно к задаче (43) и в отдельном доказательстве не нуждаются.
Теорема 9 специфична для задач линейного программирования — об этом говорит пример 5, в котором основная задача имеет решение, а двойственная задача — не имеет. Поэтому теорема 9 требует отдельного доказательства. Доказательство теоремы 9. Составим функцию Лагранжа для двойственной задачи (44), взяв в качестве множителей Лагранжа и =(и',..., и"), 1» (Л, и) = (Ь, р) + (Ь, р) + ~~~~ и» ( — с — Атр — А (») + »и» + ~ и'( — с — А р — А*р) = М» = (Ь, »О + (Ь, »») — (и, с + Атр + А (»), Л»н Л, = (Л = (р, р,) е Е" Х Е": »» > 0), и»н У, =(и»н Е' и» ~ О, 1»н 1), З 9) теОРемА кунА — тАккеРА.
двоиственнАЯ ЗАдАчА 255 Как видим, функции Лагранжа задач (43) и (44) отличаются лишь знаком. Согласно теореме 4 задача (44) имеет решение Е~ =(р*, р*) тогда и только тогда, когда функция Е,(Х, и) на Л, Х П, имеет седловую точку ()*,иа) ~ Л,ХП„Т. е. Е,()а,и)<Ь,(Х*,и„)<Е,(),Ц), иЯУ, ) ЯЛа.
Но Ь,(А, и)= — Е(и, ) ), поэтому из последних неравенств следует, что если ()~,иа) — седловая точка функции Ь,(),, и) на Л, Х Е м то (иэ, Ха) — седловая точка функции Ь(и, А) на (70 Х Лг. Таким образом, функции Ь, (1, и) и Ь (и, Х) одновременно либо имеют седловую точку, либо ее не имеют. Согласно теореме 4 это означает, что задачи (43) п (44) либо обе не имеют решения, либо обе имеют решение. В том случае, когда обе эти задачи имегот решение, равенство (45) вытекает из теоремы 6 и следствия 1 из нее. Таким образом, в теоремах 7 — 9 установлена определглная эквивалентность исходной и двойственной к ней задач лилейного программирования. Такая эквивалентность широко попользуется при разработке и исследовании различных методов решения задач линейного программирования. Так, например, если к двойственной задаче применить симплекс-метод и аатем его истолковать в терминах исходной задачи, то придем к таь называемому двойственному симплекс-методу.
Об этом и других методах решения задач линейного программирования, основанных на теории двойственности, см., например, [3, 11, 12, 33, 71, 130, 225, 265, 340). 8. Выше было замечено, что в любой задаче линейного программирования двойственная задача, написанная для двойственной аадачи, совпадает с исходной. В общем случае зто не так. В самом деле, двойственная задача всегда равносильна задаче выпуклого программирования.
Поэтому в невьшуклых задачах (1), (2) задача, двойственная к двойственной задаче, заведомо не может совпадать с исходной. Любопытно заметить, что такое явление возможно и в задачах выпуклого программирования. Пример 8. Пусть 1(и)= (иР- 1п1(иш(л'=(ишЕ": д(и) —— =!и! — 1~ 0)). Здесь П, =Е", Уэ = О, иа = О, Л, = =(ХшЕ'. ).~0). Функция Лагранжа Ь(п, А)=1иР+) (!и!'— — 1)=(1+1)!иР— Л.
Отсюда лР()) = 1п1 Х (и,)') = — й прн зев~ Х+ 1 ) 0 и ~(Х) = — при 1, + 1 < О. Следовательно, двойственная задача имеет вид ф(А) = — Л - зпр; А ш Л = Ь, А ~ Л„ ), + 1 > 0). Эта задача линейного программирования, поэтому двойственная к ней аадача не может совпасть с исходной задачей.
Заметим, что в этой задаче (иа = О, ) * = 0) — седловая точка. 9. Кратко остановимся еще наодномважномклассе задач,называемых задачами геолсегричеслого программирования, в кото- элкмвнты ВЫпуклОГО АнАлиЗА »ГЛ, 1 где с, > О, ае — заданные числа, ш$ Е». = (х = (х„..., х„): х, ~ ) О, ..., х„)и О).
Функция А (х) из (46) называется иоеиномом. Для исследования задачи (46) удобнее перейти к новым переменным и =(и„..., и,+ ) по формулам и» = 1п х, (1 = 1,..., Г); и„+, — — — Ь»+ ~ аци;, Ь» = — 1пе;, 1= 1,..., п, (47) и переписать ее в эквивалентном виде: ,» (и) = ~» е "+» -+- ш1; (48) и=(. и ": т,.„..—.,„, т»=0,;=1,...,.). 1=1 Отметим, что функция 7(и) выпукла на Е"+", 0' — многогран- ное множество, и поэтому к задаче (48) применима теорема 4.
Составим функцию Лагранжа (3) для этой аадачи: »=1 »»=1 и т / и - Ь ( ' ' — т,,„,— ~т»)т В (В „т)и, е -и„ »=1 ;=Л», " л ~ Еи = ло. С помощью классического метода (5 $.2) нетрудно показать, что нижняя грань функции»»»(з)= е* — Л,з — Л;Ь, переменной з на числовой оси равна»»»и = Л» — Л»1ВЛ» — Л;Ьь причем приЛ,) 0 она достигается в точке з„= — 1ВЛО функция Л, 1п Л» при Лс = 0 здесь считается доопределенной по непрерывности нулем.
Отсюда, опираясь на линепность функции Ь(и, Л) по переменным и„..., и„получаем »)»(Л) = ш1 Е(и,Л) = Кт+и и чз (Л, — Л» 1п Л» — Л»Ь») »=1 — при других Л. ЛяЕ+, ~ а;;Л»=0, /=1,...,ге рых переход к двойственной задаче весьма плодотворен. Речь идет о задачах минимизации следующего вида: д(х) = ~ е»х»»1... х,»"-»-ш1; хан Х = шсЕ"~, (46) т=1 а 9] теОРемА кунА — тАккеРА. двоиственнАя зАдАчА Поэтому двойственная задача (34) здесь будет иметь вид в л(](Л) = ~~~~~ (Л] — Л] 1а Л] — Л]Ь,)-о-зар; Л ее Л, (49) оо л-(л-]л„...,ос сс Е „ц=о, 1-1 Если здесь верхняя грань достигается в точке Л*чь О, то задачу (49) можно записать в более простой форме. А именно, учитывая, что любую точку Л=(Л„..., Л.)ФО можно представить в виде Л=ач, где а= ~о Л], ч=(ч„...,чс),чс=Л;/а, 1-1 ч, +...
+ ч„= 1, задачу (49) перепишем сначала в терминах переменных (а, ч): о]]1(а, ч) = л(о(ач) = ~~ ~а(ч] — ч]1аач] — ч]Ь]) = 1 1 = а 1 — 1аа+ ~', (ч]1ас] — ч]1ач]) -чзар] 1=1 (ас ч) я Лг —— и со -(]...О: ~о, ° с"„Е.,=о, Ь.,;,=о. ~=о....,.(. 1=1 1=1 Далее, пользуясь классическим методом (3 1.2), убеждаемся, оо ]с ч]Л] .с ]] с] что точка ас =П (+ ) 0 (здесь принято 0' = 1) доставляет ч]) функции о(]о(а, ч) максимальное значение по а) 0 при фиксированном ч ен Е+, причем л]о1(а*, ч) = Ц ~ — '„,). 1=1 ч Тогда двойственная задача (49) перепишется в следующем виде: Ч1 ЧС с ... с„ л(]9(ч) = -чзар] ч ~ Л„ (50) л, (,=о„...„о-сс Е„-о. Е.оч=о,, о, „), 1=1 Ъ Если ч* = (ч,', ..., ч„') я ]а1 Е+ — решение задачи (50), то, полагая Л*=асч'", где а*=11 —,, и +Ьс=Л] (1= 1, ° ° п) 1=1 из системы линейных алгебраических уравнений (47) можно ЭЛЕМЕНТЫ ВЬШУКЛОГО АНАЛИЗА (гл. 4 ада получить ида, ...,и,а, откудаимеемрешение х„=(х,а — — е 'а.
...,хс, =е"") исходной аадачи (46). Задача (50) часто бывает проще аадачи (46). Переход к двойственной задаче особенно эффективным окааывается тогда, когда множество Л, в задаче (50) состоит из единственной точки тх, которая и будет решением атой задачи. Аналогично может быть исследована и более общая задача геометрического программирования де(х)-+дп1; хее Х = (хя (п(Е+'.
Ед(х)(1,...,д (х)<1), где Еа(х), ..., Е„(г) — позиномы. Подробнее о геометрическом программировании, его приложениях см., например, в [7, 131, 234]. Читателей, нселающих подробнее ознакомиться с красивой и богатой результатами теорией двойственности, с различными ее приложениями, отсылаем к )'2, 3, 18, 21, 67, 116, 137, 146, 156, 166, 167, 201, 255, 264, 290, 293]. Здесь мы лишь отметим, что параллельное рассмотрение задачи минимизации и двойственной к ней задачи, с одной стороны, приводит к важным теоретическим результатам, с другой стороны, служит источником различных методов минимизации. Заметим также, что в последнее время растет интерес к задачам, в которых нарушены соотношения двойственности (37),— такие задачи возникают при исследовании объектов, описываемых противоречивыми системами ограничений, и имеют интересные приложения 1146].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
