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

Смотреть слайды в полном размере
Презентация Методы типа ветвей и границ

Презентация «Методы типа ветвей и границ» содержит 31 слайд и доступна в формате ppt. Размер файла: 634.07 KB

Вы можете предварительно ознакомиться с презентацией, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати.

Просмотреть и скачать

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


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!