и, кроме того, все функции задержек непрерывны по совокупности
переменных. Тогда справедлива следующая теорема.
Теорема 3.
Метрика сети непрерывно зависит от параметров мо-
дели.
Доказательство.
Из теоремы о непрерывной зависимости ОДУ (4)
от параметра следует, что целевая функция
F
(
z, c
)
, z
∈
Z
(
c
)
, c
∈
C,
экстремальной задачи (5) непрерывна. Анализ линейных соотноше-
ний (2) и (3) показывает, что отображение
c
→
Z
(
c
)
непрерывно по
Хаусдорфу [7]. Ввиду теоремы 1 отсюда можно заключить, что опти-
мальное решение задачи (5)
z
∗
=
z
∗
(
c
)
непрерывно зависит от пара-
метра
c
. Таким образом, метрика сети также непрерывна, как сумма
непрерывных функций (см. уравнение (1)).
Непосредственным следствием теорем 1 и 2 является вывод о том,
что решение задачи маршрутизации устойчиво к изменению параме-
тров модели.
Алгоритм поиска равновесной маршрутизации.
Для поиска
оптимальных маршрутов передачи продуктов каждой тяготеющей
пары будем применять следующую схему алгоритма.
1. Произвольно выберем начальную маршрутизацию (шаг
t
= 0
).
2. Пусть на шаге
t
= 0
,
1
, . . .
уже построена маршрутизация, обо-
значаемая
M
t
(
M
t
= (
{
L
k
j
}
,
{
λ
k
j
}
)
). Ей отвечает векторпотоков
z
t
.
В
сети с фиксированной метрикой
ρ
(
L, z
t
)
найдем кратчайший маршрут
L
. (Достаточно воспользоваться алгоритмом Дейкстры [9].)
3. Пусть в текущей маршрутизации
M
t
существует маршрут
L
t
,
имеющий б´oльшую длину по сравнению с
L
. (Иначе решение зада-
чи уже найдено.) Тогда часть потока
λ
t
, передаваемого по маршруту
L
t
, перебросим на маршрут
L
в целях уменьшения разности длин
этих маршрутов. (Это возможно вследствие монотонности функций
задержек, см. (1).) При этом либо уравняются длины маршрутов, либо
маршрут
L
останется, по-прежнему, короче, а маршрут
L
t
не будет
использоваться (в случае
λ
|
L
=
λ
t
)
.
4. Определим очередную маршрутизацию ТС
M
t
+1
как результат
добавления к
M
t
пары
L, λ
|
L
и, возможно, исключения маршрута
L
t
в
случае, когда он не будет применяться.
Указанные действия — применение принципа уравнивания
Ю.Б. Гермейера как метода решения минимаксных задач [10] (см.
критерий (7)).
Теорема 4.
Последовательность маршрутизаций
{
M
t
, t
= 0
,
1
, . . .
}
,
построенная по принципу уравнивания, сходится к равновесному ре-
шению задачи.
82 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2
