книги / Математические методы принятия решений
..pdfЛ,4 |
Уз?4» *3 |
Рис. 4.10. Графики зави |
Рис. 4.11. Графики зави |
симости /з,4 от аргумен |
симостей /з*4 и х* от ар |
та хз и параметра zi |
гумента Z2 |
По значениям / 3*4(22), приведенным на рис. 4.11, строим зави симости / 2*34 и х \ от z\ (рис. 4.13).
/ 2,3,4
Рис. |
4.12. Графики |
зависимости |
Рис. 4.13. Графики зависимостей |
/ 2,3,4 |
от аргумента |
хг и пара- |
/ 2*3 4 и х* от аргумента z\ |
|
метра z\ |
|
|
Проведем оптимизацию решения на первом шаге. Число само летов, которые совершают налет на первый рубеж, задано: zo = 80. Выигрыш составит
fu2,3A(xi) = Q № 0 + f h , M ) , Qi(rr,) = iV1(l
где vi = x\e~ a'Ni, z\ = (z0 - x i)e- a '^ ', Ni = N \ - Q i(x \) .
По значениям / 2*3,4, приведенным на рис. 4.13, строим график зависимости / 1,2,3,4 от х\ при z0 = 80 (рис. 4.14). По точке макси
мума получаем, что х* = 34, а полное число пораженных орудий равно 14,1.
/l ,2,3,4
Рис. 4.14. График зависимости / 1,2,3,4 от аргумента х\
Итак, 34 самолета бомбят первый рубеж, 46 самолетов направ лено дальше. К зоне действия орудий второго рубежа дошло z* самолетов:
z* = 46е~а' ^ ' , |
N ^ N i - Q x i x t ) , |
(4.3) |
д 1( х П = М ( 1 - е |
- ^ Р ') , V* = х * е ~ “ |Л\ |
|
Получили z* = 37, и на первом рубеже поражено <51(2:*) = 5,6 орудий. При z* = 37 по значениям, приведенным на рис. 4.13, полу чили оптимальное управление на втором шаге: х | = 23, т. е. дальше следует направить 14 самолетов. Пользуясь формулами, аналогич ными формулам (4.3), получим
Q2(X Î) = 5,4, |
z \ = |
10,7, |
х 3 = 0, |
|
|
Q 3( x 3*) = 0, |
23* = |
5,9, |
Х4 |
= 5,9, |
<5 4 (2:4 ) = 3,1. |
Итак, в первую |
волну |
вылетов |
войдут |
34 самолета: ni = 34. |
Ко второму рубежу подойдут 37 самолетов, из них полетят даль ше только 14, а так как всего самолетов осталось 46, то во вторую волну следует включить пг = 46(14/23) = 28 самолетов, п3 = 0 (так как х 3 = 0) и в четвертую волну — оставшиеся 18 самолетов.
Анализ полученных результатов показывает, что эффективнее осуществлять планирование на подступах к каждому рубежу, т.е. каждый раз решать задачу, аналогичную рассмотренной.
Продолжая решение, убеждаемся, что эта задача является вы рожденной задачей динамического программирования — планиро вать нужно каждый шаг отдельно, распределяя самолеты перед рубежом так, чтобы получать максимальное число самолетов, пре одолевающих данных рубеж.
§4.5. Вычислительные аспекты решения задач методом динамического программирования
Мы рассмотрели алгоритм решения задач, опирающийся на ос новное функциональное уравнение метода динамического програм мирования
fmax(So) = m ax{/i(S0, æi) + f max(Sm-\(So, æi))b |
(4.4) |
Если f](So, xi) известно, то уравнение (4.4) представляет типич ное рекуррентное соотношение. Чтобы вычислить f max(So), необхо
димо в памяти компьютера иметь |
значения |
функций |
f\(S o ,x \),..., f m- \(S m- 2, хт-\), Sm-i(S o ,x i) |
или алгоритмы для |
|
образования этих значений. |
|
|
Поскольку невозможно запомнить все |
значения |
функции |
f m-\(Sm-2, ï m-i). запоминают лишь дискретный набор значений fm-\((Sm-2, х т—1);)• Другие значения могут быть получены ин терполяцией и экстраполяцией записанных данных. Чтобы найти максимум целевой функции по х\, рассмотрим дискретный набор значений {х\}3, j = 1,2, Одно или несколько значений х\, даю щих максимум, также запомним.
Повторяя эту процедуру на каждом шаге, получаем функцию дохода и функцию стратегии для данного шага. Рекуррентно вычис лим последовательности {fi(Si-\,X i)} и {xj(5i_i)}. Эта процедура является итеративной, что облегчает ее программирование. Отме тим, что как только функция f\(So, ®i) использована для вычисле ния /г (5 ь ^ г ) и Æ2(S I ), ее можно стереть из памяти, и т. д. Чем мень ше область возможных значений Xi, тем меньше требуется объем памяти, тем легче применить метод динамического программиро вания.
Для определенности рассмотрим случай, когда So — вектор раз мерности 2, So = f{x, у), и мы запоминаем значения So в 100 точ
ках по х и по у, т. е. имеем 104 чисел. Этот случай трудностей не вызывает. Если размерность вектора более высокая, скажем 4, то получим 108 чисел.
Для изучения таких процессов на современных компьютерах применяют более тонкие алгоритмы. К примеру, вместо простого запоминания набора значений { /* ($ _ !,а?*)}, г = 1, 2, . . . , в памяти хранят метод воспроизведения функции /,( 5 , - 1, Xi). Наиболее про стой прием такого воспроизведения функции —это представление ее в виде полинома.
Методы динамического программирования эффективнее приме нять к решению задач с дискретными переменными, чем с непре рывными. Основное функциональное уравнение имеет один и тот же вид и для дискретных, и для непрерывных переменных. В от дельных случаях при наличии непрерывных переменных удается сократить расчеты, используя дифференциальное исчисление; од нако в большинстве случаев решаемая задача сводится к задаче с дискретными переменными.
Матод динамического программирования позволяет найти все оптимальные решения, сколько бы их ни было, для любой адди тивной функции многих переменных, которая определена на любом множестве D, заданном условиями-ограничениями.
§ 4.6. Теория игр. Игры в чистых стратегиях
На практике часто имеют место ситуации, когда нашим целям противостоят цели противника. Подобные ситуации называются конфликтными. Примеры подобных ситуаций можно встретить в экономике, военных задачах, в разрешении политических проблем и т. п. Принятие решений каждой из сторон связано с преодолени ем конфликта и затруднено в силу неопределенности поведения
противника.
Естественно, что противник стремится предпринять наименее выгодные для нас действия, чтобы обеспечить себе наибольший успех. Мы не можем точно предсказать действия противника, равно как и он не может точно предсказать наши действия. И, тем не ме нее, как нам, так и ему приходится принимать вполне определенные решения.
Необходимость обосновывать оптимальные решения, принима емые в тех или иных конфликтных ситуациях, привела к возник новению специального направления в современной математике — теории игр. Под термином «игра» здесь понимается упрощенная математическая модель рассматриваемой конфликтной ситуации. В отличие от реального конфликта игра ведется по определенным правилам, которые четко определяют права и обязанности участ ников игры, объем информации каждой стороны о другой, а также исход игры (выигрыш и проигрыш каждого участника).
Задача теории игр состоит в выработке игроками стратегии, ко торая обеспечит одной стороне максимальный выигрыш, а другой — минимальный проигрыш. Теория игр используется в конфликтных ситуациях, которые повторяются многократно.
Задолго до появления теории игр широко использовались подоб ные упрощенные модели конфликтов —игры в буквальным смысле слова: шахматы, шашки, домино, карточные игры и т.д. Отсюда происходит как название самой теории, так и различные термины, используемые в ней. Так, конфликтующие стороны называют игро ками, одну реализацию игры — партией, выбор игроком того или иного действия из возможных (в пределах правил)—ходом и т.д. Различают два вида ходов — личные и случайные. Личный ход пред полагает сознательный выбор игроком того или иного действия, разрешенного правилами игры. Случайный ход не зависит от воли игрока — он может быть определен с помощью датчика случайных чисел.
Игры, состоящие только из случайных ходов, называют азарт ными. Характерный пример — игра в лото. Игры, в которых имеются личные ходы, называются стратегическими. Существуют стратеги ческие игры, состоящие только из личных ходов (например, шах маты). Существуют также стратегические игры, состоящие как из личных, так и из случайных ходов (например, карточные игры). За метим, что в играх с личными и случайными ходами неопределен ность имеет два вида: неопределенность результата случайных хо дов и неопределенность поведения противника в его личных ходах.
В теории игр не исследуют азартные игры, занимаются толь ко стратегическими играми. Задача теории игр —определить такую стратегию игрока, при которой его шансы на выигрыш оказались
бы наибольшими. В основе поиска оптимальных стратегий лежит следующее основное положение: считается, что противник также разумен и активен, как и сам игрок, и предпринимает все меры для того, чтобы достичь успеха.
Разумеется, на практике это не всегда выполняется. Часто на ши действия в реальном конфликте оказываются оптимальными не тогда, когда мы исходим из наиболее разумного поведения про тивника, а тогда, когда удается предвидеть, в чем противник может ошибаться, и воспользоваться его «глупостью». При этом мы рис куем. Известно, как рискованно рассчитывать на «глупость» про тивника. Теория игр не учитывает элементы риска. Она выявляет лишь наиболее осторожные, «перестраховочные» варианты пове дения в данной ситуации. Риски учитываются в другом разделе математики —в теории статистических решений. Можно сказать, что теория игр дает нам мудрые советы. Учитывая эти советы, мы принимаем на практике те или иные решения, часто выбирая со знательно некоторый риск. Теория игр ценна прежде всего самой постановкой задач, которая учит не забывать о том, что противник тоже мыслит, и учитывать его возможные хитрости и уловки. Пусть рекомендации, вытекающие из игрового подхода, не всегда опреде лены и не всегда осуществимы, однако полезно, выбирая решение, ориентироваться, в числе других рекомендаций, и на игровую мо дель. Не стоит только выводы, вытекающие из этой модели, считать окончательными и непререкаемыми.
В теории игр наиболее исследованы конечные парные игры с ну левой суммой. Игра называется парной, если в ней участвуют два игрока. Участников игр может быть более двух, они могут быть объединены в группы. Тогда игра называется коалиционной. Иг ра называется конечной, если каждый игрок имеет конечное число стратегий, т. е. конечное число вариантов поведения, и бесконечной, если хотя бы один из игроков имеет бесконечное число стратегий. Делая личный ход, игрок следует одной из стратегий. Игрой с нуле вой суммой является игра, в которой выигрыш одного игрока равен проигрышу другого.
Оптимальная стратегия игрока — это такая стратегия, которая при многократном повторении игры обеспечивает игроку макси мально возможный средний выигрыш, а другому — минимальный
средний проигрыш. Предположим, что рассматривается некоторая конечная парная игра с нулевой суммой, когда игрок А имеет т стратегий, а игрок В имеет п стратегий (игра т х п). Обозначим стратегии игрока А через А\, А 2 ,. А т, а стратегии игрока В через В\, В 2 ,..., В п. Пусть игрок А, делая личный ход, выбирает некоторую стратегию A i, г = 1, 2, . . . , га, а игрок В —стратегию B j, j = 1,2,..., п. Обозначим через ay реализуемый в этом случае вы игрыш игрока А . Для определенности мы будем отождествлять себя с игроком А и рассматривать каждый ход с позиции выигрыша иг рока А. При этом под выигрышем ay можно понимать как действи тельный выигрыш, так и проигрыш (например, проигрыш можно рассматривать как отрицательный выигрыш). Набор выигрышей ay для разных значений i и j располагают в виде матрицы, строки которой отвечают стратегиям игрока А, а столбцы — стратегиям иг рока В (табл. 4.5). Это есть платежная матрица игры.
Принцип минимакса
Таким образом, задать |
игру —это задать га стратегий игро |
ка А, п стратегий игрока В |
и для пар (Ai, Bj) —задать выигрыш ay. |
Все элементы a y можно увеличить на одно и то же число, чтобы все они стали неотрицательными. Полученная при этом матрица будет эквивалентна исходной. Выбор оптимальной стратегии для игрока А —это выбор стратегии Ai, которая обеспечивает ему мак симально возможный выигрыш, независимо от стратегии игрока В . Игрок А предполагает, что минимальный выигрыш, который он по лучит при стратегии Ai, —это минимальное число в г-й строке. Иг рок В отвечает стратегией, которая минимизирует его собственный проигрыш. С точки зрения игрока А , ему необходимо выбрать та кую стратегию А{, которая максимизирует минимально возможный
выигрыш а = max min aij — максиминная стратегия (максимин).
г 3
Величину a называют еще нижней ценой игры. Меньше, чем а, игрок А выиграть не может. Для игрока В оптимальной страте гией является та, при которой максимально возможный выигрыш игрока А оказывается наименьшим и в любом случае не превос ходит р = min max a y . Величина р называется минимаксом, или
верхней ценой игры. Все параметры игры заносятся в платежную матрицу игры (см. табл. 4.5).
|
Платежная матрица игры |
Таблица 4.5 |
||
|
|
|||
Стратегия |
в, |
в2 |
Bn |
OLi = m in d i j |
|
|
|
|
3 |
А\ |
<2ц |
a \ 2 |
a \n |
a i |
а 2 |
Û21 |
a 2 2 |
0>2n |
a 2 |
А-т |
&ml |
&т2 |
amn |
a m |
Рj = m a x d i j |
Pi |
P2 |
Pn |
|
Максиминная стратегия игрока А так же, как и минимаксная стратегия игрока В, является наиболее осторожной, перестрахо вочной стратегией, и она гарантируют игроку В, что максимально возможный выигрыш игрока А оказывается наименьшим и в любом случае не превосходит минимакса, или, иначе, верхней цены игры. Точно так же при любом поведении игрока В игроку А гарантиро ван минимально возможный выигрыш (наибольший по сравнению с остальными стратегиями) не меньше нижней цены игры (максимина). Принцип осторожности, диктующий игрокам выбор таких стратегий, называется принципом минимакса.
Пример. Рассмотрим следующую игру. Игроки А п В одновре менно и независимо друг от друга записывают одно из трех чисел: либо 1, либо 2, либо 3. Если сумма записанных чисел оказывает ся четной, то игрок В платит игроку А эту сумму; если же сумма чисел оказывается нечетной, то эту сумму выплачивает игрок А игроку В. Игрок А имеет три стратегии: А\ — записать 1, A i —запи сать 2, Аз — записать 3. Стратегии игрока В аналогичны. Рассмат риваемая игра является игрой размеренностью 3 х 3, ее платежная матрица имеет 3 строки и 3 столбца. Эта матрица представлена в табл. 4.6.
Заметим, что выигрыш игрока А, равный, например, — 3, означа ет в действительности его проигрыш, так как в этом случае игрок А выплачивает 3 уел. ед. игроку В.
В матрице (табл. 4.6) одни элементы являются положительны ми, а другие отрицательными. Чтобы все элементы платежной мат рицы были положительными, увеличим каждый элемент рассмат риваемой матрицы на одно и то же число, например на 6. Получим матрицу, представленную в табл. 4.7. С точки зрения анализа опти мальных стратегий эта матрица эквивалентна исходной, но верхняя и нижняя цена игры увеличится на 6. Будем анализировать иг ру, применяя принцип минимакса и используя платежную матрицу, представленную в табл. 4.7.
|
|
Таблица 4 |
.6 |
|
|
Таблица 4 .7 |
|||
Исходная платежная |
|
Редуцированная платежная |
|||||||
матрица |
|
|
|
матрица |
|
|
|||
Стратегия |
В\ |
Вг |
Вг |
Стратегия |
в, |
в 2 |
В3 |
ои |
|
А\ |
2 |
- 3 |
4 |
А, |
8 |
3 |
10 |
3 |
|
а 2 |
- 3 |
4 |
-5 |
|
а 2 |
3 |
10 |
1 |
1 |
Аз |
4 |
- 5 |
6 |
|
Аз |
10 |
1 |
12 |
1 |
|
|
|
|
|
Pi |
10 |
10 |
12 |
|
Предположим, что игрок А выбирает стратегию А \. Тогда в за висимости от того, какую стратегию изберет противник, наш вы игрыш будет равен либо 8, либо 3, либо 10 уел. ед. Итак, выбирая стратегию А \, мы в худшем случае получаем выигрыш 3 уел. ед. Ес ли же мы выбираем стратегию А 2 или стратегию A j, то будем иметь в худшем случае выигрыш 1 уел. ед. Запишем минимально возмож ные выигрыши для разных стратегий Ai в крайнем правом столбце платежной матрицы (см. табл. 4.7). Ясно, что следует выбирать ту стратегию, где минимально возможный выигрыш оказывается наибольшим (по сравнению с остальными стратегиями). В данном случае это есть стратегия А \. Выигрыш 3 уел. ед. является макси мальным в тройке минимальных выигрышей (в тройке 3, 1, 1). По лучим максиминный выигрыш (максимин) — нижнюю цену игры.
Итак, если выбираем максиминную стратегию (в данном случае это стратегия Ai), то при любом поведении противника нам гаран тирован выигрыш не меньше нижней цены игры (в данном случае этот выигрыш равен 3 уел. ед.). Аналогичным образом рассуждает противник. Если он выберет стратегию В \, то в худшем для себя
случае позволит нам получить выигрыш 10 уел. ед. Это же отно сится и к выбору стратегии Вг. При выборе стратегии Вз худший (для противника) случай соответствует нашему выигрышу, равно му 12 уел. ед. Числа 10, 10, 12 —максимальные значения наших выигрышей, отвечающие стратегиям противника В \, Вг, Вз соот ветственно. Выпишем эти значения в нижнюю строку платежной матрицы (см. табл. 4.7). Ясно, что противник должен выбрать ту стратегию, при которой максимально возможный выигрыш игро ка А оказывается наименьшим. Это либо стратегия В \, либо Bj. Обе стратегии являются минимаксными, обе они дают противнику гарантию того, что выигрыш игрока А в любом случае не превысит минимакса, или, иначе, верхней цены игры, равной в данном случае 10 уел. ед. Противник имеет две минимаксные стратегии: В\ и ВгКакую он предпочтет?
Полагая, что мы проявили осторожность и выбрали максиминную стратегию Л ь он, возможно, не станет выбирать стратегию В ь поскольку при этом мы получили бы выигрыш 8 уел. ед. Значит, скорее всего, он выберет стратегию Вг, тогда наш выигрыш будет равен 3 уел. ед. Однако если мы правильно поняли замыслы про тивника, то не следует ли нам рискнуть и выбрать стратегию Лг? Ведь при выборе противником стратегии Вг наша стратегия Лг позволит получить нам выигрыш 10 уел. ед. Однако наше отступ ление от принципа минимакса может дорого нам обойтись. Если противник окажется достаточно хитроумным и проведет такие же рассуждения, то он может ответить на нашу стратегию Лг не стра тегией Вг, а стратегией В 3. И тогда вместо выигрыша 10 уел. ед. мы получим выигрыш всего лишь 1 уел. ед.
Игра с седловой точкой
Теория игр не всегда рекомендует применять минимаксные (максиминные стратегии). Это зависит от того, имеет ли платежная матрица игры седловую точку. Рассмотрим некоторую игру, в ко торой максиминный и минимаксный выигрыши равны, т. е. нижняя
иверхняя цена игры совпадают: а = (3. Выигрыш является одновре менно и максимальным из минимальных выигрышей для игрока Л,
иминимальным из максимальных выигрышей для игрока В. Точ ку на поверхности, являющуюся одновременно точкой минимума