Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 38
Текст из файла (страница 38)
Отсюда видно, что теорема Х ХЧ! есть следствие теоремы ХХЧ1П, а первые два варианта (207) соответствуют случаям, когда !1(х) содержит только одну или хотя бы две точки. В общем же случае из теоремы ХХЧ111 получается следующее необходимое условие оптимальности стратегии х, (при условиях теоремы ХХЧ111). С л е д с т в и е. Для того чтобы х, была оптимальна, необходимо, чтобы производная ф(х) по всем направлениям в точке х, была неположительна.
Иначе говоря, необходимо зцр [( ') = зцр ппп ~ ( " "), д1 ( О. (216) е ее де ввел ввя (кэ) дх Эффективность этого условия ограничивается опять- таки тем, что для проверки его необходимо знать все Я(х,). В этом смысле (216) менее удобно, чем (210), поскольку в последнем участвует не все !С(хв), если оно содержит более и+1 точек. Кроме того, большее удобство (210), вернее, его модификации типа (201) состоит в отсутствии операции ш[п и, значит, в большем удобстве для отыскания х„. С другой стороны, условия (216) более точны и, следовательно, более пригодны для контроля. Все сказанное исчерпывает известные нам результаты по необходимым условиям для максимина.
Теоремы ХХЧ[ — ХХЧ111 дают принципиальную возможность в сочетании с указывавшимся ранее перебором определить оптимальную х, и само значение максимина, когда множество стратегий М =М,. Что касается случая М=М„то, как мы уже знаем„ здесь существует абсолютно оптимальная стратегия х„ определяемая с помощью (199) — (199'). Что касается наилучшего гарантированного результата, то он здесь равен ппп гпах г'(х, у) вен хем~ з 181 лппгоксвмлция иге и моделей опеглций 235 и может определяться по только что перечисленным теоремам. Как видим, здесь задачи определения оптимальной стратегии и оценка ее эффективности распадаются на две отдельные задачи, как это указывалось в начале настоящего раздела. $ 18.
Аппроксимация игр и моделей операций Для проведения на практике приближенных исследований, а также для получения ряда теоретических результатов, нужно иметь четкое представление о близости игр или моделей операций. Как и всегда, такая близость может существовать или по критерию эффективности (платежу), или по множеству стратегий или по обоим этим факторам. При этом всегда встает вопрос о близости оценок эффективности и оптимальных решений. Основу для суждений по этим вопросам могут дать две простые теоремы, приведенные в этом параграфе.
Теорема ХХ1Х. Пусть на произвольных множествах М,=(г) и М,=(о) заданы два критерия Р(г, о) и Р,(г, о) такие, что ! Р (г, о) — Р, (г, о) ~ ( е при любых г Е М, и о ~ й1,. Тогда не более чем на е отличаются и оценки эффективности произвольных стратегий г=г(о), т. е. ! !п1 Р(г, о) — !п1 Р,(г, о)~(е. ячив пена Точно так же не более чем на е отличаются и оптимальные гарантированные результаты операции (макси- мины) по любому множеству М стратегий г, в том числе и по смешанным стр тегиям. Вообще 1-- зпр !п1 Р(г, о) — зцр !п1 Р,(г, о)[(е *ам зчн Лам зен для любых множеств стратегий М и У обоих игроков, каждая пара г и о которых определяет г и о, а значит, и результаты игр.
Доказательство. Пусть г=г(о) произвольна, а последовательность о„ такова, что !п1 Р (г(о), о) = !пп Р(г(о„), о„). яен, 6 а 23Б [гл. ш ОнтййАльные стРАтегйн В силу условия теоремы Р [г (о„), о„1 ~ Р, [г (о„), о„) — е ~ )[п! Р, [г (о), о) — е, «в«в Переходя к пределу при а- оо, получим [п[ Р [г (о), о) ) [п! Р, [г (о), о[ — е. ««»те ««Фе В силу полной равноправности Р и Р, имеем аналогично [п! Р, [г (о), о) ) [п! Р [г (о), о) — е.
««»те ««Мв Эти два неравенства эквивалентны первому утверждению теоремы. Для доказательства второго возьмем последовательность гь такую, что епр ш! Р(г, о) = [пп [п! Р(г„, о). А вв ««Ф» «ЕМ««У» Но, как уже доказано, [п! Р(ге, о)( !п! Р,(г„, о)+е( зцр [п[ Р,(г, о)+е, в »М «ЕФ» «еле ««Ае» и, следовательно, переходя к пределу, получаем енр [п! Р (г, о) е- зцр 1п! Р, (г, о)+ е. в «М ««А», в«М «влв Имеет место, конечно, и неравенство, получающееся перестановкой Р и Р;, совокупность этих неравенств доказывает е-близость максиминов.
Если множество М состоит из смешанных стратегий <р(г), то платежи соответственно будут равны Р = ) Р (г, о) йр (г); Р, = ~ Р, (г, о) Йр (г). По теореме о среднем, очевидно, ~Р(<р, о) — Р,(ер, о) ~(~ [Р(г, о) — Р,(г, о)[йр(г)(е. Таким образом, новые критерии эффективности удовлетворяют условиям теоремы и, как показано, не более чем на е отличаются оценки эффективности и наилучшие э 18! ьппгоксимхция иге и моделей опеглций 237 гарантированные результаты и на множестве смешанных стратегий. Наконец, последнее утверждение теоремы, очевидно, следует из уже доказанных результатов, если вместо М, и У, введем в рассмотрение М и У, что допустимо по условиям теоремы.
Замечания. 1. Теорема не утверждает близости самих оптимальных стратегий, да это н неверно. Пример: Р=у+зх, Р,=р — ех при М,=У,=( — 1; 1). Действительно, при любом з ) 0 для Р оптимально х= — 1, а для Р, оптимально х= — 1. Это обстоятельство не уменьшает практической значимости теоремы, поскольку гарантируется для ошибочно найденных (при замене Р на Р,) оптимальных стратегий результат, отличающийся от истинно оптимального не более чем на е. 2. При замене Р на Р, не сохраняются, вообще говоря, факты наличия седловой точки и абсолютной оптимальной стратегии, однако максимин ст минимакса будет отличаться не более чем на 2е, а вместо абсолютно оптимальной стратегии появится стратегия г'„реализующая максимум по г для любых о с точностью до з. 3.
Если среди неконтролируемых факторов о есть случайная составляющая, то осреднение по случайностям ничего не изменит в результатах теоремы аналогично тому, как это было для смешанных стратегий. Теорема ХХ1Х даст нам в дальнейшем возможность доказать основную теорему непрерывных игр. Сейчас же используем ее для строгого обоснования приближенной замены операции с непрерывными множествами М, и 1ч' векторов х и у на операцию с дискретными множествами Моа и 1тх для использования численных методов.
Потребуем лишь ограниченности М, и У и непрерывности критерия Р(х, у) и, взяв произвольное е, разобьем содержащие М, и У параллелепипеды М и У (а такие имеются из-за ограниченности М, и Ф) на столь малые параллелепипеды, чтобы колебание Р (х, у) на каждой паре из них не превышало е. Возьмем теперь на каждой паре таких параллелепипедов Р, (х, у) постоянным и равным значению Р(х„, у ) на центрах х„и у„этих параллелепипедов.
238 !гл. ш ОПТИМАЛЬИЫВ СТРАТЕГИИ По построению имеем, конечно, !1Р(х, у) — Р,(х, у)~<в при хЕМ, и у~!у. В силу только что доказанной теоремы рассмотрение опе- рации с критерием Р(х, у) можно с точностью до в заме- нить на рассмотрение операции с критерием Р,(х, у). Но для последней все значения х, принадлежащие одному и тому же параллелепипеду, совершенно равноценны; то же относится и к неопределенным факторам у.
Беря в ка- честве «представителей» этих параллелепипедов соответ- ственно х„и у, придем к операции с критерием Р, (х„, у„)= = Р(х„, у„), заданным на конечных множествах Маа и Ма значений х„и у *). Полученные здесь оптимальные стра- тегии будут е-оптимальны для исходной задачи. Вторую теорему удобнее представить в ином виде. о е Пусть Уе= .~~ Ун М,= )~ Мь причем 1ту е= Му+„ 1=1 М; С Мгех.
Пусть, далее, дан любой критерий Р(г, о) при г ЕМ, и ИЕУе. Наряду с этой операцией рассмотрим также операции с тем же критерием, но с множеством контролируемых и неконтролируемых факторов М; и )тл Теорема ХХХ. !. Всегда имеет место: ш1 Р(г, о) =1нп 1п1 Р(г, о), 1 о«Не ! ев О«»11 (217) зцр Р(г, о)=-!Ип знр Р(г, п), ) в«Мв 1 ео в«М1 зцр !п1 Р (г, о) = !пп зцр !п1 Р (г, о) = ее Ме »ЕНе Е ЕО 2«М1 О«Но = 1цп знр 1пп !п1 Р(г, о)( !Ип знр !п1 Р(г, о), (2!8) 1 в е«М1 / ве ЕЕН1 1.! ое ЕЕМ1иЕНу !п1 знр Р(г, о)= !!ш !п1 зпр Р(г,о)) ЕЕН, в«М, 1 ее О Е Не в Е Мо ) !пп !п1 зцр Р(г,о).
(2!8') 1, 1 ее оеН1 ееМ1 ') Если пентры х„или и„, не входят в Ме или У, то они могут быть заменены любыми другими точками параллелепипедов. ф !8! ьппгоксиикция иге н моделей опггкцнй 239 2. На Мьхй(, имеется седловая точка (г„о,) тогда и только тогда, когда она является седловой точкой для всех М;хй! при достаточно больших 1 и !.
То же относится и к абсолютно оптимальной стратегии г,. 3. Если Е= зцр !п1 Р(г, о)~ ьь, то для любого е ььма ььнф всегда найдутся М1 с М~ такие, что М~ ~ М,'+ ы ~ М~ = М, и 1„(„для которых при 1>ь,; ! >1, 1=1 зцр !п1 Р(г, о) — зцр !п1 Р(г, о)~(з. (2!9) ! *ьМе иене ьь не чье~ с Если Е= + ьь, то вместо (219) для любого Т верно зир !п1 Р(г, о)>Т при 1>(г; 1>1г. льм~ вен~ Наконец, если Е = — ьо, то верно зир !п1 Р(г, о)е-.— Т; !>!г, !'>(г. альм; оен~ Доказательство. !. Первое равенство, очевидно, следует из того, что для любого б существует ом для которого существует !ь так, что оь б У~ при 1> !ь. !п( Р(г, о) > !п1 Р (г, о) > Р (г, оь) — б > |п1 Р(г, о) — б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
