- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
§ 2. Метод ветвей и границ презентация
Содержание
- 1. § 2. Метод ветвей и границ
- 2. Задача оптимизации: где конечное
- 3. Ветвление – это функция которая каждому подмножеству
- 4. Оценка – это функция
- 5. Пусть L – это список подмножеств множества
- 6. Общая схема метода ветвей и границ
- 7. На каждом шаге необходимо обновлять рекорд
- 8. Пример: задача о рюкзаке. Даны рюкзак
- 9. Математическая модель задачи о рюкзаке:
- 10. Метод ветвей и границ схема ветвления:
- 11. Нет ветвления, если или
Задача оптимизации: где конечное множество допустимых решений множество всех подмножеств множества
Слайд 2Задача оптимизации:
где конечное множество
допустимых решений
множество всех подмножеств
множества
Слайд 3Ветвление – это функция
которая каждому подмножеству
множества
ставит в соответствие некоторое
его разбиение
таким образом:
таким образом:
Слайд 4Оценка – это функция
Величина оценивает сверху значения
функции на множестве и совпадает
с ней
на множествах, состоящих из одного элемента
Для вычисления оценки решается упрощенная
оптимизационная задача
на множествах, состоящих из одного элемента
Для вычисления оценки решается упрощенная
оптимизационная задача
Слайд 6Общая схема метода ветвей и границ
Шаг 0: ищется начальное решение
для k
=1,2,…
Шаг k: если список L=0, то стоп, - решение
иначе выбрать из списка подмножество A
вычислить оценку
если , то
иначе
Шаг k: если список L=0, то стоп, - решение
иначе выбрать из списка подмножество A
вычислить оценку
если , то
иначе
Слайд 7
На каждом шаге необходимо обновлять рекорд при обнаружении решений лучших, чем
текущее рекордное решение.
Для реализации метода необходимо указать правила:
вычисления оценки;
получения разбиения;
выбора подмножества (подзадачи) из списка L.
Для реализации метода необходимо указать правила:
вычисления оценки;
получения разбиения;
выбора подмножества (подзадачи) из списка L.
Слайд 8
Пример: задача о рюкзаке.
Даны рюкзак грузоподъемностью V и n предметов, каждый
из которых имеет вес aj и стоимость cj, j=1,…,n. Необходимо заполнить рюкзак набором предметов с наибольшей общей стоимостью.
n = 4, V = 10
j 1 2 3 4
cj 20 16 11 7
aj 5 4 3 2
n = 4, V = 10
j 1 2 3 4
cj 20 16 11 7
aj 5 4 3 2
