экстремальной задачи (6) непрерывна. Анализ линейных соотноше-
ний (2), (3) позволяет сделать вывод о том, что отображение
c
→
Z
(
c
)
непрерывно по Хаусдорфу [7]. Ввиду теоремы 1 отсюда можно за-
ключить, что оптимальное решение задачи (6)
z
=
z
(
c
)
непрерывно
зависит от параметра
c
. Таким образом, метрика сети также непрерыв-
на как сумма непрерывных функций (см. (1)).
Непосредственным следствием теорем 1, 2 является вывод о том,
что решение задачи о КМ устойчиво к изменению параметров модели.
Принцип уравнивания.
Для поиска оптимальных маршрутов при-
меним следующий подход. Произвольно выберем начальную маршру-
тизацию (шаг
t
= 0
).
Пусть на шаге
t
= 0
,
1
, . . .
имеется маршрутизация, обозначен-
ная
M
t
, M
t
= (
{
L
k
j
}
,
{
λ
k
j
}
)
. Ей отвечает вектор потоков
z
t
. В сети
с фиксированной метрикой
ρ
(
L, z
t
)
найдем кратчайший маршрут
L
t
.
(Достаточно воспользоваться алгоритмом Дейкстры [8]).
Пусть существует маршрут
L
из текущей маршрутизации
M
t
, име-
ющий большую длину по сравнению с
L
t
. (Иначе решение задачи уже
найдено.) Тогда часть потока
λ
t
, передаваемого по маршруту
L
, пере-
бросим на маршрут
L
t
. Ввиду монотонного роста функций задержек
имеется возможность уменьшить разность суммарных задержек вдоль
этих маршрутов. При этом либо длины сравниваемых маршрутов со-
впадут, либо маршрут
L
перестанет использоваться.
Определим очередную маршрутизацию ТС
M
t
+1
, добавив к
M
t
пару
L
t
, λ
t
и возможно исключив маршрут
L
в случае, когда он пере-
стает применяться.
Указанные действия составляют содержание
принципа уравнивания
Ю.Б. Гермейера [9] как метода решения задачи о кратчайших маршру-
тах.
Теорема 3.
Последовательность потоков
{
z
t
, t
= 0
,
1
, . . .
}
, постро-
енная на основе принципа уравнивания, сходится к решению
z
зада-
чи (6).
Доказательство.
Вычислим производную функции
F
(
Aλ
)
в теку-
щей точке
z
t
=
Aλ
t
по направлению вектора
Δ
, все координаты кото-
рого равны нулю за исключением тех, которые отвечают маршрутным
потокам вдоль
L
и
L
t
, равных соответственно 1 и
−
1
.
dF
(
Aλ
)
d
Δ
=
h
fA,
Δ
i
=
ρ
(
L, z
t
)
−
ρ
(
L
t
, z
t
)
>
0
.
Шаг градиентного метода в направлении
−
Δ
с целью выравнива-
ния длин маршрутов приводит к уменьшению значения целевой функ-
ции в задаче (6):
F
(
z
t
+1
)
< F
(
z
t
)
, t
= 0
,
1
, . . .
. Сходящаяся числовая
последовательность
{
F
(
z
t
)
}
в пределе дает
F
(
z
)
. Согласно теореме 1
z
t
→
z
.
74
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2008. № 1
