. , , ,

,,,

.

1. 23

2. 37

3. ...12

2 18

1.    .

. , , . , .

2.    .

X ij , i j, C ij i j. , X ij > 0 C ij > 0.

X ij :

X 11 + X 12 + X 13 + X 14 = 25

X 21 + X 22 + X 23 + X 24 = 45 (1)

X 31 + X 32 + X 33 + X 34 = 30

X 11 + X 21 + X 31 = 30

X 12 + X 22 + X 32 = 10 (2)

X 13 + X 23 + X 33 = 30

X 14 + X 24 + X 34 = 30

:

Z = C ij X ij = 21* X 11 + 36* X 12 + 28* X 13 + 21* X 14 + 25* X 21 +

35* X 22 + 26* X 23 + 25* X 24 + 23* X 31 + 21* X 32 + 27* X 33 + 21* X 34,

.. Z = C ij X ij. (3)

X ij, (1) (2) Z (3). .

:

S i = M j

, S i = X ij c ;

M j = X ij ,

.

S i = M j = 100,

, .

3.     .

:

1.     .

2.     .

.

(

). .

:

X 14 = min (25, 30) = 25

X 32 = min (30, 10) = 10

X 34 = min (20, 5) = 5

X 31 = min (15, 15) = 15

X 21 = min (45, 15) = 15

X 23 = min (30, 30) = 30

Z = 25*21 + 25*15 + 30*26 + 15*23 + 10*21 + 5*21 = 2340 . .

.

U i V j, ,

C ij U i V j = 0 (4)

. :

1. X ij > 0 (. . ) :

C 14 U 1 V 4 = 0 21 U 1 V 4 = 0

C 21 U 2 V 1 = 0 25 U 2 V 1 = 0

C 23 U 2 V 3 = 0 26 U 2 V 3 = 0 (5)

C 31 U 3 V 1 = 0 23 U 3 V 1 = 0

C 32 U 3 V 2 = 0 21 U 3 V 2 = 0

C 34 U 3 V 4 = 0 21 U 3 V 4 = 0

m + n , m + n 1 ( m , n ). , , , (5).

m + n 1 = 6 6.

U 1 = -2

U 2 = 0

U 3 = -2

V 1 = 25 V 2 = 23 V 3 = 26 V 4 = 23

2.     4, , , : U 2 = 0,

V 1 = 25; U 1 = -2;

V 2 = 23; U 2 = 0;

V 3 = 26; U 3 = -2.

V 4 = 23;

.

3.     , . . X ij = 0 ( ), :

G ij = C ij S ij, S ij = U i + V j.

G 11 = C 11 U 1 V 1; G 11 = 27 (-2) 25 = 4;

G 12 = C 12 U 1 V 2; G 12 = 36 (-2) 23 = 15;

G 13 = C 13 U 1 V 3; G 13 = 28 (-2) 26 = 4; (6)

G 22 = C 22 U 2 V 2; G 22 =35 0 23 = 12;

G 24 = C 24 U 2 V 4; G 24 = 25 0 23 = 2;

G 33 = C 33 U 3 V 3; G 33 = 27 (-2) 26 = 3.

, (. ) .

, Z 2340 . . :

X 14 = 25, X 21 = 15, X 23 = 30, X 31 = 15, X 32 = 10, X 34 = 5.

3

1.    .

7 . , , .

.

4


1 7 5



3

2

8

6

2.    .

G(A, U) , A , ( 1, 2, 3, 4, 5, 6, 7, 8), U , . L ij (i, j = 1, 2,, 8 ( ).

i j :

Y = L i X ij ,

X ij = 1, i j,

X ij = 0, .

.

:

(X ij X ji) = 0, i = 2, 3,,m 1

(. . i, , , , , );

(X 1j X j1) = 1.

(. . , );

(X mj X jm) = 1.

(. . , 1, , ).

X ij, 0 1,

Y , .

.

3.     .

, . -

L ij , i j , . , . , .

, U i V j (U i 1 i, V j 1 j). , .

:

1.     U 1 = V 1 = 0/

2.    

V j U i , . . V 2 = 8, V 3 = 10, V 4 = 10, V 7 = 12, U 2 = V 2 = 8, U 3 = V 3 = 10, U 4 = V 4 = 10, U 7 = V 7 = 12 ( )

3.     V j.

V 5, V 6 V 8. , V j, V j = U i + L ij, U i.

, V 5, 򠠠 L 4, 5 = 16 L 7, 5 = 25. U 4 U 7 : U 4 = 10, U 7 = 12.

,

V 5 = min(U 4 + L 4, 5 = 10 + 16 = 26; U 7 + L 7, 5 = 12 + 25 = 37) = 26.

, V 6, L 2, 6 = 7, L 3, 6 = 17, L 7, 6 = 18. U 2, U 3, U 7 : U 2 = 8, U 3 = 10, U 7 = 12. ,

V 6 = min(U 2 + L 2, 6 = 8 + 7 = 15; U 3 + L 3, 6 = 10 + 17 = 27;

U 7 + L 7, 6 = 12 + 18 = 30) = 15.

, V 8, L 5, 8 = 17, L 6, 8 = 13, L 7, 8 = 19. U 5, U 6, U 7 : U 5 = 26, U 6 = 15, U 7 = 12. ,

V 8 = min(U 5 + L 5, 8 = 26 + 17 = 43; U 6 + L 6, 8 = 15 + 13 = 28;

U 7 + L 7, 8 = 12 + 19 = 31) = 28.

V i ( ).

4.     .

, . . L ij >= V j U i .

L ij >= V j U i . . , 1 :

V 2 = 8, V 3 = 10, V 4 = 10, V 5 = 26, V 6 = 15, V 7 = 12, V 8 = 28.

1 5. 5 , L ij = V j U i :

L 4, 5 = V 5 U 4 = 26 10.

L 4, 5 , , 4 .

, 4 :

L 1, 4 = V 4 U 1 = 10 0 = 10.

L 1, 4 , 1 .

, 1 5, 1, 4, 5, 26.

. 1. 23 2. 37 3. ...12

 

 

 

! , , , .
. , :