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

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

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

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

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

, (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+1, …) – последовательность управлений, гдеu_s+kϵU, k = 0, 1, …;x_t+1 = 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+1 = 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)

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