Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная
Экономика
Оптимизация
| Харчистов Б.Ф.. Методы оптимизации, 2004 | |
МЕТОД ВЕТВЕЙ И ГРАНИЦ |
|
|
Метод ветвей и границ относится к группе комбинаторных методов дискретного программирования и является одним из наиболее распространенных методов этой группы. Центральную идею комбинаторных методов составляет замена полного перебора допустимого множества X частичным перебором. В случае метода ветвей и границ это осуществляется путем последовательного разбиения допустимого множества на подмножества (ветвления) и вычисления оценок (границ), позволяющих отбрасывать подмножества, заведомо не содержащие решения задачи. При реализации общей схемы метода ветвей и границ для различных задач дискретного программирования необходимо, исходя из специфики этих задач, конкретизировать правила ветвления и вычисления границ. На практическом занятии рассматривается метод ветвей и границ для задачи целочисленного линейного программирования (ЛП) следующего вида: n f (x) = X Cj-xj ^ max , j=1 Xaij-xj- < bt, i = 1, m, j=1 x} > 0, j = 1П, xj - целые, j = 1, n. Допустимое множество Х данной задачи предполагается ограниченным. В данном случае на каждом этапе (шаге) решаются непрерывные задачи ЛП: на предварительном (нулевом) этапе - задача L0; на k-м, k = 1, 2,..., этапе - задачи L2k-1 и L2k. Задача L0 , как и в методе отсечений, представляет собой исходную задачу без учета требования целочисленности; задача Lv, v = 1,2,..., получается в результате добавления к задаче L0 дополнительных ограничений. Верхняя граница (оценка) целевой функции f для задачи Lv, v = 0,1 Д..., определяется следующим образом: f ( x(v)), (v) т где x ' - решение задачи Lv . Если задача Lv не имеет решения, то полагается B,v = . В процессе решения строится дерево задач, в котором v -я, v = 0,1,2,..., вершина соответствует задаче Lv . Обозначим через I множество вершин, из которых возможно ветвление. Для ветвления на k-м, k =1,2,..., этапе выбирается v-я, veI, вершина (задача Lv ), которая имеет максимальную верхнюю оценку E,v. Пусть в решении x(v) некоторая компонента x(v), 1 < r < n, не является целочисленной. Допустимое, т.е. целочисленное, значение xr должно удовлетворять одному из неравенств, представляющих собой необходимые условия целочисленности xr: либо xr < [xrv)], либо xr > [xrv)] +1, где [a] - целая часть действительного числа а. В результате задача Lv разветвляется (разбивается) на две не связанные между собой задачи L2k-1 и L2k. Задача L2k-1 представляет собой задачу Lv с дополнительным ограничением xr < [x^ ], а задача L2k - задачу Lv с дополнительным ограничением xr > [xv)] +1, т.е. L { L Х L \ 4k-1 j x < [x^]; L2k j x> [xf>] +1. Для ускорения процесса решения вводится нижняя граница целевой функции f для целочисленного решения, обозначаемая 0. После решения задачи Lv значение 0v определяется следующим образом: 0v = 0v- , если задача Lv не имеет решения либо x не является целочисленным; max{0v"7, Итак, алгоритм решения целочисленной задачи ЛП методом ветвей и границ заключается в следующем. Решается задача ЛП L0. Если задача L0 не имеет решения, то исходная задача не имеет целочисленного решения и вычисления завершаются. Находится решение x(0) , вычисляется верхняя граница <0 = f (x(0)). Если решение x(0) является целочисленным, то полагается * (0) г* й0 x = x , f = < и вычисления завершаются. Если решение x(0) не является целочисленным, то полагается 00 = , k=1 и осуществляется переход к п. 3. Выбирается для ветвления v-я вершина из I, для которой выполняется условие Выбирается (произвольно) одна из нецелочисленных компонент xv), осуществляется ветвление по переменной xr, составляются задачи L2k-1 и L2k. Решается задача Lj, j = 2k -1, 2k. Если задача Lj не имеет решения, то полагается ВJ = -<, 0J =0J-1 и осуществляется (при j=2k) переход к п. 7. Находится x(J), вычисляется ВJ = f (x(J)). Если решение x( j) является целочисленным, то полагается 0J = max{0J-1,ВJ} и осуществляется (при J = 2k) переход к п. 7. Если решение x(J) не является целочисленным, то полагается 0J = 0J-1 и осуществляется (при j = 2k) переход к п. 7. Просматриваются вершины из I и прекращается ветвление, если выполняется условие В < 02k , i е I. Проверяется условие окончания вычислений I = 0. Если оно выполняется, то полагается f * =02k, x* = x(v), где x(v) определяется из условия f (x(v)) = 02k , и вычисления завершаются. Если условие не выполняется, то полагается k = k +1 и осуществляется переход к п. 3. Пример. Решить методом ветвей и границ следующую целочисленную задачу ЛП: f (x) = 2x1 + 3x2 ^ max , 5 x1 + 7 x2 < 35 , 4x1 + 9x2 < 36, x1 > 0 , x2 > 0 , x1, x2 - целые. Решение. Предварительный (нулевой) этап Записываем задачу L0 (исходная задача без учета требования целочисленности): (1) (2) f (x) = 2x1 + 3x2 ^ max , 5x1 + 7x2 < 35 , 4x1 + 9x2 < 36, x1 > 0, x2 > 0. Этой задаче соответствует нулевая вершина дерева задач (см. ниже рис. 11.6). Решаем графически задачу L0 (рис. 11.1). '1 2 3 4 5 6 7ЧХч9 Рис. 11.1 1 (0) Из рис. 1 1 .1 следует, что задача L0 имеет решение x Точка x(0) является решением системы уравнений (5x1 + 7 x2 = 35 , 4x1 + 9x2 = 36 . Находим x(0) и <^0 : 45x1 + 63x2 = 315 63 12 ^ x, = - = 3Ч: 28x1 + 63 x2 = 252 1 17 17 17 x = 63 5 Х 63 17 9 280 40 Д6 + 7 x2 = 35 ^ 7 x2 = 35 -18 Ч = ^ x2 = - = 2 - 17 17 2 17 17 12 6 x(0) = (3Ч, 2Ч); 17 17 6 8 14 = f (x(0)) = 2 Х 3^ + 3 Х 2 17 17 17 Поскольку x(0) не является целочисленным, то полагаем 0 = -то и выполняем 1-й этап. Первый этап Осуществляем ветвление из нулевой вершины. Выбираем для ветвления нецелочисленную компоненту x20) = 217; осуществляем ветвление по переменной x2 : x2 < 2, x2 > 3 ; составляем задачи L1 и L2 : L 2 А L0, x2 > 3. L0, x 2 < 2; Записываем задачу L1: f (x) = 2x1 + 3x2 ^ max , 5x1 + 7x2 < 35, (1) (2) 4x1 + 9x2 < 36: x1 > 0, 0 < x2 < 2. Этой задаче соответствует первая вершина дерева задач (см. ниже рис. 11.6). Решаем графически задачу L1 (рис. 11.2). Из рис. 11.2 следует, что задача L1 имеет решение x(1).? Точка x(1) является решением системы уравнений 5x1 + 7 x2 = 35 . x 2 = 2 Х Рис. 11.2 f (x) Чi 1 1 N iЧa. '1 2 3 4 5 6 41) 1 (2) Находим x(1) и I1 : 5x1 + 7 Х 2 = 35 ^ 5x1 = 21 ^ х1 = 4-5; 1 xw = (45, 2); 12 = f (x(1)) = 2 Х 4- + 3 Х 2 = 14Х 55 Поскольку x(1) не является целочисленным, то полагаем 01 =00 = . Записываем задачу L2 : f (x) = 2x1 + 3x2 ^ max , 5x1 + 7x2 < 35, (1) 4x1 + 9x2 < 36, x1 > 0, x2 > 3. Этой задаче соответствует вторая вершина дерева задач (см. ниже рис. 11.6). Решаем графически задачу L2 (рис. 11.3). '1 234567X9 (1) Рис. 11.3 (2) Из рис. 11.3 следует, что задача L2 имеет решение x . Точка x(2) является решением системы уравнений Г 4 x1 + 9 x 2 = 36, x2 = 3 Находим x( ) и | : 4 x1 + 9 Х 3 = 36 ^ 4 x1 = 9 ^ x1 = 2-4; 1 xw = (24, 3); 1 1 В2 = f(x(2)) = 2 Х 2- + 3 Х 3 = 13-. 42 Поскольку x(2) не является целочисленным, то полагаем 02 = 01 = -то . Просматриваем вершины из I = {1, 2}.? Поскольку Е1 = 14-j >02 =, то не прекращаем ветвление из 1-й вершины. Таким образом, I = {1, 2}. Поскольку }2 = 13-2 >02 , то не прекращаем ветвление из 2-й вершины. Таким образом, I = {1, 2}. Проверяем условие окончания вычислений. Поскольку IФ 0, то выполняем 2-й этап. Второй этап Выбираем для ветвления 1-ю вершину, поскольку выполняется условие 2 Е1 = 142 = maxЕ . 5 ie! Выбираем нецелочисленную компоненту xj1-* = 4-5; осу-ществляем ветвление по переменной x1: x1 < 4 , x1 > 5 ; составляем задачи L3 и L4: xl < 4; 4 j xl > 5. Записываем задачу L3: f (x) = 2x1 + 3x2 ^ max , 5x1 + 7x2 < 35, (1) 4x1 + 9x2 < 36, (2) 0 < x1 < 4, 0< x2 < 2. Этой задаче соответствует третья вершина дерева задач (см. ниже рис. 11.6). Решаем графически задачу L3 (рис. 11.4). Из рис. 11.4 следует, что задача L3 имеет решение x(3): (3) _ x = (4, 2); В3 = f (x(3)) = 2 Х 4 + 3 Х 2 = 14. Поскольку x(3) является целочисленным, то полагаем 03 = max{02,B3} = max{-TO,14} = 14 . '1 234567X9 (1) Рис. 11.4 Записываем задачу L4 : f (x) = 2x1 + 3x2 ^ max , 5x1 + 7x2 < 35, (1) 4x1 + 9x2 < 36, (2) x1 > 5, 0 < x2 < 2. Этой задаче соответствует четвертая вершина дерева задач (см. ниже рис. 11.6). Решаем графически задачу L4 (рис. 11.5). Из рис. 11.5 следует, что задача L4 имеет решение x(4) . Точка x(4) является решением системы уравнений (5 x1 + 7 x 2 = 35, x1 = 5. : 4 . Находим x(4) и В4 : 5 Х 5 + 7 х2 = 35 ^ 7 х2 = 10 ^ х2 = 1^; 3 xw = (5, 17); '1 2 3 4 5 6 7 Рис. 11.5 ^ ? Е4 = f (x(4)) = 2 Х 5 + 3-13 = 142. 77 Поскольку x(4) не является целочисленным, то полагаем 04 =03 = 14. Просматриваем вершины из I = {2, 3, 4}. Поскольку Е2 = 13-2<04 = 14, то прекращаем ветвление из 2-й вершины. Таким образом, I={3,4}. Поскольку Е3 = 14 = 04, то прекращаем ветвление из 3-й вершины. Таким образом, I = {4}. 2 Поскольку Е4 = 14-7>04 = 14, то не прекращаем ветвление из 4-й вершины. Таким образом, I = {4}. Проверяем условие окончания вычислений. Поскольку I Ф0, то выполняем 3-й этап. На 3-м этапе следует осуществлять ветвление из вершины 4, которой соответствует оптимальное значение f (x(4)) = 14 7. Несмотря на то, что полученное значение f превышает нижнюю границу целевой функции для целочисленного решения 04 = 14, дальнейшее ветвление из вершины 4 не позволяет улучшить нижнюю границу 0, поскольку f (x(4)) -04 < 1 и все коэффициенты целевой функции являются целыми числами. Таким образом, ветвление из вершины 4 в лучшем случае приведет к другому целочисленному решению, для которого f = 14. Если поиск других решений с тем же самым значением f не представляет интереса, то ветвление из вершины 4 осуществлять нецелесообразно и вычисления можно завершить. При этом f * =04 = 14, x* = x(3) = (4, 2) . Ответ: x* = (4, 2), f * = 14. |
|
| << Предыдушая | Следующая >> |
| = К содержанию = | |
Похожие документы: "МЕТОД ВЕТВЕЙ И ГРАНИЦ" |
|
|