Метод ветвей и границ решения задачи цлп
Рассмотрим задачу ЦЛП:
(1)
при ограничениях:
(2)
(3)
(4)
Алгоритм метода ветвей и границ
Находят решение ЗЛП (1) – (3). Если
оптимальный план
этой задачи не содержит дробных чисел,
то, тем самым, найдено искомое решение
задачи (1) – (4) и
Если среди компонент плана
имеются дробные числа, то
не удовлетворяет условию (4). Тогда для
одной из переменных, принявших в плане
дробное значение, составляют дополнительные
ограничения. Пусть, например, переменная
приняла
в плане
дробное значение. Тогда в оптимальном
целочисленном плане её значение будет,
по крайней мере, либо меньше или равно
ближайшему меньшему целому числу
,
либо больше или равно ближайшему большему
целому числу
+1.
Определяя эти числа, находят симплекс-методом
решение двух ЗЛП:
(I)
(II)
Здесь возможен один из следующих четырёх случаев.
Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нём и дают решение исходной задачи (1) – (4).
Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматривают вторую задачу и в её оптимальном плане выбирают одну из компонент, значение которой равно дробному числу и строят две задачи, аналогичные задачам (I) и (II).
Обе задачи разрешимы. Одна из задач имеет оптимальный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляют значения целевой функции на этих планах и сравнивают их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно её значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи, и он вместе со значением целевой функции на нём даёт искомое решение. Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные (I) и (II).
Обе задачи неразрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляют значения целевой функции на данных оптимальных планах и рассматривают ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбирают одну из компонент, значение которой является дробным числом, и строят две задачи, аналогичные (I) и (II).
Таким образом, данный итерационный процесс может быть представлен в виде дерева, на котором исходная вершина отвечает оптимальному плану задачи (1) – (3), а каждая соединённая с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нём окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи ЦЛП и значение целевой функции на нём является максимальным.
Пример. Решим предыдущую задачу методом ветвей и границ
(5)
(6)
(7)
(8)
Оптимальное решение задачи (5) – (7):
.
.
Возьмём какую-нибудь переменную, значение
которой является дробным числом,
например,
.
Тогда эта переменная в оптимальном
плане задачи (1) – (4) будет принимать
значение, либо меньшее или равное 9:
либо большее или равное 10:
Рассмотрим две ЗЛП:
(I)
(II)
Решим симплекс-методом задачу (I). Запишем её в каноническом виде.
.
i |
Базис |
|
|
3 |
2 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
||||
1 |
|
0 |
13 |
1 |
1 |
1 |
0 |
0 |
0 |
|
2 |
|
0 |
6 |
|
-1 |
0 |
1 |
0 |
0 |
|
3 |
|
0 |
9 |
-3 |
1 |
0 |
0 |
1 |
0 |
|
4 |
|
0 |
9 |
1 |
0 |
0 |
0 |
0 |
1 |
|
5 |
|
|
0 |
-3 |
-2 |
0 |
0 |
0 |
0 |
|
1 |
|
0 |
7 |
0 |
2 |
1 |
-1 |
0 |
0 |
|
2 |
|
3 |
6 |
1 |
-1 |
0 |
1 |
0 |
0 |
|
3 |
|
0 |
27 |
0 |
-2 |
0 |
3 |
1 |
0 |
|
4 |
|
0 |
3 |
0 |
|
0 |
-1 |
0 |
1 |
|
5 |
|
|
18 |
0 |
-5 |
0 |
3 |
0 |
0 |
|
1 |
|
0 |
1 |
0 |
0 |
1 |
|
0 |
-2 |
|
2 |
|
3 |
9 |
1 |
0 |
0 |
0 |
0 |
1 |
|
3 |
|
0 |
33 |
0 |
0 |
0 |
1 |
1 |
2 |
|
4 |
|
2 |
3 |
0 |
1 |
0 |
-1 |
0 |
1 |
|
5 |
|
|
33 |
0 |
0 |
0 |
-2 |
0 |
5 |
|
1 |
|
0 |
1 |
0 |
0 |
1 |
1 |
0 |
-2 |
|
2 |
|
3 |
9 |
1 |
0 |
0 |
0 |
0 |
1 |
|
3 |
|
0 |
32 |
0 |
0 |
-1 |
0 |
1 |
4 |
|
4 |
|
2 |
4 |
0 |
1 |
1 |
0 |
0 |
-1 |
|
5 |
|
|
35 |
0 |
0 |
2 |
0 |
0 |
1 |
|
;
Решим задачу (II). Запишем её в каноническом виде.
или 
Решим последнюю ЗЛП двойственным симплекс-методом.
i |
Базис |
|
|
3 |
2 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
||||
1 |
|
0 |
13 |
1 |
1 |
1 |
0 |
0 |
0 |
2 |
|
0 |
6 |
1 |
-1 |
0 |
1 |
0 |
0 |
3 |
|
0 |
9 |
-3 |
1 |
0 |
0 |
1 |
0 |
4 |
|
0 |
-10 |
|
0 |
0 |
0 |
0 |
1 |
5 |
|
|
0 |
-3 |
-2 |
0 |
0 |
0 |
0 |
1 |
|
0 |
3 |
0 |
1 |
1 |
0 |
0 |
1 |
2 |
|
0 |
-4 |
0 |
|
0 |
1 |
0 |
1 |
3 |
|
0 |
39 |
0 |
1 |
0 |
0 |
1 |
-3 |
4 |
|
3 |
10 |
1 |
0 |
0 |
0 |
0 |
-1 |
5 |
|
|
30 |
0 |
-2 |
0 |
0 |
0 |
-3 |
1 |
|
0 |
-1 |
0 |
0 |
1 |
1 |
0 |
1 |
2 |
|
2 |
4 |
0 |
1 |
0 |
-1 |
0 |
-1 |
3 |
|
0 |
35 |
0 |
0 |
0 |
1 |
1 |
-2 |
4 |
|
3 |
10 |
1 |
0 |
0 |
0 |
0 |
-1 |
5 |
|
|
38 |
0 |
0 |
0 |
-2 |
0 |
-5 |
Так как в первой строке последней симплекс-таблицы в столбце вектора имеется одно отрицательное число (-1), а среди остальных элементов этой строки нет отрицательных, то задача (II) не имеет решения.
Таким образом исходная задача (5) – (8)
имеет оптимальный план
.
При этом плане
.
Схему реализованного вычислительного процесса можно представить в виде дерева, ветвями которого являются соответствующие ограничения на переменные, а вершинами – решения соответствующих ЗЛП.
-
Задача (5) – (7)
Задача I |
|
Задача II |
|
Задача неразрешимая |
Метод ветвей и границ имеет более простую логическую схему расчетов, чем метод Гомори, поэтому в большинстве случаев для нахождения решения конкретных задач ЦЛП с использованием компьютеров применяется метод ветвей и границ.