Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 44
Текст из файла (страница 44)
Найдем теперь мииимакс для защиты (максимин для нападения). ') Напомним, что ато — абсолютно оптимальная стратегия. Таким образом, задача определения наилучшей гарантирующей стратегии защиты сведется к отысканию шах ппп ~ртуу — У1;,Р', у; = л. (и!) ! < г< а Решение этой задачи таково: уу должны быть такими, чтобы все рот — У были одинаковы. Это прямо следует из теоремы ХХХЧН, если учесть, что в данном случае <р, (у~) = ртут — У и, следовательно, тру (О) = — У = <р, (О). Йз р;у; — У=! следует а а а а й 21! ИВИМВГЫ МАКСИМИНОВ И МИНИМАКСОВ 273 Если защите известны хн то ей невыгодно бРать У; > х;(Рь ибо это не увеличивает платежа в (-м месте прорыва, уменьшая возможности в других местах.
Но при у;(х;(р; платеж становится линейным, и защите выгодно оказывается увеличивать прежде всего у, (будем считать, что нумера- ция соответствует уменьшению р;: р;>р;+1) до тех пор, пока или у,=-х,(р„или у,=п. Итак, у',"=ппп[а; х,(р,». Далее, очевидно, у'," = пнп [и — у',"; хо(р,! и вообще ю — ! оп Къ оп, у~ =гп!п ~л — ~ У! ' «;(Р до тех пор, пока этот ми(=! нимум не станет отрицательным; соответствующие у; сле- дует взять равными нулю.
Что касается оптимальной гарантирующей стратегии нападения„ то она, очевидно, состоит в том, чтобы кон- центрировать силы в месте, где р; наименьшее, т. е. в й-м месте. Минимакс для защиты поэтому равен ш!п[р и — (У; 0»=ш!п(1 ппп [р;и — ()([; 0». (247') 1<1<А Разность между (247) и (247') показывает ценность информации в целом. Эта ценность, как нетрудно увидеть, сильно растет с ростом й. Это особенно хорошо видно на простейшем случае р;=сонэ[=р. Тогда ценность информации равна ппп (рп — (т'; 0» — ппп» вЂ” — (1(; 01, ГРА и если рп — л((0, то ценность равна рп — — . Рп А Что же именно ценно для защиты: информация ли о действиях противника или сохранение в секрете своих собственных действий? Платеж для защиты, как уже упоминалось, есть вогнутая функция (как сумма вогнутых функций ппп (ру; — х;; 0»). Но тогда в силу теоремы Х'1( цена игры равна максимину (для защиты).
А это означает, что сохранение в секрете действий защиты не увеличивает результата, если неизвестно решение противника — нападающего. 274 [гл. ш оптпмлльпыв стглгкгпп Таким образом, для защиты ценна именно ингрормация о действиях противника; сохранение же в секрете своих действий особого смысла не имеет. Для нападающей стороны все обстоит наоборот. Это все верно, конечно, только в пределах рассматриваемой модели, предполагающей, что средства нападения только прорываются, не воздействуя предварительно на сами средства защиты.
Рассмотрение этой модели позволило нам получить чисто математически некоторые старые принципы военного искусства, как-то: а) нападение должно производиться концентрированно и сохранять в секрете направление прорыва; б) неинформированпая защита должна равномерно распределять свои силы; и хотя это — наилучшее поведение, она окажется в проигрышном положении по отношению к нападающему. Информация (разведка намерений противника) абсолютно необходима. П. Модель выбора дальности стрельбы в дуэли.
В этой модели (модель 1Х, 2 2) критерий эффективности (38): УР=Р(Ог)' 0 >О" йУ=р(0,)1! — й(0,)) 0,<0„ терпит разрыв на прямой 0,=0,. Поэтому здесь неприменимы все аналитические необходимые условия $ ! 7. Однако максимин определяется несложно. Прежде всего найдем !п1 ))7 (0,,0е). Этот минимум из-за ов монотонного роста*) д(0е) с уменьшением О, очевиден; он получается при Оч — О„но так, что О, > О, (т. е. противник открывает огонь раньше, чем оперирующая сторона). Отсюда )п1 ))у (0„0,) = р (0,) 11 — и (Щ. ое Поэтому оптимальное гарантирующее О, определяется как реализация шахр(0,) !! — д(О,)), т. е. из условия о, р' (О ) (! — хг(0,)) — д'(О,) р (О ) = О.
(248) *) В полком соответствии со смыслом задачи предполагается, что р(0,) в я(0е) есгь мопотовпо убывавзщве функции, причем р(о)=е(о)=!. й 21! ПРИМЕРЫ МЛКСИМИИОВ И МИИИМЛКСОВ 275 с 1 ! ' — 1~= !р.!~Ер! — 1+р.~+К.~Ер! — 1 !г=! 8=! +~Х, Ер > е С +~х;р)о,, /ы! '! Здесь, как иетрудио видеть, мы имеем дело опять с простейшим случаем теоремы ХХХЧ!!. Если оба противника одинаково метки, т. е.
д(0!) = =1)(О!), то шахр(Р,) [! — р(О!Я =шаху(1 — у) достигаетея, как известно, йри у = 0,5; следовательно, нужно выбирать Р! из условий р(0,) =0,5. Это дает гарантированный результат 0,25. Найдем мииимакс для оперирующей стороны. Если оперирующая сторона будет стрелять до выстрела противника, то !р' выражается р (О,) и потому растет с уменьшением Р,. Поэтому здесь выгодно брать Р,=Р„ что даст платеж р(О,). Если же выждать до выстрела противника, то выгодно уже (если он промахнется) подходить вплотную, т.
е. взять 0!=0, что даст р(0)=1, а общий платеж ! — д(0,). Итак, оптимальная стратегия информированной оперирующей стороны есть 0,=-0, или Р, =0 в зависимости от того, что больше р(Р;) или 1 — й(Ра) максимальный платеж, следовательно, равен шах [р(0,); 1 — д(О,)). Оптимальное гарантирующее поведение противника состоит, очевидно, в выборе такого 0;, при котором р (О;) = 1 — д(0;).
Действительно* ), если, скажем, сдвинуться от этой точки в сторону меньших Р„то увеличится р (Р,) и уменьшится [1 — д (Ое)1, а платеж шах[р(0,); 1 — д(0е)1=р(Р,) увеличится; аналогично и при увелйчении Р,. Итак, минимакс определяется значением р(0;) =1 д(0;). (248') В частности, если меткости одинаковы [р(Р)=п(0)), то минимакс достигается опять при р(0,) =п(0е)=0,5, ио равен 0,5) 0,25. Разница получается йз-за разрывности критерия при 0!=0,.
1!1. Линейная обработка информации (модель УШ). Согласно оценке эффективности, данной в главе П, имеем оптимлльиыз стглтагии ~гл. ш где К, †максимальн ошибка априорного (до измерес)ий) представления у о величине уь т. е. шах~у,— ус~. Из приведенной формулы немедленно следует, что для оптимальной фильтрации всегда необходимо выбирать р, так, чтобы р,=1 — ~ч» р, или ~~' р,=1. (249) с=! Сеа Тогда оценка эффективности приобретет вид — )Р= К, ~рс — 1 +К~ ~~' р, +~рЯ. 1250) Если К,=со, т. е.
ошибка априорного предстаиления неизвестна, то необходимо для получения удовлетвори! тельных результатов положить Д р, =1 и р,=--О. Поэтому при больших К, ~ч~р, должна быть близка к 1; во всяком случае ограничимся рассмотрением стратегий, удовлетворяющих условию ~ч~~Рс > е > О. Легко убедиться также, что для оптимальных р, должно с быть ~~ р, <1. Действительно, приД р,— 1 > 0 можно взять р,'= Ор„ гдеО<8<1. Тогда, очевидно, ~ р,"О,=Е ~з р)1)с.
с=! с=! Выбирая О < 1 так, чтобы ! ~р," — 1=0~ р,— 1=0, $ 211 пгиизгы нлкснминов н мииимлксоз 2!7 получим, очевидно, стратегию (р,'», более выгодную по (250), чем ( р, », что противоречит предположению еб оптимальности последней. Итак, можно рассматривать только стратегии, удовлетворяющие условию 1> (=Х р!) е > О. (251) Г=! Докажем теперь, что для оптимальной стратегии необходимо р! >О при всех 1. 3- =1 Действительно, предположим противоположное, и пусть для оптимальной (р," » 1, максимальное из тех 1, для которых ~ р,' < О. В силу (251) 1, а..
! — 1; кроме того, не!= ! /!+ 1 обходимо р!,,! > О, так как Д р!'>О. Более того, Рг.+! ~ ~Р! ~ с=! Пусть теперь 1', <1,— последний из номеров, для которых р» < 0; такой номер, очевидно, существует по свойству 1! 11редположим сначала, что 1, <1„тогда р»>0 при 1, <1(1,. Пусть среди этих 1 есть такие, что р1 > О. Тогда, взяв первый из таких 1', заменим дчя него р1, на р,',— Ь при достаточно малом А с одновременным изменейием р',.
на р,'. +Л<0. Величину Л всегда можно выбрать так, чтобы при 1! < з < 1' Д р,"+ Л = = ~ р)+ А < ~ '~ р,' ~ = ~ ~~; р), так как предпоследняя сумма (под знаком модуля) должна быть существенно отрицательна по свойствам /, и 1!. При таком изменении р!, очевидно, не увеличиваются и все ~р„р,' при 1Ф1, (в том числе н 1). Величина же последней суммы в (250) уменьшится. Поэтому новая стратегия даст лучший результат по (250), чем прежняя, что противоречит оптимальности последней. Поэтому или 1!=1„или же все 2!8 !гл.
ш ОПТИМЛЛЬНЫВ СГРАТИГИИ р1=0 при 1, ( 1~1,. Но тогда, уменьшая несколько р „можно аналогично только что указанной процедуре несколько увеличить р,'. (т. е. уменьшить !р' !) так, что все Х р1 не изменятся, кроме 1 из промежутка [1„1Р1, 1йЧ для которых суммы одинаковы из-за р1 — — 0 при 1, (1(1,. Эти последние суммы уменьшатся равно как и ~ч ' р! Рл из-за этого (р1) опять окажется, вопреки предположению, не оптимальной. Это противоречие н доказывает, что для оптимальной стратегии (252) р!>О при всех 1~<!. Учитывая это и (25!), можно опустить модули в (250) и после несложных преобразований привести задачу отыскания оптимальной стратегии в задаче фильтрации к отысканию: г ! !А ! гп!и ~~~ [(1 — 1)К вЂ” КА1 р!+К,) + ~ ~рЯ (258) Р ! 1=! 1=! при ограничениях (25!) и (252). Если этот минимум достигается внутри области, ограниченной (25!) и (252), то для оптимальных рг выполнено: (! — О К вЂ” КО Умножив обе части 1-го равенства на 1!! ! и просуммировав по 1, получим для и = Д[(! — 1) К вЂ” К,1 р, уравнение к ~!(! "К К' =о.
1=! 1=! э 211 пгииееы сслксииинов и минииексов 279 Следовательно, [(с — с) к коР р 1 рс и= — К, с=! ч 1(С вЂ” 0 К вЂ” К!1' с+Л р, с=! а поэтому ~~', 1(с — С) К вЂ” Кс1'— 1 рс с=! к.— К 0 — с) Рс'= р Ко l (254) ~ 1(с — ОК вЂ” К Р 1+~ с=! ! с К с (К,— К( — с)1(1+с (К,— К(с — 01 (255) р ~ю р с=! с с=! которое заведомо не выполняется при достаточно боль!них К„если К4=0. При К=О (256) всегда выполнено так же, как и (255).
Тогда Кс И рс —— , при с=1, ..., 0 р,=1 — Х р,. а'рс сй-1 Рс+Ко ~~~ с=! Из выражения (254) видно, что знак р, определяется знаком величины К,— (с — 1)К„в частности, рс) О. Но по условию (252) для !=1 имеем р,)0. Поэтому выражение (254) будет годиться только, если К,— К(с — 1) ) О.
(255) Но тогда и все оптимальные р~)0 при () О. Если (255) не выполнено, то оптимальная стратегия должна быть такова, чтобы р,=О. В остальном все формулы в принципе остаются без изменения, только р, встанет вместо р, и т. д. и вместо с следует взять ! — 1. Ясно, что этот процесс может быть продолжен для фиксированных К, и К, пока равенство, аналогичное (255), не будет уже выполнено.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
