Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 61
Текст из файла (страница 61)
6) с Ег=~ для и= 1, 2, ... и Уа(1)=0; с=1, 2, ..., Ф. Оптимальная политика задается вектором (д„(1), г),(2), ... ..., д„(дг)), определяющим выбор, который надлежит сделать в г-м состоянии, ко~да осталось и шагов. б. 8ЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ Хотя в дальнейшем будут приведены численные результаты для задачи этого типа, возникающей при рассмотрении процесса замены оборудования, сделаем уже сейчас некоторые общие замечания. Проведение вычислений усложняется не столько загрузкой пзмяти значениями последоватедьности (г„(1)) и (гу„(г)), которой можно пренебречь, сколько необходимостью хранить переходные лгатрицы Р(гу)=(ры(г))) и й(г)) =(ггг(г))).
Если Аг превышает, например, 1000, то ~рудности становятся практически непреодолимыми. Чтобы иметь возможность рассматривать задачи действнгельно крупного масштаба, необходимо изучить аналитическую структуру процесса и использовать полученную таким путем информацию для разработки приближенных методов. й(ы будем использовать линейность процесса и простую, но очень важную идею, что подходящим обрззом определенный идеализировзнный бесконечный процесс дает превосходное приближение к 7) 887 Асимпсотичвсков повядюнсв пронессу даже умеренной длины.
Однако для изучения не- установившегося состояния необходима точная постановка задачи. 7. АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ Приближенные методы, которые мы будем использовать, существенно зависят от асимптотического поведения последовательности (с„(с)) при п — ь со. Сформулируем следуюшии результат.
Т е о р е м а 1. Расс.нотрим рекурренпсное соотношение Уа())=так~де(д)+ ь ас,(д)У„с(с), (11.7У в ! где предполагается, испо (а) Ь (д) О и Ь.(д) ) О для некоторого( и всех д, ((с) ад(д) с()О С 7= 1,2, ..., Л! равномернапод, (с) т' ап(д)=1, 1=1, 2, ..., СИ. с ==! (11. 8)с Ьс(д) Ь.(д) , Ь(д)= , 4(д) =(пс) (д)Ь, (11.9)1 с!ь!2 Инылссс словами, Л (д) при каждо.к д есть транспонированная матрица по отноисению к положительной лсарковскосс матрссце. Допуспсплс также, что либо (а) фунссции Ьс (д) и асс (д) являются 4ункцссялссс конечномерного вектора д, компоненты которого предполагаются арики.наюсцпмп только конечное множество значенссй, в общелс, зависящее осп ! и !', либо (Ь) функцсссс Ьс(д) п асс(д) — непрерывньсе функцссс! конечномерного вектора д, чьи ко.ипаненпсы принимают значения в некоторых за.икнутых ограниченных областях д-пространства.
с 7оложсс.сс 388 [гл. х! МАРковскив пяоцвссы Рвшвння Тогда при и — со 1„(1) пг, г'=1, 2, ..., Лг, (11.1О) где скалярная веллчина г определяется соотношением е1 — шах 1пп а д) а)+ + (о) а) ! (1111) е и оэ~ и Доказательство этого результзтз имеется в стзтье, упомянутой в библиографии в конце главы. Величина Ь; (д) есть математическое ожидание дохода на каждом шаге, обусловленного решением д. Результат интуитивно ясен, так как он утверждает, что мы действуем ~аким образом, чтобы максимизировать средний ожидаемый доход. 8. ОБСУЖДЕНИЕ Значение этой теоремы заключается в том, что она гарантирует нам корректность очевидного метода определения оптимзлыюй политики. Именно, мы выбираем конкретную политику и используем ее повторно для получения средне~о выигрышз.
Затеи мы выбираем политику, мзксимизирующую этот средний выигрыш. С установлениел1 этого результата был открыт путь для ряда простых итеративных методов, которые могут быть использованы более эффективным образом для получения политики в процессе большой длительности.
Как и в теории цепей Маркова, имеется существеннзя разница между аналитическими резуль~атами в случае положительных коэффициентов и результатами, справедливыми только для неотрицательных коэффициентов. В большинстве приложений часто бывает так, что большая часть коэффициентов равна нулю.
Существует несколько путей обхода этой трудности. Во-первых, можно итерировать матрицы несколько раз, пока не исчезнут нули. То обстоятельство, что переходная вероятность не равна нулю, означает, что на любом конкретном шаге имеется путь перехода из 1-го состояния в че состояние. А факт, что все элементы некоторой итерированной матрицы положительны, означает, что имеется возможность перехода из Бго состояния в уче состояние не более, чем через некоторое фиксированное число шагов.
389 мвтод хОВАРдА В большинстве приугожений это в действительности и имеет место. Если же дело обстоит не так, то это обычно служит признаком какого-то обьедпнения двух разных процессов в один процесс ценой потери простоты. Вторым путем обхода многих тонких вопросов, возникающих при рассмотрении цепей Маркова с нулевыми элементами переходной матрицы, является замена этих нулей малыми величинами. Очевидно, если исходный физический процесс имеет смысл, то малые изменения в переходных вероятностях внесут пренебрежимый эффект в поведение в целом. Получив таким путем переходную мзтрицу с положительными элементами, мы можем ззтем использовать соответствующую простую теорию.
9. МЕТОД ХОВАРДА ИТЕРАЦИИ В ПРОСТРАНСТВЕ ПОЛИТИК зт 1»т — д,'Ргу(гту+ тг" '), 7=1 Для больших и тзкже имеет место равенство )г," =от+ лас (11.12) (11.13) если все состояния принадлежат одной и той же цепи *). Как установлено в 9 7, это будет ззведомо иметь место, *) Понятие пегги подробно рассматривается в книге Ховарда. Его можно найти также в любом руководстве по цепям Маркова. г/ 19 Р. Беллман. С Дрейфус Итеративный метод в пространстве политик, основанный па предшествующих идеях, детально разработан Р.
Ховардом. Мы рассмотрим его метод, который дает оптимальную политику для процессов большой длительности (т. е. «стационарных процессов»), где решения зависят только от состояния, а не от номера шага. Мы будем применять обозначения Р. Ховарда для того, чтобы легче было ссылаться на его работы. Если определить 1»лт как математическое ожидание суммарного дохода при гг-шаговолг процессе, начинающемся в состоннин г, прн использовании фиксированной политики, то легко видеть, что 1/ удовлетворяет рекуррентному соот- ношению зйо ь!авковскнв пяопьссы Ргшвния (гл.
х! если все рг,.) О. Зто уравнение показывае~, чго доход будет в целом складываться из двух частей: стационарной части лтг, обусловленной поведением при л — со, н переходной чзсти вн зависящей только от начального состояния, Подстановка предельного выражения (11,13) в соотношение (11.12) дает: и тй+пя= ~ рг, [г;,+пГ+(л — 1)д]. (11.14) )=! Так как по определению ~ч 'ргг=1, это вырзжение упрог — — ! щаегся и принимает вид в + и! = ~о ры (гц + пг) г=! !=1, 2, ..., Аг.
(11.15) 10. ОПЕРАЦИЯ ОПРЕДЕЛЕНИЯ ПЕРЕХОДНЫХ ЗНАЧЕНИЙ 11. ПРОЦЕДУРА УЛУЧШЕНИЯ ПОЛИТИКИ Теперь мы подошли к основной задаче. Мы показали, как, угадан политику, т. е. определив выбор альтернатив на каждом шаге, вычислить свяаанные с ней характеристики. Поставим вопрос о нахождении на основе этой информании лучшей политики. Под «лучшей» понимзем политику, дающую «) ЧТ10 — та!ое де!а!!в!па!!оп орегаг!оп. (Примо ред) Выше записана система Аг уравнений с )Ч+1 неизвестными, вг(!=1,..., Аг) н я.
Однако, очевидно, прибавление постоянной ко всем о; не изменяет уравнений. Это значит, что важны лишь относи!ельные значения вн а не абсолютные. Следовагельно, одна из величин тй может быть выбрана произвольной, и останегся Аг уравнениЙ с »Ч неизвестными. Если положить о = О, то решение урзвнений дает средний прирост я за длительное время и относительные значения различных начальных состояний тй для фиксированной поли гики.
Говард называет указанный выше прием нахождения выигрыша и переходных значений для заданной политики операцией определения значения (ЧОО) *). 121 Рвшвнив задач/! о тАкси большее мзтемагическое ожидзние выигрышз д. Вернемся к уравнению (11.15), Решив его относительно а,, получим: Ф д"= ~ ры(г//+ о;) — ои 1= 1, 2,..., Ач. (1!.16) /=- ч Напомним, что р;, и ги зависят от конкретной политики, ко- торой мы решили следовать. Используя значения ои связанные со старой политикой, мы можем выбрать новую политику, максимизирующую пра- вую часть равенства (11.16). Обозначив характеристики, свя- занные с этой иолчжикой, индексом и, выберем такое л ири л' котором обраи!ается в максимум сумма ~„)/.
(г.. +о.) — оь -ч !а! / он // // / /=ч где )/'.Ы означан т переходные вероятности, связанные с выбором // политики // в сссгоянии б Если для зздащюй политики определены значения а, и и, то испо.чьзоиание указанного выше правила для построе- ния новой политики называется процедурой улучшвния по- л///ппкп (Р! К)Я). Можно доказать, что это правило (а) нри каждом свсем применении приводит к политике, дающей более вь/сокий или ио крайней мере такой же вы- игрыш, (Ь) в конечном счете приведет к оптимальной политике. Доказательства этих фактов сугиесгвенно опираются на линейность нашей простой модели. Однако интуитивно не оче- видно, что решение, диктуемое приростом а, и значениями и; одной ноличики, приведет к политике с большим выигрышем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
