Пусть
Z
— многогранник допустимых потоков по линиям передачи.
В соответствии с выражениями (2) и (3)
Z
— выпуклый ограниченный
многогранник. Рассмотрим следующую экстремальную задачу:
F
(
z
) =
n
l
=1
z
l
t
l
(
z
l
)
→
min
z
∈
Z
.
(5)
Теорема 1.
Пусть все функции задержек монотонно возрастают,
дифференцируемы и
∀
l f
l
(
z
)
→ ∞
, z
→
¯
z
l
.
Тогда, если
Z
=
∅
, то
минимум целевой функции (5) достигается в единственной точке
z
∗
,
которой отвечает некоторая равновесная маршрутизация.
Доказательство.
С помощью критерия Сильвестра проверим по-
ложительную определенность матрицы Якоби целевой функции
F
(
z
)
.
Условия теоремы и определение этой функции (см. (4), (5)) дают
∂
2
F
∂z
2
l
= (
z
l
t
l
(
z
l
) +
t
l
(
z
l
)) =
f
l
(
z
l
)
>
0
,
∂
2
F
∂z
l
1
∂z
l
2
= 0
, l
1
=
l
2
,
где штрихом обозначено дифференцирование по переменной
z
l
. Все
условия этого критерия выполнены, поэтому целевая функция
F
(
z
)
—
строго выпуклая. В условиях теоремы это позволяет сделать вывод о
том, что решение выпуклой экстремальной задачи (5) существует и
единственно.
Докажем, что
z
∗
— точке минимума функции (5) — отвечает рав-
новесная маршрутизация. Для этого применим теорему Куна–Таккера
[6], которая в данном случае служит критерием оптимальности потока
z
∗
. В записи условий оптимальности учтем, что ограничения (3) неак-
тивны. Согласно принятым предположениям элемент
z
∗
удовлетворяет
строгим неравенствам в (3).
Выразим произвольный допустимый вектор
z
в виде
z
=
Aλ
, где
вектор
λ
= (
λ
k
j
)
входит в соотношения (2). Через
A
обозначена
n
×
×
J
-матрица всех маршрутов, соединяющих рассматриваемую тяготе-
ющую пару. Напомним, что
A
— это
0
×
1
-матрица инциденций ребра–
маршруты. Маршруты передачи представлены столбцами матрицы
A
.
Указанное представление вектора потоков
z
=
Aλ
всегда возможно:
для неприменяемых маршрутов
L
k
j
полагаем
λ
k
j
= 0
.
Условия оптимальности из теоремы Куна–Таккера в задаче (2)–(5)
представляют собой систему соотношений, распадающуюся на под-
системы, описывающие оптимальные решения для отдельных тяготе-
ющих пар. Поэтому рассмотрим произвольную пару
k
, зафиксировав
маршрутизацию остальных пар. Для упрощения записи в обозначени-
ях опустим верхний индекс
k
.
Итак, запишем функцию Лагранжа [6, 7]:
H
(
μ, λ
) =
F
(
Aλ
) +
μ, λ
0
−
J
j
=1
λ
j
, λ
0
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 2 79
