Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 42
Текст из файла (страница 42)
Критерием эффективности оперирующей стороны пусть будет яг = <р (х; „„..., х; < „>). Таким образом, стратегией оперирующей стороны является выбор хь ограниченных (235), а стратегией противника †выб дискретной функции <(1). Тогда имеет место Теорема ХХХЧ1. Если <р(г„..., г„) непрерывна и такова, что для любых 1, и 1'< и (г„..., г„) г( +г) ф (г„ ..., гн „ , , гь+(, " г; +г) гп+т~ ° ° ° ~ гл) ~~> ЪППП (ф(г„..., гн „г(о ..., г;, <, г;„..., г„); <р(г„..., г;, „гь, ..., гп „г)„..., г„)1, (237) то оптимальной гарантирующей стратегией оперирую- А щей стороны является х,= —, а /А А> шах пцп <р (х< ш) = ф ), „' л ) ' (М<) < (<) Если же <р(г„..., г„) не непрерывна, то зцр (п(ф(х<ш) (Ат) <(!) реализуется на некоторой последовательности векторов А х (й) = (х; (й)), стремящихся к — . 5 20! два твогкмы о глспгвдвлвннн гвстгсь 2б1 Для доказательства достаточно показать, что, каков бы ни был вектор х = (х„ ..., х„] с Л = <пах ! х, — х<! чь О, с<з<с~сс всегда найдется вектор х', сколь угодно близкий к 1-" ° '.-~ А А < — „, ..., — ~, для которого !и! <р (хс < л) ) 1п! <р (хс <с>).
с <с) < <<1 Поскольку рассматриваются минимумы по всевозможным перестановкам хо то можно принять, ничего не меняя, х,<х,«... х„. Тогда, очевидно, Л =х„— х,. =(х]сс]. Для него А<с'<Л и для 1 «< п Но это неравенство тем более справедливо и для < = 1, а. Точно такие же неравенства верны и для !х<с<с — х„'" ~ при 1(<(л. Пусть теперь х"' = (х',"] = Здесь имеем Ь<*>(Л<"; !хам — х~м!( — ' при 1=1, 2; а — 1; а. Продолжая операцию осреднения х; и х„ь придем ~ л] в конце концов к х " =х,=(х„], для которой Ь о«=пах)х„— х«! = ~ .
5-.с< Ясно, что все указанные операции не меняют фиксированной суммы, т. е. л ах<<и = А. с=< Докажем теперь, что 1п! ф (хс<~с] ( !п! <р [х<, пл]. <<а с<и 262 [гл. )и ОПТИМАЛЬНЫЕ СТРАТЕГИИ Для этого достаточно проверить аналогичное неравен- ство при переходе от х(А) к х'"+".
Этот переход заключа- ется в том, что два каких-то х(, и х(, заменяются нх сред- ним значением. Имеем по условию теоремы: (п! <Р [х]А(!))] = ыл = !п! [ппп [<Р(х)А([), ..., Х((А(! )), Х[А()() =х<„х!'()!+)), ... ( (!) а> (м <м м> ). ( ы> х((р-<)а ха(р) х(а> х!(р+ыа ' ' 'а с(а)) Ф<х(а)а (й) (Ь (й) Й) (Ь Х((! Т)а Х( а Х(И())а,, а Х((р Г)>Х( Ха(р+() Х(чи)]]~~ ! <ы м "(,+"<, ()п(<Р ( х«о, ..., х]и-(> < (!> х< к( а х) (р-оа 2 а ..
Х! <аа)) П)! Ф [х](!) 1 ((!) Итак, для любого х построен х) = [х,!] такой, что нижняя граница для х не превосходит нижней границы для х„причем Л)(Л/2. Продолжая эту операцию, получим последовательность х„, для которых ЛА(Л/2", а !п(<Р[х„;<,] не убывает, ( (!) а, значит, и не меньше, чем !п(<Р~Х)(~)]. Этоидоказы(!) !А А) вает теорему, поскольку хр ( — „, ..., — )Из-за Л„О.
Анализируя доказательство, легко убедиться, что утверждение теоремы не изменится, если на векторы х, кроме (235), будет наложено требование х ЕЕ, где мно- жество Š— любое выпуклое множество, содержащее вместе с вектором х все векторы, получающиеся перестановкой его координат. Условие теоремы выполнено для вогнутых функций, поскольку взяв г = [х„ ..., х; „ хо ..., х~ „ х~, ..., Х„) и у= [х„..., х, „х, ..., х,„хь ..., х„), имеем в силу свойства вогнутости (Р ( 2 г +. в У) ~ 2 <Р (х) + в <Р (У) ~ ш)п [<Р (г), <Р (у)], что и требуется в условии теоремы.
з 201 двк ткогкиы о гкспгкдклкняи гкскеск 263 Однако условие теоремы, конечно, значительно шире условия вогнутости; так, скажем, при а, ) 0; а, ) 0; хьк) 0 функция (а,х,-!-а,х,)' выпукла, как квадрат положительной выпуклой: если ) [Хх+ (1 — Х) у) < Ц (х) + +(1 — Х)1(у), то ~' [Хх+ (1 — Х) у) ( Р~' (х) -1- 2Х (1 — Х) [ (х) ~ (у) )- +(1 — Х)'['(у) (Хк['(х)+ Х(1 — Х) [!'(х)+)' (у)) + + (1 — Х)' Р (у) = Ч*(х) + (1 — ~) Р (у). Но при тех же х)0; х)0; а, 0; а)0 эта функция удовлетворяет условию теоремы, ибо (к,+~,) + (~,+~,) ° [ + .
+ (линейная а,х,+а,х, вогнута). Пример функцйи х,'+х, 'показывает, что утверждение теоремы верно отнюдь не всегда. Для этой функции при любых перестановках х, и х, выгодно брать или х,=А; х,=О или наоборот, но никак не х,=х,=0,5А. Эта простая теорема может применяться в различных задачах. Первым примером применения можно назвать модель действий нападения против обороны (модель 1Ч), рассматриваемую с точки зрения обороны (для нападения это будет определение минимакса).
Тогда в соответствии с (9) критерий эффективности при р,=р=сопз! имеет вид Ф'= — ~шах [х; — ру;; 0) = ~ш!п[ру; — х;; О), (238) 1=1 1=1 где выбор [у;) — стратегий защиты — подчинен условию ,~~у;= п; нападение ограничено условием ~ х; = У. ~=1 К=1 Функция (238) вогнута по у, как сумма вогнутых функций ш)п [ру; — х,; О[. Если фиксировать хь но переставлять их между собой, то это эквивалентно тому, что, наоборот, х, остаются на месте, но переставляются уе Таким образом, противник — нападающая сторона — может переставлять у,, даже фиксировав свои величины хь 264 [гл. щ оптимляьные стРлтегии Выполнение условий теоремы ХХХЧ(позволяет утверждать, что при любых хь если только неизвестно их расположение, обороняюшрмуся выгодно равномерно распределять свои силы, т. е.
брать у; — —. Поскольку этот вывод не зависит от величины хи то он справедлив и при нефиксированных хь Этот вывод останется, конечно, без изменения и в случае, если вообще ь 1Р' = ~г(хà — ру,), Г=т когда функция г(х; — ру;) удовлетворяет условию Гп)п(г(х,— ру,)+г(х,— ру,); г(х,— ру)+г(х,— руГ)1 < < (.,— р + )+ (,— р + ). Сильное отличие рГ от постоянной, как мы увидим далее, уже не позволит считать равномерное распределение оптимальным.
Примером другого рода может служить перспективное планирование выбора технологических процессов (см. й 7), когда задача в силу (56) может быть приведена к виду Л п 1Р = ~~.",Г()х~, хг) 0; ~хг — — В. Здесь х есть часть общей суммы В средств, которая очпускается на )ьй процесс, а д~ — средства, выручаемые за продукцию /-го типа, произведенную на единицу затраченных средств. В й 7 было сказано, что оптимальным поведением при известных бГ является отпуск всех средств на один наиболее эффективный технологический процесс.
Однако положение дел может радикально измениться, если И1 неизвестны, например, из-за неизвестности будущих цен на продукцию. Если эта неопределенность такова, что возможны всякие перестановки Й1 между собой, то это эквивалентно перестановкам хг Линейность 1Р' обеспечивает выполнение условий теоремы ХХХЧ, а, следовательно, здесь наивыгоднейшим будет равномерное распределение средств на все технологические процессы. э 20! две теОРемы О РАспРеделении РВОУРОА 265 Эти рассуждения останутся, конечно, справедливыми и прн более общих видах записи )Р: л )(у= ~~'.',фр (х;), если только будет выполнено (237). Однако наиболее прямыми случаями применения тео- ремы являются, конечно, всякие задачи, так илн иначе связанные с поиском, с разработкой (или уничтожением) чего-то при неизвестном его местоположении.
Пусть эффек- тивность поиска чего-то характеризуется выходом 7(г) при использовании ресурса г в должном, одном, месте из Об- щего числа и мест возможного поиска. Тогда, распреде- ляя общее количество ресурса А на количества х; в 1-е место поиска, исследователь операции (а в худшем случае и оперирующая сторона) не будет знать, какое из х; ока- жется тем г, которое только и может принести пользу ) (г). Таким образом, здесь задача является частным случаем рассмотренной, когда ф(г„..., г„)=~(г»).
Условие (237) вырождается в )' ~ '+ '1 ) ш(п (7 (г,); 7 (г»)) и наверняка выполнено для любой неубывающей функции. Таким образом, максимин здесь всегда достигается при равномерном распределении ресурса. Это общее утверждение может вызвать законное жи- тейское недоумение в ряде случаев. Пусть, например, поиск совершенно неэффективен, пока не будут совершены затраты, сравнимые с А„т. е. пусть, например, г(г)=0 при г < А — е и ) (е) = 1 при г ) А — е.
Тогда равномерное распределение А по многим местам приведет к 1(г)=0, т. е. нулевому эффекту. В то же время концентрируя ре- сурс в одном месте, можно мол и получить эффект, если повезет. Для разъяснения этого «парадокса» нужно опять обратиться к нашим основным понятиям. Действительно, здесь равномерное распределение реали- зует максимин, но этот максимин равен просто минимуму и получается, конечно, и при любом другом распределении ресурсов; в частности, концентрация ресурса тоже в худ- шем случае (а их будет и — 1 случаев из п) даст нулевой эффект.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
