Курсовая работа: Решение задачи на нахождение оптимального пути методом ветвей и границ
•оценка нулевых элементов.
Матрица называется приведённой, если в каждой строке и в каждом столбце содержится нулевой элемент.
Для того чтобы привести матрицу, нужно из каждой строки вычесть соответствующий минимальный элемент. Далее вычесть минимальный элемент только из тех столбцов, где нет нулевого элемента. Сумма всех минимальных элементов обозначается H и является возможной минимальной длинной контура.
Оценку нулевых элементов будем обозначать буквой θ . Для того, чтобы найти оценку нулевого элемента, находящегося на пересечении i – ой строки и j –го столбца, нужно найти сумму минимального элемента i – ой строки и минимального элемента j – го столбца.
1.4. Схема решения задачи
1)Приведение исходной матрицы.
2)Оценка нулевых элементов. Выбираем нулевой элемент с максимальной оценкой
3)Раздробим множество Q на множество Qij и Qi j . Множество Qij получает дополнительную оценку θ ij .
4)Для того чтобы найти границу множества Qij , вычеркнем из приведённой матрицы i – ую строку и j –ый столбец.
5)Поставим запрет на движение по дуге vij vij .
6)Вернёмся к пункту 1.
Практическая часть.
Приведённая матрица С1 в Приложении 1 содержит затраты на доставку (бензин и оплата труда шофёра) из одного магазина в другой. Например, если из второго магазина поехать в пятый, то затраты фирмы составят 3 денежных единицы. Эта стоимость включает в себя только затраты на бензин и заработную плату шофёра. Так как за определённым магазином не может следовать тот же магазин, то соответствующее время движения предполагается равным бесконечности. Именно поэтому на диагонали и стоят знаки бесконечности. Первым элементом является фирма.
Находим возможное минимальное время рейса. Складываем элементы приведения матрицы, получаем 42 минуты. Затем проводим оценку нулевых элементов, складывая минимальные элементы в соответствующих столбцах и строках. Выбираем максимальную оценку – 10 (правило минимакса). В матрице С3 вычёркиваем 7-й столбец и 3-ую строку т.к. именно на их пересечении и стоит нулевой элемент с максимальной оценкой - 10. Получаем матрицу С4 . ставим запрет на движение из седьмого магазина в третий, т.е. из 7 в 3 магазин ехать нельзя (т.к. предыдущее вычёркивание строки и столбца означает путь из 3 в 7 магазин).
Одновременно начинаем ветвить множество Q . Сначала разделим его на Q 37 и Q 37 с чертой. К Q 37 с чертой прибавляем оценку нулевого элемента 10. Получаем 52. К Q 37 ничего не нужно прибавлять и оценка остаётся 42 (т.к. следующая матрица С4 оказалась приведённой). Продолжаем ветвить Q 37 т.к. у данного элемента наименьшая оценка – 42 (42<52). Проделывая и дальше эти процедуры, получаем минимальный по затратам путь, равный 42 денежным единицам (возвратов не было, т.к. все последующие матрицы оказались приведёнными (нулевые элементы в каждой строке и столбце)).
Оптимальный путь выглядит так: из гаража в третий магазин, из третьего в седьмой, затем в четвёртый, после в шестой, затем во второй потом в пятый и снова в гараж компании.
Заключение.
Задача коммивояжёра позволяет решать не только задачи на определение минимального маршрута по времени и затратам труда и денежных средств, но и целый ряд других оптимизационных задач из разных областей.
Поставленная задача о доставке деревьев «бансай» была решена с помощью метода ветвей и границ, который является наиболее простым, удобным и эффективным из известных методов.
Теперь компания «Ветка сакуры» благодаря полученному решению, будет эффективно расходовать ресурсы и время на обслуживание магазинов, что значительно увеличит её прибыль и наладит отношения с заказчиками, которых раньше водитель иногда не успевал обслужить. А у водителя теперь не будет возможностей увеличивать часы своей работы и расходы на бензин, т.к. все тонкости данного маршрута (пробки в различное время суток, затраты бензина на маршруте, разрешённый скоростной режим) будут известны администрации досконально. Таким образом, выявление данной проблемы и её решение с помощью метода ветвей и границ, помогло фирме справиться с очень многими трудностями по доставке деревьев бансай. С помощью этого метода администрация может оптимизировать и другие маршруты по доставке другого рода растений.
Список литературы:
1. Х.А. Таха « Введение в исследование операций». М. Изд. «ВИЛЬЯМС», 2001г. Шестое издание.
2. Е. П. Липатов. «Теория графов и её применения». М. Изд. «ЗНАНИЕ», 1986г.
3. В. М. Бондарев «Основы программирования» 1998г., Изд. дом «Феникс»
Приложение 1.
|
1 |
2 |
3 |
4 |
К-во Просмотров: 426
Бесплатно скачать Курсовая работа: Решение задачи на нахождение оптимального пути методом ветвей и границ
|