Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 60
Текст из файла (страница 60)
Иногда область допустимых решений ограничивалась дополнительными условиями. Параметры состояния, описывающие систему, были как дискретными, так и непрерывными, а сами процессы — как детерминированными, стохастическими, так и адаптивными. В первых девяти главах дан единый вычислительный алгоритм, одинаково применимый к линейным и нелинейным критериям, к детерминированным и стохастическим процессам. Будучи общим методом, он не нуждается в перекройке для применения к конкретному процессу. В главе Х показано, как можно,воспользовавшись конкретной аналитической структурой задачи, дать вычислительные алгоритмы более простые, чем даваемые классическими методами или прямым методом динамического программирования. На последующих страницах мы намерены описать несколько дополнительных способов, позволяющих воспользоваться индивидуальной аналитической структурой задачи оптимизации для существенного упрощения ее численного решения.
Во многих случаях задачи аттимизации разрешимы во 382 МАРКОВСКИЕ ПРОЦЕССЫ РЕШЕНИЯ 1гл. х! всей общности ~олько при использовании этих более тонких и искусных методов. Сначала мы хотим рассмотреть некоторые задачи, занимающие привилегированное место в динамическом программировании, а по существу и в математическом анализе. Сюда относятся задачи, которые обладают некоторыми чертами линейности. В искусстве построения математических моделей одной из наиболее трудных является задача уравновешивания реалистического описания и мощности существующего аналитического и вычислительного аппарата.
Довольно часто упрощенные до бессмысленности задачи решаются тщательным образом, в то время как чрезмерно сложные процессы остаются без внимания, причиной чего являются математические трудности. Несмотря на некоторую опасность построения линейных моделей для задач реального мира, трудно отказаться от эстетического наслаждения, которое дает получение точных решений. Примирение этих двух сторон — один из камней преткновения прн построении моделей. Численные результаты этой главы основаны главным образом на работе Р.
Ховарда. Многие дальнейшие результаты можно найти в его книге, упомянутой в конце главы. 2. МДРКОВСКИЕ ПРОЦЕССЫ Прежде чем говорить о марковских процессах решения— частном случае секвенциальных процессов решения, которые мы хотим рассмотрегь в этой главе,— необходимо пояснить, что такое процесс Маркова. Рассмотрим систему, которая в любой фиксированный лшмент времени может находиться в одном из конечного числа состояний, которые мы перенумеруем числами 1= 1,2, „ ., Лг, и предположим,что в дискретные моменты времени 1= 0,1, „, система переходит из одного из этих состояний в другое, Далее, пусть процесс перехода происходит не детерминированно, а стохастически и управляется переходной матрицей Р= (рй), где Рг — веРоЯтность того, что система в момеит 1 + ! Наводятся в состоянии у, если известно, что в момент 8 (1 1.
1) оиа была в состоянии й мхяковбкий пяоцвсс Ряшвния ййз Мы рассмотрим здесь важный случай, когда переход- ная матрица Р не зависит от времени. Это — наиболее инте- ресный случай, Введем следующие функции: х! (!) — вероятность того, что система в момент ! находится в состоянии 1, ! = 1,2,..., АГ, где предполагается, что ! принимает только значения О, 1„., Тогда элементарные правила теории вероятностей приводят к уравнениям х, + ! (!) = ~Ч~~ р! х, (!), / = 1, 2, ..., А!, ю= ! х,(!)=гг Теория марковских процессов посвящена изучению асиыптотического поведения функций х,(!) при ! — со. Если все переходные вероятности рп положительны, то не составляет большого труда доказать, что эти функции сходятся при ! — се! к величинам х(!), удовлетворяющим уравнению «стационарного режима» !е х(()='~'„р!!х(!), у=1, 2,..., Аг. (11,4) г=! Сходи»!ость этих функций при ! — со, по-видимому, не является слишком неожиданной, если принять во внимание свойство перемешивания, содержащееся в условии, что все р;, положительны.
Неожиданным же в этом случае является тот факт, что предельные значения не зависит от первоначального состояния системы, т.е. от значений х,(!). Именно эта математическая идея объясняет необходимость тщательного тасования карт. Действительно, чаще всего тасование делается довольно небрежно, и при игре в бридж большую информацию о картах противника можно получить, помня взятки при предыду!цей сдаче. 3. МАРКОВСКИЙ ПРОЦЕСС РЕШЕНИЯ Теперь мы хотим перенести понятие марковского процесса на более общие ситуации, в которых решения принимаются на каждом шаге.
Предположим, что на каждом шаге в качестве переходной матрицы может быть выбрана одна из мликоаскив пгопяссм Рншвиия (гл. х~ множества ааких маарнц, и обозначим матрицу, соответсгвуюшую политике ~у, через Р(д)=(р;,(д)). Предположим далее, что меняется не только состояние на каждом шаге, но также и доход, который является функцией начального и конечного состояний и решения. Пусть )с' (г1) = (г;;(д) ) означает соответствующую матрицу доходов.
Процесс такого типз нззывается марковским прог(ессом решения. Жы хотим рассмотреть здесь задачу о выборе последовательности решений, максимизирующнх математическое ожидание дохода, получаемого в Аг-шаговом процессе, при заданном начальном состоянии системы, 4. ПРИМЕР— ЗАДАЧА О ТАНСИ Прежде чем перейти к аналитическому рассмотрению задач такого рода, посмотрим, как весьма естественным образом они возникают. В качестве иллюстрации дадим упрощенный вариан~ операции пробега такси.
Удобство примера тзкого рода состоит в том, что он позволяе~ нам придать конкретный смысл таким понятиям, как «переходная матрица», «альтернативные решения» и т.д. Предположим, что водитель такси обслуживает окрестности трех городов. Если сн находится в городе 1, ~о перед ним стоят три альтернативы. (1) Он может курсировать в надежде, что его остановит пассажир. (2) Он может подъехать к ближайшей стоянке такси и ожидать в очереди. (3) Он может иключиться в радиосеть и ожидать вызова по радио. В городе 3 он имеет такие же альтернативы, а в городе 2 последняя альтернатива отсутствует, так как в этом городе нет обслуживания пассажиров с помсщью радио. Для каждой фиксированной альтернативы в каждом городе задаются вероятности того, что следующая поездка произойдет в любой из городов 1, 2 и 3, и соответствующие известные доходы в денежных единицах, связанные с каждой поездкой.
Поскольку каждой альтернативе соответствуют разные совокупности клиентов, веров~ности перехода и доходы зависят от альтернатив. примяв — адддчд о такси Если им приписать некоторые гипотетические числа, то данные задачи можно записать в виде таблицы 11. 1. Таблица 1!.! Переходная нераятность доход Состояние о арод! Ааьтерна- тнаа а г = ! а а у =- 1 1 4 3 4 ! 8 7 8 1 4 3 4 1 16 Т!оясним таблицу на примере предпоследней строки. Из нее видно, что, если водитель находится в городе 3 и выбирает вторую альтернативу, то с вероятностью одна восьмая попадегся клиен~, желаюший поехать в город 7, причем доход от этого равен 6; с вероятностью три четверти произойдет поездкз в город 2, дающая доход 4, и с вероятностью одна восьмая произойдет поездка внутри города 5' с доходом в две единицы.
В этой задаче имеются три состояния, т.е. И= 3, и три альтернативы в состояниях 1 и 3 и две в состоянии 2, т,е. л, = 3, ла= 2, л,= 3. Значит, имеется 3 2 3 = 18 возможных политик. После того кзк будут изложены методы решения, мы вернемся к этой зздзче и продемонстрируем ее численное решение. ту 12 Р. Беллмен, С дрейфус 1 2 ! 16 1 4 1 2 1 !6 ! 4 1 8 3 4 1 4 3 16 5 8 1 2 ! !6 ! 2 1 8 3 16 1О 4 8 8 2 4 4 6 ' 4 14 О 18 8 !6 8 1О 2 8 6 4 2 4 О 8 МАРКОВСКИР ПРОЦБССЫ РБШБНИЯ (гл.
Х! б. АНАЛИТИЧЕСКАЯ аОРМЬЛИРОВНА Используем теперь аппарат функциональных уравнений для получения аналитической формулировки задачи, поставленной в З 3. Пусть для 1=1, 2, ..., Л'; п=0, 1, ... У„(1) — ожидаемый доход при и-шаговом пропсссс, если начать из состояния г и использовать оптимальную политику. (11.5) Захгетидг, что и означает длину процесса, тогда как используемое в предшествующих параграфах, означало аре.ня. Тогда принцип оптимальности приводит к рекуррентным соотношениям у„(г) = пгах1 ~' ры(гу) (г;, (г))+у„г (1)), (11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
