. Z=18y1+16y2+5y3+21y4min :
. y5, y6 -, .. ³:
:
(3) 1y1 + 2y2 + 3y3 + 4y4 - A5 y5- A6 y6 =A0,
y3, y4, .. , 1- 3 y4, 3, 4:
, ( ).
1 . : y3, y4.
: y1, y2, y5, y6.
:
Y1=(0;0;3;2/3;0;0) . :
Z=18y1+16y2+5y3+21y4=18y1+16y2+5(3-3y1- y2+ y6)+21(2/3-1/3y1- 2/3y2+ 1/3y5)=29-4y1- 3y2+ 7y5+ 5y6.
Z1=Z(Y1)=29 , .. Z y1, y2, Z . .. y1 , . y1 ( y2, y5, y6 0 ).
: y1=min{3/3;2/1}=1, .. , y3 .
2 . : y1, y4.
: y2, y3, y5, y6.
, y4 y1 :
Z=25 5/3y2+4/3y3+ 7y5+ 11/3y6.
Y2=(1;0;0;1/3;0;0) Z2=Z(Y2)=29 , .. Z y2, Z . y2 ( y3, y5, y6 0 ).
: y2=min{3;3/5}=3/5, .. 2- , y4 .
3 . : y1, y2.
: y3, y4, y5, y6.
, y1 y2 :
Z=24+y3+3y4+ 6y5+ 4y6. Y3=(4/5;3/5;0;0;0;0) , .. Z . Zmin=Z(Y3)=24.
, .
.
Z=0+ max
xj ³ 0 (j=1,2,,n), bi ³ 0 (i=1,2,m; m£n).
1. , (1)-(2). , , (-1). , .
|
|
(1)
: Z-C1x1 - C2x2 -×××-Cnxn=C0. (2)
x1 ³ 0, x2 ³ 0,..., xn ³ 0. , bi ³ 0, i=1,2,,m.
2. .
:
) X£A0 0³0, , .. .
) , , , , .
) , , , .
, : n- Ai (1£i£m£n) . xi, , .
:
( ) m , m , , .
, , , , , , - x1,x2,...,xm, .. :
(3)
x1 ³ 0, x2 ³ 0,..., xn ³ 0. , bi ³ 0, i=1,2,,m.
x1,x2,...,xm, , , {x1,x2,...,xm} - ; .
Z xm+1,..., xn, Z (3), :
Z =C0 + Cm+1xm+1 +... + Cnxn. (4)
.
. | |||||||||
0 | x1 | x2 | xm | xm+1 | xn | ||||
x1 | b1 | a1,m+1 | a1n | ||||||
xk | bk | ak,m+1 | a1n | ||||||
xm | bm | am,m+1 | amn | ||||||
Z | C0 | -Cm+1 | -Cn |
, , . : Z-Cm+1x m+1 C m+2x m+2 -×××-Cnxn=C0.
|
|
1- (), 1- ( ), 2- b1, b2,,bm. , . ij .
.. i (i=1,2,,n) , - , . : xm+1 = 0,..., xn = 0
(3) :
x1 = b1, x2 = b2,..., xm = bm.
( ) , x1,x2,...,xm:
X1 = (b1, b2,..., bm,0,..., 0).
, .. , , , . . . . .
Z (4) . .. xm+1 = 0,..., xn = 0, Z1 = C0.
, , .. Z, - xm+1,..., xn ( , .. , ). , , , 0 .
C¢m+1,...,C¢n ( - , .. ), , - xm+1,..., xn , L; , X=(b1,b2,..., bm,0,...,0) .
3. .
: , .
: , .
.., , , max (min) Z=c0 ( ), bi ( ), 0, .. .
4. , .. Cm+1,..., Cn , xm+1,..., xn, , , .. Z.
, . .., Ci<0 ( max) Ci>0 ( min) .
, , Cm+1 (4) xm+1, .. m+1 . xm+1, .. , xm+1 ¹ 0, 0 - . , .
xm+1 , x1,x2,...,xm, . , , , .
|
|
m+1, . m+1 , .
. . :
1), bi ai,m+1 ;
2) , bi =0 ai,m+1 <0;
3) , ai,m+1 =0;
4) 0, bi =0 ai,m+1 >0;
5) , bi ai,m+1 .
, ( ) , . x1,x2,...,xm, xm+1, .. , .
. , (Zmax = Zmin =-). , k, (, ), .
, , 1, ak,m+1.
5. x1,...,xk-1,xk,xk+1,...,xm x1,..., xk-1,xk+1,...,xm+1, x xm+1.
.. - , .
:
) : x - xm+1;
) ak,m+1 , ak,m+1 . ;
) , ai,m+1 (i=1,2,,k-1,k+1,,m) , m+1, .. x1,..., xk-1,xk+1,...,xm, (,m+1), 0. xm+1 . -, (i=1,2,,k-1,k+1,,m; j=1,2,,m,m+2,,n) : (1)-
] ]
- - - - - - - - - - -
- - - - - - - - - - -
] ]
.
. | ||||||||||
0 | x1 | x2 | xk | xm+1 | xn | |||||
x1 | b1 | a1,k | a1n | |||||||
x2 | b2 | a2k | a2n | |||||||
xm+1 | bk | ak,k | akn | |||||||
xm | bm | am,k | amn | |||||||
Z | C0 | -Ck | -Cn |
II, . , xm+1,..., xn; , xk, xm+2 ,..., xn.
3 ( ).
, I aij, II . : I, II, III,... - , ( Z max min). , max (min) Z = ¥ ( ). .
|
|
1. Z=2x1+3x2max
(1) x1³0, x2³0.
:
Z-2x1-3x2=0.
1, x3, x4, x5, x6 . (..2 ).
. | ||||||||
0 | x1 | X2 | 3 | x4 | x5 | x6 | ||
3 | 18/3 | |||||||
4 | ||||||||
X5 | ||||||||
6 | ||||||||
Z | -2 | -3 |
.3 . ; (-3), 2- , 2 ( ). .4 2=min{18/3;16;5;}=5. ( ). , x5 x2.
C 2 .5 .
) x3, x4, x2, x6 ( x5 x2).
) , 1 32=1, , . 1.
) , , x2 , . :
..
2 .
2.
. | ||||||||
0 | x1 | x2 | 3 | x4 | x5 | x6 | ||
3 | -3 | |||||||
4 | -1 | 11/2 | ||||||
x2 | ||||||||
6 | ||||||||
Z | -2 |
. 1- , 1 , 1=min{3/1;11/2;;7}=3. 1- , 11=1 x1 x1. - 3.
3.
. | ||||||||
0 | x1 | x2 | 3 | x4 | x5 | x6 | ||
1 | -3 | |||||||
4 | -2 | 5/5 | ||||||
x2 | 5/1 | |||||||
6 | -3 | 12/9 | ||||||
Z | -3 |
. 5- , 5 , 4=min{;5/5;5/1;12/9;}=1. 2- , 25=5 . 4.
4.
. | ||||||||
0 | x1 | x2 | 3 | x4 | x5 | x6 | ||
1 | -1/5 | 3/5 | ||||||
5 | -2/5 | 1/5 | ||||||
x2 | 2/5 | -1/5 | ||||||
6 | 3/5 | -9/5 | ||||||
Z | 4/5 | 3/5 |
. Zmax=24, x1=6, x2=4, x3=0, x4=0, x5=1; x6=3.