Решение транспортной задачи
: .
: .1. .
,
. ,
. ,
,
, ,
.
.
1
,
j1 J2 Ji Jn
R1 C1.1 C1.2 C1.j C1.n B1
R2 C2.1 C2.2 C2.j C2.n B2
Ri Ci.1 Ci.2 Ci.j Ci.n Bi
Rm Cm.1 Cm.2 Cm.j Cm.n Bm
A1 A2
Ai ... An
,
1. i,j ,
, ,
Ri Jj. _i,j
. , ,
,
.
(
) ,
( ).
. , ,
, .
( ), i,j I,
Jj, Xi,j,. i,j,
.
( ) ,
,
, .
,
.
,
.
, ,
.
, ,
.
.
,
.
,
, , ,
(Bi), (i) (i,j)
.
(bi (i=l...m)
(ai(j=l...n), ()
: (j ( (bi,
().
,
.
,
.
, .
.
2. .
: m
1, 2, ..., Am. B -
a1, 2, ..., m .
n B1, 2, , n
b1, b2, ..., bn . i,j
Ai
Bj. i,j,
. (,
), ,
.
, ..
.
3. .
, X={xi,j}m.n
,
m+n U1, U2, ..., Um; V1, V2, ..., Vn,
Vj-Ui<=Cij (i=1,m; j=1,n) (1), Xij>0
Vj-Ui=Cij (2).
Ui, Vi ,
(1) (2) .
.
,
.
.
:
;
m+n U1 ,U2, ..., Um; V1,
V2, , Vn , Vj-Ui=Cij
;
.
e , .. ,
.
, .
:
, .. X'
, X;
X' U'i, V'j
;
U'i, V'j .
.
4. .
,
:
(ai=(bj ( i=1, .., m; j=1, ...,n) (3)
, ,
.
, (3) .
.
2- :
1. ,
(ai>(bj (i=1, ...,m; j=1, ...,n);
2.
(ai<(bj ( i=1, ...., m; j=1, ...,n);
"
", " ".
:
.
1 A2, ..., Am a1, 2, ..., m,
B1, 2, ..., n b1, b2, ..., bn,
( ai> ( bj, ( i=1, m ; j=1, n).
(X),
, .
-
-, .
Xi,j ( ai (i=1 , m ).
Xi,j = bi (j=1 , n ).
M ,
.
, , -. ,
,
. ,
n B1, 2, ..., n, ,
, n+1 ,
Bn+1 = ( i, - ( bj, ( i=1, , m ; j=l, ..., n),
bn+1 .
n+1 bn+1
.
.
, Am+1 am+1
.
5. .
.
. , "-
", ,
.
"- ".
( cepo-
). . B1
18 . 48,
A1 , 18 (1,1).
B1 , A1 30
. 2, (27 ),
27 (1,2);
3 1 3.
3 39 . 30
2, , 9
. 18 12 4; 6
5, 20 4
. ;
.
, ,
. ,
, .
:
, ,
i,j.
,
i, j,
, .
,
j.
"- ".
.
,
Bi j, Cj.i. ,
,
. ,
, . m + n - 1.
, ,
m + n - 1.
.
.
"- " i.j,
,
.
6.
:
.. . .:
, 1986
.. -
. .: , 1982
.., .., . .
. .: , 1980