Сотсков А.И., Колесник Г.В. Оптимальное управление в примерах и задачах (2002) (1249284), страница 7
Текст из файла (страница 7)
За это времяx0система перейдет в новоесостояниеx*(t + dt) ≈ x*(t) + dx*(t),где, из (4.2),t0τTtРис. 4.142dx*(t) = f(t, x*(t), u*(t))dt.Изменение значения функционала (4.1) на отрезке [t, t + dt]. можетпроисходить только за счет интегральной его части и приближенносоставляетt + dt∫ F (t, x * (t ), u * (t ))dt≈ F(t, x*(t), u*(t))dt,tа оставшаяся часть, согласно принципу оптимальности Беллмана, будетравна J*(t + dt, x*(t + dt)).
Таким образом, получено следующее рекуррентное соотношение:J*(t, x*(t)) ≈ F(t, x*(t), u*(t))dt + J*( t + dt, x*(t + dt)).Теперь, пользуясьследующим образом:оптимальностьюu*(t), можем(4.4)переписать (4.4){F(t, x(t), u(t))dt + J*( t + dt, x(t + dt))}.J*(t, x(t)) ≈ umax( t )∈U(4.5)tДалее, в предположении дифференцируемости J*(t, x) по своимаргументам, переходя к пределу при dt → 0 и учитывая (4.2), получимследующее соотношение:–∂J * (t , x )∂J * (t , x )= max {F(t, x(t), u(t)) +f(t, x(t), u(t))}.u(t)∈Ut∂t∂x(4.6)Соотношение (4.6) представляет собой дифференциальное уравнение вчастных производных первого порядка для определения функции J*(t, x).Оно называется уравнением Беллмана в дифференциальной форме.Краевым условием для данного уравнения является оптимальное значениефункционала при t = t1, равное терминальному члену:J*(t1, x(t1)) = Ф0(t1, x(t1)).(4.7)Как правило, аналитическое решение уравнения (4.6) найти довольносложно или вовсе невозможно.
Поэтому прибегают к дискретизации задачи(4.1) – (4.3) с последующим ее численным решением. Дискретная задачаформулируется следующим образом:J(x(⋅), u(⋅)) =N −1∑ F (t , x , u )Δti =0iiii+ Ф0(xN) → max.xi+1 = f(xi, ui), x0 – задано.ui ∈ Ui,(4.8)(4.9)(4.10)43Отметим, что в дискретной задаче состояние системы будет описыватьсявектором x = (x0, x1,…, xN) ∈ RN+1, а управление – вектором u = (u0, u1,…, uN–1)∈ RN.Для (4.8) – (4.10) уравнение Беллмана будет иметь следующий вид:Ji*(xi) = max{F(ti, xi, ui)Δti + Ji+1*( f(xi, ui))},u ∈Ui(4.11)iс краевым условиемJN*(xN) = Ф0(xN).Решение задачи (4.11) при заданных краевых условиях производитсяпоследовательным решением уравнения (4.11) для шагов i = N–1, N–2, …, 0(обратный ход метода Беллмана). При этом на каждом шаге получаетсяоптимальное управление ui* как функция от текущего состояния системы xi.На втором этапе по полученным функциям ui*(xi) производится синтезоптимального управления для задачи с конкретным начальным условием x0.Таким образом, метод динамического программирования, в отличие отрассмотренных выше необходимых условий, дававших оптимальноеуправление как функцию времени u*(t) (программное управление), позволяетопределять оптимальное управление как функцию состояния системы u*(t, x)(синтезированное управление), что дает возможность отыскивать решениесразу для целого класса задач с различными начальными условиями.Далее будем считать, что в функционал задачи время не входит явно.Положим шаг Δti равным 1.
Введем понятие горизонта планирования какколичества шагов, оставшихся до завершения управления. ОбозначимVk(x) = JN -k*(x),т.е. максимальный выигрыш, который можно получить за k шагов, еслиначать из состояния x. В этом случае рекуррентное соотношение для Vk(x)принимает вид:Vk(x)= max{F(x, u) + Vk-1(f(x, u)),u∈U(4.12)с краевым условием: V0(x) = Ф0(x).Примеры441. З а д а ч а р а с п р е д е л е н и я р е с у р с а . Имеется некоторый ресурсв объеме а > 0, который необходимо распределить между N агентами, так,чтобы максимизировать их суммарную полезность, если функция полезностиi-го агентаFi(ui) = ln ui,где ui – объем ресурса, получаемый i-м агентом. (Считаем, что агенты как-топеренумерованы.)Р е ш е н и е . В формальной постановке задача имеет вид:NJ(u) =∑ ln ui =1N∑ui =1ii→ max;(4.13)≤ a; a > 0.Приведем ее к задаче оптимального управления. Для этого необходимовыделить переменную, являющуюся аналогом времени (номера шага) взадаче оптимального управления, горизонта планирования, а такжепараметры состояния и управления в каждый момент времени.Пусть номером шага в задаче является номер агента i, для которогопринимается решение о распределении ресурса.
Тогда величина ui будетявляться управлением на i-м шаге. Введем параметр состояния системы xi какобъем ресурса, имеющийся к i-му шагу (i = 1, N). Тогда, из условия задачиполучаемxi+1 = xi – ui;x1 = a.(4.14)Так как может быть распределено ресурса не более, чем имеется вналичии, то имеет место ограничение на управление0 ≤ ui ≤ xi.(4.15)Таким образом, (4.13) – (4.15) представляет собой задачу оптимальногоуправления в дискретном времени. Решим ее с использованием принципаБеллмана.
Обозначим через Vk(x) значение функции выигрыша, когдагоризонт планирования равен k, т.е. ресурс х распределяется между kагентами (не важно, что последними, так как все агенты имеют одинаковыефункции полезности).Рассмотрим последний шаг в нашей задаче, который имеет место послетого, как ресурс полностью распределен между всеми агентами.
Согласнокраевому условию функция Беллмана V0 на этом шаге равна45V0(x) = Ф0(x) ≡ 0.Рассмотрим теперь ситуацию, когда ресурс должен быть распределенодному агенту. В этом случае горизонт планирования k = 1 и рекуррентноесоотношение (4.12) принимает видV1(x) = max{ ln u + V0(x – u)} = max{ ln u } = ln x ,0 ≤ u≤ x0 ≤ u≤ xоткуда uN*( x) = x.Аналогично, при горизонте планирования k = 2 имеем:V2(x) = max{ ln u + V1(x – u)} = max{ ln u + ln(x – u)}.0 ≤ u≤ x0 ≤ u≤ xМаксимум выражения в фигурных скобках по u∈[0, x] достигается приxx, при этом V2(x) = 2 ln . Значит, оптимальное управление в этой22xситуации uN – 1*( x) = .2u*(x) =Покажем далее, что для горизонта k = 0,…, N оптимальное управление нашаге (N + 1 – k) и функция Беллмана горизонта k имеют вид:uN + 1 – k*( x) =x,kxkVk(x) = k ln .(4.16)Предположим, что это верно на некотором шаге (N + 1 – k). Определимоптимальное управление и функцию Беллмана горизонта k:Vk+1(x) = max { ln u + Vk(x – u)} = max { ln u + k ln0≤ u ≤ x0≤ u ≤ xx −u}.kОбозначимx −u.kУсловия первого порядка максимума функции А(uN – k) имеют вид:А(u) = ln u + k lnkdA 1= –= 0,du u x − uоткудаuN – k*( x) =x,k +1Vk+1(x) = (k +1) lnx.k +1Таким образом, определен общий вид оптимального управления дляпроизвольного шага в задаче.
Теперь проведем синтез оптимальногоуправления для задачи с N агентами и начальным объемом ресурса, равныма:u1*( x1) =x1a= ;NNx2 = x1 – u1* = a –aa( N − 1)=;NN46u2*( x2) =x2a= ;N −1 Nx3 = x2 – u2* =a( N − 1)aa( N − 2 )–=;NNN…uk*( xk) =xka= ;N +1 − kNxk+1 = xk – uk* =a( N + 1 − k )aa( N − k )–=;NNN…Таким образом, в данной задаче оптимальным является равномерноераспределение ресурса между агентами:a aau* = ( , , …,).N NN2. М о д е л ь Р а м с е я в д и с к р е т н о м в р е м е н и . Найтиоптимальное потребление ct, максимизирующее функцию полезности агентаза Т периодов времени с учетом дисконтирования:T −1∑ β U ( c ) → max ;t =0tt0 ≤ ct ≤ stst+1 = ρ(st – ct), s0 – задано,ρ > 1; 0 < β < 1.если U(ct) = ct1 – μ, 0 < μ < 1.Определить предельную оптимальную траекторию при T → ∞ (если онаесть).Р е ш е н и е .
Для данной задачи рекуррентное соотношение (4.12) приметвид:Vl(s) = max {c1 – μ + βVl – 1(ρ(s – c))}.0≤ c≤ sВычислим V1(s), V2(s), V3(s) и определим общий вид Vl(s):V0 = Ф0(sT) ≡ 0,1–μ1–μ1–μV1(s) = max{c+βV}=s, cT– 1(s) = s,0(ρ(s – c))} = max {c0 ≤ c≤ s0 ≤ c≤ sV2(s) = max{c1 – μ + βV1(ρ(s – c))} = max{c1 – μ + β(ρ(s – c)) 1 – μ}.0 ≤ c≤ s0 ≤ c≤ sОбозначим А2(с) = c1 – μ + β(ρ(s – c))максимум А2(с):1–μdA2= (1 – μ)с–μ – β(1 – μ)ρ1 – μ (s – c)1 – μ = 0dc, и определим с, доставляющее⇒ c* =s, где d = (βρ1 – μ)1/μ.1+ dТаким образом:V2(s) = (1 + d)μ s1 – μ, cT– 2(s) =s.1+ d47Далее,V3(s) = max {c1 – μ + βV2(ρ(s – c))} = max {c1 – μ + β(1 + d)μ(ρ(s – c)) 1 – μ}.0≤ c≤ s0≤ c≤ sОбозначим А3(с) = c1 – μ + β(1 + d)μ(ρ(s – c))имеет вид1–μ.
Условие максимума А3(с)dA3= (1 – μ)с–μ – (1 – μ)(1 + d)μ dμ (s – c)–μ = 0dc⇒c* =s.1+ d + d 2ТогдаV3(s) = (1 + d + d2)μ s1 – μ, cT– 3(s) =s.1+ d + d 2Проверим, что для произвольного шага n выполнено:nsVn(s) = s1 – μ ( ∑ d k )μ , cT– n(s) =n −1∑dk =0.(4.17)kk =0Допустим, что (4.17) выполнено для некоторого n. Определим вид Vn+1(s) иcT–n–1(s).nVn+1(s) = max{c1 – μ + βVn(ρ(s – c))} = max{c1 – μ + β(ρ(s – c))1 – μ ( ∑ d k )μ}.0 ≤ c≤ s0 ≤ c≤ sk =0Выписывая аналогично предыдущим рассуждениям условия экстремумапервого порядка для функции Аn+1(с), получимc* =sn∑d.kk =0Тогдаn +1Vn+1(s) = s1 – μ ( ∑ d k )μ , cT– n(s) =k =0sn∑d,kk =0что и требовалось доказать.Таким образом, оптимальное управление в данной задаче будет иметь видsct*(s) = T −t −1∑d.kk =0Тогда оптимальная траектория системы st* (объем сбережений приоптимальном потреблении) определяется рекуррентно из соотношенияT −t −2st+1* = ρ( st* – ct*( st*)) = ρ( st* –s *tT −t −1∑dk =0k∑dk∑dk) = ρd T k−=t 0−1st*, s0* = s0.k =048Определим теперь предельную оптимальную траекторию при T → ∞.Видно, что функция Vn(s) имеет конечный предел при n → ∞ только еслиd < 1:n1–μμV(s) = limV(dk ) =n(s) = lim s∑n→∞n→∞k =0s1− μ.(1 − d ) μПри этомc(s) = limcn*(s) = (1 – d)s.n→∞Управление c(s) по определению полагается решением задачи сбесконечным горизонтом планирования∞∑βt =0t 1− μtc→ 0max;≤c ≤ sttst+1 = ρ(st – ct), s0 – задано.При этом функция V(s) является решением операторного уравненияБеллмана для данной задачиV = BV,где оператор В определен на классе W непрерывных, вогнутых, монотонныхфункций Ф: R1 → R1, таких, что Ф(0) = 0 и действует по формулеBФ(s) = max{c1 – μ + βФ(ρ(s – c))}.0 ≤ c≤ sДействительно, проверим, чтоs1− μ( ρ ( s − c ))1− μ1–μmaxV(s) == 0≤c≤ s {c+β}.(1 − d ) μ(1 − d ) μИз условий максимума функции в фигурных скобках получаем:c–μ – βρ 1 – μ−μ( s − c)−μ–μμ ( s − c)=c–d=0(1 − d ) μ(1 − d ) μ⇒c* = s(1 – d) = c(s).Но тогдаBV(s) = s1– μ(1 – d)1– μμ 1– μ 1– μ+d sd1s1− μ=.(1 − d ) μ(1 − d ) μТаким образом, решение задачи с бесконечным горизонтом планированияc(s) = (1 – d)s.Оно не зависит от момента времени t, а определяется только текущимсостоянием системы s.
Такое решение называется стационарным. Дляопределения соответствующей ему траектории st найдем переходноеотображение Y(⋅):st+1 = Y(st) = ρ(st – c(st)) = ρ(st – st(1 – d)) = ρdst =(ρβ)1/μ st.49Решением этого уравнения является функцияst = s0 α t,где α = (ρβ)1/μ.Видно, что в зависимости от величины коэффициента α траектория st,соответствующая стационарному потреблению, может возрастать, убыватьили оставаться постоянной с течением времени.3.
Определить решение уравнения Беллмана для задачи с линейнойполезностью:∞∑βt =0tct → max ;0≤ct ≤ x txt+1 = f(xt – ct), x0 – задано,0 < β < 1.если f(⋅)∈W такова, что limf'(z) = ρ, где ρβ < 1 (т.е. f(⋅) ограничена сверхуz →∞линейной функцией b + ρz, см. рис. 4.2).При этом решение понимается как предел решений для конечныхгоризонтов.Р е ш е н и е .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
