Синтез оптимальных систем методом динамического проектирования. Лабораторная работа №4 (1253750), страница 2
Текст из файла (страница 2)
Какие методы следует применять для нахождения глобальногоэкстремума функционала?7. Что означает проклятие размерности при применении методадинамического программирования?8. Почему для нахождения оптимального управления методомдинамического программирования идут от конца процесса к началу?9. Чем отличается метод динамического программирования отодношагового перебора?10.Является лирешениезадачи методомдинамическогопрограммирования единственным?11.
Связь динамического программирования с классическимвариационным исчислением.12. Связь динамического программирования с принципом максимумаЛ.С.Понтрягина.Литература:1. Сборник лабораторных работ по курсу «Управление в техническихсистемах»: Метод. указания к лабораторным работам / Под ред. К.
А.Пупкова. - М.: Изд-во МГТУ им. Н.Э.Баумана, 2002. – 72с.2. Деменков Н.П. Вычислительные аспекты решения задач оптимальногоуправления: Учебное пособие. -М. : Изд-во МГТУ им.Н.Э.Баумана,2007.-171с.3. Деменков Н.П. Практикум по динамическому программированию: Учебноепособие.
-М.: Изд-во МГТУ им.Н.Э.Баумана, 2015.-100с.4. Деменков Н.П., Микрин Е.А. Управление в технических системах: Учебник. М.: Изд-во МГТУ им.Н.Э.Баумана, 2017.- 452с.4 _________________________________________________________________________________Деменков Н.П. Синтез оптимальных систем методом динамического программированияМосковский государственный технический университет им.Н.Э.БауманаКафедра “Системы автоматического управления”__________________________________________________________________________________Приложение А.
Задача о распределении ресурсовВ распоряжении инвестора имеется некоторый запас средств (ресурсов)Р, который должен быть распределён между k предприятиями П1,П2,...,Пk.Каждое из предприятий Пi при включении в него каких-то средств хприносит доход, зависящий от средств х, т.е. представляющий собой какуюто неубывающую функцию Li(x). Все функции Li(x), i=1,2,...,k заданы.Спрашивается, как нужно распределить средства Р между предприятиями,чтобы в сумме они дали максимальный доход?Эта задача легко решается методом динамического программирования.Хотя в своей постановке она не содержит упоминания о времени, можно всеже операцию распределения средств мысленно развернуть в какой-топоследовательности, считая за первый шаг вложение средств в предприятиеП1, за второй П2, и т.д.Объект управления в данном случае - средства или ресурсы, которыераспределяются.
Состояние объекта перед каждым шагом характеризуетсяодним числом S - наличным запасом еще не вложенных средств. В этой задаче"шаговыми управлениями" являются средства х1,x2,...,xk,выделяемыепредприятиям. Требуется найти оптимальное управление, т.е. такуюсовокупность чисел x1,x2,...,xk, при которой суммарный доход максимален:kJ= Li(xi)=> max.(А.1)i 1Найдём для каждого i-го шага условный оптимальный выигрыш Ji(s) (отэтого шага и до конца), если мы подошли к данному шагу с запасом средств s.Соответствующее ему условное оптимальное управление xi(s) есть средства,вкладываемые в i-е предприятие.Начнём оптимизацию с последнего, k-го шага. Пусть мы подошли к этомушагу с остатком средств s. Что нам делать? Очевидно, вложить всю суммуs целиком в предприятие Пk.
Поэтому условное оптимальное управление на k-мшаге: отдать последнему предприятию все имеющиеся средства s, т.е. xk(S)=s,а условный оптимальный выигрыш Jk(S)=Lk(S).Задаваясь целой гаммой значений s (располагая их достаточно тесно), мыдля каждого значения s будем знать xk(S) и Jk(S). Последний шагоптимизирован.Перейдем к предпоследнему, (k-1) шагу. Пусть мы подошли к нему снекоторым запасом средств 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)}.(А.2)x SЗнак max (x S) означает, что берется максимальное значение по всем x, какиетолько возможны (вложить больше, чем s, мы не можем), от выражения,стоящего в фигурных скобках.
Этот максимум и есть условный оптимальныйвыигрыш за два последних шага, а то значение x, при котором этот максимумдостигается, - условное оптимальное управление на (k-1) шаге.Далее оптимизируем (k-2), (k-3) и т.д. шаги.В общем, для любого i-го шага будем находить условный оптимальный5 _________________________________________________________________________________Деменков Н.П. Синтез оптимальных систем методом динамического программированияМосковский государственный технический университет им.Н.Э.БауманаКафедра “Системы автоматического управления”__________________________________________________________________________________выигрыш за все шаги с этого и до конца по формулам:Ji(s)=max {Li(x)+Ji+1(s-x)}x S(А.3)и соответствующее ему условное оптимальное управление xi(s) - то значение x,при котором этот максимум достигается.Продолжая таким образом, дойдем наконец до первого предприятия П1.Здесь нам не нужно будет варьировать значение s. Мы точно знаем, что запассредств перед первым шагом равен Р:J*=J1(Р)=max{L1(x)+L2(Р-x)}.(А.4)xРИтак, максимальный выигрыш (доход) от всех предприятий найден.Теперь остается только "прочесть рекомендации".
То значение x, при которомдостигается максимум (А.4), и есть оптимальное управление x1* на 1-ом шаге.После того, как мы вложим эти средства в первое предприятие, у нас ихостанется s=Р-x1*.“Читая” рекомендацию для этого значения s, выделяем второмупредприятию оптимальное количество средств: x2*=x2(Р-x1*) и т.д. до конца.Решим численный пример для Р=10 у.е. и k=5. Функции дохода для случая,когда вкладываются только целые количества средств, заданы в табл. А.1.Таблица А.1x12345678910L1(x)1,01,21,31,31,31,31,31,31,31,3L2(x)0,61,11,21,41,61,71,81,61,61,6L3(x)0,30,61,31,41,51,51,51,51,51,5L4(x)0,10,51,21,82,52,93,53,53,53,5L5(x)0,50,91,41,51,71,81,81,81,81,8В каждом столбце, начиная с какой-то суммы вложений, доходыперестают возрастать (реально это соответствует тому, что каждоепредприятие способно "освоить" лишь ограниченное количество средств).Выполним условную оптимизацию по вышеизложенной методике, начинаяс последнего, 5-го шага.Каждый раз, когда мы подходим к очередному шагу, имея запас средств s,мы пробуем выделить на этот шаг то или другое количество средств, беремвыигрыш на данном шаге по табл.
А.1, складываем с уже оптимизированнымвыигрышем на всех последующих шагах до конца (учитывая, что средств у насосталось уже меньше, как раз на такое количество средств, которое мывыделили) и находим то вложение, на котором эта сумма достигаетмаксимума. Это вложение и есть условное оптимальное управление на данномшаге, а сам максимум - условный оптимальный выигрыш. В табл. А.2 данырезультаты условной оптимизации по всем шагам.Таблица А.2-----------------------------------------------------------------¦S ¦ i=5¦ i=4¦ i=3¦ i=2¦ i=1|¦¦-----------¦-----------¦-----------¦-----------¦-----------|¦¦ x5(s)¦J5(s)¦x4(s)¦J4(s) ¦x3(s)¦J3(s)¦x2(s)¦J2(s) ¦x1(s)|J1(s)|¦-----¦-----¦-----¦-----¦-----¦-----------¦-----------¦-----------|¦ 1 ¦ 1 ¦ 1,0 ¦ 0¦ 1,0 ¦ 0| 1,0 ¦ 0 | 1,0 ¦||¦ 2 ¦ 2 ¦ 1,2 ¦ 1¦ 1,3 ¦ 1| 1,6 ¦ 0 | 1,6 |||¦ 3 ¦ 3 ¦ 1,3 ¦ 2¦ 1,6 ¦ 2| 2,1 ¦ 0 | 2,1 |||¦ 4 ¦ 4 ¦ 1,3 ¦ 3¦ 2,3 ¦ 2| 2,4 | 0 | 2,4 |||6 _________________________________________________________________________________Деменков Н.П.
Синтез оптимальных систем методом динамического программированияМосковский государственный технический университет им.Н.Э.БауманаКафедра “Системы автоматического управления”__________________________________________________________________________________¦ 5 ¦ 5 ¦ 1,3 ¦ 3¦ 2,5 ¦ 1| 2,9 ¦ 0 | 2,9 |||¦ 6 ¦ 6 ¦ 1,3 ¦ 4¦ 2,6 ¦ 2| 3,4 ¦ 5 | 3,5 |||¦ 7 ¦ 7 ¦ 1,3 ¦ 5¦ 2,7 ¦ 2| 3,6 | 5 | 4,1 |||¦ 8 ¦ 8 ¦ 1,3 ¦ 5¦ 2,8 ¦ 4| 3,7 | 5 | 4,6 |||¦ 9 ¦ 9 ¦ 1,3 ¦ 6¦ 2,8 ¦ 5| 3,9 | 7 | 5,1 |||¦ 10 ¦ 10 ¦ 1,3 ¦ 7¦ 2,8 ¦ 5| 4,1 | 7 | 5,6 | 2 | 5,6 |-------------------------------------------------------------------Таблица построена так: в первом столбце даются значения запасасредств s, с которым мы подходим к данному шагу. Далее таблица разделенана пять пар столбцов, соответственно номеру шага. В первом столбцекаждой пары приводится значение условного оптимального управления, вовтором - условного оптимального выигрыша.Таблица заполняется слева направо, сверху вниз.
Решение на пятом последнем шаге вынужденное: выделяются все средства, на всех остальныхшагах решение приходится оптимизировать.В результате последовательной оптимизации 5, 4, 3, 2 и 1 шагов получимполный список всех рекомендаций по оптимальному управлению и безусловныйоптимальный выигрыш J* за всю операцию. В последних двух столбцах табл.А.2 заполнена только одна строка, так как состояние системы перед началомпервого шага нам известно: s0=Р=10. Оптимальные управления на всех шагахвыделены рамкой. Таким образом, мы получили окончательный вывод: надовыделить первому предприятию две единицы из десяти, второму - пять единиц,третьему - две, четвёртому - ни одной, пятому - одну единицу.
При этомраспределении доход будет максимальным и равен 5,6.Табл. А.2 заполняется следующим образом. Пусть, например, нам нужнооптимизировать решение x3(7) - как поступить на третьем шаге, если мыподошли к нему с запасом средств s=7, и сколько максимум мы можемвыиграть на всех оставшихся шагах, включая третий?Предположим, что все шаги после третьего (4-й и 5-й) ужеоптимизированы, т.е. заполнены две первые пары столбцов табл. А.2.
Найдёмx3(7) и J3(7). Для этого составим вспомогательную табл.А.3.Таблица А.3------------------------------------------------------¦ x ¦ 7-x ¦ L3(x) ¦ J4(7-x) ¦ L3(x)+J4(7-x)¦------------------------------------------------------¦ 7 ¦0¦1.8¦0¦1.8¦¦ 6 ¦1¦1.7¦1.0¦2.7¦¦ 5 ¦2¦1.6¦1.3¦2.9¦¦ 4 ¦3¦1.4¦1.6¦3.0¦¦ 3 ¦4¦1.2¦2.3¦3.5¦¦ 2 ¦5|1.1¦2.5¦3.6¦¦ 1 ¦6¦0.6¦2.6¦3.2¦¦ 0 ¦7¦0¦2.7¦2.7¦-------------------------------------------------------В первом ее столбце перечислены все возможные вложения x на третьемшаге, не превосходящие s=7. Во втором столбце - то, что остается послетакого вложения от запаса средств s=7. В третьем столбце - выигрыш натретьем шаге от вложения средств x в третье предприятие (заполняется постолбцу L3(x) табл.А.1).
В четвертом столбце – оптимальный выигрыш навсех оставшихся шагах (четвертом и пятом) при условии, что мы подошли кчетвертому шагу с оставшимися средствами (заполняется по столбцу i=4табл.А.1). В пятом столбце – сумма двух выигрышей: шагового иоптимизированного дальнейшего при данном вложении x в третий шаг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
