.


:




:

































 

 

 

 





 

, , . , , , . , . , , , . , -, . , . , , .

.

, .. , .

, .

. . , . , , - , , , .

, , . , .

, . , . .

, : ; , , , .. .

, , , , , , .

.

[ ., 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].

. , . . , - : . - , .. .

. . .

. . , . .

. , , , .. , .

, , , . , , - . . , , , . . , , , , .

, , , () . . . .

.

. . , . , , , ; , , .

, . , , .

, , , , , , , .

, . . , : , . , .

; , . , . . , , .. .

, . , - . , , .. . , , .

. () . . , , , () , ( ). , , .

- , .

, .

, , . , . , , , .

. . , , . .

, ( ). , , , , .

, . , , , . , : , , .

-.

, . . , , .

, , (, ) , . , , , . , () . , , . , () .

, , , . , . , .. .

, . , , , .

, , . , . , , , , , .. , .

, , , . , , . , , , , , . , , .

, , .

, , . , , . , .

( ), . . , .

, , () . , . .

.

, . , . , , .. , , .

, , , , . , .. , . , . , , , . , .

, .

, .

- , , .

- , , .

, .

, . . .

, , .

 





:


: 2015-11-05; !; : 629 |


:

:

.
==> ...

1720 - | 1689 -


© 2015-2024 lektsii.org - -

: 0.22 .