Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 50
Текст из файла (страница 50)
П. Если (рЦ вЂ” оптимальная стратегия оперируГои4ей спюроны в симметричной игре, то такая же стратегия оптимальна и для противника. Действительно, из определения оптимальной стратегии оперирующей стороны и О=О следует, что ~аГ р11)0 при 1(1(п. 1=1 Но тогда отсюда ~ аГ рч = —,'5, 'амрАГ ( 0 /=1 ' ' 1=1 шах „~ ~с1х; (Л '=' (294) при любых 1(п. А зто и означает, что (рЯ есть оптимальная стратегия противника. Пусть теперь даны произвольная матрица А=(~а;~)~ (1(1«п; 1(/(т) и двойственные задачи линейного программирования: 315 $241 РЕШЕНИЕ МАТРИЧНЫХ НГР при условиях х)>0; ~~р~архг(Ь~, 1=1,..., и. 1=1 пи(п ~ ~ЬТуо'.
(Р1) '=' (295) при условиях у1>0; ч.",аочу1>со 1=1, ..., т. ' !=1 Образуем квадратную кососимметрическую матрицу оо о 0 ... 0 — а„...— а„, с, 0...0 — а, ...— а„ с„ — Ь„ 0 (296) 0 0 Ь,... а„...а„ 0 Ь„ а„,...а„ вЂ” с ...— с Здесь числа т, и, 1 показывают число строк и столбцов в подматрицах матрицы В. Обозначим, далее, через (х, ... х , у, ... у„, Ц =г смешанную стратегию в симметрйчной игре с матрицей В.
Теорема Х1.1Ч. Решение двойственных задач линей- ного программирования (294) и (295) эквивалентно реше- нию симметричной игры с матрицей В. Точнее, если г,— оптимальная стратегия в игре с матрицей (296) и при етом )оо >О, то х; = —, и у!= —, дают решение задач (294) и (295).
Наоборот, если х; и у! — решение (294) и (295), то ! ВЕЛиЧМНЫ )1о Хо )ооХ1 уч Аоу' Обри 1+ ~» хо + ~~ У1 1=1 1=1 зуют оптимальную смешанную стратегию (х,', ..., х", у'„..., у„", )оо) в игре с матрицей (296). Д о к а з а т е л ь с т в о. Пусть г,— оптимальная страте- гия для игры (296), имеющая )оо > О. Поскольку эта игра симметрична, то г, оптимальна для обоих противников и о=0, 316 теогемы о гешнннн лнтлгоннстнчнскнх нгг [гл.
/ч При применении оперирующей стороной эта стратегия дает ~ а//у/ — с/Х' ) О; 1 < / < т, 1/ т при первых т чистых стратегиях противника. При и чис- тых стратегиях противника из второй группы имеем л~ — ~~.", а//х)+ Ь/)Р Ъ О; 1 (1 < п. Наконец, при применении противником последней чистой стратегии (поскольку она входит с положительной вероят- ностью Р в оптимальную смешанную): гл л ч~~ ~с/х/ — ~~'„, Ь/у3 = О.
/=1 /=г х[ Деля все эти соотношения на Р > О и вводя х,'= — „,; о У/ у; = —, имеем ур ' н м %1 %'1 да/ у/)с/, '1(т, г а; х;(Ь;; /(и, /=г /=г ~а н ~ с,х/ = ч~'' „Ь;у/. (297) / ~ /=г Первые две системы неравенств показывают, что (х/) и (у/) удовлетворяют условиям задач (294) и (295), т. е. являются допустимыми векторами в этих задачах. Для любого допустимого вектора (х;) задачи (294) в силу допустимости (у/) и последнего равенства (297) имеем П$ гп/ л х,"~( х(х,а) "~= /мт 1=1 /=1 и/м Ъ л ги = ч~',~~ ~ч'.,а/ х/) у/ ( ~~Р~Ь/у; = ~~~~с/х/. /=Г /=Г 1=1 ' /=1 Но это означает, что шах г,'с/х/=,~~с/х/. Я/ 1 /мт 1 81т ф 24] РЕШЕНИЕ МАТРИЧНЫХ ИГР Аналогично и пцп ~~„','Ь/у/ — — .~~Ь/у/. 1=1 Отсюда и следует, что (х/) и (у/) являются решениями соответственно задач (294) и (295).
Обратно, пусть (х,'.] и (у;) — решения задач (294) и (295) линейного программирования. Положим 1 Ло хл — Ллх' /' 1+ХЕ/+ Ху/ гл = (х,'... х", у ... ул, Лл). или после умножения на Лл О~ л Ус/ 1 — 1'„',Ь/у) = О. /=1 1=1 (298) Кроме того, л О$ ~~~ а//у/:) с/, ~ а//х,' < ЬР /=1 Умножая на Л' и перенося все величины в левые части неравенств, получим 1</<ш, 1«'<и. ,~~а//у,' — с Лл =НО; 1=1 — У а//х] + Ь/Лл ) 0; /=1 (299) Но (298) и (299) в совокупности означают, что применение оперирующей стороной стратегии г' гарантирует платеж, не меньший нуля, при любых чистых стратегиях Очевидно, что ~х]+ ~!у/'+ Л'=1.
Далее, в силу /=1 =! ' теоремы двойственности линейного программирования М л Ус/х/' = ~~'„Ь/у/ !.=1 ' 1=1 318 тзогемы о гашения лнтлгонистических иге [гл. ш противника в игре с матрицей (296). Поскольку последняя игра симметрична, то ее цена равна нулю, а потому стратегия г', обеспечивая платеж, не меньший цены игры, есть оптимальная стратегия. Этим и завершается доказательство.
Последние теоремы позволяют применять методы линейного программирования в теории игр и наоборот. Однако эта связь, впервые обнаруженная Данцигом и фон Нейманом, не имеет никакого отношения к поиску наилучших чистых гарантирующих стратегий, максиминов и минимаксов в чистых стратегиях. Эти задачи, как и точное решение непрерывных игр, являются пока самостоятельной трудной проблемой.
2 25. 0 численных методах решения матричных игр ц(Р)=~р(р„..., Р„)= ппп ~~ а;,.р; (300) д«г«т ы =1 при условиях р; ) О, ~ р;= 1. Этот максимум и есть цена ~=1 игры. Аналогично оптимальная смешанная стратегия противника определяется как реализующая минимум функции ф(Я)= шах ~~~ а;,д,; 1«$«И г=1 т [,>0, ~д,=[. /= г (301) Доказанные в $24 теоремы о связи задачи решения игры в смешанных стратегиях с решением задач линейного программирования позволяют пользоваться для решения игр численными методами, разрабатываемыми в линейном программировании, и обратно.
Не останавливаясь на численных методах линейного программирования, излагающихся в многочисленных книгах, перейдем к рассмотрению других возможностей. Прежде всего, из теоремы ХХХ1Х следует, что задача определения оптимальной смешанной стратегии оперирующей стороны эквивалентна следующей задаче. Определить максимум функции з 251 о чнслвнных мнтодвх гашения матгнчных нгг 319 Выражая рл и дл через другие переменные, приведем эти задачи к виду 1. Определить максимум функции (а в 1)-го переменного 1л-1 ГР1(Р„..., Рл,)лл ГП(П ~ ~Р ~(а; — ал )РГ+ал (302) 1<1<л1 в области, определяемой неравенствами л — 1 р,)0, .... р„, в0; ~р,(1.
(303) 1 1 2. Определить минимум функции (и — 1)-го переменного 1и-1 1Р (д1, ..., д )= птах ~ ~2'~(а;у — аг )Цу+аг (304) бегал в области д1)0, ..., ~)„1>0; ~.", д (1. (305) Для характеристики задач (300) — (301) и (302) — (305) остается отметить, что, как показано ранее, функции ф(р) и 1р,(р„..., рл,) вогнуты, а ф(9) и ф1(дг, ..., д 1) выпуклы.
Области (303) и (305), очевидно, выпуклы, ограничены и замкнуты*). Вогнутость <р1 и выпуклость тр1 обеспечивают совпадение локальных максимумов (минимумов) с максимумами (минимумами) в целом. Таким образом, получаются удобные условия для применения любых численных методов поиска экстремумов, например, градиентного метода и метода случайного поиска. Для применения второго нет вообще никаких препятствий; что же касается первого, то здесь необходимы уточнения в связи с видом функций 1р, и ф„ являющихся кусочно-линейными. Определение градиента ГР1 ДОЛЖНО ПРОИЗВОДИТЬСЯ В КажДОЙ ТОЧКЕ (Р„..., Рл,) л-1 длЯ фУнкции,Я (аи,— ал;,)Рг+аля пРи том значении 1„ для которого в рассматриваемой точке достигается значе- /Л вЂ” 1 ние ппп ~~~.",(аы — а„у)р1+а„у . если эта точка не лежит 1~1~а 1=1 л) Таким оправам, сформулнрованпые задачи есть задачи вогнутого н выпуклого программирования.
320 теОРемы О Решении АнтАГОнистических иГР 1ГН. !у на краю линейного куска ~р„то все получается просто. На краях 1, заведомо не единственно и потому не ясно, как определить направление на следующую точку в процессе поиска экстремума; к тому же здесь вообще нет производной. Однако эта трудность несущественна. Во-первых, попадание точно на край маловероятно. Во-вторых, чтобы продолжить движение, здесь можно взять любую из 1, (например, первую из таких 1,), реализующих указанный выше минимум, и для него определить градиент, и, значит, следующую точку поиска экстремума.
Таким образом, градиентный метод вполне может быть реализован. Следует заметить только, что при желании можно и на краях легко получить точное направление наиболее крутого подъема, воспользовавшись тем, что для ГрГ и на краях есть производная по всем направлениям. Эта производная легко определяется по теореме ХХЕ'П1, вполне применимой к данному случаю, несмотря на дискретность переменной 1, выполняющей здесь роль вектора у этой теоремы.
Таким образом, может быть точно определено направление наибольшего подъема во всех точках области (303). Аналогично обстоит дело и для ~РГ. Перейдем к описанию специфического для теории игр итеративного численного метода нахождения цены игры и оптимальных смешанных стратегий. Идея метода предложена Брауном н состоит в следующем. Пусть дана матричная игра 'йа;,ф 1<Г<п, 1<1(т. Рассматривается бесконечный процесс повторения этой игры, при которой каждый из игроков каждый раз предполагает, что противник выберет смешанную стратегию, определяемую частотами появления чистых стратегий в прошлых повторениях, а сам выбирает чистую стратегию, обеспечивающую наилучший результат при таком положении. Пусть уже сделано й повторений игры, в которых первый игрок выбирал чистые стратегии 1„..., ГА, а второй— 1ы ..., 1А.
Тогда на й+1-м повторении первый игрок предполагает, что второй выберет с равной вероятностью любую из 1„..., 1А, а это эквивалентно ранее сказанному о частотах появления чистых стратегий, поскольку з 251 о часлвннмх нвтодвх гвшвння нвтгячнмх ягг 321 (307) Тем самым ои как бы не вполне доверяет этой последней информации, считая равновероятным у первого игрока как выбор стратегии (в+„так н всех предшествующих. Чтобы закончить описание этого процесса, нужно определить выбор стратегий в первой игре. Во втором варианте процесса 1, выбирается произвольно, а 1, в соответствии с (308) в виде аа?. 11 ю.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
