Пусть мы ищем решение задачи.

ОПТИМИЗАЦИЯ С ДИСКРЕТНЫМ ВРЕМЕНЕМ

Динамическое программирование

Система наблюдается в моментах времени

Состояние системы характеризуется числом . Известно значение _.Система меняет своё состояние под воздействием управлений , которые можно свободно выбирать из заданного множества которое назовём областью управления.Управления влияют на состояния системы по правилу

, (1)

где – заданная функция.

Предположим, что выбраны величины _.Тогда, начиная с ), далее получим ) и т.д.

Таким образом, каждому выбору управлений соответствует свой путь (или график).

Пусть имеется функция такая, что польза от выбранного пути есть сумма:

(*)

Эта сумма носит название целевой функции.

Иногда вместо пишут .

Вместе с любой заданной последовательностью находим последовательность и получаем соответствующие допустимые пары. При этом целевая функция принимает определенное значение.

Задача состоит в том, чтобы среди всех наборов допустимых пар и найти оптимальный набор пар , , дающий наибольшее значение целевой функции.

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

найти

при условиях , задано, (2).

Рассмотрим пример реальной задачи, которая решается по изложенной выше схеме.

Пусть средства в момент В каждый момент пусть часть, используемая для потребления, – часть для сбережения. Средства можно употребить в дело с уровнем прироста . После изъятия количества средств , остаток средств идёт в дело. При этом, с учётом прироста, получаем .

Пусть польза от потребления равна .

Пусть функция возрастает и выпукла вверх по .

Вся полученная польза равна:

Итак, решается задача:

Найти при условиях

задано, , .

Свойства целевой функции.

Пусть при система имеет значение x. Наилучшее, что можно сделать в оставшийся период – выбрать (следовательно, ) так, чтобы максимизировать при .

Назовем оптимальной целевой функцией для этой задачи в момент s.

(3)

где , , , (4)

Управления, максимизирующие (3) при условиях (4), зависят от х. В частности, зависит от х.

Управления, зависящие от состояния системы назовем политиками.

Если мы напишем для каждого политику, то мы тем самым решили задачу (2)

Рассмотрим важное свойство целевой функции. При имеем

Пусть при система в состоянии . При выборе при получен выигрыш , при этом система окажется в состоянии

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

Следовательно, наилучшим выбором для будет то, которое максимизирует сумму

Теорема: Пусть обозначает целевую функцию в момент

, ,

для задачи найти:

(5)

при условиях , – задано,

Тогда удовлетворяет уравнениям

(6)

(7)

Замечание: Разумеется значения выбираются среди решений разностного уравнения (1) при фиксированном и возможных выборах .

Обычно эта теорема используется так: ищем функцию (7).

Максимизируются значение U*_T (x). Следующий шаг – используя (6) найти J_T_-1(x) и соответствующую W*_T_-1(x). Действуя аналогично, находим все J_T (x), J_T_-1(x),….,J₀(x) и соответствующие U*_T(x), U*_T_-1(x),…,U*₀(x).

Это позволяет построить решение исходной задачи оптимизации.

Пример.

Рассмотрим задачу найти:

max , при условиях , t=0, 1, 2, , .

Здесь T=3, f(t,x,u)=1+x-u² , g(t,x,u)=x+u.

Из (7) при T=3получаем, что J₃(x) представляет собой наибольшее значение функции , .

Оно получается при u=0, т.е. J₃(x)=1+x, .

При s=2 функция максимизируется, обозначим ее h₂(u)=1+x-u²+J₃(x+u)

Так как J₃(x)=1+x, J₃(x+u)=1+(x+u) и h₂(u)=1+x-u²+1+x+u=2+2x+u-u²; h₂’(u)=1-2u, h₂’(u)=0, u=1/2, h₂(u) выпукла вверх, то u, u₂*(x)=1/2, J₂(x)=h₂(u₂*(x))=2+2x+1/2-1/4=2x+9/4.

При s=1 мы максимизирует функцию h₁(u)=1+x-u²+2(x+u)+9/4=3x+2u-u²+13/4

h₁’(u)=2-2u; h₁’(u)=0, u=1.

Находим u₁*(x)=1 и J₁(x)=3x+2-1+13/4=3x+17/4.

При s=0 максимизируется функция

Укажем оптимальные значения состояния системы:

