Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 34
Текст из файла (страница 34)
стратегий противника вида (191), рассчитанных на информацию об х2, то такая игра всегда имеет седловую точку. Применив зту теорему к случаю (184) — (184'), увидим, что (191) превращается в множество стратегий вида у;(у, хб 1 ( Е, ! ( !), 207 6 !61 о сндяовых точк»х основанных на получении информации обо всех х, при 1 ( 1 к моменту выбора уо Объединяя это с (!84), приходим к следующему порядку многошаговой игры.
Сначала оперирующая сторона выбирает х„ не имея никакой информации (кроме знания Й); затем противник, зная М, и х„ выбирает у,; далее оперирующая сторона, зная х, и у„ выбирает х, и т. д.; последним выбирается у», когда известен весь вектор х и, конечно, уу при 1 (Й вЂ” 1. Эта игра носит название игры с полной информацией. В качестве следствия теоремы ХХ1И имеем поэтому известную теорему из теории игр. Следствие (теорема Цермело). Всякал игра с полной информацией имеет седловую точку.
Цена игры может быть записана в виде (184'). Имея в виду принципиальную важность рассмотрения игр многих лиц, обратим внимание на данное Нэшем обобщение для них понятия седловой точки в виде так называемых точек равновесия в бескоалиционных играх. Игра и лиц называется бескоалиционной, если у 1-го игрока имеется собственный критерий эффективности— платеж 1;(х„ ..., х„), причем независимый от других игроков выбор х; из некоторого М; составляет стратегию г'-го игрока. Введем обозначение х* = (х„ ..., х„) и М* = Ма х ...
х М„. Точка х," =- (х,', ..., х'„) называется точкой равновесия, если для всех г выполнено 1;(хе, ..., х,', ..., х,',) = = шах);(х„', ..., х,' „хг, х,'+„..., х„'). (194) «ве м~ Легко проверить, что при и=2 и )» — — ), определение (194) превращается в свойство -(186) седловых точек. Несомненно интересна следующая, установленная Х. Никайдо и К. Исода е) связь между нахождением точек равновесия и нахождением максимина в некоторой операции с критерием эффективности, выраженным через (194).
*) Соответству1онгэя статья имеется в сборнике «бесконечные »итагонистические игры». 208 (гл. ш оптиыАдьиыи стРАТБгии Теорема ХХ!Ч. Игра п лиц имеет точку равновесия (х'„..., х„') = х,'. тогда и только тогда, когда гпах ппп ~ч" [~г(х„..., хл)— «" ем' у'ем' ~=1 — 1т(х„..., хг „уо х;„, ..., хл)) =О. При ятом х', является оптимальной стратегией в операции с критерием *) Ф*(х*, у*)=~Р [1'г(х„..., хл)— с=1 — )г(х„..., х; „уо хг+„..., х„)). Доказательство. Очевидно, при всех хе ЕМ* ппп Фа(х*, у*) (О, у'е М а вслед за этим н гпах ппп Ф(х', уа)(0. ллеМ* у*а Мл Если существует точка равновесия х,', то по определению ппп Ф(х,', у')=О. у*а М" Тем самым н гпах ппп Ф(х*, у*)=0 — - пии Ф(ха у*) (108) л' е М * у' е М ' у ем" Если же, обратно, равен нулю макснмнн, то существует х,, для которой выполнено (195).
Но отсюда 0 = ппп ~чС„[1;(х'„..., х„')— ут ЕМ" 1=1 — 6(хтю, х~ „уь х~+„хл)) = л = ~~р ~[~;(хе„..., х„'') — гпах ~;(х'„...,ха „уоха„„...,хе)[. т=т у;ем~ *) Легко видеть, что оиерация ~„может быть заменена иа операцию пип. 209 й 161 О СЕЛЛОЕИХ ТОЧКАХ о ~ р.(!)г(! =7' о 2 ] (р,(!) Ж=Т;+ Р„ о (197) р,(О) =1. Поскольку все члены суммы по ! неположительны, отсюда немедленно следует, что для всех 1 6,..., .— 1'( о оо ; (Х„..., Х„) =- ГнаХ р'; (Хо ..., Х, „УО Х,о„..., Х„), и о Мо а это и значит, что х," есть точка равновесия.
Легко провести аналогию между этой теоремой и леммой $ 15 (см. (165) — (165')). Не останавливаясь более на играх п лиц, отметим лишь, что доказанная теорема еще раз подтверждает широту охвата максиминных постановок вопроса. Разумеется, теорема ХХ!Ч носит довольно формальный характер и не снимает трудностей(принципиальных), которыехарактерны для теориибескоалиционных игр. В заключение раздела о седловых точках приведем интересный пример операции с седловой точкой, относящейся к теории надежности.
Пусть имеются два агрегата, способные выполнять одну и ту же работу. Первый имеет закон надежности р, (!) о со средним временем работы Т,=) р,(!)о(1; второй агрео гат имеет среднее время работы Т,. Поставим вопрос о целесообразности замены первого элемента вторым через время работы т, не дожидаясь выхода первого элемента из строя, чтобы отправить его на профилактический ремонт.
В качестве критерия эффективности для выбора т возьмем среднее время работы (безотказной) системы из первого и заменяющего его второго элементов. Это время равно Т Т = ] р, (1) о(1+ р, (т) Т, = Т (т; р, (!)]. (196) о Стратегией оперирующей стороны здесь является выбор т, а стратегией противника (природы) — закон надежности р,(!) с ограничениями 210 !гл. ш оптнмАльвые стРАтегип Имеем следующие простые утверждения.
А. Если р,(1) связано пюлько первым и третьим ра- венспюами из (197), то игра с критерием (!96) имеет седловую точку. Цена игры — щах [Т„Т,]. Оптимальная гарантирующая стратегия оперирующей стороны ! 0 при Т,<Т„ то«т '[ оо при 7",) 7',, (198) Оптимальная стратегия природы (наихудшая для опери- рующей стороны) рт(1) = е-Пг . Действительно, если 2=0, то при любых р,(1) Т=Т;, если же т= оо, то Т=Т,. Поэтому применение указай- ной стратегии выбора т обеспечивает всегда получение Т = Гпах [7 „' Т,]. Наоборот, пусть р,'(1) =е уг; тогда 7" =Т вЂ” Т е-тГГ + T е-тет1= Т,+е 'цг (Т,— Т ) < <гпах [Т,; Т,].
Далее, имеем 2пах [Т„Т,] = !п! Т [т,„„р, (1)] < зпр (п! Т [т, р, (1)] < р,и2 Г р,(о < !и! зпр Т[т, р,(1)]<зпрТ[2, р',(1)] <Гпах [Т„Т,]. »1(П Отсюда и следуют все утверждения. Б. Если имеются все ограничения (197), но !21>Т„' то игра (196) опять имеет седловую точку с той же ценой игры и т„„„но оптимальной стратегией природы будет р,"(1) = 1 при 1=0, 2т, *11) 2гт* т ~о, при 1> О. Т +12 Доказательство.
По-и режиему т„„, при всех р, (1) ЧаЕт Т=гиаХ [Т„Т»]. «ПрИМЕНЕИИЕ» Прнрадсй р",(1) Обге- печивает, очевидно, при любых т > 0 т, г, — 2» т 27» — 2 т т Т=Т ! — е ГМ +Т„т е Гтт.о~ < Г, 2Т, -2 — 'т т 1 Гтт.о, 7 е Г',.о, 2Т, =Т,+(7' — Т,)е Г', -о, (Гпах [Т„Т»], 3 17! иеоаходямые хсловия оптимальности 211 Если же т = О, то при р",(!) будет Т = Т, ( гпах (Т„Т,).
Р!так, всегда р,(!) дает Т(шах [Т„Т,). Отсюда, так же как и в предыдущем случае, следуют все утверждения. Итак, в условиях этих теорем оказывается невыгодной замена для профилактики, а нужно все время до выхода из строя использовать тот нз агрегатов, который имеет большее среднее время работы. Это утверждение, казалось бы, противоречит всей практике работы людей. Однако на самом деле это не так. Просто условия теорем (информация о р,(!)) не отвергают законов надежности типа е-' при линейной комбинации таких законов.
Они-то и оказываются наиболее неприятными видами законов, хотя и наиболее употребительны в теории надежности. Если же будет известно, что О, ( Т„ то такие законы не будут разрешены, и положение изменится в полном соответствии со здравым смыслом. Это будет показано в последующих разделах. В частности, в игре (196) исчезнет седловая точка при общем виде р, (!), удовлетворяющих (197). $ !7. Необходимые условия оптимальности Поскольку обычный экстремум является частным случаем максимина, то необходимые условия для последнего должны включать в себя и необходимые условия экстремума функций (М=М„, а !У состоит из одной точки) и необходимые условия вариационного типа (если М состоит, например, из дифференцируемых функций) и т.
д. Собственно, необходимые условия для макснмина должны быть, конечно, существенно сложнее необходимых условий для обычных экстремумов. Сколько-нибудь общие условия оптимальности (в рассматриваемом понимании этого слова) для широкого класса множеств М пока еще не разработаны. Поэтому ограничимся рассмотрением крайних случаев М=М, и М=М„имея в виду показать специфику постановок задач о необходимых условиях оптимальности при наличии неопределенных факторов.
При поиске оптимальных стратегий нужно считаться с двумя следующими обстоятельствами: !. Согласно 9 !5 существуют два понятия оптимальности †абсолютн оптимальность и просто оптимальность. (гл. Ш оптвнальима стглте»яя Кроме этого, заслуживает отдельного рассмотрения и случай наличия седловых точек. 2. Задача определения оптимального варианта проведения операции может быть разбита на две задачи: а) поиск оптимальной стратегии; б) определение оптимального результата (максимина), который может рассматриваться и как оценка эффективности оптимальной стратегии.
Такое разбиение иногда может быть полезно, например, потому, что решение первой задачи может оказаться более простым. В соответствии со сказанным начнем с необходимых условий абсолютной оптимальности. Эти условия являются тривиальным следствием определения (164) и по существу (для любого М) совпадают с обычными условиями оптимальности (без неконтролируемых факторов), но с добавлением того, что они должны выполняться тождественно по уЕ1»'. В частности, для М=л4, при дифференцируемости Р(х, у) по х имеем: Для того чтобы постоянная х, Е М, была абсомотно оптимальнойй внутренней в М, стратегей, необходимо, чтобы при х=(х„..., х„) ' ~ =О; уЕМ, 1=1, ..., п.
(199) Граничная х, из М, может быть оптимальной, только если производнал Р(х, у) в х, по любому направлению т, не выводящему из М„неположительна, т. е. если (199') при любом уЕФ. Необходимость тождественного выполнения (199) при фиксированном х, и показывает на «редкость» абсолютной оптимальности в множестве М,, если У вЂ” достаточно обширное множество. Прямо противоположное положение имеется при М = М,. Тогда абсолютно оптимальная стратегия заведомо имеется, если множество М, замкнуто и ограничено, а Р(х, у) $17) язовходимыз тслозия оптимлльности 2!3 непрерывна по х; вто непосредственно следует из выполнимости (164).
Значение х, оптимальной х, =х,(у) определяется уравнением (200) Р(л„у) =шах Р(х, у) ке Чц при каждом уЕУ. 1-1еобходимыми условиями для значений х„, внутренних к Л1„будет опять (199), но с той разницей, что теперь х, может зависеть от у, и потому (199) не имеет характера тождества по у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
