Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

МЕТОД ВЕТВЕЙ И ГРАНИЦ

Общая схема метода «ветвей и границ». Другим широко применяемым для решения задач дискретного программирования методом является метод ветвей и границ. Впервые данный метод для решения ЦЗЛП предложили в 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), ..., Dlq(q), удовлетворяющие условиям:

Для каждого подмножества находятся оценки сверху (верхние границы) для целевой функции ξD1(q), ξD2(q), ..., ξDl1(q), уточняющие ранее полученную оценку ξD(q), то есть ξDi(q) ≤ ξD(q), i∊1:lq. Возможно одно из двух:

2.1. Если существует такой план х(q), что

то этот план оптимальный.

2.2. Если такой план не найден, то выбирается одно из множеств Di(q), i∊1:lq (как правило, имеющее наибольшую оценку

Все имеющиеся к текущему моменту концевые подмножества, т. е. те подмножества, которые еще не подверглись процессу дробления, переобозначаются как D1(q+1), D2(q+1),..., Dl(q+1)(q+1), после чего процесс повторяется.

Схема дробления множества D представлена на рис. 4.3 в виде графа. Существуют и более сложные системы индексации подмножеств, при которых не требуется их переобозначение на каждом шаге.

Конкретные реализации метода ветвей и границ связаны с правилами разбиения на подмножества (правилами ветвления) и построения оценок значений целевых функций на данных подмножествах (границ).