Материалы по курсу (часть 2)

динамического программирования, выражающее Wi(Si-1) через уже известную функцию

Wi+1(Si),

Этому условному оптимуму целевой функции соответствует условное оптимальное управление на i-м шаге xi(Si-1), которое совместно с оптимальным управлением на всех последующих шагах обращает целевую функцию на всех оставшихся шагах, начиная с данного, в минимум.

5. Произвести условную оптимизацию последнего, m-го шага, задав множество состояний Sm-1, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого Sm-1 условный оптимум целевой функции по формуле

и находя условное оптимальное управление xm(Sm-1), для которого этот минимум достигается.

6. произвести условную оптимизацию (m-1)-го,(m-2)-го и т. д. шагов по формуле

, полагая в ней i=(m-1),(m-2),… и для каждого шага указать условное оптимальное управление xi(Si-1), при котором достигается минимум.

Так как начальное состояние системы S0 одно, и оно известно, то на первом шаге варьировать состояние системы не нужно – оптимальное значение целевой функции для S0 находится непосредственно. Это и есть оптимум функции цели за весь процесс перевода:

7. Произвести безусловную оптимизацию управления, учитывая выработанные ранее рекомендации на каждом шаге. На первом шаге оптимальное шаговое управление 1 =1(0). Пользуясь = (−1, ), находим изменившееся состояние системы S1, для него определяем оптимальное управление на втором шаге 2 и т. д. до конца.

Т.к. мы применяем условные вероятности, то

∑ (( )| −1, ) = 1

Пример 1:

Решается задача управляемого перевода организма из исходного состояния S0 в конечное состояние S3 (лечение, нормализация состояния оператора). При этом существуют

промежуточные состояния 1(1), 1(2), 1(3), 2(1), 2(2), а возможные переходы их состояния в состояние изображены на рис.2.11 в виде ориентированного ациклического графа. На ребрах графа проставлено время, требуемое для перевода организма из одного состояния в другое. В каждом состоянии Si-1 имеется несколько управляющих воздействий xi, которым соответствуют определенные наборы вероятностей перехода ( | −1, )

Сумма чисел в каждой строке

= 1

Кроме того, в состоянии 2(1) всегда применяется управление x3(1) и (3 | 2(1), 3(1)) =

1, а в состоянии 2(2) всегда применяется x3(2)

Требуется каждому состоянию сопоставить одно оптимальное управляющее воздействие, при котором общее среднее время перехода из в будет минимально, а также определить это время.

Времена перехода организма из состояния в состояние равны:

Условную оптимизацию, как и раньше, начинаем с последнего, 3-го шага управления. Из условия задачи видно, что на 3-м шаге управление вынужденное, поэтому

̅ (2(1)) = 31 = 3

В течение ближайших 3-х дней больному необходимо сделать срочную операцию. Для уменьшения риска неблагоприятного исхода желательно, чтобы состояние больного непосредственно перед операцией было наилучшим. С помощью медицинских обследований состояние больного оценивают по трехбалльной шкале, причем оценка 1 соответствует наихудшему состоянию S1, 2 – промежуточному S2, 3 – наилучшему S3. Надо рассчитать оптимальную стратегию врача (т.е. в какой из трех дней лучше всего делать операцию), если вероятности наступления состояний S1, S2, S3, и в любой день не зависят от состояния больного в предыдущий день и равны

p1=P(S1) =0,3; p2=P(S2) =0,5; p3=P(S3) =0,2;

Для решения этой задачи составим дерево альтернатив, изображенное на рис.2.13 Пусть zi - оценка состояния больного, а xi - принимаемое решение в i-й день. Тогда после измерения состояния больного в 1-й день (Изм1), если z1=3, то x1=[On], т.е. принимается решение оперировать; если z1=1, то x1=[Жд]- ждать следующего дня, а если z1=2, то возникает неопределенность (может быть принято, как одно, так и другое решение). Аналогичная ситуация возникает и на второй день после процедуры Изм2, если в 1-й день принято решение [Жд]. Таким образом задача заключается в выработке рекомендаций о принятии оптимальных решений, если в 1-й или во 2-й день состояние больного будет оценено как 2.

В качестве критерия оптимальности (целевой функции) будем использовать среднеожидаемую оценку состояния оперируемого больного, которую необходимо максимизировать. Пусть wi(j)- значение целевой функции на i-й день при zi=j. Допустим, больного решили оперировать лишь на 3-й день. В этом случае среднеожидаемая оценка состояния больного перед операцией будет равна (рис. 2.14).

̅3 = 3(1) 1 + 3(2) 2 + 3(3) 3 = 1 0,3 + 2 0,5 + 3 0,2 = 1,9

Этот результат показывает, что если на 2-й день мы получили z2=2, то (так как это больше, чем 1,9) наилучшим будет решение x2=<On> и для второго дня дерево альтернатив представляется в виде рис. 2.15. Из рисунка видно, что w2(1) = w̅3.Рассуждая аналогично, среднеожидаемая оценка состояния больного на 2-й день

̅2 = 2(1) 1 + 2(2) 2 + 2(3) 3 = 1,9 0,3 + 2 0,5 + 3 0,2 = 2,17

Это больше, чем 2, поэтому, если в 1-й день будет z1=2,то оптимальным решением будет воздержаться от операции в надежде на улучшение состояния больного в оставшиеся два дня, и дерево альтернатив для первого дня приобретает вид рис. 2.16. Из этого рисунка видно, что w1(1)=w1(2)=w̅2. Наконец, среднеожидаемая оценка состояния больного в 1-й день

