Постановки векторных задач об оптимальной маршрутизации ТС
(всех пар) даны в работах [2–4].
В случае единственной
k
-й тяготеющей пары под оптимальной
маршрутизацией понимается такой выбор допустимой маршрутиза-
ции, что не существует соединяющего
k
-ю пару маршрута
L
, для ко-
торого
(
8
j
)
ρ
(
L, z
)
6
ρ L
k
j
, z ,
причем некоторые из этих неравенств являются строгими. (Маршрут
L
более привлекателен по сравнению с маршрутами из множества
{
L
k
j
}
).
Таким образом, все оптимальные маршруты являются кратчайши-
ми в метрике
ρ
(
L, z
)
, а их поиск состоит в решении задачи о кратчай-
ших маршрутах.
Отметим, что решение той же задачи на подграфе графа сети может
привести к более коротким маршрутам.
Основной результат.
Задача о кратчайших маршрутах решается
для произвольно зафиксированной тяготеющей пары. В дальнейшем
для упрощения записи будем опускать индекс
k
.
Пусть
Z
— многогранник допустимых потоков по линиям переда-
чи. (Ввиду равенств (2), (3)
Z
– выпуклый компактный многогранник.)
Определим функции
t
l
=
t
l
(
z
l
)
,
l
= 1
,
2
, . . . , n
, как решения обыкно-
венного дифференциального уравнения (ОДУ)
z
l
t
0
l
+
t
l
=
f
l
(
z
l
)
(5)
с нулевыми начальными значениями, где штрих означает дифферен-
цирование по переменной
z
l
.
Рассмотрим следующую экстремальную задачу:
F
(
z
) =
n
X
l
=1
z
l
t
l
(
z
l
)
→
min
z
2
Z
.
(6)
Теорема 1.
Пусть, все функции задержек монотонно возрастают,
дифференцируемы и
(
8
l
)
f
l
(
z
)
→ ∞
, z
→
ˉ
z
l
. Тогда, если
Z
6
=
?
, то
минимум целевой функции (6) достигается в единственной точке
z
,
которой отвечает некоторая оптимальная маршрутизация.
Доказательство.
По условию теоремы и определению (5), (6)
имеем
∂
2
F
∂z
2
l
= (
z
l
t
0
l
(
z
l
) +
t
l
(
z
l
))
0
=
f
0
l
(
z
l
)
>
0
.
Критерий Сильвестра [5, c. 95] позволяет заключить: экстремаль-
ная задача (6) выпукла, а целевая функция
F
(
z
)
— строго выпукла.
72
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2008. № 1
