Курсовая с практикой на тему Методы динамического программирования

Содержание:

Введение 3
1 Теоретические аспекты динамического программирования 5
1.1 История возникновения динамического программирования 5
1.2 Общие понятия о динамическом программировании и методе динамического программирования 8
1.3 Схема динамического программирования 9
2 Применение методов динамического программирования при решении задачи 15
2.1 Постановка задачи 15
2.1 Решение задачи методом динамического программирования 16
2.3 Постановка задачи 20
2.4 Решение задачи 21
Заключение 24
Список литературы 25

Введение:

Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей.
Первоначально эта область была основана, как системный анализ и инжиниринг. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.
Слово «программирование» в словосочетании «динамическое программирование» в действительности к «традиционному» программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация».
Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи[10, c. 125].
Актуальность темы курсовой работы состоит в том, что динамическое программирование позволяет решать многошаговые задачи оптимизации, которые встречаются в различных областях человеческой жизнедеятельности.
Целью курсовой работы является получение практических навыков решения задач методом динамического программирования.
В соответствии в поставленной целью курсовая работа имеет следующие задачи:
— дать понятие динамического программирования и метода динамического программирования;
— дать описание схемы метода динамического программирования;
— привести примеры задач из строительной сферы, решаемых с помощью метода динамического программирования.
Объектом исследования является строительная сфера.
Предметом исследования является метод динамического программирования.
Курсовая работа состоит из двух частей – теоретической и практической.
В теоретической части приводятся теоретические аспекты динамического программирования и его метода.
Даны понятия динамического программирования и его метода, описана схема решения задач методом динамического программирования.
Так, под динамическим программированием подразумевают подход, который позволяет находить решение задач оптимизации.
Обозначено место динамического программирования в системе методов экономико-математического моделирования.
Практическая часть курсовой работы посвящена решению задач методом динамического программирования.
Предметной областью решаемых задач является строительная сфера.
В первой задаче производится выбор объектов для инвестиций и суммы инвестиций с целью получения максимальной прибыли.
Используется метод обратной прогонки.
Вторая задача посвящена нахождению оптимального маршрута между пунктами.
Данная задача решается методом прямой прогонки.
Практическая значимость курсовой работы заключена в том, что полученные в результате написания навыки решения задач, могут быть применены в других прикладных ситуациях.

Заключение:

Под динамическим программированием подразумевают подход, который позволяет находить решение задач оптимизации.
Задачи оптимизации формулируются как задачи многошагового оптимального управления некоторой системой. Именно в этом случае, целесообразно применения инструментария динамического программирования к решению задачи оптимизации.
В качестве научного направления, динамическое программирование берет начало в 50-х годах ХХ века. Основоположником данной теории является американский математик Ричард Беллман и его сотрудники.
Основная суть метода динамического программирования заключена в том, что исходная задача посредством некоторых действий может быть сведена к упорядоченности совокупности задач, которые имеют более низкую размерность. Решая задачи маленькой размерности, можно найти решение исходной задачи, используя их взаимосвязь.
В основу метода динамического программирования положен принцип, носящий название принцип оптимальности Беллмана (1953 г.):
Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения.
Оптимальную траекторию можно строить, как от начальное состояния, так и от конечного состояния, воспринимая его, как начальное.
В связи с этим обстоятельством метод динамического программирования условно делится на метод прямой и обратной прогонки.
В курсовой работе были приведены два примере применения метода динамического программирования: выбор объекта для инвестиций и выбор оптимального маршрута. Таким образом, цель курсовой работы достигнута.

Фрагмент текста работы:

1 Теоретические аспекты динамического программирования

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

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