Глава 4. Динамическое программирование и марковские процессы

4.1. Введение

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

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

4.2. Динамическое программирование

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

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

Из (4.1) получаем следующее рекуррентное соотношение:

Определение 4.1. Стратегия называется оптимальной, если для любой стратегии а и любого выполняется неравенство

Для нахождения оптимальной стратегии воспользуемся принципом оптимальности и методом динамического программирования.

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

Принцип оптимальности был впервые сформулирован Беллманом [7]. Используя этот принцип, получаем рекуррентное соотношение

справедливое для всех и любого где

для всех Соотношения (4.3), (4.4) позволяют находить оптимальную стратегию. В разделе 4.3 будет приведен иллюстрирующий пример.

Отметим, что метод динамического программирования применим и в случае, когда величины и зависят от при этом рекуррентные соотношения (4.3) и (4.4) остаются справедливыми.

Итак, мы рассмотрели задачу нахождения оптимальной стратегии для случая конечного времени планирования. Займемся теперь изучением оптимальных стратегий для процессов с бесконечным временем планирования. Предположим, что величины и не зависят от Воспользуемся снова оператором переводящим -мерный вектор X в вектор той же размерности. Для любой стратегии и любого -мерного вектора определим

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

при условии, что в момент окончания последнего перехода выплачивается сумма, равная компоненте вектора X, если при этом процесс попадает в состояние . В частности, получаем, что

Определение 4.2. Стратегия называется -оптимальной, если для любой стратегии а и любого выполняется неравенство

Из приведенного определения следует, что стратегия является оптимальной тогда и только тогда, когда она -оптимальна.

Лемма 4.1. Для любого элемента имеет место равенство

где при (см. теорему 3.1).

Доказательство. Из теоремы 3.1 имеем

где при

Определим оператор равенством . В частности, совпадает с оператором

Лемма 4.2. Имеет место следующее равенство:

Доказательство. Из определения и формулы (2.3) имеем

Лемма 4.3. Если оптимальная стратегия, то для любого элемента либо

либо

Доказательство. Из теоремы 3.2 следует, что если — оптимальная стратегия, то либо либо для любой стратегии . В силу (4.8) имеем

а из теоремы 3.1 получаем, что

и

Таким образом, если то из неравенства следует, что т. е.