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

Июль 30, 2022

Главная
Информатика
§ 2. Метод ветвей и границ

Содержание

2. Задача оптимизации: где конечное множество допустимых решений множество всех подмножеств множества
3. Ветвление – это функция которая каждому подмножеству множества ставит в соответствие некоторое его разбиение таким образом:
4. Оценка – это функция Величина оценивает сверху значения функции на множестве и совпадает с ней на
5. Пусть L – это список подмножеств множества Рекорд – это число, которое:
6. Общая схема метода ветвей и границ Шаг 0: ищется начальное решение для k =1,2,… Шаг k:
7. На каждом шаге необходимо обновлять рекорд при обнаружении решений лучших, чем текущее рекордное решение. Для реализации
8. Пример: задача о рюкзаке. Даны рюкзак грузоподъемностью V и n предметов, каждый из которых имеет вес
9. Математическая модель задачи о рюкзаке:
10. Метод ветвей и границ схема ветвления: пусть определены значения Оценки:
11. Нет ветвления, если или
13. Скачать презентацию

Слайд 2

Задача оптимизации:
где конечное множество
допустимых решений
множество всех подмножеств
множества

Слайд 3

Ветвление – это функция
которая каждому подмножеству
множества
ставит в соответствие некоторое

его разбиение
таким образом:

Слайд 4

Оценка – это функция
Величина оценивает сверху значения
функции на множестве и совпадает с

ней
на множествах, состоящих из одного элемента
Для вычисления оценки решается упрощенная
оптимизационная задача

Слайд 5

Пусть L – это список подмножеств множества
Рекорд – это число, которое:

Слайд 6

Общая схема метода ветвей и границ
Шаг 0: ищется начальное решение
для k

=1,2,…
Шаг k: если список L=0, то стоп, - решение
иначе выбрать из списка подмножество A
вычислить оценку
если , то
иначе

Слайд 7

На каждом шаге необходимо обновлять рекорд при обнаружении решений лучших, чем

текущее рекордное решение.
Для реализации метода необходимо указать правила:
вычисления оценки;
получения разбиения;
выбора подмножества (подзадачи) из списка 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

Слайд 9

Математическая модель задачи о рюкзаке:

Слайд 10

Метод ветвей и границ
схема ветвления:
пусть определены значения
Оценки:

Слайд 11

Нет ветвления, если
или