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

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

х,= 3,75, х2= 1,25, z = 23,75


х1=3,х2= 2, z = 23 Нижняя граница (оптимум)

*! = 4, х2= 0,83, z = 23,33


х, = 4,5, x2=0,z = 22,5

Нет решения


= 4,х2=0, z = 20

Нет решения

Рис. 9.8. Другой путь решения задачи примера 9.2.1

У нас есть три нерассмотренные подзадачи, которые должны быть решены, - ЛП1, ЛПЗ и ЛП4. Предположим, что мы произвольно выбрали первой задачу ЛП4. Эта задача не имеет решения и, следовательно, является прозондированной. В качестве следующей выберем подзадачу ЛПЗ. Ее оптимальным решением является л:, = 4,5, х2 = 0 и 2 = 22,5. Нецелочисленное значение переменной х, (= 4,5) порождает две ветви решений при х, < 4 и х, > 5 и соответствующие им подзадачи ЛП5 и ЛП6. При этом

пространство решений ЛП5 = пространство решений ЛПО + (х, > 4) + (х2 < 0) + + (х, < 4) = пространство решений ЛПО + (х, = 4) + (х2 < 0),

пространство решений ЛП6 = пространство решений ЛПО + (х, > 4) + (х2 < 0) + + (х, > 5) = пространство решений ЛПО + (х, > 5) + (х2 < 0).

Теперь не рассмотрены подзадачи ЛП1, ЛП5 и ЛП6. Подзадача ЛП6 прозондирована, так как не имеет допустимых решений. Подзадача ЛП5 имеет целочисленное решение (х, = 4, х2 = 0, 2 = 20) и, следовательно, порождает нижнюю границу (г = 20) оптимального значения целевой функции задачи ЦЛП. Теперь остается лишь подзадача ЛП1, решение которой также является целочисленным (х, = 3, х2 = 2, 2 = 23). Следовательно, нижнюю границу значений целевой функции полагаем равной 23. Так как все подзадачи прозондированы, оптимальным решением задачи ЦЛП является решение, соответствующее последней нижней границе, а именно х, = 3, х2 = 2 и z = 23.



Последовательность решения подзадач, показанная на рис. 9.8 (ЛПО, ЛП2, ЛП4, ЛПЗ, ЛП6, ЛП5, ЛП1), является наихудшей; тем не менее, она встречается на практике. Этот пример указывает на основную слабость метода ветвей и границ: как выбирать следующую подзадачу для исследования и как выбирать для нее переменную ветвления?

В процессе решения, представленного на рис. 9.7, мы случайно наткнулись на хорошую нижнюю границу значений целевой функции на самой первой подзадаче ЛП1, что позволило прозондировать ЛП2 без детальных исследований и закончить вычисления. По существу, мы завершили вычисления, решив лишь одну подзадачу. В процессе решения, представленном на рис. 9.8, мы были вынуждены исследовать семь подзадач, и лишь тогда завершились вычисления метода ветвей и границ. Хотя имеются эвристические соображения, позволяющие угадать , какая из ветвей может привести к улучшенному решению задачи ЦЛП (см., например, [3]), не существует строгой теории, которая всегда обеспечивала бы надежные результаты.

Теперь сформулируем алгоритм метода ветвей и границ в общем случае. Предположим, что рассматривается задача максимизации. Зададим нижнюю границу оптимального значения целевой функции z задачи ЦЛП равной Положим i = 0.

Шаг 2. (Зондирование и определение границы). Выбираем i-ю подзадачу линейного программирования ЛГО для исследования. Решаем ЛШ и зондируем ее, при этом возможна одна из трех ситуаций.

a) Оптимальное значение целевой функции задачи ЛГО не может улучшить текущей нижней границы.

b) ЛГО приводит к лучшему допустимому целочисленному решению, чем текущая нижняя граница.

c) ЛГО не имеет допустимых решений. Возможны два варианта.

a) Если задача ЛГО прозондирована, нижняя граница изменяется только при условии, что найдено лучшее решение задачи ЦЛП. Если все подзадачи прозондированы, необходимо закончить вычисления: оптимальным решением задачи ЦЛП является то, которое соответствует текущей нижней границе, если такая существует. Иначе положить i = i + 1 и повторить шаг 1.

b) Если задача ЛГО не прозондирована, переходим к шагу 2 для выполнения ветвления.

Шаг 2. Ветвление. Выбираем одну из целочисленных переменных х:, оптимальное значение xf которой в оптимальном решении задачи ЛГО не является

целым числом. Исключаем из пространства допустимых решений область [ху]<Х;<[х]] + 1 (где [у]- наибольшее целое, не превосходящее v) путем

формирования двух подзадач ЛП, которые соответствуют ограничениям

хИ +

Положим i = i + 1 и переходим к шагу 1.



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

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

УПРАЖНЕНИЯ 9.2.1

1. Решите задачу ЦЛП из примера 9.2.1 методом ветвей и границ, начиная с переменной х2 как переменной ветвления. Решите подзадачи с помощью программы TORA, используя опцию MODIFY (Изменить) для задания верхней и нижней границ. Начните с решения подзадачи, включающей ограничение х, ГхЛ .

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

а) Максимизировать z = Зле, + 2х2

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

2х, + 5х2 < 9, 4х, + 2х2 < 9, х х2 > О и целые.

Ь) Максимизировать z = 2х, + Зх2

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

5х, + 7х2<35, 4х, + 9х2 < 36, xv х2>Ои целые.

с) Максимизировать z = х, + х2 при ограничениях

2х, + 5х2< 16, б*, + 5х2 < 27, xv х2 > 0 и целые.

d) Минимизировать z = 5х, + 4х2

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

Зх, + 2х2>5, 2х, + Зх2 > 7, xv х2 > 0 и целые.

е) Максимизировать z = 5х, + 7х2 при ограничениях

2х, +х2< 13, 6х, + 9х2<41, х х2>Оицелые.



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