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

 

Модель вероятностного динамического программирования

с конечным числом этапов

 

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

Пусть обозначает две возможные (альтернативные) стратегии поведения фирмы. Будем использовать матрицы переходных вероятностей и функций дохода , заданные формулами (1)-(4).

Задачу ВДП можно сформулировать следующим образом. Пусть число состояний для каждого этапа (года) равно m (в нашей задаче m = 3).

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

Обратное рекуррентное соотношение, связывающее , имеет вид:

причем

 

Уравнение (5) учитывает то, что накапливающийся доход образуется в результате перехода из состояния на этапе n +1 с вероятностью . Введя обозначение

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

 

В нашей задаче, например, в случае, когда удобрения не используются (k = 1), получим

 

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

Рассмотрим задачу о стратегии агрофирмы с горизонтом планирования 3 года (N = 3) и матрицами (19.9)-(19.12).

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

Таблица 19.1. Выигрыш для каждого этапа

	5,3	4,7
		3,1
	-1	0,4

 

Этап 3.

		Оптимальное решение
	5,3	4,7	5,3
		3,1	3,1
	-1	0,4	0,4

 

Этап 2.

		Оптимальное решение
			8,19
			5,61
			2,13

 

Этап 1.

		Оптимальное решение
			10,74
			7,92
			4,23

 

Оптимальное решение показывает, что в 1-й и 2-й годы агрофирма должна применять удобрения () независимо от состояния почвы. На третий год следует применять удобрения только тогда, когда система находится в состояниях 2 или 3 (т.е. при удовлетворительном или плохом состояниях почвы). Суммарный ожидаемый доход за три года составит при хорошем состоянии системы в первый год, - при удовлетворительном состоянии системы в первый год и при плохом состоянии.

 

Рассмотрим второй вариант ВДП – модель с бесконечным числом этапов.

 

19.5. Определение оптимальной стратегии для процесса с бесконечным числом этапов (оптимальная долгосрочная стратегия)

 

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

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

Шаг 1. Вычисляется - ожидаемый доход, получаемый за один этап при стратегии s для заданного состояния .

 

Шаг 2. Вычисляются стационарные вероятности для матрицы переходных вероятностей , соответствующие стратегии s . Эти вероятности находятся из уравнений

где .

 

Шаг 3. Вычисляется ожидаемый доход за один шаг (этап) при выбранной стратегии s:

 

Шаг 4. Оптимальная стратегия определяется из условия

 

Проиллюстрируем этот алгоритм на нашем примере в случае бесконечного горизонта планирования.

В этой задаче имеется восемь стационарных стратегий

Стационарная стратегия, s	Действия
	Не применять удобрения вообще
	Применять удобрения независимо от состояния почвы
	Применять удобрения, если почва находится в состоянии 1
	Применять удобрения, если почва находится в состоянии 2
	Применять удобрения, если почва находится в состоянии 3
	Применять удобрения, если почва находится в состоянии 1 или 2
	Применять удобрения, если почва находится в состоянии 1 или 3
	Применять удобрения, если почва находится в состоянии 2 или 3

 

Матрицы вероятностей и доходов для стратегий от 3 до 8 получаются из аналогичных матриц для стратегий 1 и 2. Получим:

 

 

 

 

 

 

 

Результаты вычислений приведены в следующей таблице

 

s
	5,3		-1
	4,7	3,1	0,4
	4,7		-1
	5,3	3,1	-1
	5,3		0,4
	4,7	3,1	-1
	4,7		0,4
	5,3	3,1	0,4

 

Стационарные вероятности находятся из уравнений

 

Например, для второй стратегии (s = 2) уравнения имеют вид

 

 

(Одно из уравнений избыточно). Решение системы уравнений дает

 

 

Для данной стратегии ожидаемый годовой доход равен

 

Аналогично рассчитываются и годовые доходы для всех остальных стратегий (см. Табл.)

				-1,0
	6/59	31/59	22/59	2,256
				0,4
				-1,0
	5/154	69/154	80/154	1,724
				-1.0
	5/137	62/137	70/137	1,734
	12/135	69/135	54/135	2,216

 

Из таблицы видно, что в условиях нашего примера наибольший ожидаемый годовой доход дает стратегия 2 (долгосрочная стратегия требует применения удобрений независимо от состояния почвы).

 

Вопросы для самоконтроля

1. В чем состоит суть задач динамического программирования?

2. Что такое аддитивная целевая функция?

3. Что такое мультипликативная целевая функция?

4. Сформулируйте необходимые условия применения метода ДП

5. Сформулируйте принцип оптимальности Беллмана.

6. В чем принципиальное отличие метода ВДП от метода динамического программирования?

7. Как определяется средний ожидаемый доход за один переход?