2 / 16
П.С. Селин, В.И. Цурков, А.А. Гурченков
44
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 1
ми и транспортными многогранниками [1, 2]. Одной из задач оптимизации в
моделях транспортного типа, где классические функционалы минимизации за-
менены минимаксными, является нахождение минимакса и построение наслед-
ственно минимаксной сети (матрицы), любая подсеть которой представляет со-
бой минимаксную сеть многогранника, которому она принадлежит [3–6]. Для
вычисления минимаксных значений построены системы линейных соотноше-
ний и показано, что расчет минимакса можно упростить. Полученные результа-
ты основаны на характеристических функциях, зависящих от координат векто-
ров и параметра. Неотрицательность характеристических функций — это кри-
терий непустоты усеченных сетевых и транспортных многогранников. Для
сетей исследуемых классов также приведен алгоритм построения наследственно
минимаксной сети.
Перейдем к основным определениям и обозначениям. Все
n
-вершинные се-
ти рассмотрим с множеством узлов
1
( ) = { , , },
n
U n u u
а все
n
,
m
-вершинные дву-
дольные сети — с множествами узлов (долями)
1
( ) = { , , }
n
U n u u
и
( ) =
V m
1
{ , ,
}.
m
v v
Будем отождествлять
n
-вершинные сети и
,
n m
-вершинные дву-
дольные сети с неотрицательными матрицами смежности
= ( ),
ij
X x
1 ,
,
i j n
и
= ( ),
ij
X x
1
,
i n
1
,
j m
где
=
ij
ji
x x
— вес дуги (петли при
=
i j
) с верши-
нами
i
u
и
j
u
в первом случае и
ij
x
— вес дуги с вершинами
i
u
и
j
v
во втором.
Для множеств неотрицательных векторов и пар из них применяют следую-
щие обозначения:
1
= { = ( , , ) :
0 };
n
n i
a a a
i
A
1
=
:
, 1
1 (при
2) ;
n
n
i
i
R a a
i n
n
A
,
,=
=1
=1
= ( , ) :
,
,
= ;
n
m
n
m
n m
i
j
i
j
A
a b
A B
B
,
,
,=
,=
= ( , )
:
.
n
m
n m
n m
A B
A B
В транспортных задачах условие равенства сумм координат пары векторов
из множества
,
,=
n m
называется замкнутостью, или условием баланса [7–9].
Многие утверждения и конструкции (без ограничения общности) рассматрива-
ются с векторами из множества
n
и парами векторов из множества
,
,
.
n m
Обозначим множества сетей, степени узлов которых равны координатам
вектора
A
из множества
n
как
( ) = ( ) = ( ) : ( )
( );
= 0
ij
L
ii
X x X
x
i
A A
A A
;
( ; ) = ( ) = ( ) : ( ) ( );
,
ij
ij
c X x X
x c i j
A A
A A
—
класс сетей, веса дуг которых
не превосходят заданного неотрицательного параметра
c
.
Множества сетей
( )
A
и
( ; )
c
A
называются сетевыми и усеченными сете-
выми многогранниками [6, 7, 10, 11].
Множества двудольных сетей, степени узлов которых равны координатам
векторов из пары
,
,=
( , )
,
n m
A B
обозначим
( , ) = ( , ) = ( ) :
0 , ;
ij
ij
X
x x
i j
A B A B