1.7. Анализ чувствительности по отношению к коэффициенту переоценки

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

Пример (Вейнот [111]). Имеются два состояния 1 и 2. В состоянии 1 возможны три решения

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

Следовательно,

при Вид функции в зависимости от показан на рис. 2.

Для этой задачи является -оптимальным при -оптимально, а -оптимально при

Рис. 2. Суммарный средний доход с учетом переоценки, как функция от коэффициента переоценки .

Заметим, что все -оптимальны. Разбиение множества значений коэффициента переоценки на области, соответствующие различным оптимальным стратегиям, для примера Вейнота показано ниже:

Рассмотрим пример 2 из предыдущего раздела (задачу водителя такси). Ховард [63] нашел зависимость оптимальной стратегии от коэффициента переоценки для этой задачи:

Из приведенных диаграмм видно, что существует такая точка в которой две или три стратегии являются оптимальными. Такая точка называется критической [63] или точкой безразличия [106]. Например, является точкой безразличия для первого примера. Заметим также, что существуют две стратегии, отличающиеся лишь решениями, принимаемыми в одном из состояний, для которых точка безразличия. Можно представить случай, когда существуют две стратегии, имеющие точку безразличия которые отличаются друг от друга решениями, принимаемыми в двух или большем числе состояний. Ниже показан такой случай, однако он нереализуем.

Имеет место следующее утверждение.

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

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

Следовательно,

или

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

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

Мы не приводим здесь алгоритма нахождения точек безразличия, подробное описание которого содержится в работе Смолвуда [106].

Интересной задачей является анализ поведения при Она подробно рассматривается в гл. 3.

Ссылки и комментарии

Теория цепей Маркова излагается во многих стандартных учебниках по теории вероятностей или теории марковских процессов, например, в книгах Кемени и Снелла [70], Феллера [56], Баручи-Рида [12], Карлина [68], Дуба [50] и Чжун Кайлая [23].

Марковские процессы принятия решений с переоценкой впервые были рассмотрены Ховардом [63], им же был предложен итерационный алгоритм нахождения стратегий. Блекуэлл [14] дал строгий анализ этого процесса и доказал существование стационарной

Р-оптимальной стратегии (следствие к теореме 1.3). Блекуэллу также принадлежат лемма 1.1 и теоремы 1.1, 1.2, 1.3.

Существование стационарных -оптимальных и -оптимальных стратегий независимо от Блекуэлла было доказано Дерманом [36] и Висковым и Ширяевым [126].

Формулировка задачи с переоценкой в виде задачи линейного программирования впервые была дана Депену [48]. Результаты раздела 1.3 принадлежат Де Хелинку и Эпану [28]. Общая теория линейного программирования содержится, например, в книге Данцига [25].

Пример 2 из раздела 1.6 разобран в работе Ховарда [63]. Там же рассматриваются и другие интересные задачи — об игре в бейсбол и о замене автомобиля. Последняя будет рассмотрена в разделе 2.6 в качестве примера модели без переоценки.

Теорема 1.7 принадлежит Смолвуду [106], который также дал алгоритм нахождения точек безразличия, используя теорему Гамильтона — Кэли из линейной алгебры.

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

Мак-Куин [80] рассмотрел с позиции динамического программирования метод последовательных приближений, дающий монотонную сходимость к -оптимальной стратегии, и показал [81] эффективность предложенного алгоритма.

Вторая задача заключается в исследовании марковского процесса принятия решений специального вида, для которого Такой процесс называется сепарабельным [28]. Задача Ховарда о замене автомобиля (которая будет рассмотрена в разделе 2.6) является задачей такого типа. Для сепарабельного процесса Де Хелинк и Эпан [28] и Денардо [32] предложили простой алгоритм и изучили его свойства.

Наконец, упомянем так называемую магистральную теорему. Обозначим время планирования и зафиксируем число Магистральная теорема утверждает, что существует такое число что -оптимальная стратегия, вычисленная для любого совпадает с одной из -оптимальных стратегий, вычисленных для Эту теорему доказал Шапиро [104], он же нашел верхнюю оценку величины