Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная Экономика Оптимизация
Харчистов Б.Ф.. Методы оптимизации, 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,Ветвление на k-м, k = 1,2,.., этапе из i-й, i е I, вершины следует прекратить, если верхняя граница < i целевой функции для задачи Li не больше известной на данном шаге нижней границы 02k целевой функции для целочисленного решения. Процесс решения завершается, когда отсутствуют вершины, из которых возможно ветвление, т.е. I = 0. При этом оптимальное значение f * =02k, решение x* = x(v), где x(v) определятся из усло- вия f (x(v)) = 02k .
Итак, алгоритм решения целочисленной задачи ЛП методом ветвей и границ заключается в следующем.
Решается задача ЛП L0.
Если задача L0 не имеет решения, то исходная задача не имеет целочисленного решения и вычисления завершаются.
Находится решение x(0) , вычисляется верхняя граница
<0 = f (x(0)).
Если решение x(0) является целочисленным, то полагается
* (0) г* й0
x = x , f = < и вычисления завершаются.
Если решение x(0) не является целочисленным, то полагается 00 = , k=1 и осуществляется переход к п. 3.
Выбирается для ветвления v-я вершина из I, для которой выполняется условие
iel
Выбирается (произвольно) одна из нецелочисленных компонент 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.
<< Предыдушая Следующая >>
= К содержанию =
Похожие документы: "МЕТОД ВЕТВЕЙ И ГРАНИЦ"
  1. 11. МЕТОД ВЕТВЕЙ И ГРАНИЦ
    11. МЕТОД ВЕТВЕЙ И
  2. Задачи
    методом ветвей и границ следующую целочисленную задачу ЛП: f (x) = x1 + 2x2 ^ max , 4x1 + 2x2 < 13, x1 > 0, x2 > 0, x1 , x2 - целые. Решить методом ветвей и границ следующую целочисленную задачу ЛП: f (x) = 2x1 + 2x2 ^ max , 2 x1 + 5 x2 < 16, 6x1 + 5x2 < 30, x1 > 0, x2 > 0, x1 , x2 -
  3. 11. Метод ветвей и границ
    1. Решается задача L0: x (ветвление из 0-й вершины по x2j). Решается задача L1: ' 1, 6Л V4 У x () = Е1 = 121, 01 = ; задача L2 не имеет допустимых 4 задача L3: x(3) = (0, 6), Е3 = 12, 03 = 12; задача L4: x(( решений: 02 =
  4. 3. Постиндустриальные проблемы устойчивого развития
    методических требований. Экономические прогнозы и экологическая экспертиза приобретает возрастаю щее значение в деловых кругах. Они взаимодействуют и в зна чительной мере задают пороговые значения осуществимости нововведений. Речь идет о классификации деловых и финансо вых предпосылок и ограничений, об экспертизе и тенденциях экоразвития индустрии, сферах обращения и потребления, о
  5. 2.1.4. Сочетание методов государственного управления
    метода, исключая при этом остальные. Даже в рамках одного конкретного акта управления субъект управления, опираясь на определенный метод, подкрепляет его другими методами. Иначе говоря, в управлении экономикой все три метода управления могут применяться одновременно, параллельно, но в существенно разных про- 122 порциях. Один из методов, несущий основную нагрузку управления, становится ведущим,
  6. 9.4. ГОСУДАРСТВЕННОЕ РЕГУЛИРОВАНИЕ СЭЗ
    методологический и мето-дологический аспекты. Его суть сводится к созданию необходи мой нормативно-правовой базы функционирования СЭЗ в стра не, а также осуществлению финансово-кредитной, налоговой и иной экономической политики государства, направленной на по вышение эффективности функционирования зон любого типа. Инструментами государственного регулирования СЭЗ являют ся
  7. з 2. ИСПОЛНИТЕЛЬНАЯ ВЛАСТЬ: ЕЕ ПОТЕНЦИАЛ И ТРУДНОСТИ
    методического руководства, координации и контроля. И все же отраслевой принцип управления настойчиво пробивал себе дорогу. С середины 60-х гг. вновь создаются министерства на уровне Союза ССР и республик. Система министерств как отраслевых центров и государственных комитетов как координационно- регулирующих центров была закреплена в 1978 г. в Законе СССР О Совете Министров СССР. Она сохранилась
  8. Централизованная и функциональная децентрализованная публичная администрация в странах Латинской Америки
    методов взаимодействия общества и государства. С 1980-х гг. в большинстве стран Латинской Америки осуществлялся переход от авторитарных методов государственного управления к демократическим. Сама жесткость латиноамериканских военных режимов 70- х и 80-х годов привела гражданскую элиту и широкую общественность этих стран к признанию самоценности демократии и прав человека. Громоздкость
  9. Глава 19. Экономические проблемы России в системе мирохозяйственных связей
    методы извлечения этой прибыли, как пршпо, также далеки от законных (уход от налогов и пр.). Но рано или поздно будут уменьшены налоги, потеплеет инвестиционный климат. Придет время, когда станет выгоднее выйти из тени, платить налоги сполна, проводить все операции законно. И тогда проявятся последствия установившейся традиции невыплат дивидендов, привычки владельцев контрольных пакетов акций
  10. Словарь
    методология в изучении коммерческой деятельности: Учебник/А.И. Харламов, О.Э. Башина, В.Т. Бабурин и др.; Под. ред. А.А. Спирина, О.Э. Башиной. - М.: Финансы и статистика, 1996. Погостинская Н.Н., Погостинский Ю.А. Системный анализ финансовой отчетности. -С.-П.: Изд. Михайлова В.А., 1999 . Практикум по финансовому менеджменту: учебно-деловые ситуации, задачи и решения/ Под ред. Е.С.Стояновой. 2-е