 |
 |
 |
 |
|
 |
 |
83
дискретного программирования методом является метод ветвей и границ. Впервые данный метод для
решения ЦЗЛП предложили в 1960 г. Лэнг и Дойг, а его «второе рождение» произошло в 1963 г. в связи
с выходом работы Литтла, Мурти, Суини и Кэрел, посвященной решению задачи о коммивояжере [33].
Вообще говоря, термин «метод ветвей и границ» является собирательным и включает в себе целое
семейство методов, применяемых для решения как линейных, так и нелинейных дискретных задач,
объединяемое общими принципами. Кратко изложим их.
Пусть стоит задача:
где D — конечное множество.
Алгоритм является итеративным, и на каждой итерации происходит работа с некоторым
подмножеством множества D. Назовем это подмножество текущим и будем обозначать его как D
(q)
, где
q
— индекс итерации. Перед началом первой итерации в качестве текущего множества выбирается все
множество D (D
(1)
=D),
и для него некоторым способом вычисляется значение верхней оценки для
целевой функции max f(x) ?
?
( D
(1)
). Стандартная итерация алгоритма состоит из следующих этапов:
1°. Если можно указать план x
(q)
?D
(q)
, для которого f(x
(q)
)?
?
( D
(q)
), то x
(q)
=х* — решение задачи (4.29).
2°. Если такой план не найден, то область определения
D
(q)
некоторым образом разбивается на
подмножества D1
(q)
,
D2
(q)
, ..., D
lq
(q)
, удовлетворяющие условиям:
Для каждого подмножества находятся оценки сверху (верхние границы) для целевой функции ?D1
(q)
,
?D2
(q)
, ..., ?D
l1
(q)
, уточняющие ранее полученную оценку ?D
(q)
, то есть ?D
i
(q)
?
?
D
(q)
, i?1:l
q
. Возможно одно
из двух:
2.1. Если существует такой план х
(q)
, что
то этот план оптимальный.
2.2. Если такой план не найден, то выбирается одно из множеств D
i
(q)
,
i?1:l
q
(как правило, имеющее
наибольшую оценку
Все имеющиеся к текущему моменту концевые подмножества, т. е. те подмножества, которые еще не
подверглись процессу дробления, переобозначаются как D1
(q+1)
,
D2
(q+1)
,..., D
l(q+1)
(q+1)
,
после чего процесс