Синтез оптимальных систем методом динамического проектирования. Лабораторная работа №4

Московский государственный технический университет им.Н.Э.БауманаКафедра “Системы автоматического управления”__________________________________________________________________________________СИНТЕЗ ОПТИМАЛЬНЫХ СИСТЕМ МЕТОДОМДИНАМИЧЕСКОГО ПРОГРАМИРОВАНИЯЛабораторная работа №4 по курсу ОУДПЦель работы: овладеть навыками и умением по построениюоптимальных систем на основе принципа оптимальности Р.

Беллмана.Необходимое оборудование: ПЭВМ, совместимая с IBM PC, пакетMatlab под операционной системой Microsoft Windows.Продолжительность работы: 4 часа.ВведениеМетод динамического программирования Р.Беллмана, основанный напринципе оптимальности, применим не только к оптимальным задачамдинамики, но и весьма широкому кругу технических и экономических задач, вкоторых связи между координатами, управлениями и критерииоптимальности могут задаваться как в виде дифференциальных уравненийвесьма произвольного вида, так и в виде экспериментально определенныхграфиков или таблиц численных данных.Принцип оптимальности, сформулированный Р.Беллманом, гласит:оптимальное управление таково, что каким бы ни было начальное состояниесистемы и начальное оптимальное управление u *(t), определённое дляинтервала t0tti, всегда последующее управление u **(t) на интервале ti t tkдолжно быть также оптимальным относительно состояния, возникшего врезультате первого этапа.

Это означает, что значение функционала J* винтервале to t tk на управлениях u *(t) и u **(t) должно быть одинаковым.Основой вычислительных процедур динамического программированияслужит рекуррентное уравнение Беллмана, которое является следствиемприменения принципа оптимальности к многошаговым процессам.Если процесс управления удается разбить естественным илиискусственным путем на отдельные шаги или этапы, то управляемыйдинамический процесс в этом случае описывается разностным уравнениемxn+1=T(xn,un), unUn, n=0,1,2, ...

,k-1, xo=x(0),(1)зависящим от параметра управления un, который на каждом шаге можетпринимать одно из множества значений Un (пространство допустимыхуправлений на n-м шаге) и параметра состояния xn.Качество управления определяется значением целевой функции L,численное значение которой можно рассматривать как потери, которыенесем при том или ином управлении.Потери за один шаг будут зависеть от состояния процесса в начале шагаи примененного на этом шаге управления, то естьLn=L(xn, un), un  Un.За критерий качества управления можно принять полные потери за все k1 _________________________________________________________________________________Деменков Н.П.

Синтез оптимальных систем методом динамического программированияМосковский государственный технический университет им.Н.Э.БауманаКафедра “Системы автоматического управления”__________________________________________________________________________________шагов процесса и представить критерий качества управления k-шаговогопроцесса в видеk 1Jk=  Ln(xn,un).(2)n 0Оптимизация управления k-шагового процесса состоит в том, чтобынайти такую последовательность управлений u0, u1, …,u1, ..., uk-1, при которойкритерий качества Jk принимает минимальное значение.Выбор управления на отдельном шаге осуществляется не с точки зренияинтересов данного шага, выражающихся в минимизации потерь на данномшаге, то есть величины L(xn,un), а с точки зрения интересов всего процесса вцелом, выражающихся в минимизации суммарных потерь L(xn,un)+Jn+1*[T(x,u)]на всех последующих шагах.Из принципа оптимальности следует, что оптимизация управления дляпроизвольной стадии многошагового процесса заключается в выборе толькопоследующих управлений.

Поэтому удобно учитывать не те шаги, которыеуже были пройдены, а те, которые осталось проделать, чтобы привестипроцесс в конечное состояние.Оптимальное значение целевой функции J* и оптимальное управлениена каждом шаге многошагового процесса определяется из уравнения БеллманаJ i* ( x )  min{Li ( x , u )  J i*1 ( x , u )} ,(3)uUв котором величина i означает число шагов до конца процесса.Метод динамического программирования как метод оптимизациидинамических систем, т.е.

процессов, развивающихся во времени иописываемых тройкой ( x , u , t), может применяться и для оптимизациистатических задач, если роль параметра t будет выполнять некоторый другойпараметр,допускающийразбиениезадачиоптимизациинапоследовательность этапов (метод нахождения кратчайшего пути в графе).Практическая работа1. Ознакомиться с решением задачи распределения ресурсов,приведенную в Приложении A.2. Выполнить синтез оптимального управления методом динамическогопрограммирования для задачи распределения ресурсов.Инвестор выделяет средства в размере 5 млн. ден. ед., которые должныбыть распределены между тремя предприятиями. Построить планраспределенияинвестициймеждупредприятиями,обеспечивающийнаибольшую общую прибыль, если каждое предприятие при инвестировании внего средств x млн.

