.
, . , . , .
1, 2,..., m, , , ai (i=1, 2,.... ). n B1, B2,.... Bn, ; bj (j=1, 2,..., ). Ai Bj, ij =(cij).
, .. , Ai j .
, Ai Bj, ij. xij, , :
(10)
:
, (11)
, (12)
.
(11) ; (12) .
(10) (12) :
(13)
, (13), , .
.
, . , i- (i- ) ui , j (j- ) Vj, . , ..
(14)
( ). : - , , . (14) ; , ( ), . . , (10).
|
|
(13) , (11) (12) . . , (12), (11).
. , (13) (11), (12) + 1. + - 1. ( ), . 6, + - 1 , . .
6
1. . ( ): - . , , , ; , . , + - 1. ( ) , , , , , , . . - ( ), (-) . . 7: (1;1) , (1;2) ; (2;2) ; (2;3) ; (3;3) ; , (3:4) . m+n-1=3+4-1=6. :
|
|
7 -
4 | ||||
, ij , ( ) .
cij. , , . , , , , . , . . , , . 8.
8 -
4 | ||||
: (2;1), (3;2), (1;3), (2;4), (1;4), (3;4). , . 3.7, :
f(X) = 1*30 +2*100 + 2*40 +2*70 + 3*20 +4*20 = 590.
, , , - .
2. . ui ( ), i = 1, , Vj ( ), , j = 1, n. , . , (i;j) (14). (14), ( ), + 1 + ui vj. , (, u1 = 0), .
- , . 7. 1 = 0 (14) (1;1) (1;2), v1 = 4 v2 =5. v2, (2;2) u2 = 2, u2, (2;3) v3 = 8. v3, (3;3) 3 = 1, (3;4) v4 =5. . 9, , .
9 - -
30 | |||||
5 - | 2 | ||||
70 | - 30 | ||||
|
|
, . 3.8, 3 .
, . 8, . 10.
10 -
4 | |||||
-1 | |||||
, (i;j) , dij, :
(15)
, ; Vj. , ( ). , . , : , , , .. , . , .
(15) . , - (. . 9), :
(16)
, (, 1170).
, (. 10), :
, , .. ( 590). , , , .. , , . , . , , .
3. ( ). , ; , ( ) . , , . 9, (1;3) (. (16)).
(), , ; . , , , ( , ). , , , . + -, + . . 9, (, . 12).
|
|
-, + -. , , , . , - ( . 9), , , .
. 9 . 11.
f(X) =4*30 +5*0 +2*30 +3*100 +7*10 +4*110 = 990, 1170, . 11 . ( ui Vj , 2):
11 -
30 | |||||
-5 | |||||
-1 |
, ( , ), ; . 11. , .. ( ). , ; , , , . .