Основы динамического программирования
Автор: elfenok.89 • Декабрь 21, 2018 • Дипломная работа • 18,268 Слов (74 Страниц) • 569 Просмотры
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение высшего профессионального образования «Ульяновский государственный педагогический
университет имени И.Н.Ульянова»
КАФЕДРА АЛГЕБРЫ И ГЕОМЕТРИИ
Квалификационная работа
Основы динамического программирования
студента 5 курса
физико-математического факультета
Гочиевой Эльвиры
Гурбанмагамаевны
Научный руководитель:
Глухова Наталья Владимировна
Ульяновск
2010
СОДЕРЖАНИЕ
Введение…………………………………………………………............3
Глава 1.Общая характеристика методов динамического программирования
§1.1. Краткая историческая справка……………………………………………..4
§1.2. Постановка задач оптимизации…………………………………………….4
§1.3. Понятие "динамическое программирование"…………………………..…8
1.3.1. Понятия динамическое программирование "сверху вниз" и "снизу вверх". ……………………………………………………………………..10
§1.4. Этапы построения алгоритма решения задач методом динамического программирования……………………………………………………………….12
§1.5. Случаи, когда применимо динамическое программирование……..…...12
§1.6. Задача об инвестировании………………………………………………...13
§1.7. Задача о нахождение кратчайшего пути…...………………………….…18
§1.8.Задача о замене оборудования…………………………………………….20
Глава 2. Модели управления запасами……………………………...………...27
§2.1 Постановка задачи. Качественное описание……………………………27
§2.2 Математическая постановка задачи………………………………………27
§2.3. Применение метода динамического программирования к задаче оптимального управления запасами……………………………………………28
§2.4. Алгоритм решения задачи………………………...………………………29
Глава 3. Целочисленное динамическое программирование……..……..……30
§3.1. Графический метод решения……………………………………………30
§3.2. Метод Гомори…………………………………….………………………32
§3.3. Задача о загрузке корабля …..……………………………………………35
Глава 4. Стохастическое программирование…………………………………38
Глава 5.Динамическое программирование для марковских процессов…….42
§4.1. Свойства марковских систем. Функциональное уравнение Беллмана...42
§4.2. Метод последовательных приближений…………………………………45
Приложение…………………………………………………………………….50
Список литературы.................................................................................63
Введение
В наше время наука уделяет все большее внимание вопросам организации и управления, что приводит к необходимости анализа сложных целенаправленных процессов под углом зрения их структуры и организации.
Такие задачи чаще всего решаются с помощью динамического программирования.
Динамическое программирование представляет собой математический аппарат, разработанный для эффективного решения некоторого класса задач математического программирования. Этот класс характеризуется возможностью естественного (а иногда и искусственного) разбиения всей операции на ряд взаимосвязанных этапов. Термин "динамическое" в названии метода возник, видимо, потому что этапы предполагаются разделенными во времени. Однако этапами могут быть элементы операции, никак не связанные друг с другом показателем времени. Тем не менее, метод решения подобных многоэтапных задач применяется один и тот же, и его название стало общепринятым, хотя в некоторых источниках его называют многоэтапным программированием. Модели динамического программирования могут применяться, например, при разработке правил управления запасами, устанавливающих момент пополнения запасов и размер пополняющего заказа, при разработке принципов календарного планирования производства, при распределении дефицитных капиталовложений между возможными новыми направлениями их использования, при составлении календарных планов текущего и капитального ремонта сложного оборудования и его замены и т.д.
...