Лекции по ОУ (1050564), страница 13
Текст из файла (страница 13)
Если удается решить задачу Коши –Беллмана, то оптимальное значение критерия качества исходной задачи можнополучить как частное значение функции Беллмана при τ = t 0 , y = x0 . При этомфункция, на которой достигается минимум в (4.2.9), даст нам оптимальноеуправление [3].4.3.
Схема Беллмана для дискретных задачПусть задана дискретная системаx(t + 1) = f ( x(t ), u (t ), t ), t = 0, K, T − 1,(4.3.1)где T – фиксированный момент времени, ∀ t x(t ) ∈ E n , u (t ) ∈ E m , f – заданнаявектор-функция, и пусть задано начальное условие:73x(0) = x0 .(4.3.2)Дискретное управление будем считать допустимым, если выполнено условиеu (t ) ∈U , t = 0, K, T − 1,(4.3.3)где U – заданное множество в пространстве E m .
Обозначим множество допустимых управлений через D 0 и рассмотрим задачу оптимального управления,которая состоит в нахождении допустимого управления и соответствующейтраектории, удовлетворяющей (4.3.1), (4.3.2), при которых достигает минимумакритерий качества:J ( x, u ) =T −1∑ F (x(t ), u(t ), t ) + Φ(x(T )).(4.3.4)t =0Зафиксируем произвольный момент времени 0 < τ ≤ T − 1 и рассмотримвспомогательную задачу, в которой за начальный момент времени взято τ , а заначальное состояние системы – произвольный вектор x ∈ E n . Таким образом,рассмотрим задачу:x(t + 1) = f ( x(t ), u (t ), t ), t = τ, τ + 1, K, T − 1 ,x(τ) = x ,u (t ) ∈ U , t = τ, τ + 1, K, T − 1,τJ ( x, u ) =(4.3.5)(4.3.6)(4.3.7)T −1∑ F (x(t ), u(t ), t ) + Φ(x(T ) ) → min .(4.3.8)t =τВ данной задаче допустимые управления – это последовательностиu = {u (τ), u (τ + 1), K, u (T − 1)}, для которых выполняется условие (4.3.7).
Обозначим множество таких допустимых управлений через D τ .Определение 4.3.1. Функцияψ ( x, τ) = minτ J τ ( x, u )u∈ Dназывается функцией Беллмана задачи (4.3.1) – (4.3.4).Очевидно, исходная задача – это частный случай вспомогательной, т.е.можно положить:min J ( x, u ) = ψ ( x0 , 0) .u∈ D 0Можно показать, что уравнение Беллмана представляет собой рекуррентные соотношения:ψ( x, τ) = min[F ( x, v, τ) + ψ( f ( x, v, τ), τ + 1)], τ = 0,1K, T − 1 ,V ∈U(4.3.9)причем функция Беллмана удовлетворяет краевому условиюψ (x, T ) = Φ ( x) .74(4.3.10)Соотношения (4.3.9), (4.3.10) определяют задачу Коши – Беллмана дляслучая дискретных систем.Из задачи Коши – Беллмана можно последовательно определить функцииψ ( x, τ) . А именно ψ ( x, T ) = Φ( x) – известна. Для ψ ( x, T − 1) имеем из (4.3.9)ψ ( x, T − 1) = min[F ( x, v, T − 1) + ψ( f ( x, v, T − 1), T )] =v∈U= min[F ( x, v, T − 1) + Φ( f ( x, v, T − 1) )].(4.3.11)v∈UИспользуя ψ ( x, T − 1) , найдем ψ ( x, T − 2) и т.
д. При этом каждый раз нужно решать задачу минимизации функции m переменных v1 , K, vm на множествеU . Это конечномерная задача, для решения которой существуют разработанные методы. Предположим, найдены те векторы v ∈U , на которых достигаетсяминимум в (4.3.9). Очевидно, они зависят от x, τ , и пусть это будут векторыv( x, T − 1), v( x, T − 2),K, v( x, 0) .Далее решение задачи находится следующим образом. Положим:uˆ (0) = v( x0 , 0), xˆ (1) = f ( x0 , uˆ (0),0 ), uˆ (1) = v( xˆ (1),1),xˆ (2) = f ( xˆ (1), uˆ (1),1), K, uˆ (T − 1) = v( xˆ (T − 1),T − 1) ,xˆ (T ) = f ( xˆ (T − 1), uˆ (T − 1),T − 1) .Построенная последовательность uˆ = {uˆ (0), uˆ (1),K, uˆ (T − 1)} будет оптимальным управлением, а последовательность xˆ = {xˆ (0), xˆ (1),K, xˆ (T )} – оптимальной траекторией.
Доказательство этого утверждения содержится в [3].4.4. Примеры решения задач с помощью метода БеллманаПример 1. Одномерная задача без ограничений. Применим метод Беллмана к следующей задаче оптимального управления:dx= u (t ) ,dtt ∈ [0, T ] ,x(0) = x0 ,T∫J ( x, u ) = u 2 (t ) dt + px 2 (T ) → min ,0где x(t ) ∈ E 1 , u (t ) – кусочно-непрерывная скалярная функция, x0 , p, T – заданные числа, причем p ≥ 0 .75Пусть ψ( y, τ) – функция Беллмана рассматриваемой задачи. Запишем задачу Коши – Беллмана:⎧ ∂ψ( y, τ)⎫∂ψ( y, τ)min ⎨u++ u2 ⎬ = 0,u∂τ⎩ ∂y⎭ψ( y, T ) = py 2 .ОбозначимR ( y , u , τ) =∂ψ( y, τ)∂ψ( y, τ)+ u2 .u+∂τ∂yПри фиксированных y, τ имеем функцию скалярной переменной u .
Таккак на управление нет ограничений, то для того, чтобы найти точку, при которой R( y, u , τ) достигает минимума, нужно приравнять к нулю производную∂R( y, u , τ), т.е. будем иметь∂u∂ψ( y , τ)+ 2u = 0 ,∂yоткуда1 ∂ψ( y, τ).(4.4.1)u=−2 ∂yЭто действительно точка минимума, так как∂ 2 R ( y, u , τ)= 2 > 0.∂u 2Подсчитаем минимум функции R( y, u , τ) :221 ⎛ ∂ψ( y, τ) ⎞∂ψ( y, τ) 1 ⎛ ∂ψ( y, τ) ⎞⎟⎟ +⎟ =min R( y, u , τ) = − ⎜⎜+ ⎜⎜u2 ⎝ ∂y ⎠4 ⎝ ∂y ⎟⎠∂τ21 ⎛ ∂ψ( y, τ) ⎞∂ψ( y, τ)⎟⎟ += − ⎜⎜.4 ⎝ ∂y ⎠∂τДля определения функции Беллмана ψ (ζ, τ) получили задачу:21 ⎛ ∂ψ( y, τ) ⎞∂ψ( y, τ)⎟⎟ +− ⎜⎜= 0,4 ⎝ ∂y ⎠∂τψ( y, T ) = py 2 .76(4.4.2)(4.4.3)Будем искать ψ( y, τ) в виде многочлена относительно переменной y , т.е.пустьψ( y, τ) = ϕ 0 ( τ) + ϕ1 ( τ) y + ϕ 2 ( τ) y 2 ,(4.4.4)где ϕ 0 , ϕ1 , ϕ 2 – неизвестные функции, подлежащие определению. После подстановки этой функции в (4.4.2), (4.4.3) получим равенства многочленов:−1(ϕ1 ( τ) + 2ϕ 2 ( τ) y )2 + dϕ0 + dϕ1 y + dϕ 2 y 2 = 0 ,4dτdτdτϕ0 (T ) + ϕ1 (T ) y + ϕ 2 (T ) y 2 = py 2 .Приравнивая коэффициенты при одинаковых степенях y , придем к системетрех дифференциальных уравнений с начальными условиями:dϕ 2− ϕ 22 ( τ) = 0 ,dτdϕ1− ϕ1 (τ)ϕ 2 ( τ) = 0 ,dτdϕ 0 1 2− ϕ1 (τ) = 0 ,dτ 4ϕ 2 (T ) = p ,ϕ1 (T ) = 0 ,ϕ 0 (T ) = 0 .Проинтегрируем первое уравнение.
Имеемdϕ 2= ϕ 22 (τ) ,dτилиd ϕ2ϕ 22= dτ, −1= τ+C.ϕ2Произвольную постоянную C можно найти из условия (4.4.7):ϕ 2 (T ) = −откудаC=−1= p,T +C1 + Tp.pСледовательно,ϕ 2 (τ) = −1pp.=−=τ+Cp (τ − T ) − 1 p (T − τ) + 177(4.4.5)(4.4.6)(4.4.7)(4.4.8)(4.4.9)(4.4.10)Для определения функции ϕ1 (τ) имеем задачу Коши (4.4.6), (4.4.9). Этооднородное дифференциальное уравнение с нулевым начальным условием, поэтому ϕ1 (τ) ≡ 0 . Аналогично из (4.4.7), (4.4.10) ϕ 0 (τ) ≡ 0 .
Подставив найденныефункции ϕ 0 , ϕ1 , ϕ 2 в равенство (4.4.4), получим функцию Беллмана рассматриваемой задачи:py 2.ψ( y , τ ) =p (T − τ) + 1При y = x0 эта формула даст минимальное значение критерия качества. Используя (4.4.1) найдем оптимальное управление:uˆ ( τ) = −px01 ∂ψ( x0 , τ).=−p (T − τ) + 12∂yПример 2. Задача для системы, линейной по состоянию. Рассмотрим задачу оптимального управления для системы двух дифференциальных уравнений с закрепленным левым концом без ограничений:dx1= x1 (t ) u (t ) + x2 (t ) ,dtdx2= u 2 (t ) , t ∈ [0; T ],dtx1 (0) = x01 ,x2 (0) = x02 ,TJ ( x, u ) = G ( x(t ), t ) dt → min .∫0Здесь x(t ) = ( x1 (t ), x2 (t ) ) – вектор состояния, u (t ) – скалярное управление, G ( x, t ) – заданная функция.
Следуя обозначениям п. 4.2, имеемT⎡ x1 (t ) u (t ) + x 2 (t )⎤f ( x(t ), u (t ), t ) = ⎢ 2⎥,ut()⎦⎣F ( x(t ), u (t ), t ) = G ( x(t ), t ), Φ ( x) = 0 .Запишем уравнение Беллмана (4.2.9):⎡ ∂ψ( x, t )⎤∂ψ( x, t ) 2 ∂ψ ( x, t )u ++ G ( x, t ) ⎥ = 0 .min ⎢( x1u + x2 ) +u∂x2∂t⎣ ∂x1⎦Обозначим78j ( x, u , t ) =∂ψ( x, t ) 2 ∂ψ( x, t )∂ψ( x, t )( x1u + x2 ) +u ++ G ( x, t ) .∂x1∂x2∂t(4.4.11)Чтобы найти минимум функции j ( x, u , t ) по переменной u , подсчитаем еечастную производную и приравняем ее к нулю.
Получим:∂ψ ( x, t )∂j ( x, u, t ) ∂ψ ( x, t )=x1 + 2u = 0.∂u∂x1∂x2Отсюда найдем−11 ∂ψ( x, t ) ⎛ ∂ψ( x, t ) ⎞⎟⎟ .uˆ ( x, t ) = −x1 ⎜⎜x∂2 ∂x1⎝⎠2(4.4.12)∂ 2 j ( x, u , t )∂ψ ( x, t )=2> 0 , функция j ( x, u , t ) будет иметь ми∂x 2∂u 2нимум при u = uˆ ( x, t ) . Подставляя û в (4.4.11), найдем минимальное значениеj ( x, u , t ) :При условии, что∂ψ ( x, t ) ⎡ 1 ∂ψ ( x, t ) 2 ⎛ ∂ψ( x, t ) ⎞⎟⎢−x1 ⎜⎜min j ( x, u, t ) =u∂x1 ⎢ 2 ∂x1∂x 2 ⎟⎠⎝⎣2∂ψ ( x, t ) 1 ⎛ ∂ψ ( x, t ) ⎞ 2 ⎛ ∂ψ ( x, t ) ⎞⎜⎟ x1 ⎜⎜⎟⎟+∂x2 4 ⎜⎝ ∂x1 ⎟⎠∂x⎝⎠2−2+−1⎤+ x2 ⎥ +⎥⎦∂ψ ( x, t )+ G ( x, t ) .∂tТаким образом, уравнение Беллмана в рассматриваемом примере приметвид∂ψ( x, t )1 ⎛ ∂ψ( x, t ) ⎞⎟x 2 − ⎜⎜∂x14 ⎝ ∂x1 ⎟⎠2−1⎛ ∂ψ( x, t ) ⎞ 2 ∂ψ ( x, t )⎜⎜⎟⎟ x1 ++ G ( x, t ) = 0 .∂∂xt⎝⎠2Вместе с краевым условием ψ ( x, T ) = 0 это уравнение составит задачу Коши –Беллмана.
Если найдем решение этой задачи, то формула (4.4.12) приx = ( x01 , x02 ) даст нам оптимальное управление.Пример 3. Задача распределения капитальных вложений между предприятиями. Эта задача рассматривалась в п. 2.4. Ее математическая постановка определяется формулами (2.4.20) – (2.4.24). Преобразуем задачу следующим образом. Вместо функционала (2.4.24) будем рассматривать функционал с терминальным членом:J * ( x, u ) =T −1∑f0(u (t ), t ) + M [x(T ) − A]2 ,t =∂79где M > 0 – произвольно большое число. Очевидно, минимум J * будет достигаться тогда, когда терминальный член равен нулю, т.е. когда x(T ) = A . Поэтому ограничение на правом конце можно не рассматривать. Таким образом, будем решать следующую задачу:x(t + 1) = x(t ) + u (t ), t = 0,KT − 1 ,x ( 0) = 0 ,u (t ) ≥ 0, t = 0,KT − 1 ,J ( x, u ) =T −1∑ f (u(t ), t ) + M [x(T ) − A]20→ min .t =0Запишем уравнение Беллмана:ψ ( x, t ) = min[ f 0 (V , t ) + ψ( x + V , t + 1)], t = 0,K, T − 1 ,V ≥0ψ ( x, t ) = M ( x − A) 2 .Проведем вычисления для случая T = 3, A = 10 , и пусть⎧0.4V 2 − 16V , t = 0,⎪⎪f 0 (V , t ) = ⎨0.6V 2 − 18V , t = 1,⎪2⎪⎩0.7V − 25V , t = 2.Шаг 1.
Для t = 2 имеем[]ψ( x, 2) = min 0.7V 2 − 25V + M ( x + V − 10) 2 .V ≥0Так как M > 0 – произвольное сколько угодно большое число, то минимум квадратной скобки будет достигаться, когда множитель при M обратится вноль. Следовательно, для оптимального значения Vˆ на этом шаге будем иметьVˆ ( x, 2) = 10 − x .(4.4.13)При этомψ ( x, 2) = 0.7(10 − x) 2 − 25(10 − x) = 0.7 x 2 + 11x − 180 .Шаг 2. Для t = 1 имеем[]ψ ( x,1) = min 0.6V 2 − 18V + 0.7( x + V ) 2 + 11( x + V ) − 180 =V ≥0[]= min 1.3V 2 − 7V + 1.4 xV + 0.7 x 2 + 11x − 180 .V ≥080При каждом значении переменной x функция в квадратных скобках определяетпараболу, обращенную ветвями вверх. Абсцисса вершины параболы определяется формулой7 − 1.4 xV == 2.69 − 0.539 x .2.6Для оптимального значения Vˆ будем иметь с учетом округления:⎧2.69 − 0.539 x, если x ≤ 5,Vˆ ( x,1) = ⎨если x ≥ 5.⎩0,(4.4.14)Подсчитаем функцию Беллмана:⎧⎪0.324 x 2 + 14.66 x − 189.4, если x ≤ 5,ψ ( x,1) = ⎨⎪⎩0.7 x 2 + 11x − 180,если x ≥ 5.Шаг 3.
Для t = 0 имеем⎧⎪0.4V 2 − 16V + 0.324( x + V ) 2 + 14.66( x + V ) − 189.4, если x + V ≤ 5,ψ ( x, 0) = min ⎨V ≥0 ⎪0.4V 2 − 16V + 0.7( x + V ) 2 + 11( x + V ) − 180,если x + V ≥ 5,⎩или⎧⎪0.724V 2 − 1.34V + 0.648 xV + K, если V ≤ 5 − x,ψ ( x, 0) = min ⎨V ≥ 0 ⎪1,1V 2 − 5V + 1.4 xV + K,если V ≥ 5 − x,⎩(4.4.15)где многоточие относится ко всем оставшимся слагаемым, не зависящим от V .В обоих случаях мы имеем параболы, обращенные ветвями вверх. Абсциссавершины 1-й параболы определяется формулойV =1.34 − 0.648 x= 0.925 − 0.44 x .2 × 0.724Отсюда для оптимального значения Vˆ будем иметь⎧0.925 − 0.44 x, если x ≤ 2.06,Vˆ ( x, 0) = ⎨если x ≥ 2.06.⎩0,Для 2-й параболы из (4.4.15) абсцисса вершины – этоV =5 − 1.4 x= 2.27 − 0.636 x .2 × 1.1В этом случае оптимальным значением будет81(4.4.16)⎧5 − x, если x ≤ 5,Vˆ ( x, 0) = ⎨если x ≥ 5.⎩0,Таким образом, в данном примере задача Коши – Беллмана имеет два решения.Выпишем два варианта распределения капитальных вложений (дляx(0) = 0 ):1) согласно формулам (4.4.13), (4.4.14), (4.4.16):uˆ (0) = Vˆ ( x, 0)x =0= 0.925 ,xˆ (1) = x(0) + uˆ (0) = 0 + 0.925 = 0.925 ,uˆ (1) = V ( x,1) x =0.925 = 2.69 − 0.539 × 0.925 = 2.19 ,xˆ (2) = xˆ (1) + uˆ (1) = 0.925 + 2.19 = 3.115 ,uˆ (2) = Vˆ ( x, 2)x =3.115= 10 − 3.115 = 6.885;2) согласно формулам (4.4.13), (4.4.14), (4.4.17):uˆ (0) = V ( x, 0) x =0 = 5 ,xˆ (1) = xˆ (0) + Vˆ (0) = 0 + 5 = 5 ,- uˆ (1) = Vˆ ( x,1)x =5= 0,xˆ (2) = xˆ (1) + Vˆ (1) = 5 + 0 = 5 ,uˆ (2) = uˆ ( x, 2 ) = 10 − 5 = 5 .Из этих двух вариантов нужно выбрать тот, при котором критерий качества принимает меньшее значение.825.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
