. , I , S . , , I S. (i, j), . (i, j), , , /.
8.1 , ( ). , 8.1 : I II. I ={1} ={2, 3, 4, 5}, , (1, 2), (1, 3) (1, 4). II ={1, 2}; ={3,4,5}, (1, 3), (14)), (2, 3) (2, 5).
.
:
rij , .
X ={ xij } /.
xij , .
X ={ xij } /, , I S /. , X , I S, :
, X ={ xij }, /, , / .
, . I S , I S. , , [2].
1956. , .
. . , .
, . i j , :
1) xij < rij ;
2) rij >0 .
Q, Q = min { qi, 1 ≤ i ≤ l } qi = { xij rij, , xij, }. , Q, Q .
|
|
, , , .
[2]. . , . , , , , , . 3- : , .
1.
.
.
, z. [ i, +, e (z)], i z; , , (i, z) ; e , . y, (z, y) . y [ z, +, e (y)], e (y) = min { e (z), rzy xzy }. y, . [ z, -, e (y)], e (y) = min { e (z), xzy }. y , z - .
. [~, ~, ∞] , . , . , , - .
2.
.
z. [ y, +, e ], (y, z) e. [ y, -, e ], (y, z) e. y , y.
, , , .
- . - , .. . , .
8.2. , , . (1,2),(2,3),(3,4) ( 8.3).
8.2
8.3
(1,3),(3,2),(2,4). (3,2) , , . ( 8.5) .
|
|
8.4
, 1000 . , (1,2),(2,4), . , , . , . . , 70- . 2 , -.
-:
1) . , . , .
2) - . , .
, [6].
-
(i,j) () (r ij, rji). , , . ( ij, ji) . , , .
j, i, [aj,i], ai , j i. .
1 (i,j) , , .. ( ij, ji) = (r ij, rji). 1=∞ 1 [∞,-]. i =1 2.
2 S i, j, i (.. cij >0 j Î Si) . Si ¹ Æ, , 4.
3 Si k, . a k = cik k [ ak, i ]. (.., k=n), , . i=k .
4 ( ). i =1, , 6. i ¹ 1, , i, i , r ( Si). i=r 2.
5 ( ). N p ={1, k 1, k 2,, n } , p - ( 1) ( n). , , f p =min{ a 1, ak 1, ak 2,, an }. , , fp . (i,j), , ( ij, ji) :
) (ij- fp, cji + fp), i j,
|
|
) (ij+ fp, cji - fp), j i.
, 4 . i=1 .
6 ().
) m F=f1+ f 2 ++ fm.
) (r ij, rji) ( ij, ji) (i,j), . (a, b)= (r ij - ij, rji - cji). a>0, , (i,j), a. b>0, b. , a>0, b>0, .
, .
8.1
, 8.1 -. 8.5 .
1
( ij, ji) (r ij, rji).
1. 1=∞ 1 [∞, - ]. i=1.
2. S 1 =[2,3,4] ¹ Æ.
3. k =3, c 13 =max {c 12,c 13,c 14 }=max {20,30,10}=30. a 3 =c 13 =30 3 [30,1]. i=3 2.
2. S1=[4,5] ¹ Æ.
3. k=5 a5=c35=max{10,20}=20. 5 [20,3]. . 5.
5. , 5 . 1: (5) [20,3] (3) [30,1] (1). , N 1 ={1,3,5} f 1 =min {a 1, a 3,a 5 }={∞,30,20}=20. N 1:
(13, 31)=(30-20, 0+20)=(10,20),
(35, 53)=(20-20, 0+20)=(0, 20).
2
1. 1=∞ 1 [∞, - ]. i=1.
2. S 1 =[2,3,4] ¹ Æ.
3. k =2, c 12 =max {c 12,c 13,c 14 }=max {20,10,10}=20. a 2 =c 12 =20 2 [20,1]. i=2 2.
2. S 2=[ 3,5] ¹ Æ.
3. k =3, a 3 =c 23 =40. 3 [40,2]. i=3 2.
2. S3=[4]¹Æ.
3. k =4, a 4 =c 34 =10. 4 [10,3]. i=4 2.
2. S 4 =[5] ¹ Æ. 1 3 , S4.
3. k =5, a 5 =c 45 =20. 5 [10,3]. i=4 2.
5. N 2 ={1,2,3,4,5} f 2 =min{∞,20,40,10,20}=10. N 2:
(12, 21)=(20-10, 0+10)=(10,10),
(23, 32)=(40-10, 0+10)=(30,10),
(34, 43)=(10-10, 5+10)=(0,15),
(45, 54)=(20-10, 0+10)=(10, 10).
3
1. 1=∞ 1 [∞, - ]. i=1.
2. S1=[2,3,4] ¹ Æ.
3. k =2, a 2 =c 12 =max {10,10,10}=10 2 [10,1]. i=2 2.
2. S 2 =[3,5] ¹ Æ.
3. k =3, a 3 =c 23 =30 3 [30,2]. i=3 2.
2. S3={ Æ } ( c 34 =c 35 =0). 4.
4. [30,2] 3 r =2. 3 , . i=r=2 2.
2. S 4 =[5] ¹ Æ. 3 .
|
|
3. k =5, a 5 =c 25 =30. 5 [30,2]. . 5.
5. N 3 ={1,2,5} f 3 =min{∞,10,30}=10. N 3:
(12, 21)=(10-10, 10+10)=(0,20),
(25, 52)=(30-10, 0+10)=(20,10).
4
N 4 ={1,3,2,5} f 4 =10.
5
N 5 ={1,4,5} f 5 =10.
8.4 -
6
, , 1, . 6 .
6. F=f1+ f 2 ++f 5 =20+10+10+10+10=60. . 8.2
8.2 8.1
(rij-rji)-(cij-cji) | |||
(1,2) | (20,0)-(0,20)=(20,-20) | 20 | 12 |
(1,3) | (30,0)-(0,30)=(30,-30) | 30 | 13 |
(1,4) | (10,0)-(0,10)=(10,-10) | 10 | 14 |
(2,3) | (40,0)-(40,0)=(0,0) | 0 | - |
(2,5) | (30,0)-(10,20)=(20,-20) | 20 | 25 |
(3,4) | (10,5)-(0,15)=(10,-10) | 10 | 34 |
(3,5) | (20,0)-(0,20)=(20,-20) | 20 | 35 |
(4,5) | (20,0)-(0,20)=(20,-20) | 20 | 45 |
1 ?
2 -.
3 ?
4 -?
5 -?
6 -.
()
- | |
- | |
- | |
- | |
- | |
- | |
1 , . . Excel: / . . .- , , 2006. - 337 .
2 , . . .1 / .; . . - .: , 1972. - 335 .
3 , .. : / . , .., ..; . .. - .: , 2001. - 407 .
4 , .. : / .. . , 2007. - 16 .
5 , .. : 230105 , / ... - : , 2007.-36.
6 .. : 230100 , 230105 , 230400 , 230401 / ... : , 2011. 58.
7 , .. : . - . 2-, / .. . - : , 2001.- 528 .
|
|
8 , . . .- . 6- / ., .; . . : , 2001- 912 .: .
9 , . / . . .: - , 1983. 592 c.
.
, , , .
-, -, .
, : , .
. ,
, , .
, , 3 V 18 36 , [4] [5].
. 𠠠 . ..
֠ ..
10.10.2011
60×84 1/16. . 2/9(2011).
100. .-..3,75.
-
660049, ., . , 82
(391) 227-69-90
(391) 211-97-25