3 / 16
Алгоритм построения наследственно минимаксной сети с заданным вектором степеней узлов
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 1
45
=1
=1
deg = = ; deg = = ,
m
n
i
ij
i
j
ij
j
j
i
u x a i
v x b j
( , ; ) = ( , ) = ( ) : ( , ) ( , );
.
ij
ij
c X
x X
x c
A B
A B
A B A B
В транспортных задачах множества
( , )
A B
и
( , ; )
c
A B
называются класси-
ческим и усеченным транспортными многогранниками [1, 2].
Рассмотрим следующую вероятностную задачу. Пусть
,
,=
( , )
,
n m
A B
> 0,
t
и
пусть
( , ) = ( )
ij
X
x
A B
— транспортная матрица-план, задаваемая векторами
A
и
.
B
Тогда
( , ) =( )
ij
tX
tx
A B
— матрица времени, необходимого на транспортиров-
ку продукта от производителя
i
к потребителю
,
j
1
,
i n
1
.
j m
Обозначим
( )
X
M
— множество всех подматриц матрицы
= ( , ).
X X
A B
Поскольку каждая
подматрица задается произвольными подмножествами строк и столбцов,
| ( ) |=(2 1)(2 1)
n
m
X
M
— число всех подматриц в множестве
( ).
X
M
Введем
следующий функционал
( ( , )) = max .
ij
ij
X
x
A B
Допустим, что подматрицы
Y
вы-
бирают из множества
( )
X
M
равновероятно и критерием для каждого выбора
является значение
( ( , ))
t X
A B
наибольшего элемента из
.
tY
Распределение ве-
роятности на множестве
( )
X
M
равномерно, поэтому задача минимизации ожи-
даемого значения максимального времени, необходимого на транспортировку
( )
(2 1)(2 1)
( ),
n
m
Y X
t
Y
M
сводится к задаче минимизации функционала
( )
( ( , )) =
( ).
Y X
X
Y
A B
M
Задача минимизации функционала
( )
X
имеет единственное решение, за-
даваемое наследственно минимаксной матрицей
*
*
( , ) = ( )
ij
X
x
A B
[5]:
*
( , ) ( , )
min ( ( , )) = ( ( , )).
X
X
X
A B A B
A B
A B
Характеристические функции.
Сформулируем условия, при которых
( ; ),
c
A
( , ; )
,
c
A B
для чего введем понятия характеристических функций
[4, 5, 12].
Пусть
n
A
и
0.
c
Характеристической функцией называется функция
вида
1
1
( ; ) = ( 1)
(
)
,
.
k
i
i
i
k
i k
i k
i k
a ck i
c ck k
a ck a
a c ck a c
A
(1)
Для и характеристическую функцию определяют как
=1
=1
( , ; ) =
(
)
, 1
.
m
k
k
j
j
i
j
b ck
i
j
c
b
b ck a k n
A B
(2)