В рассмотренных примерах управляемые переменные, а также переменные состояния и шага принимали только целочисленные значения. (Задачи такого рода называют задачами дискретного программирования ). Кроме того, на результаты и переходы из одного состояния в другое не оказывали влияния случайные факторы. Учет случайного характера параметров модели есть предмет анализа стохастического динамического программирования . Рассмотрим небольшой пример, иллюстрирующий основные идеи и методы стохастического динамического программирования.
Пример 2.8.4. Задача садовника. Предположим, что каждый год почва может находиться в одном из трех состояний: хорошем (1), удовлетворительном (2) или плохом (3). Пусть k=1 и 2 – две возможные стратегии поведения садовника: не удобрять или удобрять. Оптимальное поведение садовника определяется такой стратегией, при которой он получает наибольший ожидаемый доход через N лет. Обозначим рij(k) – вероятность перехода почвы из состояния i в состояние j при применении садовником стратегии k. Пусть 0.2 0.5 0.3 0.3 0.6 0.1 {рij(1)}= 0 0.5 0.5 , {рij(2)}= 0.1 0.6 0.3 0 0 1 0.05 0.4 0.55 Поясним суть приведенных данных: Если садовник не применяет удобрения (k=1), то при хорошем состоянии почвы (строка 1) вероятность ее перехода в хорошее состояние – 0.2, в удовлетворительное – 0.5 и в плохое – 0.3. При
278 плохом состоянии (строка 3) с вероятностью 1 почва остается плохой. Если садовник применяет удобрения (k=2), то при хорошем состоянии почвы (строка 1) вероятность ее перехода в хорошее состояние – 0.3, в удовлетворительное – 0.6 и в плохое – 0.1. При плохом состоянии (строка 3) с вероятностью 0.05 почва станет хорошей, с вероятностью 0.4 удовлетворительной и с вероятностью 0.55 останется плохой. Обозначим rij(k) – доход (или убыток), который получит садовник за одногодичный период, если почва перейдет из состояния i в состояние j при применении садовником стратегии k. Пусть 7 6 3 6 5 – 1 {rij(1)}= 0 5 1 , {rij(2)}= 7 4 0 . 0 0 –1 6 3 –2 Поясним суть приведенных данных: Если садовник не применяет удобрения (k=1), то при переходе из хорошего состояния почвы (строка 1) в хорошее доход составит 7 единиц, в удовлетворительное – 6 и в плохое – 3. При переходе из плохого состояния (строка 3, вспомним, что в этом случае с вероятностью 1 почва остается плохой) доход составит –1 (убыток). Если садовник применяет удобрения (k=2), то при переходе из хорошего состояния почвы (строка 1) в хорошее доход составит 6, в удовлетворительное – 5 и в плохое – убыток в размере 1 (не в коня корм). При переходе из плохого состояния (строка 3) в хорошее доход составит 6, в удовлетворительное – 3 и в плохое – убыток 2. Обозначим vi(k) – ожидаемый доход, обусловленный одним переходом из состояния i при стратегии k, тогда vi(k)=∑jpij(k)rij(k). Если удобрения не применяются (k=1), тогда v1(1)=0.2×7+0.5×6+0.3×3=5.3, v2(1)=0×0+0.5×5+0.5×1=3, v3(1)=0×0+0×0+1× (–1)= –1. При использовании удобрений (k=2) имеем v1(2)=0.3×6+0.6×5+0.1× (–1)=4.7, v2(2)=0.1×7+0.6×4+0.3×0=3.1, v3(2)=0.05×6+0.4×3+0.55× (–2)=0.4. Как и прежде будем анализировать плановый период с конца, обозначим fn(i) – оптимальный ожидаемый доход за n лет до конца периода, тогда рекуррентные соотношения примут вид:
279 f1(i)=maxk{vi(k)}, fn(i)=maxk{vi(k)+∑jpij(k)fn-1(j)}, n=2,3,…,N. (2.8.4) Проведем вычисления при N=4. Результаты поместим в таблицы 2.8.4 – 2.8.7.
280 n=4 Таблица. 2.8.7 vi(k)+pi1(k)f3(1)+pi2(k)f3(2)+pi3(k)f3(3) Оптим. решение
i k=1 k=2 f4(i) k* 1 5.3+.2×10.74+.5×7.92+.3×4.23= =12.68 4.7+.3×10.74+.6×7.92+.1×4.23= =13.097 13.10 2 2 3+0×10.74+.5×7.92+.5×4.23= =9.075 3.1+.1×10.74+.6×7.92+.3×4.23= =10.195 10.19 2 3 –1+0×10.74+0×7.92+1×4.23= = 3.23 .4+.05×10.74+.4×7.92+.55×4.23 =6.4315 6.43 2 Из оптимального решения следует, что в 1-й,2-й и 3-й годы садовник должен применять удобрения (k*=2) при любом состоянии почвы, а в 4-й год (n=1) садовнику следует применять удобрения только при условии, что состояние почвы удовлетворительное или плохое. Суммарный ожидаемый доход за четыре года составит f4(1)=13.10 при хорошем состоянии почвы в первый год, f4(2)= 10.19 при удовлетворительном состоянии и f4(3)=6.43 при плохом состоянии. Приведенный выше метод решения задачи называют еще методом итераций по стратегиям. Задачу садовника можно обобщить в двух отношениях. Во- первых, переходные вероятности и значения дохода не обязательно одни и те же в любой год; в этом случае они являются функциями n- го этапа: pij(k,n) и rij(k,n). Во-вторых, можно использовать коэффициент дисконтирования ожидаемых доходов, вследствие чего значения fN(i) будут представлять собой приведенные величины
ожидаемых доходов по всем этапам. Если α – годовой коэффициент дисконтирования, вычисляемый по формуле α=1/(1+t), где t – годовая норма процента, то рекуррентное соотношение (4.9.4) преобразуется к виду: fn(i)=maxk{ vi(k)+α∑jpij(k)fn-1(j)}, n=2,3,…,N. (2.8.5) Упражнение. Решите задачу садовника при коэффициенте дисконтирования α=0.6. (ответ приводится в таблице 2.8.8). Таблица. 2.8.8 n=1 n=2 n=3 n=4 i f1(i) k* f2(i) k* f3(i) k* f4(i) k* 1 5.3 1 6.94 1 7.77 1 8.26 1 2 3.1 2 4.61 2 5.43 2 5.92 2 3 0.4 2 1.44 2 2.19 2 2.66 2
281 Заметим, что использование коэффициента дисконтирования приводит к другим оптимальным стратегиям. В данном случае при хорошем состоянии почвы удобрения не требуются в течение всех четырех лет. Для определения оптимальной долгосрочной стратегии применяют два метода. Первый метод основан на переборе всех
возможных стационарных стратегий управления и может быть использован при их малом числе. Второй метод (итераций по стратегиям) более эффективен в том смысле, что определяет оптимальную стратегию за малое число итераций. Идея метода заключается в использовании соотношения (2.8.4) при n → ∞. Итак, задача стохастического динамического программирования включает в себя матрицу переходных вероятностей системы из состояния i в момент времени tn-1 в состояние j в момент tn. Матрица переходных вероятностей совместно с исходными вероятностями состояний полностью определяет марковскую цепь. Можно задачу стохастического динамического программирования (Марковскую задачу принятия решений) сформулировать как задачу линейного программирования (см. тему 2.2), однако в вычислительном отношении метод итераций по стратегиям более эффективен. Для задач с К альтернативами решений на каждом шаге и N состояниями соответствующая модель линейного программирования включает (N+1) ограничений и NК переменных.
Ви переглядаєте статтю (реферат): «Стохастическое динамическое программирование» з дисципліни «Математична економіка»
