ВУЗ:
Составители:
Рубрика:
53
Найденное методом расширения цикла решение на 12,4 % имеет
большие энергозатраты, чем оптимальное решение
0
1
μ
, полученное
полным перебором всех
N
вариантов )24!4)!1((
=
=
−
=
n
N
:
.1131,5,2,3,4,1)( ,1,5,2,3,4,1
0
1
0
1
=== ЭЭ
μμ
(4.10)
Как и при решении классической задачи коммивояжера, решение,
найденное методом расширения цикла, следует попытаться улучшить на
основе проверки
первого необходимого условия оптимальности.
Действительно, анализ структуры решений (4.9), (4.10) показал, что
выделенные в них жирным шрифтом элементы [см. формулу (4.11)] не
являются минимальными ни в строках, ни в столбцах матрицы
c
(табл. 18):
11,22,44,3,,
0
11,44,33,2
() 143 49,
() 334 40.
ðö
Lñcc
Lccc
μ
μ
=++++=++++=
=++++=++++=
35 51
c c 21 20
10 20
2,5 5,1
cñ
(4.11)
Следовательно, снимая жесткое ограничение однократности прохода
через каждый пункт, длина некоторых участков цикла может быть
уменьшена, что сократит и энергозатраты. В частности, решив задачу о
кратчайшем пути (рис. 2), найдем:
Таким образом, с учётом (4.11), (4.12)
уменьшение общей длины
каждого из маршрутов в (4.11) будет соответственно равно:
.990)1120()1010()(
,1697)1120()1421()(
0
1
1
=+=−+−=Δ
=+=−+−=Δ
μ
μ
L
L
рц
(4.13)
Новые маршруты
′
рц
1
μ
,
′
0
1
μ
будут получены из (4.10) и (4.9) при
замене в них участков 5;3, 1;5 соответственно на 5,2,3 и 1,4,2,5 :
. 105, 2 ) (
),
20
вместо
(
115421 , 4, 2 , 5) (
),
21
вместо
(
141045 , 2 , 3 ) (
5 ,2
0
5 , 2
2 ,51,44 , 2 2 , 5
0
1
, 5
5,35 , 22 , 3
0
5
, 3
= ==
=
=
+
+
=
++ ==
=
=
+
= + ==
c
L
L
сcc c
L
L
сc c
L
L
μ
μ
μ
(4.12)
Страницы
- « первая
- ‹ предыдущая
- …
- 49
- 50
- 51
- 52
- 53
- …
- следующая ›
- последняя »
