Функция Беллмана

Перейдем к вопросам сходимости в вычислительной схеме Н. Н. Моисеева. Основное осложнение связано с тем, что теперь в разностной задаче (7) точки х могут принимать лишь дискретные значения а ., принадлежащие сетке 5. Поэтому в принципе может оказаться, что ни для какой пары точек из соседних сеток я., ж +1 не удастся построить соединяющей их траектории (1) на малом интервале [tt, t +1]. В этом случае разностная задача просто не имеет решения. Чтобы избежать этой опасности, следует наложить определенные ограничения на /г-шаг сетки по фазовым координатам. Кроме того, нужно гарантировать разрешимость элементарной операции. Эти вопросы исследовались в работах [56], [37]. Разрешимость разностной задачи и сходимости численного решения к решению задачи (1)—(5) была доказана в предположении некоторых свойств непрерывности функции Беллмана решаемой задачи. Однако для практики вычислений более существенным является другое условие шаги сетки hr по r-й компоненте фазового пространства должны быть связаны с шагом сетки по времени т соотношением ftr=T1+P>-, где рг 1 — некоторые числа, зависящие от строения области достижимости за малое время т для системы (1). Напомним, что областью достижимости D (Z, t) называется совокупность правых концов траекторий системы x=f (х, и), х (0)=z при произвольных измеримых и (t), и ( ) U, О t т. В работе автора [93] те же вопросы были решены только с одним предположением h—0 (t2). При этом под элементарной операцией следует понимать решение следующей простой геометрической задачи, являющейся аппроксимацией дифференциальной на малом интервале времени. Для расширенной системы (1) (пополненной уравнением x°=f(x, u), х° (0)=0) строится в каждой точке х область x- -tf (х, U) (если / (х, U) не выпукла, следует заменить ее выпуклой оболочкой). Далее эта область расширяется присоединением всех сфер радиуса ft2 с центрами в ж+т/ (x1U), Полученную область в пространстве х°, х1,.. ., хп обозначим DT (х), а ее проекцию на гиперплоскость х1, а 2,. ... . ., х" — jD (х). Если шаги сеток А=ста, то при определенном соотношении между с и С можно утверждать, что для любой точки xlj 5" найдется хотя бы одна точка xj.+i 5 41 такая, что  [c.125]


Эта функция (функция Беллмана) имеет простой содержательный смысл. Пусть в момент tn система находится в состоянии х1, ж2 , и определяется оптимальное управление на отрезке ( , Т). Тогда Fn (х1, ж2) есть минимальное значение ж1 (Т0). Функции Fn последовательно вычисляются для n=N, N — 1,. . ., 1, с помощью уравнения динамического программирования (см. 44).  [c.305]

Решение задачи осуществляется специальным алгоритмом, использующим типичную для динамического программирования функцию Беллмана Fn (/). Определяется она следующим образом. Рассмотрим часть задачи пусть система в момент п находится в состоянии /. Нужно перевести ее к моменту N, минимизируя за счет выбора состояний /я+1,. ..,/> значение  [c.387]

Функции Беллмана F для ПЗР определяются соот-  [c.344]

Формулы (4) являются следствием соотношений Беллмана (3). Согласно формуле (4) оптим. значения ресурса определяются поэтапно на f-м этапе исследуется t-ii способ использования ресурса, причём к этому моменту уже выделены ресурсы для использования по предыдущим способам (распределению подлежат лишь qt единиц ресурса), а влияние последующих способов учитывается с помощью функции Беллмана  [c.344]


