РГР_М_1_. Решение задач линейного программирования в пакетах Mathcad и ms excel
 Скачать 1.5 Mb.
|
Лабораторная работа 4. Реализация алгоритмов решения задачи коммивояжёра.Задача коммивояжера и ее модификации часто встречаются на практике, например, при планировании различных перевозок [6,7]. Она может быть сформулирована следующим образом. Имеется nгородов, при этом расстояния между любой парой городов iи jизвестны и составляют cij, i,j = 1,…,n. Если между городами нет пути, то cij =  . Также полагают, что cii = , i = 1,…,n. Таким образом, исходные данные задачи коммивояжера задаются матрицей C: . Коммивояжер, выезжая из какого-либо города, должен посетить все города, побывав в каждом из них ровно один раз, и вернуться в исходный город. Объезд городов, удовлетворяющих этим требованиям, называется маршрутом коммивояжера. Длина маршрута равна сумме расстояний всех входящих в маршрут переездов из города в город. Требуется найти маршрут минимальной длины. Математическая модель задачи коммивояжера имеет и другие интерпретации, например, задача о перенастройке оборудования, задача о прокладке коммуникаций и другие [7]. Для решения задачи коммивояжера разработан ряд алгоритмов точного и приближенного решения: метод ветвей и границ [3], алгоритмы локального поиска [6] и другие. В случае небольших n (n < 10) задача коммивояжера может быть решена методом полного перебора всех возможных маршрутов. Число таких маршрутов равно n!/2. При больших n точное решение задачи, как и в случае задачи о рюкзаке, может потребовать значительных затрат машинного времени. Поэтому актуальной является разработка приближенных алгоритмов. Самый известный приближенный алгоритм – это так называемый алгоритм “иди в ближайший” или “жадный” алгоритм. Он заключается в следующем. Из текущего города коммивояжер идет в ближайший город, в котором он еще не был, а после обхода всех городов возвращается в исходный город. Варианты заданий. Разработать алгоритм полного перебора и «жадный» алгоритм для задачи коммивояжера [8]. Найти точное и приближенное решение задачи коммивояжера, используя реализованные алгоритмы.
|