Макеты страниц 4.3. Свойства оптимальной стратегииВ отличие от бесконечного времени планирования, в рассматриваемом случае оптимальная стратегия не обязательно стационарна. Рассмотрим следующий пример. Пример. Пусть имеется система, которая в каждый момент времени может находиться в одном из двух состояний 1 или 2. В состоянии 1 существуют два решения. При первом система получает доход, равный 1, и с вероятностью одношаговых доходов имеют вид
Таким образом,
и Найдем теперь оптимальную стратегию для случая конечного времени планирования. Пусть
Для произвольного Обозначим любое из трех отношений Для получения асимптотики суммарного среднего дохода в случае периодической стратегии нужно лишь уметь находить такую асимптотику для стационарной стратегии. В частности, в разобранном выше примере для вычисления величины Лемма 4.4 а) Если матрица
б) Если
где Доказательство. Будем для краткости вместо а) Так как
б) Так как
Кроме того,
т.е
Полагая
получаем утверждение б). Применим теперь лемму 4,4 к рассмотренному выше примеру. Заметим, что
Тогда в силу леммы 4.4 имеем
Покажем, как связаны оптимальные стратегии для процессов с конечным и бесконечным временами планирования. Лемма 4.5. Пусть Доказательство.
Из леммы 4.3 получаем, что при всех достаточно больших
Но из леммы 4.2 следует, что
Таким образом, для любой стратегии
для всех значений Теорема 4.1. Пусть Доказательство. По определению
а последний член в правой части равномерно ограничен по сделанному предположению о неограниченности данной разности сверху. Следствие 1. Разность Доказательство. Заметим, что
Но в силу лемм 2.4 и 4.4 выражения, стоящие в скобках, равномерно ограничены по Следствие 2. Если элемент Доказательство.
Переходя к пределу в (4.27) по подпоследовательности Покажем, что
существует при каждом Для этого достаточно доказать, что Заменим повсюду Пусть Лемма 4.6. Пусть
для всех
Доказательство. Пусть для определенности
что противоречит сделанному предположению. Таким образом,
Меняя местами
Обозначим Приведем теперь две леммы, которые будут существенно использованы при доказательстве теоремы 4.2. Лемма 4.7. Если ли и
Доказательство. Для любой стратегии
где
откуда следует утверждение леммы. Лемма 4.8. Пусть Доказательство. Так как
где Заметим, что
Отсюда вытекает, что все предельные для Обозначим Пусть имеется бесконечно много точек
где
выполняется для бесконечного числа выбранных точек. Таким образом, у бесконечного числа выбранных точек будут совпадать по крайней мере две координаты, т. е. Докажем теперь теорему об асимптотической периодичности Теорема 4.2. Если
существует при каждом I, где Доказательство. Предположим, что в оптимальной стратегии конечное число раз. Тогда можно выбрать такое
где Применяя лемму 4.7, получаем
И, наконец, из леммы 4.8 следует, что Следствие. Для всякого
Доказательство. Пусть
где Ссылки и комментарии Все результаты этой главы принадлежат Брауну [19], который рассмотрел также специальный случай, когда все элементы матрицы утверждающая, что последовательность векторов Общая теория динамического программирования содержится в книгах Беллмана [7], [8], Беллмана и Дрейфуса [9]. Формулировка задачи линейного программирования применительно к марковским процессам принятия решений с конечным временем планирования была дана Дерманом и Клейном [43], но мы ее здесь не рассматриваем. Представляет также интерес магистральная теорема, доказанная для процессов, изучавшихся в этой главе (см. Шапиро [1041). Аналогичные задачи рассматривал Юшкевич [146] в связи с понятием канонических стратегий.
|
Оглавление
|