§ 2. Метод ветвей и границ

1.

§ 2. Метод ветвей и границ

2.

Задача оптимизации:
( x) max
x
где
2
конечное множество
допустимых решений
множество всех подмножеств
множества

3.

Ветвление – это функция
которая каждому подмножеству A
множества
ставит в соответствие некоторое его разбиение
A A1 A2 Ak
k 0, Ai 0, i 1,2, , k
Ai Aj 0,
i j
таким образом:
( A) { A1, A2 , , Ak }
( A) 0 | A | 1
| A | 1

4.

Оценка – это функция
:2 R
а) ( A) ( x) x A
б ) ( A) ( x), если A {x}
Величина ( A) оценивает сверху значения
функции на множестве A и совпадает с ней
на множествах, состоящих из одного элемента
Для вычисления оценки решается упрощенная
оптимизационная задача

5.

Пусть L – это список подмножеств множества
Рекорд rec (L ) – это число, которое:
а) rec ( L) max ( x)
x
б ) rec ( L) ( x), если {x} L
( xrec ) rec( L) xrec рекордное решение
x0 начальное решение

6.

Общая схема метода ветвей и границ
Шаг 0: ищется начальное решение
L { }
для k =1,2,…
Шаг k: если список L=0, то стоп, xrec - решение
иначе выбрать из списка подмножество A
вычислить оценку ( A)
если ( A) rec ( L) , то L L \ { A}
иначе L L \ { A} ( A)

7.

На каждом шаге необходимо обновлять рекорд
при обнаружении решений лучших, чем
текущее рекордное решение.
Для реализации метода необходимо указать
правила:
1) вычисления оценки;
2) получения разбиения;
3) выбора подмножества (подзадачи) из
списка L.

8.

Пример: задача о рюкзаке.
Даны рюкзак грузоподъемностью V и n
предметов, каждый из которых имеет вес aj и
стоимость cj, j=1,…,n. Необходимо заполнить
рюкзак набором предметов с наибольшей
общей стоимостью.
n = 4,
V = 10
j
1
2
3
4
cj
20 16 11
7
aj
5
4
3
2

9.

Математическая модель задачи о рюкзаке:
1, предмет j берем
xj
иначе
0,
n
c x
j 1
j
j
max,
n
a x
j 1
j
j
V,
x j {0,1}.

10.

Метод ветвей и границ
схема ветвления:
1
x j 0
пусть определены значения
Оценки:
m
cj xj
j 1
n
c
j m 1
x1, , x m
m
j
ajxj
j 1

11.

Нет ветвления, если
rec
или
V