8 / 16
П.С. Селин, В.И. Цурков, А.А. Гурченков
50
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 1
Минимакс и наследственно минимаксная сеть с заданным вектором сте-
пеней узлов.
Для вектора
n
A
вычислим наименьшее значение
= ( ),
c c
A
при
котором
( ; ) .
c
A
Определение
5.
Пусть
n
A
и
( ) .
A
Значение
( ) =
c
A
min{ : ( ; ) }
c
c
A
называется минимаксом для
A
или
( )
A
[12].
Величина
( )
c
A
в работах [3–5] называется весом вектора
.
A
Легко заметить
справедливость тождества
( ) ( ) ,
max
min
min{ : ( ; )
} =
{ : ( ) = ( )} .
ij
ij
X
i j
c
c
x X x
A A
A
A
Для минимакса имеет место теорема 7 [12].
Теорема 7.
Пусть
n
A
и
( ) .
A
Величина
c
является минимаксом
( = ( ))
c c
A
( ; )
c
A
и
,
p
,
p
c cp a c
что
( ; ) = 0.
p
c
A
Перейдем к построению формулы вычисления минимакса
( ),
c
A
где
.
n
A
Обозначим
( ) = {( , ) : ,
, 1
}.
T
i j i j
i j n
A
Для
( , ) ( )
t r T
A
построим си-
стему соотношений
>
1
=
;
( 1)
;
> ,
< ;
,
> .
i
i
i t
i r
tr
tt
t
tt
tr
r
tr
r
a a
c
t r
c t a c
c t a r n
c t a r t
(8)
Примем
= 0,
tr
c
если система
(8)
не имеет решений.
Замечание 3.
При
=1
r
(тогда и
=1
t
) система
(8)
не имеет решения, и в этом слу-
чае, как отмечено выше,
11
= 0,
c
но
( ) = 0
c A
A
— нулевой вектор. Поэтому будем
предполагать, что в системе
(8)
вектор
A
отличен от нулевого и
>1.
r
Теорема 8.
Пусть
,
n
A
где
1
> 0,
a
и
( ) .
A
Тогда
( , ) ( )
( ) =
.
max
tr
t r T
c
c
A
A
◄
Примем
( , ) ( )
= max .
pq
tr
t r T
c
c
A
Из первого равенства системы (8) следует
>
( 1)
= 0,
pq
i
i
i p
i q
c p q
a a
а из неравенств в системе (8) —
= ( ;
).
p
pq
q l
c
A
Поэтому
>
( ;
) = ( 1)
= 0.
p
pq
pq
i
i
i p
i q
c
c p q
a a
A
Применяя (1), получаем
1
=1
>
( ;
) = ( 1)
(
)
= 0.
i
pq
p
p
pq
pq
i
pq
i
i
i p
i
i p
a c p
c
c p p
a c p a a
A
Очевидно, что при
<
pq
c c
имеет место
( ; )<0.
p
c
A
Из теоремы 1 (пункт а)
следует, что
( , ) ( )
( )
= max .
pq
tr
t r T
c
c
c
A
A
Используя теорему 7, получаем, что
,
p
,
p
c cp a c
при котором