: [ 3, 5, 6, 7, 8, 11]
7.
:
,
, . , .
.
, m A1,A2,...,Am a1, a2,..., am , n B1, B2,..., Bn b1, b2,..., bn . cij i- j- , (): .
, , .
.. - , .
: xij - , i- Ai j- Bj (i=1,..., m; j=1,...,n), . xij ³ 0, - m×n. = .
i- j- xij , ijxij. , .. (i=1,...,m; j=1,...,n), .. . , .. xij, cij, :
L= =min, (1)
:
1. , , , .. . m -:
(2)
2. , , , , .. . n -:
(3)
-. : () X=(x11,x12,,xij, ,xmn), (1) .
|
|
, (4)
, .. , , . , .
:
) ;
) .
.
.
(), , n B1, B2,..., Bn n+1 (B), . B : ci = 0 (i=1,...,m)., .. . .., - xi Ai B , Ai xi . . b .
(), , m+1 (A), . A : cj=0(j=1,...,n). .. - xj , , A.
, , , .. .
. , . .
, .
B1 | B2 | ... | Bn | ai | |
A1 | c11 x11 | c12 x12 | ... | c1n x1n | a1 |
A2 | c21 x21 | c22 x22 | ... | c2n x2n | a2 |
... | ... | ... | ... | ... | ... |
Am | cm1 xm1 | cm2 xm2 | ... | cmn xmn | am |
bj | b1 | b2 | ... | bn |
n , ,
n , ,
n
n xij, i- j- .
(i,j) , i- j- .
. , :
B1 | B2 | Bn | ai | |
A1 | ||||
A2 | ||||
bj |
( ) =
|
|
= .
: Z(X)= 9x11+5x12+3x13+4x21+6x22+8x23. .
. , 1- , 1- , 2- - 2- :
x11+x12+x13=90,
x21+x22+x23=110. , .
, , :
x11+x21=50,
x12+x22=70,
x13+x23=80. , .
: xij>=0, i=1,2,..,m; j=1,2,...,n.
: , Z(X)= 9x11+5x12+3x13+4x21+6x22+8x23
x11+x12+x13=90,
x21+x22+x23=110,
x11+x21=50,
x12+x22=70,
x13+x23=80,
xij>=0, i=1,2,..,m; j=1,2,...,n.
.
. , , ..
,
.
. , .
=>0. xij=aibj/M (i=1,2,,m; j=1,2,,n) , .. (2) (3). , xij (2) (3),
ij ђ=max Cij L= '; , (2), £C =C =CM.
ij ђ=minCij L= '; , (2), ³C =C =CM.
,
CM£L£CM,
.. .¨
, , . , .
(xij) (i=1,...,m; j=1,...,n), (2), (3) ( ): , ().
, .. (xij) , .
.1. , , , , .. r=m+n-1 xij, .
m+n , , mn . m+n . , (2) i=1,2,,m (3) j=1,2,,n, . .
2- . , m+n-1 .
, m+n-1 (), .
, - , (i=1,2,,m; j=1,2,,n) m+n-1, .
|
|
.2. m+n-1 , .
, , , () - . , m+n-1.
, , , .
, , .
(i1,j1),(i1,j2),(i2,j2),...,(ik,j1), , , . - , , , 90, , . , . , , .
, . , = (i=1,2,,m; j=1,2,,n) , , .
, , - , , .. m+n-1, , , , .
:
1. , - , .. . , , , , , .
2. , , , , . , , , .
:
1. - - . , , .
. , , .
- , .
|
|