Метод проектов
<<  Методы развития творческого воображения (РТВ) Комбинаторные методы решения вероятностных задач  >>
Метод ветвей и границ
Метод ветвей и границ
Графически МВГ можно представить в виде дерева решений – связанного
Графически МВГ можно представить в виде дерева решений – связанного
Алгоритм МВГ
Алгоритм МВГ
Задача
Задача
Получаем: Так как решение нецелочисленное, то производим ветвление
Получаем: Так как решение нецелочисленное, то производим ветвление
Задача коммивояжера
Задача коммивояжера
Решение задачи коммивояжера методом ветвей и границ
Решение задачи коммивояжера методом ветвей и границ
Ответ :
Ответ :
Решим задачу коммивояжера в EXCEL
Решим задачу коммивояжера в EXCEL
Алгоритм решения задачи коммивояжера в Excel
Алгоритм решения задачи коммивояжера в Excel
Метод ветвей и границ
Метод ветвей и границ
Метод ветвей и границ
Метод ветвей и границ

Презентация на тему: «Метод ветвей и границ». Автор: Кира. Файл: «Метод ветвей и границ.ppt». Размер zip-архива: 1028 КБ.

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

содержание презентации «Метод ветвей и границ.ppt»
СлайдТекст
1 Метод ветвей и границ

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

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

2 Графически МВГ можно представить в виде дерева решений – связанного

Графически МВГ можно представить в виде дерева решений – связанного

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

3 Алгоритм МВГ

Алгоритм МВГ

Строятся вершины первого уровня. Для них подсчитывается оценка ?( ) Ветвится вершина, которой соответствует лучшая оценка. Подсчитываются оценки для вершин второго уровня. Среди «висячих» вершин 1 и 2 уровней выбирается вершина с наилучшей оценкой и производится ее ветвление. Аналогично на k-ом уровне среди «висячих» вершин выбираем вершину с наилучшей оценкой и ветвим ее. Действие продолжается до последнего n-ого уровня. Оптимальное решение соответствует вершине, для которой значение ? самое большое.

4 Задача

Задача

Решаем задачу симплекс методом или графически. В итоге получаем: Так как решение нецелочисленное, то произведем ветвление: возьмем нецелочисленную переменную и проведем разбиение множества на два подмножества.

5 Получаем: Так как решение нецелочисленное, то производим ветвление

Получаем: Так как решение нецелочисленное, то производим ветвление

первого решения (решения с наибольшей оценкой). Получаем ответ: Ответ: L(x)=29, x1=2, x2=5

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

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

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

7 Решение задачи коммивояжера методом ветвей и границ

Решение задачи коммивояжера методом ветвей и границ

Пусть известны расстояния между городами. Поскольку минимальное расстояние между городами равно 1 и число шагов равно 5, в качестве оценки возьмем ?( )=5. Произведем ветвление первого уровня: ?( )=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 Далее производим ветвление вершин второго уровня. Среди «висячих» вершин выбираем наименьшую оценку и производим ее ветвление и т.д. до последнего этапа, пока не получим наименьшее решение.

8 Ответ :

Ответ :

9 Решим задачу коммивояжера в EXCEL

Решим задачу коммивояжера в EXCEL

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

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

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

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

11 Метод ветвей и границ
12 Метод ветвей и границ
«Метод ветвей и границ»
http://900igr.net/prezentacija/pedagogika/metod-vetvej-i-granits-182354.html
cсылка на страницу
Урок

Педагогика

135 тем
Слайды