, , , , (). , , . , . , , , . : , . , , ( (-1)). : - , . .
. .
, . , .
, ()
L = max (min)
(1)
x1 ³ 0, x2 ³ 0,..., xr ³ 0. k£m£n.
xj ³ 0 (j=1,2,,n), (1) , .. k=m () : () L= max (min) : , i=1, 2,...,m.
x1 ³ 0, x2 ³ 0,..., xn ³ 0,
: L=CX max (min) A1x1+A2x2++Anxn£ B, X³ 0,
=(C1,C2,...,Cn) - , =(x1,x2,,xn),
,
1= , 2= ,,n= , = - , .
.
aij m n; bi B=(b1,b2,...,bm), xi - X=(x1,x2,...,xn), - C=(C1,C2,...,Cn).
m , , AX. : A×X £ B.
|
|
C1x1+C2x2+××××+Cnxn CX.
, :
L=C X max (min) A×X £ B, X ³ 0.
, .
(1) , .. k=0 () :
() :
L= max (min)
, i=1, 2,...,m, x1 ³ 0, x2 ³ 0,..., xn ³ 0,
: L=CX max (min) A×X = B, X ³ 0.
: L=CX max (min) A1x1+A2x2++Anxn= B, X³ 0.
, . , (, ), .
, , . n
. (1)
. (2)
, n+1 :
. (3)
, , .
. =(b1,b2,,bn) (1) =(b1,b2,,bn, bn+1) (3) (2), , , (3) (2) (1).
. - (1), 1b1+a2b2++anbn £b.
bn+1, .. 0£b-(1b1+a2b2++anbn )= bn+1,
, =(b1,b2,,bn, bn+1) (3) (2). ,
1b1+a2b2++anbn + bn+1= 1b1+a2b2++anbn +[ b-(1b1+a2b2++anbn )]=b.
(3) (2), ..
1b1+a2b2++anbn + bn+1=b .
, bn+1, 1b1+a2b2++anbn £b.
, - (1).
¨
m xn+1, xn+2,..., xn+m, :
L = C1x1+C2x2+... + Cnxn +0×xn+1 + 0×xn+2 + ××× +0×xn+m max
:
x1 ³ 0, x2 ³ 0,..., xn, xn+1, xn+2,..., xn+m ³ 0.
, , , , , .. . , .
- :
|
|
ai1x1 + ai2x2 + ××× + ainxn = bi Û ai1x1 + ai2x2 + ××× + ainxn £ bi,
ai1x1 + ai2x2 + ××× + ainxn ³ bi.
xj , , , xj = uj - vj, uj, vj - , uj ³ 0, vj ³ 0. , .. .
, C1x1+C2x2+... + Cnxn, : -1x1-C2x2-... -Cnxn.
.
L=CX = C1x1+C2x2+... + Cnxn, ( ), .
X=(x1, x2,..., xn), , () .
, , - .
, , .
d=CX* .
X=(x1, x2,..., xn) , Ai (i=1,2,..., m), A1x1+A2x2++Anxn = B xi, .
Ai m-, , m.
, m , .
, () .
.
12 1(x1(1),x2(1)) 2(x1(2),x2(2)), . (x1, x2) , A1 A2. ,
=(x1-x1(1), x2-x2(1)) =(x1(2)-x1(1),x2(2)-x2(1)) , =t(), 0 £ t £ 1, x1-x1(1)=t(x1(2)-x1(1)), x2- x2(1)=t(x2(2)-x2(1)).
, ,
1-t = l1, t = l2,
.
, l1 ³ 0, l2³0 l1+l2=1, 0 £ t £ 1. 1 2, l1 l2. 1 2 :
=l11+l22;
l1³0, l2³0, l1+l2=1.
l1=1 l2=0 1, l1=0 l2=1 - 2. , t 0 1, .
1 2 () .
n 1, 2,n. - ,
=l11+l22++lnn; lj³0, (j=1,2,,n), l1+l2++ln=1.
, .
, , .
, , , , . .
|
|
, .
, .
, .
.
, , ; .
( ) , .
1. ( ) .
.
.
F - F1 F2 (. .). F A1, A2 . F1 F2, - ; F, F1 F2. , F - .¨
, , () ( , ). , , , , .
, , , , , .
, , , .
n- .
- , , , , , .
, , , .
.
2 ( ). n- .
.
, n . n=3, .. 123. , . 123 (. ).
2
4
1 3
. . , , .. =l11+l44; l1³0, l4³0, l1+l4=1. (*)
4 , , , .. 4=l22+l33; l2³0, l3³0, l2+l3=1. (**)
(**) (*),
=l11+l4(l22+l33)= l11+l2l42+l3l43.
l1= t1, l2l4=t2, l3l4=t3,
= t11+t22+t33, t1³0, t2³0, t3³0, t1+t2+t3=1,
.. - 1, 2, 3. , , t1=0, , 4 .
|
|
=0.1+t22+t33=t22+t33, t1=0,t2³0, t3³0, t2+t3=1. ¨