Общая схема метода ветвей и границ решения ЗДП

. В начале процесса  разбивается на  подмножеств:

В начале должна быть вычислена величина  – нижняя оценка оптимального значения  на , т.е. если - решение ЗДП, то

 (1)

.

Для всех подмножеств в , полученных в результате разбиения, должна быть вычислена верхняя оценка  функции  на .

Величины  и  используются для сужения области поиска решения ЗДП. А именно если выполняется условие  (2).

(2) означает, что  на множестве  функция не достигает своего максимума, следовательно в дальнейшем подмножество  можно не рассматривать при решении задачи.

Предположим (2) выполнено для , т.е. их нужно выбросить из рассмотрения. Потом корректируем , на графе они просто вычеркиваются. Рассматриваем только оставшиеся висячие вершины подмножества. Для продолжения решения выбираем для разбиения следующее подмножество.

Выбираем следующее для разбиения подмножество из условия:

 (4)

Пусть  разбивается на , переобозначим

Для каждого из этих подмножеств вычисляем:

 (5)

Проверяем условие (5).

Пусть условие (5) выполняется для  (6).

Нужно скорректировать два подмножества  и

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

Дальнейший процесс решения задачи можно построить двумя способами.

Граф:

Первый способ:

Для дальнейшего разбиения выбирается подмножество из подмножеств, полученных в результате последнего разбиения , например:

Пусть это будет  и производим разбиение.

Дальнейший процесс будет проходить также.

При этом способе можно достаточно быстро получить подмножество , содержащее всего один план задачи

, то - претендент на оптимальный план. Запоминаем на графе на ветке, приводящей к  ставим конец и корректируется величина , т.е. .

 увеличена, следовательно нужно рассмотреть все нерассмотренные подмножества.

Далее продолжаем процесс решения задачи также.

Второй способ:

Выбирается множество для разбиения из всех висячих вершин, ещё нерассмотренных.

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

Решением задачи будет тот план, который дал последнее значение величине .

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

1) как найти ;

2) по какому принципу проводить разбиение множества;

3) как вычислить .