Функции/ /),/г(0, - /я(0. учитывающие вклад последующих шагов в общий эффект, называются функциями Беллмана - по фамилии американского математика Р. Беллмана, создателя метода динамического программирования. С помощью этих функций ведется анализ задач динамического программирования. Очевидно, если мы сумеем вычислить / ( о) и найти политику замен, то это и будет решение задачи.  [c.369]

Для принятия окончательного решения вычислим функцию Беллмана вида  [c.371]

Используя полученные формулы, вычислим значения функций Беллмана/ (/) при различных я и А Значения функций будем вписывать в табл. 11.2.  [c.372]

Величина максимальной прибыли (согласно табл. 11.2) определяется функцией Беллмана/10(7) = 60. Теперь найдем оптимальную политику, обеспечивающую эту прибыль.  [c.374]

Эффективность динамического программирования обусловлена использованием рекуррентных формул (11.3 11.7), позволяющих осуществить рациональный процесс поиска оптимальных вариантов, чем полный перебор вариантов. Это делается при помощи функций Беллмана, несущих информацию об оптимальном продолжении процесса.  [c.374]

Используя рекуррентное соотношение (9.58), последовательно находят функции Беллмана ф2 (г),. . ., Ф 1(г) и значение функции ф (г) при z = b. Одновременно определяют xl(z),. .., x z) и ( ).  [c.225]

Функционал 28 Функция Беллмана 225  [c.330]

Функционал (3) принято называть опорным. По определению опорный функционал совпадает с функцией Беллмана S. Основное ее свойство заключается в том [4], что в конечный момент времени она численно равна терминальному члену функционала, т.е.  [c.99]

Последнее требование означает, что решение уравнения ( 1 6) должно совпадать с функцией Беллмана У(1,хаа) = 8(1,хая), а опорный функционал должен являться оптимальной функцией Ляпунова на заданном отрезке времени при любом допустимом векторе управления. Поэтому поиск ОУ, определяемого через решение задачи Коши (16)-(17), должен исключать непосредственное использование процедуры типа и -и  [c.101]


Функция Беллмана (i, т) удовлетворяет уравнению динамического программирования  [c.141]

Хорошую модель составить непросто. По словам Р. Беллмана, если мы попытаемся включить в нашу математическую модель слишком много черт действительности, то захлебнемся в сложных уравнениях, содержащих неизвестные параметры и неизвестные функции. Определение этих функций приведет к еще более сложным уравнениям с еще большим числом неизвестных параметров и функций и т. д.  [c.100]

Получившаяся постановка, т.е. задача (1.5.31), (1.5.32) с функциями g°, g, заданными согласно (1.5.38), (1.5.39), принадлежит так называемому классу линейно-квадратичных оптимальных задач, бывшему весьма популярным в литературе 1960-70 годов. Наиболее эффективные результаты здесь были получены с использованием уравнения Беллмана. Применим для решения задачи теорему Кротова, включающую в себе, как частный случай, и уравнение Беллмана [Кротов и др., 1973].  [c.74]

Известны строгие математические методы решения задач оптимизации (например, симплекс-метод и распределительный метод для линейных задач, метод градиента для задач нелинейных, методы Беллмана для задач динамического планирования и т. д.). Но в аудите эти методы в настоящее время не применимы в силу неразработанности формальных или стохастических (вероятностных) зависимостей между варьируемыми факторами, с одной стороны, параметрами оптимизации и ограничивающими функциями — с другой. Поэтому приближение к оптимальности достигается, как это предусмотрено общероссийским стандартом Планирование аудита , эмпирически — вариантностью планирования, выявлением в ходе планирования областей повышенного риска, корректированием принятых решений в ходе проверки.  [c.137]

Отметим основное отличие данной реализации метода динамического программирования от схемы вычислений 15. Оно связано с использованием интерполяции функции Беллмана F (х1, х ) с узлов сетки. Этим снимается ограничение на шаг сетки в фазовом пространстве типа h=o (t), необходимое в схеме метода Н. Н. Моисеева. Вместе с тем интерполяция является источником определенных ошибок, тем более, что сетки приходится брать сравнительно грубые. Кроме того, используя интерполяцию, неявно предполагают наличие у функции Беллмана таких свойств гладкости, которых может и не быть. Известны простые примеры задач, в которых функция Беллмана разрывна, а наличие разрывов производной может считаться почти общим явлением. Схема вычислений 15 может быть (при h=0 (t2)) обоснована без всяких предположений о свойствах функции Беллмана. Что касается реализации алгоритма на ЭВМ, то в данном случае наибольшие ограничения связаны с ресурсом памяти. Вычисления в [4] тре= буют N таблиц по 30x30 величин, однако при вычислении очередной функции Fn (х1, х2-) в оперативной памяти нужно иметь только две такие таблицы.  [c.307]

Метод П. д. позволяет существенно сократить перебор вариантов, необходимый для отыскания оптимального. Напр., в ПДЗ общее число вариантов деятельности предприятия равно /с . Поэтому для решения ПДЗ путём непосредств. сравнения всех вариантов, требуется nkn — 1 операций. Вычисление всех необходимых значений функции Беллмана ПДЗ и реализация процесса последоват. определения оптим. выпусков  [c.344]

Приведенная в 1с Супермартингальная характеризация последовательности Y — (Уп) относительно каждой из мер семейства Р(Р) не покажется неожиданной, если операцию взятия ess sup в (12), 1с, интерпретировать как оптимизационную задачу выбора "наилучшей" вероятностной меры. При таком понимании интересующее нас супермартингальное свойство есть не что иное, как одно из утверждений широко известного "принципа оптимальности" которому удовлетворяет процесс-цена ("функция Беллмана") в стохастических оптимизационных задачах.  [c.170]

Следует отметить, что известные достаточные условия оптимальности [7,9] приближенного синтеза управлений сформулированы в терминах произвольной вспомогательной функции со свойствами функции Ляпунова. Развиваемый же нами подход основан на введении опорного функционала со свойствами функции Беллмана (задача Коши (4), (5)) и линеаризации системы (1) относительно заранее неизвестной вектор-функции ОУ. Функционал качества (13) также оказывается полуопределенным и относится к неклассическим в том смысле, что содержит вектор ит.  [c.100]

Задача определения кратчайших маршрутов на заданной транспортной сети. Следует заметить, что для минимизации целевой функции ф( ж.. ) в транспортной задаче нужно, чтобы "стоимости" с.., входящие в выражение (2.3) для нее, уже были бы минимальны. Таким образом, возникает еще одна оптимизационная задача, связанная с отысканием "кратчайшего" маршрута LOT г-го склада до j-ro потребителя на заданной дорожной сети. Рассмотрим постановку этой задачи. Дана матрица dj длин участков дорожной сети, соединяющих узлы с номерами s и t. Если между какими-либо узлами дорожной сети нет прямого сообщения, то на соответствующем месте в матрице ничего не проставлено. Заметим, что элемент ds( в общем случае может отличаться от элемента d(s в силу, например, одностороннего движения в том или ином направлении. Требуется определить кратчайший маршрут между узлом s и каким-либо другим узлом t. Для решения задачи исходные данные заносят в матрицу. Далее применяют или алгоритм Беллмана динамического программирования, или метод Дейкстры, который является его модификацией. Эти алгоритмы весьма просты, и справку по ним можно найти, например, в справочнике [39].  [c.161]

Приближенное решение задач оптимального управления (1978) -- [ c.125 , c.305 ]