Оптимальное значение целевой функции:

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

Полагая в уравнении

последовательно получаем

Таким образом, максимизация целевой функции равна

- матрица 2 дифференциала

По критерию Сильвестра второй дифференциал – отрицательно определенная форма следовательно получаем тоже максимум

Подобный подход возможен в любой задаче, но он слабо реализуем при больших T.

Рассмотрим еще одну задачу :

Найти

max

при условии

Поскольку и
для t выполняется неравенство

Далее , независимо от u , и поэтому и любое решение оптимальнее

Уравнение (1) при S=T-1 дает

Первая производная по u функции равна

1+ux=3/2, ux=1/2.

При этом .

Итак, ( )

Рассмотрим уравнение (6) при

Снова получаем

при этом

Очевидно, что далее, продолжая процесс, получим

Подстановка в разностное уравнение дает =

При этом .

Примечание

Теорема справедлива и в том случае, когда область управления не фиксирована, но зависит от и , . Тогда максимизация в (2), (3), (5) выполняется при . В (6)(стр. 7),(7)(стр. 7) максимизациявыполняется при и , соответственно.

Часть множеств задается набором неравенств .

Если - пустое множество, то принимается соглашение, по которому максимум взят по этому множеству равен - .

Рассмотрим задачу, в которой

= ( - ), > 0, - заданные положительные числа

= , r – уровень дисконтирования, 0 < < , (0, 1), A>0

Ищется

max ( + ) (I)

В соответствии со сделанным замечанием, = (0, x)

f(t, x, u) = , t = 0, 1, … T-1

f(T, x, u) = - эта функция от u не зависит, и ее максимум, равный совпадает с ней самой, = (II), и любое = (0, x) – оптимальное.

Из (6) получаем

= + (x-u))] (III)

При s = T-1

= + ] (IV),

так как

(x-u)) =

Для обозначим

g(u) = +

Тогда g’(u) = (1-) + (1-)(-1)

g’(u) =0 ó = (-1)

= 1 + = (V)

u =

так как g’(u) = (1-)(-) + (1-)(-) , < 0,

поэтому максимизирует g(u)

g ( ) = + A =

= + = (1 + A ( -1)) =

A =

= (1 + -1) = (VI)

Тогда ввиду (IV), (VI) (в (VI) вычитаем max y(u), подставляем в (IV))

(x) =

Отметим, что имеет тот же вид, что и

Для s= T-2

(x) =

По аналогии со сделанным выше находим, что максимум достигается при = u = , где = 1+ и где (x) =

Продолжая аналогично, находим для любого t

(x) = , где = A, а для при t<T имеем

= 1+ = 1 +

Оптимальное управление:

(x) = , t<T

Для нахождения оптимальных подставляем эти значения в рекурсивное уравнение

Предположим что для всех t тогда

линейное уравнение первого порядка с постоянным коэффициентом

См раздел 14 страница 1

Уравнение Эйлера

Рассмотри задачу найти (1) при заданном значении и свободно изменяющихся

С другой стороны часто можно переформулировать задачу динамического программирования в виде (1)

Если положить получим задачу с U=R

Предположим что уравнение при любом выборе и имеет единственное решение U

Определим f( )=f(t, x_t, )= при

t<T и .

Иными словами,

Пусть , … , - оптимальное решение задачи (1). Для любого заданного t производная выражения (1) по равна 0. Положим , тогда , … , удовлетворяют уравнению Эйлера:

(2)

номер переменной функции F, по которой взята производная

t=0,1,…,T

Это разностное уравнение второго порядка, подобное уравнению Эйлера из вариационного исчисления.

При t = T уравнение (2) переходит в , из которого находим

Эта величина подставляется в (2) при t = T-1 и получаем и т.д., так не получим , а задано

Рассмотрим задачу

найти

Положим, для t=0,1,2

при t=0,1,2

Поэтому уравнение Эйлера при t=0,1 принимает вид

При t=2 уравнение Эйлера имеет вид

так как

Построим

не участвует в построении уравнения Эйлера: .

При

Подставим в , учтем, что ,

;

Тогда , .

Свести к задаче динамического программирования можно так:

, ;

Infinite Horizon

Неограниченный период.

Проблема ставится так:

найти (1)

при условии, что - заданное число,

…

