Программа дисциплины (syllabus) (стр. 8 )

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

,

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

.  (5)

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

,

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

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

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

Введем  в  рассмотрение  условные  максимумы показателя эффективности за

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

;

.

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

.

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

.

Тема 7 Исследование операций.

План

1)Предмет, история становления и перспективы развития исследования операций.

2)Принятия решений и элементы теории игр.

Краткое изложение материала

Описание игры включает перечень участников конфликта, задание множеств возможных действий и оценок эффективности этих действий для каждого из них. Участников конфликта принято называть игроками. Обозначим множество всех игроков через . Далее будем считать множество N конечным. Игроков принято различать по их номерам, т. е. считать ={1,2, ..., n}. Множество возможных действий i-го игрока обозначим через . Элементы этого множества принято называть стратегиями. Каждый игрок имеет не менее двух различных стратегий, в противном случае его действия заранее определены и фактически он не участвует в игре. В результате выбора i-м игроком стратегии  складывается система стратегий , которая называется ситуацией. Эффективность возможных действий игроков мы будем оценивать теми выигрышами, которые игроки получают в каждой ситуации s. Выигрыш игрока i в ситуации s обычно обозначается через  Функция , определенная на множестве всех ситуаций, называется функцией выигрыша игрокаi. Цель i-го игрока - максимизация своей функции выигрыша.

Данный способ описания игры заключается в том, что рассматриваются все возможные стратегии каждого игрока и определяются выигрыши, соответствующие любой возможной ситуации. Описанная таким образом игра называется бескоалиционной игрой n лиц в нормальной форме

.  (1)

Игра (1) называется антагонистической, если в ней участвуют два игрока и значения функций выигрыша в каждой ситуации равны по величине и противоположны по знаку.

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

Г = <А, В, Н>,  (2)

где А и В - соответственно множества стратегий игроков I и II, а Н - функция выигрыша игрока I.

Конечная антагонистическая игра в нормальной форме называется матричной игрой.

Это название можно объяснить следующей возможностью описания игр такого рода. Поскольку множество возможных действий каждого из игроков в этом случае конечно, можно положить А = {1, 2, ..., m}, В = {1, 2,..., n}, где m и n — соответственно число стратегий игроков I и II, а значения функции Н представить в виде следующей матрицы:

Здесь - выигрыш игрока I в ситуации (i, j), где i - номер строки (стратегия игрока I), j - номер столбца (стратегия игрока II). Матрица Н называется матрицей игры или матрицей выигрышей.

Матричная игра полностью определяется своей матрицей выигрышей. Поэтому часто вместо выражения “игра с матрицей выигрышей Н” употребляется выражение “игра Н”.

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

Принцип максимина (минимакса)

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

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

.

Величину

 (3)

принято обозначать через  (или просто v) и называть нижним значением (нижней ценой) игры, а соответствующую этому значению стратегию i° игрока I - максиминной стратегией. Если игрок I придерживается данной стратегии, то его выигрыш будет не меньше максиминного значения, то есть

 (4)

Аналогично стратегия j°, определяемая равенством

называется минимаксной стратегией игрока II, а соответствующее значение  (или просто ) - верхним значением (верхней ценой) игры.

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

 (5)

Полагая, что в неравенстве (4) j = j°, а в выражении (5) i = i°, получим:

 (6)

Принцип, которого придерживается игрок I, называется принципом максимина, так как его гарантированный выигрыш равен величине (3). Игрок IIтакже придерживается этого принципа, так как

.

Из неравенства (6) следует, что во всякой матричной игре .При этом возможны два следующих случая:

.  (7)

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

Вопрос о разделе между игроками разности  (а в рассматриваемом случае она положительна) остается, таким образом, открытым. Это влечет за собой неопределенность в действиях игроков.