Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 49
Текст из файла (страница 49)
1-1 !'= 1 Эта система, очевидно, равносильна системе однородных уравнений ~ а1~ (и!ру) = О; 1 ( г, )~~ а;р, '= О (287) относительно неизвестных а, р1. Равенства ~а!ф — о 1=0 (1(Й) 1=1 из (286) означают, что у матрицы однородной системы уравнений (287) (288) между столбцами существует линейная зависимость < г ~!)!'=1 и, следовательно, хоть одно д~ >О, т. е. ее 1 ранг не превышает г ( я. Поэтому система (287) имеет нетривиальные решения (а;р)) и ( — а!рД при сколь угодно малых шах (а,'(=и.
!<!~А Выбрав а так, чтобы а Тпах ~~'. !а!ур7~( — (а(1), а>г>г+1! получим, очевидно, из-за (285) л ппп ~~ а!г(1 ~ а;) р7 > о+ †. (289) Рг>!>гь1 1-! 308 теОРемы О Решении литАГОиистических ЕГР (ГИ! Гч В то же время в силу (287) имеем А Л ХОГГ(1+а!) р7=О Х(1+а!)р1=1 Г=! 1=! ;~а! (1 — а;) р1=О, .~Я(! — а,') р1=1. !=! Г=! (290) Поскольку гпах ~ а,' ~ ( 1, очевидно, рГ!Г!=(1+а;) рг~ О, р,'"=(1 — а,') р,')О. Таким образом, (289) и (290) с учетом р,'=0 при ! > й означают, что системы Р!Ы=(р!'") и Р'*'= (р,'*') являются оптимальными стратегиями оперирующей стороны и в то же время (р!) =Ро=О 6Р! '+О 5Р! '. а это противоречит тому, что стратегия Р, крайняя.
При предположении г > й совершенно аналогично придем к противоречию с условием, что Я,— крайняя оптимальная стратегия противника. Итак, г=й. Пусть теперь о ~ 0; тогда вторая система в (286) означает, что в матрице (288), где уже й = г, последний столбец является линейной комбинацией остальных г столбцов. Если бы детерминант (291) был бы равен нулю, то какой-то из его столбцов был бы линейной комбинацией остальных г — 1 столбцов, а вместе с ним и последний столбец (288) был бы линейной комбинацией тех же г — 1 столбцов. Но тогда ранг матрицы (288) был бы не более г — 1, что при й=-г означало бы наличие нетривиального решения системы (287), а это опять привело бы к противоречию с исходным предположением, что Р,— крайняя оптимальная стратегия.
Итак, детерминант (291) отличен от нуля, как только О~О. Таким образом, вспоминая, что (286) получалось после некоторой перестановки строк и столбцов в исходной пла- $ 241 РЕШЕНИЕ МАТРИЧНЫХ ИГР 309 тежной матрице Еа(~~(, приходим к следующей теореме, принадлежащей Шепли и Сноу.
Теорема ХШ1. Все крайние оптимальные стратегии р, и Я, обоих игроков в игре с платежной матрицей ((а(Р~! и цена игры о должны удовлетворять какой-либо из систем уравнений: ~ р,'=1, (292) 1 ~~'; о,', = 1, (293) ~~'., а(ьчр,',— о=О; (=! з=1,...,г, где квадратная матрица й а;„(, й получена вычеркиванием некоторого количества строк и столбцов из матрицы йаы'й'. Все остальные р,' и ()Р( для (~(, и 1~1, должны быть равны нулю. Если цена игры о Ф О, то матрица (~ а(,((й должна быть невырожденной. Эта теорема дает, конечно, лишь необходимые условия для крайних оптимальных стратегий; среди решений (292) и (293) могут оказаться и неоптимальные стратегии и даже такие решения, когда не выполнено условие р~',) О или д,(е) О. Однако если это все выполнено, то решения уравнений (292) и (293) дают уже обязательно крайние оптимальные стратегии.
Доказательство этого имеется в книге Карлина. Мы здесь на этом малосущественном обстоятельстве останавливаться не будем, ибо этот факт не меняет необходимости перебора всевозможных систем (292) — (293). А если уж они все перебраны, то безразлично, все ли соответствующие оптимальные стратегии крайние или среди них есть и не таковые. Применение теоремы Х1.П на практике затруднено не только из-за необходимости перебора всех квадратных подматриц матрицы йа!.~(, но и из-за необходимости проверки оптимальности стратегий, т.
е. условий (285) (условия ре) О и о1)О затруднений, конечно, не вызывают). В связи с только что доказанным целесообразно остановиться на понятии вполне смешанной игры. Игра называется вполне смешанной, если в каждую оптимальную смешанную стратегшо каждого из игроков 310 ткогкиы о гкшкнии лнтлгонистичкских иге [гл. ш любая чиппая стратегия входит с положительной вероятностью. В такой игре все чистые стратегии существенны, и без потери эффективности ни одна из них не может быть выброшена. Раз во вполне смешанной игре все р; и а не равны нулю, то система (292) — (293) должна базироваться на самой исходной матрице [[ау[[ без вычеркивания строк или столбцов. Но тогда матрица [[а;.[[ должна быть квадратной, а при о~О еще и не вырожденной. Вполне смешанной игрой может быть только квадратная игра с невырожденной матрицей, если о~О.
Но если система (292) — (293) должна базироваться на [[а;~[[, то она единственна и потому единственны и крайние оптимальные стратегии сторон, как решения неоднородных систем уравнений с числом уравнений, равным числу неизвестных. Единственность крайней стратегии означает, конечно, и единственность оптимальной стратегии вообще. Вполне смешанная игра имеет единственное решение, т. е.
одну пару оптимальных смешанных стратегий сторон. Вполне смешанные игры являются как бы антиподами игр, имеющих седловую точку в чистых стратегиях. Примерами вполне смешанной игры могут служить игры с матрицами: 1. Матрица Минковского — Леонтьева.
ау(д при 1Ф1'; 1, 1 <п и с а > д)0, если еще л ~ч~ а; >ад>0; 1(1(п. 8=! 1!. Циклическая матрица. а, а, а, ... а„ , а„ , а, а, ... а„ , при [А[~0. а, а, а, ... а„ Доказательство имеется в книге Карлина. Несмотря на то, что теорема Х1.П выглядит исчерпывающим способом решения матричных игр, сложность такого З11 гашение метгичных иге решения заставляет искать и иные пути решения матричных игр. Целесообразно остановиться на связи решения матричных нгр с решением задач линейного программирования.
Согласно теореме ХХХ)Х решение игры состоит из двух задач: а) поиск Р, такой, что и е пип ч~Р а; ре= шах пип ч~~ ~а,ср =о; ! <с<и!с ! Р=(Рс) ! <с смс-! б) поиск Я, такой, что шах,Я асс!))=пип шах,~ ~ассс(с=о. !<с<!!с=! е !<с<и)=! Пусть аы) О, а значит, и о ) О. Этого можно всегда добиться, не меняя оптимальных стратегий добавлением ко всем элементам аы одной и той же достаточно большой величины. Вводя о(Р) = ш(п,~ Яас~рс !<с<и!=! о(('„)) = !пах ~ асСс)ср ! < с < !! с = ! можно записать первую задачу как стремление к максимизации величины и(Р) при условиях л е о(Р)~~,~ Яа;,Р;, /=1, ..., т, ~ч~, 'Рс=1; Рс)О. с=! с=! Введем новые переменные х = — .
Рс и(Р) ' Тогда, очевидно, имеем условия 1(~ а; х;; хс~~О. с=! л л Из связи же ',~ р;=1 получим =~~ хо Стрем!=! о(Р) ' ! ление к увеличению о(Р) ведет в новых переменных к и стремлению добиться минимума ~ хе с ! 312 теогииы о гишинии ннтлгонистичнских игг (гл, !ч Точно так же, вводя у;= дг, получим, что вторая й(Р) задача означает стремление к получению максимума ! Х у! = — при условиях н(д) 1> Х а!у,; у>О. 1=! Итак, всякое решение игры (Р„ (,),) при цене игры о дает в то же время решение укаэанных задач на экстремум для переменных х! и ур причем и ы ~н.; ху — ~чз, (ля !=1 1=! о Обратно, если имеются решения (х11 и (у11 указанных задач, причем ~ х,' = ~ у~ = —, то, очевидно, для !=! !'=! р)=охф д)=оу) имеем ч; р,.
= 1, ,'", д~ = 1, л~ н ~ч', а;удз<о<~~р~ а; р,'; 1<а, 1'<т. /=1 1=1 Но отсюда ппп~ а; р;')о) шах ~ агф, ! г=! ~ ! 1=! тогда и !пах ш(п~~'.~ агтр!) о) ппп шах,~, аддин ! ! ! о ! 1=! В силу теоремы ХХХ1Х все неравенства становятся равенствами, о оказывается ценой игры, а Р, = (рЯ и Ц, = (д)) — оптимальными смешанными стратегиями. Поскольку приведенные выше две экстремальные задачи для х; и ут являются ничем иным, как двойственными задачами линейного программирования, то получена З1й 5 241 РЕШЕНИЕ МАТРИЧНЫХ ИГР Теорема Х1.11!.
Решение матричной игры с платежной матрицей)~аД при ! (и; /(т эквивалентно решению двойственных задач линейного программировании: ппп ~~'., х/ при х/ р= О, 1=1 и .~! ~,/~1) 1; 1=! /=1, ..., т; /пах Р; у/ при у )О / ! ~.', а/.у ( 1; ! = 1, ..., и. !/ / В ° Ф 2) и и и ппп Р,' а; р;= ш1п~ —,~, а//р/~ = — шах.~'„а//р/= / 1=1 / 1=! / 1=1 = — шах ~' а;,р =" — !тип шах ~ч, а; р = — о. — 1Р/) Ценой игры о является величина, обратная общему ЗНаЧЕНиЮ ОПтиМаЛЬНЫХ,~ ~Х/и=,~ УЧ/= —, а ОптиМаЛЬНЫЕ /=! р', и д~ связаны с оптимальными значениями х,' и у/ч связями ру=охи, у~=ау).
Согласно атой теореме решение матричных игр в смешанных стратегиях сводится к решению некоторых частного вида двойственных задач линейного программирования и, значит, может быть получено методами линейного программирования. Однако, и обратно, любая задача линейного программирования может быть сведена к решению некоторой матричной игры. В общем случае любая задача линейного программирования сводится к так называемой симметричной игре. Матричная игра с платежной матрицей А =~(а//а называется симметричной, если матрица А кососимметрична, т. е.
если а// — — — а/о Симметричные игры обладают следующими свойствами. 1. Цена симметричной игры равна нулю. Действительно, 314 теОРемы О Решении АнтАГОнистических НГР (Гл. !ч Но из-за произвольности (рГ) в левой части следует о= Гпахппп ~ч~ а;,рГ( — о, (в) т. е. 2о (О. Точно так же и наоборот: Гпах ~~'., а, Н11 — — — ппп ~ аГ л11 ~ )— Гпах ппп,~~ а; д; = — о, С 1=1 ! 1=1 () ' '=' и благодаря произвольности (д ) о=пни гпах ~~' а;~д~) — о (ю) 1 1=1 и 2о ) О. Таким образом, о = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
