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

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

В настоящее время алгоритмы метода являются наиболее надежным средством решения целочисленных задач, встречающихся в практических исследованиях [2].

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

Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 году для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связано с работой Литла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям.

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

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

Таблица 1

Матрица исходных данных

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

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

Таблица 2

Матрица с минимальными значениями по строкам

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

Таблица 3.

Матрица редукции строк

Нахождение минимальных элементов по столбцам (таблица 4).

Таблица 4.

Матрица с минимальными значениями по столбцам

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

Таблица 5.

Матрица редукции столбцов

Для каждой нулевой ячейки получившейся преобразованием матрицы находится «оценка». Оценкой будет сумма минимального элемента по строке и по столбцу, в которых размещена нулевая ячейка. Нулевая ячейка при этом сама не учитывается. d_i и d_j тоже не учитываются. Найденная оценка записывается рядом с нулем, в скобках (таблица 6).

Таблица 6.

Матрица оценок

Выбирается нулевая ячейка с наибольшей оценкой. Производится замена значения нулевой ячейки на . Тем самым был найден отрезок пути. Необходимо выписать отрезок пути из i-го пункта в j-ый. В данном случае из лингвистического центра в рынок. Производится исключение строки и столбца, содержащих нулевую ячейку с максимальной оценкой. В ячейку соответствующую обратному пути записывается , так как не будет производиться возвращение обратно (таблица 7).

Таблица 7.

Редукция матрицы

Так как полный путь ещё не найден, то следует производить преобразования матрицы. Нахождение минимальных элементов по строкам (таблица 8).

Таблица 8.

Матрица с минимальными значениями по строкам

Выполнение редукции по строкам (таблица 9).

Таблица 9.

Матрица редукции строк

Нахождение минимальных элементов по столбцам (таблица 10).

Таблица 10.

Матрица с минимальными значениями по столбцам

Выполнение редукции по столбцам (таблица 11).

Таблица 11.

Матрица редукции столбцов

Вычисление оценок нулевых ячеек (таблица 12).

Таблица 12.

Матрица оценок

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

Таблица 13.

Редукция матрицы

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

(таблица 14).

Таблица 14.

Матрица оценок

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

Таблица 15.

Редукция матрицы

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

Таблица 16.

Исходная таблица данных

Тем самым найден оптимальный путь. В результате преобразований найденный путь будет иметь вид: «лингвистический центр» - «рынок» - «общежитие» - «университет» - «лингвистический центр».

Время на прохождение данного пути вычисляется с помощью исходных данных:  минут.

По полученным данным для наглядности строятся граф, представленный на рисунке 1.

Рисунок 1. Дерево пути

В соответствии с решением, оптимальный маршрут обхода всех пунктов с условием неизвестности первоначального пункта отправления в следующем: на первом шаге следует начать движение из пункта «лингвистический центр»; на втором - маршрут проходит в пункт «рынок»; на третьем - направиться в пункт «общежитие»; на четвертом - маршрут проходит в пункт «университет»; на пятом - возвращение в исходный пункт «лингвистический центр». Минимальное время, потраченное на обход всех пунктов, составляет L=22 минут.

Список литературы:

1. Акулич И.Л., «Математическое программирование в примерах и задачах», Москва «Высшая школа» 1993 г.
2. Таха Х., «Введение в исследование операций» В 2-х книгах. Кн.1. Пер.с англ. – М.: Мир, 1895. −479 с., ил.