↑ Вернуться > Секция 9 Математика

Осипов Геннадий Владимирович, Гутарина Алёна Васильевна

ПРИМЕНЕНИЕ МЕТОДА ВЕТВЕЙ И ГРАНИЦ К РЕШЕНИЮ ЗАДАЧИ КОММИВОЯЖЁРА

Осипов Геннадий Владимирович, Гутарина Алёна Васильевна

Логачёва Людмила Фёдоровна, научный руководитель

ФСПО им. Н.Н. Поликарпова ФГБОУ ВПО «Госуниверситет – УНПК», г. Орёл

 

Аннотация

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

 

Коммивояжер бродячий торговец. Задача коммивояжера – важная задача планирования транспортных перевозок. Коммивояжеру следует объехать n пунктов и в конце вернуться в исходный пункт. Требуется определить наиболее выгодный маршрут объезда (суммарное время в пути, суммарная стоимость дороги, или, в простейшем случае, длина маршрута). Задача может быть решена перебором всех вариантов объезда и выбором оптимального. Сложность в том, что количество возможных маршрутов быстро возрастает с ростом n (оно равно n! – количеству способов упорядочения пунктов). Одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон.

Рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ [1]. Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующую последовательность действий [1]:

  1. Построение матрицы с исходными данными;
  2. Нахождение минимума по строкам;
  3. Редукция строк;
  4. Нахождение минимума по столбцам;
  5. Редукция столбцов;
  6. Вычисление оценок нулевых клеток;
  7. Редукция матрицы;
  8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
  9. Вычисление итоговой длины пути и построение маршрута.

В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги». Итак, методика решения задачи коммивояжера [1]:

  1. Построение матрицы с исходными данными.

Сначала необходимо длины дорог, соединяющих города представить в виде следующей таблицы:

Город 1 2 3 4
1 М 5 11 9
2 10 М 8 7
3 7 14 М 8
4 12 6 15 М

В нашем примере у нас четыре города и в таблице указано расстояние от каждого города к трём другим, в зависимости от направления движения (т.к. некоторые железнодорожные пути могут быть с односторонним движением). Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности: ∞. Это сделано для того, чтобы данный отрезок пути был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от первого города к первому, от второго ко второму, и т.п. в качестве отрезка маршрута.

  1. Нахождение минимума по строкам.

Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец:

Город 1 2 3 4 di
1 М 5 11 9 5
2 10 М 8 7 7
3 7 14 М 8 7
4 12 6 15 М 6
  1. Редукция строк.

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di):

Город 1 2 3 4 di
1 М 0 6 4 5
2 3 М 1 0 7
3 0 7 М 1 7
4 6 0 9 М 6

В итоге в каждой строке будет хотя бы одна нулевая клетка.

  1. Нахождение минимума по столбцам.

Далее находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строку:

Город 1 2 3 4 di
1 М 0 6 4 5
2 3 М 1 0 7
3 0 7 М 1 7
4 6 0 9 М 6
dj 0 0 1 0
  1. Редукция столбцов.

Вычитаем из каждого элемента матрицы соответствующее ему dj:

 

Город 1 2 3 4 di
1 М 0 5 4 5
2 3 М 0 0 7
3 0 7 М 1 7
4 6 0 8 М 6
dj 0 0 1 0

В итоге в каждом столбце будет хотя бы одна нулевая клетка.

  1. Вычисление оценок нулевых клеток.

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.

Город 1 2 3 4
1 М 0 (4) 5 4
2 3 М 0 0
3 0 7 М 1
4 6 0 8 М

Итак, по всем нулевым клеткам:

Город 1 2 3 4
1 М 0 (4) 5 4
2 3 М 0 (5) 0 (1)
3 0 (4) 7 М 1
4 6 0 (6) 8 М
  1. Редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от четвёртого ко второму).

Город 1 2 3 4
1 М 0 (4) 5 4
2 3 М 0 (5) 0 (1)
3 0 (4) 7 М 1
4 6 0 (6) 8 М

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно):

Город 1 2 3 4
1 М 0 (4) 5 4
2 3 М 0 (5) М
3 0 (4) 7 М 1
4 6 М 8 М
  1. Если полный путь ещё не найден, то переходим к пункту 2, если

найден , то к пункту 9.

Если мы еще не нашли все отрезки пути, то возвращаемся ко второму пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т.д. Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9.

  1. Вычисление итоговой длины и построение маршрута.

Найдя все отрезки пути, остается только соединить их между собой и рассчитать общую длину пути (стоимость поездки по этому маршруту, затраченное время и т.д.). Длины дорог соединяющих города берем из самой первой таблицы с исходными данными. Маршрут получился следующий: 4 → 2 → 3 → 1 → 4. Общая длина путиL = 30 [1].

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

 

Список использованных источников

  1. Галяутдинов Р. Р. Задача коммивояжера – метод ветвей и границ // Сайт преподавателя экономики. [2013]. URL:http://galyautdinov.ru/post/zadacha-kommivoyazhera (дата обращения: 30.03.2015).
  2. Мудров В.И. Задача о коммивояжере. – М.:«Знание», 1969. – С. 62.

 

Голосовать Оценка 1Оценка 2Оценка 3Оценка 4Оценка 5 (1 голосов, средний: 5,00 из 5)
Loading...Loading...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

шестнадцать − один =

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>