Динамическое программирование и дифференциальное и интегральное исчисление в образах

курсовая работа

2) Вычислительные аспекты динамического программирования

3) Рассмотреть подробнее примеры данной темы

4) Изучить функции

5) Рассмотреть последовательно и ряды.

1. Динамическое программирование

1.1 Задачи оптимальности и их разновидности

Вся математика изначально и многие ее разделы впоследствии -- в том числе и ДП -- своим происхождением и развитием обязаны именно практической, хозяйственной, экономической жизни общества. Выйдя из самих ее основ и неоднократно пройдя классический цикл «от живого созерцания к абстрактному мышлению и от него к практике», развив в себе мощные количественные методы анализа, математика не может не найти эффективные приложения в самых различных сферах человеческой деятельности. Данное обстоятельство подчеркивает, в частности, неправомерность острого противопоставления математики и реального мира, равно как теории и практики вообще.

Динамическое программирование есть поэтапное планирование многошагового процесса, при котором на каждом этапе оптимизируется только один шаг.

Управление на каждом шаге должно выбираться с учетом всех его последствий в будущем. Динамическое программирование -- это планирование дальновидное, с учетом перспективы. Это не близорукое планирование «вслепую» на один шаг. Напротив, управление нa каждом шаге выбирается исходя из интересов операции в целом.

Проиллюстрируем принцнп «дальновидного» планирования на примерах.

Пусть, например, планируется работа группы разнородных промышленных предприятий на период времени Т лет и конечной задачей является получение максимального объема продукции некоторого класса С товаров широкого потребления.

В начале периода имеется определенный запас средств производства (машин, оборудования), с помощью которого можно начать производство товаров этого класса.

«Шагом» или «этапом» процесса планирования является хозяйственный год. Пусть нам предстоит выбор решения на закупку сырья, машин и распределение средств по предприятиям на первый год. При «близоруком» поэтапном планировании мы приняли бы решение: вложить максимальное количество средств в закупку сырья и пустить имеющиеся машины на полную мощность, стремясь к максимальному объему продукции класса С к концу первого же года.

При дальновидном планировании, напротив, будут предусмотрены мероприятия, обеспечивающие пополнение машинного парка по мере его изнашивания. С учетом таких капиталовложений объем продукции основного товара С первый год будет меньше, чем мог бы быть, но зато будет обеспечена возможность расширения производства в последующие годы.

Возьмем другой пример. Процесс планирования в шахматной игре тоже распадется на отдельные шаги (ходы). Допустим, что фигуры условно оценены тем или другим числом очков соответственно своей важности; беря фигуру, мы выигрываем это число очков, а отдавая -- проигрываем.

Разумно ли будет, продумывая шахматную партию на несколько шагов вперед, всегда стремиться к тому, чтобы на каждом шаге выигрывать максимальное число очков? Очевидно, нет. Такое, например, решение, как «пожертвовать фигуру», никогда не может быть выгодно с узкой точки зрения одного-единственного хода, но может быть выгодно с точки зрения партии в целом.

Так обстоит дело и в любой области практики. Планируя многоэтапную операцию, мы должны выбирать управление на каждом шаге, исходя не из узких интересов именно этого шага, а из более широких интересов операции в целом, и далеко не всегда эти две точки зрения совпадают.

Общее правило: в процессе поэтапного планирования управление на каждом шаге должно приниматься с учетом будущего. Однако из этого правила есть исключение. Среди всех шагов существует один, который может планироваться попросту, без «оглядки на будущее». Какой это шаг? Очевидно, последний. Этот последний шаг, единственный из всех, можно планировать так, чтобы он как таковой приносил наибольшую выгоду.

Спланировав оптимальным образом этот последний шаг, можно к нему «пристраивать» предпоследний, к этому в свою очередь предпредпоследний и т. д.

Поэтому процесс динамического программирования всегда разворачивается в обратном по времени направлении: не от начала к концу, а от конца к началу. Раньше всего планируется последний шаг. А как его спланировать, если мы не знаем, чем кончился предпоследний? Очевидно, нужно сделать разные предположения о том, чем кончился предпоследний шаг, и для каждого из них выбрать управление на последнем.

