Автор работы: Пользователь скрыл имя, 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
Рисунок 3 – Сетевая модель операции, шаг 1
2-й шаг. k = 2. Второй шаг оптимизации задается сечением по вершинам А2, В2, C1. Из состояний А2 и C1 возможен единственный переход в вершины А1 и B1 соответственно, поэтому в вершинах А2 и C1 записываем суммарные издержки 29 и 28 на первых двух шагах перехода в конечное состояние S1.
Из вершины В2 возможны два варианта перехода: в вершину А1 или вершину B1. При переходе В2 → А1 сумма издержек составляет 11 + 13 = 24, на переходе В2 → В1 сумма составляет 15 + 10 = 25. Из двух вариантов суммарных издержек выбираем наименьшую (24) и обозначаем стрелкой условно оптимальный переход В2 → А1, как показано на рис. 4.
Рисунок 4 – Сетевая модель операции, шаг 2
3-й шаг. k = 3. На третьем шаге сечение проходит через вершины А3, В3, С2, D1. Из вершин А3 и D1 возможен единственный переход в вершины А2 и С1 соответственно. Суммарные издержки для состояния D1 равны 28 + 19 = 47; для состояния А3: 29 + 20 = 49. Из вершины В3 возможны два варианта перехода: в вершину А2 издержки равны 29 + 9 = 38; в вершину В2 – 13 + 24 = 37.
Для вершины С2 возможен переход в вершину В2 (21 + 24 = 45) и в вершину С1 (18 + 28 = 46). Выбираем для вершин В3 и С2 наименьшие суммарные издержки и обозначаем стрелкой условно оптимальный переход, как показано на рис. 5.
Рисунок 5 – Сетевая модель операции, шаг 3
4-й шаг. k = 4. Четвертый шаг оптимизации задается сечением по вершинам А4, В4, C3, D2, Е1. Из состояний А4 и Е1 возможен единственный переход в вершины А3 и D1 соответственно, поэтому в вершинах А4 и Е1 записываем суммарные издержки:
А4А3: 18 + 49 = 67
Е1D1: 18 + 47 = 65.
Вершина В4: В4А3: 10 + 49 =59
В4В3: 13 + 37 = 50.
Вершина С3: С3В3: 20 + 37 =57
С3С2: 21 + 45 = 66.
Вершина D2: D2С2: 19 + 45 =64
D2D1: 11 + 47 = 58.
Рисунок 6 – Сетевая модель операции, шаг 4
5-й шаг. k = 5. На пятом шаге сечение проходит через вершины А5, В5, С4, D3, Е2, F1. Из вершин А5 и F1 возможен единственный переход в вершины А4 и Е1 соответственно:
А5А4: 15 + 67 = 82
F1Е1: 16 + 65 = 81.
Вершина В5: В5А4: 13 + 67 =80
В5В4: 12 + 50 = 62.
Вершина С4: С4В4: 18 + 50 = 68
С4С3: 12 + 57 = 69.
Вершина D3: D3С3: 18 + 57 = 75
D3D2: 11 + 58 = 69.
Вершина Е2: Е2D2: 16 + 58 = 74
Е2Е1: 15 + 65 = 80.
Рисунок 7 – Сетевая модель операции, шаг 5
6-й шаг. k = 6. Шестой шаг оптимизации задается сечением по вершинам А6, В6, C5, D4, Е3, F2, G1. Из состояний А6 и G1 возможен единственный переход в вершины А5 и F1 соответственно, поэтому в вершинах А6 и G1 записываем суммарные издержки:
А6А5: 13 + 82 = 95
G1F1: 10 + 81 = 91.
Вершина В6: В6А5: 14 + 82 =96
В6В5: 15 + 62 = 77.
Вершина С5: С5В5: 10 + 62 = 72
С5С4: 12 + 68 = 80.
Вершина D4: D4С4: 16 + 68 = 84
D4D3: 12 + 69 = 81.
Вершина Е3: Е3D3: 15 + 69 = 84
Е3Е2: 14 + 74 = 88.
Вершина F2: F2Е2: 15 + 74 = 89
F2F1: 12 + 81 = 93.
Рисунок 8 – Сетевая модель операции, шаг 6
7-й шаг. k = 7. Сечение А7, В7, C6, D5, Е4, F3, G2, Н1.
Вершина А7: А7А6: 18 + 95 = 113
Вершина Н1: Н1G1: 11 + 91 = 102
Вершина В7: В7А6: 15 + 95 = 110
В7В6: 18 + 77 = 95.
Вершина С6: С6В6: 9 + 77 = 86
С6С5: 13 + 72 = 85.
Вершина D5: D5С5: 15 + 72 = 87
D5D4: 10 + 81 = 91.
Вершина Е4: Е4D4: 15 + 81 = 96
Е4Е3: 14 + 84 = 98.
Вершина F3: F3Е3: 16 + 84 = 100
F3F2: 10 + 89 = 99.
Вершина G2: G2F2: 14 + 89 = 103
G2G1: 11 + 91 = 102.
8-й шаг. k = 8. Сечение А8, В8, C7, D6, Е5, F4, G3, Н2, I1.
Вершина А8: А8А7: 16 + 113 = 129
Вершина I1: I1Н1: 12 + 102 = 114
Вершина В8: В8А7: 14 + 113 = 127
В8В7: 20 + 95 = 115.
Вершина С7: С7В7: 15 + 95 = 110
С7С6: 11 + 85 = 96.
Вершина D6: D6С6: 13 + 85 = 98
D6D5: 13 + 87 = 100.
Вершина Е5: Е5D5: 13 + 87 = 100
Е5Е4: 10 + 96 = 106.
Вершина F4: F4Е4: 14 + 96 = 110
F4F3: 18 + 99 = 117.
Вершина G3: G3F3: 12 + 99 = 111
G3G2: 18 + 102 = 120.
Вершина Н2: Н2G2: 17 + 102 = 119
Н2Н1: 12 + 102 = 114.
9-й шаг. k = 9. Сечение А9, В9, C8, D7, Е6, F5, G4, Н3, I2.
Вершина А9: А9А8: 10 + 129 = 139
Вершина В9: В9А8: 13 + 129 = 142
В9В8: 10 + 115 = 125.
Вершина С8: С8В8: 16 + 115 = 131
С8С7: 9 + 96 = 105.
Вершина D7: D7С7: 14 + 96 = 110
D7D6: 14 + 98 = 112.
Вершина Е6: Е6D6: 15 + 98 = 113
Е6Е5: 15 + 100 = 115.
Вершина F5: F5Е5: 12 + 100 = 112
F5F4: 16 + 110 = 126.
Вершина G4: G4F4: 19 + 110 = 129
G4G3: 9 + 111 = 120.
Вершина Н3: Н3G3: 16 + 111 = 127
Н3Н2: 10 + 114 = 124.
Вершина I2: I2Н2: 11 + 114 = 125
I2I1: 8 + 114 = 122.
10-й шаг. k = 10. Сечение А10, В10, C9, D8, Е7, F6, G5, Н4, I3.
Вершина А10: А10А9: 14 + 139 = 153
Вершина В10: В10А9: 12 + 139 = 151
В10В9: 10 + 125 = 135.
Вершина С9: С9В9: 15 + 125 = 140
С9С8: 18 + 105 = 123.
Вершина D8: D8С8: 13 + 105 = 118
D8D7: 15 + 110 = 125.
Вершина Е7: Е7D7: 14 + 110 = 124
Е7Е6: 13 + 113 = 126.
Вершина F6: F6Е6: 12 + 113 = 125
F6F5: 19 + 112 = 131.
Вершина G5: G5F5: 13 + 112 = 125
G5G4: 11 + 120 = 131.
Вершина Н4: Н4G4: 16 + 120 = 136
Н4Н3: 15 + 124 = 139.
Вершина I3: I3Н3: 11 + 124 = 135
I3I2: 15 + 122 = 137.
11-й шаг. k = 11. Сечение В11, C10, D9, Е8, F7, G6, Н5, I4.
Вершина В11: В11А10: 10 + 153 = 163
В11В10: 9 + 135 = 144.
Вершина С10: С10В10: 10 + 135 = 145
С10С9: 10 + 123 = 133.
Вершина D9: D9С9: 13 + 123 = 136
D9D8: 14 + 118 = 132.
Вершина Е8: Е8D8: 11 + 118 = 129
Е8Е7: 14 + 124 = 138.
Вершина F7: F7Е7: 10 + 124 = 134
F7F6: 18 + 125 = 143.
Вершина G6: G6F6: 11 + 125 = 136
G6G5: 18 + 125 = 143.
Вершина Н5: Н5G5: 15 + 125 = 140
Н5Н4: 19 + 136 = 155.
Вершина I4: I4Н4: 16 + 136 = 152
I4I3: 14 + 135 = 149.
12-й шаг. k = 12. Сечение C11, D10, Е9, F8, G7, Н6, I5.
Вершина С11: С11В11: 11 + 144 = 155
С11С10: 8 + 133 = 141.
Вершина D10: D10С10: 15 + 133 = 148
D10D9: 13 + 132 = 145.
Вершина Е9: Е9D9: 15 + 132 = 147
Е9Е8: 14 + 124 = 138.
Вершина F8: F8Е8: 9 + 129 = 141
F8F7: 21 + 134 = 155.
Вершина G7: G7F7: 12 + 134 = 146
G7G6: 13 + 136 = 149.
Вершина Н6: Н6G6: 15 + 136 = 151
Н6Н5: 16 + 140 = 156.
Вершина I5: I5Н5: 11 + 140 = 151
I5I4: 9 + 149 = 158.
13-й шаг. k = 13. Сечение D11, Е10, F9, G8, Н7, I6.
Вершина D11: D11С11: 11 + 141 = 152
D11D10: 12 + 145 = 157.
Вершина Е10: Е10D10: 16 + 145 = 161
Е10Е9: 13 + 141 = 154.
Вершина F9: F9Е9: 11 + 141 = 152
F9F8: 20 + 138 = 158.
Вершина G8: G8F8: 14 + 138 = 152
G8G7: 12 + 146 = 158.
Вершина Н7: Н7G7: 14 + 146 = 160
Н7Н6: 13 + 151 = 164.
Вершина I6: I6Н6: 10 + 151 = 161
I6I5: 17 + 151 = 168.
14-й шаг. k = 14. Сечение Е11, F10, G9, Н8, I7.
Вершина Е11: Е11D11: 9 + 152 = 161
Е11Е10: 11 + 154 = 165.
Вершина F10: F10Е10: 15 + 154 = 169
F10F9: 19 + 152 = 171.
Вершина G9: G9F9: 13 + 152 = 165
G9G8: 12 + 152 = 164.
Вершина Н8: Н8G8: 13 + 152 = 165
Н8Н7: 15 + 160 = 175.
Вершина I7: I7Н7: 9 + 160 = 169