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

Автор работы: Пользователь скрыл имя, 27 Ноября 2012 в 09:14, курсовая работа

Описание работы

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

Содержание работы

С.
Введение 3
1 Теоретическая часть. Модели динамического программирования 4
1.1 Предмет динамического программирования 4
1.2 Постановка задачи динамического программирования 6
1.3 Принцип оптимальности и математическое описание динамического процесса управления 8
1.4 Оптимальное распределение инвестиций 10
1.5 Выбор оптимальной стратегии обновления оборудования 13
2 Расчетная часть 16
Заключение 30
Список использованных источников 31

Файлы: 1 файл

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

— 225.00 Кб (Скачать файл)

                     I7I6: 16 + 161 = 177.

 

15-й шаг. k = 15. Сечение F11, G10, Н9, I8.

Вершина F11: F11Е11: 16 + 161 = 177

                      F11F10: 18 + 169 = 187.

Вершина G10: G10F10: 10 + 169 = 179

                      G10G9: 10 + 164 = 174.

Вершина Н9: Н9G9: 9 + 164 = 173

                      Н9Н8: 12 + 165 = 177.

Вершина I8: I8Н8: 13 + 165 = 178 

                     I8I7: 14 + 169 = 183.

 

16-й шаг. k = 16. Сечение G11, Н10, I9.

Вершина G11: G11F11: 9 + 177 = 186

                      G11G10: 10 + 174 = 184.

Вершина Н10: Н10G10: 10 + 174 = 184

                       Н10Н9: 10 + 173 = 183.

Вершина I9: I9Н9: 11 + 173 = 184 

                     I9I8: 10 + 178 = 188.

 

17-й шаг. k = 17. Сечение  Н11, I10.

Вершина Н11: Н11G11: 10 + 184 = 194

                       Н11Н10: 9 + 183 = 192.

Вершина I10: I10Н10: 9 + 183 = 192 

                     I10I9: 15 + 184 = 199.

 

18-й шаг. k = 18.

Вершина S0: S0Н11: 10 + 192 = 202 

                     S0I10: 13 + 192 = 205.

 

Минимально  возможные суммарные издержки по обслуживанию всех                      18 машин на оптовой базе «Ларес» составляют 202 усл. ед.

II этап. Безусловная оптимизация.

Определяем  оптимальную траекторию на исходном сетевом графе, просматривая результаты всех шагов в обратном порядке, учитывая, что выбор некоторого управления на k-м шаге приводит к тому, что состояние на (k-1)-м шаге становится определенным.

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


 


 


 


 


 


 


 



 

 

 

Рисунок 9 – Оптимальная последовательность операций

Минимальные издержки Fmin соответствуют следующему оптимальному пути на графе:

(S0→ H11 → H10 → H9 → G9 → G8 → F8 → E8 → D8 → C8 → C7→ C6 →   → C → B5 → B4 → B3 → B2 → A1 → S1) и равны:

Fmin = 10 + 9 + 10 + 9 + 12 + 14 + 9 + 11 + 13 + 9 + 11 + 13 + 10 + 12 + 13 + + 13 + 11 + 13   = 202 усл. ед.

 

Таким образом, в соответствии с решением оптимальное  управление процессом разгрузки и загрузки машин товаром состоит в следующем: на первом шаге следует оформить документы по загрузке одной машины, на втором – по разгрузке двух машин, затем по загрузке одной машины; далее обслуживать одну машину по разгрузке товара, четыре машины по загрузке, три машины по разгрузке, одну машину по загрузке; в последнюю очередь оформить документы по разгрузке трех машин, по загрузке одной машины и разгрузить последнюю машину.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

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

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

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

 

 

 

 

                                                                         

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

1 Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – М.: Финансы и статистика, 2001.- 544 с.

2  Ломкова Е. Н., Эпов А. А. Экономико-математические модели управления производством (теоретические аспекты): Учеб. пособие. – Волгоград: ВолгГТУ, 2005. – 67 с.

3 Холод Н. И., Кузнецов А. В., Жихар Я. Н. и др.; под общ. ред. Кузнецова А. В. Экономико-математические методы и модели: Учеб. пособие. –Мн.: БГЭУ, 2000. – 412 с.

4 Шикин Е.  В., Чхартищвили А. Г. Математические  методы и модели в управлении: Учеб. пособие. – 2-е издание, испр. – М.: Дело, 2002. – 440 с.

 

 

 




Информация о работе Динамическое программирование