ВВЕДЕНИЕ 2
ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ. ПОНЯТИЕ «МЕТОДА ВЕТВЕЙ» 4
1.1. Дискретное программирование 4+4
1.2. Дискретные оптимизационные задачи 5
1.3. Сущность метода ветвей и границ 6
ГЛАВА 2. МЕТОДЫ ВЕТВЕЙ ДЛЯ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ 9
2.1. Алгоритм метода ветвей и границ 9
2.2. Применение метода ветвей на примере «задачи коммивояжера» 12
ЗАКЛЮЧЕНИЕ 21
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 22
Краткое содержание работы:
ВВЕДЕНИЕ
Дискретная оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.
Необходимость принятия наилучших решений так же стара, как само человечество. Испокон веку люди, приступая к осуществлению своих мероприятий, раздумывали над их возможными последствиями и принимали решения, выбирая тем или другим образом зависящие от них параметры - способы организации мероприятий. Но до поры, до времени решения могли приниматься без специального математического анализа, просто на основе опыта и здравого смысла.
Возьмем пример: человек вышел утром из дому, чтобы ехать на работу. По ходу дела ему приходится принять целый ряд решений: брать ли с собой зонтик? В каком месте перейти улицу? Каким видом транспорта воспользоваться? И так далее. Разумеется, все эти решения человек принимает без специальных расчетов, просто опираясь на имеющийся у него опыт и на здравый смысл. Для обоснования таких решений никакая наука не нужна, да вряд ли понадобится и в дальнейшем.
Однако возьмем другой пример. Допусти, организуется работа городского транспорта. В нашем распоряжении имеется какое-то количество транспортных средств. Необходимо принять ряд решений, например: какое количество и каких транспортных средств направить по тому или другому маршруту? Как изменять частоту следования машин в зависимости от времени суток? Где поместить остановки? И так далее.
Эти решения являются гораздо более ответственными, чем решения предыдущего примера. В силу сложности явления последствия каждого из них не столь ясны; для того, чтобы представить себе эти последствия, нужно провести расчеты. А главное, от этих решений гораздо больше зависит. В первом примере неправильный выбор решения затронет интересы одного человека; во втором - может отразиться на деловой жизни целого города.
Выбранное решение должно по возможности гарантировать нас от ошибок, связанных с неточным прогнозированием, и быть достаточно эффективным для широкого круга условий. Для обоснования такого решения приводится в действие сложная система математических расчетов. Например, применяется метод ветвей для решения задач дискретного программирования.
Целью курсовой работы является изучение метода ветвей для решения задач дискретного программирования.
Задачами курсовой работы является:
- рассмотрение теоретических основ дискретного программирования, а также изучение сущности понятия «метод ветвей;
- анализ метода ветвей для решения задач дискретного программирования.
Курсовая работа состоит из введения, двух глав, заключения и списка использованной литературы.
В нашей компании вы можете заказать консультацию по любой учебной работе от 300 руб. Оформите заказ, а договор и кассовый чек послужат вам гарантией сохранности ваших средств. Кроме того, вы можете изменить план текущей работы на свой, а наши авторы переработают основное содержание под ваши требования