ден. ед. приносит прибыль Li(x) млн. ден. ед. (i=1, 2 и 3) последующим данным (табл.1)Таблица 1Инвестированиесредств (млн. ден. ед.)x12345Прибыль (млн. ден. ед.)L1(x)3,223,574,1244,85L2(x)3,334,875,267,349,49Таблицы полученного управления (распределенияпоказателя качества построить на каждом шаге.L3(x)4,277,6410,2515,9316,12инвестиций)и2 _________________________________________________________________________________Деменков Н.П. Синтез оптимальных систем методом динамического программированияМосковский государственный технический университет им.Н.Э.БауманаКафедра “Системы автоматического управления”__________________________________________________________________________________Сделать выводы и результаты продемонстрировать преподавателю.3.

Ознакомиться с решением задачи о рюкзаке, приведенную вПриложении Б.4. Методом динамического программирования решить в Matlab(предварительно составив программу) задачу о рюкзаке.Имеется n предметов, aj - вес, bj - ценность j -го предмета, aj > 0; bj > 0:Требуется загрузить рюкзак, выдерживающий максимальный вес c, наборомпредметов, суммарная ценность которых максимальна. a = (a1; : : : ; an); b =(b1; : : : ; bn):1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.c = 25; a = (6; 7; 9; 8; 4; 7); b = (2; 12; 3; 7; 1; 3):c = 29; a = (5; 7; 9; 6; 7; 5); b = (4; 8; 3; 7; 1; 3):c = 26; a = (7; 4; 9; 8; 6; 5); b = (2; 12; 3; 7; 1; 3):c = 27; a = (7; 9; 3; 8; 5; 12); b = (2; 4; 3; 7; 1; 3):c = 25; a = (9; 6; 3; 8; 7; 4); b = (7; 4; 2; 5; 1; 3):c = 25; a = (9; 6; 13; 8; 7; 5); b = (7; 9; 2; 5; 1; 3):c = 26; a = (9; 6; 3; 8; 7; 9); b = (7; 4; 2; 5; 5; 3):c = 26; a = (9; 4; 3; 8; 5; 9); b = (7; 4; 2; 5; 7; 3):c = 25; a = (7; 5; 4; 8; 6; 9); b = (7; 4; 2; 5; 7; 3):c = 26; a = (7; 5; 4; 8; 4; 9); b = (6; 4; 2; 5; 7; 3):c = 24; a = (7; 5; 4; 8; 4; 6); b = (6; 8; 2; 5; 7; 3):c = 29; a = (7; 5; 9; 8; 14; 6); b = (6; 8; 2; 5; 7; 3):c = 29; a = (7; 8; 9; 8; 14; 6); b = (6; 2; 4; 5; 7; 3):c = 29; a = (7; 8; 9; 8; 14; 5); b = (6; 2; 4; 5; 7; 8):c = 29; a = (7; 8; 9; 8; 4; 15); b = (6; 2; 4; 5; 7; 3):c = 28; a = (4; 8; 9; 8; 9; 15); b = (6; 2; 4; 5; 7; 3):c = 29; a = (4; 8; 9; 8; 9; 9); b = (6; 7; 4; 5; 7; 8):c = 31; a = (4; 8; 9; 8; 3; 9); b = (6; 7; 4; 5; 7; 8):c = 33; a = (4; 8; 9; 8; 3; 8); b = (6; 7; 4; 5; 7; 8):c = 32; a = (4; 8; 9; 8; 3; 8); b = (6; 7; 2; 5; 7; 8):c = 34; a = (3; 8; 9; 8; 3; 8); b = (6; 7; 2; 5; 7; 8):c = 34; a = (3; 8; 9; 8; 3; 7); b = (6; 7; 2; 5; 7; 8):c = 31; a = (3; 8; 5; 8; 3; 7); b = (6; 4; 2; 5; 7; 8):Таблицы полученного управления (распределения инвестиций) ипоказателя качества построить на каждом шаге.Сделать выводы и результаты продемонстрировать преподавателю.В результате выполнения ИПР студент должен получить следующиенавыки и умения:1.

Навыки по оптимизации систем управления на основе принципаоптимальности Р.Беллмана.2. Умение определить условия управляемости и достижимостисистемы.3. Умение решить задачу оптимизации методом динамическогопрограммирования.В результате выполнения ИПР студент должен получить следующиезнания:1. Понятие о принципе оптимальности Р.Беллмана.2. Методах решения задач на основе динамического программированиядля дискретных систем.3 _________________________________________________________________________________Деменков Н.П.

Синтез оптимальных систем методом динамического программированияМосковский государственный технический университет им.Н.Э.БауманаКафедра “Системы автоматического управления”__________________________________________________________________________________3. Достоинствах и недостатках решения задач оптимизации методамидинамического программирования.Оформление отчетаОтчет по лабораторной работе должен содержать:1.

Титульный лист.2. Наименование и цель работы.3. Постановка задачи исследования.4. Вычислительный алгоритм решения исследуемой задачи, блок-схемупрограммы и программу.5. Результаты моделирования (таблицы полученного управления ипоказателя качества на каждом шаге).2. Выводы по работе.Вопросы:1. Постановка задачи оптимизации на основе метода динамическогопрограммирования.2.

Что такое многошаговый процесс управления?3. Какие вычислительные проблемы возникают при решении задачоптимизации методом динамического программирования?4. Как можно получить оптимальное управление для статическихзадач?5. Почему для функционирования системы требуется выполнениеусловий управляемости или достижимости?6.