. : (, , ..), - ; ; ij . , dij.
.. () ( ). ( + -), (. 7), . ij, dij (. 2-3). .
3.2.1 . , . , . . , . . : .. . .
, , n-1. , n-1. (. , ). , n-1 , . , . (. , 2.3).
3.2.2 . , , :
1 - . ( , ). v 1=100 (. .).
, , . , , . . , : v 7=100-30=70; v 6=70+35=105; v 5=105-40=65; v 4=65-30=35; v 3=35+25=60; v 2=60-20=40.
|
|
2 - . :
vj- ui £ cij; (1.8)
vj - ui = cij, xij (1.9)
(1.8) vj - ui - cij. 1.2 35.
3 - . , (1-2-3-4-5-6-7-1). (gmin=x56=15, ..).
1.2, , gmin. , gmin - . x56 . 1.
.
. , , . .
3.2.3 . . . . 2.5 1.4 15 6 . 5-1=4 : 1.2, 2.4,1.3 4.5. 2-5, , , . :
1 - . .
2 - . :
vj- ui £ cij, xij=0 (1.10)
vj - ui = cij, 0<xij<dij (1.11)
vj - ui ³ cij, xi=dij (1.12)
:
vj - ui = cij+dij, xi=dij
dij - . , , - . .
vj - ui - cij. +, - -. 1.4 3.4, 8 7.
|
|
3 - . . , . "+", .
x=min[xij, (dij - xij)]
.
"-", .
x=min[xij, (dij - xij)]
.
+8 1.4. 1-4-2-1. x24=7, d14 - x14=6-0=6, :
x=min(7, 6)=6.
1.
.
.
.1. .
1. =3395.
1.2 , 5.6 .
2. =2870.
7.3 , 2.3 .
3. =2835.
.1. .
1. =318.
1.4 x14=6.
2. =270.
, 2.4 x24=1. .
3.4 , 2.4 .
3. =263.
2.5 , 1.2 .
4. =263.