Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 39
Текст из файла (страница 39)
ь е н! ььн~ ьь нв Второе равенство доказывается аналогично. Обозначив Р,(г, о)= !п1 Р(г, о) и применяя последовательно уже ьенф доказанные равенства, получим третье равенство. Заклю- чающее его неравенство следует из того, что для любого б существует гм для которого зцр !п1 Р(г, о)( !п1 Р(гм о)+б( альм, ьен, иеи, < И Р(гм о)+б( зир !п1 Р(г, о)+б ььив гчм~ юенэ при всех ! и ! таких, что М,Згь.
Последнее утверждение первой группы аналогично третьему. 2. Если (г„о,) — седловая точка, то Р (г„ о) > Р (г, о,) > Р (г, о,) при любых г ЕМ, и оЕ У„. То же неравенство будет тем более выполнено при г Е М; и о Е д!р Поэтому (г„о„) 240 !Гл. ш ОПТИМАЛЬНЫЕ СТРАТЕГИИ будет седловой парой для всех Ме И Уп корзрые соответственно содержат г, и о,; по условиям твбремы такими являются все М; и 1т'; с достаточно большими номерами. Обратное столь же очевидно, ибо если г„ о, являются седловой точкой во всех У;хМГ при 1)1, и 1~)1„то для всякой пары г, о найдутся среди этих номеров такие, что гЕМИ СЕ111; но тогда Р(г~ ос) Р(гсс пс) ~ Р(гс с) Поскольку г и о — любые из М, и У„то г„о, есть седловая точка в Ме х й11.
Совершенно аналогично доказывается и утверждение об абсолютно оптимальной стратегии. 3. Если Е= зпр 1п1 Р(г, о) = -1-сс, то утверждение 3 се Мс сеМс тривиально. Если Е= — ао, то при М1=М; требуемое есть следствие (218') и того, что максимин по МГ и У~ всегда меньше минимакса (лемма (160)). Пусть теперь !'. конечно. Зададим е и обозначим через М1 множество тех г, для которых при 1)! !п! Р(г, о) ) 1п! Р(г, о)) ш! Р(г, о) — е. сЕМР есесс РЕГС! В силу первого утверждения теоремы каждое г принадлежит какому-либо М; и, следовательно, ~.", М;=М,. 1=! Очевидно также, что М;1=М;,. Обозначим через М1 общую часть М, и М;.
Очевидно, что М1 г М,',!. Кроме того, каждое г принадлежит всем М; и М;, начиная с достаточно больших 1, поэтому Х М~=М.. 1=! Пусть гб М1, тогда по определению М1~ М,' !п! Р(г, с) ) 1п( Р (г, о) — е РЕУс ССМс при всех 1) 1. Но отсюда для любых 1 и ! ~)1 зпр 1п! Р(г, и)) зпр ш! Р(г, с)э зир 1п! Р(г, о) — Р. ЕЕЛ1с РЕФс еме сем семс ТЕЛ~С с й 181 лппеоксимкция нге я моделей опеекций 24! Но, применив к системе М,' (218), получим, что существуют !«и 1. такие, что прн !) !«* !) !« ецр 1п1 Р(г, о)) зцр 1п1 Р(г, о) — е. «е ме «ен/ «емэ Репа «е с Объединив полученные неравенства, получим последнее утверждение теоремы.
Теорема ХХХ довольно общая и имеет качественный характер. Утверждаемая в ней возможность аппроксимации оценки эффективности любой стратегии позволяет производить сравнение конечного числа стратегий и выбор из них наилучшей. Однако неравномерность стремления к пределу не позволяет производить аппроксимацию для определения максиминов и минимаксов; именно поэтому в (218) появляется неравенство. Третий раздел теоремы утверждает, что эту неприятность можно избежать, перестроив множества М; (или й// для минимакса). В качестве приложения этой теоремы докажем следующее.
Следствие. Если Р(х, у) вогнуто-выпукла, непрерывна и ограничена сверху или снизу на М,хй/, где ОР Ф М, = Х М/ и /!/= ~ /«/, а калсдое из М; и /«/ выпукло, / =! /=/ замкнуто и ограничено, причем М; ~ М/~„ /Ч/ ~- /Ч/~„ то на М,х/«' у Р(х, у) есть, хотя бы обоза!енная, седловая точка. Докажем сначала утверждаемое для М,х й/ при любом ! и без предположений об ограниченности Р(х, у). Действительно, на М,хй/ всегда есть седловая точка по теореме й 16. Образуем для случая М, = М, = Ме множества М~/ согласно третьему утвержденйю теоремы.
Имеем тогда ! епр 1п1 Р(х, у) — зцр !п1 Е'(х, у) (е «ем[ в« н «ем,'., «ен, при всех достаточно больших у н 1. Но по (218') и (218) 242 [гл. ш оптимлльные стултвгии вв имеем ( ~ М! = М, Г= ! ш[ зир Р(х, р) = Ио! !п1 зир Р(х, у) = УЕИ «ЕМв ! УЕВ! «ЕМв = [нп зир !п[ Р(х, Й)= Игп Иш зир [п[ Р(х, у). «ЕМв уЕЛв! ! «УМЕ«, уЕЛв! Поэтому, конечно, зир [п[ Р(х, и) — [п1 зир Р(х, Й)~(з, 1- «ЕМв УЕФ УЕМ «ЕМ! что в силу произвольности з доказывает требуемое. Пусть теперь Р(х, у) ограничена снизу.
Учтя тогда конечность !п[ зир Р(х, у) из-за ограниченности М, и уел! «ем! ограниченности Р(х, у) снизу, образуем множества !)[~!и Ф аналогичные ранее образованным М! так, что ~~", !!1,' =Ф и г= ! ~ ! -в Р!!. в! — «' в У!«в!)~ уеЛВ «еМв УЕВУ; «емв ! для достаточно больших !' и !. По (218) и (218') имеем зпр ш1 Р(х, у)=Ит зцр ш1 Р(х, у)= «ЕМ, УЕМ ! "«ЕМ! УЕЛ! = 1пп [п1 зир Р(х, у)= Ит ш1 зпр Р(х, у). УЕМ «ЕМ! !' ! УЕЛ!В, «ЕМ! г Отсюда, благодаря конечности [п1 зир Р(х, у) и про- ИЕМ««ЕМ! ! извольностн е, получим требуемое равенство !п1 зир Р(х, у) = зпр !п1 Р(х, у).
УЕЛ! «Е Ив «ЕМ,УЕЛ! Если Р(х, у) ограничено сверху, то — Р(х, у) ограничено снизу, и этого достаточно для использования уже доказанного. й 191 освовождение от огндиичкний $ 19. Освобождение от ограничений. Игровой смысл множителей Лагранжа Как уже говорилось, множество М стратегий х обычно ограничено как видом используемых функций х(у), так и ограниченностью активных средств, что часто выражается в виде тех или иных неравенств на контролируемые факторы х.
Удобно представлять в связи с этим множество М заданным совокупностью условий: х Е МсР; Ф; (х) ) 0; 1 <1<1. (220) Здесь Р— произвольное множество, на декартовом произведении которого с )У задана Р(х, у). Что касается Ф;(х), то это или функционалы или операторы вида Ф;(х(у)1; в последнем случае неравенства Ф,(х) ) 0 трактуются как выполняющиеся тождественно по у Ей(, поскольку они по существу являются обязательными для оперирующей стороны требованиями Ф (х) ) О. В дальнейшем для простоты записи максимины на Рх)У будут часто писаться без указания этих множеств. Нахождение наилучшей гарантирующей стратегии оперирующей стороны при наличии ограничений вида (220) сводится путем изменения критерия эффективности и введения добавочных неопределенных факторов к такой же задаче, но без ограничений.
Такая возможность вытекает из следующей теоремы*). Теорема ХХХ1. Пусть стратегия х, реализует гпах 1п1 Р(х, у) при ограничениях (220), и пусть еентоаеы аен Ры )а=(йч) неотРииательны, т. е. Р;)О. Тогда х, Реализует 1 шах 1п1 (Р(х, у)+ ~ ргФг(х) ) — со, (221) Х а~9>ее где хЕР, убей, а р ограничено лишь тел, что р) О. Наоборот, если х реализует (221), то оно реализует и ') г" (х, у) предполагается принимающей только конечные значения. 244 оптвихяьяые стуяткгин !гл. ш шах пб Р(х, у) (при условиях (220)).
Всего~ .т ум учи зцр !п( ~Р(х, у)+ ~ рчФ;(х)1 = знр 1п! Р(х, у), (221') к у~у>о ь 1=3 3 учм ууи если последняя величина имеет смысл (ограничения (220) непротиворечивы). Если Р (х, и) ограничена снизу и (221) ровно — оо, и!о (220) пропгиворечивы .
Если (220) противоречивы и Р(х, р) ограничено сверху, то (221) равно — оо. Доказательство. Пусть х, удовлетворяет (220) и 1п! Р(х„у) ~ !п! Р(х, у) при всех х, удовлетворяюуен ддн щих (220). Тогда 1п( ~Р (х„у) + ~ч„'(х;Ф;(х,)1 = 1п! Р (х„у), (222) ибо в силу (220) и !у)0 левая часть всегда не меньше правой, а при р=О функция в правой части равна функции в левой. Точно так же при любых х, удовлетворяющих (220), !п! ~Р(х, у)+ ~рчФ,(х)1 =!и(Р(х, у).
(223) Если же х не удовлетворяет неравенствам (220), то хотя бы для одного 1, Ф;,(х) (О. Тогда, полагая рп — оо, а остальные р;=О, очевидно, получим ш1 ~Р(х, у)+,~~ рчФг(х) =- — оо. (224) у,й>оЕ 1=1 Но из (222) — (224) следует гпах 1п! Р(х, у) = !п! Р (х„у) = х, Ф (х)>0 у д ! !п( ~Р(х„у)+ ~~ р;Ф,(х,) д,д>О Е с = шах ш1 ! Р (х, у) + ~~~ р;Ф; (х) .
к у,я>дь $ !9! освоеождение от огелиичений 245 Обратно, если стратегия х, реализует (22!), не равный — ьь, то она удовлетворяет (220), ибо иначе для нее будет справедливо (224), что противоречит предположению о реализации максимина. Если же х, удовлетворяет (220), то для нее выполнено (222) так же, как и вообще для всех х, удовлетворяющих (220). Но тогда, поскольку х» реализует (22!), имеем !п1 Р(х„у)'=- !п1 Р(х, у), « и если только х удовлетворяет (220). Отсюда и следует второе утверждение теоремы. Аналогично доказываются и все остальные утверждения. Разумеется, теорема остается справедливой при частичном «переводе» условий в критерий эффективности. Таким образом, имеется возможность довольно гибкого маневрирования постановкой задачи.
Фиксируя сначала у и рассматривая ьнр Р(х, у) и применив только что доказанную ««и теорему с последующим взятием нижней грани по уЕУ, очевидно, получим ! !п1 зцр Р(х, у)= !п1 зпр !п1 ! Р(х, у)+ ~ р;Ф,(х) у«н д«м р«н ««рй>о Е (225) К сожалению, аналогичного полного результата при поиске седловой точки Р (х, у) (если она имеется) нет.
Однако достаточные условия сохраняются. Т е о р е м а Х Х Х Г. Если у критерия эффективности Р(х, у) -!- ~ р,Ф,(х), р,,) О, есть седловая точка !х,; (у„)«»)) при максимизации критерия по х и минимизации по у и р, то (х„у,) есть седловая точка Р(х, у) при условиях Ф;(х)) О. Аналогичное утверхсдение верно и для случая обобщенной седловой точки. 246 [гл. ш ОПТИМАЛЬНЫЕ СТРАТЕГИИ Действительно, по свойству седловых точек имеем для любых у, р и х Р(х, у)+,е'., !ЕЫФ;(х)(Р(х„у,)+~рмФе(х,)( ( Р (х„у)+ ~~~, 'р;Ф, (х,). (226) Полагая в правой части неравенства ре= 0 и у=у„ имеем Р(х„у,)+ Х !ТИФ;(х,) ~Р(х„у,), т. е. Х )евоФ;(хо) ~(0 ь«! Но по предыдущей теореме х, есть наилучшая гарантирующая стратегия для Р (х, у) с условиями Фе(х))0 и, следовательно, Ф;(х,)) О.
Поскольку )ое) О, то имеем, следовательно, в Х ! МФе(х.)=0. (227) Тогда написанные выше неравенства (226) дают прн !о;=0 и произвольных х и у, удовлетворяющих условиям Ф;(х)>0, Р (х, и,) ~Р (х, у,) + ~ рпоФ;(х) (Р (х„уо) (Р (х„у). Е=! Это и доказывает первое утверждение. Из общего неравенства (160) следует для с 7. (х, у, р) =Р(х, у) + ~ )А,Ф,(х), !ПЕ зпр !и! 7.(х, у, !Е)( !п! зир 7.(х, у, !А), ЕЕАВ «ЕРРЬО УЕМ,МЬО «ЕР причем левая часть не меньше, чем зцр !п! 1,(х, у, (о).
«еР ром. Йьо й 19 ОСВОБОЖДЕНИИ ОТ ОГРАНИЧЕНИЙ 247 Если последняя величина равна правой части только что написанного неравенства, то по (221') и (225) совпадают и Бпр 1п1 Р(х,р) и 1п1 знрР(х, р), что и заканх«Му«1В у«в«х«М чивает доказательство теоремы. Применительно к поиску обычного максимума функции Р (х) при условиях Ф;(х)э 0 теорема ХХХ1' означает следующее. Для того чтобы х, реализовало максимум, достаточно существование вектора р, такого, что ивах (Р (х)+ ~'.,1«МФ1(х)) =Р (х,)+ .1'„рв,Ф1(х,) х 1=1 1=1 в Р(х)+,Я~ р;,Ф(х)= ппп(Р(х,)+~рФ;(х) ввЬ в Из теоремы ХХХ1 следует, что задача о поиске максимума любой функции 7(х) при условиях (220) эквивалентна задаче нахождения наилучшей гарантирующей стратегии с для критерия эффективности 7(х)+ ~~' р;Ф;(х)=Ь(х, р), 1=1 где х уже не стеснено неравенствами (220), а р1) О. Это совершенно общее утверждение придает «игровой» смысл множителям Лагранжа как неопределенным факторам в задаче поиска оптимальной стратегии для формы Лагранжа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
