7.6. ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ НА СЕТЯХ
Многие динамические задачи оптимального планирования и управления (например, управления запасами, распределения ресурсов и др.) можно представить .в виде сети (или графа), в которой каждому состоянию системы соответствует некоторая вершина сети и задача оптимального управления сводится к задаче отыскания кратчайшего маршрута в сети (на графе).
Рассмотрим, например, некоторую сеть, которая содержит 
вершин, и множество ориентированных дуг, которые соединяют некоторые вершины (рис. 7.16). Поставим в соответствие каждой допустимой стратегии в состоянии 
дугу 
. Перемещению по каждой дуге соответствуют определенные затраты (эффект) 
. Предположим, что время перемещения из вершины в вершину 
равно одиному временному отрезку, а коэффициент дисконтирования (дисконт-фактор) обозначим через 
.
Пусть маршрут начинается из некоторой произвольной вершины . Предположим, что из вершины направляемся к вершине 
, при этом возникают дисконтированные затраты 
. Если процесс длится на протяжении неограниченного времени, то маршрут является бесконечным.
Обозначим через yi интегральные дисконтированные затраты (ИДЗ) для оптимального бесконечного маршрута, который начинается в вершине . Если выбранная стратегия является стационарной, то каждый раз, возвратившись к вершине , мы снова выберем ту же стратегию 
(то есть дугу), что и в предыдущем случае захода в эту вершину.
Пусть существует стационарная стратегия, которая является оптимальной, тогда соответствующие величины ИДЗ удовлетворяют следующей системе функциональных уравнений:
для всех вершин ; 
. (7.6.1)
Возникают вопросы:
Всегда ли можно для всех значений 
отыскать однозначное и конечное решение?
Если ответ на первый вопрос - 'да', то является ли соответствующая стационарная стратегия действительно оптимальной?
Ответы на оба вопроса являются утвердительными. Они следуют из теоремы о стационарной стратегии [6; 18].
Всегда существуют однозначно определенные конечные , 
, и соответствующая им стационарная стратегия является оптимальной.
Рассмотрим методы решения системы функциональных уравнений (7.6.1) и отыскание оптимальных стратегий.
Метод итераций по критерию
Рассмотрим систему функциональных уравнений вида
для всех .
Ее решение методом итераций по критерию состоит из следующих шагов.
1. Задаемся начальными значениями 
(например, 
) и 
.
2. Вычисляем 
для всех .
3. Если 
для всех , то заканчиваем вычисления, в противном случае - переходим к второму шагу очередной итерации, положив 
.
Если все 
и все 
, то значения 
возрастают монотонно и каждое из 
сходится к своему пределу, однако сходимость не гарантируется за конечное число итераций.
Метод итераций по стратегиям (в пространстве стратегий)
Рассмотрим метод итераций по стратегиям для решения системы функциональных уравнений (7.6.1).
Первый шаг. Выберем произвольную начальную стратегию и положим , 
. Заметим, что выбор стратегии означает выбор некоторой дуги 
для каждой вершины.
Второй шаг. Для заданной пробной стратегии вычислим значения в соответствии с системой уравнений (расчета 'стоимости' вершин):
или 
, (7.6.3)
где дуга отображает выбранную пробную стратегию для состояния (вершины) .
Третий шаг. Проверим возможность дальнейшего улучшения стратегий, для чего вычислим
для всех (7.6.4)
Четвертый шаг. Если 
= для всех , то прекратим вычисления. Текущая стратегия будет оптимальной. В противном случае изменим текущую стратегию для каждой вершины , для которой 
<
. Для этого в качестве новой стратегии выберем дугу, которая позволяет достичь значения 
(в (7.6.4)). Перейдем на второй шаг (
)-ой итерации с новой пробной стратегией.
Метод итераций по стратегиям обладает следующими свойствами:
для любой вершины 
и, если < , то 
< ;
алгоритм является конечным;
стратегия, позволяющая по завершению вычислений достичь 
, является оптимальной.
Минимизация средних затрат.
Рассмотрим случай, когда критерий оптимизации сети представляет собой средние затраты (эффект) за интервал времени.
Предположим, что средние затраты для данной модели существуют и обозначим их минимальное значение через 
. Кроме того, предположим, что в рассматриваемой сети существует направленный маршрут от любой вершины ,по крайней мере, к одной из вершин, входящих в соответствующий минимальный цикл.
Построим функциональные уравнения для определения .
Пусть 
- ИДЗ для системы (сети), если ее текущее состояние в данный момент является . Тогда эквивалентные средние затраты (ЭСЗ) для системы в начальном состоянии будут равны 
.
ЭСЗ для каждой вершины удобно связать с таким соотношением [18]:
, 
, (7.6.5)
где 
- 'вес' -ой вершины.
Тогда
. (7.6.6)
Подставляя из (7.6.6) в (7.6.1), после несложных преобразований получим функциональное уравнение в виде
, (7.6.7)
или в следующем эквивалентном виде:
для всех вершин .
Положив 
, получим искомые функциональные уравнения
для всех вершин (7.6.8)
Для решения функциональных уравнений (7.6.8) целесообразно воспользоваться методом итераций по стратегиям. Заметим, что если найдены значения , удовлетворяющие функциональным уравненим (7.6.8), то и значения 
=
для всех , где - некоторая произвольная константа, также будут решениями этой системы. Таким образом, значения 
не являются единственными и для удобства целесообразно принять одно из них равным нулю (например, 
).
Предположим, что на каждой итерации проверяемая пробная стратегия включает ровно один цикл.
Алгоритм метода итераций по стратегиям состоит из следующих процедур.
Первый шаг. Выберем произвольную пробную стратегию, то есть для каждой вершины некоторую дугу , и положим 
.
Второй шаг. Для выбранной пробной стратегии вычислим значения 
и 
решив такую систему уравнений
для всех , (7.6.9)
где дуга отображает текущую пробную стратегию в состоянии .
Третий шаг. Проверим возможность дальнейшего улучшения, вычислив
для всех (7.6.10)
Четвертый шаг. Если 
для всех 
, то остановимся. Текущая стратегия оптимальна. В противном случае изменим текущую стратегию для каждой вершины для которой 
, выбрав дугу, позволяющую достичь значения 
в соответствии (7.6.10). Перейти к второму шагу ( )-ой итерации при новой пробной стратегии.
Итак, на каждой итерации требуется решать систему функциональных уравнений (7.6.9). Если проверяемая пробная стратегия включает лишь один цикл, то уравнения (7.6.9) всегда имеют единственное решение [6].
Заметим, что если составить уравнение (7.6.9) для всех вершин, входящих в цикл, то все веса 
исчезнут, так что, получим
,
где 
- совокупность дуг, входящих в цикл, а 
- количество дуг в этом цикле.
Данный алгоритм обладает следующими свойствами [6, 18]:
на каждой итерации 
;
вычисления заканчиваются после конечного числа итераций;
оптимальной является та стратегия, которая позволяет достичь значений 
, при этом 
.
Пример 7.7. Рассмотрим сеть, изображенную на рис. 7.17. На ее дугах проставлены соответствующие значения 
. Для того, чтобы применить метод итераций по стратегиям, необходимо выбрать начальную пробную стратегию, в которой для каждой вершины 
имеется исходящая дуга. Пусть такой пробной стратегией является следующая:
для вершины 1 - дуга (1,4);
для вершины 2 - дуга (2,1);
для вершины 3 - дуга (3,2);
для вершины 4 - дуга (4,1).
Таким образом, эта стратегия включает единственный цикл (1,4)-(4,1). Составим систему функциональных уравнений для выбранной пробной стратегии:
(1)
Ее можно записать в следующем эквивалентном виде:
Решение этой системы следующее:
; 
.
Как видно из рис. 7.17, изменение решений возможно лишь для вершин 1 и 2, где имеется более одной исходящей дуги.
При 
, в соответствии с формулами (1) для вершины 1 получим
для дуги (1,4) при .
Аналогично для вершины 2
(2)
для дуги (2,3) при 
.
Таким образом, если , то для каждой вершины выполняется условие 
и начальная стратегия будет оптимальной. Если 
, то минимум достигается на дуге (2,3), и это решение должно на следующей итерации заменить стратегию (2,1).
Пример 7.8. Рассмотрим снова ту же сеть (рис. 7.17) при 
и положим 
. Пусть требуется найти оптимальную стратегию, минимизирующую средние затраты за интервал времени.
В качестве начальной пробной стратегии выберем ту же, что и в примере 7.7, и, применив формулы (7.6.9), запишем следующую систему функциональных уравнений:
Эта система имеет следующее решение
.
Расчет показателей возможного улучшения по формулам (7.6.10) дает такие новые значения для весов 
:
для вершины 1: 
(для дуги (1,4));
для вершины 2: 
(для дуги (2,1)). Поскольку 
, то найдена оптимальная стратегия, для которой 
.
Динамическая задача управления запасами с бесконечным плановым периодом
Рассмотрим важную с практической точки зрения динамическую задачу управления запасами при бесконечном плановом периоде, являющуюся обобщением динамической задачи для конечного планового периода.
Пусть имеется система снабжения, которая производит продукцию, накапливает ее в запас и поставляет заказчику соответственно спросу. Исходные данные системы (задачи) такие: объем выпуска продукции 
ед., спрос на отрезке времени постоянен и равен 
ед., при этом уровень запасов на конец отрезка времени должен удовлетворять условию 
. Затраты на производство 
объема выпуска продукции 
задаются соотношением
Затраты на хранение запаса уровня равны 
где 
. Предположим, что система функционирует неограниченно долго. Требуется определить такую оптимальную стратегию управления запасами (то есть найти объем выпуска на каждом интервале (отрезке времени)), при которой минимизируются средние затраты за отрезок.
Выберем уровень запасов в начале отрезка (где = 0, 1, 2, 3, 4) в качестве переменной состояния системы. Стационарная стратегия будет представлять собой правило установления оптимального объема выпуска продукции для каждого значения .
Для решения этой задачи необходимо прежде всего представить ее в виде сети (сетевой модели). Каждому возможному состоянию поставим в соответствие одну вершину сети; при заданном каждому допустимому объему выпуска соответствует некоторая дуга . Так, если уровень запасов в начале отрезка равен , объем выпуска составляет единиц, а спрос единицы, то запас на начало следующего отрезка будет равен 
. Следовательно, дуга соответствует объему производства 
.
Таким образом, затраты при выборе стратегии (дуги) определяются выражением
. (7.6.11)
В связи с наличием ограничений на объем выпуска и уровень запасов , некоторые сочетания и недопустимы. Например, при = 0 должно быть 
, поскольку .
Сеть, соответствующая условиям задачи, приведена на рис. 7.18. При этом величины рассчитаны согласно (7.6.11).
Предположим, что в качестве критерия оптимальности принят минимум средних затрат (СВ) за интервал времени. Поэтому решаемое функциональное уравнение имеет вид:
для всех .
В качестве пробной стратегии выберем следующую: выпускать недостающее для полного удовлетворения спроса количество продукции при 
3 так, чтобы уровень запасов на конец интервала времени был равен 
; и вообще ничего не выпускать, если на данном интервале 
. На сети эта стратегия представляется так (см. рис. 7.19):
вершина 0 - дуга (0,0),
= 3;
вершина 1 - дуга (1,0),
= 2;
вершина 2 - дуга (2,0),
= 1;
вершина 3 - дуга (3,0),
= 0;
вершина 4 - дуга (4,1),
= 0.
Решение. Первая итерация. Используя алгоритм метода итераций по стратегиям, составим систему функциональных уравнений, отвечающих пробной стратегии:
Ее решение следующее:
.
Для всех вычисляем
.
В результате, имеем
= 0 для дуги (0,0); 
= -12 для дуги (1,3); 
= -14 для дуги (2,3); 
= -19 для дуги (3,0); 
= -20 для дуги (4,1).
На этом первая итерация заканчивается. Поскольку 
и 
, то переходим ко второй итерации, в качестве новой пробной стратегии выбрав такую: (0,0), (1,3), (2,3), (3,0), (4,1). Результаты вычислений, полученных в ходе выполнения ряда последовательных итераций приведены в табл.7.11.
Таблица 7.11
|
Вер-шина |
0 |
1 |
2 |
3 |
||||||||
|
(i, j) |
wi(0) |
Wi(0) |
(i, j) |
wi(1) |
Wi(1) |
(i, j) |
wi(2) |
Wi(2) |
(i, j) |
wi(3) |
wi(3) |
|
|
0 |
0, 0 |
0 |
0 |
0, 0 |
0 |
- 9 |
0, 1 |
0 |
|
0, 2 |
0 |
0 |
|
1 |
1, 0 |
- 2 |
- 12 |
1, 3 |
- 12 |
- 12 |
1, 3 |
|
|
1, 2 |
- 2 |
- 8 |
|
2 |
2, 0 |
- 4 |
- 14 |
2, 3 |
- 14 |
- 22 |
2, 4 |
|
|
2, 4 |
- 8 |
- 10 |
|
3 |
3, 0 |
- 19 |
- 19 |
3, 0 |
- 19 |
- 24 |
3, 4 |
|
|
3, 0 |
- 17 |
- 17 |
|
4 |
4, 1 |
- 20 |
- 20 |
4, 1 |
- 20 |
- 20 |
4, 1 |
- 21 |
- 21 |
4, 1 |
- 18 |
- 18 |
|
|
19 |
19 |
|
17 |
||||||||
Продолжение табл. 7.11
|
Вер-шина |
4 |
5 |
6 |
||||||
|
(i, j) |
wi(4) |
Wi(4) |
(i, j) |
wi(5) |
Wi(5) |
(i, j) |
wi(4) |
Wi(4) |
|
|
0 |
0, 2 |
0 |
- 1 |
0, 1 |
0 |
- 1 |
0, 2 |
0 |
0 |
|
1 |
1, 3 |
|
|
1, 3 |
- 6 |
- 6 |
1, 3 |
|
|
|
2 |
2, 3 |
|
|
2, 4 |
- 10 |
- 10 |
2, 4 |
|
|
|
3 |
3, 0 |
|
|
3, 0 |
- 16 |
- 16 |
3, 0 |
|
|
|
4 |
4, 1 |
- 22 |
- 22 |
4, 1 |
- 21 |
- 21 |
4, 1 |
|
|
|
|
|
16 |
|
||||||
Анализируя эту таблицу, можно сделать следующие выводы:
на первой итерации значения не улучшаются (
);
на всех следующих итерациях 
=2, 3, 4, 5, 6 выполняется условие <
;
после шестой итерации найдена оптимальная стратегия управления запасами. Она имеет вид:
при 
0, 1, 2; 
при 3, 4.
Ей отвечает производственный цикл (5, 5, 0, 5, 0). При этом средние затраты минимальны 
. Соответствующий минимальный цикл приведен на рис. 7.20.
