Каждой стационарной стратегии соответствуют свои матрицы переходных вероятностей и доходов, которые можно построить на основе матриц Р1, Р2, R1 и R2. Например, для стационарной стратегии, требующей применения удобрения только тогда, когда состояние почвы плохое (состояние 3), результирующие матрицы переходных вероятностей и доходов задаются следующими выражениями.

Эти матрицы отличаются от Р1 и R1 только третьей строкой, включенной в них из матриц Р2 и R2. Причина этого в том, что Р2 и R2 - матрицы, соответствующие ситуации, когда удобрения применяются при любом состоянии почвы.

УПРАЖНЕНИЯ 19.1

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

2. Определите все стационарные стратегии в примере с садовником.

19.2. МОДЕЛЬ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С КОНЕЧНЫМ ЧИСЛОМ ЭТАПОВ

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

Пусть k = 1 или 2 обозначает две возможные (альтернативные) стратегии поведения садовника. Матрицы Рк и Rk, представляющие переходные вероятности и функцию дохода для альтернативы k, определены в разделе 19.1; здесь они приводятся для удобства.

Р2 =

Задачу садовника можно представить как задачу динамического программирования (ДП) с конечным числом этапов следующим образом. Пусть число состояний для каждого этапа (года) равно т (3 в примере с садовником). Обозначим через fn(i) оптимальный ожидаемый доход, полученный на этапах от п до N включительно при условии, что система находится в начале этапа п в состоянии L

Обратное рекуррентное уравнение, связывающее fn и fn+1, можно записать в виде

/ (/) = maxjf>,;(у)]}, = 1,2, ...,N,

где fN+l(J) = 0 для всех j.

Приведенное уравнение основано на том, что накапливающийся доход rl + fn*iU) получается в результате перехода из состояния I на этапе п в состояние /

на этапе п + 1 с вероятностью / *. Введя обозначение

рекуррентное уравнение ДП можно записать следующим образом:

A(/) = max{vf},

/ (/) = maxvf+Xp*/ +l(y)J, = 1,2, ...,N-l.

Проиллюстрируем использование рекуррентного уравнения для вычисления величин v* в задаче садовника для ситуации, когда удобрения не применяются (k = 1).

у,1 =0,2x7 + 0,5x6 + 0,3x3 = 5,3,

v\ =0x0 + 0,5x5 + 0,5x1 = 3,

Ц=0х0 + 0х0 + 1х(-1) = -1.

Эти значения показывают, что если состояние почвы в начале года оказывается хорошим (состояние 1), то при одном переходе ожидаемый годовой доход составляет 5,3. Аналогично, если состояние почвы удовлетворительное, ожидаемый годовой доход составит 3, а в случае плохого будет равен -1.

Пример 19.2.1

В этом примере задача садовника решается при данных, заданных матрицами Р1, Р2, R1 и R2. Предполагается, что горизонт планирования включает 3 года (N= 3).

Так как значения v* многократно используются в вычислениях, для удобства они

сведены в таблицу. Напомним, что значение к = 1 соответствует решению не удобрять , к = 2 - удобрять .

Этап

Оптимальное решение показывает, что в 1-й и 2-й годы садовник должен применять удобрения (к = 2) независимо от состояния системы (состояния почвы по данным химического анализа). На 3-й год садовнику следует применять удобрения только тогда, когда система находится в состояниях 2 или 3 (т.е. при удовлетворительном или плохом состоянии почвы). Суммарный ожидаемый доход за три года составитyj(l) = 10,74 при хорошем состоянии системы в 1-й год,/,(2) = 7,92 - при удовлетворительном состоянии системы в 1-й год и/ДЗ) = 4,23 - при плохом состоянии.

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

В первом случае значения доходов и переходные вероятности />* должны

быть функциями этапа п. Здесь рекуррентное уравнение динамического программирования принимает вид

/A.(.-) = max{vf- },

Второе обобщение заключается в следующем. Пусть а(< 1) - годовой коэффициент переоценки (дисконтирования), тогда D долларов будущего года равны aD долларам настоящего года. При введении коэффициента переоценки исходное рекуррентное уравнение преобразуется в следующее:

/ (;) = max