Автор работы: Пользователь скрыл имя, 02 Ноября 2012 в 08:38, курсовая работа
При решении многомерных задач оптимизации предлагается совместное применение методов ветвей и границ и динамического программирования. На первом этапе задача решается методом динамического программирования отдельно по каждому из ограничений. Последовательности, полученные в результате решения функционального уравнения динамического программирования, в дальнейшем используется для оценки верхней (нижней) границы целевой функции. На втором этапе задача решается методом ветвей и границ. При использовании этого метода определяется способ разбиения всего множества допустимых вариантов на подмножества, то есть способ построения дерева возможных вариантов, и способ оценки верхней границы целевой функции.
Комплексное применение методов динамического программирования и ветвей и границ позволяет повысить эффективность решения дискретных задач оптимизации. При решении задач большой размерности с целью уменьшения членов оптимальной последовательности используются дополнительные условия отсечения.
ВВЕДЕНИЕ 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
Конечная вершина определяет вариант (последовательность) = 3, 1, 5, 2, 4 с наилучшей оценкой ∆ = 20. Поэтому данный вариант является оптимальным.
Непосредственной проверкой убеждаемся, что время обработки всей последовательности деталей для этого варианта совпадает со значением оценки-прогноза и является минимальным:
ЗАКЛЮЧЕНИЕ
Метод ветвей и границ является универсальным методом решения комбинаторных задач дискретного программирования. Сложность практического применения метода заключается в трудностях нахождения способа ветвления множества на подмножества и вычисления соответствующих оценок, которые зависят от специфики конкретной задачи.
В ходе выполнения курсовой работы были рассмотрены различные задачи линейного программирования, которые решаются методом ветвей и границ, что доказывает его универсальность и простоту в использовании.
Также пришли к выводу, что метод ветвей и границ — один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.
Комплексное применение методов динамического программирования и ветвей и границ позволяет повысить эффективность решения дискретных задач оптимизации.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Информация о работе Анализ метода ветвей и границ в задачах линейного программирования