7.5. ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С БЕСКОНЕЧНЫМ ЧИСЛОМ ШАГОВ
Способы оценки бесконечных последовательностей эффектов (затрат)
Рассмотренные выше модели задач планирования и управления (например, трудовыми ресурсами или запасами) охватывали некоторый интервал времени, состоящий из конечного числа периодов (отрезков). Если функционирование системы на этом не прекращается, а ранее принятые решения безусловно влияют на ее поведение в будущем. С такой точки зрения эти модели можно рассматривать как элементы бесконечного планового периода. При этом сам бесконечный плановый период можно трактовать как предел конечного планового периода при 
.
Для того, чтобы в моделях с бесконечным плановым периодом получить определенные решения, вводится ограничительное предположение о стационарности, которое означает, что все функции затрат или эффектов (экономических) и внешние условия для каждого из периодов стационарны или изменяются циклически. Если же рассматривается вероятностная система, то ее вероятностные характеристики также полагаются стационарными.
Прежде чем рассмотреть методы принятия решений при бесконечном плановом периоде, выработаем основные способы оценки и сравнения бесконечных последовательностей эффектов (или затрат).
Существует три основных способа оценки таких последовательностей [6; 18]: 1) средний эффект за интервал времени - СЭ; 2) интегральный дисконтований эффект - (ИДЭ); 3) эквивалентный средний эффект - ЭСЭ. Рассмотрим эти оценки. Предположим, что некоторой стратегии управления системой отвечает такая последовательность эффектов (затрат):
, тогда СЭ = 
.
Главный недостаток критерия СЭ состоит в том, что он одинаково оценивает как доход, полученный в данный момент, так и будущие доходы. Вместе с тем ценность одного и того же дохода сейчас и в будущем спустя 
временных интервалов (например шагов), вовсе неодинакова, из-за действия инфляции. Чтобы учесть эту неравноценность, вводится коэффициент дисконтирования 
(
), с помощью которого вся последовательность будущих эффектов (прибылей или затрат) сводится к настоящему времени.
В результате приходим к интегральному дисконтированному эффекту:
ИДЭ = 
. (7.5.1)
Величину можно вычислить, например, как 
, где 
- годовая процентная ставка (то есть годовые проценты, получаемые вкладчиком за деньги, вложенные в банк).
Связь между критериями СЭ и ИДЭ осуществляется через эквивалентный средний эффект (ЭСЭ).
Под ЭСЭ понимается такая величина эффекта, постоянная на всех интервалах времени, 
, что ИДЭ для последовательности из значений ЭСЭ и для исходной последовательности совпадают.
Предположим, что для последовательности 
ИДЭ = 
. (7.5.2)
Обозначим ЭСЭ через 
. Имеем последовательность
.
Поскольку по определению для обеих последовательностей величины ИДЭ совпадают, то 
, откуда
ЭСЭ =
ИДЭ. (7.5.3)
Пример 7.4. Модель эксплуатации лесного хозяйства. Для иллюстрации использования введенных оценок рассмотрим следующую задачу. Леспромхоз планирует засадить лесом новый земельный участок. Предположим, что дерево, срубленное в 
-й отрезок времени (например, в -й год), с момента его посадки принесет прибыль 
(грн.). Предположим также, что затратами на посадку и уход за лесом можно пренебречь и что все деревья на участке должны быть срублены одновременно. Требуется определить оптимальный момент (год) рубки леса, при котором достигается максимальная прибыль при коэффициенте дисконтирования 
.
1. Рассмотрим сначала случай, когда после рубки леса не будут делаться новые посадки (однократное принятие решений).
Необходимо найти такое значение , что
ИДЭ ( ) = 
.
Искомое значение определяется следующим соотношением
.
2. Теперь рассмотрим бесконечношаговый плановый период. Предположим, что каждый раз после рубки леса на -м интервале времени, на (
)-м осуществляются новые насаждения леса, причем этот процесс повторяется бесконечное число раз. Если каждый раз рубка леса осуществляется через отрезков после посадки, то ИДЭ последовательности прибылей для бесконечного планового периода будет равен
.
Откуда
. (7.5.4)
Оптимальной для бесконечного планового периода является такая стратегия , при которой максимизируется величина 
. (7.5.5)
Искомое значение 
, при котором достигает максимума, определяется из условия
(7.5.6)
Откуда приходим к соотношению
. (7.5.7)
При этом оптимальное значение удовлетворяет неравенству 
, где 
- оптимальное значение при однократном принятии решений.
Модель восстановления при бесконечном плановом периоде
Довольно распространенный класс задач, приводящих к необходимости исследования бесконечного числа этапов, составляют задачи (процессы) восстановления. В этих процессах очередной момент восстановления происходит в то время (момент), когда система возвращается в исходное состояние (например, рубка леса или замена оборудования). В этих задачах управляющими переменными (стратегиями) являются интервалы времени между компонентами восстановления. Рассмотрим общую модель задачи восстановления.
Конечный плановый период. Предположим, что в задаче восстановления возможными стратегиями являются 
(
) - число интервалов времени между соседними моментами восстановления.
Свяжем с каждым вариантом затраты (или эффект) 
при их оценке в начале периода восстановления (например, стоимость замены оборудования). Обозначим через 
интегральные дисконтированные затраты для оптимальной стратегии восстановления, при которой один из альтернативных вариантов должен быть выбран за 
интервалов времени до конца планового периода.
Предположим, что выбран альтернативный вариант . Тогда сразу появляются затраты , и если предположить, что в следующий момент восстановления (то есть на отрезке 
) также принимается оптимальное решение, то в дальнейшем возникают затраты 
, где 
используется для приведения будущих затрат через интервалов времени к настоящему моменту. Следовательно, за интервалов времени до конца планового периода оптимальной будет такая стратегия, при которой минимизируется сумма ( + ). Итак, приходим к рекуррентному соотношению:
. (7.5.8)
Бесконечный плановый период. Рассмотрим случай бесконечного планового периода. Полагая в (7.5.8) и опустив индекс у функции , получим соотношение
. (7.5.9)
Оно представляет собой экстремальное или функциональное уравнение с неизвестным 
.
Используя функциональные уравнения, необходимо определить:
имеется ли у данного уравнения конечное решение;
если имеется, то является ли оно единственным;
если оно единственное, то является ли минимальным значением для всех возможных (не обязательно) стационарных стратегий.
Из соотношения (7.5.8) следуют неравенства
и 
, (7.5.10)
причем (7.5.10) должно быть строгим неравенством хотя бы для одного . Отсюда следует, что функциональное уравнение (7.5.9) имеет однозначное конечное решение вида
. (7.5.11)
Оптимальная стационарная стратегия соответствует выбору альтернативного 
, которое дает возможность получить оптимальное значение .
Здесь мы воспользовались как критерием оценки ИДЭ при 
. Очевидно при 
соотношение (7.5.11) не выполняется. Для того, чтобы использовать критерий СЭ, перейдем сначала к критерию ЭСЭ, для чего положим 
.
Тогда после простых преобразований выражение (7.5.11) принимает вид
. (7.5.12)
Полагая в (7.5.12) , получим следующее решение
. (7.5.13)
Таким образом, стратегия будет оптимальной, если при ней минимизируются средние затраты за интервал времени.
Методы последовательных приближений
Рассмотрим методы решения функционального уравнения вида
. (7.5.14)
Существует три подхода к решению уравнения (7.5.14).
П е р в ы й подход основан на динамическом характере модели. Он состоит в выяснении того, не будет ли стратегия, оптимальная для очень длительного, но конечного планового периода, одновременно оптимальным решением и для бесконечного периода.
Рассматривается решение для модели со конечным плановым периодом
, (7.5.15)
где принимает очень большие значения.
Чтобы такой подход был справедлив, необходимое выполнение следующих условий:
при любом достаточно большом решение 
, получаемое из (7.5.15), должно также удовлетворять уравнению (7.5.14);
если длительность планового периода очень велика, то стратегия , оптимальная для бесконечного планового периода, будет оптимальной также и для конечного планового периода.
Для модели восстановления справедлива следующая теорема о длительности планового периода, которая обуславливает этот подход [6].
Теорема. Существует такое конечное значение 
, что для любого конечного периода длительностью отрезков (
) выполняются следующие соотношения:
если
,
то
; (7.5.16)
если
,
то
. (7.5.17)
Из (7.5.16) следует, что любая стратегия , оптимальная при достаточно большой длительности планового периода (
), одновременно является оптимальной стационарной стратегией и для бесконечного планового периода, а (7.5.15) является обратным утверждением.
Второй подход состоит в том, чтобы попытаться угадать некоторое значение . Далее на основе этого значения вычисляется величина в правой части (7.5.14) и проверяется выполнение этого уравнения. Если оно не выполняется, то результат вычислений используется в качестве скорректированного значения , и процесс снова повторяется. Соответствующий метод называется методом итераций по критерию (или в пространстве функций) [9; 18]. Он состоит в следующем.
Пусть 
- первоначально выбранное значение . Метод заключается в построении последовательности приближений 
, 
, . на основе рекуррентного соотношения
. (7.5.18)
Предположим, что 
. Если = 0, то можно доказать, что 
.
, то есть совокупность - монотонно возрастающая последовательность приближений. Тогда при достаточно большом значение окажется сколь угодно близким к 
. Тем не менее в общем случае не существует такого конечного , что равно .
Таким образом, метод итераций по критерию обеспечивает сходимость к истинному значению , но число итераций не является конечным.
Пример 7.5. Для иллюстрации метода итераций по критерию рассмотрим задачу восстановления с такими исходными данными:
= 5, 
= 8.7, 
= 12.9, 
= 14.7, 
= 19.7, 
= 28.7, 
= 0.8.
Можно вычислить, что
,
так что = 3 - оптимальная стратегия.
Вычисляя 
на основании соотношения (7.5.18), при 
получим
;
;
.
Вычисляя аналогично далее получаем: 
= 25.53, 
= 27.57, 
= 28.76, 
= 29.37, 
= 29.68, 
= 29.84, 
= 29.91, причем на всех итерациях 
.
Третий подход состоит в попытках угадать оптимальную стратегию для бесконечного планового периода. Для пробной стратегии, которая проверяется на оптимальность, вычисляют соответствующие интегральные дисконтированные затраты (ИДЗ), которые используются в качестве значения , затем проверяется справедливость уравнения (7.5.14). Если оно выполняется, то текущая пробная стратегия является оптимальной, в противном случае в качестве новой пробной стратегии выбирается та, для которой достигается минимум правой части (7.5.14). Поскольку имеется конечное число 
различных стационарных стратегий, и мы никогда не возвращаемся к ранее отброшенной стратегии, то оптимальная стратегия отыскивается за конечное число итераций. А именно, как только стратегия остается оптимальной в течение двух итераций подряд, то вычисления можно прекратить, причем будет равно оптимальному значению . Данный метод называется методом итераций по стратегиям [6; 18].
Соответствующий алгоритм метода состоит из следующих шагов.
Первый шаг. Примем 
и выберем начальную стратегию 
.
Второй шаг. Для заданной пробной стратегии вычислим интегральные дисконтированные затраты (ІДВ) в течение бесконечного планового периода:
. (7.5.19)
Третий шаг. Проверим возможность дальнейших улучшений стратегии, для чего вычислим
, (7.5.20)
и выберем в результате стратегию 
.
Четвертый шаг. Если 
, то прекратим расчеты. Стратегия оптимальна. В противном случае изменим предыдущую стратегию на . Перейдем к (
) итерации на второй шаг, используя в качестве новой стратегии .
Пример 7.6. Для иллюстрации этого метода рассмотрим предыдущий пример с теми же исходными данными:
= 5, = 8.7, = 12.9, = 14.7, = 19.7, = 28.7, = 0.8.
Пусть в качестве начальной пробной стратегии выбрана 
, тогда
.
Первая итерация. Используя (7.5.20), вычисляем
.
Вторая итерация. Находим ИДЗ для стратегии 
:
.
Повторное использование формулы (7.5.20) дает
Поскольку 
, то дальнейшие расчеты можно прекратить; стратегия оптимальная и для нее 
.
