Курсовая работа: Решение задачи на нахождение оптимального пути методом ветвей и границ

Москва 2008г.

Содержание:

Постановка задачи. 3

1. Теоретическая часть. 4

1.1. Математическая постановка задачи коммивояжёра. 4

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

1.3. Алгоритм решения. 5

1.4. Схема решения задачи. 5

Практическая часть. 6

Заключение. 7

Список литературы: 8

Приложение 1. 9

Приложение 2. 11

Постановка задачи.

Фирма «Ветка Сакуры» занимается выращиванием и доставкой самых любимых в Японии растений, в частности, маленьких комнатных и садовых деревьев «бансай». Такие деревья заказывают только шесть магазинов города Москвы; все они расположены в разных районах города. Доставку осуществляет только один водитель на единственной машине. Заказы поступают один раз в две недели от каждого магазина. Водитель должен завести деревья во все шесть магазинов за один день и вернуться обратно на фирму, чтобы отдать соответствующие документы в бухгалтерию, а также, чтобы поставить машину в гараж. Начальной точкой отправления машины также является фирма, т.к. машина, склад и бухгалтерия находятся в одном месте – на фирме.

В последнее время администрация фирмы стала замечать, что вследствие неоптимального пути, по которому ездил водитель в магазины, расходы фирмы сильно увеличились. Это объясняется тем, что водитель особо не задумывается о маршруте поставок, а может быть, даже и удлиняет его, т.к. у него почасовая оплата, а бензин оплачивается фирмой. Также, из-за того, что часто водителем был выбран неоптимальный маршрут доставки деревьев, а администрация не обращала на эту часть своей деятельности никакого внимания, заказы иногда не доставлялись за один день, и фирма была вынуждена платить неустойки, что также уменьшало её прибыль.

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

1. Теоретическая часть.

Коммивояжёр, находясь в одном из городов должен посетить ещё n-1 город. При этом должны выполнятся следующие условия:

•каждый город он должен посетить только один раз;

•вернутся туда же, откуда выехал;

•затраты на поездку должны быть минимальными.

1.1. Математическая постановка задачи коммивояжёра

Дан ориентированный граф G, имеющий n вершин и дуг. Необходимо найти длину кратчайшего замкнутого маршрута, содержащего каждую вершину только один раз.

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

Нашу задачу будем решать методом ветвей и границ. Решение будем изображать на дереве. Дерево – ориентированный граф без циклов.

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

1.3. Алгоритм решения

Алгоритм содержит две основные процедуры:

--> ЧИТАТЬ ПОЛНОСТЬЮ <--