Такое оптимальное управление, выбранное при определенном условии о том, чем кончился предыдущий шаг, мы будем называть условным оптимальным управлением.

Принцип динамического программирования требует нахождения на каждом шаге условного оптимального управления для любого из возможных исходов предшествующего шага.

Продемонстрируем схему такой процедуры. Пусть планируетсят-шаговая операция, и неизвестно, чем кончился (т--1)-й шаг. Сделаем об этом ряд «гипотез» или «предположений». Эти гипотезы мы обозначим:

S(1)(m-1) , S(2)(m-1) ,,, S(j)m-1

Оговоримся, что буквой S(j)m-1 не обязательно обозначается одно число: это может быть и группа чисел, характеризующих исход (m--1)-го шага, .а может быть и просто качественное состояние той физической системы, в которой протекает управляемый процесс.

Найдем для каждого из предположений условное оптимальное управление на последнем (m-м) шаге. Это будет то из всех возможных управленийUm, при котором достигается максимально возможное значение выигрыша на последнем шаге.

Предположим, что для каждого из предположений условное оптимальное управлениеUm на последнем шаге найдено:

U*m (S(1)m-1) ; U*m (S(2)m-1); U*m (S(j)m-1)

Это означает, что последний шаг спланирован для любого исхода предпоследнего.

Перейдем к планированию следующего от конца, предпоследнего шага. Снова сделаем ряд гипотез о том, чем кончился предпредпоследний ((m -- 2)-й) шаг:

Поставим вопрос: как нужно выбирать для каждой из этих гипотез условное оптимальное управление на (m--1)-м шаге?

Очевидно, его нужно выбирать так, чтобы оно, сов-местно с уже выбранным управлением на последнем шаге, обеспечивало максимальное значение критерия W на двух последних шагах.

Другими словами, для каждой из гипотез нужно найти такое условное оптимальное управление на (m--1)-м шаге

U*m-1 (Sm-2)

чтобы оно, в совокупности с уже найденным условным оптимальным управлениемU*m(Sm-1), давало максимально возможный выигрыш на двух последних шагах.

Очевидно, к (т-- 1)-му шагу таким же точно способом может быть присоединен (m -- 2)-й и т. д. вплоть до самого последнего (от конца) 1-го шага, с которого процесс начинается.

Первый шаг, в отличие от всех других, планируется несколько иначе. Так как мы обычно знаем, с чего начинается процесс, то нам уже не требуется делать гипотезы о том, в каком состоянии мы приступаем к первому шагу. Это состояние нам известно. Поэтому, учитывая, что все последующие шаги (2-й, 3-й и т. д.) уже спланированы (условно), нам остается просто спланировать первый шаг так, чтобы он был оптимальным с учетом всех управлений, уже принятых наилучшим образом на всех последующих шагах.

Принцип, положенный в основу построения такого решения (искать всегда оптимальное продолжение процесса относительно того состояния которое достигнуто в данный момент), часто называют принципом оптимальности.

1.2 Метод динамического программирования и его основные этапы

Рассмотренный принцип оптимальности лежит в основе метода ДП 1 решения задач управления многошаговыми процессами. Метод ДП включает три основных этапа:

1) предварительный этап;

2) этап условной оптимизации;

3) этап безусловной оптимизации.

Изложим содержание этих этапов, имея в виду задачу ДП на поиск максимума.

Предварительный этап проводится с целью уменьшения вычислительной работы на последующем этапе решения и, по существу, заключается в нахождении всех допустимых значений управлений щ и фазовых переменных Xi (т. е. фактически областей определения функций Bi(xi) или, в более сложных случаях, множеств, содержащих эти области определения). Иными словами, на данном этапе отбрасываются все заведомо неподходящие, нереализуемые значения фазовых и управляющих переменных. Проводится предварительный этап в естественном порядке от первого шага к последнему: i=1,2,...,N, а опираются соответствующие расчеты на уравнение процесса хi = fi(xi-1,ui).Данный этап особенно удобен при табличном способе задания функций, фигурирующих в условии задачи.

