Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 41
Текст из файла (страница 41)
доказательство теоремы ХХХ1) только р= + со и и =О. Это обстоятельство еще более облегчает задачу; однако практически пользоваться значением ьь невозможно. Окончательное завершение всех этих рассуждений можно видеть в следующей теореме. Ограничимся рассмотрением случая М = М, (т.
е. когда х=х) и непрерывных функций. Теорема ХХХ1Ч. (Метод штрафных функций). Если Р (х, у) и Ф~ (х) непрерывны на замкнутых ограниченных Р и У и множество М, непусто, то шах пппР(х, у)= 1пн шах пт)п [Р(х, у)+)АЕ(х)]. кЕМ, УЕН Р ~ кЕР рЕН Если х,(рк) реализует шах ппп [Р (х, у)+р„Е(х)], то «Е Р уЕН при р„- ьо любая предельная точка х, реализует шах ппп Р(х, у). кеМ, уе Ч Доказательство. В силу теоремы ХХХ1 достаточно доказать, что шах 1п1 [Р(х, у)+(АЕ(хН = «Е Р У! Р к. Ь = 11ш шах ппп[Р(х, у)+рЕ(х)1 (230) Р Р «Е~ УЕН и что предельная точка последовательности х,(р„) реали- зует максимин, стоящий слева.
Отметим, прежде всего, что ппп Р(х, у)+ рЕ(х) не уен возрастает с ростом р, так как по построению Е(х) непо- ложительна. Но тогда и Гпах ппп [Р(х, у)+)АЕ(х)), как кеР уеп легко видеть, не возрастает с ростом р и, значит, имеет предел (может быть, н бесконечный). Пусть теперь х, реализует левый максимин в (230), тогда в силу, например, все той же теоремы ХХХ1 х,~М, и, следовательно, Е(х,) О, 255 з 19! освоаождваяу от огглниченяй Поэтому шах ш1 [Р(х, у)+)УЕ(х)] = У.Р>У =ш!пр(х„у)= 1пп ппп [Р(хе у)+!УЕ(хей < „ЕУ Р РЕР "Иш шак ш!п [Р(х, р)+)еЕ(х)], (231) Р а «ЕР УЕМ Пусть теперь задана последовательность р» так, что шах ппп [Р (х, у)+ р» Е (х)] = «Е Р уЕФ = ппп(Р [х, ()е„), у]+ р»Е [х, (р»)]] РЕУ и х,(!У„) имеет предел, который обозначим через х,.
Покажем прежде всего, что х,ЕМ,. Если бы это было не так, то в силу замкнутости М, все х, (р„) при достаточно больших п также не принадлежали бы М,. Но тогда для них Е[х,(!У„)] (О и Е [хе] (О и Е[х,(р„)]- Е [х,] в силу непрерывности Е(х). Из ограниченности Р (х, д), очевидно, что правая часть (231) равна Иш ппп [Р [х,(р„), у]+р„Е [х,(!е„)]]= — оо. Р» ее РЕФ А это в силу неравенства (231) и теоремы ХХХ! противоречит предположениям о непрерывности функции на ограниченных замкнутых М, и а! при непустоте первого. Но если х,ЕМм то Е(х,)=0 и в силу Е[х,()е„)](0 и непрерывности Р(х,у) имеем, что правая часть (231) равна 1пп ш(п [Р [х,(р»), у]+ !У„Е[х,(р„)]) ( У„Ф УЕУ < Иш ппп Р [х, (р»), д] = ппп Р [х„у] = Р»» РЕИ УЕФ !п1 [Р(хе У)+!УЕ(хе)] з= УЕЛГ. УЬО (шах ш! [Р(х, у)+рЕ(х)].
«ЕР УЕФ, Р РО 256 ОПТИМАЛЪНЫЕ СТРАТЕГИИ [ГЛ. (и Сравнение этих неравенств с (23!) показывает, что всюду должны стоять знаки равенства, а это и доказывает теорему полностью. Доказанная теорема утверждает по существу, что всегда можно взять достаточно большое [е и свести при- ближенно задачу отыскания (пах пппР(х, у) при М„ «Е М» йЕ Аа заданных ограничениями (220), к задаче (пах ппп [г (х, у)+рЕ(х)1 иеР уел при Е(х), заданном (229).
Введя дополнительное переменное и непрерывный ана- лог (229), задачу определения шах пйп Е(х, у) можно и Е Ма йи)У свести к задаче определения максимума с одним ограни- чением. Действительно, для любого х пп'пР(х, у)= шах и, У Е А( и ~У(й, у) где неравенство должно выполняться при всех уЕ)Ч. Если пересечение )() с внутренностью куба простран- ства векторов у или пусто или имеет положительную меру, то бесконечное количество ограничений Е (х, у) — и ) О эквивалентно(при непрерывной Е(х, у)) одному Е(х, и) ) О, где Е(х, и)ии — ) [Е(х, у) — и — [Е(х, у) — и[[У([у.
(231') Отсюда (пах ппп Р(х, у) = (пах и. (23Г) УЕ Ма УЕА) Х, и; Я (й, и) Э- 0( ХЕМа С помощью теоремы ХХХ1Ч убеждаемся, что последняя задача приближенно эквивалентна поиску (для больших С) шах [и — СЕ(х, иН. и; «ЕМа Теорема ХХХ[П также может быть в некотором смысле обобщена на случай поиска максиминов и минимаксов.
й 19! ОСВОВОЖДВНИЕ ОТ ОГРАНИЧЕНИИ 257 Теорема ХХХу'. Если Р(х, у) и Ф1(х) непрерывны и вогнуты по х Е Р при любом уел! и если Р— замкнупюе ограниченное выпуклое множество, то при М„заданных условиями (220), зор !и! Р(х, у)= !п! Вор !и! Ь(х, у, р), «е Ме У е М й>0 «е Р У е М (232) !п! Впр Р(х, у)= )п! ш! Впр Ь(х, у, !Е). УЕМ «ЕМ, ЙГ«0 УЕМ «ЕР Доказательство. Согласно (22!') и (225) доста- точно доказать, что правые части (232) соответственно равны зпр ш! Ь(х, у, р) и !п(зпр ш! Ь(х, у, р). У. Й>0 Р « Й>0 При фиксированном у Ь(х, у, р) вогнута по х и вы- пукла по !е (как линейная по (0).
Повторяя первую часть доказательства следствия теоремы ХХХ, заключаем отсюда, что зпр !п(Е(х, у, р)= ш! зир Е (х, у, (0). «ЕР йЬВ Й>0«ЕР Взяв нижнюю грань по у от обеих частей этого равен- ства и использовав возможность перестановки порядка взятия нижних граней справа, немедленно получим второе из равенств (232). Далее имеем с зпр !и! !п(Ь(х, у, р)=зир !и([!п(Р(х, у)+ ~ !Е,Ф,(х)]. *е ° уем Й>0 «е й>0 уе ч Но !п(Р(х, у) вогнута по х вслед за вогнутостью уем Р(х, у) при любом у. Отсюда так же, как и выше, сле- дует зпр !п! Ь(х, у, р)= .Е Е Р У Е М, ЙЬО ! = !п! Вор [!и! Р(х, у)+ ~ !01Ф,(х)] = ЙЪО «ЕР УЕМ =. !п1 зпр !п! Е(х, у, !0), ЙЬ0 «ЕР УЕМ а это и требовалось. Ю.
В. Гермейеу 258 ОПТИМАЛЬНЫЕ СТРАТЕГИИ (гл. ш В силу этой теоремы для любого е существует р, такое, что ~ зир !п1 Г (х, у) — зпр !п1 А,(х, у, р,) ! (е, АЕМе РЕМ МЕРРЕМ что вполне аналогично утверждению метода штрафных функций. Мы не сможем остановиться на обобщении дискретного принципа максимума для задач определения максимина с ограничениями, равно как и на формулировке необходимых условий максимнна с ограничениями, которые могут быть получены при объединении теорем ХХХ1 и ХХЧ1!, поскольку это довольно громоздко.
Интересующихся отошлем к одной из работ автора книги. В заключение отметим, что замена некоторых из ограничений Ф;(х))0 на условия Ф,(х)=0 эквивалентна введению дополнительных ограничений — Ф; (х) ) О. Легко проверить, что при этом форму Лагранжа можно и не изменять введением дополнительных слагаемых, но соответствующие рт в (22Г) и (225) полагать изменяющимися уже от — ОО до +СО. Метод штрафных функций также при этом не изменяется. Моисно, однако, упростить соответствующие члены в Е (х), взяв просто — Ф,' (х) вместо — (Ф, (х) — ~ Ф, (х) !]'.
$20. Две теоремы о распределении ресурса при большой неопределенности Как уже говорилось в главе 1, одной из типичных задач является задача объединения ряда операций в одну общую операцию. При этом одной из составных частей стратегии оперирующей стороны является распределение имеющихся активных средств по отдельным участкам, т. е. по частным операциям. Если считать, что способ действий внутри каждой частной операции уже выбран (может быть, в зависимости от наличия активных средств), то единственным выбираемым контролируемым фактором остается распределение активных средств по частным операциям. $20) два тзогзмы о глспгвдзлзняя РесуРсА 259 Обозначая вектор активных средств, отпускаемых на !-ую операцию, через хо критерий ее через Р;(хп у,), имеем при суммарном критерии Ф(Р„..., Р,) (где з— число частных операций) и общем векторном количестве активных средств А операцию вида К = Ф (Р, (х„у,) „..., Р, (х„у,)1 = Ф' (х, у), (233) ~х!(А; х=(х„..., х,).
к=! Что касается вектора у=(у!), то он может быть или вектором общего вида, как всегда ограниченным нахождением в множестве У, или же по соображениям, аналогичным только что указанным, иметь смысл распределе. ния ресурса, н тогда Довольно естественными общими предположениями о задаче (233) при этом является монотонность функций Р,иФ,т.е. Ф(Р„..., Р,))Ф(Р;, ..., Р;), когда Р!)Р!для всех !, Р,(х!, у;) > Р!(х;, у;), когда х, ) х;, у; ) уе (234) В этих предположениях ресурсы не вредно обоим противникам использовать полностью, т.
е. можно принять ~ч~х!=А; ~ч~у!=В. Напомним, что один вектор считается не меньшим второго, если он не меньше второго по каждой координате. В задаче (233), в общем случае, кроме неопределенного фактора у, может быть еще и неопределенность в виде самого критерия, т.
е. функции Ф(Р;). Эта задача достаточно сложна, и вряд ли могут быть даны достаточно эффективные методы ее решения в общем виде. Нас интересует здесь иллюстрация высказанного в главе 1 общего тезиса о том, что прн большой неопределенности задачи и малом количестве ограничений решение 2бб (гл. ш ОПТИМАЛЬНЫЕ СТРАТЕГИИ должно быть относительно простым в широких предположениях о виде критериев эффективности рь В качестве первого примера ситуаций с большой неопределенностью возьмем следующую, на первый взгляд, несколько искусственную игру. Пусть имеется функция <р(г„..., г„). Оперирующая сторона пусть выбирает по своему произволу величины х((1(п), подчиненные лишь ограничению л ~ х;=А. (235) Противник же пусть выбирает, какое из гг приравнять какому из хь но так, чтобы соответствие <Ц) номеров < и 1 было взаимно однозначным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
