ВУЗ:
Составители:
Рубрика:
132
Приложение 2
Решение задачи коммивояжера размера 10 х 10
модифицированным методом расширения цикла
Матрица расстояний
с (табл. 1) данного числового примера
заимствована из [17], где приведено и оптимальное решение, полученное
одним из известных методов:
0
1
μ =<1,3,7,10,8,6,2,5,4,9,1>, (
0
1
μ )=1159. (1)
Знание оптимального решения позволяет убедиться в том, что и для
более общих условий (элементы с
ij
равномерно распределены в диапазоне
0 – 1000) модифицированный МРЦ (раздел 3) с заданной достоверностью
обеспечивает получение оптимального решения.
Для проведения расчетов без использования ЭВМ эстафетным
методом (рис. 2) вычислены элементы совмещенной матрицы кротчайших
маршрутов и их длин ||
0
k,l
μ /
0
k,l
L || (табл. 2). Покажем, что и для
рассматриваемого примера существует хотя бы один начальный цикл
<k·γ·k>, приводящий к оптимальному решению при использовании МРЦ
(табл. 12) или ММРЦ (табл. 15). Из C
2
10
=45 возможных начальных циклов
по крайней мере цикл
μ
1
3
= <3·5·3> = <3,6,5,4,1,3>, L <3·5·3> = 763,
полученный согласно (3.7) и табл. 2, приводит к оптимальному решению,
что видно из результатов расчетов, данных в табл. 3.
На первом шаге процесса (табл. 3, t = 1,) в интервал r с границами j
r-1
,
j
r
последовательно включается каждый элемент γ
∈
G
1
и вычисляются
соответствующие приращения длины цикла:
()
(
)
(
)
r-1 r r-1 r-1 r
t00
γ,j,r
j γ jj,γ j,j
ttt
δ r, γ = δ =L μ +L μ -c .
Например, для r = 1, (j
0
;j
1
) = (3;6) и γ = 7 имеем
(
)
(
)
(
)
11010
3,7 7,6 3,6
δ 1;7 = L μ +L μ - c = 141+ 422 - 200 = 363, (2)
при этом
00
376 3,7 7,6
μ = μμ= 3, ,5, 4,9,6 ,
⋅⋅
7
U
что и записано в первой строке табл. 3.
Страницы
- « первая
- ‹ предыдущая
- …
- 128
- 129
- 130
- 131
- 132
- …
- следующая ›
- последняя »
