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

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

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

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

Пример 9.3.2

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

Решение начальной задачи о назначениях (полученное с помощью TORA) следующее:

2 = 15, (х13 = x3l = 1), (хг5 = хи - xi2 = 1), все остальные переменные равны 0.

Это решение порождает два частичных цикла (1-3-1) и (1-5-4-2). Это же решение обозначено как узел 1 дерева подзадач на рис. 9.14. Полученное значение целевой функции 2=15 принимаем в качестве нижней границы длины оптимального цикла, проходящего через все 5 городов.

z = 15 (1-3-1)(2-5-4-2)


z=17 (2-5-2)(1-4-3-1)


z= 16 (1-3-4-2-5-1)

z = 21 (1-4-5-2-3-1)

z=19 (1-4-2-5-3-1)

Рис. 9.14. Дерево подзадач решения задачи коммивояжера методом ветвей и границ



Прямолинейный способ определения верхней границы оптимального цикла заключается в том, чтобы выбрать какой-либо полный цикл и подсчитать его длину. Например, полный цикл 1-2-3-4-5-1 (выбран произвольно) дает общую длину 10 + 5 + 7+ 4+ 3 = 29. (Можно получить лучшее значение верхней границы, если взять другой полный цикл. Помните, что наименьшая верхняя граница - цель поиска методом ветвей и границ.)

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

Чтобы исключить частичные циклы в задаче узла 1, надо разбить эти частичные циклы путем принудительного приравнивания переменных х , задающих эти циклы, нулю. Частичный цикл 1-3-1 можно разбить, если положить х13 = 0 или х31 = О (одновременно только одну переменную). Аналогично частичный цикл 2-5-4-2 можно разбить, если ввести ограничения х2Ь = 0, х54 = 0 или xi2 = 0. Каждое из подобных ограничений порождает отдельную ветвь дерева подзадач (и, конечно, отдельную подзадачу). Важно заметить, что нет необходимости разбивать все имеющиеся частичные циклы - достаточно исключить только один частичный цикл. Причина этого в том, что введение в задачу нового ограничения автоматически влияет на значения всех переменных этой задачи, что создает благоприятные условия для формирования полного цикла. На основании этого аргумента обычно разбивают один частичный цикл, наименьший по количеству составляющих его дуг, поскольку это приводит к меньшему количеству новых ветвей в дереве подзадач.

Выбирая для удаления короткий цикл 1-3-1, получаем на дереве подзадач две ветви, определяемые условиями х13 = 0 и х31 = 0, выходящие из узла 1. Новые задачи о назначениях строятся путем удаления из последней задачи переменной ветвления (т.е. х]3 или х31), что уменьшает размер подзадач. Другой путь построения подзадач (который дает тот же самый результат при решении этих подзадач и который сохраняет их размер) заключается в том, чтобы назначить переменным ветвления значения расстояний, равные бесконечности. Например, в подзадаче с ограничением х13 = 0 расстоянию d13 присваивается значение °°.

Из двух имеющихся подзадач решим сначала задачу с условием х13 = 0 (узел 2 на рис. 9.14) - порядок решения подзадач произвольный. Получаем решение 2=17, которое формирует два частичных цикла (2-5-2) и (1-4-3-1). Эту подзадачу разбиваем на две путем введения дополнительных ограничений х25 = 0 и х52 = 0 так же, как это сделано в задаче узла 1.

Теперь имеется три нерешенные подзадачи, которые соответствуют узлам 3, 4 и 5 на рис. 9.14. Произвольно выбираем для решения подзадачу узлаЗ. В исходных данных для этой подзадачи устанавливаем dl3 = °° и d2b = °°. Ее решение дает 2 = 21 с полным циклом 1-4-5-2-3-1. Поскольку получено решение с полным циклом, то ветвления в узле 3 не будет.

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

Из нерассмотренных подзадач 4 и 5 выбираем для решения подзадачу 4. Для ее решения в данных исходной задачи о назначениях положим dn = °° и d52 = °°. Получаем решение этой подзадачи с 2 = 19 и полным циклом 1-4-2-5-3-1. Это решение предлагает новую верхнюю границу г = 19.



Осталась нерассмотренной только подзадача узла 5. Для ее решения в данных исходной задачи о назначениях положим d31 = °°. Получаем решение с г = 16 и полным циклом 1-3-4-2-5-1, а также новую верхнюю границу г = 16.

Нерассмотренных подзадач не осталось. Оптимальным циклом будет цикл 1-3-4-2-5-1 с длиной в 16 миль.

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

Конечно, существуют эвристические подходы, позволяющие помочь в предсказании последовательности подзадач, ведущей к оптимальному решению наиболее эффективным путем. Например, после того, как определены все ветви (подзадачи), выходящие из некоторого узла дерева подзадач, первой решается та подзадача, у которой исключаемой переменной хц соответствует наибольшее значения расстояния dtj среди рассматриваемых подзадач. Если воспользоваться этим правилом в данном примере, то после определения подзадач узла 1 первой надо решать подзадачу 5, что приведет к оптимальному решению всего за два этапа. (Первый этап - решение подзадачи 5, второй этап - решение подзадачи 2, которое дает худшее значение целевой функции (г = 17), чем существующая на тот момент верхняя граница, равная 16.)

УПРАЖНЕНИЯ 9.3.2

1. Решите задачу примера9.3.2, начав с удаления частичного цикла 2-5-4-2. При прохождении дерева подзадач примените следующие правила.

a) На каждом уровне дерева подзадач исследуйте подзадачи слева направо. Переходите на следующий уровень только после того, как будут рассмотрены все подзадачи текущего уровня.

b) Исследуйте подзадачи вертикально , начиная от нулевого узла и последовательно проходя по ветвям, пока не будут рассмотрены все подзадачи одной последовательности ветвей.

2. Решите методом ветвей и границ задачу из упражнения 9.3.1.1.

3. Решите методом ветвей и границ задачу из упражнения 9.3.1.2.

4. Решите методом ветвей и границ задачу из упражнения 9.3.1.3.

9.3.2. Применение метода отсекающих плоскостей для решения задачи коммивояжера

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



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