1.5. принцип оптимальности беллмана

1.5. принцип оптимальности беллмана

Согласно Р. Беллману, основной принцип оптимальности управления многошаговыми процессами может быть словесно выражен следующим образом: «Оптимальное поведение обладает тем свойством, что, каковы бы ни были исходное состояние и первоначальное решение, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первоначального решения». Иными словами, любой участок оптимальной траектории, в том числе и завершающий, также является оптимальным, а ошибки в управлении, приводящие к отклонениям от оптимальной территории, впоследствии не могут быть исправлены. Конечно, столь общее положение не может быть непосредственно применено к решению задач ДП и нуждается в конкретизации.

Для строгой формулировки принципа оптимальности введем, как и выше, ряд вспомогательных функций Bq(xq), Bi(xi), ..., BN(xN). Функции Ві(хі), і = 0,1,2,... , N, имеют важный экономический смысл и представляют собой максимальные значения (рассмотрим для определенности случай задачи на поиск максимума) сумм частных целевых функций

Zi+i(Xi,ui+i) + ... + zn(xn-i,un), вычисляемые по всем допустимым «укороченным» наборам управлений (ttj+i,..., itjv)Иными словами, Ві(хі) — условно-оптимальное

Значение Целевой функции При Переводе СИСТеМЫ ИЗ СОСТОЯНИЯ Xi

после шага с номером і в конечное состояние х^; условность оптимального значения состоит в том, что оно относится не ко всему процессу, а к его заключительной части, и зависит от выбора состояния хі, являющегося начальным для «укороченного» процесса. Тем самым функции Ві(хі), называемые функциями Беллмана, характеризуют экстремальные свойства управляемой системы S на последних шагах процесса. При этом имеет место простое и важное соотношение

BN(xN) = О,

справедливое по той причине, что состояние ждг уже является конечным, дальнейших изменений состояний системы не происходит, и соответствующий экономический эффект равен 0.

Принцип оптимальности Р. Беллмана, лежащий в основе метода ДП решения рассматриваемых задач, выражается следующим основным функциональным уравнением:

Bi-i(xi-x) = max.{zi(xi-i,Ui) + Ві(хі) хі = /і(хі_і,щ)} , (*)

Ui

в котором индекс і изменяется по номерам всех шагов процесса в обратном порядке: і = N, N — 1,..., 2,1.

По своей структуре функциональное уравнение Беллмана является рекуррентным. Это означает, что в последовательности функций Во(хо), Bi(x),... ,Bn(xn) каждая предшествующая выражается через последующую

Важно подчеркнуть, что при вычислении максимума в функциональном уравнении Беллмана для каждого фиксированного значения Xi-i одновременно с Ві-\{хі-) определяется то значение переменной щ (одно или несколько), для которых этот максимум достигается. Это значение зависит от состояния х{-, и обозначать его будем через йі(жг_і) (символ «~», называемый «тильда», служит в алфавитах различных языков на латинской основе для указания передачи буквой особого звучания, а в математике часто обозначает некоторую условность

^ Здесь можно провести простую аналогию с известной функцией «факториал», определяемой равенством п! = 1 ■ 2 ■. .. • (га — 1) ■ щ для нее справедливо рекуррентное соотношение га! = га • (га — 1)!, показывающее, каким образом значение факториала га! выражается через предшествующее значение (п — 1)!.

или приближенность). Фактически щ(х^) является (возможно, многозначной) функцией, называемой условно-оптимальным управлением (условность заключается в зависимости управления от выбора состояния Жі_і). И хотя функции йі(Хі-і) явно не фигурируют в уравнении (*), они играют не менее важную роль, чем функции Беллмана Ві-(хі-), и используются для окончательного построения оптимального решения. Таким образом, при проведении расчетов последовательно вычисляются и запоминаются условно-оптимальные управления un{xn-), un-i(xn-2), ui(xq).

Следует заметить, что принцип оптимальности Беллмана рассматривает конкретную решаемую задачу с оптимальным значением Bo(xq) не обособленно, а как представителя семейства подобных ей задач с оптимальными значениями Bi(xi),..., Bn(xn) меньшей размерности, т.е. более простых. Между задачами этого семейства существует связь, которая описывается функциональным уравнением (*) и позволяет, начиная с простейшей функции Bn(xn) — 0, последовательно вычислить все остальные функции Bn-i(xn-i), • • • > Во(хо), т. е. фактически получить решения всего семейства задач. Данный прием, заключающийся в замене задачи семейством однотипных задач, в результате решения которых находится решение исходной задачи, называется принципом инвариантного погружения.

Полностью аналогичное выражение имеет принцип оптимальности и для решения задач на минимум; при этом в функциональном уравнении (*) обозначение максимума «тах» просто меняется на обозначение минимума «min».