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

Сентябрь 7, 2022

Главная
Алгебра
Методы типа ветвей и границ

Содержание

2. Содержание: 1. Задачи с булевыми переменными 1.1. Фронтальный спуск по дереву ветвлений 1.2. Поиск с возвратом
3. ОБЩИЕ СВОЙСТВА МЕТОДОВ ТИПА ВЕТВЕЙ И ГРАНИЦ 1. Метод вычисления оценки таков, что по мере спуска
4. Часть 1 Решение задач с булевыми переменными
5. 1.1. Фронтальный спуск по дереву ветвлений
6. Содержательное описание алгоритма Шаг 1. На построенной части дерева ветвлений выбирается вершина с наилучшей оценкой, принадлежащая
7. ПРИМЕР 1 Пусть задана задача о ранце вида:
8. ДЕРЕВО ВЕТВЛЕНИЙ XXopt = {0, 0, 1, 1}; R=12.
9. Достоинства и недостатки фронтального спуска по дереву ветвлений: Достоинства: шанс на неполный перебор, первый же полный
10. САМОСТОЯТЕЛЬНО Пользуясь фронтальным спуском решить задачу вида:
11. 1.2. Поиск с возвратом
12. Содержательное описание алгоритма Шаг 1. R = плохое значение Шаг 2. i = 1 Шаг 3.
13. ПРИМЕР 2
14. Построение дерева ветвлений
15. САМОСТОЯТЕЛЬНО Пользуясь методом типа ветвей и границ, реализующим поиск с возвратом, решить задачу вида:
16. ЧАСТЬ 2 Решение многокритериальных задач методами типа ветвей и границ
17. Основные положения Свертка критериев с помощью эталонов позволяет получить новую целевую функцию вида: где Fi -
18. ПРИМЕР 2 Пользуясь описанным выше методом свертки, решить многокритериальную задачу с булевыми переменными вида:
19. Условия свертки Для того, чтобы преобразовать (1) в однокритериальную задачу, следует определить максимальные и минимальные значения
20. Поиск максимальной величины F1
21. Решение задачи (2) методом типа ветвей и границ S 17 1 0 10 1 17 0
22. Поиск минимальной величины F1 сводится к решению задачи (3):
23. Решение задачи (3) методом типа ветвей и границ S 7 1 0 0 1 2 0
24. Поиск максимальной величины F2
25. Решение задачи (4) методом типа ветвей и границ s 1 14 11 0 14 1 10
26. Поиск минимальной величины F2
27. Решение задачи (5) методом типа ветвей и границ S 3 1 0 0 7 3 4
28. Использование эталонов для преобразования(1) в однокритериальную задачу
29. Вид системы (6) после преобразований
30. Решение задачи (7) методом ветвей и границ S F1=12; F2=5; φ=0 F1=10; F2=5; φ =0,0816 1
32. Скачать презентацию

Слайд 2

Содержание:
1. Задачи с булевыми переменными
1.1. Фронтальный спуск по дереву ветвлений
1.2. Поиск

с возвратом (алгоритм Балаша)
2. Многокритериальные задачи
2.1.Поиск величин эталонов методами типа ветвей и границ.
2.2. Формальная постановка задачи.
2.3. Решение многокритериальной задачи методом типа ветвей и границ.

Слайд 3

ОБЩИЕ СВОЙСТВА МЕТОДОВ ТИПА ВЕТВЕЙ И ГРАНИЦ
1. Метод вычисления оценки таков,

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

Слайд 4

Часть 1
Решение задач с булевыми переменными

Слайд 5

1.1. Фронтальный спуск по дереву ветвлений

Слайд 6

Содержательное описание алгоритма
Шаг 1. На построенной части дерева ветвлений выбирается вершина

с наилучшей оценкой, принадлежащая i-у ярусу.
Шаг 2. Если i=n, где n – число переменных, то перейти к шагу , в противном случае – к шагу 3.
Шаг 3. В базис частичного плана, соответствующего выбранной вершине, вводится (i+1)-я переменная и вычисляются соответствующие оценки. Перейти к шагу 1.
Шаг 4. Конец алгоритма. Оценка выбранной на предыдущем шаге вершины является оптимальным значением целевой функции.

Слайд 7

ПРИМЕР 1
Пусть задана задача о ранце вида:

Слайд 8

ДЕРЕВО ВЕТВЛЕНИЙ
XXopt = {0, 0, 1, 1}; R=12.

Слайд 9

Достоинства и недостатки фронтального спуска по дереву ветвлений:

Достоинства: шанс на неполный

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

Слайд 10

САМОСТОЯТЕЛЬНО
Пользуясь фронтальным спуском решить задачу вида:

Слайд 11

1.2. Поиск с возвратом

Слайд 12

