Деменков Н.П. Вычислительные аспекты решения задач оптимального управления (2007) (1253737), страница 13
Текст из файла (страница 13)
Пусть мы подошли к нему с некоторым запасом средств S. Обозначим Jk–1(S) условный оптимальный выигрыш на двух последних шагах (k – 1)-ми k-м, который уже оптимизирован.Если мы выделим на (k – 1)-м шаге (k – 1)-му предприятиюсредства Х, то на последний шаг останется (S – X) средств. Нашвыигрыш на двух последних шагах будет равен сумме Lk–1(X) ++ Jk(S – X), и нужно найти такое значение Х, при котором этот выигрыш максимален:Jk–1(S) = max {Lk–1(X) + Jk(S – X)},x≤ s(3.13)где max означает, что берется максимальное значение по всем X,x≤ sкакие только возможны (вложить больше, чем S, мы не можем), отвыражения, стоящего в фигурных скобках. Этот максимум и естьусловный оптимальный выигрыш за два последних шага, а то значение X, при котором этот максимум достигается, является условным оптимальным управлением на (k – 1)-м шаге.Далее оптимизируем (k–2)-й, (k–3)-й и так далее шаги.В общем для любого i-го шага будем находить условный оптимальный выигрыш за все шаги, начиная с этого шага и до концарасчета, по формулеJi(S) = max {Li(X) + Ji+1(S–X)}x≤ s90(3.14)и соответствующее ему условное оптимальное управление Xi(S) –то значение X, при котором этот максимум достигается.Продолжая таким образом, дойдем, наконец, до первого предприятия П1.
Здесь нам не нужно будет варьировать значение Si.Мы точно знаем, что запас средств перед первым шагом равен Р:J* = J1(Р) = max {L1(X) + L2(Р – X)}x≤ P(3.15)Итак, максимальный выигрыш (доход) от всех предприятийнайден. То значение X, при котором достигается максимум (3.15),и есть оптимальное управление X1* на 1-м шаге.После того, как мы вложим найденные средства в первое предприятие, у нас их останется Р – X1*.Для полученного значения S выделяем второму предприятиюоптимальное количество средств: X 2∗ = X2(Р – X1*), и так далее доконца вычислений.Решим численный пример для Р = 10 (условных единиц) и k = 5.Будем считать, что вкладываются только целые количествасредств.
Функции дохода заданы в табл. 3.5.Таблица 3.5xL1(x)L2(x)L3(x)L4(x)L5(x)123456780,51,01,42,02,52,83,03,00,10,51,21,82,52,93,53,50,61,11,21,41,61,71,81,80,30,61,31,41,51,51,51,51,01,21,31,31,31,31,31,3В каждом столбце табл. 3.5, начиная с какой-то суммы вложений, доходы перестают возрастать (реально это соответствует тому, что каждое предприятие способно освоить лишь ограниченноеколичество средств).Выполним условную оптимизацию по изложенной выше методике, начиная с последнего 5-го шага.Каждый раз, когда мы подходим к очередному шагу, имея запас средств S, мы пробуем выделить на этот шаг то или другое ко91личество средств, берем выигрыш на данном шаге по табл. 3.5,складываем его с уже оптимизированным выигрышем на всех последующих шагах до конца расчета.
Учитывая, что средств у насосталось уже меньше, как раз на такое количество средств, котороемы выделили, находим максимальную сумму вложений. Эта суммавложений и есть условное оптимальное управление на данном шаге,а сам максимум – условный оптимальный выигрыш. В табл. 3.6 даны результаты условной оптимизации по всем шагам.Таблица 3.6S12345678910i=5i=4i=3i=2i=1X5(S)J5(S)X 4(S)J4(S)X3(S)J3(S)X2(S)J2(S)X1(S)J1(S)123456789101,01,21,31,31,31,31,31,31,31,301233455671,01,31,62,32,52,62,72,82,82,801221224551,01,62,12,42,93,43,63,73,94,100000555771,01,62.12,42,93,54,14,65,15,625,6Табл.
3.6 построена так: в первом столбце даются значения запаса средств S, с которым мы подходим к данному шагу. Далеетаблица разделена на пять пар столбцов соответственно номерушага. В первом столбце каждой пары приводится значение условного оптимального управления, во втором – условного оптимального выигрыша.Табл. 3.5 заполняется слева направо, сверху вниз. Решение на5-м – последнем – шаге является вынужденным, т. е. выделяютсявсе средства, на всех остальных шагах решение приходится оптимизировать.В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-гои 1-го шагов мы получим полный список всех значений оптимальныхуправлений и безусловный оптимальный выигрыш J* за всю операцию.
В данном случае он равен 5,6. В последних двух столбцахтабл. 3.6 заполнена только одна строка, так как состояние системыперед началом 1-го шага нам в точности известно: S0 = Р = 10. Оптимальные управления на всех шагах выделены рамкой. Таким обра92зом, мы получили окончательный вывод: надо выделить первомупредприятию две единицы из десяти, второму – пять единиц, третьему – две, четвертому – ни одной, пятому – одну единицу.
При этомраспределении доход является максимальным и равен 5,6.Рассмотрим на примере, как заполняется табл. 3.6. Пусть намнужно оптимизировать решение X3(7). Как поступить на 3-м шаге,если мы подошли к нему с запасом средств S=7. Какой максимальный выигрыш мы можем получить на всех оставшихся шагах,включая 3-й?Предположим, что все шаги после 3-го (4-й и 5-й) уже оптимизированы, т.
е. заполнены две первые пары столбцов табл. 3.6. Найдем X3(7) и J3(7). Для этого составим вспомогательную табл. 3.7.В первом ее столбце перечислены все возможные вложения X на 3-мшаге, не превосходящие S = 7. Во втором столбце – то, что остаетсяпосле такого вложения от запаса средств S = 7. В третьем столбце –выигрыш на 3-м шаге от вложения средств X в третье предприятие(заполняется по столбцу L3(X) табл.
3.5). В четвертом столбце –оптимальный выигрыш на всех оставшихся шагах (4-м и 5-м) приусловии, что мы подошли к 4-му шагу с оставшимися средствами(заполняется по столбцу i = 4 табл. 3.5). В пятом столбце – суммадвух выигрышей: шагового и оптимизированного дальнейшегопри данном вложении X в 3-й шаг. Из всех выигрышей последнегостолбца выбирается максимальный (в табл.
3.7 он равен 3,6, а соответствующее управление X(7) = 2).Таблица 3.7X7– XL3(X)J4(7– X)L3(X)+J4(7– X)76543210012345671,81,71,61,41,21,10,6001,01,31,62,32,52,62,71,82,72,93,03,53,63,22,7Возникает вопрос: а что если при запасе средств на 1-м шагедля вспомогательной таблицы типа табл. 3.7 максимум выигрышадостигается не при одном значении X, а при двух или больше?93Ответ ясен: совершенно все равно, какое из значений выбрать;от этого выигрыш не зависит.Вообще в задачах динамического программирования решениевовсе не должно быть единственным.3.1.4.
Структура решения задач динамическогопрограммированияОтыскание оптимальной стратегии принятия набора последовательных решений в большинстве случаев проводится следующим образом: сначала осуществляется выбор последнего по времени решения, затем при движении в направлении, обратном течению времени, выбираются все остальные решения вплоть доисходного.Для реализации метода необходимо выявить все ситуации, в которых может происходить выбор последнего решения. Условия, вкоторых принимается решение, называют состоянием системы. Состояние системы – это описание системы, позволяющее, учитываябудущие решения, предсказать ее поведение. Нет необходимости выяснять, как возникло то или иное состояние или каковы были предшествующие решения.
Это позволяет последовательно выбирать всего по одному решению в каждый момент времени. Независимо оттого, отыскивают оптимальные решения с помощью табличного метода и последующего поиска или аналитическим путем, обычно быстрее и выгоднее осуществлять выбор по одному решению в одинмомент времени, переходя затем к следующему моменту и т. д.К сожалению, таким методом можно исследовать не все процессы принятия решений. Необходимым условием примененияметода динамического программирования является аддитивностьоценок всех решений, а также независимость будущих результатовот предыстории того или иного состояния.Если число решений очень велико, то можно построить относительные оценки состояний так, чтобы оценки, отвечающие каждой паре последовательных решений, отличались друг от друга напостоянную величину, представляющую собой средний доход(выигрыш) на решение.Также можно выполнять дисконтирование доходов от будущихрешений.
Необходимость в этом иногда появляется в том случае,когда решение принимаются редко, скажем раз в году. Тогда ужене нужно рассматривать последовательно 1,2,3…решения, чтобыдостичь решения с бóльшим номером.94Вместо этого можно непосредственно оперировать функциональным уравнением, что, как правило, дает существенное сокращение объема вычислений.3.2. Процедуры динамического программированиядля непрерывных системЗадача выбора оптимального управления u (t ) для непрерывного объекта, описываемого векторным дифференциальным уравнениемdx= f ( x , u ),dtи имеющего критерий оптимальноститJ ( x , u ) = ∫ L( x , u ) dt + G ( x (T )),0может быть сведена к задаче, описываемой уравнениями (3.7) и(3.8), при условии достаточной подробной дискретизации процесса.В общем случае закон оптимального управления u ∗ ( x , t ) находится из решения векторного дифференциального уравнения в частных производных.3.2.1.
Уравнение Гамильтона–Якоби–Беллманав частных производныхОдин из аспектов классической теории Гамильтона–Якоби связан с нахождением дифференциального уравнения в частных производных, которому удовлетворяет функция оптимального качества J ∗ .Ричард Беллман обобщил теорию Гамильтона–Якоби на дискретные многошаговые процессы и комбинаторные задачи.Пусть движение системы описывается векторным дифференциальным уравнениемx = f ( x , u , t )(3.16)95с терминальным граничным условиемφ ⎡⎣ x ( tk ) , tk ⎤⎦ = 0(3.17)и критерием качестваtkJ = Gk ⎡⎣ x ( tk ) , tk ⎤⎦ + ∫ L ⎣⎡ x ( τ ) , u ( τ ) , τ⎤⎦ d τ.(3.18)tОптимальное значение критерия качества, определенное соотношением (3.18), для данной задачи имеет видtk⎧⎪⎫⎪J ∗ ( x , t ) = min ⎨Gk ⎡⎣ x ( tk ) , tk ⎤⎦ + ∫ L ( x , u , τ ) d τ ⎬ ,u (t )t⎩⎪⎭⎪(3.19)причем на гиперповерхности φ ( x , t ) = 0 должно выполняться граничное условиеJ ∗ ( x,t )φ( x ,t ) = 0= Gk ( x , t ) .(3.20)Предположим, что функция J ∗ ( x , t ) существует, непрерывна иимеет непрерывные частные производные первого и второго порядка во всех представляющих интерес точках пространства ( x , t ) .Пусть система движется из точки ( x , t ) в течение некоторого отрезка времени Δt и при этом управление u ( t ) не является оптимальным.
Тогда система достигнет новой точки ⎡⎣ x + f ( x , u , t ) Δt , t + Δt ⎤⎦ .Предположим, что при дальнейшем движении из этой точкиприменяется оптимальное управление, когда функция оптимального качества с точностью до членов первого порядка может бытьпредставлена в формеJ ∗ ( x + f ( x , u , t ) Δt , t + Δt ) + L ( x , u , t ) Δt = J 1 ( x, t ) .96Поскольку в интервале [t , t + Δt ] использовано неоптимальноеуравнение, то имеет место неравенствоJ ∗ ( x , t ) ≤ J 1 ( x , t ).(3.21)Знак равенства в (3.21) будет справедлив в том случае, если винтервале [t , t + Δt ] управление u ( t ) выбирается так, что оно минимизирует правую часть соотношения (3.23):{}J ∗ ( x , t ) = min J ∗ ⎡⎣ x + f ( x , u , t ) Δt , t + Δt ⎤⎦ + L ( x , u , t ) Δt .uПо предположению функция J ∗ ( x , t ) непрерывна и дифференцируема, поэтому можно разложить первую часть последнегоравенства в ряд Тейлора по x и t :⎧⎪⎫⎪∂J ∗∂J ∗J ∗ ( x ,t ) = min ⎨ J ∗ ( x ,t ) +f ( x ,u ,t ) Δt +Δt + L ( x ,u ,t ) Δt ⎬.u ⎪∂x∂t⎪⎭⎩(3.22)Поскольку функционал J ∗ и, следовательно, его частные про∂J ∗изводныене зависят явным образом от управления u , то, пе∂tреходя к пределу при Δt → 0 в выражении (3.22), получим−⎧⎪⎫⎪∂J ∗∂J ∗f ( x , u , t )⎬.= min ⎨ L ( x , u , t ) +u ⎪∂t∂x⎩⎭⎪(3.23)Множители Лагранжа p ( t ) являются функциями чувствительности, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
