Статья опубликована в рамках: XLIX Международной научно-практической конференции «Научное сообщество студентов XXI столетия. ТЕХНИЧЕСКИЕ НАУКИ» (Россия, г. Новосибирск, 30 января 2017 г.)
Наука: Информационные технологии
Скачать книгу(-и): Сборник статей конференции
отправлен участнику
НАХОЖДЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ В ЗАДАЧЕ КОММИВОЯЖЕРА МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ
На сегодняшний день задача поиска оптимального пути является актуальной, так как к её решению сводится анализ разнообразных ситуаций, возникающих в таких отраслях, как экономика, техника, военное дело, строительство. Таким образом, сформулированную задачу решают методом ветвей и границ.
В настоящее время алгоритмы метода являются наиболее надежным средством решения целочисленных задач, встречающихся в практических исследованиях [2].
Метод ветвей и границ является универсальным методом решения комбинаторных задач дискретного программирования.
Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 году для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связано с работой Литла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям.
Суть метода ветвей и границ заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов [1].
Дана задача коммивояжера. Известно, что нужно обойти такие пункты как «университет», «рынок», «общежитие», «лингвистический центр». Известно время, требующееся на прохождение пути между этими пунктами. Причем передвижение возможно как пешим ходом, так и на транспорте. Время (в минутах), требующееся для обхода пунктов, представлено в матрице (таблица 1).
Таблица 1
Матрица исходных данных
пункт |
университет |
рынок |
общежитие |
лингвистический центр |
университет |
|
3 |
9 |
7 |
рынок |
8 |
|
6 |
5 |
общежитие |
5 |
12 |
|
6 |
лингвистический центр |
10 |
4 |
13 |
|
Найти оптимальный путь методом ветвей и границ, при котором время обхода всех пунктов будет минимальным. Рассмотрим решение задачи без условия. Из постановки задачи следует, что данный цикл является гамильтоновым. Для решения задачи с неизвестным пунктом отправления следует произвести следующие операции над исходной матрицей.
Нахождение минимальных элементов в каждой строке и запись его в отдельный столбец (таблица 2).
Таблица 2
Матрица с минимальными значениями по строкам
пункт |
университет |
рынок |
общежитие |
лингвистический центр |
di |
университет |
|
3 |
9 |
7 |
3 |
рынок |
8 |
|
6 |
5 |
5 |
общежитие |
5 |
12 |
|
6 |
5 |
лингвистический центр |
10 |
4 |
13 |
|
4 |
Производится редукция строк, то есть необходимо из каждого элемента строки, вычесть соответствующее значение минимального элемента di. В итоге в каждой строке появляется нулевая ячейка (таблица 3).
Таблица 3.
Матрица редукции строк
пункт |
университет |
рынок |
общежитие |
лингвистический центр |
di |
университет |
|
0 |
6 |
4 |
3 |
рынок |
3 |
|
1 |
0 |
5 |
общежитие |
0 |
7 |
|
1 |
5 |
лингвистический центр |
6 |
0 |
9 |
|
4 |
Нахождение минимальных элементов по столбцам (таблица 4).
Таблица 4.
Матрица с минимальными значениями по столбцам
пункт |
университет |
рынок |
общежитие |
лингвистический центр |
университет |
|
0 |
6 |
4 |
рынок |
3 |
|
1 |
0 |
общежитие |
0 |
7 |
|
1 |
лингвистический центр |
6 |
0 |
9 |
|
dj |
0 |
0 |
1 |
0 |
Производится редукция столбцов, то есть необходимо из каждого элемента столбца, вычесть соответствующее значение минимального элемента dj. В итоге в каждом столбце появляется нулевая ячейка (таблица 5).
Таблица 5.
Матрица редукции столбцов
пункт |
университет |
рынок |
общежитие |
лингвистический центр |
университет |
|
0 |
5 |
4 |
рынок |
3 |
|
0 |
0 |
общежитие |
0 |
7 |
|
1 |
лингвистический центр |
6 |
0 |
8 |
|
dj |
0 |
0 |
1 |
0 |
Для каждой нулевой ячейки получившейся преобразованием матрицы находится «оценка». Оценкой будет сумма минимального элемента по строке и по столбцу, в которых размещена нулевая ячейка. Нулевая ячейка при этом сама не учитывается. di и dj тоже не учитываются. Найденная оценка записывается рядом с нулем, в скобках (таблица 6).
Таблица 6.
Матрица оценок
пункт |
университет |
рынок |
общежитие |
лингвистический центр |
университет |
|
0(4) |
5 |
4 |
рынок |
3 |
|
0(5) |
0(1) |
общежитие |
0(4) |
7 |
|
1 |
лингвистический центр |
6 |
0(6) |
8 |
|
Выбирается нулевая ячейка с наибольшей оценкой. Производится замена значения нулевой ячейки на . Тем самым был найден отрезок пути. Необходимо выписать отрезок пути из i-го пункта в j-ый. В данном случае из лингвистического центра в рынок. Производится исключение строки и столбца, содержащих нулевую ячейку с максимальной оценкой. В ячейку соответствующую обратному пути записывается
, так как не будет производиться возвращение обратно (таблица 7).
Таблица 7.
Редукция матрицы
пункт |
университет |
общежитие |
лингвистический центр |
университет |
|
5 |
4 |
рынок |
3 |
0 |
|
общежитие |
0 |
|
1 |
Так как полный путь ещё не найден, то следует производить преобразования матрицы. Нахождение минимальных элементов по строкам (таблица 8).
Таблица 8.
Матрица с минимальными значениями по строкам
пункт |
университет |
общежитие |
лингвистический центр |
di |
университет |
|
5 |
4 |
4 |
рынок |
3 |
0 |
|
0 |
общежитие |
0 |
|
1 |
0 |
Выполнение редукции по строкам (таблица 9).
Таблица 9.
Матрица редукции строк
пункт |
университет |
общежитие |
лингвистический центр |
di |
университет |
|
1 |
0 |
4 |
рынок |
3 |
0 |
|
0 |
общежитие |
0 |
|
1 |
0 |
Нахождение минимальных элементов по столбцам (таблица 10).
Таблица 10.
Матрица с минимальными значениями по столбцам
пункт |
университет |
общежитие |
лингвистический центр |
университет |
|
1 |
0 |
рынок |
3 |
0 |
|
общежитие |
0 |
|
1 |
dj |
0 |
0 |
0 |
Выполнение редукции по столбцам (таблица 11).
Таблица 11.
Матрица редукции столбцов
пункт |
университет |
общежитие |
лингвистический центр |
университет |
|
1 |
0 |
рынок |
3 |
0(4) |
|
общежитие |
0(4) |
|
1 |
dj |
0 |
0 |
0 |
Вычисление оценок нулевых ячеек (таблица 12).
Таблица 12.
Матрица оценок
пункт |
университет |
общежитие |
лингвистический центр |
университет |
|
1 |
0(2) |
рынок |
3 |
0(4) |
|
общежитие |
0(4) |
|
1 |
Выполнение редукции матрицы. В данном случае путь из «общежитие» в «университет» занимает минимальное время (таблица 13).
Таблица 13.
Редукция матрицы
пункт |
общежитие |
лингвистический центр |
университет |
1 |
0(2) |
рынок |
0(4) |
|
Так как полный путь ещё не найден, то следует производить преобразования матрицы. В данной матрице уже существуют оценки нулевых ячеек и дальнейшие преобразования производить не целесообразно
(таблица 14).
Таблица 14.
Матрица оценок
пункт |
общежитие |
лингвистический центр |
университет |
|
0(2) |
рынок |
0(4) |
|
Выполнение редукции матрицы. В данном случае максимальная оценка пути равна 0(4), следовательно, следующий путь из «рынок» в «общежитие» (таблица 15).
Таблица 15.
Редукция матрицы
пункт |
лингвистический центр |
университет |
0 |
Последним этапом является путь из пункта «университет» в «лингвистический центр». Вычисление итогового времени на прохождение пути и построение маршрута (таблица 16).
Таблица 16.
Исходная таблица данных
Тем самым найден оптимальный путь. В результате преобразований найденный путь будет иметь вид: «лингвистический центр» - «рынок» - «общежитие» - «университет» - «лингвистический центр».
Время на прохождение данного пути вычисляется с помощью исходных данных: минут.
По полученным данным для наглядности строятся граф, представленный на рисунке 1.
Рисунок 1. Дерево пути
В соответствии с решением, оптимальный маршрут обхода всех пунктов с условием неизвестности первоначального пункта отправления в следующем: на первом шаге следует начать движение из пункта «лингвистический центр»; на втором - маршрут проходит в пункт «рынок»; на третьем - направиться в пункт «общежитие»; на четвертом - маршрут проходит в пункт «университет»; на пятом - возвращение в исходный пункт «лингвистический центр». Минимальное время, потраченное на обход всех пунктов, составляет L=22 минут.
Список литературы:
- Акулич И.Л., «Математическое программирование в примерах и задачах», Москва «Высшая школа» 1993 г.
- Таха Х., «Введение в исследование операций» В 2-х книгах. Кн.1. Пер.с англ. – М.: Мир, 1895. −479 с., ил.
отправлен участнику
Оставить комментарий