Тема 1.4. Многошаговые игры. Игры погони

Простейшим примером таких игр может служить задача для двух игроков, расположившихся на прямой на расстоянии d. На каждом шаге игры игроки могут одновременно смещаться влево или вправо при полной информации о позиции друг друга После очередного шага игрок 2 уплачивает игроку 1 величину G(S), где S - расстояние между ними. С вероятностью A(d) игра может быть продолжена и с вероятностью 1-A(d) окончена.

Если обозначить через P₁, P₂, Q₁, Q₂ вероятности смещения игроков в ту или иную сторону, то одна из возможных формулировок задачи имеет вид

Существенно больший интерес может представить игра погони на плоскости или в пространстве, где устанавливается принципиальная возможность поимки одного игрока другим или отыскивается траектория, минимизирующая время поимки. Эти игры относятся к т.н. непрерывным многошаговым играм, решение которых сводится к дискретным моделям [18].

Тема 1.5. Статистические решения. Основные понятия.

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

Выбор наилучших решений в условиях неполной информации является одним из основных занятий людей.

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

Проектируя гидротехнические сооружения, мы стремимся сделать их надежными, несмотря на непредсказуемые землетрясения, паводки и т.п.

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

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

Однако большинство процессов характеризуется "дурной неопределенностью" и невозможно найти законы распределения и другие вероятностные характеристики. В таких ситуациях приходится прибегнуть к экспертным оценкам.

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

Пусть задан некоторый вектор S = (S₁,S₂,..,S_n), описывающий n состояний внешней среды, и вектор X = (X₁,X₂,..,X_m), описывающий m допустимых решений. Требуется найти вектор X^* =(0,0,..,0, X_i ,0,..,0), который обеспечивает оптимум некоторой функции полезности W(X,S) по некоторому критерию K.

Информация oб указанной функции представляют матрицей размерности m x n c элементами W_ij = F(X_i, S_j), где F - решающее правило.

Рассмотрим типичный пример формирования такой матрицы

Планируется выпуск новой продукции, для чего необходимо закупить станки. Система оптовой торговли может поставить не более 50 станков; комплект поставки - 10 станков. Минимальный объем поставок - 20 станков. Соответственно, вектор решений об объеме поставок X = (20,30,40,50).

Ежегодный доход от продукции, снимаемой с одного станка, cоставляет 21.9 тыс.руб. Оптовая цена одного станка 4.775 тыс.руб., эксплуатационные расходы - 3.6 тыс. руб. Затраты на подготовку производства составляют 25.5 тыс.руб. и не зависят от числа станков и объема выпуска.

Пусть спрос пропорционален количеству продукции, снимаемой с S работающих станков, и для простоты ограничимся вектором состояний спроса S = (0,10,20,30,40,50).

Если решающее правило сформулировать как "доход - издержки", то можно рассчитать элементы матрицы полезности:

W_ij = (21.9 - 3.6) * min( X_i, S_j) - 4.775 X_i - 25.5

Например

W₁₁ = -(4.775 20+25.5) = -121,
W₁₂ = (21.9-3.6) * 10-(4.775 20+25.5) = 62,
W₁₃ = (21.9-3.6) * 20-(4.775 20+25.5) = 245,
W₁₄ = W₁₅ = 245 (спрос останется неудовлетворенным).

Глава 2. Выбор критерия принятия решения

Предположим, что в нашем распоряжении имеются статистические данные, позволяющие оценить вероятность того или иного спроса, и этот опыт может быть использован для оценки будущего. При известных вероятностях P_j для спроса S_j можно найти математическое ожидание W(X,S,P) и определить вектор X^*, дающий

Если для вышеприведенного примера задать вектор P = (0.01, 0.09, 0.2, 0.3, 0.3, 0.1), то математические ожидания прибыли при разных выборах:

W₁ =-121*0.01 + 62*0.09 + 245*0.2 + 245*0.3 + 245*0.3 + 245*0.1 = 224.87,

W₂ = 305.22, W₃ = 330.675, W₄ = 301.12

и выбор максимального значения обнаруживает оптимальность варианта 40 станков с ожидаемой прибылью 330.675 тыс.руб.