33 Метод ветвей и границ, решение линейных целочисленных задач.(Метод Ленд и Дойг)

Этот метод разработан для решения задач частично целочисленного программирования. Минимизировать

(3.11)

при условиях

(3.12)

(3.13)

(3.14)

Некоторые из d_j могут быть равны +inf. При решении задачи предполагается, что область допустимых значений является ограниченным многогранным множеством.

Решение задачи осуществляется следующим образом.

Сначала решается обычная задача линейного программирования (3.11) - (3.13). Если полученный оптимальный план Х⁰ не удовлетворяет условиям целочисленности, то значение целевой функции f(x^⁰)=ϕ⁰ дает нижнюю границу для искомого экстремума, т.е. minf(x)≥ϕ⁰. Рассмотрим какую-то переменную x_i0 (1≤i₀≤n₁), которая в данном плане не получила целочисленного значения. В оптимальном целочисленном плане значение x_i0 должно быть либо уменьшено по крайней мере до [Х_i0], либо увеличено по крайней мере до [Х_i0]+1 (что ещё можно записать как ]Х_i0[). Если границы изменения Х_i0 не были заданы, то их можно вычислить, решив две ЗЛП (максимизации и минимизации Х_i0, при условиях (3.12) - (3.13)). Затем для каждого фиксированного значения k_i0 в найденном отрезке можно найти minf(x) путем решения задачи линейного программирования (3.11) - (3.13) с дополнительным ограничением Х_i0=k_i0.

Возможные разновидности таких ЗЛП можно представить в виде некоторого дерева задач, в котором вершина 0 соответствует исходному плану X⁰, а каждая из соединенных с ней ветвью вершин отвечает оптимальному плану задачи минимизации f(x) при ограничениях (3.12) - (3.13) и дополнительном ограничении Х_i0=k_i0.

Каждой из вершин приписывается граница ϕ^k=ϕ(i₀,k), равная минимальному значению f(x) для соответствующей задачи. Понятно, что ϕ⁰ = ϕ(i₀,k) для всех k. Процесс продолжается до тех пор, пока дальнейшее ветвление становится невозможным. При ветвлении каждой вершине в качестве её границы приписывается оценка, равная значению целевой функции в ЗЛП, соответствующей этой вершине. Итак, оптимальный план в конечном итоге дает вершина с минимальным f(x). Собственно, алгоритм метода Ленд и Дойг следующий:

1. Задание исходного множества. Множество G⁰=G задается условиями (3.12) - (3.14).

2. Задание остальных множеств. Множества G (kнадj), V=1,2,...,r_k; k=1,2... определяется условиями (3.12) и (3.14) и дополнительным условием

(3.13а)

3. Вычисление оценок (границ). Для G(0надk) ϕ(G⁰)=f(x⁰), где х (0надk) - оптимальный план ЗЛП (3.11)-(3.13). Для G(kнадV) ϕ(G(kнадV))=f(x(kнадV)), где x(kнадV) - оптимальный план ЗЛП (3.11), (3.12), (3.13а). Если множество G(kнадV) оказывается пустым, т.е. соответствующая ЗЛП неразрешима, то ϕ(G(kнадV))=+inf.

4. Вычисление планов. Если Х⁰ удовлетворяет 3.14, то Х⁰ является оптимальным планом задачи (3.11) -(3.14). Если Х(kнадV) удовлетворяет условию (3.14), то Х(kнадV) является оптимальным планом задачи (3.11), (3.12), (3.13а), (3.14) и планом задачи (3.11) - (3.14).

5. Ветвление. Оно возникает всегда, когда план Х(kнадV) не удовлетворяет условию целочисленности (3.14). Пусть X_r (k над V(k)) - нецелочисленная компонента такого плана (1≤r≤n₁), тогда множество G(kнадV(k)) разбивается на два подмножества:

где и

В случае, если все c_j в целевой функции целые для j≤n₁ и равны 0 для j>n₁, оценку ϕ(G(kнадV)) можно заменить на более сильную оценку ϕ(G(kнадV))=]f(x(kнадV))[.

Конечность алгоритма следует из предположения об ограниченности множества (3.12) - (3.13).