Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 26
Текст из файла (страница 26)
е. эффективность окажется равной меньшей нз эффек- тивностей стратегий х, и х,. Таким образом, здесь невы- годно комбинировать стратегии даже при многократном повторении и нужно использовать все время одну и ту же стратегию, которая является лучшей при У=1. Этот вывод верен и ри стандартном у, который будет выбираться противником ври О < р < 1 примени- тельно к худшей из стратегий х, и х,. Для реализации этого противнику не нужна информация о конкретном выборе х при повторении операций и даже не нужно знание р, если оно не О или не 1, Тем самым ясна нецелесообразность применения опе- рирующей стороной смешанных или подобных стратегий при критерии (133). Пусть теперь имеется (131), О < р < 1. Тогда при стандартном поведении противника, знающего р, (Р',(р)=пип шах Р(хд, у)= — О<С~РС С =пип шах [Р (х„у); Р(х„у)]. Этот результат не зависит от р, если только О < р < 1.
Если же принять р =О, р = 1 (т. е. чистые стратегии), то лучший результат будет равен шах [пипР(хо у); пипР(х„у)], если опять-таки противнику известно р. В общем случае применение любого числа стратегий х, при комбинированном использовании их (все рс > О и ~~~,рс —— 1) даст эффективность для р = (рс] К', (р) = пип шах Р (х„у), (158) и в то время как применение лучшей чистой стратегии только шах пип Р (х„у). (159) С Р Покажем, что имеет место следующая общая лемма имеющая большое значение для дальнейшего и означающая, что (158) лучше, чем (159): Э 14] пОВтОРение ОпеРлции и смешлнные стРлтегни 155 Лемм а. зцр1п1Р(х, у)(!П1зцрР(х, у). (160) Доказательство. Для произвольного х и произ- ВОЛЬНОГО У ИМЕЕМ 1п1Р(х, О)(Р(х, у)(зцрР(х„у). Р Л~ Но тогда из-за произвольности упрификсированномх ! п1 Р (х, О) ( ш1 зцр Р (хГ, и) = соне!.
Р Р Н, 1 ппп шах (х; — у)'=— 4 шах пт!и (х, — д)' = О, Р при тахшак(х; — у)'= 1. Р Замечание к лемме. Из этой леммы с очевидностью следует, что прн любом виде законов надежности элементов р;(1) поагрегатное дублирование (см. (22) †(23)) выгоднее, чем дублирование системы в целом ((16) — (17)). Все сказанное относительно критериев (131) и (133) имеет место, когда нет случайных факторов (естественных или искусственных). Если таковые имеются, то искать минимум по неопределенным факторам можно уже после соответствующего осреднения, Поскольку это верно для всех х, то верно (160). Из этой леммы немедленно следует, что выгодно использовать как можно большее число стратегий при повторении операций, если, конечно, противник действует стандартно.
При этом безразличны значения рь лишь бы все они были больше нуля. Возможную величину выигрыша в эффективности, т. е. разницу между (!58) и (159), можно видеть на примере Р(х, у)=(х — у)' для хГ=О; 1 при 0<у(1. Здесь оцзикл эеэективности стгатзгий (гл. и В заключение приведем еще один пример полезности использования смешанных стратегий. Воспользуемся для этого моделью Ш поиска экстремума. Согласно проведенной в $ 10 оценке эффективности чистых стратегий (81') для любой чистой стратегии (» ° ° хд У Ч7 < — й — ' (161) Рассмотрим стратегии х(0) вида ! — ! "= а! — од+О (182) Если О, < х, < — О„то ошибка по-прежнему не през взойдет йппп(х,— 8; 0+28,— х,), что в среднем даст величину, не большую (20ю (20о хо) (ха Оо) 3~ (~~ йОо.
гз, где О изменяется в ~0; 0,5 Пусть теперь О случайно и подчинено закону равномерного распределения. Для образования полной смешанной стратегии достаточно положить недопустимыми все стратегии, кроме х(0), распределенных равномерно, вслед за равномерным распределением О. Оценим эффективность этой стратегии. Пусть истинное место реализации экстремума х, расположено в Тогда в силу (811 ошибка определения величины экстремума при фиксированном О не превзойдет величины й)х, — 8). Обозначив О, = , ' , без труда убедимся, 0,5 что в среднем ошибка не превзойдет $14) ПОВТОРЕНИЕ ОПЕРАЦИИ Н СМЕШАННЫЕ СТРАТЕГИИ 157 При всех других значениях х, до 1 — О, величина ошибз ки точно так же в среднем не превзойдет 4 ЙО„а при Азе х,~~1 — О, не превзойдет— Таким образом, в целом оценка эффективности стратегии (162) будет удовлетворять неравенству 3 3 0,3 А — 0,3 )Р ~ — — йО,= — — й Сравнивая это с (!61), видим, что смешанная стратегия (162) при М > 2 более эффективна, чем любая чистая стратегия (в среднем, конечно); прн больших У этот выпгрыш достигает 25'1,.
ГЛАВА 111 ОПТИМАЛЬНЫЕ СТРАТЕГИИ $ 15. Понятие оптимальной стратегии в зависимости от информированности оперирующей стороны и противника Пусть дано множество М стратегий х(г, у) =х и множество У значений неопределенных факторов у; пусть г— случайные факторы. Будем считать, что критерий эффективности г"(х, г, у) разрешается осреднять по законам распределения <р(г) (если такое осреднение не разрешается, то случайные факторы приравниваются к неопределенным); осредненный критерий будем обозначать через г"(х, у). Тогда, если цель активного противника (когда он есть) противоположна цели оперирующей стороны или если цель противника неизвестна, то по (67) оценкой эффективности стратегии х является !п1 ~г"(х, г, у)йр(г)= 1п1г(х, у).
Поскольку х зависит, вообще говоря, от г, то результат осреднения зависит от вида х как функции г. В соответствии с двумя отмеченными выше случаями сравнения стратегий можно ввести и два понятия оптимальной стратегии. 1. Под оптимальной стратегией (оптимальной гарантирующей) х, в множестве М следует понимать такую стратегию х„для которой достигается максимум указанной оценки эффективности, т. е. !п1г (х„у) = шах !п1 Р(х, у) =Г„(М). (!63) гчл лчмрчя й 15! попятие ОптииАльпой стРАтеГий 159 Сама величина Р„есть оптимальный гарантированный результат проведения операции с точки зрения исследователя операции.
Это определение, конечно, не может быть заменено термином: «оптимальна пара х„ у„ для которой Р(х„, у,)=шах!п1Р(х, у)», ибо макснмин является величиной, лежащей между шах гпахР(х, у) и ш(пш(пР(х, д), и поэтому это значех у у х ние принимается в бесконечном числе точек, не имеющих никакого отношения к оптимальной гарантирующей стратегии. Так, например, Р(х, у)=х+у, (0~(х<1, 0(у(1) имеет максимин, равный 1, и единственное х,=1; в то же время все пары, удовлетворяющие уравнению х+у=1, также дают значение функции, равное максимину, хотя соответствующие х и не являются оптимальными гарантирующими стратегиями.
Если верхняя грань Р„(М) величины (п1Р(х, у) по у«»Г хЕМ недостижима ни прн каком х„то оптимальной гарантирующей стратегии нет, но для любого з всегда существуют приближенно оптимальные стратегии х, (так называемые е-стратегии), удовлетворяющие неравенству 1п1 Р(х„у) Ъ зпр ш1 Р (х, у) — з = Р„(М) — е. (163') х«М у«У В случае конечного количества стратегий в М (сравнение эффективности заданных стратегий) оптимальная стратегия всегда существует. Оптимальная стратегия (и тем более е-стратегия) может быть не единственна; тогда задача может состоять или в отыскании всех таких стратегий или в отыскании хотя бы одной из них.
Поскольку все стратегии в данной операции для оперирующей стороны априори равноценны, то достаточно нахождения хотя бы одной оптимальной (или приближенно оптимальной) стратегии. Надобность в знании всех может появиться только, если данная операция является составной частью другой более широкой 160 1~л. п~ йптаилльныс с|РАтгзип операции, исследование которой предполагается произвести когда-либо потом.
П. Под абсолютно оптимальной стратегией (когда она есть) будем понимать такую стратегию х, Е М, для которой Р(х„у))Р(х, у) при любых хЕ М и уЕ Ф. Иначе говоря, Р (х„у) = щах Р (х, у); у Е У. (164) «ем Под е-абсолютно оптимальной стратегией следует понимать х',Е М, для которой Р (х,', у) э знр Р (х, у) — е (164') при любых у~ У.
Разумеется, всегда желательно получить хотя бы е-абсолютно оптимальную стратегию, а не просто оптимальную. Однако это редко бывает возможно. В качестве примера, где при малых е отсутствуют е-абсолютно оптимальные стратегии, можно указать на Р(х, у) =х у при М = ( — 1, 1] = й1. Здесь оптимальной стратегией является х=О, а е-абсолютно оптимальной стратегии при е<1, очевидно, нет, ибо при любой х, Ф 0 существуют у, = — з)дпх,=х, так, что Р (х„у,) = — ! х, ~ < 1 — 1 = Р (х„у,) — 1. Также очевидно, что прн х,=О и при у,=1, х,=1 имеем Р(0, у,)=0 < Р(х„у,) — е при е< 1.
Пусть теперь существует х,. Оценка эффективности для х„ очевидно, будет удовлетворять ! п1 Р (х„, у) ) 1п1 Р (х, у) «ел при любом хЕ М. $ 161 ПОНЯТИЕ ОИТИМАЛЬНОЙ СТРАТЕГИИ 161 Отсюда очевидно, что ш1 Р(х„у) =шах 1п1Р(х, у) = Р„(М). РЕЮ «ЕМ дЕФ Таким образом, абсолютно оптимальная стратегия (если она существует) является и просто оптимальной. Соверщенно аналогичное утверждение верно, конечно, и для оптимальных с точностью до е стратегий. Отсюда следует, что, отыскивая все оптимальные стратегии, мы среди них отыщем и абсолютно оптимальную, если она существует. Здесь, поскольку всегда хочется иметь абсолютно ,"оптимальную стратегию, мы приходим в противоречие с высказанным только что тезисом об отсутствии необходимости поиска всех оптимальных стратегий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
