(Задача коммивояжера) Коммерческаядеятельность связанаспоездкамипогородам длязаключениясделок. Коммерсант,выезжая изкакого-либогорода, должен посетитьвсегорода,побываввкаждомизниходинитолькоодинраз,ивернутьсявисходныйгород.Необходимоопределитьтакуюпоследовательность объездагородов,прикоторой длинамаршрута, стоимость, или время проездабылабынаименьшей, поэтому передпоездкой составить кратчайшиймаршрут.Экономико-математическаяпостановкаэтой задачи.Расстояния междулюбойпароймножестваиз n городовизвестны aij (i =1, m; j =1, n, i ≠ j).Еслипрямогомаршрута междугородами i и j несуществует,тодопускают,что аij =∞. При этом переменная xij =–1–,–есликоммивояжерпереезжаетизгорода i вгород j (i =1, m; j =1, n, i ≠ j);впротивномслучае xij =0. Задачазаключается вопределенииматрицыцелыхнеотрицательных значений переменных xij, минимизирующих целевую функцию вида
mn
F (x)=åå(aij × xij)®min, (1£ i £ m); (1£ j £ n)
ij
приограничениях:
1)длявъездавгород j толькоодинраз:
m
å xij =1,
i =1
i =1, m;
2)длявыездаизгорода i толькоодинраз:
n
å xij =1,
j =1
j =1, n
Значит необходимоопределитьтакуюпоследовательность объездагородов,которая обеспечитминимальное время илиминимальную стоимость проезда,илиминимальное расстояние переезда. Втакойпостановкезадачакоммивояжерапредставляет собой задачуцелочисленноголинейногопрограммирования.Условияограниченийтребуют:
1)чтобымаршрут включал только один въезд вкаждый город;
2) чтобымаршрутвключаллишьодин выезд изкаждогогорода;
3)чтобымаршрутобразовывал контур,проходящийчерезвсегорода.Такимобразомформируетсяэкономныйвариантмаршрутаввидекольца. Оптимальныймаршрутзадачи строится методомветвейи границ.
Неориентированныйграфзадачикоммивояжера
Расстояния междулюбойпарой городов(i, j)известны исоставляют dij,где i =1, т; j =1, n. Еслипрямогомаршрутасообщениямеждугородаминесуществует,а такжедлявсех i = j полагаем,что dij =∞.На этомоснованиирасстояниямеждугородамиудобнопредставитьввидематрицы D =(dij) n х n. Если городам поставить в соответствие вершины графа,асоединяющимихдорогамребра,товтерминахтеорииграфов задача заключается в определении гамильтонова цикламинимальнойдлины.Гамильтоновциклвключаетвсевершиныграфаровноодинраз,причемначальная вершинасовпадаетсконечной,адлинаопределяется суммойдлинвсехребер.Такимобразом, необходимо построить кольцевоймаршрутпроездавсехгородовминимальнойдлины, начиная слюбогопунктаив любуюсторону.Посколькувсегогородов n,токоммивояжер,выехавиззаданногогорода,долженпобыватьвостальных(n –1)городахтолько один раз. Следовательно,всегосуществует(n –1)!возможных маршрутов,средикоторыходинилинесколько–оптимальные.Вбольшинствеслучаев можно предположить,что расстояние междугородами i и j являетсясимметричными равнорасстояниюотгорода j догорода i,т.е. dij = dji. Расстояниямеждугородамизапишемввидематрицы D. Есливзадаче n городов,то D является матрицейразмером(n х n)снеотрицательнымиэлементами dij ≥0, которые отображают длиныребервсетигородов.Так,при n =5 количество возможных вариантов маршрутовравно(5–1)!=24.
Так, например, расстояниямеждугородамизаданыматрицей:
| i j | |||||
| ∞ | ∞ | ∞ | ∞ | ∞ |
Решение задачиможнопредставитьввидезамкнутогоконтура,представляющегособой кольцевоймаршрут, например,изображенногонарисунке:
возможныйвариант проездаможно записатьввидесовокупностисоответствующихпардуг:
Мk ={(1,2),(2,4),(4,5),(5,3),(3,1)}.
Длина F (Mk) маршрута равна сумме соответствующих длин реберматрицырасстояний,тогдацелевуюфункциюможнозаписатьтак:
F (Mk)=
å dij ®min
(i, j)Î Mk
i =1, n;
k =1,(n -1).
Длялюбогодопустимого маршрута каждая строка икаждый столбецматрицы расстояний D содержаттолькопоодномуэлементу.Решениемзадачиявляетсяопределениекольцевого маршрутаминимальнойдлины:
| j i | |||||
Алгоритм р ешения задачикоммивояжераметодом ветвей и границ:
1. Построение матрицы с исходными данными. 2. Нахождение минимума по строкам. 3. Редукция строк. 4. Нахождение минимума по столбцам.5. Редукция столбцов. 6. Вычисление оценок нулевых клеток. 7. Редукция матрицы. 8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9. Вычисление итоговой длины пути и построение маршрута. Будем оперировать понятиями: вершины графа - «города», ребра их соединяющие – «дороги».
2.Нахождение минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.
| j i | di | |||||
| ∞ | ∞ | ∞ | ∞ | ∞ |
3.Редукцию строк проводим– из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di)
| j i | |||||
| ∞ | ∞ | ∞ | ∞0 | ∞ | |
| dj |
В итоге в каждой строке будет хотя бы одна нулевая клетка.
4.Нахождение минимума по столбцам минимальные значения в каждом столбце (dj)и выписываем в отдельную строку.
5.Редукция столбцов Вычитаем из каждого столбца матрицы соответствующее ему dj.
| j i | |||||
| ∞ | ∞ | ∞ | ∞0 | ∞ |
В итоге в каждом столбце и строке будет хотя бы одна нулевая клетка. Такимобразоммыполучимполностью редуцированнуюматрицуВеличины di и dj называют константамиприведения. Cумма констант приведения определяетнижнююграницу:
æ n n ö
H =çå di +å dj ÷= 140.
i 1
Длинамаршрутаопределяется выражением:
F (Mk)=
n
å dij,
(i, j)Î Mk
k =1;(n -1),
j =1 ø
причем каждая строка истолбец входятвмаршрут толькоодин разсэлементом dij.
6.Определяемребро ветвления, вычислением оценок нулевых клеток: длячегодлявсехклетокматрицыс нулевымиэлементамизаменяем поочередно нули на∞ иопределяем длянихсумму новыхобразовавшихсяконстант приведения,ониприведенывскобках.
| j i | di | |||||
| ∞ 0(10) 0(0) | ∞ 0(10) | 0(20) ∞ | 0(40) ∞ 0(0) | 0(30) ∞ | ||
| dj |
Среди них наибольшаясуммаконстант приведенияравна(40+0)=40ребра(1,4),следовательно, множество–разбиваетсянадваподмножества{(1,4)} включающее ребро,и{(1,4)}, невключающее это ребро.
Исключение ребра (1,4) проводим путем замены элемента d 1,4 =0 на ∞, после чего осуществляемочередное привед–е–ниематрицы расстоянийдляобразовавшегосяподмножествабез {(1,4)}, врезультатеполучимредуцированнуюматрицу:
| j i | di | |||||
| ∞ | ∞0 | ∞10 | ∞10 ∞0 | ∞ | ||
| dj |
Нижняяграница гамильтоновых цикловэтогоподмножества
––
Н (1,4)=140+40=180.
Включение ребра (1,4) проводится путем исключения всех элементов первой строкии четвертого столбца,вкоторойэлемент d 4,1 =0заменяем на∞дляисключения образования негамильтоновацикла. Врезультатеполучим другуюсокращеннуюматрицу(4×4),котораяподлежитопять операции приведения.
| ji | di | ||||
| ∞0 | ∞0 | ∞ | ∞ | ||
| dj |
Cуммаконстант приведениясокращеннойматрицы
å di +å dj =10.
i j
После операции приведения сокращенная матрица будетиметьвид
| j i | di | ||||
| ∞ 0(30) | ∞ 0(10) | 0(20) ∞ 0(30) | 0(30) ∞ | ||
| dj |
Нижняяграница подмножестваменьше и {(1,4)}равна:
Н (1,4)=140+10=150<180.
Посколькунижняягр–а–ница этогоподмножествас {(1,4)}меньше,чемподмножества без{(1,4)},торебро(1,4) включаем вмаршрут.
Затемопять Определяемреброветвления. Сэтойцельюопределяем сумму констант приведения(указаны в скобках) длянулевыхклеток, заменяя ихпоочередно на∞.Максимальная сумма констант d 4 + d 3 =30+0=30принадлежити ребру (4,3). Следовательно, разби–ва–еммножество маршрутов{(1,4)}надваподмножества{(1,4);с(4,3)}и{(1,4);без(4,3)}.
Исключение ребра(4,3)проводимпутемзаменыэлемента d 4,3=0 на ∞, после чего осуществляемочередное привед–е–ниематрицы расстоянийдляобразовавшегосяподмножества{(4,3)}, врезультатеполучимредуцированнуюматрицу:
| j i | di | ||||
| ∞0 | ∞0 | ∞∞30 | ∞ | ||
| dj |
Определяем константыприведенияинижнююграницу:
H (4,3)=150+30=180.
Включение ребра(4,3)вматрицу проводим путемисключенияэлементов третьейстрокиитретьегостолбца.
| j i | di | |||
| ∞0 | ∞ | |||
| dj |
Определим константыприведенияинижнюю границу подмножества:
H (4,3)=150+20=170.
Посколькуэта граница меньше, торебро (4,3) включаем в маршрут.Затемпроводимоперациюприведенияиполучимредуцированнуюматрицу.
| ∞ | |||
| ∞ |
Определяем ребро ветвления,длячегопоочередно нулевые элементы матрицы заменяем на∞иопределяем длянихсуммуконстант приведения(указанывскобках).
| 0(10) | ∞ | ||
| 0(10) | 0(10) | ||
| 0(10) | ∞ |
Выбираемреброветвления (2,1).Исключаемребро (2,1) путем замены d 2,1 =0 на∞
| di | ||||
| ∞ | ∞0 | ∞ | ||
| dj |
Вычислим нижнююграницу: H (2,1)=170+10=180.Включаем ребро (2,1) путем исключенияпервой строки ипервогостолбца,получимсокращеннуюматрицу
| di | |||
| ∞ | |||
| dj |
Дляисключенияобразованиянегамильтоновациклазаменяем d 3,2 =0на∞.
Вконечномитогеполучаемсокращеннуюматрицу
| j i | ||
| ∞0 | ∞ |
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,5) и(5,2). Врезультате по дереву ветвленийгамильтонов цикл образуют ребра(1,4), (4,3), (3,5), (5,2), (2,1), Последовательностьобъездагородовкоммивояжером1–4– 3–5–2–1представлена матрицей смежности втабл. Длина маршрута равна F (Mk)=40+20+20+40+60=180совпадает снижней границей подмножества.
| j i | |||||
Деревообъединяетвсемножествовариантов,авершиныдерева–этоподмножествачастичноупорядоченныхвариантоврешений.
