Сотсков А.И., Колесник Г.В. Оптимальное управление в примерах и задачах (2002) (1249284), страница 8
Текст из файла (страница 8)
Для конечных горизонтов имеем рекуррентное соотношениеVk(x) = max{c + βVk – 1(f(x – c))}.0 ≤ c≤ xОбозначим z = x – c. ТогдаVk(x) = max{x – z + βVk – 1(f(z))} = x + max{ – z + βVk – 1(f(z))}.0≤ z ≤ x0≤ z ≤ x1. Покажем, что ∀k = 1, 2, … Vk(x) ≤ x + K для некоторой константы K > 0:V0 = Ф0(xT) ≡ 0,V1(x) = x + max{ – z + βV0(f(z))} = x + max{– z } = x,0 ≤ c≤ s0≤ z ≤ xV2(x) = x + max{ – z + βV1(f(z))} = x + max{ – z + βf(z)} ≤0≤ z ≤ x0≤ z ≤ x≤ x + βb + max{ – z(1 – ρβ)} = x + βb.0≤ z ≤ xРассуждая по индукции, получаем:Vk(x) = x + max{ – z + βVk – 1(f(z))} ≤0≤ z ≤ x≤ x + b(β + β2 + … + βk – 1} ≤ x +βb,1− β∀ k ≥ 2.Так как ∀ x ≥ 0 последовательность Vk(x) – не убывает при k → ∞ и, крометого ограничена, то существует конечный пределV(x) = klimVk(x) ≤ x + K .→∞50Из непрерывности оператора Беллмана В для данной задачи в классефункций W имеемBФ(x) = x + max{ – z + βФ(f(z))}0≤ z ≤ xследует, что BV = V.2.
Обозначим А(z) = – z + βV(f(z)). Покажем, что функция А(z) достигаетмаксимума на множестве {z ≥ 0}. Из свойств V(⋅) получаем:А(0) = 0,A(z) = – z + βV(f(z)) ≤ – z + β(f(z) + K) ≤ – z + β(b + ρz + K) =β(b + K) – z(1 – ρβ),которая убывает при z → ∞.Тогда в силу вогнутости А(⋅), она имеет вид, изображенный на рис. 4.3.3. Исходя из вида функции A(z), можно заключить, чтопри x ≥ z *, т.к.
z ( x ) = z *⎧x + a,V(x) = ⎨,⎩ βV ( f ( x )), при x < z * т.к. z ( x ) = x(4.18)A(z).где z(x) = arg max0≤ z ≤ xВ частности, при x < z* V(x) = βV(f(x)) < V(f(x)), откуда, в силумонотонности функции V(⋅) следует, чтоfx < f(x). Но тогда по непрерывностиb + ρzимеем такжеz* ≤ f(z*) (рис. 4.4).f(z)4. Найдем величины а и z*.В силу монотонности f(⋅) при z ≥ z*выполнено f(z) ≥ f(z*) ≥ z*. Тогда в силупункта 3 получаем:0zа = max{ – z + βV(f(z))} =z ≥0Рис.
4.2= max{ – z + β(f(z) + а)}.z ≥z *Видно, что выражение в скобкахсовпадает с А(z) при z ≥ z*. Эта функциявогнута и достигает максимума на{z ≥ 0} в точке z*. Предположим также,что А(z) дифференцируема в точке z*(что предполагает дифференцируемостьA(z)a0z*zРис. 4.351Vf(z)V(x)f(z*)z*axxz*xzz*Рис. 4.4функций V(⋅) и f(⋅)).
Тогда точка максимума может быть найдена из условияэкстремума первого порядка A'(z*) = 0, откуда получаемf'(z*) =1β, а = max { – z + β(f(z) + а)} =max{−z + βf ( z )}z ≥0z ≥01− β.5. Построим функцию V(⋅) для x < z*.а). Рассмотрим отрезок Δ1 = [x1, z*], где x1 < z* и f(x1) = z*. Тогда ∀ x∈Δ1f(x) ≥ z*, поэтому в силу (4.18)V(x) = βV(f(x)) = β(f(x) + a).б). Рассмотрим отрезок Δ2 = [x2, x1], где x2 < x1 и f(x2) = x1.
∀ x∈Δ2 f(x) ∈ Δ1,тогда в силу (4.18) и предыдущего пунктаV(x) = βV(f(x)) = β 2 (f(f(x)) + a).Продолжая эти рассуждения далее, на отрезке Δn = [xn, xn–1], где xn < xn–1 иf(xn) = xn–1. имеем:V(x) = β n (f(…f (f(x))…) + a).n разНа стыках функция устанавливается, исходя из непрерывности. Например,в точке z* выполнены условия:V(z* +) = z* + a = z* +βf ( z*) − z *βf ( z*) − z *= β( f(z*) +) = V(z* –).1− β1− βТаким образом, решение уравнения Беллмана V(x) полностью восстановленодля x ≥ 0.52…0x0Δkx1…xk–1 z*xk–2Δk–1Δ2x0~x=xkx= xk+1Δ1Рис.
4.5.6. Определим переходное отображение Y(x) = f(z(x)) (где z(x) = arg max A(z),0≤ z≤ xсм. п. 3).При x ≥ z* z(x) = z*, откуда Y(x) = f(z*) = ~x . При x < z* z(x) = x, тогдаY(x) = f(x) > x. Процесс изменения фазовой координаты x при такомпереходном отображении для некоторого начального условия x0 показан нарис. 4.5.В заключение рассмотрим задачу, в которой время (номер шага) явновходит как аргумент функции полезности, стоящей под знаком суммы(дисконтирующий множитель не считается за такой случай).При этом результат оптимизации существенно зависит от упорядоченияшагов, поэтому понятие горизонта планирования использовать нельзя.Следовательно, рекуррентное соотношение Беллмана в данной задаче будетзаписываться в общем виде (4.11).4.
З а д а ч аор а н ц е . Имеется контейнер емкостью V игрузоподъемностью M и N типов изделий, для каждого из которых известныстоимость ci, вес mi и объем vi. Требуется разместить в контейнере наборизделий максимальной суммарной стоимости.Р е ш е н и е . Обозначим через xi – количество предметов i-го типа,размещенных в контейнере. Тогда задача будет иметь вид:NL(x) = ∑ ci x i → max,i =1N∑m xi =1ii≤ M,N∑v xi =1ii≤ V,xi ∈ N, i = 1,…, N.Сведем ее к дискретной задаче оптимального управления. Пусть "шагом"операции является номер класса изделий, которые складываются в53контейнер. Определим две переменных состояния: μi – оставшаясягрузоподъемность после распределения изделий i-го класса и γi – свободныйобъем после распределения изделий i-го класса.
Тогда с каждым шагомсостояние системы будет изменяться по следующему закону:μi+1 = μi – mi+1 xi+1, μ0 = M,γi+1 = γi – vi+1 xi+1, γ0 = V.Очевидно, управлением в данной задаче является количество изделий xi,помещаемых в ранец на каждом шаге. Функция Беллмана Jl(μ, γ) в даннойзадаче будет представлять собой максимальную стоимость набора,состоящего из изделий классов i ≥ l, помещенных в контейнер:Jl(μ, γ) = max{cl xl + Jl+1(μ – ml xl, γ – vl xl)},xlml xl ≤ μ,vl xl ≤ γ.Так как управление xl является дискретным, то функцию Беллмана удобнопредставлять в табличном виде, с дискретизацией, соответствующейминимальным изменениям объема и грузоподъемности контейнера припомещении в него изделий.В качестве примера рассмотрим случай M = 7, V = 7, N = 3, со следующимипараметрами изделий:Класс, i123Стоимость, ci451Масса, mi321Объем, vi133В этом случае исходная задача целочисленного программирования запишетсякакL(x) = 4x1 + 5x2 + x3 → max,3x1 + 2x2 + x3 ≤ 7,x1 + 3x2 + 3x3 ≤ 7,xi ∈ N, i = 1,…, N.Множество допустимых состояний системы на каждом шаге представляетсобой пары (μ, γ), где μ, γ ∈ {0, 1, …, 7}.Функция Беллмана для шага 3 имеет вид:J3(μ, γ) = max{ x3},x3x3 ≤ μ,3 x 3 ≤ γ,x3 ∈ N.Ее значения для допустимых состояний приведены в таблице.54μ\γ01234567000000000100000000200000000301111111401111111501111111602222222702222222На шаге 2 функция Беллмана имеет вид:J2(μ, γ) = max{5 x2 + J3(μ – 2 x2, γ – 3 x2)},x22x2 ≤ μ,x2 ∈ N.3 x2 ≤ γ,Таблица значений J2(μ, γ) строится с использованием уже полученнойтаблицы для J3(μ, γ):μ\γ0123456700000000010000000020000000030155555540155555550155555560256101010107025610101010На шаге 1 функция Беллмана имеет вид:J1(μ, γ) = max{4 x1 + J2(μ – 3 x1, γ – x1)},x13x1 ≤ μ,x 1 ≤ γ,x1 ∈ N.Таблица значений J1(μ, γ) выглядит следующим образом:μ\γ0123456700000000010004444420004448830155558840155599950155599960256101010107025610101014Максимальная стоимость набора изделий соответствует значению J1(7, 7), асам набор – оптимальным значениям компонент управления (x1, x2, x3), накоторых достигаются значения функций J1, J2 и J3: x1 = 1, x2 = 2, x3 = 0.55Упражнения1.
Дана модель Рамсея в дискретном времени с конечным горизонтом:T −1∑βtln ct → max ;0≤ ct ≤ stt =0st+1 = ρ(st – ct), s0 – задано,ρ > 1; 0 < β < 1.а). Выписать для данной модели рекуррентное соотношение Беллмана, найтиобщий вид функций выигрыша Vk(s), k = 1, 2,…, и оптимальных стратегийпотребления ck(s).б). Определить решение уравнения Беллмана V(s) для этой задачи путемпредельного перехода при T → ∞ (если она есть). Показать, что стационарнаястратегия потребления не зависит от ρ, а оптимальная стационарная фазоваятраектория имеет вид геометрической прогрессии. Найти неподвижнуюточку стационарного переходного отображения Y(⋅) как функцию параметровβ и ρ.2.
В задаче:n −1n −1,∑ β i cip → maxc ≥0i =0∑ci =0ii≤ s, p > 1, β > 0,получить рекуррентное соотношение Беллмана для функций Vn. Исходя изнего получить рекуррентное соотношение для постоянных коэффициентов ввыражении для Vn. Описать характер оптимальной стратегии потребления ci взависимости от параметра β.Получить выражение для Vn непосредственно.3. Рассматривается задача:∞∑ β U ( c ) → max ;t =0tt0 ≤ ct ≤ x txt+1 = f(xt – ct), x0 – задано,где U(c) ≤ a + δ c ∀ c ≥ 0, и f(z) ≤ b +ρz ∀ z ≥ 0,a, δ, β, b, ρ, – положительные параметры, β < 1, ρβ < 1, функции f, U ∈ W.Доказать, что существует решение уравнения Беллмана V(⋅) для этой задачи иимеет место неравенство:V(x) ≤ δ x + K, K = const.Определить значение K.564.
В задаче 3 положить:c=0⎧0,U(c) = ⎨.⎩a + δc, c > 0Построить функцию Беллмана V(⋅).5. Дана скалярная динамическая системаx& = ax + bu,t ≥ 0,с критерием качества∞22J(u) = ∫ αx + βu dt → inf,0где a, b ≠ 0, α > 0, β > 0 – заданные постоянные. Показать, что оптимальноеуправление u* имеет вид1bu * = – (a +a 2 + b 2αβ −1 )x,а функция Беллмана V(t, x) – видV(t, x) = x2β b– 2 (a +a 2 + b 2αβ −1 ).6. Найти функцию Беллмана V(⋅) и оптимальное управление длядинамической системыx& = u,0 ≤ t ≤ 1,x(1) → min;| u | ≤ 1.7.
Найти оптимальное решение задачи о ранце при M = 8, V = 6, N = 3:Класс, i123Стоимость, ci321Масса, mi321Объем, vi21357Литература1. Андреева Е.А., Бенке Х. Оптимизация управляемых систем. Тверь, Изд.ТГУ, 1996.2. Афанасьев В.Н., Колмановский В.Б., Носов В.Р. Математическая теорияконструирования систем управления. М.: "Высшая школа", 1998.3. Беленький В.З. Оптимальное управление: принцип максимума идинамическое программирование.
М.: РЭШ, 2001.4. Брайсон А., Хо Ю-Ши Прикладная теория оптимального управления. М.:Мир, 1972.5. Бурштейн И.М. Динамическое программирование в планировании. М.:Экономика, 1968.6. Катулев А.Н., Северцев Н.А. Исследование операций: принципыпринятия решений и обеспечение безопасности. М.: Физматлит, 2000.7. Цлаф Л.Я. Вариационное исчисление и интегральные уравнения.
М.:Наука, 1966.58.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
