Анализ метода ветвей и границ в задачах линейного программирования

При решении многомерных задач оптимизации предлагается совместное применение методов ветвей и границ и динамического программирования. На первом этапе задача решается методом динамического программирования отдельно по каждому из ограничений. Последовательности, полученные в результате решения функционального уравнения динамического программирования, в дальнейшем используется для оценки верхней (нижней) границы целевой функции. На втором этапе задача решается методом ветвей и границ. При использовании этого метода определяется способ разбиения всего множества допустимых вариантов на подмножества, то есть способ построения дерева возможных вариантов, и способ оценки верхней границы целевой функции.
Комплексное применение методов динамического программирования и ветвей и границ позволяет повысить эффективность решения дискретных задач оптимизации. При решении задач большой размерности с целью уменьшения членов оптимальной последовательности используются дополнительные условия отсечения.

ВВЕДЕНИЕ 3
1 ОПИСАНИЕ ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ 4
2 МЕТОД ВЕТВЕЙ И ГРАНИЦ 5
2.1 Описание метода ветвей и границ 5
2.2 Алгоритм действия метода ветвей и границ 5
2.3 Общий алгоритм решения задач с помощью метода границ и ветвей, его суть 7
2.4 Пример использования метода ветвей и границ 8
3 ПРИМЕНЕНИЕ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧ РАЗЛИЧНОГО ТИПА 9
3.1 Применение метода ветвей и границ для задач календарного планирования 9
3.2 Задача коммивояжера 12
3.2.1 Формулировка задачи 12
3.2.2 Метод ветвей и границ 12
3.3 Применение метода ветвей и границ для задач календарного планирования 15
ЗАКЛЮЧЕНИЕ 19
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 20