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

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.3.1

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

Предмет /

Так как вес одного предмета w, для всех наименований и максимальный вес W принимают целочисленные значения, состояние х, может принимать лишь целочисленные значения.

Этап 3. Точный вес, который может быть загружен на этапе 3 (предмет наименования 3), заранее неизвестен, но он должен принимать одно из значений 0, 1, 4 (так как W = 4 тонны). Состояния х3= 0 и х3= 4 представляют собой крайние случаи, когда предметы третьего наименования совсем не загружаются или загружают самолет полностью. Остальные значения х3 (= 1, 2 или 3) предполагают частичную загрузку самолета предметами третьего наименования. Действительно при этих значениях х3 все оставшиеся емкости самолета могут быть заполнены предметами третьего наименования.

Так как вес w3 одного предмета третьего типа равен 1 тонне, максимальное количество единиц этого типа, которое может быть загружено, равно [4/1] = 4. Это означает, что возможными значениями х3 будут 0, 1, 2, 3 и 4. Решение т3 является допустимым лишь при условии, что w3m3<x3. Следовательно, все недопустимые альтернативы (те, для которых w3m3> х3) исключены. Следующее уравнение является основой для сравнения альтернатив на этапе 3.

/3(х3) = max{l4m3}, max{m3} =


Шаг1. Шаг 2.

Выразим/;(*,) как функциюв виде

/(*,) = max .{nm,+fM{xM)}, / = 1,2,...,и,

m,=0.1.....МЧ1

г, =0.1.....w

где/U ) = 0.

Выразим jcjj как функцию дг,- для гарантии того, что левая часть последнего уравнения является функцией лишь xt. По определению Xj - xUl представляет собой вес, загруженный на этапе /, т.е. хг = WjiTij или xUi - Xj- Wjirii. Следовательно, рекуррентное уравнение приобретает следующий вид.

/;(*,.)= max {rifn.+fM(xi-wimi)}, / = 1,2,..., п.

wi,=0.1.....

г, =0.1.....w



14/Пз

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

т3 = 0

т3 = 1

т3 = 2

т3 = 3

т3 = 4

h(Xi)

Этап 2.

f2{x2) = max{47m, + /3(х, -3m,)}, тах{/и,} =

= 1.

47/772 + Н(хг - З/п2) Оптимальное решение

Xl /772 = 0 пь. = 1 h(x2) m

0 0+0=0 -00

1 0 + 14=14 - 14 0

2 0 + 28 = 28 - 28 0

3 0 + 42 = 42 47 + 0 = 47 47 1

4 0 + 56 = 56 47+ 14 = 61 61 1

Этап 1.

/, (дг,) = max {3 lm, + /,(*,- 2/n,)},

max{m,} =

4 .2.

= 2.

31 m, + f2(xi

-2m,)

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

mi =0

m, = 1 mi = 2

0 + 0 = 0

- -

0 + 14=14

- -

0 + 28 = 28

31+0 = 31 -

0 + 47 = 47

31+14 = 45 -

0 + 61 =61

31 + 28 = 59 62 + 0 = 62

Оптимальное решение определяется теперь следующим образом. Из условия W= 4 следует, что первый этап решения задачи при хг = 4 дает оптимальное решение ml = 2, которое означает, что два предмета первого наименования будут загружены

в самолет. Эта загрузка оставляет хг=* хх-2т\ =4-2x2 = 0. Решение на втором этапе при а:2=0 приводит к оптимальному решению т2 =0, которое, в свою очередь, дает х3 = х2- 3т = 0-3x0 = 0. Далее этап 3 при х3 = 0 приводит к т\ =0.

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



Следовательно, оптимальным решением задачи является т\ = 2, т\ = О и т\ = 0* Соответствующая прибыль равна 62 ООО долларов.

В таблице для первого этапа нам, по существу, необходимо получить оптимальное решение лишь для xt = 4, так как это последний этап, подлежащий рассмотрению. Однако в таблицу включены также вычисления для х, = 0, 1, 2 и 3, которые позво ляют провести анализ чувствительности решения. Например, что произойдет, если максимальная грузоподъемность самолета будет 3 тонны вместо 4? Новое оптимальное решение может быть определено, начиная с х1 = 3 на первом этапе и продолжая так, как мы поступали при я, = 4.

Задача о загрузке является типичным представителем задачи распределения ресурсов, в которой ограниченный ресурс распределяется между конечным числом видов (экономической) деятельности. При этом целью является максимизация соответствующей функции прибыли. В таких моделях определение состояния на каждом этапе будет аналогично приведенному для задачи о загрузке: состоянием на этапе i является суммарное количество ресурса, распределяемого на этапах i, i + 1,п.

Решение задачи о загрузке в Excel. Природа вычислений в динамическом программировании такова, что делает невозможным разработку универсальных программ для решения задач ДП. Возможно, этим объясняется отсутствие на сегодняшний день коммерческих программных продуктов, рассчитанных на решение широкого класса задач ДП.

Здесь мы покажем, как решается в Excel один подкласс задач ДП - задача о загрузке с одним ограничением (файл chlOKnapsacLxls1). На рис. 10.4 показан рабочий лист Excel для решения задачи о загрузке методом обратной прогонки. Рабочий лист разбит на два раздела. В разделе, ограниченном столбцами Q:V, выводятся результаты вычислений. В другом разделе (столбцы А:Р) в его верхней части (строки 3-6) содержатся входные данные для текущего этапа, нижняя часть (строка 7 и ниже) зарезервирована для вывода результатов вычислений по этапам. Отметим, что максимальное возможное число альтернатив т, на этапе i не должно превышать 10 (ячейки D6:N6).

e с

>

О P

Q R-j S

T , U V

Dynamic Prog

lammir

q (Backward) Knapsack Model

Input Data and Step* Calculation*

Ouput Solution Summary

Ilumber of *taae*1№*

Re*, limit, W-

Maximum WAv cannot exceed 10

x 1 m

x 1 m

uirent stage- 1

Are m vatut* correct?

1 Stage

Optimum

r m

Solution

f m

Puc. 10.4. Шаблон Excel для решения задачи о загрузке

На рис. 10.5 показаны этапы вычислений для задачи примера 10.3.1. Вычисления выполняются последовательно по этапам и пользователю необходимо предос-

1 Эта рабочая книга закрыта паролем от изменений, поэтому она не русифицирована. Кроме того, перед ее использованием следует установить в Windows (Панель управленияЯзык и стандарты) региональные установки Английский (США), иначе не все вычисления в этой книге выполняются корректно. Это замечание относится ко всем рабочим книгам и шаблонам Excel, которые упоминаются в оставшейся части книги. - Прим. ред.



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