ВВЕДЕНИЕ 3
ГЛАВА 1 ОБЩИЕ ПОДХОДЫ ИСПОЛЬЗОВАНИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ПРИКЛАДНЫХ ЗАДАЧАХ 5
1.1 Обоснование необходимости методов динамического
программирования в прикладных задачах 5
1.2 Достаточность методов динамического программирования в
прикладных задачах 8
ГЛАВА 2 КОНКРЕТНЫЕ РЕАЛИЗАЦИИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ В ПРИКЛАДНЫХ ЗАДАЧАХ 15
2.1 Методы динамического программирования в непрерывном случае 15
2.2 Методы динамического программирования в дискретном случае 28
2.2.1 Математическая модель задачи о рюкзаке 28
2.2.2 Методы решения задачи о рюкзаке 30
ГЛАВА 3 ПРОГРАММНАЯ РЕАЛИЗАЦИЯ 38
3.1 Решение задачи о рюкзаке 38
3.2 Описание интерфейса 38
ЗАКЛЮЧЕНИЕ 45
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 46
ПРИЛОЖЕНИЕ
Динамическое программирование в математике и теории вычислительных систем — метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами, который намного эффективнее, чем решение «в лоб». Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил это определение до современного.
Впервые сформулированная американским математиком Д.Б. Данцигом задача о рюкзаке (ранце) (англ. Knapsack problem) - одна из NP-полных задач комбинаторной оптимизации, популярность которой вызвана большим количеством её приложений, поскольку многие из реально возникающих задач описываются в рамках данной модели. Основные сферы применения находятся в областях планирования и управления производственными и транспортными системами. Название своё получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Непосредственно термин «рюкзак» может быть интерпретирован достаточно широко. Данная задача и её варианты широко используются для моделирования большого числа практических задач.
Актуальность работы заключается в том, что мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.
1) Разбиение задачи на подзадачи меньшего размера.
2) Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
3) Использование полученного решения подзадач для
конструирования решения исходной задачи.
Объект исследования - математическая модель задачи о рюкзаке.
Предмет исследования - оптимизация задачи о рюкзаке методом динамического программирования.
Целью выпускной квалификационной работы является использование метода динамического программирования для решения задачи о рюкзаке.
Задачи работы:
1) Изучение общих подходов динамического программирования;
2) Создание алгоритма для решения задачи о рюкзаке;
3) Программная реализация задачи о рюкзаке.
Выпускная квалификационная работа состоит из введения, трёх глав, заключения, списка используемых источников.
В главе 1 рассматриваются общие подходы использования динамического программирования в прикладных задачах. В главе 2 приводятся конкретные реализации динамического программирования в прикладных задачах. В главе 3 разрабатываются алгоритм и интерфейс программы. В заключении представлены результаты и выводы о выполненной работе.
В выпускной квалификационной работе представлены общие подходы необходимости использования динамического программирования в некоторых прикладных задачах.
В настоящее время разработаны современные методы и алгоритмы решения задач дискретной оптимизации. Применение пакетов программ возможно без знания алгоритмов решения задач, однако знание алгоритмов и технологий их реализации позволяет более эффективно использовать прикладные программы. В этих программах используются алгоритмы, связанные с перебором большого числа вариантов, комбинаторные алгоритмы.
В работе подробно рассмотрены реализации динамического программирования в дискретном случае, а так же упомянуты реализации динамического программирования в непрерывном случае. Работа посвящена задаче о рюкзаке, методам её решения. Из них рассмотрены: метод ветвей и границ и метод динамического программирования. Программная реализация осуществлена для метода динамического программирования.
Задача о рюкзаке является довольно удачным примером демонстрации комбинаторных методов поиска оптимального решения метода динамического программирования.
Предложенная модификация алгоритма Беллмана-Форда,
использованная в программе для решения задачи о рюкзаке, в отличии от существующих программ, позволяет проводить расчеты в несколько раз быстрее, исключая ненужные операции.
