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

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

Метод ветвей и границ относится к комбинаторным методам, в основе которого положены построения решений, позволяющих уменьшить объем перебора вариантов решений.

Графически МВГ можно представить в виде дерева решений – связанного графа, не содержащего цикл. Корень этого дерева – все множество вариантов, а вершины – подмножества частично упорядоченных вариант.

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

Трудность метода состоит в получении самой оценки.

Алгоритм МВГ

1.  Строится вершина первого уровня.

Для них подсчитывается оценка ψ() j=1…3

2.  Ветвится вершина, которой соответствует лучшая оценка.

Пусть ψ()> ψ(), ψ(), тогда ветвим , получаем , . подсчитываем оценки для вершины второго уровня.

3.  Среди «висячих вершин» первого и второго уровней выбираем вершину с наилучшей оценкой и производим ее ветвление.

4.  Аналогично на k-ом уровне среди «висячих» вершин k-ого уровня (k, k-1,k-2…1) выбираем вершину с наилучшей оценкой и ветвим ее. Действие продолжается до последнего n-ого уровня на ограниченном множестве k=1,2…n

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

Решение задачи целочисленного линейного программирования методом ветвей и границ.

Пусть задана задача ЛП

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

Поскольку решение нецелочисленное, произведем ветвление. Возьмем первую нецелочисленную и проведем разбиение множества на 2 подмножества.

Получаем 2 подзадачи:

Решаем каждую из задач

Так как - целочисленное и , то

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

Пусть задана задача

Решаем задачу симплекс методом.

	5	2	1	0	20
	8	4	0	1	38
Δ	-7	-3	0	0	0

	1			0	4
	0			1	6
Δ	0			0	28

					1
	0
Δ	0				71

 

Ответ:

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

Задача коммивояжера может быть симметричной и несимметричной.

Пусть имеется n пунктов, между которыми известны расстояния для каждой пары пунктов. Коммивояжер должен выбрать самый кротчайший (самый дешевый) замкнутый маршрут, начинающийся в городе, где он находится, и там же заканчивающийся. В каждом из пунктов необходимо побывать один раз. Если схема движения не зависит от направления, то задача симметричная. Число возможных вариантов в задачи коммивояжера (n-1)!

Решение МВГ

Пусть известны расстояния между городами.

1.  Поскольку минимальное расстояние между городами равно 1 и число шагов равно 5 – в качестве оценки возьмем ψ()= 1*5=5

2.  1) Ψ(=4+min(, j=3,4,5

Ψ(=9+ min(11;8;1)+3*1=13

Ψ(=6+min(4;3;8)+3=12

Ψ(= 1+min(11;8;1)+3=5

2) Ψ(=1+11+min(9;2)+2*1=16

Ψ(=1+1+min(11;8)+2=12

Ψ(=1+8+min(4;3)+2=14

3) Ψ(=4+9+min(8;1)+2=16

Ψ(=4+2+min(3;8)+2=11

Ψ(=4+10+min(1;8)=15

4) Ψ(=4+2+3+1+1=11

Ψ(=4+2+8+11+1=26

 

Ответ:

Алгоритм решения задачи коммивояжера в Excel

1.  Вводим ограничения для элементов матрицы по строкам и столбцам (сумма по строкам и столбцам равна 1). Сумма элементов главной диагонали равна 0.

2.  Если не удается найти оптимальный путь, то ставим ограничения, что коммивояжер не может вернуться в пройденный уже путь.

3.  Если оптимальный путь не найден (коммивояжер посетил не все пункты до возвращения в начальный пункт), то ставим ограничение, что сумма n элементов полученного пути меньше, либо равна (n-1). Повторяем действие до тех пор, пока не будет получен оптимальный путь.