. .
.
. .
.
,
(1)
ai , bj . xij i - j - , cij i - j - .
(1), . X , . :
b1 | b2 | bn | ||
a1 | c11 | c12 | c1n | |
x11 | x12 | x1n | ||
a2 | c21 | c22 | c2n | |
x21 | x22 | x2n | ||
am | m1 | m2 | mn | |
xm1 | xm2 | xmn |
xij. , xij, , , xij.
, (1) ,
(2)
, (2), , , (2) . (2) . , .
, (m+1) - , , (n+1) - .
> , ( ).
> , ( ).
. :
, :
, .
, (1) .
:
ai . , bj. i- j- cij. , . ( ).
|
|
|
:
:
20 + 30 + 60 t 30 + 25 + 40
, 15 (= 20 + 30 + 60 (30 + 25 + 40)).
12- .
x11 , 1- 1-
x12 , 1- 2-
..
x43 , 4- 1-
:
x11 + x21 + x31 + x41 = 20
x12 + x22 + x32 + x42 = 30
x13 + x23 + x33 + x43 = 60
:
x11 + x12 + x13 = 30
x21 + x22 + x23 = 25
x31 + x32 + x33 = 40
x41 + x42 + x43 = 15
:
xijt 0, i = 14 ( ), j = 13 ( )
( ):
= 7x11 + 10x12 + 2x13 + x21 + 8x22 + 5x23 + 3x31 + 2x32 + 9x33 à min
2. . U :
- . U1 . U1 . , , U1 .
, :
1) U ;
2) ( ) .
(1) . -. - , . -, .
.
, n+m-1 , .. . . , .
, .
. . , - , . .
|
|
. . -. , . .
) - . - . , :
(1) | |||||
(2) | |||||
(3) | |||||
(1) | (2) | (3) | (4) |
( ) , .
1. - ( , ). (1,1). 30 , 40 . 30 : x11=min {30,40} = 30. a1= 30 b1 =40 x11= 30. , :
0 | |||||
2. - . (2,1). x21=min {60,10} = 10 . a2 b1 :
0 | |||||
3. - (2,2). x22=min {50,50} = 50. : , . , , :
0 | ||||||
4 5, :
|
|
0 | ||||||
0 | ||||||
, :
30 | ||||
( ), . : , n+m -1 ( - 6). , , .. 5.
() . . , . - , . (. ). , , . .
(3,2), (2,3). (2,3). :
B) . - , - , . .
, . ( ).
1 (1) | |||||||
5 (5) | 1 (2) | 6 (6) | |||||
4 (4) | 1 (3) | ||||||
:
|
|
, ( 6). , - . .