7 / 16
Алгоритм построения наследственно минимаксной сети с заданным вектором степеней узлов
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 1
49
Определение 3.
Сеть (матрица)
( , ) = ( )
ij
X A B x
называется равномерной,
если справедливы два условия [3–5]:
1)
= ,
i
p
a a
=
j
q
b b
= ;
ij
pq
x x
2)
,
i
p
a a
j
q
b b
.
ij
pq
x x
Каждая неотрицательная матрица
= ( ),
ij
X x
1
,
i n
1
,
j m
задает пару
векторов
,
,=
( , )
,
n m
A B
где
=1
=1
= ,
= ,
= ( , ) ( , ).
m
n
i
ij
j
ij
j
i
a x b x X X
A B A B
Будем го-
ворить, что матрица
X
задает пару векторов
( , ).
A B
Определение 4.
Для
,
,=
( , )
n m
A B
двудольная сеть (минимаксная)
( , )
X
A B
называется наследственно минимаксной, если каждая ее подматрица есть ми-
нимаксная матрица пары векторов, которую задает эта подматрица [3–5].
Основные свойства наследственно минимаксных сетей заключены в двух
(эквивалентных) утверждениях [3–5].
Теорема 5.
Для каждой пары векторов
( , )
A B
из множества
,
,=
n m
существу-
ет единственная наследственно минимаксная матрица
( , ),
X
A B
причем она яв-
ляется равномерной.
Теорема 6.
Каждый транспортный многогранник
( , )
A B
содержит одну и
только одну наследственно минимаксную матрицу, которая является равно-
мерной.
Алгоритм построения наследственно минимаксной сети заключен в следу-
ющей лемме [3–5].
Лемма 3.
Пусть
,
,=
( , )
n m
A B
и
( , ) = ( ) ( , ; ( , )),
ij
X
x
c
A B
A B A B
причем
( , ) = .
kq
c
c
A B
Тогда для пар векторов
( , )
A B
и
( , ),
A B
где
= ( , ) ,
i
i
a a c
q
A B
1
,
i k
= ,
j
q j
b b
1
,
j m q
= ,
i
k i
a a
1
,
i n k
= ( , ) ,
j
j
b b c
k
A B
1
,
j q
имеет место
,
,=
( , )
,
k m q
A B
,
,=
( , )
n k q
A B
и
( , ; ( , ))
,
c
A B A B
,
( , ; ( , ))
.
c A B
A B
Замечание 2 к лемме 1.
Из теоремы 3 следует: а) если
= ,
k n
то пары векторов
( , )
A B
не существует; б) если
= ,
q m
то пары векторов
( , )
A B
не существует; в) при
=
k n
и
=
q m
пары векторов
( , )
A B
и
( , )
A B
не существует.
Алгоритм 1.
Построение наследственно минимаксной двудольной сети [3–5].
Пусть
( , )
A B
— произвольная пара векторов из множества
,
,=
.
n m
Наслед-
ственно минимаксную матрицу
( , ) = ( )
ij
X
x
A Β
строят следующим образом.
Шаг 1.
Вычисляют минимакс
( , ) ( , )
max
( , ) =
tr
t r T
c
c
A B
A B
=
kq
c
(теорема 4) и строят
подматрицы искомой матрицы
( , ),
X
A B
первая из которых состоит из мини-
максных элементов, а вторая — нулевая (теорема 3).
Шаг 2.
Определяют пары векторов
( , ),
A B
( , )
A B
(см. лемму 3), применя-
ется теорема 4 для вычисления минимаксов
( , ),
c
A B
( , )
c
A B
и теорема 3 для
определения части элементов подматриц
1
( , ) ( , ; ( , ))
X
c
A B A B A B
и
2
( , ) ( , ; ( , ))
X
c
A B A B A B
искомой матрицы
( , )
X
A B
и т. д. Очевидно, что
процесс, содержащийся в алгоритме, конечен.