, – допустимая пара последовательностей, если - задано, , определяется уравнением . При этом , g не зависят от переменной t явно. Таким образом (1) называется автономным рядом.

f удовлетворяет условиям ограниченности для всех x,u, u . Поэтому ряд в (1) сходится. Сравним с прогрессией.

Пусть = (u_s , u_s₊₁ , …) – последовательность управлений, гдеu_s₊_kU, k = 0, 1, … ;x_t₊₁ = g(x_t , u_t), t = s, s+1, … ; x_s = x.

Тогда польза, полученная за период t = s, s+1, … равна

Положим, что

и максимумы взяты по всем последовательностям .

Таким образом, – максимальный успех, который можно получить от t=s до +.

При условии, что в момент t=s система находится в состоянии x, называется оптимальной целевой функцией для задачи (1).

Имеем

Максимизируя получаем одно и то же значение в обоих случаях, поскольку будущее (+) выглядит вполне одинаково в момент 0 и в момент s.

Из (5) следует:

Положим, по определению

Из (6) следует, что если мы знаем , то мы знаем для всех s.

Теорема. Целевая функция в (4) для задачи (1) удовлетворяет уравнению Беллмана.

J (x) = max [f(x,u)+ßJ(g(x,u))] (8)

uÎU

Грубое рассуждение напоминает рассуждения для конечного периода Т. Предположим, что мы при t=0 находимся в состоянии х. Выбрав управление u, получаем о f(x,u)=f(x,u) и во время t=1 попадаем в x₁=g(x,u).

Выбор оптимальной последовательности управлений при t=1 и так далее даёт прибавку в последующий период J₁(g(x,u))=J(g(x,u)). Следовательно, наилучший выбор при t=0, тот что максимизирует сумму f(x,u) +J(g(x,u)), поэтому максимум этой суммы равен J(x)

(8) – функциональное уравнение, можно доказать, что при условиях ограниченности (2), и полагая, что максимум в правой части (8) существует, это уравнение имеет единственное решение которое автоматически является оптимальным уравнением u(x), максимизирующее правую часть (8) — оптимальное и оно не зависит от t. Обычно решить уравнение (8) бывает непросто.

Пусть мы ищем решение задачи.

Найти

Max ^t(x_t, v_t)^1-(1)

x_t+1=a(1-v₁)x_t, t=0,1....

V_tÎ(0,1)

a>0, x₀>0, Î (0,1), Î (0,1)

a^1- <1

, уравнение (8) имеет вид

(ii)

Задача напоминает задачу, в которой целевая функция была пропорциональна . Предположим, что и в этой похожей задаче при некоторой постоянной k.

Или, сокращая на > 0:

(iii)

Положим .

Тогда

или

или , где

(IV)

Так как ’’()<0, и так как (0;1).

Таким образом, в предположении, что

найдено максимизирующее управление (iv).

При этом из (iii)следует, что

Так как , получаем

Или

Откуда

Тогда (iv):

В итоге получаем:

В этом примере, однако

И условия ограниченности не выполнены.

Поэтому следует слегка изменить задачу, положив

Тогда

В новой задаче целевая функция равна

Где , откуда 0< <1.

Легко видеть, что удовлетворяет уравнению Беллмана для новой задачи (с тем же оптимальным значением ).

Условие ограниченности выполнено, т.к.

Таким образом в (IV) оптимальное.

, соответствующее x_z удовлетворяет уравнению

x_t₊₁= a(1-u_t) x_t = a(1-u)x_u=ar x_t

При условии решением является x_t₌ x(ar )^t

Значение функции

И мы проверим, что значение целевой функции есть в такой в (V)

Важный вопрос, а существует ли искомые максимумы?

Если выполнены (2), ФУНКЦИИ f,g непрерывны и U компактна, то максимумы в (4) и(8) существует. Кроме этого, (8) имеет единственное решение, если использовать теорему о сжимающем отображении.

Принцип максимума

Мы рассматривали метод динамического программирования. Другой метод основан на принципе максимума. Этот метод удобен, когда есть ограничения на разовую пере6менную.

Рассмотрим задачу найти

, t=0,…,T-1 (1)

– задано, – свободно

Пусть U представляет собой интервал

Определим функцию Понтрягина (Hamiltonian)

(2)

– сопряжения (присоединения) функции