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

Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче комивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям.

Введение 3
1. Понятие о методе ветвей и границ 5
2. Общая схема метода ветвей и границ 6
3. Применение метода ветвей и границ в решении прикладных задач 8
3.1. Задача о ранце 8
3.1.1. Математическая модель задачи. 8
3.1.2. Пример решения задачи о ранце 9
3.2. Задача Коммивояжера 13
3.2.1 Определения 14
3.2.2. Постановка задачи 15
3.2.3. Решение задачи 15
3.2.4. Разбиение множества маршрутов на подмножества 17
3.2.5. Пример решения задачи коммивояжера методом ветвей и границ 17
3.3. Решение целочисленных задач линейного программирования 24
3.3.1. Алгоритм решения: 24
3.3.2 Иллюстрация метода ветвей и границ на примере 27
Заключение 31
Список использованных источников: 32