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

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.2. Прежде чем представлять эти методы, рассмотрим пример, демонстрирующий универсальность задачи коммивояжера для описания различных практических ситуаций (см. также упражнения 9.3.1).

Пример 9.3.1

Дневной график работы предприятия, производящего краски, включает изготовление партий белой (Б), желтой (Ж), красной (К) и черной (Ч) красок. Так как предприятие использует одно и то же оборудование для изготовления всех четырех типов краски, необходима его надлежащая чистка между изготовлением различных партий краски. Приведенная ниже таблица содержит время чистки оборудования в минутах, если за изготовлением краски, указанной в строке, следует изготовление краски, указанной в столбце. Например, если за белой краской следует желтая, то время чистки равно 10 минут. Поскольку за определенным цветом краски не может следовать такой же цвет, то соответствующее время чистки полагается равным бесконечности. Необходимо определить оптимальную последовательность дневного производства четырех типов краски, которая минимизирует суммарное время чистки оборудования.

Время чистки в мин., если следующий цвет

Текущий цвет

белый

желтый

черный

красный

Белый

Желтый

Черный

Красный

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

Эту задачу можно решить путем полного перебора шести [(4-1)! = 3! = 6] возможных контуров сети. Приведенная ниже таблица показывает, что последовательность узлов Б- Ж->К->Ч->Б определяет оптимальный контур.

Производственный цикл (контур) Суммарное время чистки

Б->Ж->Ч->К- Б 10 + 19 + 25 + 45 = 99

Б- Ж->К->Ч->Б 10 + 18 + 20 + 50 = 98

Б->Ч->Ж->К->Б 17 + 44 + 18 + 45 = 124

Б->Ч->К- Ж->Б 17 + 25 + 40 + 20 = 102

Б->К->Ч- Ж->Б 15 + 20 + 44 + 20 = 99

Б->К->Ж->Ч->Б 15 + 40 + 19 + 50 = 124



Метод полного перебора контуров практически применим лишь для задач малой размерности. Например, сеть с 11 узлами имеет 10! = 3 628 800 контуров. Следовательно, требуется более эффективный подход к решению таких задач.

Определим переменные хц равными 1, если узел ; достигается из узла г, и 0 в противном случае. Необходимым условием для контура (цикла) является то, что узел I связывается лишь с одним узлом и узел j достигается лишь из одного узла. Считая М достаточно большим положительным числом, мы можем записать задачу предприятия, производящего краски, следующим образом.

Минимизировать г = МхББ + 10хБЖ + ПхБЧ + 15x£/f + 20хЖБ + Мхжж + 19хжч + )хЧБ + 44д

при ограничениях

+ 18хжк + 50хЧБ + 44хчж + Мхчч + 25хчк + 4ЬхКБ + 40хкж + 20хкч + Мхкк

ХББ ХБЖ ХБЧ ХБК ~~ ХЖБ ХЖЖ ХЖЧ ХЖК ~ >

хЧБ + хчж + хчч + хчк - 1,

ХКБ ХКЖ ХКЧ ХКК ~ ХББ ХЖБ ХЧБ ХКБ = 1

х 4- х 4- х 4- X ~ 1 хБЧ -Ь хжч + xt/1J + хкч - 1,

ВЙ ХЖК ХЧК~~ ХКК ~ 1

хц = 0 или 1 для всех i и

решение должно быть контуром (полным циклом).

Использование константы М в целевой функции гарантирует, что производство краски одного цвета не будет повторяться подряд.

УПРАЖНЕНИЯ 9.3.1

1. Менеджер проектов имеет 10 сотрудников, которые работают над шестью проектами, причем каждый работает одновременно над несколькими проектами, как показано в следующей таблице.

Сотрудники




Менеджер должен встретиться с каждым из 10 сотрудников один раз в неделю для обсуждения их проблем. Беседа с каждым из них длится примерно 20 минут, т.е. на разговоры со всеми сотрудниками уходит 3 часа 20 минут. Предлагается проводить встречи менеджера с группами сотрудников, работающих над одним и тем же проектом, чтобы уменьшить суммарное время, которое тратится на совещания. Менеджер планирует составить график обсуждения проектов таким образом, чтобы уменьшить движение в офисе, т.е. сократить число сотрудников, входящих и выходящих из комнаты для совещаний. В какой последовательности необходимо рассматривать проекты?

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

Необходимо составить маршрут движения продавца книг, минимизирующий суммарное расстояние. Сформулируйте задачу в виде задачи о назначениях ЦЛП.

3. Пусть в предыдущем упражнении города Б, В, Г и Д обозначены через 1,2,3 и 4, а город А разделен на два, которые обозначены через 0 и 5. Пусть маршрут продавца книг начинается в городе 0, проходит (в некотором порядке) через города 1, 2, 3 и 4 и заканчивается в городе 5. Определим переменную vt для города i (i = 0, 1, 5), которая удовлетворяет условиям 0 < и( < 5. Пусть xtj = 1, если в маршруте город j следует за городом г, и 0 в противном случае. Покажите, что ограничения

у,-уу + 5х,.<4, г = 0,1.....4, j = 1, 2, 5,

гарантируют исключение вчсех неполных маршрутов в решении задачи.

9.3.1. Применение метода ветвей и границ для решения задачи коммивояжера

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



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