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

Федеральное Государственное  Образовательное  Учреждение

Среднего  профессионального  образования

Краснодарский гуманитарно-технологический  колледж 
 
 
 
 
 
 

Курсовая  работа по дисциплине «Математические  методы»

На тему: «Динамическое программирование» 
 
 
 
 
 
 

Выполнил:

студент 4го курса гр.22-03

Мироненко Роман

Проверила:

Тутынина  Н.И. 
 

Краснодар – 2010г.

Содержание

1. Введение
2. История
3. Идея динамического программирования
4. Общая структура динамического программирования
5. Задача динамического программирования
6. Пример задачи динамического программирования
7. Задача о загрузке

• Общие сведения
• Рекуррентные соотношения для процедур прямой и обратной прогонки
• Решение задачи о загрузке
• Анализ чувствительности решения

8. Заключение
9. Список используемой литературы

 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ 

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

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

История

     Словосочетание  динамическое программирование впервые  было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение до современного. Первоначально эта область была основана, как системный анализ и инжиниринг, которая была признана IEEE (Институт инженеров по электротехнике и электронике ). Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

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

Идея  динамического программирования

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

1. Разбиение задачи на подзадачи меньшего размера.
2. Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
3. Использование полученного решения подзадач для конструирования решения исходной задачи.

      Подзадачи решаются делением их на подзадачи  ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

     Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи, F₃ = F₂ + F₁ и F₄ = F₃ + F₂ — даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали F₂ дважды. Если продолжать дальше и посчитать F₅, то F₂ посчитается ещё два раза, так как для вычисления F₅ будут нужны опять F₃ и F₄. Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решение для задач, которые он уже решал.

     Чтобы избежать такого хода событий мы будем  сохранять решения подзадач, которые  мы уже решали, и когда нам снова  потребуется решение подзадачи, мы вместо того, чтобы вычислять  его заново, просто достанем его  из памяти. Этот подход называется кэширование. Можно проделывать и дальнейшие оптимизации — например, если мы точно уверены, что решение подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее.

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

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

Динамическое  программирование обычно придерживается двух подходов к решению задач:

• нисходящее динамическое программирование: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.
• восходящее динамическое программирование: все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего программирования в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить, решение каких подзадач нам потребуется в дальнейшем.

       Языки программирования могут запоминать результат вызова функции с определенным набором аргументов, чтобы ускорить «вычисление по имени». В некоторых  языках такая возможность встроена (например, Scheme, Common Lisp, Perl), а в некоторых требует дополнительных расширений (C++). Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций, и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах. Обычное динамическое программирование является частным случаем несериального динамического программирования, когда граф взаимосвязей переменных — просто путь. НСДП, являясь естественным и общим методом для учета структуры задачи оптимизации, рассматривает множество ограничений и/или целевую функцию как рекурсивно вычислимую функцию. Это позволяет находить решение поэтапно, на каждом из этапов используя информацию, полученную на предыдущих этапах, причём эффективность этого алгоритма прямо зависит от структуры графа взаимосвязей переменных. Если этот граф достаточно разрежен, то объём вычислений на каждом этапе может сохраняться в разумных пределах. Одним из основных свойств задач, решаемых с помощью динамического программирования, является аддитивность. Неаддитивные задачи решаются другими методами.  

Общая структура динамического  программирования

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

     Характерной особенностью динамического программирования является последовательное исследование переменных. Главное заключается  в том, что создается такая  вычислительная схема, когда предпочтительнее большое количество задач с малым  числом переменных, а не одна задача с множеством переменных. В результате процесс вычисления представляется не таким объемным. Но следует отметить, что для этого необходимо соблюдение двух условий:

1. когда критерий оптимальности аддитивен или когда оптимальные решения отдельных шагов создают общее оптимальное решение;
2. когда будущие результаты не предполагают использование предыстории того положения системы, при котором принимается решение.

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

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

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

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

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

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

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