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

Задача линейного программирования решается без учета целочисленности. Далее рассматривают одну из переменных х^., на которую накладывают ограничение целочисленности, но получившую дробное значение. На основе полученного решения составляют дополнительные ограничения:

X- < [х*] и X- > [х.*] + 1,

где [х-] — целая часть нецелочисленного значения переменной х* в оптимальном решении. Затем решаются еще две задачи линейного программирования, в каждую из которых вошли все исходные ограничения и одно из дополнительных.

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

Если одно из решений удовлетворяет требованию целочисленности, значение целевой функции принимается за граничное L. При этом рассмотрение других задач продолжается до тех пор, пока не будет получено: •

на одной из ветвей — недопустимое решение; •

на одной из ветвей — целочисленное решение. Тогда значение целевой функции сравнивается с L (верхним — при max, нижним — при min); если полученное значение хуже, оно отбрасывается, если лучше, то принимается за граничное; •

на одной из ветвей — нецелочисленное решение, однако при этом значение целевой функции хуже граничного. Тогда дальнейшее рассмотрение также прекращается.

На первом цикле расчета

L [-<» при max L; ггр [+<» при min L.

Пример.

Определить значение переменных для следующей оптимизационной задачи:

max L = 7х1 + 3х2; 5х1 + 2х2 < 20; 8х1 + 4х2 < 38; х1, х2 > 0 — целые.

Решение. В результате решения задачи симплекс-методом найдем оптимальное решение: x = 1; x2 = 7,5, L1 = 29,5, где верхний индекс переменных — номер задачи (рис. 8.4).

В полученном решении х2 = 7,5 — нецелочисленное. Поэтому для дальнейшего решения составляем две новые задачи с различными граничными условиями.

Задача 2: Задача 3:

max L = 7х1 + 3х2; max L = 7х1 + 3х2;

5х1 + 2х2 < 20;5х1 + 2х2 < 20;

8х1 + 4х2 < 38;8х1 + 4х2 < 38; х1 > 0;х1 > 0; 0

< х2 < 7. х2 > 8.

Рис. 8.4

Результаты решения симплекс-методом задачи 2: х^ = 1,2; х| = 7; Ь2 = 29,4.

Результаты решения симплекс-методом задачи 3: = 0,75; х\ = 8; Ь3 = 29,25.

В задаче 1 переменная х11 = 1 — целочисленная, а при целочисленности х2 в последующих задачах х1 перестала быть целочисленной. Затем следует накладывать ограничения целочисленности на х1 и т. д.

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

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