Материал: ОиММПР. Лекция 10

шага и до конца, если i− ый шаг начинается с некоторого состояния S . Такую величину называют условным оптимальным выигрышем Wi ( S ) .

Тогда, принимая решение на каждом i− шаге, мы должны выбрать решение Xi так, чтобы условный оптимальный выигрыш был максимальным от

i− шага и до конца.

Определение: оптимальность в малом понимается через оптимальность в большом.

Любой процесс имеет где-то окончание, т.е. имеет горизонт планирования. Тогда последний этап «не имеет будущего». Вот именно его можно оптимизировать только из условий данного этапа. После этого приступают к оптимизации ( m−1)− го этапа. Выбирают такое Xm−1 , чтобы при применении

этого Xm−1 его можно было внести в управление последнего шага. При этом мы задаём состояние, с которого начинается ( m−1)− ый шаг. Поэтому функцию Wi ( S ) называют условным оптимальным выигрышем. Таким образом, процесс оптимизации разворачивается от конца к началу, и начальное состояние становится известно. Принцип Беллмана нашёл применение в методе программно-целевого планирования (любое действие планируется некоторым проектом).

Функциональное уравнение Беллмана.

Назовём состоянием системы некоторый вектор координат: S=(ξ1 ,ξ2 , ... ,ξL) . В некоторых задачах состояние системы – одна величина. Тогда

работу системы можно представить как движение в фазовом пространстве – пространстве состояний. Назовём это - шаговым управлением – управлением на i− ом шаге. Рассмотрим процесс управления системой за m шагов. Функция

какое-то управление Ui , то система перейдёт в новое состояние S'=ϕi (S ,U i) . Эта

функция должна быть так же известна. Если эти функции не заданы, то их надо сформулировать. Введём Wi ( S )− условный оптимальный выигрыш. Это выигрыш

на всех этапах от i до конца, если i− ый шаг начинается с состояния S . Рассмотрим m шагов. Начнём с (i+1)− го шага. Предполагаем, что мы

системой управляем оптимально, величина оптимального выигрыша Wi+1 (S') . На i− ом шаге - любое управление. Wi ( S )− неоптимальный выигрыш, т. к. на i− ом шаге мы применяем управление Ui .

Это функциональное уравнение Беллмана. Для использования уравнения Беллмана оптимизацию начинают с конца:

-этап условной оптимизации

1)i=m

Wm ( S )=max {f m(S ,U m)} .

U m

2) i=m−1

Wm−1 ( S )=max {f m−1 (S ,U m−1 )+Wm [ϕm−1 ( S,Um−1 )]}

U m−1

Итак, идя от конца к началу, мы получаем последовательно:

Wm ( S ) ,Wm−1 ( S ), ... ,W 1 ( S )

Um ( S ) ,Um−1 ( S ) , ... ,U1 ( S)

Придя в начальное состояние W1(S), мы можем подставить S = S0 и W1(S0) = Wmax – это безусловный выигрыш.

- этап безусловной оптимизации

Теперь необходимо получить, идя от начала к концу по цепочке, на каждом шаге (этапе) безусловно оптимальные уравнения:

18 из 20

U1 ( S )=U1 ( S0 )=U'1

ϕ1 (S ,U 1)=ϕ (S0 ,U '1)=S'1

U2 ( S )=U'2

ϕ2 (S ,U 2)=ϕ (S'1 ,U'2)

Итак, в конце мы получаем безусловно оптимальное решение:

U'1 ,U'2 , ... ,U'm ;W max

Пример: транспортная задача.

Все вышеприведенное определено для конечных вариационных задач, т. е. основано на методе обратного прогона.

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

f (p; S+T )=lim sup ( pD ;T ) ,

D [0 , S]

который предполагает, что супремум фактически достигается и в пределе может

ограниченная замкнутая область состояний, S — состояние в точке t интервала

[0,T].

В теории динамического программирования имеется еще один важный метод приближения, который называется «приближением в пространстве поведений». Он рассматривает естественную двойственность между функцией f(p), описывающей максимальный функционал, и оптимальным(-и) поведением(- ями) q=q(p). В задаче q рассматривается как индекс поведения (управления) среди всех возможных по множеству поведений Q для D.

19 из 20