21. Доминируемые стратегии.

Если в платежной матрице Р все элементы i –й строки не меньше соответствующих элементов k-й строки, а aij ≥akj, j=1,n, а по крайней мере один строго больше, то

i-я строка называется доминирующей, а k-я строка доминируемой.

22. Решение игр в смешанных стратегиях.

Если , то применение чистых стратегий не дает оптимального решения игры. Его можно получить случайным образом чередуя чистые стратегии, т.е в смешанных стратегиях.

ОПРЕДЕЛЕНИЕ: Смешанной стратегией SА игрока А называется применение

m

чистых стратегий А1,А2,….., Аm с вероятностями p1,p2,…..,pm, pi = 1.

i=1

S А = А1 А2 … Аm

P1 P2 … Pm

Аналогично для игрока В:

B1 B2 … Bn n

SB = q1 q2 … qn ,  qj=1

j=1

ТЕОРЕМА НЕЙМАНА: Каждая конечная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.

23. Графическое решение игр вида 2n и m2.

У таких игр всегда имеется решение, содержащее не более двух активных стратегий для каждого из игроков. Если найти эти активные стратегии, то игра 2 х n или m х 2 сводится к игре 2 х 2.

Д ля игры m*2 решение находится совершенно аналогично. Действительно, поскольку выигрыш игрока А одновременно является проигрышем игрока В, то для решения задачи нужно построить ломаную, соответствующую верхней границе выигрыша игрока А, а затем найти на ней точку с минимальной ординатой.

24. Метод динамического программирования. Принцип оптимальности и уравнение Беллмана.

Метод динамического программирования состоит в том что оптимальное управление строится постепенно. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учётом последствий, так как управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным  с точки зрения процесса в целом. Это основное правило динамического программирования, сформулированное Беллманом, называется принципом оптимальности.

Так, если система в начале k - шага находится в состоянии   и мы выбираем произвольное управление  , то она придет в новое состояние в  , и последующие управления  должны выбираться оптимальными относительно состояния  . Последнее, означает, что этих управлениях максимизируется  величина  , то есть показатель эффективности на последующих до конца процесса шагах  . Обозначим через  .

Выбрав оптимальное управление   на оставшихся   шагах, получим величину  , которая зависит только от  , то есть  .

Назовем величину   условным максимумом. Если мы теперь выберем на k-м шаге некоторое произвольное управление  , то система придет в состояние  . Согласно принципу оптимальности, необходимо выбирать управление  так, чтобы оно в совокупности с оптимальным управлением на последующих шагах (начиная с (k+1)-го) приводило бы к общему показателю эффективности на    шагах, начиная с k-uго и до конца. Это положение в аналитической форме можно записать в виде следующего соотношения:

,

 ,      (1)

получившего название основного функционального уравнения динамического программирования, илиосновного рекуррентного уравнения Беллмана.

Из уравнения (1) может быть получена функция  , если известно функция  . Аналогично можно получить  , если известно   и т. д., пока не будет определена величина  , представляющая по определению максимальное значение показателя эффективности процесса в целом:

.

Решая уравнение (1) для определения условного максимума показателя эффективности за   шагов, начиная с k-го, мы определяем соответствующее оптимальное управление  , при котором этот максимум достигается. Это управление также зависит от  ; будем обозначать его через   и называть условным оптимальным управлением на k-м шаге. Основное значение уравнения (1), в котором реализована идея динамического программирования, заключается в том, что решение исходной задачи определения максимума функции   n переменных   сводится к решению последовательности nзадач, задаваемых соотношениями (1), каждое из которых является задачей максимизации функции одной переменной  .

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

Если начальное состояние   задано  , то непосредственно

определяют максимум целевой функции

,

а затем - искомое безусловное оптимальное управление по цепочке

.                  (2)

Если задано множество  начальных состояний  , то дополнительно решают еще одну задачу на максимум

,

откуда находят  , а затем по цепочке (2) - безусловное оптимальное управление.

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

Приведем рекуррентные соотношения для этого случая. Уравнения со­стояний для прямого хода удобно записывать в виде

.

Введем в рассмотрение условные максимумы показателя эффективности за k шагов, от 1-го до k-говключительно, - величину  . Повторив приве­денные рассуждения, придем к следующей системе уравнений Беллмана:

;

.

В результате решения этих уравнений получим последовательности

;  .

Далее определим безусловное оптимальное управление по цепочке

.