Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 30
Текст из файла (страница 30)
Как уже говорилось, множества стратегий М, и М, отражают крайние степени возможной будущей информированности оперирующей стороны. Если М, абсолютно реально, то реализация М„, даже приближенная, как правило, затруднительна; с чисто методической точки зрения реализация М, (и, значит, получение Р„) вообще невозможна, потому что любое измерение или узнавание неизбежно связано с новыми случайными и неопределенными факторами, значения которых уже не будут известны оперирующей стороне. Дело усугубляется еще и тем, что информация о у появляется обычно не сразу, а по мере развития операции во времени, в динамике операции. Поэтому решения о выборе координат вектора х необходимо производить постепенно, по мере поступления информации о у. Рассмотрим общий случай предполагающейся динамики в информированности оперирующей стороны.
Положим, что информация о г не поступает ни к оперирущей стороне, ни к противнику. Пусть вектор х состоит в свою очередь из векторов х„х„..., х„, записанных в порядке течения времени и принятия о них оперирующей стороной решений в соответствии с изменением информации о у. Информация о у в момент ( считается состоящей в указании того, к какой из частей У,(и;) множества У принадлежит у.
Здесь а; — может быть, даже континуальные «номера» этих подмножеств, например, «наименьшее» из у, принадлежащих этим множествам. Должно быть Д,'У;(а~) =У для любого (. а» Далее, поскольку информация может с течением времени только увеличиваться, то каждое из У»(и;) должно представлять собой сумму некоторых из У;+,(а,+,). Мпо- $151 ПОНЯТИЕ ОПТИМАЛЬИОй СТРАТЕГИИ 179 жЕСтВО ТЕХ Иэ игео дяя КОтОрЫХ УГ„(а;е,) ПрИНадЛЕжат )У1(а;), будет обозначаться [а1+1)- . Отсюда следует, что стратегии х(у) в этом случае могут быть записаны в виде*) х= [х1[)»'1(аг), ху)1<ГЦ = [х;(и;, ху)1 < 1)), 1= 1,, К (182) если предположим, что при принятии решения ох; известны все ху длЯ / < 1 (в теоРии игР соответствУющие игРы называются играми с полной памятью).
Множество этих стратегий обозначим через М„. Все эти предположения не меняют, разумеется, общей записи платежа или оценок эффективности (67), равно как и общей записи наилучшего гарантированного результата (163) — (164), а лишь конкретизируют выбор семейства функций М в виде всех функций типа (182). Однако если бы мы сделали аналогичную запись стратегий для противника и установили бы общий порядок изменения информации и принятия решений обоих игроков (порядок «ходов»), то получили бы «многошаговую» игру.
Тот факт, что платеж был бы все равно равен г(х, у)=г(х„..., ха, у„..., р»), где х и у — суммарные стратегии сторон типа (182), последовательно определяющие значения «ходов» хг и уь называется в теории игр сведением многошаговой игры к игре в нормальной форме. Принятие определенной последовательности улучшения информации и стратегий (182) позволяет и наилучший гарантированный результат (163) — (164) записать (равно как и процесс его получения) в виде многошаговой процедуры, совершенно аналогичной процедуре динамического программирования. Действительно, в момент принятия решения об х» будут известны Уже все х; пРи 1 < й и то множество 111» (и») (т.
е. номер сса), к которому принадлежит конкретное у. Тогда, а) При желании функции «;(и„х ) могут трактоваться в виде функций типа (Па). 180 (гл. ш Оптимхлы(ыв стгатегии естественно, наилучший гарантированный результат для этого момента будет* ) бах ппп Р(х„...,ха „ха, уг)=Ра(х„..., ха „с(а). «ь веда(оь) (183) Соответственно наилучшей гарантирующей стратегией ха (х„..., ха „с(а) = ха будет стратегия, для которой ппп Р(х„..., х„„хаа, у) у е ма (йи равен (183). Перейдем к выбору х,, Теперь платежом (критерием эффективности) является функция (183); с(а — неопределенный параметр, ограниченный тем, что известно ха х и то, что а„принадлежит (иа) — „„,.
Тогда наилучший гарантированный результат на Й вЂ” 1-м шаге, очевидно, равен гпах ппп Ра(х„..., ха „аа) = ль, оэе(оа) „„ =Ра д (х, ..., ха „аа,). (183') Соответственно опРеделЯетсЯ и хае ((х„...,х „с(а э). Понятная теперь рекурренция заканчивается определением Р((и,) и хт(а,) и окончательной гарантирующей оценкой Р", = пни Р, (а,). (183") Тот факт, что стратегия (х,'(х„..., х; „а()) =х', есть оптимальная гарантирующая из стратегий (182), доказывается дословным повторением рекурреиции, на основе которой была определена эта оптимальная стратегия. Действительно, пусть имеется произвольная стратегия (182). ') Здесь в далее для простоты рассуждений предполагается достижимость всех верхних и нижних граней.
Однако общая схема остается беэ иэмененнй и в других случаях. 181 $151 ПОНЯТИЕ ОПТИМАЛЬНОЙ СТРАТЕГИИ Тогда ппп Г (х, [а„х/// < 1), р) = =ппп ппп г (х,(а,), х,(а„х,),... ау уеА(у (ау) ..., х,(и и х// < й — 1), х (и„, х// </е), у).
Но фиксация ау влечет за собой фиксацию и,при/<и, поскольку соответствующие Л/ (и,) должны содержать Уу(ау); поэтому будут фиксированы для заданной стратегии и все хп Отсюда имеем в силу определения х3 пип г" (х„..., хэ „ху, и) ( УеА)у (ау) < ш(п р[х„..., х„„хуе(х„..., ху „иу) У) = уе))у (ау) =РА(х„..., ху-) ау) и ш(п п(х;[ао х///< 1) у) (ш)пРА(х((а( х/// < () ау) = у Е (У ау =пт(п ппп Гу(х,(ие)...ху,(иу „хЯ<й — 1).иу). ау, ауе(ау)— ау-1 Повторяя рассуждение й раз, придем, наконец, к ппп Г (х; (а„х/// < ( ); у) < ппп г', (и,) = г",. РЕП а, Поскольку это верно для любой стратегии (182), то оптимальность стратегии х' в смысле (162) для М=М„ доказана. Стоит отметить, что проведенная рекурренция типа динамического программирования позволяет дать и соответствующую трактовку задачи исследователя операции по пониманию и отысканию оптимальной гарантирующей стратегии.
Именно задача исследователя операции разбивается как бы на две задачи на каждом й-м шаге процесса. 1. Исследователь должен определить критерий эффективности (на з-м шаге от начала процесса), которым является функция Р,+, (х„..., х„ауе,). 182 [гл. ш ОПТИМАЛЬНЫЕ СТРАТЕГИИ )У=У,ХАГ,Х... Хй(„. Тогда к моменту определения х, ничего о у не известно, кроме у~М. Поэтому Л/,(а,)=й(, а,=сонэ(=0. В момент решения о х, уже известно у,; множество 1т',(а,) представляет собой множество У (у,) возможных векторов у с фиксированной частью координат у,; а, =у,.
Аналогично У;(а~) есть )Ч(у„..., ут,)-множество векторов у с фиксированными у„..., у,. Множество (аГ),—,, есть, очевидно, не что иное, как ФГ,. Стратегия оперирующей стороны приобретает вид х = (хГ (хР, у,; / ( 1); 1 ( Ц (184) и рассчитана на поступление точной информации о у;, к моменту принятия решения о хи Это означает, иными словами, что цель операции (критерий эффективности) меняется со временем (номером шага) и исследователь операции должен выяснить эту динамику.
2. На каждом з-м шаге исследователь операции должен дать алгоритм решения задачи поиска оптимального гарантирующего вектора х, при любых фиксированных х„..., х,, и известных (а,+,) — и а,. Таким образом, здесь идет речь об алгоритме решения одношаговой игровой ситуации в чистых стратегиях. При такой трактовке особо может быть поставлен вопрос о возможности задания упрощенных приближенных г, „поскольку оперирующая сторона в целом может выбирать критерий достаточно произвольно, а, значит, и его динамику.
Рассмотрим один из частных случаев описанной динамики, полагая, что к моменту принятия решения о х; будут точно известны векторы у при / < 1, где вектор у составлен из Уу(1(й), так же как и х из хп Пусть множество Ф векторов у есть декартово произведение множеств У~ векторов у 5 151 ПОНЯТИЕ ОПТИМЛЛЬНОЙ СТРЛТЕГИИ 183 Наилучший гарантированный результат Р", в этом случае по (183) †(184) приобретает вид шах пнпР(х, у) = у у»у =Рвах ппп ...
шах ппп Р(х, ..., х„, уо ..., у»). у у и у»л у»ум» у»уу» (184') Здесь под М, понимается множество значений вектора х, так, что М,=М,хМ»х... ХМ». Отмеченная выше динамическая процедура получения оптимальной стратегии в данном случае превращается в точное или приближенное определение критериев Р,(х„..., х„у,...., у,,)= = ш1п шах ...
шах пнп Р (х„..., х„, уо ..., у„) у у+, у» у» и в выдачу алгоритма определения вектора х'„реализующего — е шах Р,(х„..., х„у„. -, у,-») Лу Пользуясь этими материалами, оперирующая сторона будет определять конкретное значение х,' непосредственно по получении информации о у„ ..., у,, Разумеется, ситуация с йнформироваиностью сторон в многошаговых процессах отнюдь не исчерпывается ситуациями (184) и даже (182) и результатами типа (184') или (183 ). Даже в схеме, имеющей в общем вид схемы (184), может существовать вектор х»„, заведомо не становящийся известным противнику, как и у» неизвестен оперирующей стороне.
Тогда возникает ситуация, удобная для применения смешанных стратегий относительно х„+,. Однако это не сильно изменит запись наилучшего гарантированного результата (184). Нужно лишь ввести новые понятия стратегий, включив ~р(х„+,) вместо х»+, и введя вместо Р(х, у) 184 ОПТИМАЛЬНЫЕ СТРАТЕГИИ (гл. ш соответствующий осредненный по у(ху~,) платеж г (х„..., хь, ~р (ху,), И1,..., ЙА) = = ) Р (х„..., х„, ха у„у„..., рк) Йр (хк+,). (185) Однако даже эти многошаговые сложные процедуры есть, как мы уже знаем, только частный случай общих постановок вопроса об оценке эффективности стратегий и выбора наилучшей из них, данных в (67), (163) и (163') при специальном виде стратегий, рассчитанных на ту или иную информацию оперирующей стороны о неопределенных факторах. Несколько хуже обстоит дело с учетом постепенного уточнения информации о случайных факторах; здесь, видимо, необходимо выходить за пределы теории антагонистических нгр и оценок (67).
Отчасти поэтому мы не будем рассматривать этот вопрос. Из всего сказанного в этом разделе видно, что не существует единого понятия оптимального выбора и оптимального гарантированного результата, все зависит от той степени информированности оперирующей стороны о неопределенных факторах, которую можно ожидать или которую зададут исследователю операции. Если же не задавать информированность, то необходимо исследовать влияние ее на результат операции и выбор стратегии. Такое исследование в сколько-нибудь полном виде практически невозможно, если векторы х ну име|от значительную размерность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
