Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 25
Текст из файла (страница 25)
Конкретно это можно реализовать двумя путями. 1. Реализуются определенные частоты применения р и 1 — р в У повторениях, но номера, при которых берутся х, и х„выбираются случайно„скажем, комбинация номеров с„..., урсс применения х, выбирается с вероятностью рс„., с, так что сумма всех таких вероятностей равна 1. Интуитивно ясно, что следует взять равномерное распределение, т. е.
принять 1 рс,...,с „=сопз1= — „. ау рсс Но тогда, осредняя (132) по этим случайностям, получим 1Р'.(р у') = Е '"„"'" Х (с,.... с„,) х Х р(х„ус) + Х р(х„ус), се(с1, ..., асс) сс(с„...,срсс) где у, †стратег, применяемая противником в с-м повторении. Меняя порядок суммирования, очевидно, имеем ч(с,(Р, У') = ~ '>' Р (х„ Ус) ~Х'~ Рс„ ...,с „ + (с„...,с м)сс +~ ~Р(х„Ус) (1 — ~Ч' "" ° - .асс с= с= с (с,..... сал) э с лс с яу-с г с'сс '1 сс ~ 1 =у ~~ (рр(хс, ус)+(1 — р) Р(хс, ус)).
(150) с с 148 оценил зеезктивности стухтегий !гл. и Отсюда, учитывая независимость выбора уь при раз- НЫХ 1 ПОЛУЧИМ ппп!У',(р, у') =,— „ппп ~ !РР(х„у1)+(! — Р)Р(х„у,.)]= У У. "., У»»1=! !Е = — ~~!' гп1п !РР(х„у)+(1 — р) Р(х„у)] = ;=! У = гп!п(РР(х„у)+(! — Р)Р(х„у)], (151) т. е. действительно, не предполагая стандартности действий противника, можно получить результат (146), правда, в среднем.
Легко теперь убедиться, что указанные значения Р», ... 1,»! действительно дают паилучгний результат. В самом деле, при любых р»,,;„„полагая, в частности, у, = —... =- у1т =- у, получим »т ° ~М (»„.... 1 ~) Х ~~' Р(х„у;)+ ~, Р(х„у;) ( 1=1 1=1 1Е(1». " ° !рай) 1Ф(1» -'!УЕ»] !и!и ~~'. ' ' У" "!р!»!Р(х„у) + (! — Р)1!Р(х„у)] = У (1,., 1рн) =и!!п(РР(х„у)+(1 — р) Р(х„у)] =гп!и Уl,(р, у ), (!52) У У» так как ~ Р1„...,! м=1. ( 1»,..., 1У1У] Но неравенство ( 152) и означает требуемое утверждение. Суммируя сказаннм, имеем, что применение стратегии р, т.
е. в )ту случаях х„а в Ф(1 — р) случаях х„гарантирует нам при случайном равновероятном выборе номеров повторений, в которых применяются х, и х„в среднем оценку (146) при любых комбинациях неопределенных факторов. Это верно, если противник не информирован э' 14! повтотвнив опвгвции и смвшвнныв сттлтвгин 149 о конкретном (хотя и случайном) выборе номеров, в которых берется х,.
Совершенно аналогично обстоит дело и при применении различных стратегий хт, лишь бы Ф/й было целым. Тогда вместо (146) при фиксации величин р (г~~.",р =1 ~/=г будем иметь оценку / А К,(р)= ш(п~ ~чр~р~р(хт, у)) . (153) р !=! В этой записи р; есть частота применения х; и потому р;Ф вЂ” обязательно целое число. Используя частоты р;=О, можно, конечно, считать й в произвольным; однако всегда р; = т;/М и ~т;= У.
П. Случайность вводится в выбор стратегии х, или х, в каждом повторении операции, независимо от его номера и независимо от предыдущего выбора. Тогда р трактуется уже как вероятность выбора стратегии х, в каждом повторении операции. Появляется, следовательно, искусственно создаваемая оперирующей стороной случайность при каждом повторении операции независимо от У. Осреднение Р(х, у) по этим случайностям дает новый критерий эффективности пары стратегий х, и х, в каждой операции Р(р, у) — — рР(х„у)+(1 — р) Р(х„у). Обобщая это, введем понятие смеси стратегий х„..., хв как совокупности вероятностей р, применения стратегий хп при обязательном условии,~ Яр~ — — 1. 1=1 Если в смесь формально входят все имеющиеся у оперирующей стороны стратегии, пусть некоторые с р;=О, то такая смесь обычно называется смешанной стратегией.
Понятие смешанной стратегии легко обобщается и на бесконечные множества возможных значений вектора х= (х„..., х,). Тогда только должны задаваться законы распределения ик <р (х'), т. е. вероятности р (х, < х,', х, < х,'... < х, < х,') того, что случайный вектор х 150 оцннкл зеенктннностн стглтнгнй [гл. и окажется меньшим вектора х' = (х', ); смешанной стратегией и называется здесь закон распределения вр(х'). Осредненный критерий эффективности для смешанной стратегии приобретает вид Р [вр(х); о) = ( ...( Р (х„ ..., х„ й)в[ар(х„ ..., х,) =- ') Р (х, р)в[ар(х).
(154) Под интегралом ) Р(х, у)г[вр(х) понимается з-мерный интеграл типа Стнлтьеса, т. е. предел сумм Р(х,в„х,в„..., х,в„р)х ва хр(хвв, <х,<х,в,+„..., хн,<х, <хв,+в) при увеличении числа точек хы разбиения области изменения каждой координаты х„ вектора х. Здесь р означает вероятность попадания вектора х в малый параллелепипед, определяющуюся через вр(х'): р =ар(хвв,+„..., хн,+в) — Яр1+ ~ Х р1,— 1=> 1=в 1=1+> в-в в-в в — р1в +... + ( — 1)в гр (хвп, ..., х в,), 1=« 1=1+1 >=1+> где Рп „вЂ” значение вр(х,', ..., х,') при х'=х;,1 х,' = = хнва ° ° ° а хва=хввв„а и пРИ остальных Равных х в,+,.
Именно поэтому для единства записи интеграла мы и воспользовались формой записи (154) вместо обычно используемой формы ) Р(х„..., х) р(в[хв ... Й~,). С многомерным интегралом Стилтьеса и его свойствами можно познакомиться в книге Шилова и Гуревича «Интеграл, мера и производная>. Если имеется плотность распределения вероятности 1(х„..., х,), то (154) приобретает вид ) ... ) Р(х„..., х„р)~(х„..., х,) в[ха ... «[х,. з 141 повтогяяяз опзг»цяя я смеш»яныз стглтегяи 151 Компоненты х; случайного вектора х в смешанной стратегии могут быть, конечно, и независимы, но это только частный случай смешанных стратегий. Обобщение понятия смешанной стратегии на случай, когда значения х есть функции, связано с затруднениями в понимании соответствующих законов распределения, и здесь рассматриваться не будет.
Как уже говорилось ранее, такие функции будем заменять их значениями на дискретных множествах аргументов, а тогда достаточно рассмотреть уже определенные смешанные стратегии. Из (154) получаем (132): Я7,(ф(х),у)= — ~~,Р(<рсх), у!) (!55) «=1 и отсюда приходим к оценке эффективности смешанной стратегии в виде Я1, (<р(х)) =пцп Р(!р(х), у). Однако теперь эта оценки имеет смысл и при У=1, а р; трактуются уже не как частоты применения стратегии х, в У операциях, а как вероятности их применения в каждой операции.
Это существенно отличает применение смешанных стратегий от способа 1 введения случайности. В дальнейшем, следуя сложившейся в теории игр традиции, будем все время вести разговор о смешанных стратегиях; этому способствует и большая простота действий с ними. Это тем более допустимо, поскольку при смешении конечного числа стратегий (155) и (156) формально совпадают с (153), если не учитывать разницу между вероятностями и частотами.
Однако смешанные стратегии определены и при бесконечном числе чистых стратегий, в то время как в спосабе 1 число стратегий с р!чьО не может превышать числа У, т. е. числа повторений операции. Не следует забывать и о разнице между этими двумя подходами с практической точки зрения. Действительно, подход 1 реализуем всегда, поскольку р, определяемое заранее, обусловливает и необходимый «запас» стратегий х, и х, для У операций. При использовании же 152 ОЦЕНКА ЭФФЕКТИВНОСТИ СТРАТЕГИЙ [ГЛ. Н смешанных стратегий количества х, и х, оказываются случайными, что не может не вызвать затруднений, если подготовка «запаса» х, и х, связана с какими-либо действиями, например, с производством. Применение комбинации стратегий может, конечно.
стать практически невозможным или нежелательным по каким-либо причинам; тогда пропадает смысл в рассмотрении обоих методов искусственного введения случайности (иначе называемых рандомизацией стратегий). Следует не забывать о принципиальном отличии случайности в смешанных стратегиях от обычных случайных факторов, состоящее в том, что первые случайности относятся к категории сознательно выбираемых, контролируемых факторов, а вторые в к неконтролируемым.
Итак, применение смешанных стратегий !р(х), расширяя множество стратегий оперирующей стороны (прежние стратегии х, именуемые «чистыми», получаются как частный случай смешанных, когда вероятность появления данной чистой стратегии х, равна 1, а остальных х— нулю), позволяет рассчитывать и на изменение эффективности с пппр(х, у) на пппр(!р(х), у], что при разумном выборе !р (х) должно дать увеличение достижимой эффективности ввиду увеличения множества стратегий. Однако эти надежды основаны на двух существеннейших предположениях. а) Осреднение критерия по случайностям (естественным или искусственным) по (66) допустимо. б) Противник не имеет информации о конкретном, хотя и случайном, выборе х, т.
е. неконтролируемые неопределенные факторы не могут выбираться по принципу реализации пппР(х, у). Иначе это означает предположение об отсутствии связи между х и у. Возможность же знания <р(х) не отрицается. Принятие первого предположения, как уже говорилось в Э 6, может быть иногда неприемлемым риском. Применение лсе смеси стратегий (т.
е. Кол!бинаций), если недопустимо осреднение (66), априори осмысленно только 141 поетоееняе опеелцсссс и сиешлнные сселтю ан 153 при стандартном поведении противника в мноеократно повторяющейся операс!ии. Предположение б) еще более существенно для сравнения эффективности смешанных и чистых стратегий. Между тем во многих книгах по теории игр оно объявляется следствием случайности выбора конкретной стратегии при использовании смешанных стратегий; откуда, мол, может узнать противник то, что заранее не известно самому исследователю операции и даже оперирующей стороне.
Эго утверждение, однако, неверно, особенно, если случайный выбор по необходимости должен быть произведен достаточно рано по отношению ко всему течению операции. Рассмотрим теперь простейший пример, показывающий возможную выгоду применения смешанных стратегий. Пусть имеются всего лиспь две стратегии х, и х,идва значения неопределенных факторов у, и у„ а критерием пусть является символ Кронекера — — с 1, 1=1, Р(хн ух)=Ь, = ( О' ( Тогда для любой стратегии х; пппР(хн у~)=0. ес В то же время применение смешанной стратегии с р = 0,5 гарантирует получение в среднем %'(р, уу) = 0,5 при максимально возможном значении исходного критерия эффективности 1.
Перейдем теперь к вопросу о том, какой смысл может иметь применение смешанных стратегий или, лучше сказать, комбинации стратегий при многократном повторении операций, если будут критерии (131) или (!33). Ограничимся случаем двух стратегий х, и х,. Приняв критерий (!33), получим при 0 < р < 1 даже при стандартном поведении противника оценку эффективности (157) (р) =ппп ппп Р(х~ у), — „с<с<в с' где 1;=1, 2. Поскольку из-за 0 < р <! каждое из этих значений принимается хоть один раз, то !Р„(р) = ппп (ш!и Р (х„у); ппп Р (х„у)), 154 ОЦЕНКА ЭФФЕКТИВНОСТИ СТРАТЕГИЙ 1Гл. сс т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
