Беклемишев - Дополнительные главы линейной алгебры (947281), страница 71
Текст из файла (страница 71)
Таким образом, первый игрок заинтересован в выборе макси)лального элемента матрицы, а второй — в выборе минимального ~лемента. В соответствии с этим первого иногда назьвают максимизирующим игроком, а второго — минимизирующим. 5. Гарантированные выигрыши. Представим себе в роли первого игрока очень осторожного человека, который не хочет рискоВать, а хочет получить, если это возможно, хоть и не самый большой, 5 5 ПРИЛОЖЕНИЯ ЛИНЕННОГО ПРОГРАММИРОВАНИЯ 3!9 но зато гарантированный выигрыш, не зависящий от действий второго игрока. Первый игрок может рассуждать так: «В самом худшем случае мне достанется самый маленький элемент из выбранной мной строки.
Поэтому следует выбрать ту строку, в которой самый маленький элемент максималенм Итак, пусть ! = 1, ..., т, а 1 = =-!,...,п,н аьь = гпах пни а;/. Выбран стратегию !'„первый игрок ие может получить меньше чем а,„,:,', что бы ни выбрал второй игрок. При других стратегиях он может получить и меныпе чем а;„„и больше, но это зависит от действий второго. Однако если второй действует осторожно, первый не может получить больше некоторого предела, который мы сейчас установим.
Число шах ппп а// называется гаранп/ироааппым выигрышем перного игрока. Число — шах пнп а, является верхней границей / выигрыша второго игрока, боль.пе которой при осторожных действиях первого игрока он получить не может. Проведем аналогичные рассуждения за второго игрока. Для получения гарантированного выигрыша он должен выбрать тот столбец, в котором самь!й большой элемент будет минимальным, т. е. столбец с номером /!, для которого аьь = пп'п !пах а,/. / ! При стратегии /! второй игрок получает гарантированный выигрыш, равный — ппп шах а».
Одновременно мы получаем, что число / / ппп !пах а» является верхней границей выигрыша первого игрока, / с больше которой он при осторожных действиях второго игрока получить не может. Установим, как связаны между собой гарантированные выигрыши игроков. Нетрудно доказать, что обязательно !пах ппп а// ~ ппп шах а». с / Это означает, что всегда верхняя граница выигрыша не меньше, чем гарантированный выигрыш. Действительно, рассмотрим столбец /и, составленный из элементов р, = пнп а;/.
Каждый из элемен/ тов этого столбца не больше соответствующего элемента любого другого столбца: р!=- -и», 1' = 1, ..., и. Если й-й элемент столбца 1/ является наибольшим, то для всех 1'=1, ..., и верно шах р, = р« ( а«/ ( гпах и//. В20 гл. м систВмы нВРАВВнстВ и линенноа пРОГРАммиРОВАнив Поскольку р„не больше каждого из п чисел, то оно не больше ми- нимального из них: гпах р, ( пип шах а!!. ! ! ! Это совпадает с доказываемым неравенством.
Игры, в которых выполнено равенство гпах пип а!! = пип шах а!г, ! ! называются вполне определенными. Если ап!, — тот элемент, кото- рый равен обеим частям этого равенства, то, выбрав стратегию 4,. первый игрок получает свой гарантированный выигрыш, который одновременно является и его максимальным выигрышем при осто- рожной игре второго игрока. Это — большее, на что он может рассчитывать. Точно так же второй игрок выбирает стратегию !А и вьигрывает — ап!,. Это верхняя граница выигрыша при пра- вильных действиях первого. Если ни один из игроков не рассчиты- вает на оплошность другого, то результат игры определен, с чем н связано название этого класса игр. Стратегии !, и !, называются чистьиии оптичальньши сгпра!пе- гиями.
Рассмотрим в качестве примера игру с матрицей !!~ ~!! Ясно, что первому игроку следует выбрать вторую строку, а Второму, если только он не надеется на ошибку первого, нужно выбрать первый столбец. Положение меняется, если мы перейдем к игре с матрицсй !>2 4!!' Эта игра уже не будет определенной, так как шах ш!п ац = 2, ! а ппп шах а! — — 3. Стремясь получить свой гарантированный ! ! выигрыш 2, первый игрок должен выбрать вторую строку.
Если при этом второй игрок, также рассчитывая на гарантированный выигрыш — 3, выбирает первый столбец, то он получает больший выигрыш, равный — 2. При таких стратегиях первый игрок явно в невыгодном положении: он мог бы получить 3, если бы, надеясь на осторожность второго, выбрал первую строку. Тогда второй получил бы только гарантированный минимум. В этой игре, как мы видим, нет чистых оптимальных стратегий, гарантированно даю- щих наилучшие возможные при правильной игре обеих сторон ре- зультаты. 6, Смешанные стратегии.
Рассмотрим игру, для которой а!,!, = !пах пип а,! ~ пип шах а!! = а!,ь. ! !' ! 5 а пРилОжения линеинОГО пРОГРАммиРОВАния ЗЯ1 До сих пор мы предполагали, что игра играется один раз. Прн этом предположении для рассматриваемого случая дальше продвинуться не удается. Будем считать, что игра повторяется многократно. Если при многократном повторении игры первый игрок будет постоянно выбирать стратегию 1м то второй игрок, рассчитывая на это, будет выбирать стратегию 1'„и первый будет получать аьь. Если же первый неожиданно выберет стратегию ~'„то выигрыш его будет равен аьь, причем аьь" аьд ) аьь.
Однако если он будет продолжать выбирать стратегию 1П то второй заметит это и оставит ему выигрыш пнп аьп не больший, а вообще говоря, меньший чем ацн. Правильное решение игрока в ие вполне определенной игре состоит в том, чтобы выбирать стратегию случайным образом так, чтобы противник не мог предугадать, какая стратегия будет выбрана в следующий раз. При правильном выборе стратегий и их вероятностей такое решение позволяет поднять средний выигрыш выше, чем шах нйп ау, хотя и не доведет его до ппп шах ау.
/ / Допустим, что стратегия 1 применяется первым игроком с вероятностью х', 1 = 1, ..., и, а стратегия / применяется вторым игроком с вероятностью у~, 1' = 1, ..., и. Естественно, что х' ~ О, х'+... + х" = 1 и у О, у'+".+у"=1. Выигрыш первого игрока теперь — случайная величина, математическое ожидание которой нетрудно подсчитать.
Так как стратегии выбираются независимо, вероятность выбора пары стратегий 1, 1 равна х'у~, а значит, математическое ожидание величины выигрыша первого игрока есть г (х, у) = .у, 'пух'уу ьг или, в матричной форме, хгАу. Столбцы х = 1х", ..., х" 1г и у =!!у', ..., у" Г мы назовем смешанными сглрааегиями первого и второго игроков, а стратегии, рассматривавшиеся выше, в отличие от смешанных, будем называть чистыми. Чистые стратегии можно рассматривать как смешанные стратегии, определяемые столбцами единичной матрицы.
Геометрически мы можем представлять себе чистые стратегии как базисные векторы в гп-мерном (или соответственно а-мерном) пространстве, а смешанные стратегии — как выпуклые комбинации чистых. Все множество смешанных стратегий„найример, йервого игрока изображается выпуклой оболочкой гп точек в гп-мерйом Зкз ГЛ. М СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕЯНОЕ ПРОГРАММИРОВАНИЕ аффинном пространстве, причем эти точки не лежат ии в какой (т — 1)-мерной плоскости.
Такое множество — простейший т-мерный многогранник — называется т-мерным симплексом. Исследуем, чего могут достигнуть игроки, если они будут при. менять смешанные стратегии. Если первый игрок выберет стратегию х, то он может быть уверен, что его выигрыш будет не меньше чем пип хгАу. У Этот минимум существует, так как функпия хгАу при фиксированном х непрерывна на замкнутом ограниченном множестве значений у. Поэтому гарантированный выигрыш первого игрока прн применении смешанных стратегий не превосходит зпр пип хгАУ. к Аналогично, при выборе стратегии у второй игрок выигрывает не меньше — шах хгАу, и потому при его правильной игре выигрыш первого игрока не превосходит 1п( гпах хгАу.
3 к Ниже мы увидим, что эти верхняя и нижняя грани достигаются и, следовательно, являются максимумом и минимумом, а пока отметим только, что выполнено неравенство пипхгАу ~ енр лип хну =а~!П(шах х~Ау ~шах х Ау. (8) У к у к В доказательстве здесь нуждается только средний знак неравенства. Очевидно, что при любых х и у выполнено ш1пхгАу т;хгАу~гпаххгАу. У к Так как правая часть этого неравенства не зависит от х, имеем епр ш(пхгАу ~ шах хГАу. У к Но в этом неравенстве левая часть не зависит от у. Поэтому енр пил х ГАу ~ (п( шах хгАу.
В действительности здесь обязательно имеет место равенство. В этом заключается основная теорема теории матричных нгр, котй. рую мы ниже докажем. Но сейчас для доказательства формулы (8) полученного нами неравенства достаточно. Докажем еще, что при любом х выполнено пйп „'Я а~ф ~ пт(п г (х, у). .1 э 6, пРиложения линеинОГО пРОГРАммиРОВАния 823 Действительно, по определению г (х, у) имеем ~(х, у) .„У,ус,Яас~хс.
с с Если мы заменим каждую внутреннюю сумму на наименьшую из них, мы получим неравенство с (х, У) ~ Д Ус') сп1п Р, аух' = пип Я ассхс. ) с Это верно при всеху, в частности при том, на котором достигается ппп с' (х, у). Этим требуемое неравенство доказано. Аналогично Р доказывается, что Гпах У, 'ауУс "» шах ~,' ассх'УС М 7. Применение линейного программирования. Из доказанных нами неравенств видно, что, выбрав стратегию х, первый игрок может быть уверен, что его выигрыш будет ие меньше чем о = пнп ~ ассхс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
