Министерство образования и науки РФ
ГОУ ВПО «УГТУ-УПИ»
Курсовая работа
По дисциплине: теория информационных процессов и систем
На тему: комбинированные задачи использование динамического программирования для их решения.
Примеры решения задач предполагающих необходимость выбора оптимального варианта из очень большого количества возможных вариантов.
Семестр № 7.
Преподаватель:Александров О.Е.
Студентка гр.ДО 43010 да
г. Алапаевск
Запольских Алевтина Евгеньевна
Екатеринбург 2006
Динамическое программирование
Введение
Метод динамического программирования – широко известный и мощный математический метод теории управления, был предложен в конце 50-х годов американским математиком Р.Беллманом и быстро получил широкое распространение, чему способствовали ярко и доходчиво написанные книги самого Беллмана, которые были быстро переведены на русский язык и изданы у нас в стране . Вскоре стало ясно, что метод динамического программирования тесно связан с классическим методом Гамильтона-Якоби в аналитической механике (для систем с непрерывным временем) и с последовательным анализом Вальда ( для систем с дискретным временем). Однако весьма общая и отчетливая формулировка метода динамического программирования, дана Беллманом, а также многочисленные приложения метода к разнообразным проблемам теории принятия решения, экономики, экологии и других областей знания способствовали закреплению этого метода как одного из важнейших инструментов теории управляемых процессов.
Задача оптимального управления.
Пусть задан некоторый критерий качества процесса управления ( критерий оптимальности) вида
Здесь R (x,u) и F(x) – заданные скалярные функции своих аргументов, N – момент окончания процесса, N>0.При этом функция R может отражать расход средств или энергии на каждом шаге процесса, а функция F – характеризовать оценку конечного состояния системы или точность приведения в заданное состояние.
Задача оптимального управления формулируется как задача определения допустимых управлений u(0), u(1),-,u(N-1), удовлетворяющих ограничениям, и соответствующей траектории, то есть последовательности x(0),x(1),-,x(N), которые в совокупности доставляют минимальное значение.
Минимизация обычно отвечают выбору управления, обеспечивающего наименьшие затраты средств, ресурсов, энергии, наименьшее отклонение от заданной цели или заданной траектории процесса. Наряду с этим часто ставится также задача о максимизации критерия , например о максимизации дохода или объема производства. Однако нетрудно видеть, что максимизация критерия J эквивалентна минимизации критерия (-J). Поэтому простая замена знака у функции R и F приводит задачу о максимизации критерия к задаче о его максимизации.
Элементарный подход.
Элементарный подход к поставленной задаче оптимального управления, состояние системы в каждый последующий момент времени выражается через ее состояние и управления в предыдущий момент времени. Применяя это соотношение многократно, можно выразить состояние системы во все моменты времени только через начальное состояние x0 и управления в предшествующие моменты. В результате получаем:
J=R(x0,u(0))+R(f(x0,u(0)),u(1))+_=F(x0,u(0),u(1),_,u(N-1)).
Здесь F – некоторая громоздкая, но, вообще говоря , известная функция своих аргументов. Таким образом, поставленная задача оптимального управления свелась к задаче о минимизации функции F от векторов u(0),u(1),_,u(N-1), то есть от Nm переменных. При больших N (а обычно представляет интерес именно процессы с большими N) это задача о минимизации функции большого числа переменных .
Принцип оптимальности.
Сформулированный Р.Беллманом принцип оптимальности гласит: отрезок оптимального процесса от любой его точки до конца процесса сам является оптимальным процессом с началом в данной точке.
Принцип оптимальности легко доказывается от противного. Пусть x(t)=x* - некоторая точка оптимальной траектории, то есть состояние системы вдоль оптимального процесса в момент t, 0<t<<N. Рассуждая от противного, предположим, что отрезок этого процесса от момента времени t до момента N не является оптимальным процессом в смысле критерия качества при начальном условии x(t)=x*. Значит, существует допустимое управление и соответствующая ему траектория, для которых критерий Jt принимает наименьшее значение, чем на исходном оптимальном процессе. На ряду с исходным оптимальным процессом x(k), k=0,1,_,N, процесс состоящий из двух участков: исходного процесса x(k) при k= = 0,1,_,t и «улучшенного» процесса при k= =t+1, _,N. Для этого составного процесса критерий J будет иметь меньшее значение, чем для исходного процесса, так как сумма первых t слагаемых для составного процесса остается той же, что и для исходного процесса, а сумма остальных слагаемых, равна Jt , уменьшится по сравнению с исходным процессом. Данное утверждение означает, что исходный процесс не является оптимальным, а это противоречит сделанному предложению.
Таким образом, принцип оптимальности доказан. Столь простое доказательство наводит на мысль о тривиальности этого принципа. Однако это не так: принцип оптимальности является следствием аддитивности и не имеет места с случае неаддитивного критерия.
Метод динамического программирования.
В типичном случае динамическое программирование применяется к задачам оптимизации, которые не решаются простым перебором ( из-за временных ограничений или слишком большого объема необходимой памяти) жадными алгоритмами ( из-за того, что они не делают оптимального результата), а более простой путь решения если и существует, то его нахождение неочевидно. У таких задач может быть много быть много решений и в общем случае это определяет некий показатель ( назовем его качеством решения), и требуется выбрать оптимальное, при котором данный показатель становится либо минимумом либо максимумом ( или еще чем-то:) – в зависимости от условия задачи).
По своему принципу динамическое программирование напоминает метод разделяй и властвуй задача делится на подзадачи, которые либо являются очевидными, либо сводятся к своим подзадачам и т.д. Но есть и некоторые отличия например, таких подзадач относительно немного, что позволяет решит каждую только один раз.
Небольшое количество подзадач, многие из которых приходится решать много раз называется перекрытием подзадач и является характерным признаком динамического программирования.
Вторым характерным признаком излагаемого метода является оптимальность для подзадач. Задача обладает таким свойством, если оптимальное решение задачи содержит оптимальные решения ее подзадач.
Общий рецепт построения алгоритмов по принципу динамического программирования следующий:
1. Хорошо понять условие.
2. Найти такое разбиение задачи на две или более подзадач, чтобы оптимальное решение задачи содержало оптимальное решение всех подзадач, которые в нее входят.
3. Написать рекуррентное соотношение ( если мы разбиваем задачу на подзадачи, значит, можем выразить качество решения задачи либо через ее подзадачи, либо элементарным образом).
4. Вычислить оптимальное решение значение параметра для задачи. Тут возможно два варианта если задачу решаем рекурсивно, значит процедура делит заданную ей задачу на подзадачи ( предварительно выяснив, не является ли задача тривиальной и проверив, не решалась ли она ранее тогда нужно лишь взять уже готовое решение из соответствующего массива) и получив решение ставив флаг, что эта подзадача уже решена. Такое решение называется сверху вниз т.е. берем глобальную задачу, потом решаем только необходимые для нее подзадачи. Если же рекурсия невозможна по техническим или еще какам-нить причинам , то применяется такой подход: решаются сначала элементарные подзадачи, потом только те, которые требуют результатов уже решенных подзадач и т.д. , пока не будет решена общая задача. Такой метод называется решением снизу вверх в большинстве случаев он оказывается быстрее, но менее понятным и простым, хотя есть и исключения.
5. Если необходимо получить не только значения качества оптимального решения, но и найти само решение, то на шаге 3 нужно также запомнить некоторую дополнительную информацию о ходе решения решение каждой подзадачи. Этот шаг иногда еще называют обратным ходом.
Пример1.Перемножение матриц.
Задача о перемножении матриц формулируется следующим образом: дана последовательность из n матриц (А1,А2,Аn) заданных размеров (матрица I имеет размеры pi-1 x pi); требуется найти такую полную расстановку скобок в произведении А1А2А3Аn, чтобы количество умножений было минимально возможным (далее кол-во умножений еще называется стоимостью т.е. это именно тот параметр, который в данной задаче необходимо минимизировать).
Произведение матриц ассоциативно [A(BC)=(AB)C], то расстановка скобок не повлияет на результат, но может существенно повлиять на кол-во умножений. Для начала нужно убедиться в том, что полный перебор всех возможных вариантов не даст эффективного алгоритма: действительно, в каждой тройке матриц можно расставить скобки двумя вариантами, а значит в 3n матриц можно расставить скобки не мене, чем 2n вариантами, т.е. кол-во вариантов (а следовательно и время работы программы, перебирающей все варианты) экспоненциально зависят от n.
Шаг1. найти разбиение задачи на подзадачи.
Обозначим через Ai..j матрицу, являющуюся произведением матриц AiAi+1Aj. Последнее произведение матриц при оптимальной расстановке скобок в произведении А1А2Аn производится между матрицами А1..k и Ak+1…n. Иными словами ,при перемножении, диктуемом такой расстановкой скобок мы сначала вычисляем произведение А1..k, потом Ak+1…n и наконец, вычисляем их произведение. Значит стоимость этой оптимальной расстановки равна стоимости вычисления каждой из этих двух матриц плюс стоимость их перемножения.