, , .
1) , .. .
2) , () .
3) , m , n A1,A2,...,An.
, ( ) , .. Ai (i=1,2,..., m), A1x1+A2x2++Anxn = B xi, .
. . , , .
, , , .. , '''' (, , '' ''), , ( , - ).
. . ABCDEGH. , . 7 , . , , - , .. .
, , .. , , . , . ''" (. simplex - ) - n- n+1 (, 3- ).
, , , ( , ) , , - , ( ).
|
|
- - :
- ;
, ;
, .
-
.
L=0+ max
xj ³ 0 (j=1,2,,n), bi ³ 0 (i=1,2,m; m£n).
1. , - m , , , - .
, , , , , , , , , - x1,x2,...,xm, .. :
(1)
x1 ³ 0, x2 ³ 0,..., xn ³ 0. (2)
(3),
bi ³ 0, (i=1,2,...,m).
x1,x2,...,xm, (3), , {x1,x2,...,xm} - ; . .. .
2. L xm+1,..., xn, L (3), . :
L=C0 + C¢m+1xm+1 +... + C¢nxn. (4)
.. i (i=1,2,,n) , - , . : xm+1 = 0,..., xn = 0
(3) :
x1 = b1, x2 = b2,..., xm = bm.
( ) , x1,x2,...,xm:
X = (b1, b2,..., bm,0,..., 0).
(2) , .. , , , . . . . .
L (4) . .. xm+1 = 0,..., xn = 0, L = C0.
, , .. L, - xm+1,..., xn ( , .. , ). , , , 0 .
, C¢m+1,...,C¢n (4) , , - xm+1,..., xn , L; , X=(b1,b2,..., bm,0,...,0) .
|
|
3. , , .. C¢m+1,..., C¢n , xm+1,..., xn, , , .. L.
, . , , C¢m+1 (4) xm+1. xm+1, .. , xm+1 ¹ 0, - . , .
xm+1 , x1,x2,...,xm, , xm+1 (3). , ( m+2=0, m+3=0,, n=0, ):
(5)
m+1, . m+1 , .
, ( ) , . , xm+2=0,...,xn=0, x m+1 , b¢i/ a¢i,m+1(i=1,2,,m), xm+1 xj .
.
, , (.. ), . .
, xi (i=1,2,,m). . : xm+1 , bi - , aim+1 xm+1. xi = a¢i,m+1xm+1 + +a¢i,nxn + b¢i xm+1 .
, , .
1) xm+1=|b¢i/a¢im+1|, b¢i a¢im+1 b¢I ¹ 0 a¢im+1 ¹ 0.
xm+1 , b¢i/ a¢i m+1, xm+1 xj .
: x3 = 8-2x2 +...; x2 = 8/2=4 x3 = -8+2x2 +...; x2 =8/2=4.
2) xm+1=, b¢i a¢i m+1 0.
: x3 = 8+2x2 +...; x2 = .
3) xm+1=0, b¢i =0 a¢i m+1<0.
: x3 = 0-2x2 +...; x2 = 0.
4) xm+1=, b¢i =0 a¢i m+1>0.
: x3 = 0+2x2 +...; x2 = .
5) xm+1=, a¢i m+1=0.
: x3 = 5+0x2 +...; x2 = x3 = -5+0x2 +...; x2 = .
(5) xm+1=, max L = ¥ - .
, ( ) , . x1,x2,...,xm, xm+1, .. , b¢i/ a¢i,m+1 .
(i=1,2,,m) ; , k£m. . ., = min i. ak,m+1 . r= . i, k . ,r ³ 0. , xm+1 r ( , xi < 0). xk. (3) , xm+1 xk.
|
|
.., - , .
4. , xm+1 xk. x1,x2,...,xk-1,xk+1,...,xm,xm+1; xk,xm+2,..., xn.
, xm+1,..., xn; , xk, xm+2 ,..., xn.
(3) (4) .
, . , xk, xm+1 ( , aim+1 ¹ 0) xm+1 .
xk ( ) (3) xm+1 ( ):
xm+1 = - ( xk + xm+2 +... + xn)
xm+1 . :
(6)
xk =0, xm+2 = 0,..., xn = 0, (7)
: (8).
¢ x1,..., xk-1, xk+1,..., xm, xm+1; ( ) (7), (8). , .
, (6) L ( L ):
L¢ = C0 - (Ckxk +Cm+1xm+1 +... + Cnxn) ³ L. (9)
.
5. 3 ( ).
. , , .. Ck, Cm+1,..., Cn (9) , : , . (7), (8) , .
, : , , , L .
: , .
Z :
1) F, F= -Z , Zmin=-Fmax;
2) : , .
: , .
|
|
, ( ) . , ( ) () . -. , -.
. . , . , - .