Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 43
Текст из файла (страница 43)
266 (гл. ш оптимлльиыи стглтегии шах ппп ~р[хил, у) =вахш(пф[хи~>), юпьй го (239) »р (г„..., г„) = ш(п <р (г„..., г„, у); где не представляет труда проверить, что если ~р по г„ ..., г„ удовлетворяет условию (237) при любом у, то этому условию удовлетворяет и ф(г„..., г„). Тем не менее здесь стоит отказаться от равномерного распределения в сторону концентрации. На чем же основаны надежды на улучшение при отказе от чистого максимина. В рассматриваемом случае это только надежды на случай; в нашем понимании это означает целесообразность применения смешанных стратегий вида: с вероятностью гг весь ресурс направляется на 1-е место поиска.
Поскольку противник †приро, то мы вправе ожидать отсутствие у него информации о нашем конкретном (хотя и случайно выбираемом) направлении ресурсов. Платеж при таком подходе, очевидно, равен ~р (г„..., г„) = в = г„где гг =сия по подстановке 1(1) и ~чР г;=1. Оче~=! видно, опять условия теоремы выполнены и наивыгоднейшие распределения «ресурса», равного единице, есть г; = 1/л. Итак, получаем опять-таки равномерное распределение, но при новом понимании ресурса. Разумеется, выигрыш в эффективности (1/и вместо 0) не очень велик и падает с ростом числа мест поиска.
Поэтому при большом п опятьаки все стратегии по существу равноценны (если только не появится у оперирующей стороны какая-то информация, априорная или добываемая в процессе поиска). Поэтому здесь создается большой простор для всякого рода произвольных попыток, в том числе и для эвристики, Однако при этом не следует забывать и о другом, более понятном пути †использовании информации, добываемой в процессе поиска. В заключение обсуждения теоремы ХХХХХ! отметим следующее.
Если кроме выбора функции 1(1) есть еще неопределенные факторы у, то задача определения максимина может быть представлена в виде 3 201 две теогемы о експеелеленнн гестасе гбт шах !р„(х») < ф»», (О) «» при условиях (243) » 1)й+1; ~х,=А; 1=1 1(»(Й, х =0; ф, (х;) = ф» (х»); Но тогда верно утверждение теоремы ХХХЧ1 и для задачи (239). Перейдем теперь ко второй интересующей нас теореме. Пусть выполнено (234) и <р(Р;)= и!!п Р;(хну,); ~~Рх!=А; ~' у,=В. (240) !<!к«!=! 1=1 Требуется определить оптимальную стратегию в вариантах максимина и миинмакса.
Прежде всего заметим, что по (234) ш!и ппп Р«(хь у!)= ппп ш!пР!(х„у!)= — !к к«!кг<» — „ = ппп Р,(хо В). (241) ! к!к» Наихудшим случаем здесь является концентрация сил противника в самой «слабой» частной операции при заданном х= (х!). Зафиксировав (24!), увидим, что как в случае мини- макса (когда у, станут известны), так и в случае макси- мина (когда следует принять все у;=В), оптимальная стратегия получается из решения задачи оптимизации при известных у,: !пах ппп Р;(хь у!)=шах ппп <р»(х!). (242) « .« В этой задаче «противник» как бы только выбирает число ! в критерии Р(х, !) = !р!(х!). Будем предполагать нумерацию частных операций выбранной (при известных у!) так, что !р;(О) ( !р;+,(О). Р!, а, значит, и ф! пусть будут непрерывны по хь Теорема ХХХУП.
(Принцип уравнивания.) Среди оптимальных х,=(х1) или имеются такие, что для некоторого я(з — 1 они реализуют 268 (гл. ш оптнийльяые стелтвгян или же имеются реализующие шах 1р,(х,) «« при условиях ф1(х;) = 1р, (х,); ~ х; = А; 1 = 1,..., з — 1. 1=1 (243') Если ф1(0)=ф«(0) при всех 1(з, то всегда имеет место второй случай. Если ф;строго монотонны, то указанный вид оптимального реи1ения необходим.
Д о к а з а тел ь с т в о. Предположим противоположное— среди оптимальных х, нет удовлетворяющих (243) или (243'). Возьмем тогда произвольную х„и пусть й таково, что 1рй(0)< ппп ф1(х1)(фй+,(0) (при й=п второе неравен1Ч1~« ство пропадает). Уменьшим теперь в стратегии х, все х1 при й~~й+1 до нуля, увеличив соответственно все или некоторые х,' при 1< я так„чтобы не нарушилось равенство Д х; = А.
Полученная новая стратегия х' будет в силу монотонности г"1 (а значит, и 1р;) обладать свойством ппп 1р,(х;)) ппп 1р;(х,'). 1~1~й 1К1~й Но последняя величина и равна самому оптимальному результату по определению й. Итак, имеется оптимальная х', для которой х,'=0 при 1) й+1. Пусть, далее, 1„..., 1,— все номера, которые реалиЗУЮт ППП 1Р; (Х1) = Ярьй,. 1<1< й Если есть хоть один номер 1,(й, не входящий в систему 1„..., 1,, то будем уменьшать х1 до величины х1, пока не станет 1р; (х",)= йр'„,+е, где е †ско угодно малая, но фиксированйая величина. Зто всегда можно сделать, ибо 1,<й и ф; (хй) ) (р,„,>ф1,(0). Распределяя неотрицательный и нейулевой вектор х;— — хг между х1, при 1'=1, ...,1, можно или увеличйть все 1р1, или же найдется („для которого прибавление к хп вектора х — х," не изменит ф11с В первом случае з 201 дзз тзогзаы о глспгздзлзнни гвстгсх 269 увеличился бы и ппп ~р;(х;) по сравнению с Ф',„„что ~~!<з невозможно по предположению об оптимальности (ху) и (хД.
Во втором случае, устремляя е к О, получим стратегию х", в которой 1, также входит наряду с („..., 1, в реализующие пип <р;(х ) = Ф',„,. ~<с<а Повторяя эту операцию необходимое число раз, получим стратегию х„=(х,'") такую, что х'"=0 при /)й+! и ~р;(х~")= Юг,„, при 1(й. Но поскольку х,„реализует шах ппп <р;(х;) среди 1 ~Ф~З всех х, то она, очевидно, реализует этот максимум, в частности и среди х, удовлетворяющих условиям ~р;(х~)= = <р„(х„); х„+~ — — О.
Этим построена оптимальная хыо удовлетворяющая требованиям теоремы, вопреки предположению, что таковой не существует. Теорему можно считать доказанной, проверив по ходу ее доказательства и остальные в ней содержащиеся утверждения. Если А — скаляр (а следовательно, и х;=х;), то при фиксированном й и равном ему числе неизвестных х; (1~ й) число уравнений (243) ь ~р;(х;) = ~рз(х„), ~ х;= А к=~ также равно й.
Это обеспечивает нахождение оптимальной стратегии путем решения систем уравнения при й = 1,..., з с последующим сравнением ф, для этих вариантов между собой. Наиболее прост случай <р;(0)=~р,(0) при 1(!<з. Тогда нужно брать Й=з и оптимальная стратегия определяется как стратегия, дающая при Х х;=А равные значения всех ~р;(х;). Теорема ХХХЧ11 также имеет многочисленные применения.
Прежде всего отметим, что, как было показано в главах 1 и П, критерий типа гп!и Р;(хп у,) может 1 .4:. ~ ~ $ появиться по крайней мере двумя путями: йуо ОПТИИАЛЬ~!ЙЕ СТРАТЕГИЙ (гл. ш а) когда Ф(г'!)= Хх;гГ, причем А! неизвестны и ог- 1~ раничены только условиями: Г!)0; ~~АГЙ7!= 1. В этом случае принцип гарантированного результата требует, как сказано в главе 11, рассмотрения критерия типа ппп — ' Г!. !<С~л~г! б) когда ставится задача о достижении заданных величин и7! во всех частных операциях. Неравенства г!) йу! при этом заменяются стремлением критерия ппп Р!' !<!<л ~ к единице. Если же это недостижимо, то приходится просто говорить, об увеличении такого критерия. Кроме этих случаев теорема ХХХЧП позволит (как это будет видно в следующем параграфе) определить максимин для (238) при произвольных р!, можно рассмотреть и обобщения этой задачи.
Легко заметить применимость этой теоремы и к задаче поиска. Пусть поиск некоего объекта ведется в а местах, причем в Г-м месте эффективность поиска при затрате ресурса х! пусть будет 1!(х!), если объект находится в Г-м месте и нуль в противоположном случае. Математическое ожидание эффективности поиска при вероятности Г; пребывания объекта в Г-м пункте, очевидно, равно ~=,Х ~~,(~;) При этом ~хГ=А и ~Г;=1.
1=1 !=! Если Г! неизвестны, то оптимальная стратегия, исхоДЯЩаа ИЗ НЕОПРЕДЕЛЕННОСТИ Гп ОПРЕДЕЛЯЕТСЯ КаК РЕаЛИ- зующая шах ппп Й7(2,7)= шах ппп 1!(х,). (244) Ел!ля ЕГГ=! Хл,=А ! <!<л Эта задача в точности совпадает с (242), и ее решение будет даваться теоремой ХХХЧП. В частности, если 1! (0)= =1!(0), то решение определится из равенств л !'!(х!]=!'!(х!); ~х;=А. й 211 ПРИМЕРЫ МАКСИМИИОВ И МИИИМАКСОВ 27! В еще более частном случае тождественности ~е(х) =1(х) длЧ всех 1 имеем, естественно, условия 1'(х;) =1,(х,), что А дл~( монотонной 1(х) выполнимо только при х;=х,= —.
Зто означает возвращение к задаче, уже рассмотренной с помощью теоремы ХХХЧ1. Однако не следует думать, что последняя теорема является частным случаем теоремы ХХХЧП. Отметим явную связь принципа уравнивания с необхо- димыми условиями максимнна (теорема ХХЧИ). Эта связь станет очевидной, если (242) записать в виде гпах пип '~~ гир; (х ), к г для которого критерий эффективности ~ч~ г;~р;(х,) будет г.=! дифференннруем, если дифференцируемы гр, (х,). Поскольку минимум этого критерия по г может дости- гаться только при г,=О, кроме одного какого-либо П =1, то необходимые условия предусматривают как раз случай ~ре(хе)=~р,(х,) для оптимальной стратегии.
Для решения более сложных задач с неопределенными критериями вида, указанного в главе 11, можно использо- вать необходимые условия. $2!. Примеры аналитического нахождения максиминов н минимаксов для моделей главы ! !. Модель !Ч действий защиты против нападения. Продолжая рассматривать эту модель с точки зрения защиты (критерий (238)), определим теперь оптимальную стратегию защиты при любых рп если оперирующая сторона (защита) не получит информации о векторе х= [х;]. Найдем сначала оп~~~„'ш(п[р;уг — х;; О].
Очевидно, что к г=~ нападающему невыгодно иметь 0 ( х; ( р;уп поскольку иначе ппп[р;у; — х;; О] = — О, т. е. так же, как н при х,=О. Поэтому нападение будет так выбирать х, что или х;= 0 или х,) р;ус Но тогда (238) приобретает вид ~э~(рб уг — хб), чрхг = гЧ. 272 (гл. ш ОПТИМАЛЬНЫЕ СТРАТЕГИИ Линейность критерия немедленно приводит к вывоиу, что наивыгоднейшей стратегией полностью информированного нападения является концентрация всех сил в одном месте, а именно, для того г, при котором ') йгу! — У = ппп ~рту~ — У). !<с<ь и потому а г=! +у ! ! л (246) Рг и ! Соответственно и максимин критерия эффективности будет равен пп(п — У; 0 (247) Результативность защиты, не информированной о месте прорыва средств нападения, по (247) падает с увеличением числа й возможных мест прорыва.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
