 |
 |
 |
 |
|
 |
 |
84
повторяется.
Схема дробления множества D представлена на рис. 4.3 в виде графа. Существуют и более сложные
системы индексации подмножеств, при которых не требуется их переобозначение на каждом шаге.
Конкретные реализации метода ветвей и границ связаны с правилами разбиения на подмножества
(правилами ветвления) и построения оценок значений целевых функций на данных подмножествах
(границ).
4.3.2. Решение ЦЗЛП методом ветвей и границ. Рассмотрим применение алгоритма метода ветвей
и границ для решения ЦЗЛП (4.2)-(4.3). Как уже упоминалось, через
D
(q)
обозначается подмножество
множества допустимых планов задачи. Перед началом первой итерации (q = 1) в качестве текущего
множества берется все множество D (D
(1)
= D), после чего решается стандартная задача линейного
программирования (D
(1)
, f). Нетрудно заметить, что она является непрерывным аналогом
исходной задачи (4.2)-(4.3). Если найденный оптимальный план
x
ˆ
(1)
содержит только целочисленные
компоненты, то он является и оптимальным планом для (4.2)-(4.3):
x
ˆ
(1)
=
x*. В противном случае
значение f(
x
ˆ
(1)
) становится оценкой (верхней границей) значения целевой функции на множестве D
(1)
, и
мы переходим к выполнению стандартной итерации алгоритма. Опишем входящие в нее этапы.
1) Выбирается некоторая нецелочисленная компонента плана
x
ˆ
k
(q)
. Поскольку в оптимальном плане
она должна быть целой, то можно наложить ограничения x
k
?
[
x
ˆ
k
(q)
] и x
k
?
[
x
ˆ
k
(q)
]+1. Таким образом, D
(q)
разбивается на подмножества
Графическая интерпретация такого разбиения множества D
(q)
приведена на рис. 4.4.
2) Решаются задачи линейного программирования
Соответствующие максимальные значения целевой функции принимаются как ее оценки на этих
множествах:
Если оптимальный план
x
ˆ
для одной из решенных задач удовлетворяет условию