. -. - , mn , , ( ).
; , .
Ai Bj cij; (cij) . (xij), , :
L = min.
. , Ai Ui, Bj Vj.
Ui + Vj = (i=1,...,m; j=1,...,n) Ai Bj. Ui, Vj . U1,..., Um, V1,..., Vn (Ui, Vj).
, (xij) , .. m + n - 1. xij > 0.
(Ui, Vj) , :
=Ui + Vj = cij xij > 0;
, :
= cij > cij < cij.
. , m+n , :
(1) + =cij >0, ij , ;
(2) + £cij =0, ij , .
.
.
L =
, , , (*) Ui (i=1,2,,m), (**) Vj (j=1,2,,n), Z= + £cij (i=1,2,,m, j=1,2,,n). * - , Y*=(, ) Lmax=Zmin
, , , , , , - , ..
|
|
+ =cij x* ij>0;
+ £cij x* ij=0.
¨
, , . .
, , :
) , :
(1) + =cij xij>0;
) , :
(2) + £cij xij=0.
(2), , , , (.. ). , .
:
. , 1.
. 1
B1 | B2 | B3 | B4 | ai | |
A1 | |||||
A2 | |||||
A3 | |||||
bj | 1000¹1100 |
1. . , .
:
. 4-, 4=1100-1000=100 (. . 2).
2. ( ), ( m+n-1). ( ).
(. . 2). 1 4+4-1=7 .
. 2
B1 | B2 | B3 | B4 | ai | |
A1 | - | - | - | ||
A2 | - | - | |||
A3 | - | ||||
A | - | - | - | ||
bj | 1100=1100 |
:
Z(X)=1*200+2*200+3*100+7*100+9*300+12*100+0*100=5300.
3. . (1) . m+n Ui, I=1,2,,m Vj, j=1,2,,n. m+n-1, .. m+n-1 . , , ( U1) . .
, .. m+n-1, . m+n-1, . , , . , .. , , .
|
|
. , . , , , .
. . (1), , - , (1) .
:
U1+V4=1,
U2+V1=2,
U2+V2=3,
U3+V2=7,
U3+V3=9,
U3+V4=12,
U4+V4=0.
U3=0, V2=7- U3=7,
V3=9- U3=9, V4=12- U3=12,
U1=1-V4=-11, U4=0-V4=-12,
U2=3-V2=-4, V1=2- U2=6.
. 3
V1=6 | V2=7 | V3=9 | V4=12 | |
U1=-11 | ||||
U2=-4 | - 3 | 5 | + 6 2 | |
U3=0 | 0 | + 7 100 | - 12 | |
U4=-12 |
4. (2) + £cij xij=0. (2), .. , , , .
: Ui+Vj£cij, , Ui+Vj>cij, , , .
, , Dij=(Ui+Vj)-ij>0 . Dij ( ) .
: , ( ) Dij£0.
D23=0, D24=2, D31=0. , .. D24=2. . . 3.
5. , .
, - .
, , , , . , (l,k), D lk = {Dij}= [(Ui+Vj)-ij].
, {D24=2}=D24.
6. .
, , + , . , . m+n, , , , +, , . . , , +, - +.
|
|
q0= {xij}, xij , , -. q0 , . q0 +. , q0 -, +. q0 , , m+n-1.
+ (2,4) , . , (2,4), (3,4), (3,2), (2,2).
(2,4) +, . q0 , , -:q0=100.
6. q0 , . .
, , . 5. , + £cij.
, , . 5.
, , ij .
1. .
2. .
3. .
4. .
1. : .
2. .
3. .
4. - .
5. .
6. . .
.
: [ 3, 5, 6, 7, 8, 11]