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

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

f(X) -> max, (7.9)

Х€D (7.10)

где D — конечное множество.

Сначала найдем оценку £(D) (границу) функции f(X), X е D: f(X) ≤ £(D) для V X е D. Если для некоторого плана Х° задачи (7.9)-(7.10) справедливо равенствоf(X⁰) = £(D), то Х° = X^* является решением задачи. Если указанное условие не выполняется, то возмож­но разбиение (ветвление) множества D на конечное число непересека­ющихся подмножеств D¹_i: ỤD¹_i. = D, ∩D¹_i = Ө, и вычисление оценки £(D¹_i) (границ), 1≤i≤m (рис 7.1)

Рис. 7.1

Если для некоторого плана X¹_i е Di¹, 1 ≤ / ≤ m выполняется условие f(X_k^l)= £(D¹_k)≥ £(D¹_i), 1≤i≤m то X_k¹=X^* является оптимальным планом (решением) задачи (7.9)-(7.10).

Если такого плана нет, то выбирается подмножество D_k^l с наиболь­шей оценкой £(D¹_i):

и разбивается на конечное число непересекающихся подмножеств

D²_kj: UD²_kj=D¹_k, ∩D²_kj=Ө. Для каждого подмножества находится оценка £(D²_kj), 1≤j≤n (рис 7.2)

(рис. 7.2).

(рис. 7.2).

Если при этом найдется план X²_j е D²_kJ, 1 ≤j ≤n, такой, что f(X²_r)= £(D²_kr)≥ £(D²_kj), 1≤j≤n, то X²_r= X* является решением задачи (7.9)-(7.10). Если такого плана нет, то процедуру ветвления осуществля­ют для множества D²_kj с наибольшей оценкой £(D²_kj), 1≤j≤n. Способ ветвления определяется спецификой конкретной задачи.

Рассмотрим задачу, которую можно свести к задаче целочисленного линейного программирования.

Пример.

Контейнер объемом 5 м³ помещен на контейнеровоз грузо­подъемностью 12 т. Контейнер требуется заполнить грузом двух наиме­нований. Масса единицы груза m_j (в тоннах), объем единицы груза V_j (в м³), стоимости Cj (в условных денежных единицах) приведены в табл. 7.3.

Таблица 7.3

Требуется загрузить контейнер таким образом, чтобы стоимость пе­ревозимого груза была максимальной.

Решение. Математическая модель задачи имеет вид

Z(X) = 10x₁+12x₂→max, (7.11)

3x₁+x₂≤12,

x₁+2x₂≤5

x₁≥0 (7.12)

x₂≥0

x₁, x₂- целые числа (7.13)

где x₁, x₂ - число единиц соответственно первого и второго груза.

Множество планов этой задачи обозначим через D - это множество целых точек многогранника ОАВС (рис. 7.3).

Рис. 7.3

Сначала решаем задачу (7.11)—(7.13) без условия целочисленности, получим оценку множества D - значение функции Z(X) на оптималь­ном плане Х° = (¹⁹/₅, ³/₅):

ТочкаXнеявляется оптимальным планом задачи (7.1 1)— (7.13). По­этому в соответствии с методом ветвей и границ требуется разбить множество D на непересекающиеся подмножества. Выберем первую нецелочисленную переменную x₁=19/5=34/5 и разобьем множество D на два непересекающихся подмножества D¹₁ и D²₂. Линии x₁=3 (L₃) и x₄= (L₃) являются линиями разбиения.

Рис. 7.4

Найдем оценки £(D¹₁) и £(D¹₂), для чего решим задачи линейного программирования

Z(X)=10x₁+12x₂→max,

3x₁+x₂≤12

x₁+2x₂≤5

x₁≤3

x₁≥0, x₂ – целые числа

Z(X)=10x₁+12x₂→max,

3x₁+ x₂≤12

x₁+2x₂≤5

x_1≥4

x₁≥0, x₂ – целые числа

Например, графическим методом:

X¹₁eD¹₁→X⁰₁= (3,1); £(D¹₁)=42; X¹₂eD¹₂→X⁰₂= (4,0); £(D¹₂)=40.

Результат ветвления приведен на рис. 7.5

План X⁰₁ удовлетворяет условиям задачи (7.11)-(7.13), и для него выполняется условие: Z(X¹₁)= £(D¹₁)=42 >

£(/)/) = 42 >£(D¹₂) = 40. Следовательно, план X°₁= (3, 1) является решением задачи (7.11)-(7.13),

т.е. надо взять три единицы первого груза и одну единицу второго груза.

Алгоритм метода ветвей и границ

1. Находим решение задачи линейного программирования без учета целочисленности.
2. Составляет дополнительные ограничения на дробную компоненту плана.
3. Находим решение двух задач с ограничениями на компоненту.
4. Строим в случае необходимости дополнительные ограничения, согласно возможным четырем случаям получаем оптимальный целочисленный план либо устанавливаем неразрешимость задачи.