Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 35
Текст из файла (страница 35)
Для граничных х, опять-таки необходимо (199'), но с тем же существенным различием. Пусть теперь хг — все значения, удовлетворяющие (199) и (199') для данного у. Тогда окончательное х, определяется обычным перебором, исходя из Р(х„у) =- шах Р(х,, у). ! Этим и закончена процедура определения х, с помощью необходимых условий (199) — (199'). Согласно следствию теоремы Х1Ч из 5 15 при замкнутых ограниченных й( и непрерывных Р (х, у) при наличии абсолютно оптимальной х, Е М, всегда есть седловая точка (х„ у,), удовлетворяющая (186). Оценка эффективности х, равна здесь Р (х„ у,) н оказывается частным случаем задачи, относящейся к седловым точкам, которая будет изложена далее.
Аналогичное утверждение верно и для х,. Однако здесь поиск у, совпадает по существу с решением задачи поиска оптимальных у, реализующих гпшгпах Р(х, у). Эта задарен кем, ча эквивалентна задаче поиска шах ппп Р(х, у). хемеубн Задача поиска максимина с помощью необходимых условий также будет изложена далее. Перейдем к определению седловых точек, полагая Р(х, у) дифференцируемыми по х и у на ограниченных замкнутых М, и М. При поиске седловых пар (х„у,) на ОПТИМАЛЬНЫЕ СТРАТЕГИИ [ГЛ. 1Ы М,к Л/ прежде всего хочется подчеркнуть, что если, скажем, х, уже найдено, то у, нельзя, вообще говоря, получить как любую реализацию гп!и Р(х„у), так как нужно, чтобы Р(х„у,) =-щах Р(х, 1Г,).
к Так, например, для Р(х, у)=ху при ~х) < 1, ~у~ <1 седловой парой является только х,= О, у, = О, в то время как пни Р(О, у) достигается при любом у. Как ж искать седловые точки, кроме как прямым нахождением стратегий, реализующих максимнн и мини- макс? Для этого следует иметь определенный набор необходимых условий, которым должны удовлетворять седловые точки. Такие условия можно получить, пользуясь теоремой ХЧП1, дающей необходимые и достаточные условия (186), согласно которым седловая точка реализует одновременно два экстремума Гпах Р(х, д,) и ниц Р(т„р), к У равных одному и тому же Р(х„у,).
В такой формулировке задача мало чем отличается от поиска, например гнахР(х, О), который также состоит в одновременном достижении двух максимумов по х и у. Используя любые известные необходимые условия экстремума по х и у, можно всегда получить пару необходимых условий для поиска седловой точки. Пусть х=(х„..., х„); у=(у„..., у ), а М, и У заданы в виде а,<х, <Ь;, с~<у;<Г(,. Тогда,если седловая точка внутренняя для М, х У, то необходимо Р„',.(х„у,)=О= Р;„(х„у,), 1<и; 1<т. Это и дает нам и+ т уравнений для определения т+ п неизвестных х; и у.
Если точка (х„у,) лежит на границе, т. е. если, например, хм=а;„, хь=(х, и а, < х; < б;для остальных 1Ф („то необходимые условия будут Р„',. (х„у,) =0 = Ре,(х„у,) при 1~ (А,1,. 5 171 неовходимые условия оптимдльпости 215 ~се разнообразные случаи возможных расположений х„у, относительно границы легко объединяются в виде следующих общих необходимых условий. Теорема ХХЧ. Седловые точки дифференцируемой по всем аргументам функции Р (х, у) при х = (х„..., х„), у=(у„..., у ): а;(х;(Ьб с,( у,.(Н~, удовлетвораот необходимым условиям: Р„(х„у,) (хц — а;) (хц — Ь!) =-0; 1(1( п, (201) Р„,. (х„у,) (у1, — с ) (у1, — й,) = 0; ! ( ! ( т.
Кроме того, если х; = аь то Р„, (х„у,.) ( О, если х; = Ьо то Р,, (х„у,) ~ О, если у~ — — су или И,, то Р„(х,, у,) соответственно неотрицательна или неположительна. Условия (201) ничем не отличаются от необходимых условий максимума и минимума, и тем самым решение этих уравнений даст максимумы, минимумы и седловые точки (если они есть), а также, может быть, и локальные экстремумы.
Поэтому желательно дополнить теорему ХХЧ необходимым условием, выделяющим именно седловые точки, если они есть. Такое необходимое условие получаем из той же теоремы ХА!1. Действительно, пусть (хь у;) — все пары точек, удовлетворяющие (20!); рассмотрим Р (х, у) на декартовом произведении дискретных множеств Мд — — (х ) и 1Уд — — (у ). Тогда очевидно, что седловая точка Р(х, у) на исходных М, и !у есть и седловая точка из М„и й!д. Таким образом, необходимо, чтобы х,ЕМд, ~~,ЕФ и Р(х„у,) = ппп Г(х„у,) ==шах Р(хн у,). (202) У16нд х! дмд Условие (202) позволяет путем простого перебора всех (хь у,) обнаружить численно седловую точку среди всех пар, удовлетворяющих (20!).
Если же среди них нет седловой точки, то значит, ее нет н в исходной игре Ё(х, у) иа Мех й(. 215 ОПТИМАЛЬНЫЕ СТРАТЕГИИ [ГЛ. П! Условия (20!), конечно, никогда не имеют единственного решения, поскольку им удовлетворяют все граничные точки Имеем Р„' = у' — х; ГР' = — 2ху — 0,5'.
Обе производные обращаются в нуль одновременно только при у,=0,5; х,=0,5'. Кроме этого, иа подозрении все комбинации граничных точек х,л —— 0; 1 и у,л — — 0; 1. Далее условия (201) удовлетворяются еще при хз — — 1, у,=О 54 Для определения седловой точки необходимо рассмотреть для х стратегии: 0; 0,5'; 1.
Для у: 0; 0,5', 0,5; 1. Имеем соответствующую платежную матрицу Р(хь уу): 0,54 0,5 — 0,54 — о,'5 0 — о,54) О'5 О 54 ' — 0,54 О 54(! О 54) О'5+0 54' — 0,54 о 54 0,54 о 0,54 1 о — 0,54 — 0,5 Отсюда видно, что седловой точкой является х,=0,5', у,=0,5.
Максимум — при х=у=1, минимум при х=1; у = 0,5'. Разумеется, для поиска седловых точек на Мх4Ч столь же успешно могут применяться н все другие приемы для нахождения экстремумов, когда множество рассматриваемых стратегий М и вид критерия эффективности удовлетворяют соответствующим условиям. Так, если рассматриваются стратегии типа х=х(у+г), где г — случайный вектор с известным законом распределения, то критерий эффективности имеет вид г (х у) = ) г" [х (у+ е) у) Й (е).
х;=а;; Ь;; у =с; 41,. В качестве примера использования теоремы ХХЧ найдем седловую точку у вогнуто-выпуклой функции г(х, у)=ху' — 0,5х' — 0,5'у; 0< с<1; 0<у<1. 5 1Р1 неОБКОдимые услОВНБ ОптимАльиосеи 211 В силу (186) седловая точка (х„у,), если она есть, должна удовлетворять условиям: а) при фиксированном у, и прн х,=-х,(п +г) должен реализоваться максимум шах ) г (х (у, + г), у,) «ьр (г); «[У +»3 б) при фиксированном х, и при у=у, должен реализоваться минимум ш(п~у(х,(у+г), у)«цр(г). (204) Задача (203) есть вариационная задача Относительно функции х(у,+г)=х,(г), что дает возможность употреблять и соответствующие необходимые условия, например условия Эйлера. Задача же (204) есть задача на обычный экстремум с необходимыми условиями в виде равенства нулю частных производных критерия по уу в точке у=у„ если у,— не граничная точка. Таким образом, опять получится пара комплексов необходимых условий, которые дадут не единственное решение для искомой седловой точки (хотя бы для у,) с необходимостью выделения седловой точки на основе (202).
Разумеется, в большинстве задач значения х(у+а) ограничены непосредственно или через какие-либо дифференциальные связи. Тогда (203) становится типичной задачей поиска оптимального «управления» х(у,+г) с необходимостью применения всего аппарата теории оптимального управления, например принципа максимума Понтрягина. Не будем останавливаться на этом подробно, так как задачам оптимального управления в настоящее время уделяется много внимания и имеются специальные руководства, например книга В.
Г. Болтянского «Математические методы оптимального управления». С другой стороны, с нашей точки зрения, случаи, приводящиеся к задачам оптимального управления, могут быть с помощью введения дискретизации по г сведены к использованию теоремы ХХЧ или соответствующих численных методов. Отметим еще наличие довольно гибких численных методов [гл. Нс' Оптямьльные стгхтегия решения задач оптимального управления, общие идеи и обзор которых даны в статье Н. Н. Моисеева «Числессные методы теории оптимальных управлений, использующие вариации в пространстве состояний». Прежде чем изложить результаты, касающиеся нахождения максиминов и минимаксов, уточним, как производится нахождение оптимальных стратегий, седловых точек и максиминов в случае, когда множества стратегий обеих сторон конечны.
Необходимость соответствующих переборов мы уже встретили на примере (202) и встретим еще в дальнейшем. К этому же мы приходим и в случае прямой приближенной замены множеств М, и )У на дискретные множества Мс, и сУ", о возможности которой . также будет сказано далее. Если множество стратегий х и у конечно, а именно, М, = (хб с = 1, ..., л); )У = (уА 1 = 1, ..., т), то соответствующая игра может быть представлена в виде платежной матрицы ~У (хс, ус) ~~ = ~!Рсс ~5 (205) показывающей, какой платеж Рс~ (т.
е. значение критерия) получает оперирующая сторона, когда выбирает с-ую стратегию, если противник выбрал )сую. Часто дискретные конечные игры называются матричными. Для игры (205) максимин москно получить только простым перебором, определяя сначала для всех с А;=ш(пР;, а уж с затем шах Ас= шах ппп Рс~', оптимальной стратегией опес с с рирующей стороны будет с„для которой Ас, =шах А;. Аналогично обстоит дело и с минимаксом, с той лишь разницей, что оптимальной стратегией оперирующей стороны здесь будет функция с,(/), реализующая при каждом с' шахРс = В =Рс,<пс.
Если априори известно наличие у матрицы (205) седловой точки, то в основе численного метода поиска оптимальных стратегий лежит следующая процедура. 5 171 неоаходииые толовая оптцмлльпости 219 Выбрав произвольную 1,, находим Ву, и соответствующую !0(1,), которая обозначается через 1,. Затем находим Аи и соответствующую 1, так, что Р~„, = Ап. Если 1, =!„ то поиск седловой точки закончен 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}
