Промышленный лизинг Промышленный лизинг  Методички 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 [ 142 ] 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292

10.2. Рекуррентные алгоритмы прямой и обратной прогонки

Алгоритмы прямой и обратной прогонки приводят к одному и тому же решению. Несмотря на то что алгоритм прямой прогонки представляется более логичным, в специальной литературе, посвященной динамическому программированию, неизменно используется алгоритм обратной прогонки. Причина этого в том, что в общем случае алгоритм обратной прогонки может быть более эффективным с вычислительной точки зрения. Продемонстрируем использование алгоритма обратной прогонки на примере 10.1.1. Мы также представим вычисления динамического программирования в компактной табличной форме.

Пример 10.2.1

Рекуррентное уравнение для алгоритма обратной прогонки в примере 10.1.1 имеет вид /(*,.)= min {d(x xM) + fM{xM)}, i = l,2,3.

вес допустимые )-маршругы

где /4(х4) = 0 для xt = 7. Соответствующей последовательностью вычислений будет

и-* и-* Л-

Этап 3. Поскольку узел 7 (xt = 7) связан с узлами 5 и 6 (х3 = 5 и 6) только одним маршрутом, альтернативы для выбора отсутствуют, а результаты третьего этапа можно подытожить следующим образом.

а\Х}, х4) Оптимальное решение

Xi х4 = 7 h(Xi) xt

5 9 9 7

6 6 6 7

Этап 2. Так как маршрута (2, 6) не существует, соответствующая альтернатива не рассматривается. Используя значения f3(x3), полученные на третьем этапе, мы можем сравнить допустимые альтернативные решения, как показано в следующей таблице.

01*2, Хз) + Н(хъ)

Оптимальное решение

Хз = 5

х3 = 6

*) х\

12 + 9 = 21

21 5

8 + 9= 17

9 + 6 = 15

15 6

7 + 9=16

13 + 6 = 19

16 5

Оптимальное решение второго этапа означает следующее. Если вы находитесь в узле (городе) 2 или 4, кратчайший путь к узлу 7 проходит через узел 5, а если в узле

3 - через узел 6.

Этап 1. Из узла 1 начинаются три альтернативных маршрута: (1, 2), (1, 3) и (1, 4). Используя значения f2(x2), полученные на втором этапе, вычисляем данные следующей таблицы.

Оптимальное решение на первом этапе показывает, что кратчайший путь проходит через город 4. Далее из оптимального решения на втором этапе следует, что из города

4 необходимо двигаться в город 5. Наконец, из оптимального решения на третьем этапе следует, что город 5 связан с городом 7. Следовательно, полным маршрутом, имеющим кратчайшую длину, является 1-> 4-> 5-> 7, и его длина равна 21 миле.



а\хи x2) + f2(x2)

Оптимальное решение

х2 = 2

х2 = 3 х2 = Л

M*l) х.

7 + 21 = 28

8 + 15 = 23 5 + 16 = 21

21 4

УПРАЖНЕНИЯ 10.2

1. Для задачи из упражнения 10.1.1 получите рекуррентное соотношение обратной прогонки и используйте его для получения оптимального решения.

2. Для задачи из упражнения 10.1.2 получите рекуррентное соотношение обратной прогонки и используйте его для получения оптимального решения.

3. Определите кратчайший маршрут между городами 1 и 7 на сети дорог, представленной на рис. 10.3. Определите этапы и состояния системы с помощью алгоритма обратной прогонки, а затем решите задачу.


Рис. 10.3. Сеть для упражнения 3

10.3. ПРИЛОЖЕНИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

В данном разделе рассмотрено четыре примера, каждый из которых выбран для демонстрации методов динамического программирования. При рассмотрении каждого примера особое внимание обратите на три основных элемента моделей динамического программирования.

1. Определение этапов.

2. Определение на каждом этапе вариантов решения (альтернатив).

3. Определение состояний на каждом этапе.

Из перечисленных выше элементов понятие состояния, как правило, представляется весьма сложным для восприятия. Рассмотренные в этом разделе приложения последовательно показывают, что определение состояния меняется в зависимости от моделируемой ситуации. При рассмотрении каждого приложения полезно ответить на следующие вопросы.

1. Какие соотношения связывают этапы вместе?

2. Какая информация необходима для того, чтобы получить допустимые решения на текущем этапе без повторной проверки решений, принятых на предыдущих этапах?



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

10.3.1. Задача о загрузке

Задача о загрузке - это задача о рациональной загрузке судна (самолета, автомашины и т.п.), которое имеет ограничения по объему или грузоподъемности. Каждый помещенный на судно груз приносит определенную прибыль. Задача состоит в определении загрузки судна такими грузами, которые приносят наибольшую суммарную прибыль.

Перед тем как представить соотношения динамического программирования, заметим, что рассматриваемая здесь задача известна также как задача о снаряжении, где пилот реактивного самолета должен определить наиболее ценные (необходимые) предметы, которые следует взять на борт самолета, или как задача о рюкзаке, в которой солдат (или турист) должен определить наиболее ценные предметы, подлежащие загрузке в ранец (рюкзак). Кажется, что три упомянутых названия для одной и той же задачи были выбраны для того, чтобы гарантировать равное представительство военно-морского флота, воздушных сил и армии!

Рекуррентное уравнение процедуры обратной прогонки выводится для общей задачи загрузки судна грузоподъемностью W предметов (грузов) п наименований. Пусть т, - количество предметов i-го наименования, подлежащих загрузке, г,- прибыль, которую приносит один загруженный предмет /-го наименования, w,- вес одного предмета 1-го наименования. Общая задача имеет вид следующей целочисленной задачи линейного программирования.

Максимизировать z = гхтх + г2т2+ ... + гпт

при условии,что

иуи,+ w2m2 + ... + w m < W, ть т2,т >0 и целые.

Три элемента модели динамического программирования определяется следующим образом.

1. Этап i ставится в соответствие предмету /-го наименования, i = 1,2,п.

2. Варианты решения на этапе i описываются количеством т, предметов /-го наименования, подлежащих загрузке. Соответствующая прибыль равна гр\,. Значение т,- заключено в пределах от 0 до [W/wt], где [W/wJ - целая часть числа W/w,.

3. Состояние х, на этапе i выражает суммарный вес предметов, решения о погрузке которых приняты на этапах /, i + 1,п. Это определение отражает тот факт, что ограничение по весу является единственным, которое связывает п этапов вместе.

Пусть f,(x)- максимальная суммарная прибыль от этапов /, /+ 1, я при заданном состоянии Xj. Проще всего рекуррентное уравнение определяется с помощью следующей двухшаговой процедуры.



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 [ 142 ] 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292