4 / 16
П.С. Селин, В.И. Цурков, А.А. Гурченков
46
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 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)
Неотрицательность характеристических функций (1) и (2) — критерий того,
что усеченные сетевые и транспортные многогранники не являются пустыми
[4, 5, 12].
Теорема 1.
Пусть
( ; )
c
A
( ; ) 0
k
c
A
,
k
.
k
c ck a c
Если
,
,=
( , )
,
n m
A B
то
( , ; )
c
A B
( , ; ) 0
k
c
A B
,
k
1
.
k n
Далее будем применять функции (1) и (2), а также их упрощенный вид, если
обозначим
1
1
max{ :
},
;
( ; ) =
,
<
i
k
k
k
i a ck a ck
l
c
k a ck
A
и
1
1
max{ :
},
;
( ; ) =
0, < ,
j
k
j b ck b ck
l
c
b ck
B
то
> ( ; )
( ; ) = ( ( ; ) 1)
;
k
k
i
i
i k
i l
c k
c ck l
c
a
a
A
A
A
(3)
> ( ; )
=1
( , ; ) = ( ; )
, 1
.
k
k
k
j
i
j l
c
i
k
c ckl
c
b a k n
B
A B
B
(4)
Замечание 1.
Пусть
n
A
и
0.
c
Для (3) и (4), если
1
,
k
a ck
то
( ; ) = ( ; ).
k
k
l
c l
c
A A
Минимакс и наследственно минимаксная сеть смежности двудольной
сети.
Для пары векторов
,
,=
( , )
n m
A B
найдем наименьшее значение
= ( , ),
c c
A B
при котором
( , ; )
.
c
A B
Определение 1.
Пусть
,
,=
( , )
.
n m
A B
Величина
( , ) = min{ : ( , ; )
}
c
c
c
A B
A B
называется минимаксом для
( , )
A B
или
( , ).
A B
Это определение связано с очевид-
ным тождеством
( , ) ( , ) ,
: ( , ) = ( ) .
max
min
min{ : ( , ; )
} =
ij
ij
X
i j
x X
x
c
c
A B A B
A B
A B
Для минимакса имеет место теорема 2 [3–5].
Теорема 2.
Пусть
,
,=
( , )
n m
A B
и
( , ; )
.
c
A B
Величина
c
является мини-
максом
(
= ( , )
c c
A B
)
,
k
1
,
k n
что
( , ; ) = 0
k
c
A B
и
1
.
b ck
Построим формулу вычисления минимакса
( , ),
c
A B
где
,
,=
( , )
.
n m
A B
Обозна-
чим
1
( , ) = {( , ) : >
i
i
T
i j a a
A B
или
= ,
i n
1
>
j
j
b b
или
= }.
j m
Для
( , ) ( , )
t r T
A B
построим систему линейных соотношений
=1
>
1
=
;
;
> , < .
t
i
j
i
j r
tr
tr
r
tr
r
a b
c
tr
c t b
c t b r m
(5)