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

Автор работы: Пользователь скрыл имя, 16 Апреля 2014 в 17:25, курсовая работа

Краткое описание

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

Содержание

Введение…………………………………………………………………..…...6
1 Общие сведения о задаче коммивояжёра………………………………....8
Экономические ситуации, приводящие к задаче коммивояжера…....9
Постановка и математическая модель задачи коммивояжера…..…10
Методы решения задачи коммивояжера………………………..……12
Метод ветвей и границ………………………………………………….12
Венгерский метод…………………………………………..…………..14
Применение методов решения задачи коммивояжера на практике...16
3.1 Решение задачи коммивояжера методом ветвей и границ….……….16
3.2 Решение задачи коммивояжера венгерским методом……………….…25
Заключение……………………………………………………………..….…32
Глоссарий ………………………………………………………………..…..33
Список используемых источников…………

Вложенные файлы: 1 файл

TGTU_080100_62_009_-_KR_Kozhevnikova_V_A_BEK23..docx

— 168.82 Кб (Скачать файл)

 

 

СОДЕРЖАНИЕ

 

Введение…………………………………………………………………..…...6

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

    1. Экономические ситуации, приводящие к задаче коммивояжера…....9
    2. Постановка и математическая модель задачи коммивояжера…..…10
  1. Методы решения задачи коммивояжера………………………..……12
    1. Метод ветвей и границ………………………………………………….12
    2. Венгерский метод…………………………………………..…………..14
  2. Применение методов решения задачи коммивояжера на практике...16

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

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

Заключение……………………………………………………………..….…32

Глоссарий ………………………………………………………………..…..33

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

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

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

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

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

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

Задача коммивояжера находит много практических применений в таких областях как:

  • оптимизация маршрутов;
  • расчет авиационных линий;
  • конвейерное производство;
  • исследование ДНК и др.

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

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

Исходя из цели, поставлены следующие задачи:

  • изучить постановку и особенности задачи коммивояжера;
  • рассмотреть методы решения задачи коммивояжера;

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

 

Коммивояжер — разъездной сбытовой посредник.

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

Комбинаторика – раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.

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

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

В задаче коммивояжера целевой функцией, которую надо минимизировать, является стоимость обхода.

Особенностью задачи о коммивояжере является необходимость дополнительно учитывать расстояния от города до города, которые предполагаются известными. Эти «расстояния» можно заменить на количество затраченного времени, стоимость проезда или предполагать другие произвольные значения.

В общем случае мы даже не предполагаем, что стоимость проезда из I в J обязательно совпадает со стоимостью обратного проезда из J в I. Данная задача соединяет в себе простоту условия и сложность решения, обусловленную большими размерами поискового пространства.

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

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

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

 

 

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

 

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

Как сделать оптимальным выбор маршрута, отдать предпочтение определённым товарам (при одинаковом спросе), чтобы прибыль от продажи была максимальной? Решив задачу коммивояжера, можно получить ответы на все эти вопросы.

Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:

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

 

 

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

 

Постановка задачи. Коммивояжер должен объехать n городов. Известны затраты (стоимостные, временные, расстояния) на переезд между i-м и j-м  городом, которые заданы в виде матрицы. Коммивояжер, выехав из исходного города, должен объехать все города, посетив каждый один раз, и вернуться в исходный. Требуется определить в каком порядке следует объезжать города, чтобы суммарные затраты или расстояние были минимальными.

Математическая модель. Задача коммивояжера может быть сформулирована как целочисленная введением переменных xij=1, если маршрут включает переезд из города i непосредственно в город j и xij=0 в противном случае. Тогда можно задать математическую модель задачи, то есть записать целевую функцию и систему ограничений:

 

Ограничения: 

 

 

n - число городов.

Сij ,  i, j=1,n - матрица затрат, где Cij затраты на переход из i-го города в j-й.

xij - матрица переходов с компонентами:

xij = 1, если коммивояжер совершает переход из i-го города в j-й,

xij  = 0, если не совершает перехода, где i, j = 1..n

- некоторые вещественные значения

Условия (2) – (4) в совокупности обеспечивают, что каждая переменная равна или нулю, или единице. При этом ограничения (2), (3) выражают условия, что коммивояжер побывает в каждом городе один раз, в него прибыв (ограничение (2)), и один раз из него выехав (ограничение (3)). Однако этих ограничений не достаточно для постановки задачи коммивояжера, так как они не исключают решения, где вместо простого цикла, проходящего через n вершин, отыскиваются 2 и более отдельных цикла (подцикла), проходящего через меньшее число вершин. Поэтому задача, описанная уравнениями (2) – (4) должна быть дополнена ограничениями, обеспечивающими связность искомого цикла. Для того чтобы исключить при постановке задачи все возможные подциклы в систему ограничений задачи включают следующее ограничение:

 где:

 

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

 

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

 

Метод ветвей и границ ("поиск с возвратом", "backtracking") – один из наиболее эффективных и быстрых методов решения задачи о коммивояжере, был разработан Литтлом, Мерти, Суини, Кэрелом в 1963 г. Представляет собой итеративную схему неявного (улучшенного) перебора, который состоит в отбрасывании заведомо неоптимальных решений и является одной из самых эффективных процедур в группе методов ветвей и границ.

Идея метода. Пусть S0 – множество всех допустимых замкнутых маршрутов (циклов) задачи о коммивояжере с n городами и матрицей затрат:

 

Множество S0 состоит из (n-1)! допустимых решений. Метод ветвей и границ основан на разбиении множества S0 на два непересекающихся подмножества и на вычислении оценок каждого из них. Далее подмножество с минимальной оценкой (стоимостью) разбивается на два подмножества и вычисляются их оценки. На каждом шаге выбирается подмножество с наименьшей из всех полученных на этом шаге оценок и производится его разбиение на два подмножества. В конце концов получаем подмножество, содержащее один цикл (замкнутый маршрут, удовлетворяющий наложенным ограничениям), стоимость которого минимальна.

Алгоритм метода: метод состоит из предварительного этапа и общего, который повторяется необходимое число раз.

Предварительный этап. Приведение матрицы затрат {Cij}, вычисление нижней оценки стоимости маршрута r.

Вычисление наименьшего элемента по каждой строке (константы приведения):

 

Переход к новой матрице с элементами:

 

Вычисление наименьшего элемента по каждому столбцу (константы приведения):

 

Переход к новой матрице с элементами:

 

Вычисление нижней оценки стоимости маршрута (сумма констант приведения):

(11)

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

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

 

Выбор нулевого элемента, которому соответствует максимальный штраф. Если таких элементов несколько, то выбирается любой из них. Разбиение множества всех допустимых маршрутов S0 на два подмножества: подмножество содержащее ребро (h,k) – ; подмножество, не содержащее ребро (h,k) – .

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

Вычисление оценок затрат по всем маршрутам, входящим в каждое подмножество. Обозначим за минимальную оценку стоимости маршрутов, вошедших в множество , т.е. не содержащих ребро (h,k). Для оценка затрат:

 

Информация о работе Применение методов решения задачи коммивояжера на практике