1. .
2. .
3. , .
4. .
5. .
1. . . 17. // 7- . .: , 2007. . 629-697.
2. .. , , : . . 2‑ . .: -, 2005. 287 .
3. - : / . .. . 2‑ . .: -, 2005. 304 .
4. .., .. : , , : .. .: -, 2003. 444.
5. .., .. : . 2- ., . . .: , 2006. 368.
6. : , (060000) / . .. , .. , .. . .: -, 2005. 351 .
2.7.
2.7.1. 196
2.7.2. 199
2.7.3. 204
2.7.4. 214
2.7.5. 226
2.7.6. 227
2.7.7 235
.
(, , , ..) . , , , . , .
, . , (). , , , , , . , .
, . () , . , . - . , .
|
|
, .
.
, .
, , .
.
, n , m . , aij, i (i=1,2,, n), j (j=1,2,, m). :
a 11 a 12 a 1m
A = [ a ij ] = a 21 a 22 a 2m
..
a n1 a n2 a nm
, . , = .
() ( ), . .
, , . . ( ), , . , , .
.
, 2 4
. , = 1 3
miní2, 4ý= 4 1 2
. miní1, 3ý= 1, , , , miní1,2ý= 1. , , . mí4, 1, 1ý=1. , () .
. , mí2, 1, 1ý=1 . mí4, 3, 2ý=3. , miní1, 3ý=1. , () .
|
|
, , , .
:
1. "". "" "" . "" , , . , :
A= .
2. ", , ". , . , , . , . :
A= .
3. , ,
A= .
, -1, 1,
maxmin{aij}=max{-2,-2,2,-2}=2 minmax{aij}=min{4,2,3}=2,
.. . , 2, .
, , , ( ), . , . "", , "" . , . .
2 .7.2. .
miminj aij, , » minjmi a ij, , , mi minj aij £ minjmi aij. , , .. mi minj aij = minjmi aij = i0j0, (i0 j0 ) , , . i0j0 . , , i0j0, i0 j0.
, . , (). 1, 2,.., n q 1, q 2,.., q m , .
=1, i, qj ≥0 i j.
i,
a 11 1+ a 21 2++ a n1 n,
,
a 12 1+ a 22 2++ a n2 n,
, ..
|
|
a 1m 1+ a 2m 2++ a nm n
m- . , qj,
a 11 q 1+ a 12 q 2++ a 1m q m,
A , ..
a n1 q 1+ a n2 q 2++ a nm qm,
A n- .
( 1, 2,.., n) (q 1, q 2,.., q m), ( )
g= .
i , q j . ., , , ( 1*, 2*,.., n *) (q 1*, q 2*,.., qm *), ( g). , :
i ≥0,
1+ 2++ n =1,
a 11 1+ a 21 2++ a n1 n ≥ g,
a 12 1+ a 22 2++ a n2 n ≥g, (2.7.1)
.
a 1m 1+ a 2m 2++ a nm n ≥ g,
Z=g .
, (2.7.1) g > 0 i = i /g i. ( g ≤ 0 ). ,
max g =min 1/g = min( 1/g+ 2/g++ n /g) = min(x 1+ x 2++ x n)
Z= x 1+ x 2++ x n
a 11 x 1+ a 21 x 2++ a n1 x n ≥ 1,
a 12 x 1+ a 22 x 2++ a n2 x n ≥ 1, (2.7.2)
.
a 1m x 1+ a 2m x 2++ a nm x n≥ 1,
x 1, x 2,, x n ≥ 0.
(. 2.2).
: !
(, ), x 1*, x 2*,, x n*, , Z*= x 1*+ x 2*++ x n*, ( 1*, 2*,.., n *), i- i *= i */ Z*.
F = y 1+ y 2+ + y m→max;
a 11 y 1+ a 12 y 2+ + a 1m y m ≤1;
a 21 y 1+ a 22 y 2+ + a 2m y m ≤1; (7.2.3)
..
a n1 y 1+ a n2 y 2+ + an m y m ≤1;
y 1≥0; y 2≥0; y m ≥0.
.
, 1*, 2*,, m*, , F *= y 1*+ y 2*++ y m*, B (q 1*, q 2*,.., qm *), j- qj * = yj */ F *.
g =1/ Z* =1 /F*.
:
, ( 1*, 2*,.., m *) , .
( 0), ( 1*, 2*,.., m *) , .
- ( ), .
|
|
"" (), (). , , , . , , , , .
.
2.7.1. . 1:1, 3:1 4:1. :
1 1 1 ,
=1 3 1 ,
1 1 4 .
=1, :
2 0 0 (2.7.2) :
= 0 4 0 Z= x 1+ x 2+ x 3
0 0 5
2 x 1+ 0 x 2+0 x 3 ≥ 1,
0 x 1+ 4 x 2+0 x 3 ≥ 1,
0 x 1+ 0 x 2+5 x 3≥ 1,
x 1, x 2, x 3 ≥ 0.
, :
x 1*=1/2, x 2*=1/4, x 3* =1/5.
1/Z*=1/(x 1*+ x 2*+ x 3*)=20/19, ( =1) 20/19 1 = 1/19,
1*= 1*/Z*=10/19, 2*= 2*/Z*=5/19, 3*= 3*/Z*=4/19.
, 10:5:4, ( !) 1/19 , . ( , , , , ).
2.7.2. ( ) .
1. | |||
2. | |||
3. | 50 |
. , ? 1, 2, 3 . , , ( ).
Z= x 2+ x 3
0 x 2 + 150 x 3 ≥ 1,
100 x 2+50 x 3 ≥ 1,
250 x 2 50 x 3≥ 1,
x 1=0, x 2, x 3 ≥ 0.
(.2.2)
x 1*=0, x 2*=1/150, x 3* =1/150.
1/Z*=1/(x 1*+ x 2*+ x 3*)=150/2=75,
1*=0, 2*= 2*/Z*=75/150=1/2, 3*= 3*/Z*=75/150=1/2.
, , 75%.