, , . . .
( , ), .
.
, i j :
, . - , .
, , .
. . , .
. , - . . 0 (. . ).
:
,
; ; ; ; ; .
P1, P2, P3, P4, P5, (P3 P4), .. . . . Ÿ . . , : .
I :
- | ||||||||||||||
-1 | ||||||||||||||
- | -1 | |||||||||||||
F0 | -2 | -3 | ||||||||||||
-3 | -2 | -1 | ||||||||||||
, zj Pj (j=1,m) =(1, 2,...,m):
.
, , .
|
|
F0 P0 : F0 = 1*0+8*0+3*(-) = -3.
F0 . , , 4- , , 5-.
, 5- . . P1 P2. P1, . , , aij>0. P1 (, ). i= 3. 6. , .
=2: 1) 2 ; 2) , 3- , ; 3) 3- -2 , .
II :
- | |||||||||||||
5/2 | 5/2 | -1/2 | 1/2 | ||||||||||
-1 | |||||||||||||
3/2 | 1/2 | -1/2 | 1/2 | ||||||||||
-2 | -1 | ||||||||||||
, . , . , .
F0 = 3.
4- . , , . , . III .
- | |||||||||||||||||
2/5 | -1/5 | 1/5 | |||||||||||||||
-1 | |||||||||||||||||
-1/5 | -2/5 | 2/5 | |||||||||||||||
4/5 | -7/5 | 7/5 | |||||||||||||||
. , .
- | |||||||||||||||||
2/5 | 1/5 | ||||||||||||||||
-1 | |||||||||||||||||
-1/5 | 2/5 | ||||||||||||||||
4/5 | 7/5 | ||||||||||||||||
|
|
4- . . .
.
-1, ≤. 1:
, .. : .
, : .
, , .
: . - . .
:
.
, . , , .
, - , . :
, , .
, . , , , .
, , :
,
, .
. , , . . ( ):
: , ;
m 1, 2,..., m 1, 2,..,.m n 1, 2,..., n , b1, b2..., bn .
() i - j - - ij (i=1,m; j=1,n).
, .
:
1) :
.
2) :
.
3) :
.
, .
. , , . . .
(n + 1)- .
(m + 1)- . , .
|
|
:
1. ( - , ). m+n-1.
- , , .
(- ). , , . , , , ( ), .
, , . , , . , , , - . , . , . , , , , .
2. , , .
. . 100, 90, 170 30 . , 200, 160, 140 .
.
, ?
, 100+90+170+30=390 200+160+140=500. 5- .
, - .
(1,1). 11 = min(a1=200,b1=100)=b1=100 1 1, . A1 a1=200-100=100 . (1,2): 12 = min(a1,b2)=b2=90 . 2. 1 a1=100-90=10 . - (1,3). 13 = min(a1,b3)=a1=10 B3 . (1,3) A1. B3 b3=170-10=160. 23 = min(a2,b3)=a2=b3=160 A2 , B3 . . B3, (2,4) 24 =0 ( 2 ) 2. . .
|
|
b1=100 | b2=90 | b3=170 | b4=30 | b5=110 | ||
β1=12 | β2=15 | β3=21 | β4=16 | β 5=4 | ||
a1=200 | α1=0 | 12 100 | 15 90 | 21 10 | ||
a2=160 | α2=-6 | 15 160 | 10 0 | |||
a3=140 | α3=-4 | 12 30 | 0 110 |
7 m+n-1=3+5-1=7 . .
. , .
:
, , .
( .)
.
.
(1,4), (1,5), (2,2) , . "" . , , . . (1,5). .
- , , , , .
, .
"" :
1. , : " + ", - " - " " + ".
2. , , , ; .
: (1,5) , , (3,5), (3,4), (2,4), (2,3), (1,3) .
= min (10,0,110)=0. "" 0 . , "". :
b1=100 | b2=90 | b3=170 | b4=30 | b5=110 | ||
β1=12 | β2=15 | β3=21 | β4=12 | β 5=0 | ||
a1=200 | α1=0 | 12 100 | 15 90 | 21 10 | 0 0 | |
a2=160 | α2=-6 | 15 160 | ||||
a3=140 | α3=0 | 12 30 | 0 110 |
. (2,2) . .
= min (90,160)=90. "" 90 . , "". :
b1=100 | b2=90 | b3=170 | b4=30 | b5=110 | ||
β1=12 | β2=15 | β3=21 | β4=12 | β 5=0 | ||
a1=200 | α1=0 | 12 100 | 21 100 | 0 0 | ||
a2=160 | α2=-6 | 8 90 | 15 70 | |||
a3=140 | α3=0 | 12 30 | 0 110 |
. .
: ,
=100*12+100*21+90*8+70*15+30*12=5430.
, 110 . .