Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 57
Текст из файла (страница 57)
Как мы уже знаем, выпуклыми оказались платежи во второй, четвертой н восьмой моделях. Но линейный платеж в первой модели тем более выпукл. То же относится и к платежу (328) в задаче о выборе оптимального времени включения дублирующего элемента (см. 3 26). Анализируя эти примеры, видим, что выпуклых платежей можно ожидать в операциях, где целью является улучшение величин типа точности или же линейных критериев, типичных для экономики. Но ведь отсюда следует, что в большинстве задач, решаемых в настоящее время, например в экономике и автоматическом управлении (критерий — точность), следует ожидать игровых задач с выпуклыми платежами и, значит, оптимальных чистых стратегий. Не поэтому лн смешанные стратегии пока еще мало используются на практике? Не создалась ли уже поэтому привычка к использованию только чистых стратегий, переносимая без достаточных причин и на операции с не- выпуклыми платежами? Дадим один пример применения развитой теории игр с выпуклыми платежами к классической математической задаче, который должен продемонстрировать еще раз пользу рассмотрения выпуклых игр.
Речь идет о модели гй 2, приводящей к известной задаче Чебышева о наилучших приближениях функций полиномами. й 281 пггы с выпуклой платежной вкнкцпяй 363 = — ппп гпах 1)(1) — ~агР а [,) ежгжт ~ г=е (362) В силу выпуклости и )а Р (1, а) =- 1(1) — ,'У, 'а;уг~ г=е (363) по а задача об отыскании минимакса (362) эквивалентна ") (см. теорему Х1Ч) задаче об отыскании седловой точки и цены игры с платежом (363). Согласно той же теореме Х1Л оптимальные смешанные стратегии сторон в игре (363) будут иметь следующий вид.
1. Для оперирующей стороны, выбирающей а, оптимальна чистая стратегия. 2. Для природы оптимальна стратегия, состоящая не более чем из и+2 чистых стратегий 1у (1 =1, ..., и+2). Пусть ру есть вероятность примейения стратегии тогда платеж при применении любой такого типа ч) В теореме Х).Ч множества стратегий ограничены. Легко уоеднться, что векторы о прн фиксированной 1(г) всегда можно счвтать ограннченнымн, не меняя мнннмакса. Как уже говорилось, отыскание полинома Р„Я =,У, 'а,)г, г=о наилучшим образом аппроксимирующего функцию 1(1), при критерии %'= — ~ Я) — Р„(1)~ и наличии природного неопределенного фактора 1 с множеством У = [О; 11 равносильно решению задачи об определении |пах ппп [ — ')[Я вЂ” Р„(1) Ц = — гп!п гпах [)'(1) — Р„(1)[. (а;)о<г<1 ( а,.
) о < г < ~ Последняя запись и соответствует задаче Чебышева. Согласно теореме ЧП1 без изменения оптимального выбора Р„Я критерий эффективности — ~ [ Я вЂ” Р„(1) ~ может быть заменен на )Р, = — [1(1) — Р. (1)1 . (361) Таким образом, нужно получить оптимальный Р„(1) (или а= [а„..., а„)), реализующий шах ппп [ — [у(1) — Р„(1))а) = — ппп шах [)'(1) — Р„(1Ц'= а окгкт а=(аД окгкт 364 иггы с пллтвжными ьэнкциями члстного вядл (гл.
ч стратегии Р=(р„..., р„+,) н чистой стратегии а будет л+л / л ~л ~~.", ру ~)(1~) — ЯаД) =Р(Р, Т, а). (364) У=л У=о Здесь Т=((„..., 1„„). Утверждение теоремы Х1.Ч применительно к рассматриваемой задаче приводит нас к следующему результату. Теорема Х(.Ч11. Задача Чебышева о наилучшей аппроксимации функции 1" ф в отрезке (О; Ц с помои(ью л полиномов р„(() = ч~~',аф эквивалентна задаче о нахолсде1=о нии обязательно суи(ествуюи(ей седловой пючки функции Р(Р, Т, а) (364) при стремлении минимизировать ее по а и максимизировать по Р и Т.
Этот результат означает, что должна решаться задача о нахождении векторов Р„Т, н а„для которых имеет место Р(Р„Т„а,)=ттР(Р„Т„а)= тахР(Р, Т, а,). (365) и. т Итак, задача Чебышева свелась к одновременному решению комплекса двух задач на обычный экстремум. Покажем примерно, как из постановки (365) может быть получена известная теорема Чебышева. Для этого прежде всего отметим, что задача нахождения Р(Р„Т„а,)=тахР(Р, Т, а,) э. г прн фиксированном а, приводит, конечно, к необходимости Р(Р„Т„ал) =тах Р(Р, Т„а,) = тах Р(Р„Т, аь).
(366) л+ч Первая из этих задач с учетом условия ~ ру — — 1 гл1 приводит к необходимости равенства нулю производных от Р(Р, Т„а ) — Л~р~ с=л ~ 28] исты с выпуклой платяжной етнкцнвй 365 (367) Учтя требование Д ру —— 1 и вытекающее из (368) равенство и У((,,) — Х аГ!',,=( — Ц. Л, о=о можем рассматривать (369) как систему уравнений для определения р): и+о Х рг( — 1)от(8=0; о=О, ..., п, (370) Хр]=1. /= т о) Здесь предполагается, что все оптимальные р; ) О. Если это не так, то число точек О по существу становится мейьще, чем и+2, но это противоречит числу уравнений в (370). П о рте), т. е. к ~(!ь) — ~а)(,', — Л=О.
о=о Отсюда следует, что при всех Уу (! (и+2) | и 1о ]' ((ь) — ~ аф,~[ = сопз1 = Л',. о=о Но тогда в силу т;ру — — 1, положив Р'= [1, О, ..., О), имеем Л',=Р(Р„Т„а,) = щах Р(Р, Т, а,) ) р. т вгпахР(Р', Т, а,) = гпах [7(гг) — ~~ а]г[']и. (368) т о<акт Таким образом, если (аД =а, оптимально, то функция | 7 (о) — ~ агог достигаева одинакового максимума в о=о (и+2) пинках (до (! =1, ..., и+2). Первая из экстремальных задач (365) приводит, очевидно, к необходимым условиям и+о и ~ р~ ~~(ой) — ~~~~~аЯ ~]1~~ — — 0; 1=0, ..., и. (369) /=т о=о 366 иггы с пллтяжяыми юьякцнями члстиого вядл (гл.
ч Детерминант этой системы имеет внд 1 ... 1 ( !)а, ( 1)а„ю, ( — 1)а1 г ... ( — 1)апюог ( 1)а,(п ( 1)апо,!и 1 ... 1 1)в ( 1)а оо ' ' ' «+о о ооо ° ой+о, о ! ( ])по+О (оо озо ° ой+о. о +( 1)ао+о+пюг Здесь 3=а,+... +соплю. Пользуясь известным выраже нием детерминанта Вандермонда легко записать решение системы (370): )Э(Гоо " Гу-со ГЬ+Ьо "° Го+о,о) рю — ( 1)а„+(- г ( 1) о+ г1(Гоо " Го-со Го+со Го+по) о=! / — о п+ю Д (йо 0ю) Д Цо йо) ( — !)а'"' 'Д (Ггю-Гою) ' Д (Гоо — 0о) ' о=о о=о+1 (37! ) ( 1)аз+)- г Х 1 1 ... 1 ого ооо опЮо, о ого ° ° оп+ь о ого ° (и+ь о 9 291 ИГРЫ С ВЫБОРОМ МОМЕНТА ВРЕМЕНИ 367 Если нумерация 1 выбрана в порядке убывания Г~,, те все детерминанты Вандермонда, входящие в (371), псложительны.
Согласно смыслу задачи р)) О; это, очевидно, может быть только, если все ( — 1)"~+г-' имеют один и тот же знак. Но тогда а7 — — 1 — 1+ сопз1. Это означает, что, во-первмх, в (371) все множители ( — 1)оч+г-' могут быть опущены (372) л+ о Ф )-~(гоо Го-Ьо Ро-оь о ° ° ° Со+о.о) о=! 9 29. Игры с выбором момента времени Под играми с выбором момента времени (дуэльные игры или ситуации) понимают игры на единичном квадрате, т. е. при О < х < 1 и О < у < 1 с платежной функцией М(х, у), Р (Х, у) =- Го (Х), 7.(х, у), х)у; х=у; х( у.
(373) а, во-вторых, разности 7(1 ) — ~'., аЯ оказываются одинао ковыми по модулю и чередующими знак с изменением 1 от 1 до и+2. Суммируя все сказанное, получим: если оо — оптимальный л вектор в задаче Чебышева, то функция )'(1) — ~ ат1'= 6 (1) о=о имеет (а+2) точки 17 (1=1, ..., и+2), в которых поочередно достигается максимум и минимум Ь(1), причем абсолютные значения максимумов и минимумов совпадают. Это и есть частный случай общей теоремы Чебышева. К этому утверждению мы можем добавить теорему Х).ЧП с полученными выражениями (372).
Возможно, что такая трактовка может быть полезна при численном решении задачи Чебышева на практике. Кроме того, видимо, могут быть применены и численные методы решения игр в смешанных стратегиях. 368 иггы с платюкнымя функциямя члстиого вилл (гл. т Функции М (х, у), Ф (х) и 1. (х, у) предполагаются обычно дважды непрерывно-дифференцируемыми функциями, каждая в своей области задания, однако М(х, х)ФЕ(х, х), и обе эти функции аргумента х могут быть, вообще говоря, отличны от Ф(х).
Как правило, принимается также, что М (х, у) н Ь(х, у) не убывают по х и не возрастают по у. Однако это будет использовано позже. Ограничение множества стратегий обоих игроков единичным интервалом несущественно, ибо преобразованием координат любой интервал может быть переведен в единичный с соответствующим преобразованием платежа. Возможно, конечно, обобщение дуэльных игр на многомерные стратегии х и у, но это обобщение здесь не рассматривается (см. монографию Карлина).
Дуэльные ситуации достаточно распространены, особенно в исследовании военных операций. Они отражают обычно факт получения значительного преимущества над противником, если удается предварить его действия своими, хотя в ситуации имеется и противоположная тенденция некоторой выгодности запаздывания. Первая тенденция выражена в наличии разрыва платежной функции на прямой х=у, а вторая †упомянутой монотонности платежа выше и ниже этой прямой. Примером дуэльной ситуации является приведенная выше модель 1Х. В теории дуэльных игр различают так называемые бесшумные и шумные игры. При шумной дуэли выбор у становится известным первому игроку, если х) у (например, в модели 1Х он может слышать, когда произведен выстрел, и может воспользоваться этой информацией, если сам еще выстрел не произвел), и выбор х — второму игроку, если х< у.
В бесшумной дуэли такая информация не поступает вообще. В соответствии с этим шумная дуэль является как бы двухшаговой игрой с нефиксированной последовательностью ходов. Пусть здесь выполнены указанные раньше условия; тогда, если принято сначала решение обоими игроками в виде х„у, и х, оказывается больше у„вторым шагом й 291 ИГРЫ С ВЫВОРОМ МОМЕНТА ВРЕМЕНИ 369 х= У; (375) х< у. Нахождение для (373) наилучших чистых (гарантиру- ющих) стратегий не представляет затруднений, если вообще наилучший гарантированный результат достижим; если же он недостижим, т.
е. Впр 1п1 Р (х, у) не естыпах!п1 Р (х, у), А Р Р то нужно говорить об В-оптимальных чистых стратегиях, гарантирующих получение платежа, не меньшего зпр 1п1Р(х, у) — е. А Р Отметим лишь, что получается при монотонных М (х, у) и Ь(х, у). Тогда, очевидно, 1п1 Р (х, у) = ш!п (М (х, х); Ф (х); 7. (х, 1)), зпр 1п1Р(х, у) =шах пип(М(х, х); Ф(х); 7.(х, 1)). л В В Таким образом, если М(х, х), Ф(х) и 7.(х, 1) непрерывны в [О; Ц, то существует оптимальная чистая гарантирующая стратегия х,. Однако !п1Р(х„у) может быть и недостижим, если максимум величин М (х„х,); Ф (х,); 7, (х„1) есть М(х„х,) или если х,=! и М(1, 1)~Ф(1)~Ь(1, 1). х, заменяется на х = 1, как дающее максимальные М (х, у,) при известных уже у,; при х,<у„наоборот, у, заменяется на 1.
Такая двухшаговая игра может быть записана как одношаговая в виде М(1, д), Р (х, у) = Ф (х) Ь(х, 1), и таким образом, она оказывается частным случаем бесшумной дуэльной игры (373), когда М не зависит от х, а Ь вЂ” от у. Разумеется, нет необходимости в предположении о монотонности М(х, у) и Ь(х, у) для формирования шумной дуэли. В общем случае получим, очевидно: М' (у) = шах М (х, у), х > у; ЯЪУ Р (х, у) = Ф (х), Ь'(х) = пип 7.(х, у), Р~» 370 ягуы с платежными еузкцяяия чьстного вида [гл. т Аналогично получаем зпр Р(х, у)=шах (М(1, у); Ф(у); Е(у, у)) ш[пзпрР(х, у)=ш[пшах(М(1, у); Ф(у); Е(у, у)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
