Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 36
Текст из файла (страница 36)
Однако при прямом применении этой процедуры может образоваться цикл, т. е. на каком-то этапе мы возвратимся к 1,. Пример цикла дает матрица О О О О О: — 1 4 О О! 3 — 1:;О ,! 2 3 4 в которой цикл обведен ломаной линией, а седловая точка †полужирн цифрой. Конечно, замкнув цикл, можно взять новую стратегию, не совпадающую ни с одной стратегией цикла, но выгоднее исправить процедуру следующим образом. Возьмем произвольную 1„и найдем все 1,(1,), реализующие шахам,. Для каждого 1,(1,), обозначаемого 1„ найдем А;, и все 1„реализующие его. Если одно из 1, совпадает с 1„то 1, и соответствующие 1, дают седловую точку.
Если среди этих 1, нет 1„то на столбце 1, седловая точка ие может находиться, и он исключается из матрицы для дальнейшего поиска. Взяв любое 1, и найдя уже все 1,,эь)„реализующие ш1пгпь для каждого из найдем 1, реализующее шах Р;;,. Если хоть одно из совпадает с 1„то седловая точка найдена. Если же нет, то строка 1, вычеркивается. Далее для какого-то 1,, находятся 1„реализующие гпах Рп!. Процедура опять ! Ч!с заканчивается или 1, вычеркивается и т. д. Ясно, что при таком способе уже невозможно образование цикла, и после некоторого числа шагов седловая точка находится, если она есть. 220 [ГЛ, Ш ОПТИМАЛЬНЫЕ СТРАТЕГИИ Задача поиска оптимальных гарантирующих стратегий и максиминов нова*), во всяком случае, в общей постановке, и только в самое последнее время начали появляться посвященные ей работы.
Существует представление, что эта задача более простая, чем решение игр (т. е. нахождение наилучших стратегий) в смешанных стратегиях, чему посвящено уже множество работ, хотя, к сожалению, в основном зарубежных. Такое представление основано на том, что чистые стратегии являются частным случаем смешанных, и потому их меньше и проще отыскать лучшую. Зто было бы действительно так, если бы оптимальные смешанные стратегии искали только методом простого перебора. Однако на самом деле для отыскания оптимальных смешанных стратегий, как мы увидим далее, разработаны специальные численные методы решения игр, а также имеется большое количество аналитически решенных моделей.
Все эти приемы основаны на наличии в смешанных стратегиях седловой точки и, самое главное, на сугубо специальном простом виде критерия эффективности для смешанных стратегий, имеющем линейный вид относительно смешанных стратегий противников (а в целом— билинейный вид). Все эти обстоятельства, как правило, отсутствуют при нахождении оптимальных гарантирующих чистых стратегий и соответствующих максиминов (или минимаксов).
Поскольку чистые стратегии получаются из смешанных при наложении условий равенства нулю вероятностей применения всех чистых стратегий, кроме одной, то переход от решения игр в смешанных к решению в чистых стратегиях совершенно аналогичен усложнению решения задачи линейного программирования при увеличении количества условий. Таким образом, решение игр в чистых стратегиях представляет собой не менее сложную и специфическую математическую задачу, чем решение в смешанных стратегиях.
В предыдущем разделе было показано, что всякая задача о поиске максимина (и минимакса) может быть сведена к задаче о поиске седловой точки в соответствующим образом определенных расширенных множествах стра- ') В дальнейшем для краткости вту задачу Судем иногда наны. вать задачей решения игр в чистых стратегиях. $11) неовходииыв ьсловня оптимлльностн 221 тегий противника. Казалось бы, после этого нет необходимости специально рассматривать задачи определения максимина и минимакса. Однако на самом деле получающаяся при этом между стратегиями связь типа х++у(х) (при произвольности вида функций у(х)) не дает возможности эффективно применить известные необходимые условия экстремумов так, как это сделано, например, в теореме ХХЧ, когда есть седловая точка для стратегий х и у. Попытка использовать эти необходимые условия приводит к тем же вычислительным и математическим проблемам, что и прямое определение максимннов, минимаксов и соответствующих оптимальных гарантирующих стратегий.
Выше уже было упомянуто о стандартной возможности приближенной замены множеств М, и У на дискретные конечные множества М", и )Ч" с использованием нахождения максиминов прямым перебором. Однако если множества М, и Ф не ограничены, т. е. не будет обеспечена равномерная непрерывность критерия эффективности Р(х, у), то дискретизация задачи не удается, поскольку М~ и У" окажутся бесконечными, лишая тем самым нас возможности произвести необходимый перебор. Тяжелое положение может практически, конечно, создаться и при слишком больших множествах М", и У", несмотря даже иа умеренные требования к точности приближенной замены.
В связи с этим отметим: оперирующая спшрона может волевым актом существенно ограничить количество рассматриваемых стратегий, т. е. множество М~ (или М,); зто ее неотъемлемое право, поскольку вся операция формируется в конце концов ею, а не исследователем. Однако ограничить У~ — т. е. И вЂ” волевым актом оперирующей спироны нельзя, это неконтролируемый ею фактор, произвольное изменение его лишает исследование объективности, а результаты — гарантированности. Это весьма важное различие между множествами стратегий часто забывается; противнику необоснованно приписываются наши желания и возможности, что зачастую ведет к совершенно неожиданным результатам операции.
Даже если противник обладает ограниченными возможностями по просмотру всего У'()Ч) и выбору стратегий 222 ОПТИМАЛЬНЫЕ СТРАТЕГИИ 1гл. ш из этого множества, то и тогда это ничего не гарантирует, поскольку не известно, какие именно стратегии он выберет для сравнения в множестве У, которое считается известным. Единственно, чем может воздей вовать оперирующая сторона на мощность У', это †выб точности замены е и критерия эффективности. Об этом обстоятельстве не нужно забывать при выборе цели †критер эффективности в операции. Интересно отметить, что критерий, принимающий лишь два значения 0; 1 (или вообще критерии, принимающие конечное число значений), наиболее нелрихопиив по отношению к е.
Очевидно, что допустимо любое е ( 0,5, так как при таком приближении вообще исключены ошибки в определении исхода операции при дискретизации М, и )Ч; сохраняется и наличие седловых точек. Возможно, что сравнительная простота поиска наилучших стратегий и является основной причиной широкого распространения критерия 0; 1 в жизни. Разумеется, при таком критерии встречаются и свои трудности, прежде всего связанные с разрывностью критерия эффективности на М, х Гт'.
Не следует, конечно, преувеличивать возможности выбора типа критерия в модели без радикального изменения исходной пели операции, Поэтому необходимо наряду с приближенной дискретизацией задачи разрабатывать другие методы. Кажется рациональным, например, проведение дискретизации только по х, оставив непрерывным у.
Тогда задача приближенного определения максимина будет выглядеть как нахождение для дискретных х; минимумов пйп г ~хи у) =-А; Р с последующим перебором А; для нахождения максимального. Здесь основой численных методов будут известные методы поиска экстремумов функций. Далее встает вопрос — нельзя ли уменьшить множество дискретных стратегий, которые необходимо рассматривать, за счет предположений о достаточной гладкости критерия. Эго есть по существу вопрос о необходимых условиях 17) необходимые услОВия ОитнмАльностн 223 максимина, к изложению состояния которого мы и перей- дем.
Начнем с простейшей теоремы. Т е о р е м а ХХ'Ч1. Пусть Р (х, р) — непрерывная функ- ция, заданная на замкнутом множестве Е точек (х, р), где а<х(Ь, а р — точки некоторого компактного мно- жества топологического пространства. Пусть, далее, существует непрерывная Р„'(х, р). Тогда для того чтобы х, была оптимальной гарантирующей стратегией, необходимо существование р, для которого Р (хм р) =- ппп Р (х„р) = гпах 1п1 Р (х, р), (20б) л х р и выполнение хотя бы одного из трех условий: а) Р„'(х„р)= 0; б) существует р, чар, для которого Р (х„рх) = Р (х„р) = ппп Р (х„р); (207) в) х, принадлежит границе области изменения х, т. е.
равно а или Ь. Доказательство. Утверждение (206) является оче- видным следствием определения оптимальной гарантирую- щей стратегии и непрерывности Р(х, р) на компактном множестве Е. Пусть теперь х, лежит не иа границе, т. е. а < х, < Ь, и пусть не существует р„обладающей свойствами (207).
Тогда, обозначив через р(х) любую точку, удовлетворяю- щую равенству Р [х, р (х)) = ппп Р (х, р), в силу непрерывности Р(х, р), компактности рассматри- ваемого пространства и отсутствия р, чь р, имеем, что р (х) р при х х, (см. доказательство теоремы ХХ). Но по определению х, Р(х„р)=шахш(пР(х, р)=шакР [х, р(х)1. х р х Поэтому 0)Р[х, р(х)1 — Р(х„р) =Р [х, р(х)1 — Р[х„р(х)1+ +Р[х„р(х)1 — Р(х„р) )Р[х, р(х)1 — Р[х„р(х)), [гл. п1 оптимальныз стглтегии так как по (206) Р [х„р(х)] — Р(х„р) )О. Но тогда О ) Р„' [х, + 0 (х — х,), р (х)] (х — х,); О < 0 < 1.
Отсюда получаем Р;[ха+0(х — х), р(х)]<0, если х)х,; Р;(ха+0(х — х), р(х)])0, если х< ха. Непрерывность Р„'(х, р) и то, что р(х)- р при х- х„ приводят к выводу Г (х, р)=0, Р;, (х„у') (у', — с;) (у; — йг) = = Р„' (х„у„) (уи — с;) (уи — аа) ='0; 1<1кт, Р (х„у ) Р (х„у,). (209) что и завершает доказательство теоремы.
Пусть теперь пространство [р) состоит из точек т-мерного пРостРанства У=(У„...,У ) пРиУсловиЯхс;<У <йо и пусть существуют Р„' (х, у„..., у„) (необязательно непрерывные). Тогда имеем Следствие. Для того чтобы (х„у') реализовала максимин, т. е. чтобы Р (х„у') = ппп Р (х„у) = шах ппп Р (х, у), У к а необходимо выполнение хотя бы одного из следующих условий: а) 0 = Р', (х„у') (х, — а) (х, — Ь) = = Ре, (ха У ) (У( с1) (У] йа) = ... =Рв (ха У )(Ум ела)(ущ ал)~ (208) б) существует У,Фу' такое, что ф !7! нзозходимык условия оптимлльяости 225 Как в случае (208), так и для (209), число уравнений равно числу неизвестных, и потому, вообще говоря, возможно определение х„, у' и у,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
