Eng | Rus | Ukr | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Исследование операций
|
26.09.2004
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
7.7. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ДЛЯ МАРКОВСКИХ ПРОЦЕССОВВ предыдущих параграфах были рассмотрены многошаговые задачи оптимального управления в детерминированных моделях, в которых имеется взаимооднозначное соответствие между принимаемым решением и его следствием - последующим состоянием системы. Вместе с тем на практике часто встречаются системы, в которых нет такого взаимооднозначного соответствия, а можно лишь говорить о вероятности перехода в то или иное состояние. Такие системы являются вероятностными. Важный класс вероятностных систем составляют марковские системы, свойства которых в любой момент времени зависят только от текущего состояния и не зависят от предыстории процесса. Динамическое программирование является эффективным методом оптимизации систем, описываемых марковскими процессами. Свойства марковской системы.
|
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.
Начальный уро- вень запасов, 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.
Уровень запасов, 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.
Началь- ный запас, 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) при неограниченном интервале функционирования системы ( ).