Лекция 4. Метод ветвей и границ

Кононова Полина Александровна

Новосибирский Государственный Университет Факультет информационных технологий vk.com/tpr_ t_2016

9.03.2016

План лекции

Содержание лекции

1Метод ветвей и границ

Интуиция

Основная идея

Описание метода

2Решение задачи

Пример задачи коммивояжера

Метод ветвей и границ. Интуиция

Пусть решается задача

min f(x);

x2D

и мы каким то образом нашли хорошее решение x .

Метод ветвей и границ. Интуиция

Пусть решается задача

min f(x);

x2D

и мы каким то образом нашли хорошее решение x .

Дальнейшим нашим желанием будет доказать, что x

решение или найти что то лучшее, для этого мы должны сравнить x со всеми допустимыми решениями.

Метод ветвей и границ. Интуиция

Пусть решается задача

min f(x);

x2D

и мы каким то образом нашли хорошее решение x .

Дальнейшим нашим желанием будет доказать, что x

решение или найти что то лучшее, для этого мы должны сравнить x со всеми допустимыми решениями.

Но решений очень много, и на большинство из них не стоило бы даже смотреть!

Метод ветвей и границ. Интуиция

Пусть решается задача

min f(x);

x2D

и мы каким то образом нашли хорошее решение x .

Дальнейшим нашим желанием будет доказать, что x

решение или найти что то лучшее, для этого мы должны сравнить x со всеми допустимыми решениями.

Но решений очень много, и на большинство из них не стоило бы даже смотреть!

Попробуем избежать лишней работы, сравнивая x с целыми множествами допустимых решений.

Метод ветвей и границ. Интуиция

Пусть имеется d D некоторое множество непросмотренных решений.

Метод ветвей и границ. Интуиция

Пусть имеется d D некоторое множество непросмотренных

решений.

Мы можем ¾оптимистично¿ оценить решения множества d, то есть вычислить некоторую величину LB(d), нижнюю границу, такую, что

LB(d) 6 minx2d f(x).

Метод ветвей и границ. Интуиция

Пусть имеется d D некоторое множество непросмотренных

решений.

Мы можем ¾оптимистично¿ оценить решения множества d, то есть вычислить некоторую величину LB(d), нижнюю границу, такую, что

LB(d) 6 minx2d f(x).

Тогда, в случае, если f(x ) 6 LB(d), нам не нужно даже приступать к

просмотру множества d даже по оптимистичному прогнозу в нем нет ничего лучше x

Метод ветвей и границ. Интуиция

Пусть имеется d D некоторое множество непросмотренных

решений.

Мы можем ¾оптимистично¿ оценить решения множества d, то есть вычислить некоторую величину LB(d), нижнюю границу, такую, что

LB(d) 6 minx2d f(x).

Тогда, в случае, если f(x ) 6 LB(d), нам не нужно даже приступать к

просмотру множества d даже по оптимистичному прогнозу в нем нет ничего лучше x

Кроме этого нам пригодится термин верхняя граница, UB(d), которым

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

UB(d) > minx2d f(x).

Метод ветвей и границ. Интуиция

Пусть имеется d D некоторое множество непросмотренных

решений.

Мы можем ¾оптимистично¿ оценить решения множества d, то есть вычислить некоторую величину LB(d), нижнюю границу, такую, что

LB(d) 6 minx2d f(x).

Тогда, в случае, если f(x ) 6 LB(d), нам не нужно даже приступать к

просмотру множества d даже по оптимистичному прогнозу в нем нет ничего лучше x

Кроме этого нам пригодится термин верхняя граница, UB(d), которым

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

UB(d) > minx2d f(x).

LB(d) 6 min f(x) 6 UB(d):

x2d

Метод ветвей и границ. Интуиция

Пусть имеется d D некоторое множество непросмотренных

решений.

Мы можем ¾оптимистично¿ оценить решения множества d, то есть вычислить некоторую величину LB(d), нижнюю границу, такую, что

LB(d) 6 minx2d f(x).

Тогда, в случае, если f(x ) 6 LB(d), нам не нужно даже приступать к

просмотру множества d даже по оптимистичному прогнозу в нем нет ничего лучше x

Кроме этого нам пригодится термин верхняя граница, UB(d), которым

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

UB(d) > minx2d f(x).

LB(d) 6 min f(x) 6 UB(d):

x2d

В качестве верхней границы можно использовать величину UB(d) = f(xd) для некоторого xd 2 d.