Содержательное описание алгоритма
Шаг 1. R = плохое значение
Шаг 2. i =

1
Шаг 3. xi = 1
Шаг 4. Вычисляется оценка рекорда F
Шаг 5. Если F R, то перейти к шагу 6, нет –
к шагу 9
Шаг 6. Если все ограничения удовлетворяют, то
перейти к шагу 7, нет к шагу 9
Шаг 7. Если i = n, то перейти к шагу 8, нет –
к шагу 13
Шаг 8. R = F, печать R и вектора
Шаг 9. Если xi = 1, то перейти к шагу 10, нет –
к шагу 13
Шаг 10. xi = 0, перейти к шагу 4
Шаг 11. Если i = 1, то перейти к шагу 14, нет к шагу 12.
Шаг 12. i = i - 1, перейти к шагу 9.
Шаг 13. i = i + 1, перейти к шагу 3.
Шаг 14. Конец алгоритма. Последние выданные на печать значения R и , оптимальны.

Слайд 13

ПРИМЕР 2

Слайд 14

Построение дерева ветвлений

Слайд 15

САМОСТОЯТЕЛЬНО
Пользуясь методом типа ветвей и границ, реализующим поиск с возвратом, решить

задачу вида:

Слайд 16

ЧАСТЬ 2
Решение многокритериальных задач методами типа ветвей и границ

Слайд 17

Основные положения
Свертка критериев с помощью эталонов позволяет получить новую целевую функцию

вида:
где Fi - i– я целевая функция, zi = 1, если Fi max,
и zi = 0, если Fi min.

Слайд 18

ПРИМЕР 2
Пользуясь описанным выше методом свертки, решить многокритериальную задачу с булевыми

переменными вида:

Слайд 19

Условия свертки
Для того, чтобы преобразовать (1) в однокритериальную задачу, следует определить

максимальные и минимальные значения F1 и F2.

Слайд 20

Поиск максимальной величины F1

Слайд 21

Решение задачи (2) методом типа ветвей и границ
S
17 1

0 10
1 17 0 15
1 0 1 0
-∞ 12 15 10
-∞ 1 0 12 F1 max = 12

Слайд 22

Поиск минимальной величины F1 сводится к решению задачи (3):

Слайд 23

Решение задачи (3) методом типа ветвей и границ
S
7 1

0 0
1 2 0 0
1 7 0 2 1 5 0 0
5 1 +∞ 0 8 1 +∞ 0

F1 min = 5.

Слайд 24

Поиск максимальной величины F2

Слайд 25

Решение задачи (4) методом типа ветвей и границ
s
1

14 11 0
14 1 10 0 11 1 7 0
1 -∞ 0 12 1 10 0 8 1 11 0 9
1 0 1 0 1 0 1 0
-∞ 7 -∞ 9 -∞ -∞ -∞ 6

F2 max = 9

Слайд 26

Поиск минимальной величины F2

Слайд 27

Решение задачи (5) методом типа ветвей и границ
S
3 1

0 0
7 3 4 0
1 0 1 0
5 3 6 4 2 0
1 0 1 0 1 0
+∞ +∞ +∞ +∞ 7 + ∞ 5 +∞
1 0 1 0 1 0 1 0

F2 min = 5

Слайд 28

Использование эталонов для преобразования(1) в однокритериальную задачу

Слайд 29

Вид системы (6) после преобразований

Слайд 30

Решение задачи (7) методом ветвей и границ
S
F1=12; F2=5; φ=0

F1=10; F2=5; φ =0,0816
1 0
F1=12; F2=7; φ=0.25. F1=12; F2=5; φ=0
1 0
F1=12; F2=5; φ=0. F1=10; F2=∞; φ=∞.
1 0
F1=-∞; F2=+∞; φ=∞. . F1=12; F2=5; φ=0.
1 0

X opt ={1, 0, 1, 0}; F1 = 12; F2 = 5.

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

Содержание

Содержание:1. Задачи с булевыми переменными 1.1. Фронтальный спуск по дереву ветвлений1.2. Поиск

ОБЩИЕ СВОЙСТВА МЕТОДОВ ТИПА ВЕТВЕЙ И ГРАНИЦ1. Метод вычисления оценки таков,

Часть 1Решение задач с булевыми переменными

1.1. Фронтальный спуск по дереву ветвлений

Содержательное описание алгоритмаШаг 1. На построенной части дерева ветвлений выбирается вершина

ПРИМЕР 1Пусть задана задача о ранце вида:

ДЕРЕВО ВЕТВЛЕНИЙXXopt = {0, 0, 1, 1}; R=12.

Достоинства и недостатки фронтального спуска по дереву ветвлений: Достоинства: шанс на неполный

САМОСТОЯТЕЛЬНОПользуясь фронтальным спуском решить задачу вида: