7.7. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ДЛЯ МАРКОВСКИХ ПРОЦЕССОВ
В предыдущих параграфах были рассмотрены многошаговые задачи оптимального управления в детерминированных моделях, в которых имеется взаимооднозначное соответствие между принимаемым решением и его следствием - последующим состоянием системы.
Вместе с тем на практике часто встречаются системы, в которых нет такого взаимооднозначного соответствия, а можно лишь говорить о вероятности перехода в то или иное состояние. Такие системы являются вероятностными. Важный класс вероятностных систем составляют марковские системы, свойства которых в любой момент времени 
зависят только от текущего состояния 
и не зависят от предыстории процесса.
Динамическое программирование является эффективным методом оптимизации систем, описываемых марковскими процессами.
Свойства марковской системы.
Функциональные уравнения Беллмана
Пусть имеется некоторая система, которая может находиться в одном из 
состояний, и задано некоторое множество решений 
, которые могут приниматься в каждом состоянии 
, 
, и матриц условных вероятностей 
, 
, где 
- условная вероятность того, что система перейдет в состояние 
, если текущим состоянием было и принималось решение 
. При этом, в силу свойства марковской системы, допускается, что величины зависят лишь от значения текущего состояния и не зависят от предыстории процесса, то есть траектории движения, которая привела систему в состояние .
Предположим, что вероятности пребывания системы в каждом состоянии в начальный момент времени равны 
.
Тогда закон движения марковской системы полностью определяется величинами 
и матрицей . Если обозначить через 
вероятность пребывания системы в состоянии на -м отрезке времени, то
(7.7.1)
Здесь допустим, что переход из одного состояния в другое происходит точно за один интервал времени. Предположим также, что при 
величины 
стремятся к некоторым предельным значениям 
, называемым стационарными (или предельными) вероятностями состояний. Каждая величина представляет собой некоторую установившуюся относительную частоту пребывания системы в состоянии .
Величины можно получить из (7.7.1) путем предельного перехода при . Приходим к системе уравнений вида
, (7.7.2)
при условии
.
Система называется эргодической, если величины не зависят от распределения начальных вероятностей 
.
Рассмотрим примеры определения стационарных вероятностей.
Случай 1. Пусть матрица условных вероятностей имеет вид
.
Используя (7.7.2), получим
;
.
С учетом 
получим 
.
Случай 2. При заданной матрице условных вероятностей
можно показать, что 
.
Во всех случаях, когда все строки матрицы 
идентичны, стационарные вероятности равны элементам этих строк.
Случай 3. При заданной матрице условных вероятностей переходов
можно показать, что, все стационарные вероятности равны между собой:
.
Таким образом, во всех случаях, когда сумма элементов каждого столбца равна 1, все величины равны между собой, то есть
.
Такая матрица называется дважды стохастической.
Случай 4. Предположим, что матрица вероятностей имеет вид
, (7.7.3)
то есть система все время совершает колебания между этими состояниями. Можно показать, что .
Многократно используя выражение (7.7.1), получим
Следовательно, в рассматриваемом случае величины 
не стремятся ни к какому пределу при возрастании 
, то есть стационарные вероятности здесь не существуют. Аналогичные системы, описываемые матрицей 
вида (7.7.3), называются циклическими.
Случай 5. Рассмотрим систему, описываемую матрицей вида
Если такая система в начальный момент времени находится в некотором состоянии 
, то она останется в нем навсегда. Данная система распадается на множество изолированных подсистем (состояний).
Рассмотрим снова марковскую систему, описанную в начале раздела. Обозначим через 
условный эффект (или затраты), определяемый переходом системы из состояния в состояние при условии принятия решения . Такую систему удобно записать в виде сетевой модели, где каждой дуге 
соответствует пара величин 
.
Пусть каждый переход осуществляется за один интервал времени, система функционирует на протяжении неограниченного времени, а в качестве критерия выбраны интегральные дисконтированные затраты (ИДЗ). Обозначим через 
значение ИДЗ, если текущим состоянием (в данный момент) является состояние . Если в этот момент принимается решение , то справедливо соотношение
, (7.7.4)
где 
- коэффициент дисконтирования (
); 
- ожидаемый эффект (затраты) на данном отрезке времени для начального состояния при решении ; 
- интегральные дисконтированные затраты для состояния при решении .
Предположим, что система функционирует оптимально, то есть на каждом шаге принимается оптимальное решение, а период функционирования системы бесконечен. Тогда справедлива следующая система функциональных уравнений Беллмана для марковской системы, которая является естественным обобщением функциональных уравнений (7.6.1) для марковских систем:
для всех 
, (7.7.5)
где 
- множество возможных решений в состоянии .
Определим стратегию на бесконечном плановом периоде как исчерпывающее правило принятия решений, принимаемых на каждом отрезке времени в каждом состоянии. Под оптимальной стратегией как и ранее, будем понимать стратегию, обеспечивающую минимальные ИДЗ при любых начальных состояниях. Такая стратегия не обязательно должна быть стационарной (то есть такой, что каждый раз, когда система приходит в состояние , принимается одно и то же решение). Вместе с тем справедливая следующая теорема о стационарных стратегиях [6;18].
Теорема. Всегда существуют единственные конечные значения 
, удовлетворяющие функциональным (экстремальным) уравнениям (7.7.5), и детерминированная стационарная стратегия, соответствующая этим значением,которая является оптимальной.
Методы последовательных приближений
Для решения функциональных уравнений (7.7.5) можно воспользоваться теми же самыми методами, что и для функциональных уравнений (7.6.1) для детерминированных систем - метод итераций по критерию и стратегиям.
Метод итераций по критерию. Рассмотрим алгоритм метода итераций по критерию для решения функциональных уравнений (7.7.5). Он состоит из следующих этапов.
1. Выберем 
произвольным образом и положим 
.
2. Определим 
из условия
для любого . (7.7.6)
3. Если <
, то переходим к второму шагу очередной итерации, положив 
. Если же 
= для всех , то конец. Получим = .
Заметим, что в процессе выполнения итераций каждая из величин будет сходиться к своему пределу , но в общем случае эта сходимость не является конечной.
Если все величины cid ³ 0, а все yi(0) ³ 0, то значения yi(n) возрастают монотонно. При любом cid можно достичь сходимости следующим образом. Выбираем пробную стационарную стратегию, в которой для упрощения записи любое решение обозначим через d¢. Далее решаем систему линейных уравнений относительно неизвестных yi:
для каждого . (7.7.7)
Полученные решения yi(0) далее подставляются в соотношения (7.7.6). Если на произвольно выбранной итерации n прекратить вычисления и использовать непосредственно найденную из соотношений (7.7.6) оптимальную на n-м шаге стратегию в качестве стационарной для бесконечного планового периода, то соответствующие значения ИДЗ не будут превосходить значения yi(n).
Метод итераций по стратегиям. Приведем описание алгоритма метода итераций по стратегиям для решения функциональных уравнений (7.7.5). Он состоит из следующих шагов.
Первый шаг. Выбрать произвольную начальную стратегию и принять n = 0.
Второй шаг. Для заданной пробной стратегии d¢ вычислить значения yi(n) из уравнений
для каждого , (7.7.8)
где d¢ - решение, принимаемое в состоянии i.
Третий шаг. Проверить возможности улучшения стратегии: вычисляем
для каждого . (7.7.9)
Четвертый шаг. Прекратить вычисления, если Yi(n) = yi(n) для всех . Текущая стратегия оптимальна. Если же Yi(n) ¹ yi(n) для некоторых i, изменить стратегию в каждой вершине (в каждом состоянии) k, где Yk(n) < yk(n) , используя то решение, которое дает Yk(n) в (7.7.9). Принять и перейти к второму шагу следующей итерации.
Алгоритм итераций по стратегиям обладает следующими важными особенностями:
yi(n+1) £ yi(n) в любой вершине и yi(n+1) < yi(n), если Yk(n) < yk(n).
Алгоритм сходится за конечное число итераций.
При остановке алгоритма стратегия, определяющая значения 
, является оптимальной.
Пример 7.9. Модель управления запасами. Для иллюстрации применения функциональных уравнений рассмотрим стохастическую задачу управления запасами с бесконечным плановым периодом, детерминированный эквивалент которой описан в параграфе 7.6. Числовые данные этой задачи таковы: спрос вероятностный 
; 
, объем производства 
ограничен 
; конечный уровень запаса 
; 
; затраты на производство и хранение продукции описываются соотношением 
, где
Текущее состояние системы 
определяется текущим запасом ( = 0, 1, 2, 3, 4). Очевидно, если объем производства равеня , то будущие состояния системы с учетом вероятности спроса 
и 
таковы: 
, 
, причем 
. Пусть 
- минимальные ИДЗ при условии, что начальный запас равен . Тогда функциональное уравнение типа (7.7.5) для этой задачи будут иметь вид
при = 0, 1, 2, 3, 4; 
, где минимум отыскивается по всем целым , удовлетворяющим условию
.
Исходные данные задачи приведены в табл. 7.12.
Таблица 7.12
|
i |
x = dÎ D(i) |
p (f (i, d)) |
|||||
|
0 |
1 |
2 |
3 |
4 |
cid |
||
|
0 |
4 |
1/2 |
0 |
1/2 |
0 |
0 |
22 |
|
5 |
0 |
1/2 |
0 |
1/2 |
0 |
25 |
|
|
1 |
3 |
1/2 |
0 |
1/2 |
0 |
0 |
20 |
|
4 |
0 |
1/2 |
0 |
1/2 |
0 |
23 |
|
|
5 |
0 |
0 |
1/2 |
0 |
1/2 |
26 |
|
|
2 |
2 |
1/2 |
0 |
1/2 |
0 |
0 |
18 |
|
3 |
0 |
1/2 |
0 |
1/2 |
0 |
21 |
|
|
4 |
0 |
0 |
1/2 |
0 |
1/2 |
24 |
|
|
3 |
1 |
1/2 |
0 |
1/2 |
0 |
0 |
16 |
|
2 |
0 |
1/2 |
0 |
1/2 |
0 |
19 |
|
|
3 |
0 |
0 |
1/2 |
0 |
1/2 |
22 |
|
|
4 |
0 |
1/2 |
0 |
1/2 |
0 |
0 |
1 |
|
1 |
0 |
1/2 |
0 |
1/2 |
0 |
17 |
|
|
2 |
0 |
0 |
1/2 |
0 |
1/2 |
20 |
|
Решим задачу методом итераций по критерию 
0.9, начиная с 
для всех . Результаты последовательных итераций приведены в табл. 7.13.
Таблица 7.13
|
Начальный уро- вень запасов, i |
N |
Бесконеч. период |
|||||||||
|
1 |
2 |
3 |
10 |
20 |
30 |
||||||
|
xi(1) |
yi(1) |
xi(2) |
yi(2) |
xi(3) |
yi(3) |
yi(10) |
yi(20) |
yi(30) |
xI |
yi |
|
|
0 |
4 |
22 |
4 |
40 |
5 |
54,3 |
122,9 |
163,8 |
178,0 |
5 |
185,7 |
|
1 |
3 |
20 |
5 |
34,5 |
5 |
49,2 |
117,8 |
158,7 |
173,0 |
5 |
180,6 |
|
2 |
2 |
18 |
4 |
32,5 |
4 |
47,2 |
115,8 |
156,7 |
171,0 |
4 |
178,6 |
|
3 |
1 |
16 |
3 |
30,5 |
3 |
45,2 |
113,8 |
154,7 |
169,0 |
3 |
176,6 |
|
4 |
0 |
1 |
0 |
19 |
0 |
33,6 |
102,1 |
143,0 |
157,3 |
0 |
164,9 |
Рассмотрим теперь решение данной вероятностной задачи управления запасами методом итераций по стратегиям. В качестве пробной стратегии выберем следующую: = 4 - , = 0, 1, 2, 3, 4; 
= 0. Составим соответствующую этой стратегии систему уравнений для определения величин , для чего используем данные табл. 7.12:
где 
= 0.9. Ее решением является 
= 202, 
= 200, 
= 189, 
= 196, 
.
Переходим к процедуре улучшения стратегии. Воспользуемся уравнениями (7.7.8). Результаты последовательных итераций приведены в табл. 7.14.
Таблица 7.14
|
Уровень запасов, i |
N |
Yi(2) |
|||||
|
0 |
1 |
2 |
|||||
|
xi(0) |
yi(0) |
xi(1) |
yi(1) |
xi(2) |
yi(2) |
||
|
0 |
4 |
202 |
4 |
202 |
5 |
185,7 |
185,7 |
|
1 |
3 |
200 |
5 |
196,5 |
5 |
180,6 |
180,6 |
|
2 |
2 |
189 |
4 |
194,6 |
4 |
178,6 |
178,6 |
|
3 |
1 |
196 |
3 |
192,6 |
3 |
176,6 |
176,6 |
|
4 |
0 |
181 |
0 |
181 |
0 |
164,9 |
164,9 |
Как видим, процесс вычислений заканчивается после =2, поскольку 
для всех , а соответствующая стратегия 
является оптимальной, что совпадает с решением, полученным методом итераций по критерию.
Оптимизация сети по критерию эквивалентных средних затрат
Функциональные уравнения. Рассмотрим практически важный случай, когда в качестве критерия оптимальности взяты средние затраты (СЗ), и выведем соответствующие функциональные уравнения (аналогично , как для детерминированной модели в п. 7.6). Пусть имеется некоторая стратегия 
(не обязательно детерминированная). Обозначим через 
минимальные ИДЗ для системы, начинающей функционировать из состояния , где рассматривается как параметр. Стратегия определяется как оптимальная при = 1, если 
= при каждом и при всех , достаточно близких к 1. Другими словами, стратегия оптимальна, если существует 
< 1 такое, что при всех на отрезке 
ожидаемые ИДЗ при выборе стратегии равны минимально возможным. Здесь, как и в случае < 1, справедлива теорема о стационарной стратегии, утверждающая, что и при =1 всегда существует детерминированная стационарная стратегия, являющаяся оптимальной [6; 18]. Итак, допустим, что детерминированная стационарная стратегия является оптимальной. Тогда при значении , достаточно близком к 1, имеем
, (7.7.10)
где 
обозначает решение в состоянии , определяемое оптимальной стратегией . Пусть
, (7.7.11)
где 
- стационарные вероятности состояния, вычисленные из уравнений (7.7.2), для стратегии . Величину 
можно считать ожидаемыми средними затратами за отрезок времени при использовании стратегии и бесконечном периоде функционирования. Для вывода функциональных уравнений для вероятностной модели при = 1 используется тот же подход, что и для детерминированной модели (п. 7.6).
Рассмотрим ожидаемые ЭСЗ (эквивалентные средние затраты) 
и определим весовые коэффициенты 
с помощью соотношения
для всех (7.7.12)
Тогда функциональные уравнения (7.7.10) можно переписать в виде
. (7.7.13)
С учетом того, что 
, после несложных преобразований выражение (7.7.13) приводим к виду
и подставляя = 1, получаем
для всех (7.7.14)
Уравнения (7.7.14) - это экстремальные (или функциональные) уравнения для марковской системы при критерии минимума средних затрат за отрезок времени. Как и для детерминированной модели, величина называется 'весом' -го состояния, а разность -
можно рассматривать как приращение ожидаемого эффекта (средних затрат), если система начинает функционирование с состояния , а не с состояния .
Если множество величин 
удовлетворяет системе уравнений (7.7.14), то и множество 
(где 
- произвольная константа) также будет удовлетворять этой системе. Поэтому для определения искомых значений вводится условие нормировки 
.
Рассмотрим некоторую стационарную стратегию , включающую решения . Пусть 
, - решения уравнений
(7.7.15)
для всех .
Тогда справедливо следующее утверждение (достаточные условия оптимальности) [6].
1. При заданной детерминированной стационарной стратегии , когда значения 
та , найденные из уравнений (7.7.15), удовлетворяют функциональным уравнениям (7.7.14), величина является наименьшей для всех стратегий, а соответствующая ей стратегия является оптимальной.
2. Если величина не является наименьшей, то решения и из (7.7.15) не удовлетворяют уравнениям (7.7.14).
Таким образом, для определения оптимальной стратегии, минимизирующей 
, необходимо решить систему уравнений (7.7.14).
Метод итераций по стратегиям. Рассмотрим метод итераций по стратегиям для решения функциональных уравнений (7.7.14). Этот метод является обобщением соответствующего метода для детерминированной модели.
Для упрощения предположим, что для каждой пробной стратегии 
, оцениваемой на втором шаге алгоритма, существуют единственные стационарнарные вероятности. Алгоритм состоит из следующих шагов.
Первый шаг. Выбрать произвольную стационарную стратегию и положить .
Второй шаг. При заданной пробной стратегии на итерации решить систему уравнений для определения 'весов' :
(7.7.16)
где 
- решение в состоянии , определяемое стратегией .
Третий шаг. Вычислить:
(7.7.17)
Четвертый шаг. Прекратить вычисления, если 
=
для всех , при этом значение 
минимальное. Если же 
изменить стратегию в каждой вершине (в каждом состоянии) 
, где 
<
, и использовать ту стратегию, которая дает значение в уравнении (7.7.17). Перейти от к 
и вернуться к шагу 2 при новой пробной стратегии.
Изложенный алгоритм сходится за конечное число итераций.
Пример 7.10. Рассмотрим вновь стохастическую задачу управления запасами, исходные данные для которой приведены в табл. 7.12. В качестве критерия оптимальности примем минимум средних затрат за n отрезок 
. Для нахождения оптимальной стратегии применим метод итераций по стратегиям.
Запишем систему функциональных уравнений для этой задачи:
. (7.7.18)
1. В качестве пробной стратегии выберем стратегию выпуска минимально допустимого размера партии
0, 1, 2, 3, 4
2. Составим систему уравнений для определения 
Находим решение этой системы: 
= 0, 
= -2, 
= -4, 
= -6, 
= -21, 
= 20.
3. Переходим к процедуре улучшения весов и вычислим 
в соответствии с соотношением (7.7.17). Находим: 
= 0, 
=
, 
=
, 
=
, 
. Поскольку <
для = 1, 2, 3, то перейдем ко второй итерации. Результаты последовательных итераций приведены в табл. 7.15.
Таблица 7.15
|
Началь- ный запас, i |
N |
||||||||
|
0 |
1 |
2 |
|||||||
|
xi(0) |
wi(0) |
Wi(0) |
xi(1) |
wi(1) |
Wi(1) |
xi(2) |
wi(2) |
Wi(2) |
|
|
0 |
4 |
0 |
0 |
4 |
0 |
-1.25 |
5 |
0 |
0 |
|
1 |
3 |
-2 |
-6.5 |
5 |
-6.5 |
-6.5 |
5 |
-5.43 |
-5.43 |
|
2 |
2 |
-4 |
-8.5 |
4 |
-8.5 |
-8.5 |
4 |
-7.43 |
-7.43 |
|
3 |
1 |
-6 |
-10.5 |
3 |
-10.5 |
-10.5 |
3 |
-9.43 |
-9.43 |
|
4 |
0 |
-21 |
-21 |
0 |
-21 |
-21 |
0 |
-20.3 |
-20.3 |
|
C(n) |
20 |
17 |
17 |
||||||
Как видно, алгоритм сходится на итерации 
, поскольку здесь выполняется условие 
=
для всех = 0, 1, 2, 3, 4. Искомая оптимальная стратегия равна 
5, 
5, 
4, 
3, 
0, а оптимальное решение системы уравнений (7.7.18) таково: =
, 
=
, 
=
, 
=
, 
=
, 
= 0. Итак, и в данном примере минимальные средние затраты за отрезок времени равны = .
Рассмотрим рекуррентное соотношение (7.7.14) для конечного планового периода. Можно показать, что при достаточно больших значение функции суммарных затрат за отрезков времени при начальном состоянии 
связано с минимальными средними затратами соотношением
. (7.7.19)
Используя условия нормировки 
, получим из (7.7.19)
. (7.7.20)
Выражение (7.7.20) позволяет дать следующую экономическую интерпретацию величине . Весовой коэффициент равен приращению функции затрат 
при начальном состоянии (по отношению к состоянию 0) при неограниченном интервале функционирования системы (
).
