, m , , , , . , X£A0 0³0, . , , , .
L=1x1+2x2++nxn
.
xj ³ 0 j=1,2,..,n; bi ³ 0, i=1,2,,m, .
y1,y2,...,ym +1, . , +. (>>1). (y1++ym) -.
, =L+(y1++ym)=1x1+2x2++nxn+y1++ym :
(1)
n+1,,An+m, , :
(2)
yi (2).
, (1) (2) y1=0, y2=0,...,ym=0.
.
.
1. =(x*1,x*2,,x*n,0,0) yi=0 (i=1,2,,m), *=(x*1,x*2,,x*n) .
2. , , yi>0, (.. ).
3. max=, , L max=, .
. , .
, - , * - , ()=L(X*). , * m , .
, * - . , , * . =(x1,x2,,xn), L(X)<L(X*). =(x1,x2,,xn,0,0), ,
()= L(X)<L(X*)= (),
..
|
|
() < (),
, - .¨
, -. 0 yi=0, , . (- )-.
, :
1. , , ( ), + ( ), , . (m+1)- , , (m+2)- - . , (- )-. , -.
2. , , .
3. , , , (m+1)- .
. L=x1+2x2 max
1- 2- (-1),
,
, , , , x4 x5 2- 3- , , . . , 1- y1:
:
= x1+2x2-y1=x1+2x2-(x1-x2+3)max
1=(0;0;0;3;3;1).
1- .
. | ||||||||
0 | x1 | X2 | 3 | x4 | x5 | Y1 | ||
Y1 | -1 | -1 | ||||||
4 | -1 | |||||||
x5 | ||||||||
L | -1 | -2 | Max | |||||
M | -1 | Max |
(m+1)- , , (m+2)- - . (-)-, , 2- , , 2 . 1- , . y1 , 0 . 2.
2.
. | |||||||
0 | x1 | x2 | 3 | x4 | x5 | ||
2 | -1 | -1 | |||||
4 | |||||||
5 | |||||||
L | -3 | -2 | Max | ||||
-M | Max |
, ;
|
|
max(-)=0, . 2= (0; 1; 0; 2; 3;0), .
3.
. | |||||||
0 | x1 | x2 | 3 | x4 | X5 | ||
2 | -1 | ||||||
4 | 2 | 2/1 | |||||
1 | -1 | ||||||
L | -2 |
3= (3; 4; 0; 2; 3)
4.
. | |||||||
0 | x1 | x2 | 3 | x4 | x5 | ||
2 | |||||||
3 | |||||||
1 | |||||||
L |
4= (3; 6; 2; 0; 0), , .. . , . X*=(3;6) Lmax=15.
1. .
2. .
3. .
4. .
: [ 1, 5, 6, 7]