, , . , , , . , . , , , . , -, . , . , , .
.
, .. , .
, .
. . , . , , - , , , .
, , . , .
, . , . .
, : ; , , , .. .
|
|
, , , , , , .
.
[ ., 1972]:
, , , ;
, , .
, :
, ;
, ;
.
, . .
, , , , . , , , . , , ( ) , , .
. ( , , .) . , - , .
, . . , , , .
, , .
, . , .. [ .., 1972]:
|
|
ü ;
ü , .. ;
ü , , .
R.
, R [ .., 1972].
1. , . ( ), .
2. ; , . , ( , ).
3. . ( ) .
() . , .. ( R*). , . .
. . :
ü ;
ü ;
ü .
, . [ .., 1972]:
1. .
, . S = {si}, i = 1,n ( ).
2. .
, . , , ( Ψ).
3. .
Ψ , . , , , .
, [ .., 1972]:
Ø , , ;
|
|
Ø , , .. , , , , , .
, , . , ; P(v), v= 1,V . , -. - , , , . , , , , .
, , , , .
10, . 132. , , . , , .
10
/ | |||
1. | R* = max R s S | ||
2. | P(v), v= 1,V | V R* = max ∑ R P(v) s S v=1 | |
3. | - | V R* = max 1/V ∑ R s S v=1 | |
4. | - | R* = max min R s S v V | |
R* = max max R s S v V | |||
- () | R*=α min R+(1-α) max R v V v V (0 ≤ α ≤ 1) | ||
() | R* = max min (max RR) s S v V s S |
, .
(. 133).
, , . p u1 1 - p u2. q v1 1 - q v2. , , [ .. ., 1990]:
|
|
pu1 + (1 - p)u2 > qv1 + (1 - q)v2.
μ(), μB(b) a, b A B, [ .. ., 1990]:
μ() = max (min(μp(p), μ1(u1), μ2(u2))), (1)
pu1 + (1 - p)u2
μ() = max (min(μQ(q), μB1(v1), μB2(v2))), (2)
qv1 + (1 -q)v2
μp(p) p .
, [ .. ., 1990]:
μ(X→Y) = μ(-X U Y) = max (1 - μ(X), μ(Y)), (3)
X Y X, Y.
, X Y a b, μX(,b), μY(,b),
μ(X→Y) = min (1 μX(a,b), μY(a,b)), (4)
a,b
Y :
Y1: »,
1, a > b;
μY1(a,b) =
0, ≤ b;
Y2: »,
1, a ≥ (b + 0,2);
μY2(a,b) = 0,5 + 2,5 (a b), (b + 0,2) ≥ a ≥ (b 0,2);
0, ≤ (b 0,2),
μX(a,b) , b . ,
μX(,b) = min(μA(a), μB(b1)).
(4) :
μ(X→Y) = min [max (1 μX(a,b), μY(a,b))] =
a,b
= min [max (1 min (μA(a), μB(b)), μY1(a,b))].
a,b
> b μY1(a,b) = 1. (,b), min
a,b
, ≤ b. ,
μ(X→Y) = min [max (1 (μ(a), μ)) =
a≤b
= 1 - max (min (μA(a), μB(b))).
a,b
, = b. ,
μ(X→Y) = 1 - max (min (μA(a), μB(a))).
. 134.
, . , , . , , , .. . . () . ().
() . , , .
: [ .. ., 1972].
(, ). . . , , (, , ..).
, (. 135 [ .. ., 1972]). , , . ( ) .
, .. (, ), .
, .
|
|
, , . , , .
. , , , .
.
-, , . -, , , , . -, , , , . , , , .
, (. 135).
, , , , , ( ), . , .
[ .. ., 1972]. , 0, , . , ( ). , ( . 135 1). , , , ( ). , (, 2 3 . 135). k-1 , (k-1)- . , , (k-1)- , , , , ( ). k- , , , (k-1)- .
. (), , , ; , .
, , .. (i, j), i , j .
() . .
, . , , .
(), . , 0-1-2-3-4-5-6-7 , . 135, 0, 1, 2, 3, 4, 5, 6, 7 (0-1), (1-2), (2-5), (5-6), (6-7).
, , - , () . , , , 0 (, 1 . 135). 0 , , . , . 135 4 , , 0, (0-1), (1-3) (3-4) (0-1), (1-2) (2-4).
.
, . , , , , , - .
, , , . . , . . , . , , .
, , . , , , , , . .
, , .
, , , .. . , () .
( ) . , , , .. [ .. ., 1972]
= Σ ti,j,
ti,j
ti,j , i j i j.
, , .. .
, . . , . , , .
, .. , . , , , , , .
: ? , , , , - . . , . .
[ .. ., 1972]:
j- Tp(j);
i- T(i);
- Ri;
(i, j) - r(i, j);
(i, j) r(i, j).
j- [ .. ., 1972]:
Tp(j) = max {Tp(i) + tij}, (1)
i S-1j
tij (i, j)- ;
S-1j , j- .
(1) , . , , . 135, (1), [ .. ., 1972]:
Tp(0) = 0;
Tp(1) = Tp(0) + 4 = 4;
Tp(2) = Tp(1) + 8 = 12;
Tp(3) = Tp(1) + 4 = 8;
Tp(4) = max [(Tp(2) + 12), (Tp(3) + 24)] = 32;
Tp(5) = max [(Tp(2) + 4), (Tp(4) + 4)] = 36;
Tp(6) = max [(Tp(4) + 4), (Tp(5) + 8)] = 44;
Tp(7) = Tp(6) + 4 = 48.
i , , , .. [ .. ., 1972]
T(i) = max {T(j) - tij}, (2)
j Si
Si , i- .
T(i) (2) n 0, T(n) = Tp(n). , . 135.
T(7) = 48;
T(6) = T(7) - 4 = 44;
T(5) = T(6) - 8 = 36;
T(4) = min [(T(6) - 4), (T(5) - 4)] = 32;
T(3) = T(4) - 24 = 8;
T(2) = min [(T(4) - 12), (T(5) - 4)] = 20;
T(1) = min [(T(3) - 4), (T(2) - 8)] = 4;
T(0) = T(1) - 4 = 0.
T(i) T(i), [ .. ., 1972]
Ri = T(i) - T(i) (3)
R0 = 0; R1 = 0; R2 = 8; R3 = 0; R4 = 0; R5 = 0; R6 = 0; R7 = 0.
, , 2, .
(i, j) [ .. ., 1972]
r(i, j) = T(j) - T(i) - tij. (4)
(i, j) [ .. ., 1972]
r(i, j) = Tp(j) - T(i) - tij. (5)
:
r(0,1) = 4 0 - 4 = 0; r(2,4) = 32 12 - 12 = 8;
r(1,2) = 20 4 - 8 = 8; r(4,5) = 36 32 - 4 = 0;
r(2,5) = 36 12 - 4 = 20; r(1,3) = 8 4 - 4 = 0;
r(5,6) = 44 36 - 8 = 0; r(3,4) = 32 8 - 24 = 0;
r(6,7) = 48 44 - 4 = 0; r(4,6) = 44 32 - 4 = 8.
:
r(0,1) = 4 0 - 4 = 0; rc(2,4) = 32 20 - 12 = 0;
rc(1,2) = 12 4 - 8 = 0; rc(4,5) = 36 32 - 4 = 0;
rc(2,5) = 36 20 - 4 = 12; rc(1,3) = 8 4 - 4 = 0;
rc(5,6) = 44 36 - 8 = 0; rc(3,4) = 32 8 - 24 = 0;
rc(6,7) = 48 44 - 4 = 0; rc(4,6) = 44 32 - 4 = 8.
, , , .. . , , . , , . .
, , . , , .
(i, j) ∆tij > r(i, j) ∆tij - r(i, j).
∆tij ≤ r(i, j) , . , , . , , . , .
, , . 0-1-3-4-5-6-7.
T = t0,1 + t1,3 + t3,4 + t4,5 + t5,6 + t6,7 = 48.
, ( ), . . , , , . , , , , .
. , . . , , .
. , , , , .
, , , . , : (tmin), (tmax) (t).
.
.
, , .
tij σ2ij [ .., .., 1967]:
tij = (tmin + 4t + tmax)/6 (6)
σ2ij = [(tmax tmin)/6]2 (7)
, . , ( , , ..) . , , tij, (6) (ij). , tij, , .. Σ tij ( , , , ). , Σσ2ij.
, . , T ≤ T ( T () ).
:
;
;
;
;
, .
. , .
, , .
, . , .
, , .
, . , , , .
, ( ).
[ .., 1974]:
1. :
;
.
2. :
;
.
3. :
-;
-.
4. :
;
;
;
.
5. :
;
;
;
.
6. :
;
;
;
;
;
;
.
:
ü ;
ü , ;
ü , ;
ü .
:
ü ;
ü ;
ü ;
ü .
[ .., 1974].
. , . . , - : . - , .. .
. . .
. . , . .
. , , , .. , .
, , , . , , - . . , , , . . , , , , .
, , , () . . . .
.
. . , . , , , ; , , .
, . , , .
, , , , , , , .
, . . , : , . , .
; , . , . . , , .. .
, . , - . , , .. . , , .
. () . . , , , () , ( ). , , .
- , .
, .
, , . , . , , , .
. . , , . .
, ( ). , , , , .
, . , , , . , : , , .
-.
, . . , , .
, , (, ) , . , , , . , () . , , . , () .
, , , . , . , .. .
, . , , , .
, , . , . , , , , , .. , .
, , , . , , . , , , , , . , , .
, , .
, , . , , . , .
( ), . . , .
, , () . , . .
.
, . , . , , .. , , .
, , , , . , .. , . , . , , , . , .
, .
, .
- , , .
- , , .
, .
, . . .
, , .