̅1 = 1(1) 1 + 1(2) 2 + 1(3) 3 = 2,17 0,3 + 2,17 0,5 + 3 0,2 = 2,226

Это среднеожидаемая оценка состояния оперируемого больного, полученная за счет использования двух резервных дней. В случае, если бы эти дни не предоставлялись и больной бы оперировался всегда в 1-й день, среднеожидаемая оценка его состояния, как подсчитано выше, равнялась бы 1,9.

Таким образом, оптимальной стратегией врача будет следующая. Если в первый день состояние больного оценено на 3, то в этот день проводится операция. В случае же, если в первый день состояние больного оценивается меньше, чем на 3, решение об операции

откладывается до следующего дня. Если на второй день состояние больного оценивается на 3 или на 2, то в этот день проводится операция. Если во второй день состояние больного оценено на 1, то операция откладывается на 3-й день. При такой тактике мы рассчитываем, что в момент операции состояние больного в среднем окажется равным 2,336 (вместо 1,9 при чисто случайной тактике).

В данном примере вместо хирургической операции могут, конечно, рассматриваться и другие существенные воздействия на организм человека, успешность применения которых критична к состоянию человека, меняющемуся во времени. Можно также переформулировать эту задачу как нахождение оптимального выбора момента выполнения ответственных действия человеком (спортивных достижений; специальных заданий, выполняемых в экстремальных условиях) в ограниченном интервале времени в условиях меняющегося во времени его физиологического или психологического состояния. При этом считается, что во всех промежуточных точках заданного интервала времени состояние человека может быть оценено количественно. Задачу можно существенно усложнить, если ввести зависимость данного состояния от предыдущего.

13. Игровые методы обоснования решений. Основные понятия теории игр. Платежная матрица.

Рассмотрим игру (модель конфликтной ситуации), в которой участвуют два игрока A и B, имеющие прямо противоположные интересы, поэтому выигрыш одного равен проигрышу другого. Такая игра называется парной игрой с нулевой суммой. Если игрок A выигрывает a, то игрок B при этом выигрывает -a, поэтому сумма выигрышей всегда равна нулю. Процесс игры заключается в последовательных ходах (личных – сознательных и

случайных) противников, а совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от сложившейся ситуации называется стратегией игрока. При конечном числе стратегий игра будет конечной. Пусть у игрока A имеется m возможных стратегий A1, A2, …, Am, а у игрока B – n возможных стратегий B1, B2, …, Bn. Пусть также известны величины aij – выигрыши игрока A при использовании Ai с его стороны и Bj со стороны противника. Тогда игра, называемая игрой m × n, может быть представлена таблицей, называемой платежной матрицей или просто матрицей игры.

Платежная матрица (матрица игры)

Приведение игры к матричной форме может само по себе составить трудную задачу, однако таким путем многоходовая игра фактически сводится к одноходовой – от игрока требуется сделать только один ход: выбрать подходящую стратегию. Для данного игрока

среди всех стратегий имеется оптимальная, обеспечивающая ему максимальный выигрыш. Задача теории игр – нахождение оптимальных стратегий игроков в

предположении одинаковой «разумности» противников.

14. Нижняя и верхняя цена игры. Принцип минимакса. Решение игры в чистых стратегиях.

Каждый игрок выбирает для себя наиболее выгодную стратегию. При этом первый игрок стремится выбрать такую стратегию, которая доставляет ему максимальный выигрыш,

тогда как второй игрок выбирает стратегию, приводящую его к минимальному проигрышу. В

этой связи вводят понятия нижней и верхней чистой цены игры.

По матрице игры определяются нижняя и верхняя цены игры.

Нижней чистой ценой игры (максимином) называется число, определяемое по формуле:

Верхней чистой ценой игры (минимаксом) называется число, определяемое по формуле:

Принцип минимакса:

Принцип выбора противниками стратегий, соответствующих получению ими выигрышей и .

Принцип осторожности, заставляющий игроков придерживаться максиминной и минимаксной стратегий соответственно, а минимаксную стратегию и максиминную стратегию называют общим термином «Минимаксные стратегии»

Известно, что минимаксные стратегии устойчивы по отношению к информации о поведении другой стороны только в случае, если = . В этом случае матрица игры имеет седловую точку, а величина = = называется ценой игры.

Оптимальные чистые стратегии – стратегии и , при которых достигается выигрыш .

Совокупность этих стратегий – решение игры

(Иными словами: Целью участников любой матричной игры является выбор наиболее выгодных стратегий, доставляющих игроку А максимальный выигрыш, а игроку В минимальный проигрыш.

Определение. Чистую стратегию Ai игрока А называют оптимальной, если при ее применении выигрыш игрока А не уменьшается, какими бы своими стратегиями не пользовался игрок В.

Оптимальной для игрока В называют чистую стратегию Bj, при использовании которой проигрыш игрока В не увеличивается, какие бы стратегии не применял игрок А.)

Пример 1 — Самая простая конечная игра – игра 2х2. Ее матрица имеет вид таблицы. Если для этой матрицы = , то игра имеет седловую точку и ее решение – это пара чистых стратегий, пересекающихся в седловой точке.

Пример 2 — Найти нижнюю и верхнюю цены игры с платежной матрицей

32 1 4

= (10 4 3 10)

−2 4 1 2

В каждой строке платежной матрицы найдем наименьший элемент и запишем его справа от матрицы. В каждом столбце платежной матрицы найдем наибольший элемент, и

запишем его снизу от матрицы. В результате получим таблицу

Нижняя цена игры = {1,3, −2} = 3

Верхняя цена игры = {10,4,3,10} = 3= , цена игры =3