1. , . ,
F=c1x1+c2x2++CnXn (19)
A11x1+a12x2++A1nXn≤b1,
A21x1+a22x2++A2nXn≤b2,
.
Ar1X1+Ar2X2++ArnXn≤br,
Ar+11X1+Ar+12X2+Ar+1nXn=br+1, (20)
.
Am1x1+am2x2++mnXn=bm,
Xj≥0 (J=1,l≤n). (21)
1.14. ,
F*=b1y1+b2y2+bmyYm (4)
A11y11+a21y2++am1ym≥c1,
A12y1+a22y2++am2ym≥c2
.. (22)
A1nY1+a2ny2++AmnYm=Cm,
Yj≥0 (l=1,r,r≤m), (23)
19-20 21-22 , .
:
1. 19-20 , 22-23 .
2.
(24)
(20) 19-20,
(25)
22-24
3. (22-24) (2) (19)-(21), (23) ---- .
4. (22) (22)-(24) (20) (19)-(21), (23) --- (19) .
5. Xj (19)-(20) J-e (23) (22)-(24) ≥. Xj , j-e (23) . (2) (19)-(21) (22)-(24). j-e (20) , l- yl , .
Vj Ui | V1=30 | V2=8 | V3=11 | V4=12 | V5=26 | |
U1=0 | 30 6 | 24 8 | 11 15 | 12 0 | 25 26 | |
U2=4 | 26 4 | 4 15 | 29 7 | 20 8 | 24 20 | |
U2=2 | 27 28 | 14 6 | 14 9 | 10 15 | 18 24 | |
U2=24 | 6 5 | 14 16 | 28 13 | 8 -12 | 2 20 |
|
|
F=6*30+15*11+4*26+15*4+15*10+5*6+20*2=729
Vj Ui | V1=12 | V2=12 | V3=11 | V4=12 | V5=20 | |
U1=0 | 30 12 | 24 12 | 11 15 | 12 6 | 25 20 | |
U2=8 | 26 4 | 4 15 | 29 3 | 20 4 | 24 12 | |
U2=2 | 27 10 | 14 10 | 14 9 | 10 9 | 18 6 | |
U2=6 | 6 11 | 14 6 | 28 5 | 8 6 | 2 14 |
F=15*11+6*12+4*26+15*4+9*10+6*18+11*6+14*2=693 ()
A1 |
B3 |
B4 |
A2 |
B1 |
B2 |
A3 |
B5 |
B4 |
A4 |
B5 |
B1 |
. , . , - . ( ) - (, , ). , .
. , , . " ", , , . , , . : , . , , . , .
: .
G = (V, ) , , , , - . . , . ; , , ( , , ). , , . . , , . - , . , , : - , - . ,
|
|
1 () () .
- , . N (N2 - N)/2. . , - , , N2 - N.
(VS, ES) (V, E) , .
- , . , A B A , B. , vi vj vivi+1, vi+1vi+2,..., vj-1vj. , , . - . AB, BC, CD, DE 4.
, . . ( ""). . . - , . , , P1 24, P2 - 36, P1 .
, . - , . . () . , , . .
( ) , ( ) .
, , (i=1,k-1) () .
, . ( ) . , u v , , (u,v,u) . , .
( ) , ; , . , :
, , , .
.
, ( ), (-), ( ).
|
|
.
, (, ), , . , / , . , , .
: , , .
( ), , ;
, ;
() , , , , . = 0.
: ( ) ().
;
, ;
, , . = 0.
, .
, , . :
, , ;
, ;
, , ;
i j , - i j, ;
, . (. )
. , .
, , . , , , .
.
, , () . . , , , , ( , , , . .) ( , . .). . , . , . , , , .
|
|
( ) , ( ) . , , , -. , . , , , . , . , .
. , , . . (Lm).
, .
. , , , :3tMIN + 2tMt =, 5 tMIN tM . :t2t = 0,04 * (tM - tMIN)2t2t > 1, , tM tMIN t tM t MIN.