Метод ветвей и границ

2. Метод ветвей и границ

 

2.1 Теоретическая часть

Рассмотрим следующую задачу целочисленного программирования. Требуется максимизировать выражение:

n

L=∑c_j∙x_j(4)

j=1

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

n

∑а_ij∙x_j≤b_i, i=1, …,m (5)

j=1

x_jЄ{0;1}, j=1, …,n

причем с_j≥0, a_ij≥0.

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

Эффективность вычислительных алгоритмов зависит от точности и простоты способа определения верхней границы возможных решений и точности определения приближенного решения. Чем точнее способ определения верхней границы целевой функции, тем больше бесперспективных ветвей отсекается в процессе оптимизации. Однако увеличение точности расчета верхних границ связано с возрастанием объема вычислений. Например, если для оценки верхней границы использовать симплекс-метод, то результат будет достаточно точным, но потребует большого объема вычислительной работы.

Рассмотрим алгоритм решения задачи методом ветвей и границ с простым и эффективным способом оценки верхней границы целевой функции.

Обозначим: U – множество переменных x_j; S – множество фиксированных переменных, вошедших в допустимое решение; E_s – множество зависимых переменных, которые не могут быть включены в множество S, так как для них выполняется неравенство

а_ij> b_i - ∑а_ij∙x_j, i=1, …,m

x_jЄS

G_S – множество свободных переменных, из которых производится выбор для включения в S очередной переменной.

Рассмотрим первоначально одномерную задачу, когда m=1 и задача (4) имеет только одно ограничение вида (5).

Обозначим h_1j = c_j/a_1j и допустим, что x_jЄS (j=1, …,k<n) и выполняются условия

h_1,k+1≥ h_1,k+2≥ …≥ h_1l, l≤n,

l

∑a_1j>b₁ - ∑ a_1j∙x_j,

j=k+1  x_jЄS

l-1

∑a_1j≤b₁ - ∑ a_1j∙x_j,

j=k+1 x_jЄS

Условия означают, что во множество S без нарушения неравенства (5) можно дополнительно ввести элементы x_k+1, x_k+2, …, x_l-1. При введении во множество S элементов x_k+1, x_k+2, …, x_l неравенство (5) не выполняется.

Для определения верхней границы решения может быть использовано выражение

H_s =∑c_j∙x_j+ L_s^’,

x_jЄS

где

l-1

L_s^’ = ∑с_j + h_1l∆b₁ ,

j=k+1

l-1

∆b₁ = b₁ - ∑ a_1j∙x_j- ∑a_1j.

x_jЄS  j=k+1

Из условий следует, что L_s^’не меньше максимального значения величины

∑c_j∙x_j

x_jЄG_S

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

∑ a_1j ∙x_j b₁ - ∑ a_1j∙x_j = b₁^’,

x_jЄG_S x_jЄS

x_jЄ {0;1}, x_jЄG_S ,

Выбор очередной переменной для включения во множество S производится с помощью условия

h_1r(x_r) = max h_1j(x_j)

x_jЄG_S

Для выбранной переменной x_r определяются величины H_s(x_r) и H_s(x_r), т.е. в S включаются x_r = 1 или x_r = 0.

Если в процессе решения окажется, что во множестве G_S нет элементов, которые могут быть введены во множество S без нарушения ограничения (5), то полученное решение L_s =∑c_j∙x_jпринимается в качестве первого приближенного  x_jЄSрешения L₀.

Все вершины дерева возможных вариантов, для которых выполняются условия

H_s≤ L₀, из дальнейшего рассмотрения исключаются.

Из оставшихся ветвей выбирается ветвь с максимальным значением H_s, и процесс поиска оптимального варианта продолжается. Если в процессе решения будет найдено L_s = ∑c_j∙x_j> L₀, то полученное решение принимается

x_jЄS

в качестве нового приближенного результата. Вычислительная процедура заканчивается, если для оставшихся ветвей выполняется условие H_s≤ L₀.