. n () - M 1 M 2 ( ), - . Pj Mi ; τij. .
, ; , . , - , , (, - - 5 20 ).
, 1- , - . . 2- . ,
) 1- ;
) 2- .
2- . , - 1- , ( ). 2- ( , 1- ), , 2- ( -), . .
, ( , , c ) , , .
1. τij (i = 1, 2; j = 1, , n) 1. á - 1, 2, 3, 4, 5, 6 .1; 5, 2, 4, 3, 6, 1- 1b. 2- 1- 3 .
1
i | ||||||
.1. . , 11,5%.
(.. A) , , , - n!. , (, , 2- ) . , . . , , , , .
|
|
. - . , 1, 2, , n. -
Aj = τ 1 j, Bj = τ 2 j (j = 1, 2, , n). (1)
k 1 n 1. - , k - (k +1)- : 1, , k +1, k, , n. :
min{ Ak, Bk +1} < min{ Ak +1, Bk }, (2a)
min{ Ak, Bk +1} > min{ Ak +1, Bk }. (2b)
min{ Ak, Bk +1} = min{ Ak +1, Bk }. (2)
, - .
1. , - (2a). , (2b). , (2).
, 3- 1- 2-. , 1- 2- ( , (2a) (2b) ). 1- .
1. 2 n A 1, , An, B 1, , Bn . :
) A 1, , An;
) B 1, , Bn A 1, , An ( ) )).
). 1. k +1, k 1 n 1. (2b) (2), 1 k - (k +1)- , ( (2)) . - 1- (.. ). , .
). k, k 1 n 1. (2b) (2). ( - 1) k - (k +1)- . 2- k - (k +1)- . , 2- n.
, , . - , , ) 2 n ( 1), ) 1 n 1 ( n). ( ) , . , - ( ), , - , :
|
|
1) A 1 ≤ A 2 ≤ ≤ As; 2) Ai ≤ Bi (i = 1, , s), (3a)
, ,
1) Bt ≥ ≥ Bn -1 ≥ Bn; 2) Bi > Ai (i = t, , n). (3b)
, . (3a) (3b) , : , τ 1 i ≤ τ 2 i, , τ 1 i > τ 2 i. 1- τ 1 i; - 2- τ 2 i; 1- , 2- . , m,
A 1 ≤ A 2 ≤ ≤ Am, Ai ≤ Bi (i = 1, , m), (4a)
Bm +1 ≥ ≥ Bn -1 ≥ Bn, Bi > Ai (i = m +1, , n) (4b)
( m =0 m = n, .. , ).
, , , -
2. - , (4), - .
3. , (4), .
. m -. 1- G 1, , Gd,
< < ; (5a)
2- H 1, , He,
> > . (5b)
. , (4), Gi Hj. π 1 π 2 G 1. π 1 π 2 - . G 1
Ak = Ak +1 = , Ak ≤ Bk, Ak +1≤ Bk +1, (6)
(6) ,
min{ Ak, Bk +1} = min{ Ak +1, Bk } = . (7)
, 1, , - G 1, . - 3 ■
2 3 , , - (4), . (, 2- 1.) . - . , - , , . ( , ) .