Этап условной оптимизации заключается в непосредственном вычислении функций Беллмана Bi(xi) и проводится, как и предписывает принцип оптимальности, в обратном порядке от последнего шага к первому: i = N,N--1,..., 2,1. Расчет проводится следующим образом. Для последнего шага при i = N с учетом условия BN(XN) = 0 принцип оптимальности Беллмана принимает следующий наиболее простой вид:

BN-1(xn-1)=maxuN{zN(xN-1,uN)}

Иначе говоря, при планировании последнего шага нет необходимости учитывать прогноз на будущее. При этом для каждого допустимого значения аргумента xN-1 (определенного на предварительном этапе) максимум достигается при некотором управлении uN=uN(xN-1) Вычисленная функцияBn-1(xN-1) позволяет перейти к предшествующему шагу приi = N -- 1 и снова применить принцип оптимальности -- он уже не будет иметь столь простую форму записи. Продолжая аналогичным образом, завершим данный этап вычислением функций B0(x0) и ui(x0) после прохождения первого шага при i = 1.

Этап безусловной оптимизации проводится с целью окончательного вычисления оптимального значения задачиZ* и построения оптимального управления

(u1* и2*…uN*) и оптимальной траектории x0* , x1* …xN*. Проводится Данный этап в естественном порядке от первого шага к последнему:i -- 1, 2,..., N. Построение оптимального решения начинается с определения оптимального значения задачи Z* и оптимального начального состояния Xq. Если начальное состояние определено однозначно, то оптимальное значение задачи Z* равно Bо(x0); Приэтом принимаем x0*= x0. Если же начальное состояние не определено однозначно, а принимает значения из некоторого множества начальных состояний Хо, то.оптимальное значение задачи Z* вычисляется по формуле

Z* = mах{B0(x0)}.

x0€X0

В этом случае в качестве принимаем то значение переменной x0*, при котором данный максимум достигается (таких значений может быть одно или несколько).

При построении оптимального управления и оптимальной траектории используются функции Ui(xi-i), вычисленные на этапе условной оптимизации. На первом шаге при i=1, используя уже известное значение x0*, находим:

u1* = u1(x0*),х1* = f1(x0*,u1*)

На втором шаге приi = 2, используя вычисленное находим:.

u2* = u2(x1*),х2* = f2(x1*,u2*)

Продолжая аналогично, получим на последнем шаге при i = N:

uN* = un(xn-1*),хn* = fn(xn-1*,un*)

Таким образом полностью определяются оптимальное решение

(u1* и2*…uN*) и оптимальная траекторияx0* , x1* …xN*. системы. Отметим, что и оптимальное решение, и оптимальная траектория могут быть определены неоднозначно. Важно заметить, что функции Беллмана Bi(xi) не участвуют в построении оптимального решения задачи и, следовательно, не требуют длительного хранения в памяти при реализации метода ДП на ЭВМ.

Порядок расчетов в методе ДП может быть проиллюстрирован следующей схемой, в которой точками обозначены состояния системы.

Этапы метода ДП

Номера шагов процесса

12 ... N

Предварительный

? > ? > ? > …> ? >?

v

? < ? < ?< … <?<?

v

? > ? > ?> … > ?> ?

Условной оптимизации

Безусловной оптимизации

Тем самым, в ходе решения задачи методом ДП весь многошаговый процесс просчитывается три раза в переменных направлениях. Отметим следующие основные достоинства метода ДП: -- сравнительная простота и однотипность расчетов, что является удобным для алгоритмизации и программирования задач при их решении на ЭВМ;

— снижение трудоемкости решения задач за счет более полного использования свойств управляемых систем;

— отсутствие специальных ограничений на природу, характер и свойства функций f и z. Они, например, могут не являться линейными, выпуклыми, непрерывными, дифференцируемыми, и могут быть заданы как таблично, так и аналитически, т. е. в виде формул.

Делись добром ;)