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».

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
25 26 27  Наверх ↑