Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 31
Текст из файла (страница 31)
Уже при одномерных векторах имеется три возможности, выражающиеся шах ш!ПР(х, у), ппп шаху(х, у) и максимином при иск у у к пользовании смешанных стратегий. В многомерном же случае, как видно из (!84), вариантов возможной взаимной информированности не меньше, чем способов разбиения векторов х и у на системы векторов х; и у~. Поэтому необходимо ограничивать число исследуемых вариантов, используя любые, даже интуитивные соображения. Однако во всех случаях необходимо провести определение г,', г, и г, и соответствующих оптимальных стратегий, как основных, наиболее простых вариантов, дающих общее представление о ценности информации в данной ф 1$) ПОНЯТИЕ ОНТИИЛЛЬНОй СТРАТЕГИИ 185 операции.
Определение Ц„и Ц, даст возможность как-то определить направленнедальнейших исследований, а в случае наличия седловой точки и вообще закончить их. Стоит не забывать также, что при любом разбиении х и у на х« и у; результат (184') всегда заключен между Р,' и Р,. Это следует из всех материалов раздела илн может быть получено с помощью многократного повторения (160), если вспомнить, что Р', = шахпнпР(х, у)= х«Меу«К = шах ... шах ш!и ... тп!и Р(х„..., у»), х,«М, хх«М»у,«М, у»«И» Р,= ш1п ...
ппп шах ... шах Р (х„..., х», у„., у»), у«Т«, у»«М»х,«М, х»«М» и начать постепенно переставлять между собой шах и ппп. Полезно проводить и сравнение Р„' и Р, с соответственно абсолютным минимумом Р„=ппп Р (х, у) и максимумом Р„= шахР (х, у) критерия эффективности. Так, если окажется, что Р', близко к Р„, то оптимальная из М, стратегия практически ничего не дает по сравнению с любой другой.
Следовательно, для того, чтобы добиться успеха, необходимо бороться за информацию или расширять множесто М, возможных стратегий. Если же, наоборот, Р, близко к Р„, то следует ожидать от разумного противйика (если он есть) аналогичных мероприятий по изменению ситуации; если же Р„'близко к Р„, то, значит, неопределенные факторы в операции не существенны и их можно далее не варьировать.
Если разумного противника в рассматриваемой операции нет, а неопределенные факторы есть, то имеем так называемую игру с природой. С развиваемой здесь точки зрения отличие этой ситуации состоит только в том, что природа не может иметь информации о выборе стратегии оперирующей стороной. Поэтому максимин здесь несколько перестраховочен и целесообразно, вобще говоря, применение смешанных стратегий и стремление к получению информации о выборе «хода» природы. Основным 186 1гл.
п1 оптин»льныз ст»лтвгии оптимальным гарантированным результатом здесь обычно считается наилучший гарантированный результат при применении смешанных стратегий. Однако если применение смешанных стратегий лишено смысла, то приходится вновь возвращаться к максимину в чистых стратегиях и отсчитывать ценности информации о природе от него.
В заключение раздела остановимся на возможности появления в исследовании операций «некорректных» задач. Прежде всего все задачи без седловой точки часто считаются «некорректными», потому что не определяют устойчивых, относительно вариации информированности, оптимальных стратегий. Однако последовательное применение гарантированных оценок, применение смешанных стратегий и фиксация точного варианта информированности позволяет избежать всех возникающих принципиальных затруднений и создать устойчивое понятие оптимально наилучшей гарантирующей стратегии. Таким образом, здесь имеется лишь видимость некорректности, что связано с недостаточно четким пониманием оптимальности. Но можно сформулировать и модели с совершенно неустойчивыми решениями.
Дадим простейший пример. Пусть имеются два противника, производящие одну и ту же продукцию из одного и того же сырья. Пусть первый, имея количество сырья х, производит продукцию в количестве й,х, а второй, имея сырье у, производит продукции й,у. Пусть первый стремится максимально превзойти второго, т.
е. максимизировать критерий эффективности й,х — й,у; второй пусть стремится к противоположному. Эту простейшую антагонистическую игру осложним наличием связи х+у~с, показывающей, что общие запасы сырья ограничены. Ясно, что никакого компромиссного или гарантирующего решения эта задача не имеет; все решается тем, кто из противников первый сделает «ход» и захватит все сырье, т. е.
сделает х=с или у=с. В первом случае операция закончится с результатом й,с, а во втором — й,с. Здесь невозможны смешанные стратегии и ничего не дает информация; нужно только во чтобы-то ни стало опередить противника. 187 $ 151 ПОНЯТИЕ ОПТИМАЛЬНОЙ СТРАТЕГИИ Нетрудно увидеть, что такие «некорректные» антагонистические модели имеют достаточно прямое отношение к некоторым практическим ситуациям.
Разумные организаторы «игр» должны избегать подобных ситуаций. В игре с природой такие ситуации, по-видимому, невозможны. Причиной появления «некорректных» моделей, очевидно, является связь между «запасом» М, стратегий оперирующей стороны и стратегией противника у. Так, в приведенном примере, если противник первым делает «ход», то М, есть отрезок 10; с — у1, а если первой делает «ход» оперирующая сторона, то Ф= 10, с — х). В более сложных случаях связь между М, и у можем конечно, оказаться и не такой, что некоторый выбор у сводит М, к нулю. Однако во всех случаях связь эта затрудняет корректную постановку задачи *).
Таким образом, в исследовании операции, а также, видимо, и в жизни следует избегать антагонистических ситуаций с сильно связанными между собой множествами возможных стратегий М, и У. Второго рода неопределенность задачи может возникнуть в «противоположном» случае„когда оба противника уступают друг другу право первого «хода», рассчитывая получить и использовать информацию об этом «ходе» для увеличения результата операции в свою пользу.
Именно так получится, если оба противника выберут в качестве стратегии функции х(у) и у (х) поведения другого игрока, неприводящиеся к постоянной ни по одной координате. Тогда значения х и у никак не определяются, а, значит, не определяется и величина критерия эффективности, т. е. результат операции. Во всех рассмотренных выше случаях этого варианта не было, потому что предполагалось, что один из противников начнет игру, т. е. назначит х и у, или хотя бы какуюто часть этих векторов (например, х, в (184)). Выше, в (163), мы всегда полагали, что у Е У будет конкретизировано. ') Легко показать, что ситуации указанного типа могут быть приведены к случаю независимых Ме н У, но при агом интересы станут выражаться критернамн, принимаю«ними и бесконечные вначеаиа.
188 [гл. ш оптик»лънык стглткгии Излагавшийся подход всегда предполагает, что начало (пусть в виде выбора функции) за оперирующей стороной, ибо она и хочет провести операцию. После этого в модели противник обязательно делает «ход», приводящий к определенным результатам операции. Модель, правильно отражающая практику, должна давать оценку всем ситуациям, которые считаются возможными, и ставить им в соответствие значение критерия эффективности; ситуации, которым не соответствует значение критерия, находятся за пределами действия данной модели — учет их возможности требует ее изменения.
Так, скажем, всякая модель военных действий исходит из того, что кто-то их начнет. В такой модели не оценивается смысл начала военных действий. Для того чтобы рассматривать и отсутствие военных действий, т. е. продолжение мира, нужно создать модель с критерием, оценивающим полезность для оперирующей стороны отказа от начала военных действий (если, конечно, противник их не начнет) или от их продолжения. Итак, в исследовании операций нужно избегать пока связи М, и у и не рассматривать множеств стратегий противников, в которых есть пары, не обеспечивающие проведение операции, т.
е. определения ее результата— величины критерия эффективности. Последовательное проведение в жизнь осторожных оценок эффективности, разрешающих противнику применение всяких, но конкретизирующих результат стратегий, позволяет, видимо, избежать ситуаций второго типа. 5 16.
0 седловых точках Объяснение названия «функция с седловой точкой» для Р (х, у), удовлетворяющих условию шах ш!п Р (х, у) = гп[п шах Р (х, у), к у » у заключено в следующей теореме. Т е о р е м а ХЧ! !!. Для того чтобы Р', = шах [и! Р (х, у) = .«у = пппзцр Р(х, у) =Р„необходимо и достаточно суп[эст- у 189 ф 161 о седлоных точках еоеание пары точек х, и у„уля которых пип Р (х„у) = Р (х„у,) = щах Р (х, у,). (186) еен «Еме При згпом Р (х„у,)=Р,=Р„а х, н у, есть наилучшие гарантирующие стратегии сторон, т.
е. реализующие максимин и минимакс*). Доказательство. Достаточность. Пустьсущесгвует (х„у,), удовлетворяющая (186). Имеем всегда !п1 Р (х, у)(Р(х, у,), аен н поэтому зпр !и! Р(х, у)( щах Р(х, у,)=Р(х„у,). «е М,уеу «Е Ме Но пип Р (х„у) = Р (х„у,). фен Поэтому зир 1п! Р (х, у) = тпах !п! Р (х, у) = Р (х„у,). (187) «е М,еем «Еме аем Далее, зпр Р (х, у) ) Р (х„у), «Еме !п1 зпр Р(х, у)) пипР (х„у) =Р(х„у,).
еех«ем Но зпр Р(х, у,)= щах Р(х, у,)=Р(х„у,). «ЕМ« «ЕМе Отсюда !п( знр Р(х, у)= пип зпр Р(х, у)=Р(х„у,). (188) еен«еме вене «Еме ") у опредеажтся как стратегия, реализующая максимки для — Р (х, у), т. е. минимакс для р (х, у). Таким образом, аир Р (х, у) = = пип зор Р (х, у)=ге. Отметим, что в сформулированном виде вта у « теорема доказана Н. Н. Воробьевым. 190 !гл. ш ОПТИМАЛЬНЫЕ СТРАТЕГИИ Из сравнения (187) и (188) следует справедливость утверждения. Необходимость.
Пусть х,— стратегия,для которой ш( Р (х„, у) = шах ш( Р(х, р) = Р„, у уу АГ в у Мв у у М а у, †стратег противника, для которой зцр Р(х, д,)=ш!и зцр Р (х, у)=Р„. «у Мв уУАГАЕМв Имеем Р, = зцр Р (х, у„) » )Р (х„у„) ) !п( Р (х„, и) = Р,. ууМв Но по условию Р„=Р„', и, следовательно, Р (х„, у,)=зцрР(х, у,) = !п( Р(х„, у). УЕМв уЯАГ А это означает, что верхняя и нижняя границы достигаются в точке (х„, у„), т.е.
зцр и !и! можно заменить на шах и ппп, после чего выполнение (186) для х,=х„ и у, и у„полностью доказано. Если х и у — скаляры,т.е. Р(х, у) — функция двух переменных, то в точке (х„у,) она имеет в силу (186) вид седла, возрастая от (х„у,) в обе стороны по оси у и убывая в Обе стороны по оси х (если, конечно, (х„у,)— внутренняя точка).
Если есть только равенство зцр !п! Р(х, у) = ш! Ецр Р(х, у) = Кчьоо, уууМ увАВ увАГ ууМ т. е. верхние и нижние границы не достигаются, то на М х А! нет седловой точки, но такая точка, очевидно, существует на надлежаще дополненных М, и! и Р(х, у) (может быть, с включением бесконечно удаленных точек). Достаточно на фиктивной паре точек (х, у„) положить Р (х„, у„) = Р (х„, у) = Р (х, у„) = К. Именно поэтому ранее мы и сохранили термин функции с седловой точкой (обобщенной) в этом Общем случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
