Методы типа ветвей и границ - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Методы типа ветвей и границ. Доклад-сообщение содержит 31 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Методы типа ветвей и границ ТПР Лекция № 2-10

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

ОБЩИЕ СВОЙСТВА МЕТОДОВ ТИПА ВЕТВЕЙ И ГРАНИЦ 1. Метод вычисления оценки таков, что по мере спуска по дереву ветвлений оценка не улучшается. 2. Спуск по дереву ветвлений прекращается, если выбранная вершина обладает следующими свойствами: оценка этой вершины является наилучшей; существует возможность определить значения всех переменных, причем оценка остается неизменной.

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

ДЕРЕВО ВЕТВЛЕНИЙ

Слайд 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 ЧАСТЬ 2 Решение многокритериальных задач методами типа ветвей и границ

Слайд 17

Описание слайда:

Основные положения Свертка критериев с помощью эталонов позволяет получить новую целевую функцию вида: где Fi - i– я целевая функция, zi = 1, если Fi max, и zi = 0, если Fi min.