=(ij) (i= 1,m j =1,n) , ij-
=(ij) (i= 1,m j =1,n)
ij (i= 1,m j =1,n)
:
X11+ X12+ X1n=a1
X21+ X22+ X2n=a2
Xm1+ Xm2+ Xmn=am
X11+ X12+ Xm1=b1
X21+ X22+ Xm2=b2
X1n+ X2n+ Xmn=bn
Xij≥0 i=1m j=1n
:
1.:
2.
3. :
:
=(ij) (i= 1,m j =1,n
4. -
5.
6.-
:
Z=∑ ∑ aijxij→min
:
X11+ X12+ X1n=a1
X21+ X22+ X2n=a2
Xm1+ Xm2+ Xmn=am
X11+ X12+ Xm1=b1
X21+ X22+ Xm2=b2
X1n+ X2n+ Xmn=bn
Xij≥0 i=1m j=1n
:
:
.
1.
2.
3.
.
(2) m+n mn → :
1,2 m+n mn (m+n+1)
,
:
1.
2.
3.
4. . 2 3 ,
5. m+n-1 . 0 (m+n-1)
17 . .
1.
2.
3.
|
|
4. ui + vj = cij, . m + n -1, m + n -1 m + n . . , , u 1=0, .
ui vj , .
5. D ij = ui + vj - cij.
6. .
D ij £0, .
, .
7. , , .
: 2 2 1- . . . 1 .
. 1- .
8 + .
9
l
.4-9
: . .
:
:
i bj
xij≥a
.. b xij≤b
i bj =∞
18
m n 1 1 1 1
.
/ | n | |||
11 11 | 12 12 | 1n 1n | ||
21 1 | 22 2 | 2n 2n | ||
m | m1 m1 | m2 m2 | mn mn |
:
1.:
2. .
3. : i j
Xij=0
Xij=1
|
|
= (Xij)-
4.
5.
6. -
Z=∑ ∑ aij Xij→max (min)
max-
min-
:
X11+ X12+ X1n=1
X21+ X22+ X2n=1
Xm1+ Xm2+ Xmn=1
X11+ X21+ Xm1=1
X12+ X22+ Xm2=1
X1n+ X2n+ Xmn=1
Xij{1,0]