, , . . , , , , , . , , , .
(2.11)
(2.12)
(2.13)
. (2.12), (2.13) . . . , (2.11) (2.13) .
. , .
. . . N . (2.11) F , , ( ).
:
(2.14)
. (2.15)
(2.14) ( (2.15)) ., F . =( . :
(2.16)
. .
=( .
.
1. .
2. =( .
3. .
4. , ( ). .
5. .
2.3.
( ) :
1) ;
2) ;
:
, .
, , , , , - , .
,
. (. , :
|
|
,
).
, .
( .
.
, ( ) , 1. , , ) . . -, , . , - , - . -, . .
) , (2.17)
(2.18)
, (2.19)
. - :
) (2.20)
( (2.21)
, (2.22)
(2.20) - (2.22) . Ÿ :
).
(2.18) , .
.
) (2.23)
- (2.20) - (2.22) , (2.17)-(2.19).
, , - ,
).
.
, , n- .
( )
, , . , :
1. (, );
2. , ;
3. ;
4. , . .
:
, m ( i). , i=1,2,..,m.
, i - , bi . , n , ( j, j=1,2,,n). i - j - aij. -, m×n aij .
|
|
2.1
n | |||||
m |
, , cj j - . j - , , xj.
, , :
X = (x1, x2, , xn), :
( (2.24)
(2.25)
.
i , i - , bi . , j - , xi >0, , xi =0.
.. .
2.5.
. m n , . j ( ) i, ij. , , .. k kij.
, , , ai , i, bj >j. . , , , :
1. , , . "" n +1 0 i.
2. , . , m+1 .
:
(2.34)
,
xij , i j, ij ( i j).
:
. 800, 900 600 . . , 300, 600, 650 750 . . 1 . :
2.2
1 | 2 | 3 | 4 | |
1 | ||||
2 | ||||
3 |
( , ), .
, 800+900+600=2300 300+600+650+750=2300. :
- , i j .
|
|
. . , - , , .
, - . :
.
2.3
1 | 2 | 3 | 4 | 5 | >i | |
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
bj |
("- " ). . 1 18 . 48, 1, 18 (1,1). 1 , 1 30 . 2 (27 ), 27 (1,2); 3 1 3. 3 39 . 30 2, , 9 3. 18 3 12 4; 6 5, 20 4 . ; , . , , -. , , . :
2.4
1 | 2 | 3 | 4 | 5 | i | |
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
bj |
, , ij.
- - , Ai Bj, , . , Bj. - . , , , 2.4.
, Cij Cik Ai Bj Bk . , , , . , , 2: C21 = C24, b1 b4, 4 (2,1).
|
|
2.5
1 | 2 | 3 | 4 | 5 | i | |
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
bj |
. , Bi Aj Cji.
, , . , F0 =1039, F0 =723.
, , . m+n -1. , , m + n - 1.
. . , , 4
m+n-1 =4+5-1=8,
7, 3 2 0., (3,5).
- Cij, , .
.
, - .,,18 (1,1) (2,1) 18 (2,3) (1,3). . ( 1039) ( 913) , 126 . , 18 :
2.6
1 | 2 | 3 | 4 | 5 | i | |
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
bj |
.
, , , 90.
:
1)
2)
3)
, , (). + ,
, , , . .
- , , , , , ., : , - . , , . : . ., , , ` +`, ` -`.
γ. γ. k kγ. , , . , , kγ. , , , . , , , .
, , , , .
|
|
, , , -: () , .
m+n-1.
, . , , , . , , , .
k, , , ( , ).
; .
, , : . , .
.
, .
.
Ai Bj C ij; . xij, .
. Ai ( ) - αi;
Bj ( ) βj. (). ai +bj = č ij (i=1..m; j=1..n) č ij Ai Bj.
, αi βj ; , - .
, (αi βj) .
(αi βj) č ij Cij. . , xij ( m + n -1). xij>0. (αi βj) , :
č ij=αi+βj= ij, xij>0.
( xij =0), , .
, . : xij>0,
αi+βj= č ij= ij, xij=0,
αi+βj= č ij≤ ij,, . , , . :
č ij= ij ( ) (2.35)
č ij ≤ ij ( ) (2.36)
, (αi βj) Ai Bj (i=1,...,m;j=1,...,n). : .
, - .
, , (2.35). , ; , ., . :
(αi βj) (2.35), :
γi,j=i,j - č i,j.
, : .
() .
(, ). m+n-1 , m - , n .
(αi βj), , :
αi+βj= ij (2.37)
(2.37) m+n-1, m+n.
, (, ).
m+n-1
(2.37) αi, βj,
, č i,j=αi+βj .
2.7
1 | 2 | 3 | 4 | 5 | αi | |
1 | č= 7 | č= 6 | č= 6 | α1= 0 | ||
2 | č= 5 | č= 4 | č= 5 | α2= -1 | ||
3 | č= 8 | č= 6 | č= 7 | α3= 1 | ||
4 | č= 6 | č= 5 | č= 6 | α4= 0 | ||
βj | β1= 7 | β2= 6 | β3= 5 | β4= 6 | β5= 6 |
α4 =0,=> β4 =6, α4 + β4 = 44 =6,
=>
α1 =0, α1 + β4 = 14 =6,
=>
β3 =5, α1 + β3 = 13 =5,
=>
β1 =7, α4 + β1 = 41 =7,
=>
α2 =-1, α2 + β1 = 21 =6,
=>
β5 =6, α2 + β5 = 25 =5,
=>
α3 =1, α3 + β5 = 35 =7,
=>
β2 =6, α3 + β2 = 25 =7.
, č ij≤ ij, , . ( ), , . .
6 č ij≥ ij, . , č ij- ij . ( 1),, ,, (4,2):
2.8
6 + | 7 | 5 - | -1 | |||
7 + | ||||||
7 - | 5 + | |||||
14, , , -. 14 - +.
αi βj .
, :
1) , m+n-1 ( ).
2) (αi βj) , . , , .
3) č i,j=αi+βj . , , .
4) , , ( ).
5) , , , , .
2 . : F0=723,F1=709,F2=Fmin=703.
, , Fmin = 703.