.
( ) .
- :
m n . i i, j () j ( ). ij, i j.
, (.. ) , . , (=åjj) (=åii). .
? :
, .. ij ( m´n), ij , i- j- . , (ij) . , , , .. ij.
= i (i=1,2,,m), (2.3.1)
= j (j=1,2,n). (2.3.2)
(2.3.1) , (2.3.2) . ,
F = à min (2.3.3)
: (2.3.1), (2.3.2) ( ) =( 11, 12,, ij,, mn), (2.3.3) . .
2.3.1
- i | - i | j j | |||
n | |||||
1 | 2 | n | |||
1 | 11 11 | 12 12 | 1n 1n | ||
2 | 21 21 | 22 22 | 2n 2n | ||
m | m | m1 m1 | m2 m2 | mn mn |
(i,j) (i , j ) ij, ij( ). =( 11, 12,, ij,, mn) (2.3.1) (2.3.2) .
|
|
. m n , , . i- j- cij . x ij :
x ij=
1.
i =1 (i=1,2,,m), j =1 (j=1,2,n).
, , , . , , , . , , , . , e , . "" , , , . , . , .. , .
, ( , ..).
, , (MarriageProblem), cij " " . , , , . " " ( ) .
(. 2.3.2).
:
11 =2, 12 =1, 13 =5, 21 =3, 22 =4, 23 =3, 31 =4, 32 =6, 33=6;
1 =50, 2 =60, 3 =70, 1 =40, 2 =85, 3=55.
2.3.2
2 11 | 1 12 | 5 13 | |
3 21 | 4 22 | 23 | |
4 31 | 32 | 6 33 |
.
, , ..
|
|
11 + 12 + 13 =50
21 + 22 + 23 = 60 (2.3.4)
31 + 32 + 33= 70
, , :
11 + 21 + 31 = 40
12 + 22 + 32 = 85 (2.3.5)
13 + 23 + 33= 55
F ( ) :
F = 2 11 + 12 + 5 13 + 3 21 +4 22 + 3 23 +4 31 + 6 32 + 6 33.
, (2.3.4)(2.3.5) ( ). :
2.3.3
2 | 1 | 5 | |
3 | 4 | ||
4 | 15 | 6 |
:
F = 2´40 +1´10 + 5´0 + 3´0 +4´60 + 3´0+4´0 + 6´15 + 6´55=750.
3600 , . , .
:
2.3.4
2 | 1 | 5 | |
3 | 4 | ||
4 | 35 | 6 |
:
F = 1´50 + 3´40 +3´20 + 6´35 + 6´35=650.
, .. , .
.
, . , , - , , , , .
- :
1. - (1,1), :
11 =miní1,1ý.
2. (1,2), (2,1), .
3. - - .
, (. . 2.3.3) :
(1,1) :
11 =miní50,40ý=40.
1- , . (1,2) . , 1- 40 50 40 = 10 , 12 =miní10,85ý=10. 1- . - .. (. . 2.3.3).
m+n1=3+31 = 5. . , ( ) , , .
, , .. m+n1. ( ) , (.. , ) m+n1.
- , . , : - , . , , , , - . . , , . 2.3.4.
|
|