1.5. Принцип оптимальности Беллмана
Согласно Р. Беллману, основной принцип оптимальности управления многошаговыми процессами может быть словесно выражен следующим образом: «Оптимальное поведение обладает тем свойством, что, каковы бы ни были исходное состояние и первоначальное решение, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первоначального решения». Иными словами, любой участок оптимальной траектории, в том числе и завершающий, также является оптимальным, а ошибки в управлении, приводящие к отклонениям от оптимальной территории, впоследствии не могут быть исправлены. Конечно, столь общее положение не может быть непосредственно применено к решению задач ДП и нуждается в конкретизации.
Для строгой формулировки принципа оптимальности введем, как и выше, ряд вспомогательных функций 2?о(хо), В\(х1), • • •, #дг(ждг). Функции Вг(хг), г = 0,1,2,... , ./V, имеют важный экономический смысл и представляют собой максимальные значения (рассмотрим для определенности случай задачи на поиск максимума) сумм частных целевых функций
Ч+1{Хг,Щ+г) + . . . + глг(жлг-1,г4лг), вычисляемые по всем допустимым «укороченным» наборам управлений («г+ь • • • 5 им). Иными словами, — условно-оптимальное значение целевой функции при переводе системы из состояния X, после шага с номером I в конечное состояние х/у; условность оптимального значения состоит в том, что оно относится не ко всему процессу, а к его заключительной части, и зависит от выбора состояния х^, являющегося начальным для «укороченного» процесса. Тем самым функции Вг(хг), называемые функциями Беллмана, характеризуют экстремальные свойства управляемой системы 5 на последних шагах процесса. При этом имеет место простое и важное соотношение
Вк(хм) — О,
справедливое по той причине, что состояние X /V уже является конечным, дальнейших изменений состояний системы не происходит, и соответствующий экономический эффект равен 0.
Принцип оптимальности Р. Беллмана, лежащий в основе метода ДП решения рассматриваемых задач, выражается следующим основным функциональным уравнением:
Вг- 1(Хг-\) = та+Вг(Хг) \ Х{ = /г , щ) }, (*)
гц
в котором индекс г изменяется по номерам всех шагов процесса в обратном порядке: г = Ы, N — 1,..., 2,1.
По своей структуре функциональное уравнение Беллмана является рекуррентным. Это означает, что в последовательности функций Во(хо), В\(х\),..., Вн(хн) каждая предшествующая выражается через последующую
Важно подчеркнуть, что при вычислении максимума в функциональном уравнении Беллмана для каждого фиксированного значения одновременно с определяется то значение переменной щ (одно или несколько), для которых этот максимум достигается. Это значение зависит от состояния Жг-ъ и обозначать его будем через щ{х1-х) (символ называемый «тильда», служит в алфавитах различных языков на латинской основе для указания передачи буквой особого звучания, а в математике часто обозначает некоторую условность
^ Здесь можно провести простую аналогию с известной функцией «факториал», определяемой равенством п! = 1 ■ 2 ■. .. • (га — 1) ■ га; для нее справедливо рекуррентное соотношение га! = га ■ (га — 1)!, показывающее, каким образом значение факториала га! выражается через предшествующее значение (п — 1)\.
или приближенность). Фактически является (возможно, мно
гозначной) функцией, называемой условно-оптимальным управлением (условность заключается в зависимости управления от выбора состояния Xi-l). И хотя функции Üi(Xi-1) явно не фигурируют в уравнении (*), они играют не менее важную роль, чем функции Беллмана ßj_i(xj_i), и используются для окончательного построения оптимального решения. Таким образом, при проведении расчетов последовательно вычисляются и запоминаются условно-оптимальные управления ün(xn-i), ün-i(xn-2), •■■, йг(жо)-
Следует заметить, что принцип оптимальности Беллмана рассматривает конкретную решаемую задачу с оптимальным значением Во(хо) не обособленно, а как представителя семейства подобных ей задач с оптимальными значениями В\(х\),..., меньшей размерности, т.е. более простых. Между задачами этого семейства существует связь, которая описывается функциональным уравнением (*) и позволяет, начиная с простейшей функции Bn(xn) — 0, последовательно вычислить все остальные функции Bn—\(xn—\), ..., 2?о(жо)> т. е. фактически получить решения всего семейства задач. Данный прием, заключающийся в замене задачи семейством однотипных задач, в результате решения которых находится решение исходной задачи, называется принципом инвариантного погруженим.
Полностью аналогичное выражение имеет принцип оптимальности и для решения задач на минимум', при этом в функциональном уравнении (*) обозначение максимума «max» просто меняется на обозначение минимума «min».
25 26 27 Наверх ↑