Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 40
Текст из файла (страница 40)
Наличие ограничений оказывается эквивалентом появлению «противникам Однако это интересное общее свойство будет достаточно эффективно лишь тогда, когда есть удобные алгоритмы для поиска наилучшей гарантирующей стратегии. Рассматриваемому общему приему введения формы Лагранжа можно было бы дать еще трактовку такого типа: необходимо и достаточно, чтобы существовали р,(х) такие, что гпах [1(х)+ ~ рм(х) Ф;(х)) =1(х,)+ ч~~~~ 11„(х,) Ф;(х,). в=1 1=1 248 [ГЛ. Ш ОПТИМАЛЬНЫЕ СТРАТЕГИИ При этом р,(х) есть [1(х), реализующая ппп [1(х)+,'~' [Ь,ФГ(х)). Й» О 1=1 НО тОГда Прн ФГ(Х) < 0 [Ьи(Х)=со.
Поэтому для Ф; (х) < 0 следовало бы отказаться от точной реализации ппп [[(х)+ ~[1,Ф;(х)). Видимо, различ- И) 1 1=1 ные варианты необходимых условий и рассматривают случаи, когда у ~(х)+ ~~'„,[А,Ф;(х)=Е(х, [1) есть седловая 1=1 точка или когда можно подобрать рм (х) ~ сс. Приведем примеры, когда Е(х, [ь) имеет седловую точку. Теорема о вогнуто-выпуклых функциях дает основу для таких ситуаций. Действительно, если воспользоваться ею, то при ограниченных х и [1) 0 седловая точка у Е(х, р) будет всегда, когда функции )(х) и Ф,.(х) вогнуты и непрерывны; тогда и Е(х, р) вогнута по х, а по [1 в силу линейности — выпукла. Остается только сформулировать условия, когда при расширении границ х и р хотя бы одна из седловых точек остается в ограниченной области и, значит, есть фиксированная седловая точка при всех х и [1)0.
В связи со сказанным имеют место две теоремы. Теорема ХХХП. Если [(х) непрерывна и вогнута на множестве Е = [х) 0), а Ф1 (х) линейны, то для того, чтобы х, реализовало шахах) при Ф;(х) ) О, необходимо и достаточно, чтобы существовал [1, ) 0 такой, что (х„р,) есть седловая точка Е(х, [ь)=7(х)+ ~[1;Ф;(х) 1=1 при х ) О, [ь ) О.
Теорема ХХХП!. Если ['(х) и Ф (х) непрерывны и вогнуты на выпуклом Е и для любого р ) 0 (т. е. когда все рч) 0 и хо пь одно р; ) 0) существует х'~Е такой, 1 что ~.", [Ь,Ф;(х') > 0 [например, все Ф,(х') ) 0), п1о х, 1=1 реализует шах[" (х) при Ф;(х)) 0 тогда и только тогда, э !91 освавождвниг от огглничвний 249 когда есть такой ро, чою (х„р,) — седлоеол точка Е(х, р) ари хЕЕ и р) О. Достаточность того, что (х„р,) есть седловая точка, является следствием теоремы ХХХГ.
Остается доказать необходимость. Ограничимся доказательством для второй теоремы, отослав по поводу первой к монографии Карлина. Пусть х, реализует указанный максимум. Тогда по теореме ХХХ1 х, есть наилучшая гарантирующая стратегия для Е(х, р), причем гиах ппп Е(х, р)=1(х,). о р>о Если х и р)0 ограничены, т. е. !х~(М, У)р, то в силу условий у Е(х, р) есть седловая точка, то есть имеются наилучшие гарантирующие стратегии х,' и р,' и !пах ш!и Е(х, р)= ппп шах Е(х, р)=Е(х,', р,'). !о!<м м>р »>о и >р>о !В!Км (Здесь и в дальнейшем будем опускать, как само собой разумеющееся, указание на хЕ Е.) Пусть теперь У вЂ” такая последовательность, что ]У] и !и( гиах Е(х, р,)= !пи ппп шах Е(х, р) = р>о! 1км о "мо>р>о) !км = !ип шах ги!и Е(х, р)= !пи ги!и Е !х,'(й), р], о""12!< мкоър>о о Ро>р>о где х,'(й) есть х,' для У=У .
Из-за ограниченности хо'(Й) у этой последовательности есть предельная точка х,'(М). Поэтому 1ип ((. (х, (А), рЦ = 1, (х', (М), р). Пусть р, таково, что Е(хо(М), р,)( !и1 Е!хо(М), р]+е. р> о Тогда при достаточно большом й п1!и Е(х,(к), р](Ь(х,'(Й), р,]=А (х,'(М), р,]+О, Яо>р>о 250 [гл. ш опткмлльные стРлтегии где 10(;(е. Отсюда следует, очевидно, что 1ип пип Е [хо'(Я), !о! ( ш! А [х,'(М), (о!+ 2Е.
а"" лсоькьо йь о Поскольку, с другой стороны, 1!ш пип С [х,'(й), р) =ь а-юуоьйьо ) 1ип 1п! Ь[хо(М),!л)= ш! А[хо'(М) р3, "ЛсоЬйЬо йьо то в силу произвольности з 1ип ппп ь [х,' (я), Д = !пг Ь [х,'(М), р]. ЛсоЬЙЬо йЬо Но тогда по определению последовательности Ма шах !пс' Ь[х, !л)) !п! 1.[х,'(М),р]= !п! шах Е[х, !а!. )а1<мй>о йьо й>о121<м Однако обязательно и обратное неравенство; поэтому шах !и!.(.[х, )а)= !п! шах с,[х, Д= !и! Е[х,'(М), р|. 12!<мй ьо йьо !й!<м й> о Если теперь М ~ )) хо (, то С' (х) при ! х ) ( М достигает максимума в х, и в силу теоремы ХХХ1 шах !и! 1.
[х, (о) = !п(.(. [х„!а) = ~ (х,). !а!ам йз о йъо Фиксируем любое такое М, и пусть для заданного з р(е) таково, что шах ( [х, р(е)) ~ !п! шах Ь [х, !а!+е= ~(хо)+ е. !21<м й~о!а~<м Тогда имеем для любого х при !х~(М ! Ь [х, )о(е)1 =1(х)+ ~ Рт(е) Фс (х) (с(хо)+з. Отсюда с шахр!(е) ~~'„', рс(з)Ф1 (х)(7(х,) — )(х)+з. Р 1 а 19! ОСВОВОЖДЕНИЕ ОТ ОГРАНИЧЕНИИ 261 Здесь )а', (е) = ~ — ограниченный вектор. Пусть ( !Гс (а) (зпах !а; (а) теперь е - О и р — со.
Ограниченное множество векторов )а! (В) имеет хотя бы одну предельную точку р"; она, очевидно, больше О, так как гпах )н (е)= !. Пусть )ЕГ1(е) такова, что )ЕГ,(е) - )а при /, — Оо. Для любых х имеем при любом б и 1, ) /а (х, б) ! шах йчл(е) ~ ~ )а,"Ф,(х) — Ь,У, '(Ф; (х)) () (х,) — ~(х)+е. Г=т с=а Пусть теперь х' таково, что ~!ГГ Ф;(х')=с) О. СоГ=а гласно условию на ФГ(х) это имеет место. Будем предполагать 1, столь большими, что Мп в~х'~, и б таким, что ! б ЕФГ(х') < Ф ° а=а Отсюда, очевидно, имеем так р!л (е) (2 ~ ') ~~(" )+, т.
е. векторы рт(е) ограничены, а, значит, имеют хотя бы оДнУ пРеДельнУю точкУ пРи ), — ао. ПУсть это бУДет !аа И ПУСТЬ 1, ПОДПОСЛЕДОВатЕЛЬНОСтЬ 1, таКаЯ, ЧтО Р,, (Е) — )аа. Тогда прежде всего зпрЬ(х, )а,)) !п! Еир Е (х, !а)~~ а ЙЬО а ~~Вар !и! Е(х, р)= )(ха). (228) Й>а С другой стороны, из-за )а;,(з)- р, и МН вЂ” ОО, е- О ПРИ !'а — ОО ДЛЯ ЛЮбОГО Х ,(. (х, !Еа) !ип Е (х, !ан (В)) н:;, ~ (х,).
!а Но тогда и Вцр Цх, )а,) а~ 1(х,) 252 [ГЛ. Ш ОПТИМАЛЬНЫЕ СТРАТЕТИИ и тем более !п! зпр 1, (х, р,) < зир Т. (х, р,) ( ~ (х,). И. О к Отсюда, из (228) и теоремы ХХХ1 следует ппп зцрТ.(х, р)=зцр1,(х, !А,)=!'(хк)= и>о =!пах !п! Т.(х, !А) = ш11.(х„!А), Й) О Й»О что и доказывает теорему. Задача отыскания ппп ! (х) при условиях Ф; (х) > 0 сводится к рассмотренной задаче поиска шах ! — !(х)). Тогда и Т. (х, )ь) = — ! (х)+~ р,.Ф;(х). Если использовать обратную по знаку 1.* (х, р) = =1(х) — '~'ртФ;(х), то здесь по х 1.' будет уже минимизироваться, а по !А максимизироваться. Т.'(х, )А) можно, очевидно, записать также в виде )(х)+~рчФДх), если Ф,"(х) = Ф;(х) е ' О.
Тогда Ф;(х) должны, равно как и 1(х), быть выпуклыми функциями, чтобы был полный аналог теоремы ХХХН1. Ограничение в условиях теоремы, требующее для р > 0 существование х такого, что ~ ртФ,(х) > О, невозможно ю=1 снять полностью, как показывает пример ! (х) = х; Ф(х) = — х', оптимальное х=0 (единственное допустимое значение). Но х — рх' не имеет седловой точки. Однако практически зто ограничение несущественно, поскольку, прибавив ко всем Ф; (х) произвольно малое е, можно обычно считать ситуацию мало изменившейся в смысле оптимального х.
Между тем для новых Ф, (х) =. = Ф;(х) + е, если, конечно, исходная задача имела хоть один допустимый вектор х', имеем Ф;(х') > О, что и обеспечивает применимость теоремы ХХХ111. Теорема ХХХ11 в применении к линейной 1(х) дает возможность немедленно и просто доказать известную теорему двойственности линейного программирования; но зто лежит в стороне от основного направления книги, 253 э 191 ОСВОВОЖДВННВ ОТ ОГРАНННВННИ Вернемся к обсуждению вопросов, связанных с общей теоремой ХХХ1. Отметим, что условия Ф;(х)) 0 (1(!(1) можно записать в виде одного условия и(х) = ш)п ФГ(х))0; если 1<1<( х=х, то и(х) вогнута, если вогнуты все Ф;(х).
Ясно, что уменьшение размерности вектора р до 1 должно канто облегчать поиск максимина соответствующей формы Лагранжа. Неудобство этой более экономной записи состоит в ухудшении гладкости и(х) по сравнению с Ф1(х); и(х), как правило, уже недифференцируема. Если это обстоятельство существенно, то его можно обходить следующим образом.
Вместо и(х) можно ввести функцию Е(х) = —,'!., 4 (ФГ(х) — ~Ф1(х) ~Р= 1=! 1 = —,)В Ф;(х) пнп [Ф! (х); О]. (229) 1=! Легко проверить, что выполнение условий Ф,(х) )0 для всех 1=1, ..., 1 эквивалентно одному условию Е(х))0. В то же время, если х=х, то Е(х) дифференцируема вслед за ФГ(х), причем 1 Е„В(х) = — 2,Е~ Ф;,(х) ш)п (ФГ (х); О) = 1=! ! = — ~ Ф;„(х) (ФГ (х) — ! ФГ (х) ~) . 1=! При использовании Е (х) задача поиска максимина прн ограничениях (220) сводится к задаче поиска шах 1п1 (Р (х, у) + )ГЕ (х)'1.
к У НЬО Однако и эта задача, даже при ограниченных Р и У, обладает, казалось бы, рядом неудобств из-за неограниченности величины 1! и необходимости просматривать всю полупрямую ее изменения. Однако на самом деле, как 254 ОПТИМАЛЬНЫЕ СТРАТЕГИИ (гл. ш легко понять, нас интересуют (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
