Применение методов решения задачи коммивояжера на практике - Курсовая работа

Задача коммивояжера, известная также как задача о сверлильном станке или алгоритм коммивояжера была поставлена в 1934 году. Данная задача является важной и трудно решаемой. Но чтобы предприятие успешно развивалось и приносило прибыль, нужно взвешивать все плюсы и минусы не только вопросов касающихся затрат на закупку сырья и оборудования, но и вопросов связанных с транспортировкой груза к месту реализации, с нахождением оптимального маршрута и минимизацией затрат. Именно задача коммивояжера помогает найти кратчайший путь с минимальными затратами. Задача коммивояжера находит много практических применений в таких областях как: - оптимизация маршрутов;Задача коммивояжера является одной из знаменитых задач теории комбинаторики и широко применяется при разработке программного обеспечения. Комбинаторика - раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами. Задача коммивояжера также является типичной задачей оптимизации, которая широко применяется при разработке программного обеспечения. В своей области (оптимизации дискретных задач) она служит своеобразным катализатором, стимулирующим разработку наиболее эффективных методов, алгоритмов и способов их машинной реализации. Особенностью задачи о коммивояжере является необходимость дополнительно учитывать расстояния от города до города, которые предполагаются известными.Задача коммивояжера непосредственным образом связана с экономикой, т.к. суть задачи коммивояжера состоит в отыскании маршрута минимальной длины с посещением каждого города ровно один раз и с возвращением в исходную точку. В задаче коммивояжера целевой функцией, которую надо минимизировать, является стоимость обхода. Как сделать оптимальным выбор маршрута, отдать предпочтение определенным товарам (при одинаковом спросе), чтобы прибыль от продажи была максимальной?Коммивояжер должен объехать n городов. Известны затраты (стоимостные, временные, расстояния) на переезд между i-м и j-м городом, которые заданы в виде матрицы. Коммивояжер, выехав из исходного города, должен объехать все города, посетив каждый один раз, и вернуться в исходный. Задача коммивояжера может быть сформулирована как целочисленная введением переменных xij=1, если маршрут включает переезд из города i непосредственно в город j и xij=0 в противном случае. Cij, i, j=1,n - матрица затрат, где Cij затраты на переход из i-го города в j-й. xij - матрица переходов с компонентами: xij = 1, если коммивояжер совершает переход из i-го города в j-й, xij = 0, если не совершает перехода, где i, j = 1..nМетод ветвей и границ ("поиск с возвратом", "backtracking") - один из наиболее эффективных и быстрых методов решения задачи о коммивояжере, был разработан Литтлом, Мерти, Суини, Кэрелом в 1963 г. Пусть S0 - множество всех допустимых замкнутых маршрутов (циклов) задачи о коммивояжере с n городами и матрицей затрат: Множество S0 состоит из (n-1)! допустимых решений. Далее подмножество с минимальной оценкой (стоимостью) разбивается на два подмножества и вычисляются их оценки. Разбиение множества всех допустимых маршрутов S0 на два подмножества: подмножество содержащее ребро (h,k) -; подмножество, не содержащее ребро (h,k) - Примечание: максимальный штраф означает, что исключение из решения переезда, соответствующего нулевому элементу, приведет к максимальному увеличению стоимости оптимального маршрута. Для оценка затрат: При вычислении оценки затрат для учитывают, что, если ребро (h,k) входит в маршрут, то ребро (k,h) не может входить в маршрут, поэтому принимаем: ; если в маршрут включено ребро (h,k), то ни одно другое ребро, начинающееся в пункте h или заканчивающееся в пункте k не может входить в маршрут, поэтому строка h и столбец k вычеркиваются.Основная идея венгерского метода заключается в переходе от исходной квадратной матрицы стоимости С к эквивалентной ей матрице Сэ с неотрицательными элементами и системой n независимых нулей, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу. Преобразование в столбцах: Преобразование в строках: После вычитания минимальных элементов, в каждой строке и в каждом столбце будет, как минимум один ноль, проделав данные вычисления, получаем полностью редуцированную матрицу. 2) Рассматривая строки и столбцы матрицы сверху вниз, слева направо поочередно, отмечаем первый попавшийся ноль и берем его в квадратные скобки, другие нули в этой же строке и в этом же столбце вычеркиваем.Сумма констант приведения определяет нижнюю границу H: H = ?di ?dj Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*). Наибольшая сумма констант приведения равна (1 3) = 4 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).

Содержание

Введение

1. Общие сведения о задаче коммивояжера

1.1 Экономические ситуации, приводящие к задаче коммивояжера

1.2 Постановка и математическая модель задачи коммивояжера

2. Методы решения задачи коммивояжера

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

2.2 Венгерский метод

3. Применение методов решения задачи коммивояжера на практике

3.1 Решение задачи коммивояжера методом ветвей и границ

3.2 Решение задачи коммивояжера венгерским методом

Заключение

Глоссарий

Список используемых источников

Приложение А Дерево ветвлений