Применение методов решения задачи коммивояжера на практике
Место задачи коммивояжера в теории комбинаторики с ее применением при разработке программного обеспечения. Постановка и математическая модель задачи коммивояжера. Особенности решения задачи коммивояжера методом ветвей и границ и венгерским методом.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 23.04.2014 |
| Размер файла | 225,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
Введение
1. Общие сведения о задаче коммивояжёра
1.1 Экономические ситуации, приводящие к задаче коммивояжера
1.2 Постановка и математическая модель задачи коммивояжера
2. Методы решения задачи коммивояжера
2.1 Метод ветвей и границ
2.2 Венгерский метод
3. Применение методов решения задачи коммивояжера на практике
3.1 Решение задачи коммивояжера методом ветвей и границ
3.2 Решение задачи коммивояжера венгерским методом
Заключение
Глоссарий
Список используемых источников
Приложение А Дерево ветвлений
Введение
Задача коммивояжера, известная также как задача о сверлильном станке или алгоритм коммивояжера была поставлена в 1934 году. Данная задача является важной и трудно решаемой.
В современном мире происходит стремительное развитие науки и техники. С каждым годом число предприятий по производству различного рода продукции становится всё больше и больше. Но чтобы предприятие успешно развивалось и приносило прибыль, нужно взвешивать все плюсы и минусы не только вопросов касающихся затрат на закупку сырья и оборудования, но и вопросов связанных с транспортировкой груза к месту реализации, с нахождением оптимального маршрута и минимизацией затрат.
Именно задача коммивояжера помогает найти кратчайший путь с минимальными затратами.
Задача коммивояжера находит много практических применений в таких областях как:
- оптимизация маршрутов;
- расчет авиационных линий;
- конвейерное производство;
- исследование ДНК и др.
Таким образом, поиск точных и приближенных способов решения задачи коммивояжера остается актуальным и с теоретической и с практической точек зрения.
Целью данной курсовой работы является рассмотрение экономических ситуаций приводящих к задаче коммивояжера, изучение методов решения задачи коммивояжера, решение задачи коммивояжера несколькими методами.
Исходя из цели, поставлены следующие задачи:
- изучить постановку и особенности задачи коммивояжера;
- рассмотреть методы решения задачи коммивояжера;
- ознакомиться с практическим применением задачи коммивояжера.
1. Общие сведения о задаче коммивояжера
коммивояжер задача комбинаторика математический
Коммивояжер -- разъездной сбытовой посредник.
Задача коммивояжера является одной из знаменитых задач теории комбинаторики и широко применяется при разработке программного обеспечения.
Комбинаторика - раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.
Задача коммивояжера также является типичной задачей оптимизации, которая широко применяется при разработке программного обеспечения. Задача о коммивояжере является упрощенной моделью для многих других задач дискретной оптимизации, а также часто является подзадачей.
В своей области (оптимизации дискретных задач) она служит своеобразным катализатором, стимулирующим разработку наиболее эффективных методов, алгоритмов и способов их машинной реализации.
В задаче коммивояжера целевой функцией, которую надо минимизировать, является стоимость обхода.
Особенностью задачи о коммивояжере является необходимость дополнительно учитывать расстояния от города до города, которые предполагаются известными. Эти «расстояния» можно заменить на количество затраченного времени, стоимость проезда или предполагать другие произвольные значения.
В общем случае мы даже не предполагаем, что стоимость проезда из I в J обязательно совпадает со стоимостью обратного проезда из J в I. Данная задача соединяет в себе простоту условия и сложность решения, обусловленную большими размерами поискового пространства.
Задача о гамильтоновых циклах в графе получила различные обобщения. Одно из этих обобщений - задача коммивояжера, имеющая ряд применений в исследовании операций, в частности при решении некоторых транспортных проблем.
На графах задача формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. Т.е. выйдя из стартовой вершины, посетить каждую вершину графа ровно один раз и вернуться в начальную по кратчайшему пути.
Гамильтонов путь (или гамильтонова цепь) - путь (цепь), содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.
1.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.1 Метод ветвей и границ
Метод ветвей и границ ("поиск с возвратом", "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). Для оценка затрат:
При вычислении оценки затрат для учитывают, что, если ребро (h,k) входит в маршрут, то ребро (k,h) не может входить в маршрут, поэтому принимаем: ; если в маршрут включено ребро (h,k), то ни одно другое ребро, начинающееся в пункте h или заканчивающееся в пункте k не может входить в маршрут, поэтому строка h и столбец k вычеркиваются. Полученная матрица приводится, т.е. выполняется предварительный этап алгоритма. Пусть сумма приводящих констант матрицы: .
Из множеств и для дальнейшего ветвления выбирается множество, имеющее меньшую оценку. При выборе нужно вернуться к шагу 1, используя на этом шаге приведенную матрицу, полученную на шаге 3.2. При выборе нужно вернуться к матрице , принять и привести полученную в результате матрицу, после чего перейти к шагу 2, используя на нем эту приведенную матрицу. Если несколько множеств имеют равную минимальную оценку, то дальнейшее ветвление производится для всех множеств с минимальной оценкой [17, c. 94].
Таким образом, метод ветвей и границ позволяет находить все оптимальные решения.
Алгоритм продолжается до тех пор, пока в подмножестве маршрутов с наименьшей оценкой не останется всего один маршрут. В расчетах это соответствует ситуации, когда исследуемая матрица имеет размерность . [18, c. 225].
2.2 Венгерский метод
Основная идея венгерского метода заключается в переходе от исходной квадратной матрицы стоимости С к эквивалентной ей матрице Сэ с неотрицательными элементами и системой n независимых нулей, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу.
Алгоритм венгерского метода:
1) Проводим предварительные преобразования матрицы C (получаем эквивалентную матрицу Сэ).
Преобразование в столбцах:
Преобразование в строках:
После вычитания минимальных элементов, в каждой строке и в каждом столбце будет, как минимум один ноль, проделав данные вычисления, получаем полностью редуцированную матрицу.
2) Рассматривая строки и столбцы матрицы сверху вниз, слева направо поочередно, отмечаем первый попавшийся ноль и берём его в квадратные скобки, другие нули в этой же строке и в этом же столбце вычеркиваем.
3) Затем, вычёркиваем строки и столбцы с возможно большим количеством нулевых элементов. Получаем сокращённую матрицу.
4) Минимальный элемент сокращённой матрицы вычитаем из всех её элементов, а затем складываем минимальный элемент с элементами расположенными на пересечении вычеркнутых строк и столбцов. Таким образом, получаем следующую эквивалентную матрицу. После этого повторяет выполнение шага 2.
5) Производим построение цепочки из нулей стоящих в квадратных скобках и вычисляем оптимальный маршрут.
3. Применение методов решения задачи коммивояжера на практике
3.1 Решение задачи коммивояжера методом ветвей и границ
Фирма по производству новогодних игрушек должна доставить заказ в 6 городов: Кирсанов (1); Котовск (2); Рассказово (3); Мичуринск (4) Инжавино (5); Уварово (6). Нужно найти кротчайший путь, объездив все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город 1.
Расстояния между городами заданы следующей матрицей. (Таблица 1)
Таблица 1
Исходные данные, матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
5 |
4 |
2 |
4 |
1 |
|
|
2 |
1 |
M |
2 |
4 |
5 |
7 |
|
|
3 |
7 |
5 |
M |
4 |
2 |
4 |
|
|
4 |
4 |
5 |
7 |
M |
2 |
1 |
|
|
5 |
2 |
1 |
4 |
7 |
M |
5 |
|
|
6 |
5 |
7 |
2 |
1 |
1 |
M |
Математическая модель:
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы С найти минимальный элемент: di = min(j) dij. (Таблица 2)
Таблица 2
Приведение матрицы по строкам, матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
di |
|
|
1 |
M |
5 |
4 |
2 |
4 |
1 |
1 |
|
|
2 |
1 |
M |
2 |
4 |
5 |
7 |
1 |
|
|
3 |
7 |
5 |
M |
4 |
2 |
4 |
2 |
|
|
4 |
4 |
5 |
7 |
M |
2 |
1 |
1 |
|
|
5 |
2 |
1 |
4 |
7 |
M |
5 |
1 |
|
|
6 |
5 |
7 |
2 |
1 |
1 |
M |
1 |
Затем вычитаем di из элементов рассматриваемой строки. Во вновь полученной матрице в каждой строке будет как минимум один ноль. (Таблица 3).
Таблица 3
Результат вычитания минимальных элементов рассматриваемой строки, матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
4 |
3 |
1 |
3 |
0 |
|
|
2 |
0 |
M |
1 |
3 |
4 |
6 |
|
|
3 |
5 |
3 |
M |
2 |
0 |
2 |
|
|
4 |
3 |
4 |
6 |
M |
1 |
0 |
|
|
5 |
1 |
0 |
3 |
6 |
M |
4 |
|
|
6 |
4 |
6 |
1 |
0 |
0 |
M |
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: dj = min(i) dij. (Таблица 4)
Таблица 4
Приведение матрицы по столбцам, матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
4 |
3 |
1 |
3 |
0 |
|
|
2 |
0 |
M |
1 |
3 |
4 |
6 |
|
|
3 |
5 |
3 |
M |
2 |
0 |
2 |
|
|
4 |
3 |
4 |
6 |
M |
1 |
0 |
|
|
5 |
1 |
0 |
3 |
6 |
M |
4 |
|
|
6 |
4 |
6 |
1 |
0 |
0 |
M |
|
|
dj |
0 |
0 |
1 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения. (Таблица 5).
Таблица 5
Результат вычитания минимальных элементов рассматриваемого столбца, матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
4 |
2 |
1 |
3 |
0 |
|
|
2 |
0 |
M |
0 |
3 |
4 |
6 |
|
|
3 |
5 |
3 |
M |
2 |
0 |
2 |
|
|
4 |
3 |
4 |
5 |
M |
1 |
0 |
|
|
5 |
1 |
0 |
2 |
6 |
M |
4 |
|
|
6 |
4 |
6 |
0 |
0 |
0 |
M |
Сумма констант приведения определяет нижнюю границу H: H = ?di + ?dj
H = 1+1+2+1+1+1+0+0+1+0+0+0 = 8
Элементы матрицы dij соответствуют расстоянию от пункта i до пункта j. Поскольку в матрице n городов, то С является матрицей nxn с неотрицательными элементами dij >=0.
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением: F(Mk) = ?dij
Причем каждая строка и столбец входят в маршрут только один раз с элементом dij.
Шаг №1. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках. (Таблица 6).
Таблица 6
Определение ребра ветвления, матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
di |
|
|
1 |
M |
4 |
2 |
1 |
3 |
0(1) |
1 |
|
|
2 |
0(1) |
M |
0(0) |
3 |
4 |
6 |
0 |
|
|
3 |
5 |
3 |
M |
2 |
0(2) |
2 |
2 |
|
|
4 |
3 |
4 |
5 |
M |
1 |
0(1) |
1 |
|
|
5 |
1 |
0(4) |
2 |
6 |
M |
4 |
1 |
|
|
6 |
4 |
6 |
0(0) |
0(1) |
0(0) |
M |
0 |
|
|
dj |
1 |
3 |
0 |
1 |
0 |
0 |
0 |
d(1,6) = 1 + 0 = 1; d(2,1) = 0 + 1 = 1; d(2,3) = 0 + 0 = 0; d(3,5) = 2 + 0 = 2; d(4,6) = 1 + 0 = 1; d(5,2) = 1 + 3 = 4; d(6,3) = 0 + 0 = 0; d(6,4) = 0 + 1 = 1; d(6,5) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (1 + 3) = 4 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*). Нижняя граница этого подмножества:
H(5*,2*) = 8 + 4 = 12
Исключение ребра (5,2) проводим путем замены элемента d52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу. (Таблица 7).
Таблица 7
Приведение матрицы расстояний для подмножества (5*,2*), матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
di |
|
|
1 |
M |
4 |
2 |
1 |
3 |
0 |
0 |
|
|
2 |
0 |
M |
0 |
3 |
4 |
6 |
0 |
|
|
3 |
5 |
3 |
M |
2 |
0 |
2 |
0 |
|
|
4 |
3 |
4 |
5 |
M |
1 |
0 |
0 |
|
|
5 |
1 |
M |
2 |
6 |
M |
4 |
1 |
|
|
6 |
4 |
6 |
0 |
0 |
0 |
M |
0 |
|
|
dj |
0 |
3 |
0 |
0 |
0 |
0 |
4 |
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d25 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (5 x 5), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
?di + ?dj = 0
После операции приведения сокращенная матрица будет иметь вид: (Таблица 8)
Таблица 8
Сокращённая матрица, матрица размерностью 55
|
i j |
1 |
3 |
4 |
5 |
6 |
di |
|
|
1 |
M |
2 |
1 |
3 |
0 |
0 |
|
|
2 |
0 |
0 |
3 |
M |
6 |
0 |
|
|
3 |
5 |
M |
2 |
0 |
2 |
0 |
|
|
4 |
3 |
5 |
M |
1 |
0 |
0 |
|
|
6 |
4 |
0 |
0 |
0 |
M |
0 |
|
|
dj |
0 |
0 |
0 |
0 |
0 |
0 |
Нижняя граница подмножества (5,2) равна:
H(5,2) = 8 + 0 = 8 ? 12
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 8.
Шаг №2. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках. (Таблица 9).
Таблица 9
Определение ребра ветвления (5,2), матрица размерностью 55
|
i j |
1 |
3 |
4 |
5 |
6 |
di |
|
|
1 |
M |
2 |
1 |
3 |
0(1) |
1 |
|
|
2 |
0(3) |
0(0) |
3 |
M |
6 |
0 |
|
|
3 |
5 |
M |
2 |
0(2) |
2 |
2 |
|
|
4 |
3 |
5 |
M |
1 |
0(1) |
1 |
|
|
6 |
4 |
0(0) |
0(1) |
0(0) |
M |
0 |
|
|
dj |
3 |
0 |
1 |
0 |
0 |
0 |
d(1,6) = 1 + 0 = 1; d(2,1) = 0 + 3 = 3; d(2,3) = 0 + 0 = 0; d(3,5) = 2 + 0 = 2; d(4,6) = 1 + 0 = 1; d(6,3) = 0 + 0 = 0; d(6,4) = 0 + 1 = 1; d(6,5) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 3) = 3 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(2*,1*) = 8 + 3 = 11
Исключение ребра (2,1) проводим путем замены элемента d21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу. (Таблица 10)
Таблица 10
Приведение матрицы расстояний для подмножества (2*,1*) матрица размерностью 55
|
i j |
1 |
3 |
4 |
5 |
6 |
di |
|
|
1 |
M |
2 |
1 |
3 |
0 |
0 |
|
|
2 |
M |
0 |
3 |
M |
6 |
0 |
|
|
3 |
5 |
M |
2 |
0 |
2 |
0 |
|
|
4 |
3 |
5 |
M |
1 |
0 |
0 |
|
|
6 |
4 |
0 |
0 |
0 |
M |
0 |
|
|
dj |
3 |
0 |
0 |
0 |
0 |
3 |
Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
?di + ?dj = 0
После операции приведения сокращенная матрица будет иметь вид (Таблица 11):
Таблица 11
Сокращённая матрица, матрица размерностью 44
|
i j |
3 |
4 |
5 |
6 |
di |
|
|
1 |
2 |
1 |
М |
0 |
0 |
|
|
3 |
M |
2 |
0 |
2 |
0 |
|
|
4 |
5 |
M |
1 |
0 |
0 |
|
|
6 |
0 |
0 |
0 |
M |
0 |
|
|
dj |
0 |
0 |
0 |
0 |
0 |
Нижняя граница подмножества (2,1) равна:
H(2,1) = 8 + 0 = 8 ? 11
Чтобы исключить подциклы, запретим следующие переходы: (1,5),
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 8.
Шаг №3. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках. (Таблица 12).
Таблица 12
Определение ребра ветвления (2,1) матрица размерностью 44
|
i j |
3 |
4 |
5 |
6 |
di |
|
|
1 |
2 |
1 |
M |
0(1) |
1 |
|
|
3 |
M |
2 |
0(2) |
2 |
2 |
|
|
4 |
5 |
M |
1 |
0(1) |
1 |
|
|
6 |
0(2) |
0(1) |
0(0) |
M |
0 |
|
|
dj |
2 |
1 |
0 |
0 |
0 |
d(1,6) = 1 + 0 = 1; d(3,5) = 2 + 0 = 2; d(4,6) = 1 + 0 = 1; d(6,3) = 0 + 2 = 2; d(6,4) = 0 + 1 = 1; d(6,5) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 2) = 2 для ребра (6,3), следовательно, множество разбивается на два подмножества (6,3) и (6*,3*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(6*,3*) = 8 + 2 = 10
Исключение ребра (6,3) проводим путем замены элемента d63 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (6*,3*), в результате получим редуцированную матрицу. (Таблица 13).
Таблица 13
Приведение матрицы расстояний для подмножества (6*,3*), матрица размерностью 44
|
i j |
3 |
4 |
5 |
6 |
di |
|
|
1 |
2 |
1 |
M |
0 |
0 |
|
|
3 |
M |
2 |
0 |
2 |
0 |
|
|
4 |
5 |
M |
1 |
0 |
0 |
|
|
6 |
M |
0 |
0 |
M |
0 |
|
|
dj |
2 |
0 |
0 |
0 |
2 |
Включение ребра (6,3) проводится путем исключения всех элементов 6-ой строки и 3-го столбца, в которой элемент d36 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
?di + ?dj = 1
После операции приведения сокращенная матрица будет иметь вид: (Таблица 14).
Таблица 14
Сокращённая матрица размерностью 33
|
i j |
4 |
5 |
6 |
di |
|
|
1 |
1 |
M |
0 |
0 |
|
|
3 |
2 |
0 |
M |
0 |
|
|
4 |
M |
1 |
0 |
0 |
|
|
dj |
1 |
0 |
0 |
М |
Нижняя граница подмножества (6,3) равна:
H(6,3) = 8 + 1 = 9 ? 10
Чтобы исключить подциклы, запретим следующие переходы: (1,5),
Поскольку нижняя граница этого подмножества (6,3) меньше, чем подмножества (6*,3*), то ребро (6,3) включаем в маршрут с новой границей H = 9
Шаг №4. Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М (бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках. (Таблица 15).
Таблица 15
Определение ребра ветвления (6,3) матрица размерностью 33
|
i j |
4 |
5 |
6 |
di |
|
|
1 |
0(1) |
M |
0(0) |
0 |
|
|
3 |
1 |
0(2) |
M |
1 |
|
|
4 |
M |
1 |
0(1) |
1 |
|
|
dj |
1 |
1 |
0 |
М |
d(1,4) = 0 + 1 = 1; d(1,6) = 0 + 0 = 0; d(3,5) = 1 + 1 = 2; d(4,6) = 1 + 0 = 1;
Наибольшая сумма констант приведения равна (1 + 1) = 2 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,5*) = 9 + 2 = 11
Исключение ребра (3,5) проводим путем замены элемента d35 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (3*,5*), в результате получим редуцированную матрицу. (Таблица 16).
Таблица 16
Приведение матрицы расстояний для подмножества (3*,5*) матрица размерностью 33
|
i j |
4 |
5 |
6 |
di |
|
|
1 |
0 |
M |
0 |
0 |
|
|
3 |
1 |
0 |
M |
1 |
|
|
4 |
M |
1 |
0 |
0 |
|
|
dj |
0 |
1 |
0 |
2 |
Включение ребра (3,5) проводится путем исключения всех элементов 3-ой строки и 5-го столбца, в которой элемент d53 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
Сумма констант приведения сокращенной матрицы:
?di + ?dj = 0
После операции приведения сокращенная матрица будет иметь вид: (Таблица 17).
Таблица 17
Сокращённая матрица размерностью 22
|
i j |
4 |
6 |
di |
|
|
1 |
0 |
М |
0 |
|
|
4 |
M |
0 |
0 |
|
|
dj |
0 |
0 |
0 |
Нижняя граница подмножества (3,5) равна:
H(3,5) = 9 + 0 = 9 ? 11
Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут с новой границей H = 9.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (1,4) и (4,6).
Cmin = 2+1+2+2+1+1=9
Путь: (1,4); (4,6); (6;3); (3,5); (5,2); (2,1)
1>4>6>3>5>2>1
Оптимальный путь Дерево ветвлений (Приложение А).
3.2 Решение задачи коммивояжера венгерским методом
Фирма по производству новогодних игрушек должна доставить заказ в 6 городов: Кирсанов (1); Котовск (2); Рассказово (3); Мичуринск (4) Инжавино (5); Уварово (6). Нужно найти кротчайший путь, объездив все города точно по одному разу и вернуться в исходный с минимумом затрат. Исходный город 1.
Расстояния между городами заданы следующей матрицей. (Таблица 18)
Математическая модель:
Таблица 18
Исходная матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
5 |
4 |
2 |
4 |
1 |
|
|
2 |
1 |
M |
2 |
4 |
5 |
7 |
|
|
3 |
7 |
5 |
M |
4 |
2 |
4 |
|
|
4 |
4 |
5 |
7 |
M |
2 |
1 |
|
|
5 |
2 |
1 |
4 |
7 |
M |
5 |
|
|
6 |
5 |
7 |
2 |
1 |
1 |
M |
Проводим редукцию матрицы по строкам, для чего в каждой строке находим минимальный элемент и вычитаем его из элементов этой же строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль. (Таблица 19).
Таблица 19
Приведение матрицы по строкам, матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
4 |
3 |
1 |
3 |
0 |
|
|
2 |
0 |
M |
1 |
3 |
4 |
6 |
|
|
3 |
5 |
3 |
M |
2 |
0 |
2 |
|
|
4 |
3 |
4 |
6 |
M |
1 |
0 |
|
|
5 |
1 |
0 |
3 |
6 |
M |
4 |
|
|
6 |
4 |
6 |
1 |
0 |
0 |
M |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент. (Таблица 20).
Таблица 20
Приведение матрицы по столбцам, матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
4 |
2 |
1 |
3 |
0 |
|
|
2 |
0 |
M |
0 |
3 |
4 |
6 |
|
|
3 |
5 |
3 |
M |
2 |
0 |
2 |
|
|
4 |
3 |
4 |
5 |
M |
1 |
0 |
|
|
5 |
1 |
0 |
2 |
6 |
M |
4 |
|
|
6 |
4 |
6 |
0 |
0 |
0 |
M |
После вычитания минимальных элементов получаем полностью редуцированную матрицу. Проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 6). Другие нули в строке 1 и столбце 6 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 5).
Фиксируем нулевое значение в клетке (2, 3). Другие нули в строке 2 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 5).
Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 3 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (6; 5).
В итоге получаем следующую матрицу. (Таблица 21).
Таблица 21
Поиск допустимого решения, матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
4 |
2 |
1 |
3 |
[0] |
|
|
2 |
[-0-] |
M |
[0] |
3 |
4 |
6 |
|
|
3 |
5 |
3 |
M |
2 |
[0] |
2 |
|
|
4 |
3 |
4 |
5 |
M |
1 |
[-0-] |
|
|
5 |
1 |
0 |
2 |
6 |
M |
4 |
|
|
6 |
4 |
6 |
[-0-] |
0 |
[-0-] |
M |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 6-х независимых нулей (в матрице их только 3), то решение недопустимое.
Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 6, столбец 6, строку 2, столбец 2, строку 3. Получаем сокращенную матрицу (элементы выделены). (Таблица 22).
Таблица 22
Сокращённая матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
4 |
2 |
1 |
3 |
0 |
|
|
2 |
0 |
M |
0 |
3 |
4 |
6 |
|
|
3 |
5 |
3 |
M |
2 |
0 |
2 |
|
|
4 |
3 |
4 |
5 |
M |
1 |
0 |
|
|
5 |
1 |
0 |
2 |
6 |
M |
4 |
|
|
6 |
4 |
6 |
0 |
0 |
0 |
M |
Минимальный элемент сокращенной матрицы (min(M, 2, 1, 3, 3, 5, M, 1, 1, 2, 6, M) =1) вычитаем из всех ее элементов. (Таблица 23).
Таблица 23
Вычитание минимального элемента сокращённой матрицы размерностью 66 из всех её элементов
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
4 |
1 |
0 |
2 |
0 |
|
|
2 |
0 |
M |
0 |
3 |
4 |
6 |
|
|
3 |
5 |
3 |
M |
2 |
0 |
2 |
|
|
4 |
2 |
4 |
4 |
M |
0 |
0 |
|
|
5 |
0 |
0 |
1 |
5 |
M |
4 |
|
|
6 |
4 |
6 |
0 |
0 |
0 |
M |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов. (Таблица 24).
Таблица 24
Суммирование минимального элемента с элементами на пересечениях вычеркнутых строк и столбцов, матрица размерностью 66
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
4 |
1 |
0 |
2 |
0 |
|
|
2 |
0 |
M |
0 |
3 |
4 |
7 |
|
|
3 |
5 |
4 |
M |
2 |
0 |
3 |
|
|
4 |
2 |
4 |
4 |
M |
0 |
0 |
|
|
5 |
0 |
0 |
1 |
5 |
M |
4 |
|
|
6 |
4 |
7 |
0 |
0 |
0 |
M |
Проводим редукцию матрицы по строкам.
В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль. (Таблица 25).
Таблица 25
Приведение матрицы размерностью 66 по строкам
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
4 |
1 |
0 |
2 |
0 |
|
|
2 |
0 |
M |
0 |
3 |
4 |
7 |
|
|
3 |
5 |
4 |
M |
2 |
0 |
3 |
|
|
4 |
2 |
4 |
4 |
M |
0 |
0 |
|
|
5 |
0 |
0 |
1 |
5 |
M |
4 |
|
|
6 |
4 |
7 |
0 |
0 |
0 |
M |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент. (Таблица 26).
Таблица 26
Приведение матрицы размерностью 66 по столбцам
|
i j |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
M |
4 |
1 |
0 |
2 |
0 |
|
|
2 |
0 |
M |
... |
Подобные документы
Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Сущность и содержание, основные понятия и критерии теории графов. Понятие и общее представление о задаче коммивояжера. Описание метода ветвей и границ, практическое применение. Пример использования данного метода ветвей для решения задачи коммивояжера.
контрольная работа [253,0 K], добавлен 07.06.2011Формирование нижних и верхних оценок целевой функции. Алгоритм метода ветвей и границ, решение задач с его помощью. Решение задачи коммивояжера методом ветвей и границ. Математическая модель исследуемой задачи, принципы ее формирования и порядок решения.
курсовая работа [153,2 K], добавлен 25.11.2011Методика решения задач высшей математики с помощью теории графов, ее сущность и порядок разрешения. Основная идея метода ветвей и границ, ее практическое применение к задаче. Разбиение множества маршрутов на подмножества и его графическое представление.
задача [53,0 K], добавлен 24.07.2009Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.
курсовая работа [541,3 K], добавлен 08.10.2015Нахождение полинома Жегалкина методом неопределенных коэффициентов. Практическое применение жадного алгоритма. Венгерский метод решения задачи коммивояжера. Применение теории нечетких множеств для решения экономических задач в условиях неопределённости.
курсовая работа [644,4 K], добавлен 16.05.2010Оптимальная настройка параметров "алгоритма отжига" при решении задачи коммивояжера. Влияние начальной температуры, числа поворотов при одной температуре и коэффициента N на результат. Сравнение и определение лучшей функции для расчётов задачи.
контрольная работа [329,9 K], добавлен 20.11.2011Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.
контрольная работа [333,3 K], добавлен 27.11.2011Описание метода потенциалов Математическая постановка задачи об оптимальных перевозках. Метод решения задачи об оптимальных перевозках средствами Ms Excel. Постановка параметрической транспортной задачи, ее математическое и компьютерное моделирование.
курсовая работа [802,5 K], добавлен 21.10.2014Постановка задачи аппроксимации методом наименьших квадратов, выбор аппроксимирующей функции. Общая методика решения данной задачи. Рекомендации по выбору формы записи систем линейных алгебраических уравнений. Решение систем методом обратной матрицы.
курсовая работа [77,1 K], добавлен 02.06.2011Метод разделения переменных в задаче Штурма-Лиувилля. Единственность решения смешанной краевой задачи, реализуемая методом априорных оценок. Постановка и решение смешанной краевой задачи для нелокального волнового уравнения с дробной производной.
курсовая работа [1003,8 K], добавлен 29.11.2014Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.
контрольная работа [23,5 K], добавлен 12.06.2011Описание методов решения системы линейного алгебраического уравнения: обратной матрицы, Якоби, Гаусса-Зейделя. Постановка и решение задачи интерполяции. Подбор полиномиальной зависимости методом наименьших квадратов. Особенности метода релаксации.
лабораторная работа [4,9 M], добавлен 06.12.2011Пьер-Симон Лаплас - выдающийся французский математик, физик и астроном, один из создателей теории вероятностей. Уравнение Лапласа в двумерном пространстве. Способы трехмерного уравнения Лапласа. Особенности решения задачи Дирихле в круге методом Фурье.
курсовая работа [271,8 K], добавлен 14.06.2011Структура текстовой задачи. Условия и требования задач и отношения между ними. Методы и способы решения задач. Основные этапы решения задач. Поиск и составление плана решения. Осуществление плана решения. Моделирование в процессе решения задачи.
презентация [247,7 K], добавлен 20.02.2015Особенности решения обыкновенного линейного неоднородного дифференциального уравнения второго порядка с заданными граничными условиями методом конечной разности. Составление трехдиагональной матрицы. Реализация решения в программе Microsoft Office Excel.
курсовая работа [1,4 M], добавлен 23.12.2013Применение метода дополнительного аргумента к решению характеристической системы. Доказательство существования решения задачи Коши. Постановка задачи численного расчёта. Дискретизация исходной задачи и её решение итерациями. Программа и её описание.
дипломная работа [5,7 M], добавлен 25.05.2014Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016Применение математических и вычислительных методов в планировании перевозок. Понятие и виды транспортных задач, способы их решения. Особенности постановки задачи по критерию времени. Решение транспортной задачи в Excel, настройка параметров решателя.
курсовая работа [1,0 M], добавлен 12.01.2011
