Решение задачи на нахождение оптимального пути методом ветвей и границ (стр. 1 из 2)

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

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

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

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

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

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

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

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

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

Дан ориентированный граф G, имеющий n вершин и

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

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

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

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

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

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

•приведение матрицы;

•оценка нулевых элементов.

Матрица называется приведённой, если в каждой строке и в каждом столбце содержится нулевой элемент.

Для того чтобы привести матрицу, нужно из каждой строки вычесть соответствующий минимальный элемент. Далее вычесть минимальный элемент только из тех столбцов, где нет нулевого элемента. Сумма всех минимальных элементов обозначается H и является возможной минимальной длинной контура.

Оценку нулевых элементов будем обозначать буквой θ. Для того, чтобы найти оценку нулевого элемента, находящегося на пересечении i – ой строки и j–го столбца, нужно найти сумму минимального элемента i – ой строки и минимального элемента j – го столбца.

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

1)Приведение исходной матрицы.

2)Оценка нулевых элементов. Выбираем нулевой элемент с максимальной оценкой

3)Раздробим множество Q на множество Q_ij и Q_i_j. Множество Q_ij получает дополнительную оценку θ_ij.

4)Для того чтобы найти границу множества Q_ij, вычеркнем из приведённой матрицы i – ую строку и j–ый столбец.

5)Поставим запрет на движение по дуге v_ijv_ij.

6)Вернёмся к пункту 1.

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

Приведённая матрица С₁в Приложении 1 содержит затраты на доставку (бензин и оплата труда шофёра) из одного магазина в другой. Например, если из второго магазина поехать в пятый, то затраты фирмы составят 3 денежных единицы. Эта стоимость включает в себя только затраты на бензин и заработную плату шофёра. Так как за определённым магазином не может следовать тот же магазин, то соответствующее время движения предполагается равным бесконечности. Именно поэтому на диагонали и стоят знаки бесконечности. Первым элементом является фирма.

Находим возможное минимальное время рейса. Складываем элементы приведения матрицы, получаем 42 минуты. Затем проводим оценку нулевых элементов, складывая минимальные элементы в соответствующих столбцах и строках. Выбираем максимальную оценку – 10 (правило минимакса). В матрице С₃вычёркиваем 7-й столбец и 3-ую строку т.к. именно на их пересечении и стоит нулевой элемент с максимальной оценкой - 10. Получаем матрицу С₄. ставим запрет на движение из седьмого магазина в третий, т.е. из 7 в 3 магазин ехать нельзя (т.к. предыдущее вычёркивание строки и столбца означает путь из 3 в 7 магазин).

Одновременно начинаем ветвить множество Q. Сначала разделим его на Q₃₇ и Q₃₇с чертой. К Q₃₇ с чертой прибавляем оценку нулевого элемента 10. Получаем 52. К Q₃₇ ничего не нужно прибавлять и оценка остаётся 42 (т.к. следующая матрица С4 оказалась приведённой). Продолжаем ветвить Q₃₇ т.к. у данного элемента наименьшая оценка – 42 (42<52). Проделывая и дальше эти процедуры, получаем минимальный по затратам путь, равный 42 денежным единицам (возвратов не было, т.к. все последующие матрицы оказались приведёнными (нулевые элементы в каждой строке и столбце)).

Оптимальный путь выглядит так: из гаража в третий магазин, из третьего в седьмой, затем в четвёртый, после в шестой, затем во второй потом в пятый и снова в гараж компании.

Заключение.

Задача коммивояжёра позволяет решать не только задачи на определение минимального маршрута по времени и затратам труда и денежных средств, но и целый ряд других оптимизационных задач из разных областей.

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

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

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

1. Х.А. Таха « Введение в исследование операций». М. Изд. «ВИЛЬЯМС», 2001г. Шестое издание.

2. Е. П. Липатов. «Теория графов и её применения». М. Изд. «ЗНАНИЕ», 1986г.

3. В. М. Бондарев «Основы программирования» 1998г., Изд. дом «Феникс»

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

1	2	3	4	5	6	7
1	∞	15	3	8	5	17	20	3
2	9	∞	7	25	3	8	10	3