![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
||||||
![]() |
Eng | Rus | Ukr | ![]() |
![]() |
||||
![]() |
|||||||
![]() |
![]() |
||||||
![]() |
![]() |
![]() |
|||||
![]() |
Исследование операций
|
04.10.2008
|
![]() |
![]() |
|||
7.5. ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С БЕСКОНЕЧНЫМ ЧИСЛОМ ШАГОВСпособы оценки бесконечных последовательностей эффектов (затрат) Рассмотренные выше модели задач планирования и управления (например, трудовыми ресурсами или запасами) охватывали некоторый интервал времени, состоящий из конечного числа периодов (отрезков). Если функционирование системы на этом не прекращается, а ранее принятые решения безусловно влияют на ее поведение в будущем. С такой точки зрения эти модели можно рассматривать как элементы бесконечного планового периода. При этом сам бесконечный плановый период можно трактовать как предел конечного планового периода при Для того, чтобы в моделях с бесконечным плановым периодом получить определенные решения, вводится ограничительное предположение о стационарности, которое означает, что все функции затрат или эффектов (экономических) и внешние условия для каждого из периодов стационарны или изменяются циклически. Если же рассматривается вероятностная система, то ее вероятностные характеристики также полагаются стационарными. Прежде чем рассмотреть методы принятия решений при бесконечном плановом периоде, выработаем основные способы оценки и сравнения бесконечных последовательностей эффектов (или затрат). Существует три основных способа оценки таких последовательностей [6; 18]: 1) средний эффект за интервал времени - СЭ; 2) интегральный дисконтований эффект - (ИДЭ); 3) эквивалентный средний эффект - ЭСЭ. Рассмотрим эти оценки. Предположим, что некоторой стратегии управления системой отвечает такая последовательность эффектов (затрат):
Главный недостаток критерия СЭ состоит в том, что он одинаково оценивает как доход, полученный в данный момент, так и будущие доходы. Вместе с тем ценность одного и того же дохода сейчас и в будущем спустя В результате приходим к интегральному дисконтированному эффекту: ИДЭ = Величину Связь между критериями СЭ и ИДЭ осуществляется через эквивалентный средний эффект (ЭСЭ). Под ЭСЭ понимается такая величина эффекта, постоянная на всех интервалах времени, Предположим, что для последовательности ИДЭ = Обозначим ЭСЭ через
Поскольку по определению для обеих последовательностей величины ИДЭ совпадают, то ЭСЭ = Пример 7.4. Модель эксплуатации лесного хозяйства. Для иллюстрации использования введенных оценок рассмотрим следующую задачу. Леспромхоз планирует засадить лесом новый земельный участок. Предположим, что дерево, срубленное в 1. Рассмотрим сначала случай, когда после рубки леса не будут делаться новые посадки (однократное принятие решений). Необходимо найти такое значение ИДЭ ( Искомое значение
2. Теперь рассмотрим бесконечношаговый плановый период. Предположим, что каждый раз после рубки леса на
Откуда
Оптимальной для бесконечного планового периода является такая стратегия
Искомое значение
Откуда приходим к соотношению
При этом оптимальное значение Модель восстановления при бесконечном плановом периодеДовольно распространенный класс задач, приводящих к необходимости исследования бесконечного числа этапов, составляют задачи (процессы) восстановления. В этих процессах очередной момент восстановления происходит в то время (момент), когда система возвращается в исходное состояние (например, рубка леса или замена оборудования). В этих задачах управляющими переменными (стратегиями) являются интервалы времени между компонентами восстановления. Рассмотрим общую модель задачи восстановления. Конечный плановый период. Предположим, что в задаче восстановления возможными стратегиями являются Свяжем с каждым вариантом Предположим, что выбран альтернативный вариант
Бесконечный плановый период. Рассмотрим случай бесконечного планового периода. Полагая
Оно представляет собой экстремальное или функциональное уравнение с неизвестным Используя функциональные уравнения, необходимо определить: имеется ли у данного уравнения конечное решение; если имеется, то является ли оно единственным; если оно единственное, то является ли Из соотношения (7.5.8) следуют неравенства
причем (7.5.10) должно быть строгим неравенством хотя бы для одного
Оптимальная стационарная стратегия соответствует выбору альтернативного Здесь мы воспользовались как критерием оценки ИДЭ при Тогда после простых преобразований выражение (7.5.11) принимает вид
Полагая в (7.5.12)
Таким образом, стратегия Методы последовательных приближенийРассмотрим методы решения функционального уравнения вида
Существует три подхода к решению уравнения (7.5.14). П е р в ы й подход основан на динамическом характере модели. Он состоит в выяснении того, не будет ли стратегия, оптимальная для очень длительного, но конечного планового периода, одновременно оптимальным решением и для бесконечного периода. Рассматривается решение для модели со конечным плановым периодом
где Чтобы такой подход был справедлив, необходимое выполнение следующих условий: при любом достаточно большом если длительность планового периода очень велика, то стратегия Для модели восстановления справедлива следующая теорема о длительности планового периода, которая обуславливает этот подход [6]. Теорема. Существует такое конечное значение если
то
если
то
Из (7.5.16) следует, что любая стратегия Второй подход состоит в том, чтобы попытаться угадать некоторое значение Пусть
Предположим, что Таким образом, метод итераций по критерию обеспечивает сходимость к истинному значению Пример 7.5. Для иллюстрации метода итераций по критерию рассмотрим задачу восстановления с такими исходными данными:
Можно вычислить, что
так что Вычисляя
Вычисляя аналогично далее получаем: Третий подход состоит в попытках угадать оптимальную стратегию для бесконечного планового периода. Для пробной стратегии, которая проверяется на оптимальность, вычисляют соответствующие интегральные дисконтированные затраты (ИДЗ), которые используются в качестве значения Соответствующий алгоритм метода состоит из следующих шагов. Первый шаг. Примем Второй шаг. Для заданной пробной стратегии
Третий шаг. Проверим возможность дальнейших улучшений стратегии, для чего вычислим
и выберем в результате стратегию Четвертый шаг. Если Пример 7.6. Для иллюстрации этого метода рассмотрим предыдущий пример с теми же исходными данными:
Пусть в качестве начальной пробной стратегии выбрана
Первая итерация. Используя (7.5.20), вычисляем
Вторая итерация. Находим ИДЗ для стратегии
Повторное использование формулы (7.5.20) дает Поскольку |
![]() |
||||||
![]() |
|||||||
Copyright © 2002-2004 | ![]() |
||||||
![]() |
![]() |