1. .
2. . Ui Vj , Ui+Vj=Cij , . .
3. Ui+Vj£Cij .
4. , Ui+Vj-Cij + .
5. . , , - , , , - .
, , , .
. + -, , +.
6. . , -, , , +, . , , , , ij . , .
, m+n-1. , ij, , .
7. , .
.
, , e . e .
. , (.5.2). .
5. 2
B1 | B2 | B3 | B4 | B5 | ||
A1 | ||||||
A2 | ||||||
A3 | ||||||
A4 | ||||||
, .
|
|
, - .
.
, m+n-1=4+5-1=8. , . 34 (. .5.3)
. 9, - 1 , , . , U4=0. , Ui Vj Ui + Vj=0, ij , 8 :
U4+V2=7; U4+V5=12;
U2+V3=11; U3+V4=3;
U4+V3=13; U3+V5=3;
U2+V1=2; U1+V4=1.
1- V2=7 2- V3=13.
3- V5 = 12, V5 4- , U3=-9 , , 5- 6- U2=-2 V1=4. , 7- V4=12, 8- U1=-11. Ui Vj .5. 2.
Ui+Vj£Cij
:
U1+V2=-11+4=-7£11; U1+V5=-11+12=1£4;
U2+V2=-2+7=5£8; U2+V5=-2+12=10£12;
U2+V4=-2+12=10>7; U3+V1=-9+4=-5£9;
U3+V2=-9+7=-2£6; U3+V3=-9+13=4£4;
U4+V1=0+4=4>3; U4+V4=0+12=12>10.
, 41, 44, 24 , , .
, , 24.
: 24, 34, 35, 45, 43, 23, 24.
+ -, 24 (. 5.3).
5. 3
- | - | ||||||
Ui | Bi | B2 | B3 | B4 | B5 | ||
A1 | U1=-11 | 1 150 | |||||
A2 | U2=-2 | 200 | 3 + | ||||
A3 | U3=-9 | 0 | 3 | ||||
A4 | U4=0 | 2 | |||||
Vj | V1=4 | V2=7 | V3=13 | V4=12 | V5=12 | ||
24, 34, 35, 45, 43, 23, 24.
+ - + - + - +
, ,
q=min (0, 50, 50) = 0
, 34 24, 34 . (. .5.4).
5. 4
- | - | ||||||
Ui | Bi | B2 | B3 | B4 | B5 | ||
A1 | U1=-8 | 150 | |||||
A2 | U2=-2 | 200 | 50 | ||||
A3 | U3=-9 | 3 | |||||
A4 | U4=0 | 12 | |||||
Vj | V1=4 | V2=7 | V3=13 | V4=9 | V5=12 | ||
|
|
, . , , . 24 , V4, U2. , . V4 = 9, U1=- 8. .
, 41 : Ui+Vj=0+4=4>3(. . 5.4).
+
41, 21, 23, 43, 41.
+ - + - +
q=min ( 50, 200)=50 . 50 , 50 . 41 50 . . (. . 5.5)
5. 5
- | - | ||||||
Ui | Bi | B2 | B3 | B4 | B5 | ||
A1 | U1=-7 | 11 | |||||
A2 | U2=-1 | 11 100 | |||||
A3 | U3=-9 | 3 | |||||
A4 | U4=0 | 1 50 | 7 | ||||
Vj | V1=3 | V2=7 | V3=12 | V4=8 | V5=12 | ||
. . 1 V1 . :
V1=3, U4=0, V2=7, V5=12, U3=-9, U2=-1, V3=12, V4=8, U1=-7
Ui+Vj£Cij , , 15 . , 15 .
: 15, 45, 41, 21, 24, 14, 15
+ - + - + - +
q = min (50, 150, 150)=50. 50 , 50 . , 45 :
, . V5 1, V5=11, U3 (. . 5. 6)
:
U4 + V1 = 0 +3 = 3; U4 +V2 = 0 +7 = 7;
U2 + V1 = 3 -1 = 2; V3 +U2 = 12 - 1 = 11;
V4 + U2 = 8 - 1 = 7; V4 + U1 = 8 - 7 = 1;
V5 + U3 = 11 - 8 = 3; V5 + U1 = 11 - 7 = 4.
5. 6
- | - | ||||||
Ui | Bi | B2 | B3 | B4 | B5 | ||
A1 | U1=-7 | 100 | 4 50 | ||||
A2 | U2=-1 | 100 | |||||
A3 | U3=-8 | 3 | |||||
A4 | U4=0 | 7 | |||||
Vj | V1=3 | V2=7 | V3=12 | V4=8 | V5=11 | ||
:
V1 + U 1 = 3 - 7 = - 4 < 11; U1 + V2 = 7 - 7 = 0 < 8;
V3 + U1 = 12 - 7 = 5 = 5; V2 + U2 = 7 - 1 = 6 < 8;
V5 +U2 =11-1=10 < 12; V1 + U3 = 3 - 8 = -5 < 9;
V2 + U3 = 7 - 8 = -1 < 6; V3 + U3 = 12 - 8 = 4 = 4;
V4 + U3 = 8 - 8 = 0 < 3; V3 + U4 = 12 + 0 = 12 < 13;
V4+ U4 = 8 + 0 = 8 < 10; V5 + U4 = 11 + 0 = 11 < 12.
, . 4250 .. ..
|
|
Smin = 1100 + 450 + 2100 + 11100 + 750 + 3200 + 3100+ 7200=4250 . .
: .