, . , , , , . . , , , .
, :
1) :
, . ( , ..).
; , , : (- ); ; .
2) :
, ( ; .. )
, ( ; , ..). , , , , .
, ( , ).
(), : , -, , , .
-.
, , .
(3.2), . , , , , ( , ) .
|
|
(3.2) m n , r = n - m (, x1, x2,..., xr), , m (, xr+1, xr+2,..., xn) . ( -). :
r+1 = a'r+1,1 x 1 + a'r+1,2 x 2 +... + a'r+1,p x p +... + a'r+1,r x r + b'r+1
x r+2 = a'r+2,1 x 1 + a'r+2,2 x 2 +... + a'r+2,p x p +... + a'r+2,r x r + b'r+2
....... (3.12)
x q = a'q,1 x 1 + a'q,2 x 2 +... + a'q,p x p +... + a'q,r x r + b'q
.......
x n = a'n,1 x 1 + a'n,2 x 2 +... + a'n,p x p +... + a' n,r x r + b'n
b'r+1≥ 0, b'r+2 ≥ 0,..., b'q ≥ 0, ..., b'n ≥ 0
(3.12) , ( ).
(3.1) (3.12),
= o + 1 x 1 + 2 x 2 +... + r x r (3.13)
, , ,
x 1 = x 2 =... = x r = 0, :
x r+1 = b'r+1, x r+2 = b'r+2,..., x n = b' n
(0,..., 0, b'r+1, b'r+2,..., b'n) . ( 3.2). = o. : = o ?
(3.13) (3.12). - ( ), ( ). (3.12), , , .
(3.12) (3.13) :
I. (3.13) . (3.12) ≥ . , = min , .
II. , (3.13) , (3.12) - . (3.12) : + ∞. . min = - ∞, , .
III. , (3.13) , (3.12) . , : , , . ( , , (3.3)).
|
|
. , , () (') , , , , , ' ≤ . , min.
min - () .
, 3- ( (3.13) , (3.12) ), , , , , x2, x 3,..., x r, x r+1, x1, x r+2, , x n, . (3.12).
= 'o + '2 x2 + '3 x3 +... + 'r xr + 'r+1 xr+1 (3.14)
, (3.14).
( I), = ' . (3.14) , ( II), ( III) . , , , , , 1- , , , 2- .
, , () .
3- , . , (3.13) (3.14) , . , (3.12) .
, , (3.12), , , , , bi/aip. , , min(bi/aip), , , .
, , . , , , (3.13) (3.14) , Ò. .
|
|
, max , min .
.
1. : , ?
: m m n (m<n) ( ), , , .
, () , . , : () ( ) m , m , , .
2. , , , , ( ).
, , .
3. , . , .
4. , , - . , .
.
********************
3.6. = x1 + x2 + x3 → min
7ּx1 + 2ּx2 + 9ּx3 ≥ 1
2ּx1 + 9ּx2 ≥ 1
9ּx1 + 11ּx3 ≥ 1
******************** ********************
( ). , , z1, z2, z3. :
7ּx1 + 2ּx2 + 9ּx3 - z1 = 1,
2ּx1 + 9ּx2 - z2 = 1, (3.6.1)
9ּx1 + 11x3 - z3 =1.
: = x1 + x2 + x3.
3 6- , 3 (, x1, x2, x3) . (z1, z2, z3) - . :
x1 = 1/20 - 99/80z1 + 11/40z2 + 81/80z3
x2 = 1/10 + 11/40z1 + 1/20z2 + 9/40z3 (3.6.2)
x3 = 1/20 + 81/80z1 - 9/40z2 - 59/80z3
:
|
|
= 1/5 + 1/20z1 + 1/10z2 + 1/2z3 (3.6.3)
, z1=z2=z3=0. 1 = (1/20; 1/10; 1/20; 0; 0; 0) ( ). 1 = 1/5.
(3.6.3) . , z1, z2, z3 , , . . , .
: min = 1/5 = (1/20; 1/10; 1/20; 0; 0; 0).
********************
3.7. = x2 + x3 → max
: x1 - x2 + x3 = 1,
x2 - 23 + 4 = 2.
******************** ********************
. - , 2. , , - .
1. : - x1, x4, - x2 3.
x1 = 1 + x2 - x3; (3.7.1)
x4 = 2 - x2 + 2x3;
x2 x3, , :
= x2 + x3 (3.7.2)
(2 = 3= 0). 1=1, 4= 2. 1=(1; 0; 0; 2), . 1= 0. ( max). , : (3.7.2) , , 3, (x2 ). 3 . x3 (3.7.1), , 3 1 ( 1≥0). x3 , 2- x3. , , : x1 , 3 - .
2. : - x3, x4; - x1 2.
3, x4 1, 2. : x3 = 1 - x1 + x2;
x4 = 4 - 2x1 + x2; (3.7.3)
= 2 + 1 - 1 + 2 = 1 - x1 + 2x2 (3.7.4)
(3.7.4), : 2. (3.7.3) 2 , (3.7.3), . , 2 , , 2 → + ∞, → + ∞. , max = + ∞. : , .
: m = + ∞. .
********************
3.8. = x1 + x2 + x3 → min
8x1 + 4x2 + x3 ≥ 1
2x1 + 5x2 + 7x3 ≥ 1 4x1 + 6x2 + 3x3 ≥ 1
******************** ********************
. . , z1, z2, z3. : 8x1 + 4x2 + x3 - z1 = 1
2x1 + 5x2 + 7x3 - z2 = 1 (3.8.2)
4x1 + 6x2 + 3x3 - z3 = 1
= x1 + x2 + x3.
3, 6, r = n-m = 3.
1. z1, z2, z3, - x1, x2, x3, . :
x1 = 10/136 + 27/136z1 + 6/136z2 - 23/136z3,
x2 = 12/136 - 22/136z1 - 20/136z2 + 54/136z3, (3.8.3)
x3 = 8/136 + 8/136z1 + 32/136z2 - 32/136z3,
x1, x2, x3 ,
= 30/136 + 13/136 z1 + 18/136 z2 - 1/136 z3 (3.8.4)
z1 = z2 = z3 = 0. 1 = (10/136; 12/136; 8/136; 0; 0; 0)- . 1 = 30/136.
(3.8.4) z3 , , . z3 . (3.8.3) (1- 3-), z3 , z3. . , z3 , x1 x3, z3, .
|
|
z3, . , z3 gr1 = 10/136:23/136 = 10/23 ≈ 0,5. - gr3 = 8/136:32/136 = 8/32 =0,25. , , . x3, .
2. x3 z3 , , x3 → , z3 → . : - x1, x2, z3 , - z1, z2, x3. . :
x1 = 1/32 + 5/32z1 - 4/32z2 + 23/32x3,
x2 = 6/32 - 2/32z1 + 8/32z2 - 54/32x3, (3.8.5)
z3 = 8/32 + 8/32z1 + z2 - 136/32x3,
:
= 7/32 + 3/32z1 + 4/32z2 +1/32x3 (3.8.6)
z1,z2, x3 2 = (1/32; 6/32; 0; 0; 0; 8/32). 2 = 7/32.
(3.8.6) , , ( z1, z2, x3 2). . , ; .
: min = 7/32 = (1/32; 6/32; 0; 0; 0; 8/32).
-
, , , , . , , .
, , .
(3.2), r = n - m (x1,..., xr) , m (xr+1, xr+2,..., xn) - . , , , (3.12) , ( , ) , - .
x r+1 a r+1,1 x1 - a r+1,2 x2 -.. - a r+1,p xp -.. - a r+1,r xr = b r+1
x r+2 a r+2,1 x1 - a r+2,2 x2 -.. - a r+2,p xp -.. - a r+2,r xr = b r+2
.......... (3.15)
x q a q,1 x1 - a q,2 x2 -.. - a q,p xp -.. - a q,r xr = b q
..........
x n a n,1 x1 - a n,2 x2 -.. - a n,p xp -.. - a n,r xr = b n
- :
- 1x1 2x2 -... - pxp -... - rxr = o (3.16)
( (3.15) ).
(3.12) (3.15) , , .
(3.15) (3.16) 3.1.
3.1.
- | - | ||||||||||
x1 | xp | xr | x r+1 | x q | x n | ||||||
x r+1 | b r+1 | -ar+1,1 | -ar+1,p | -ar+1,r | |||||||
x q | b q | -aq,1 | - a q,p | - a q,r | |||||||
x n | b n | -an,1 | - a n,p | - a n,r | |||||||
o | - 1 | - p | - r |
= (0; 0;...;0; b r+1; b r+2;...; b n), =
3.1 : , .
j () xj, , j ,- .
- , , (3.13) = o + 1∙x1 +... + j∙xj +... + r∙xr x1,..., xr. (3.16) 3.1 , , , , .
, , , (0;...; br+1,...; bq;...; bn) I ,
min = . .
, ( ) - p>0. , , . .
. , , aip ≥ 0 (i = r+1,n) II, , min = - ∞, .
, , , p, , , - aip > 0; , aip < 0, III, , . , (- aip) . .
, bi/aip q- , s - .
, , . .
, , xp xq ( 3.1 , p ≤ r; r+1≤q ≤ n), , q , p - .
-, -. , q- , , , 1/aqp. , q- xp.
, q- , xp xq. 3.1 , , - xp , . .
. ( I), , min = - ∞ ( II), ( III) . , , , I II.
. , , ( ) , = . .
, max , min - .
.
1. .
2. , , - .
3. , , p ( xp). xp ( ) . . , min = -∞ - .
4. , akp (k ≤ r) bk/akp, bk - ( ). . xq. ( ) . aqp, - .
5. . 1/aqp ( ) xp. , (-aip/aqp), , , (-aip), , , 0. .
6. 2.
.
1) - (), , 3.1 ;
2) "" ( ) , , , , , "" .
3) - ( bk/akp), , . , , , .
***************
3.9.
= 7x1 + 5x2 → max
: 2x1 + 3x2 + x3 = 19,
2x1 + x2 + x4 = 13,
3x2 + x5 = 15,
3x1 + x6 = 18.
******************** ********************
. 4 6 . , m=4 , r=n-m=2 .
1. 1 2. 3, 4, 5, 6 , , , -: x3 + 2x1 + 3x2 = 19,
x4 + 2x1 + x2 = 13,
x5 + 3x2 = 15,
x6 + 3x1 = 18.
= 7x1 + 5x2 , - 7x1 - 5x2 = 0.
(. 3.9.1).
1= (0; 0; 19; 13; 15; 18) , 1= 0.
3.9.1 : -7 5 1 2. , ( ). , , -5 2 ( ) () . : 3, 1, 3 3, 4, 5.
: , 19/3, 13/1, 15/3, - 15/3 - 5. , 5 . . 3, , ( ) . , 2 5 .
2. - 3, 4, 2, 6. 3.9.1 1/3, 1, 3.9.2 2.
, ( ), 2 , . 1 .
. 3.9.2. 2= (0; 5; 4; 8; 0; 18), 2= 25. 3.9.2 7 1 (). 3 , 2, 1 3, . , , 3.9.3.
3. 1, 4, 2, 6. 3.9.3 3= (2; 5; 0; 4; 0; 12), 3= 39. 11/6 5 ( ), 3 4, 2, 6. 4 , 2/3 , , , 3.9.4.
4. 1, 5, 2, 6. 4= (5; 3; 0; 0; 6; 3), 4= 50. 3.9.4 , , , .
: max = 50 = (5; 3; 0; 0; 6; 3).