( ) ( )

( ) ( )

,,,,,,,,, :010-62782989 13501256678 13801310933,,,, ;,, (CIP) /. 3. :, 2005. 6 ISBN 7-302-10214-7... - -. O22 CIP ( 2004) 139321 : : http: / / www.tup.com.cn : 100084 : 010-62770175 : 010-62776969 : : : : 185260 : 30.5 : 721 : 2005 6 3 2005 6 1 : ISBN 7-302-10214-7/ F1041 : 10000 : 00. 00

(),,,,,,,,,,, : ;,,,,,,,,,,,, 1982,,1990,,,,

1980 11 (), :, 1982 2,,, 1990, : 14,,,,, :,,,,,,,,,,,,, 21 : ( ) ( ) ( ) ( ) 10 11 ( ) ( ) ( ) ( ) ( )

( ) 15 16 17,

1 1 2 2 3 3 4 3 5 4 6 6 7 1 8 1 8 2 16 3 20 4 28 5 32 6 38 44 2 47 1 47 2 48 3 51 4 53 5 60 6 61 7 63 8 * 70 73 3 78 1 78 2 79 3 89 4 91

97 4 101 1 101 2 103 3 104 4 106 5 108 111 113 5 114 1 114 2 115 3 118 4 0-1 122 5 126 131 132 6 * 133 1 133 2 146 3 151 7 * 171 1 171 2 175 3 177 4 180 187 190 8 191 1 191 2 193 3 201 4 203

211 9 213 1 213 2 224 3 * 233 4 * 236 5 238 6 241 7 * 244 245 250 10 251 1 251 2 255 3 261 4 268 5 274 6 276 281 284 11 286 1 286 2 290 3 294 4 295 5 298 300 12 301 1 301 2 306 3 313 4 322 5 M/ G/ 1 329 6 331 7 335

339 13 343 1 343 2 346 3 358 4 373 374 376 14 377 1 377 2 380 3 393 4 * 403 410 412 15 413 1 413 2 414 3 416 4 419 5 425 6 428 7 431 432 435 16 * 436 1 436 2 436 3 440 4 447 5 448 6 449 7 453

458 17 * 460 1 460 2 462 472 474

1 20 30,,,, ( operational research ) (1956, 1957 ),,,, 400% ;,, 47% 29 % ( RA ND),, 20 50,,, 20 60,,,,, ( ) ( ) 1914, ( Lanchester ) 1914 ( Erlang )1917, 20 20 20 30 ( G. B. Dantzig ) 1947, 1939 (.. ),,, 1960, ( 1932 ) ( Von N eumann) 1

( O. Morgen stern)(1944 ),, ( T. C. Koopmans ),,, ( Blacket t),,, ( 1948 ), ( 1952 ) ( 1956 ) (1957 )2005, 48 1980 1959 ( IFORS),, 1982, ( EU RO) 1975, ( APORS)1985 20 50,, (), 2, ( P. M. Morse) ( G. E. Kimball) :,,,,,,,,, :,,,,,,, :,, : (1 ), (2 ), 2

(3 ), (4 ),, (5 ),, (6 ), 3 (1 ),,, ; (2 ) ; (3 ) (, ), ; (4 ), ; (5 ) ; (6 ),, 4,, : ; ;,, : (1 ),,, (2 ),,, 3

(3 ),,, (4 ),, (5 ) ( )( scenario),,,,,,, : : xi ; yj ; k U = f( x i, yj, k ) g( xi, y j, k )0 ( ),, g,,,,,,,,,, 5,,, (1 ) 20 50, (2 ),,, 10%, (3 ),,, 18% 4

, 1971 5,, (4 ),,,, (5 ) (6 ), ;, ;, ; ;, ; (7 ) (8 ) (9 ),, (10),, ; 1957, 1958,,,,, 20 60 ; 1965 1970 20 70 20 70, 5

20 70, ; 6, 20 70,, ( S. Bonder ), :, 20 70,,,,,,,,, 20 70 20 80 :,,,,, 20 50 ( T. L. Saaty), 20 70 ( A H P ),,,, ( P. B. Checkland),,,,,,,, 20 70 20 80, 20 90 21, 1989, ( J. Rosenhead ), ( SSM : Checkland ) ( SAS T : Mason & Mitroff) ( SC: F riend)( PSM : Bryant & Rosenhead ) ( hypergame: Benett ) ( Metagame: Howard)( SODA : Eden ) ( VSM : Beer ) ( IP : Ackoff) ( CS H : Ulrich) 2001,,, 6

, ( GA : Holland) ( SA : Metropolis ) ( N N) ( FL : Zadeh) ( EC) ( TS ) ( ACO: Dorigo ) 2004 9, : Applied soft computing,, ; ( scale-free networ k),,, [1 ] Moder J J, Elmaghraby S E. Ha ndbook of Oper ations Resea rch. Founda tions and Fundamentals, Vol. 1; Models and Applica tion, Vol. 2. Von Nostrand Reinhold Company,1978 [2 ] Morse P M,Brown A A etc. Systems Analysis and Operations Research tool for policy and program planning for developing count ries, National Academy of Sciences, 1976 [3]. OR (1975) ; OR ( ) OR (1983 ). [4] H aley K B. Operational Research 78. North Holland Publish Company, 1979 [5] Brans J P. Operational Research 81. North Holland Publish Company, 1981 [6] Saaty T L. Mathematical Methods of Operations Research, McGraw Hill Book Company Inc. 1959 [7] Brans J P. Operational Research 84. North Holland Publish Company 1984 [8] Checkl and P B. Systems thinking, systems practice. Wiley, Chichester,1981 [9] Rosenhead J. Ming ers J. Ration al analysis for a problematic world r evisted. Problem st ruct uring methods for complexity, uncertainty and conflict. Wiley, Chichester,2001 [10 ],... :,1996 7

1947 ( G. B. Dantzig ),,, ( A. Charnes ) ( W. W. Cooper ), 1961, ( Y. Ijiri), ( S. M. Lee) ( V. Jaaskelainen ),, 1 1 1. 1,, 1, A B, 1-1 1-1 1 2 8 A 4 0 16 kg B 0 4 12 kg 2, 3,?, x1 x2 8,,,, : 8 x1 + 2 x2 8

, A B, 4 x1 16 4 x2 12, x1 x2 z, z = 2 x1 + 3 x2, : max z = 2 x1 + 3 x2 : x1 + 2 x2 8 4 x1 16 x1, x2 0 4 x2 12 2 ( 1-1), 500, 200 2, 1. 4 1-1, 20%, 0. 2% 1000 /, 800 /,, x1 x2,,, 0. 2%, (2 - x1 )/ 5002/ 1000, 0. 2%, [0. 8 (2 - x1 ) + ( 1. 4 - x2 ) ]/ 7002/ 1000, x1 2; x2 1. 4, z = 1000 x1, : min z = 1000 x1 + 800 x2 x1 1 0. 8 x1 + x2 1. 6 x1 2 x2 1. 4 x1, x2 0, : + 800 x2 (1 ) ( x1, x2,, xn ), (2 ), 9

(3 ), ( ), : max ( min) z = c1 x1 + c2 x2 + + cn x n ( 1-1) a11 x1 + a12 x2 + + a1 n x n ( =, ) b1 a21 x1 + a22 x2 + + a2 n x n ( =, ) b2 ( 1-2) am1 x1 + am2 x2 + + am n x n ( =, ) bm x1, x2,, xn 0 ( 1-3), ( 1-1 ) ; ( 1-2 )( 1-3) ; (1-3) 1. 2, 1 x1 x2, x1, x2 0 1 1-2, z = 2 x1 : x2 = - ( 2/ 3) x1 + z/ 3,, z, x2 = - ( 2/ 3 ) x1 + z/ 3 Q2 x1 + 2 x2 8 x1 + 2 x2 = 8, x1, x2 0, x1 + 2 x2 8, 4 x1 16 4 x2 12, x1, x2 1 1-2 ( ) ( ), 1 + 3 x2,, z - 2/ 3, z ( 1-3 ), 1 Q2, Q2 (4,2 ) z = 14 1-3 10

: 4, 2, 14,, : 1. ( ) 1 max z = 2 x1 + 4 x2, z x1 + 2 x2 8 z, Q2 Q3 ( 1-4 )Q2 Q3 z, () 2. max z = x1 + x2-2 x1 + x2 4 x1 x1, - x2 2 x2 0 1-51 -5,, 1-4 1-5 3. 1-2 x1, + x2 4,, 2 3,,,,,, ;,,,, 3 11

, 1. 3, max, min;,,, ( -, ), : ( M1 ) max z = c1 x1 + c2 x2 + + cn x n n 1 ) max z = ( M a1 1 x1 + a1 2 x2 + + a1 n x n = b1 a2 1 x1 + a2 2 x2 + + a2 n x n = b2 am1 x1 + am2 x2 + + am n x n = bm x1, x2,, xn 0 j = 1 cj x j n ai j x j j = 1 xj = bi, i = 1, 2,, m 0, j = 1, 2,, n bi > 0, - 1 : ( M 1 ) max z = C X : C = ( c1, c2,, cn ) n Pj x j j = 1 x j = b 0, j = 1, 2,, n x1 a1 j b1 X = x2 ; Pj = a2 j ; b= b2 xn am j Pj x j : max z = C X A X = b X0 bm 12

A = a11 a12 a1 n am1 am2 am n = ( P1, P2,, Pn ) ; 0 = A mn, m < n; b; C; X 0 0 (1 ), min z = CX, z = - z, max z = - CX (2 ) :,, ;, ( ), 3 1 1 ( M2 ) max z = 2 x1 + 3 x2 x1 + 2 x2 8 4 x1 16 x1, 4 x2 12 x2 0 x3, x4, x5, : x3 x4 x5, c3, c4, c5 = 0 max z = 2 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5 x1 + 2 x2 + x3 = 8 4 x1 + x4 = 16 4 x2 + x5 = 12 x1, x2, x3, x4, x5 0, (3 ) xk, xk = x k - x k, x k, x k 0,, 4 0 min z = - x1 + 2 x2-3 x3 x1 + x2 + x3 7 x1 - x2 + x3 2-3 x1 + x2 + 2 x3 = 5 x1, x2 0, x3 13

: (1 ) x4 - x5 x3, x4, x5 0; (2 ) x6 ; (3 ) x7 ; (4 ) z= - z, min z max z, max z= x1-2 x2 + 3 ( x4 - x5 ) + 0 x6 + 0 x7 x1 + x2 + ( x4 - x5 ) + x6 = 7 x1 - x2 + ( x4 - x5 ) - x7 = 2-3 x1 + x2 + 2( x4 - x5 ) = 5 x1, x2, x4, x5, x6, x7 0 1. 4, 1. 3 ( M1 ), 1. n max z = cj x j ( 1-4) j = 1 n ai j x j j = 1 = bi, i = 1, 2,, m xj 0, j = 1, 2,, n ( 1-5) ( 1-6) (1-5) ( 1-6) X = ( x1, x2,, xn ) T,, 2. A mn, mb A mm ( B 0), B, B m, a11 a12 a1 m B = = ( P1, P2,, Pm ) am1 am2 am m Pj ( j = 1, 2,, m), Pj x j ( j = 1, 2,, m),,, (1-5 ) A m, m < n, m (1-5) a11 a1 2 a1 m a21 x1 + a2 2 x2 + + a2 m x m am1 am2 am m 14

b1 a1, m + 1 a1 n = b2 - a2, m + 1 xm + 1 - - a2 n x n ( 1-7) (1-7) bm am, m + 1 m Pj x j j = 1 n = b - Pj x j j = m + 1 am n a11 a12 a1 m B = a21 a22 a2 m = ( P1, P2,, Pm ) am1 am2 am m XB X B = ( x1, x2,, xm ) T (1-7) xm + 1 = x m + 2 = = xn = 0,, X = ( x1, x2,, xm, 0,,0 ) T m, X,, 1-2 0, Q1, Q2, Q3, Q4 ( x1 = 0, x2 = 0) 3. (1-6 ), 1-2 0, Q1, Q2, Q3, Q4, m, 4., (1-5) C m n, 1-6, m,,, 1-6 15

2 1. 2,, X ( 1 ) 2. 1 1. K n, X ( 1 ) K, X ( 2 ) K + ( 1 - ) X ( 2 ) K, ( 01) ; K,,,,, 1-7 ( a) ( b), ( c) 1-2, 1-7( d ) 1-7 2. X ( 1 ), X ( 2 ),, X ( k) n E n 1, i = 1, 2,, k; i = 1, k i = 1 X = 1 X ( 1 ) + 2 X ( 2 ) + + k X ( k) k 1, 2,, k, 0 i X X ( 1 ), X ( 2 ),, X ( k ) (0 < i < 1, ) 3. K, XK; X X ( 1 ) K X ( 2 ) K X =X ( 1 ) X K ( ) 16 2. 2 + ( 1 - ) X ( 2 ), (0 << 1) 1, D = n X Pj x j = b, x j 0 j = 1

n Pj x j = b, x j 0, j = 1,2,, n j = 1 (), D D X ( 1 ) = ( x ( 1 ) 1, x ( 1 ) 2,, x ( 1 ) n D ; X ( 1 ) X ( 2 ) X = ( x1, x2,, xn ) T X x j = x ( j 1 ) X ( 2 ) = ( x 1 ( 2 ), x 2 ( 2 ),, x ( n 2 ) n Pj x ( j 1 ) = b, x ( j 1 ) j = 1 n Pj x ( 2 ) j = b, x ( 2 ) j j = 1 ) T ) T 0, j = 1, 2,, n 0, j = 1, 2,, n x ( 1 ), x ( 2 ), X =X ( 1 ) n Pj x j j = 1 + (1 - ) x ( j 2 ) + ( 1 - ) X ( 2 ) ( 01) n = j = 1,, Pj [ x ( 1 ) j n = Pj x ( j 1 ) j = 1 + ( 1 - ) x ( 2 ) j ] n + Pj x ( j 2 ) j = 1 = b + b - b = b n - Pj x ( j 2 ) j = 1 x ( 1 ) j, x ( 2 ) j 0,> 0, 1 - > 0, x j 0, j = 1, 2,, nxd, D 1 X = ( x1, x2,, xn ) T X (1 ) (2 ) P1, P2,, Pk, km; k = m,, X = ( x1, x2 m - k P 1, P2,, Pk X,,, xk, 00 ) k < m,, 2 X D, X m, (1 ) X, D m Pj x j = b (1-8 ) j = 1 1, X, P1, P2,, P m, i, i = 1, 2,, m 1 P1 + 2 P2 + + m P m = 0 ( 1-9) > 0 ( 1-9)(1-8 ), 17

( x1-1 ) P1 + ( x2-2 ) P2 + + ( xm - m ) P m ( x1 + 1 ) P1 + ( x2 + 2 ) P2 + + ( xm + m ) P m = b = b X ( 1 ) = [ ( x1-1 ), ( x2-2 ),, ( xm - m ), 0,, 0] X ( 2 ) = [ ( x1 + 1 ), ( x2 + 2 ),, ( xm + m ), 0,, 0] X ( 1 ), X ( 2 ) X = 1 2 X( 1 ) + 1 2 X( 2 ), X X ( 1 ), X ( 2 ),, xi i 0, i = 1, 2,, m X ( 1 ), X ( 2 ) X D (2 ) X D, X D, D X ( 1 ) = ( x ( 1 ) 1, x ( 1 ) 2,, x ( 1 ) n X ( 2 ) = ( x ( 2 ) 1, x ( 2 ) 2,, x ( 2 ) n X = X ( 1 ) + (1 - ) X ( 2 ) 0 << 1 X, P1 P m j > m, x j = x ( j 1 ) = x ( j 2 ) X ( 1 ), X ( 2 ), m Pj x ( 1 ) j j = 1 ) T ) T m = b Pj x ( 2 ) j j = 1 m Pj ( x ( j 1 ) - x ( j 2 ) ) = 0 j = 1 = b = 0, X ( 1 ) X ( 2 ), ( x ( 1 ) j - x ( 2 ) j ), P1, P2,, Pm, X 2 K, XK K, 1-8 X = [X ( 1 ) =X ( 1 ) 5 X, X ( 1 ), X ( 2 ) X ( 3 ), X( 1-8) X ( 2 ), X X ( 2 ) ; X ( 1 ) X ( 3 ) X X X ( 1 ) X ( 3 ), X ( 1 ) X ( 3 ) X=X ( 1 ) + ( 1 - ) X ( 3 ) 0 < < 1 X XX ( 2 ), X =X+ (1 - ) X ( 2 ) 0 << 1 X + (1 - ) X ( 3 ) ] + (1 - ) X ( 2 ) + (1 - ) X ( 3 ) + (1 - ) X ( 2 ) 18

1 =, 2 = ( 1 - ), 3 = ( 1 - ) X = 1 X ( 1 ) + 2 X ( 2 ) + 3 X ( 3 ) i i = 1, 0 < i < 1 3, X ( 1 ), X ( 2 ),, X ( k), X ( 0 ), X ( 0 ) z * = C X ( 0 ) ( z * = max z) X ( 0 ), D X ( 0 ) CX ( 0 ) k = i X ( i) i = 1 k = C i X ( i) i = 1 k, i > 0, i = 1 i = 1 k = i C X ( i) ( 1-10 ) i = 1 X ( m), C X ( m) C X ( i) X ( m) ( 1-10)X ( i), k i CX ( i) i = 1 CX ( 0 ), k i C X ( m ) = CX ( m) i = 1 C X ( 0 ) C X ( m) C X ( 0 ) = C X ( m) X ( m) ^ ( 1 ), X ^ ( 2 ) X ^,, X ^ ( k ),, ^ = i X ^ ^ C X k i = 1 ( i) X, i = i C ^ ^ ( i) C X ^ C X k i = 1 ( i) X X k > 0, i = 1 k = i C X i = 1 i = 1 ^ ( i) = m, i = 1, 2,, k k = i m = m i = 1,,,,, :,, 19

, ;, ( C n m ),,, n, m,,,,, 3 :,,,,, : 0,,,, n n + 1, ( 0, 0, 0), ( 1, 0, 0), ( 0, 1, 0), ( 0, 0, 1) x i 1, x i 0, i = 1, 2,, m, 3. 1 6 1 1 max z = 2 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5 (1-11) x1 + 2 x2 + x3 = 8 (1-12 ) (1-12 ) x3, x4, x5 4 x1 + x4 = 16 4 x2 + x5 = 12 x j 0, j = 1,2,, 5 A = ( P1, P2, P3, P4, P5 ) = P3 =, 1 0 0, P4 = 0 1 0 B = ( P3, P4, P5 ) = 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1, P5 = 0 0 1 1 0 0 0 1 0 0 0 1 B x3, x4, x5, ( 1-12) (1-12) x3 = 8 - x1-2 x2 x4 = 16-4 x1 (1-13) x5 = 12-4 x2 20

(1-13 )( 1-11 ) z = 0 + 2 x1 + 3 x2 (1-14) x1 = x2 = 0, z = 0X ( 0 ) X ( 0 ) = ( 0, 0, 8, 16, 12) T : ;, z = 0 ( 1-14 ) : x1, x2 (, ),,,, (1-14 ),, x2,,, (1-13 ), x2, x3, x4, x5,, x3, x4, x5 0 x1 = 0, (1-13) (1-15 ), x3 = 8-2 x2 0 x4 x5 = 160 = 12-4 x2 0 x2 = min(8/ 2, -, 12/ 4 ) = 3 (1-15), ( 1-15 ) x2 = 3, x5 = 0, x2 x5, ( 2, 0, 4), B x2 = 12 4 = 3 x3, x4, x2 x2 x5, ( 1-16 ) x2, ( 1-13 ) x3 + 2 x2 = 8 - x1 x4 = 16-4 x1 4 x2 = 12 - x5 (1-16) : = / 4 ; = - 2 ; =, : x3 = 2 - x1 + 1 2 x5 x4 = 16-4 x1 x2 = 3-1 4 x5 (1-17) (1-17 )( 1-11 ) 21

z = 9 + 2 x1-3 4 x5 (1-18) x1 = x5 = 0, z = 9, X ( 1 ) X ( 1 ) = (0,3,2,16, 0) T (1-18), x1,, X ( 1 ),,, X ( 2 ) X ( 2 ), X ( 3 ) : X ( 3 ) (1-19 ), x3, x4 = (2, 3, 0, 8, 0 ) T = (4, 2, 0, 0, 4 ) T z = 14-1. 5 x3-0. 125 x4 (1-19) x3, x4, x3 = x4 = 0,, X ( 3 ) 4, 2,,, 1, x1, x2 ; x3, x4, x5,,, ( ), X ( 0 ) = ( 0, 0, 8, 16, 12 ) T 1-2 ( 0, 0), X ( 1 ) = (0,3, 2, 16, 0 ) T 1-2 Q4 ( 0, 3 ) ; X ( 2 ) = (2,3,0,8,0 ) T 1-2 Q3 (2,3 ), X ( 3 ) = ( 4, 2, 0, 0, 4 ) T 1-2 Q2 ( 4, 2) X ( 0 ), X ( 1 ), X ( 2 ), X ( 3 ) 1-2, 0, Q4, Q3, Q2 3. 2,, (1 ) n max z = cj x j (1-20) j = 1 n Pj x j = b (1-21) j = 1 x j 0, j = 1, 2,, n Pj ( j = 1, 2,, n) 22 B = ( P1, P2,, Pm ) = 1 0 0 0 1 0 0 0 1

(2 ),,, x j ai j ( i = 1, 2,, m; j = 1, 2,, n), x1 + a1, m + 1 x m + 1 + + a1 n x n = b1 x2 + a2, m + 1 x m + 1 + + a2 n x n = b2 (1-22) x m + am, m + 1 x m + 1 + + am n x n = bm x j 0, j = 1, 2,, n mm 1 0 0 0 1 0 B = ( P1, P2,, Pm ) = 0 0 1 B (1-22 ) x1 = b1 - a1, m + 1 xm + 1 - - a1 n x n x2 = b2 - a2, m + 1 xm + 1 - - a2 n x n (1-23) xm + 1 = xm + 2 = = xn = 0, (1-23 ) x m = bm - am, m + 1 xm + 1 - - am n x n xi = bi ( i = 1, 2,, m) bi 0(1. 3 ), X = ( x1, x2,, xm, 0,,0 ) T n - m = ( b1, b2,, bm, 0,, 0 n - m (3 ),,, ;, 5 3. 3,, (1-23 ) xi = b i n - j = m+ 1 (1-24 )( 1-20), m z = ci b i i = 1 ) T a i j x j ( i = 1,2,, m) ( 1-24) n + cj j = m+ 1 m - ci a i j x j ( 1-25) i = 1 23

z0 m = ci b i = 1 m i, zj = z = z0 i = 1 ci a i j, j = m + 1,, n n + ( cj - zj ) x j ( 1-26) j = m+ 1 j = cj - zj ( j = m + 1,, n) z = z0 n + j x j ( 1-27) j = m+ 1 1. X ( 0 ) = ( b 1, b 2,, b m, 0,, 0 ) T j = m + 1,, n, j 0, X ( 0 ) j 2. X ( 0 ) = ( b 1, b 2,, b m,0,,0) T m + k B,, j = m + 1,, n, j 0, = 0, xm + k, X ( 1 ) m + k = 0, (1-27 )z = z0, X ( 1 ) 2. 2 3 X ( 0 ), X ( 1 ) 3. X ( 0 ) = ( b 1, b 2,, b m,0,, 0) T, m + k > 0, i = 1, 2,, m, ai, m + k 0, ( ) X ( 1 ), x ( i 1 ) x ( 1 ) m + k x ( j 1 ) = b i - a i, m + k (> 0 ) = = 0, j = m + 1,, n, jm + k ai, m + k 0, > 0, x ( 1 ) m + k z = z0 + m + k > 0, +, z+,,,,, 1, 2 j 0 j 0, 3 m + k > 0 m + k < 0 24 3. 4 X ( 0 ),

(),,,,,, 1. (1-27 ), j > 0, x j, x j ( ) j > 0,?, j > 0, xk max j ( j > 0) = k 2. P1, P2,, Pm, X ( 0 ) (1-21 ) m x ( 0 ) i = 1 i P i = b ( 1-28) Pm + 1, Pm + 2,, Pm + t,, Pn P1, P2,, Pm, Pm + t, 0 ( i = 1, 2,, m) Pm+ t Pm+ t m = i, m+ t P i i = 1 m - i, m+ t P i = 0 (1-29) i = 1 (1-29 ), ( 1-28), m m x ( 0 ) i P i + Pm + t - i = 1 i = 1 m i i = 1 ( x ( 0 ) i, m+ t P i = b - i, m+ t ) Pi + P m+ t = b (1-30), ( m ) ( x ( 0 ) i - i, m + t ) ( i = 1, 2,, m), 0 ) : x( i ( i = 1, 2,, m) i, m + t 0 ), x( i i, m + t : > 0 ( i = 1, 2,, m) = min x ( 0 ) i i i, m + t i, m + t > 0 = x( 0 ) l l, m + t 0 ) xi, = x( l X, l, m + t 25

X ( 1 ) = x 1 ( 0 ) x ( 0 ) l - 1, m + t,, 0,, l, m + t l x ( x ( m 0 ) l 0 ) - m, m + t, 0,, l, m + t X ( 0 ) X ( 1 ) x ( 1 ) i = x ( 0 ) i - x ( 0 ) l l, m + t x ( i 0 ) X ( 0 ) ; x ( i 1 ) x ( 0 ) l l, m + t x ( l 0 ),, 0 l, m + t m + t i, m + t il i = l X ( 1 ) ; i, m + t P m + t, X ( 1 ) m?, X ( 0 ), x ( 0 ) l x ( 0 ) l - l, m + t = 0 l X ( 1 ),, ( ), l, m + t 0X ( 1 ) m m P j ( j = 1,2,, m, jl)pm + t, j, (1-32 ) ( 1-31 ) m j = 1 jl Pm + t ( j, m+ t Pm + t m = j P j j l ( 1-31 ) j = 1 m = j, m+ t P j ( 1-32 ) j = 1 - j ) Pj + l, m+ t Pl = 0 l, m + t 0, P1, P2,, Pm,, X ( 1 ) m P j ( j = 1, 2,, m, jl) Pm + t,,,, (1-2 ) 3. 5 ( ),, 26

x1 + a1, m + 1 xm + 1 + + a1 k x k + + a1 n x n = b1 x2 + a2, m + 1 xm + 1 + + a2 k x k + + a2 n x n = b2 x l + al, m + 1 x m + 1 + + al k x k + + al n x n = bl x m + am, m + 1 x m + 1 + + am k x k + + am n x n = bm (1-33), x1, x2,, xm, mm I, xm + 1, xm + 2,, xn,, xk = min i bi ai k ai k > 0 = b l al k = min i b i a i k i k > 0 = b l a l k a b i, a i k bi, ai k ( ) x l, xk, x l Pk = a1 k a2 k ; Pl = al k am k 0 1 0 0 l xk x l, Pk, (1-33 ) x1 x l xm x m + 1 xk xn b : 1 a1, m + 1 a1 k a1 n 1 al, m + 1 al k al n 1 am, m + 1 am k am n (1 ) ( 1-34) l al k, 0,, 0, 1 al k, 0,, 0, al, m + 1 al, k,,1, al n al k b1 bl bm bl al k (1-34) (1-35) (2 ) ( 1-34) xk, al k 1, (1-35 )ai k ( il), (1-34) i, i 0,, 0, - ai k al k,0,, 0, ai, m + 1 - al, m + 1 al k ai k,, 0,, al n - al n al k ai k bi - bl ai k al k : 27

a i j = ai j - al j al k a i j, b i al j al k ai k ( il) ( i = l) (3 ) ; b i = bi bl al k - ai k bl ( il) al k x1 x l x m xm + 1 xk xn b ( i = l) 1- a1 k 0 al k 0+ 1 a1 k 0 a 1, m + 1 0 ab 1 n 1 n a l, m + 1 1 a l n b l (1-36) 0- am k 1 a m, m + 1 0 a m n b m al k (4 ) ( 1-36) x1, x2,, xk,, xm mm,, xm + 1,, x1,, xn X ( 1 ) = ( b 1, b l - 1, 0, b l + 1 b m, 0b k,00) T, X ( 1 ), al k,, al k 1 7 6 6 x1 x2 x3 x4 x5 b 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 x3, x4, x5, x1, x2, x1, x2 = 0, X ( 0 ) 8 16 12 = ( 0, 0, 8, 16, 12) T x2 x5, x3, x4, x2, x1, x5 = 0, x1 x2 x3 x4 x5 b 1 0 1 0-1/ 2 4 0 0 1 0 0 1 0 0 1/ 4 X ( 1 ) = (0,3,2,16, 0) T 2 16 3 4 28,

4. 1,,,, (1-22 ) n+ 1, m + 1 x1 + a1 m + 1 xm + 1 + + a1 n x n = b1 x2 + a2 m + 1 xm + 1 + + a2 n x n = b2 x m + am m + 1 xm + 1 + + am n x n = bm - z + c1 x1 + c2 x2 + + cm x m + cm + 1 x m + 1 + + cn x n = 0, - z x1 x2 xm x m + 1 x n b 0 1 0 0 a1, m + 1 a1 n 0 0 1 0 a2, m + 1 a2 n b1 b2 0 0 0 1 am, m + 1 am n 1 c1 c2 cm cm + 1 cn z, x1, x2,, xm, c1, c2,, cm, - z x1 x2 xm xm + 1 xn b bm 0 0 1 0 0 a1, m+ 1 a1 n 0 0 1 0 a2, m+ 1 a2 n 0 0 0 1 am, m+ 1 am n m m 1 0 0 0 cm+ 1 - ci ai, m+ 1 cn - i = 1 i = 1 ci ai n b1 b2 bm m - ci i = 1 bi, 1-2 1-2 C B X B b c j c 1 c m c m+ 1 c n x 1 x m x m + 1 x n i c 1 x 1 b 1 1 0 a 1, m + 1 a 1 n 1 c2 x2 b2 0 0 a2, m + 1 a2 n 2 c m x m b m 0 1 a m, m + 1 a m n m m - z - i = 1 m c i b i 0 0 c m+ 1 - i = 1 m c i a i, m+1 c n - i = 1 c i a i n 29

XB, x1, x2,, xm ; CB, c1, c2,, cm ; ; b ; cj c1, c2,, cn ; i, ;, xj cj m - ci ai j i = 1, j = 1, 2,, n 1-2, 4. 2 (1 ),, (2 ) xj m j = cj - i = 1 ci ai j,, j 0, j = m + 1,, n (3 ) j > 0, j = m + 1,, n, k x k P k 0,,, xl (4 ) max( j > 0 ) = k, xk = min,, bi ai k ai k > 0 = bl (5 ) al k ( ), xk Pk = a1 k a2 k al k am k 0 0 al k 1 l XB x l x k, ( 2) (5 ), 1 (1 ) 1, x3, x4, x5, X ( 0 ) 0 = ( 0, 0, 8, 16, 12) T,, 1-3 30

1-3 cj 2 3 0 0 0 CB X B b x1 x2 x3 x4 x5 0 x 3 8 1 2 1 0 0 4 0 x4 16 4 0 0 1 0-0 x5 12 0 [4] 0 0 1 3 - z 0 2 3 0 0 0 1-3 cj CB,, 1 = c1 - z1 = 2 - (01 + 04 + 00) = 2 2 = c2 - z2 = 3 - (02 + 00 + 04) = 3 (2 ), P1, P2, ; (3 ) max( 1, 2 ) = max( 2, 3) = 3, x2, = min i bi ai2 ai2 > 0 = min (8/ 2, -, 12/ 4 ) = 3 x5 x2 x5 [4 ] ( pivot element) x2 (4 ) [ 4],, P2 ( 0, 0, 1) T, xb x5, 1-4 1-4 c j 2 3 0 0 0 i C B X B b x 1 x 2 x 3 x 4 x 5 0 x3 2 [ 1] 0 1 0-1/ 2 2 0 x 4 16 4 0 0 1 0 4 3 x 2 3 0 1 0 0 1/ 4 - - z 9 2 0 0 0-3/ 4 b x 3 = 2, x4 = 16, x2 = 3 X ( 1 ) z = 9 = ( 0, 3, 2, 16,0 ) T ( 5) 1-4 cj - zj, c1 - z1 = 2; x1 ( 2) (4 ), 1-5 1-5 c j 2 3 0 0 0 i C B X B b x 1 x 2 x 3 x 4 x 5 2 x1 2 1 0 1 0-1/ 2-0 x 4 8 0 0-4 1 [2] 4 3 x 2 3 0 1 0 0 1/ 4 12 - z - 13 0 0-2 0 1/ 4 31

cj 2 3 0 0 0 i C B X B b x 1 x 2 x 3 x 4 x 5 2 x1 4 1 0 0 1/ 4 0 0 x 5 4 0 0-2 1/ 2 1 3 x 2 2 0 1 1/ 2-1/ 8 0 - z - 14 0 0-3/ 2-1/ 8 0 (6 ) 1-5, X * = X ( 3 ) = ( 4, 2, 0, 0, 4) T z * = 14 5 5. 1 3. 2 n Pj x j j = 1 = b xn + 1,, xn + m, a11 x1 + a12 x2 + + a1 n x n + xn + 1 = b1 a21 x1 + a22 x2 + + a2 n x n + xn + 2 = b2 am1 x1 + am2 x2 + + am n x n + xn + m = bm x1,, xn 0, xn + 1,, xn + m 0 xn + 1,, xn + m, mm x1,, xn X ( 0 ) = ( 0, 0,, 0, b1, b2,, bm ) T,,, cj 1. M - zj 0,,,, ( - M) ( M ),, 32 8

min z = - 3 x1 + x2 + x3 x1-2 x2 + x3 11-4 x1 + x2 + 2 x3 3-2 x1 + x3 = 1 x1, x2, x3 0 M x4, x5, x6, x7, min z = - 3 x1 + x2 + x3 + 0 x4 + 0 x5 + M x6 + M x7 x1-2 x2 + x3 + x4 = 11-4 x1 + x2 + 2 x3 - x5 + x6 = 3-2 x1 + x3 + x7 = 1 x1, x2, x3, x4, x5, x6, x7 0 M, 1-6 min, cj 1-6 x1 = 4, x2 = 1, x3 = 9, x4 = x5 = x6 = x7 = 0 z = - 2 - zj 0 1-6 cj - 3 1 1 0 0 M M C B X B b x 1 x 2 x 3 x 4 x 5 x 6 x 7 i 0 x4 11 1-2 1 1 0 0 0 11 M x 6 3-4 1 2 0-1 1 0 3/ 2 M x7 1-2 0 [1 ] 0 0 0 1 1 c j - z j - 3 + 6 M 1 - M 1-3 M 0 M 0 0 0 x 4 10 3-2 0 1 0 0-1 M x 6 1 0 [1 ] 0 0-1 1-2 1 1 x 3 1-2 0 1 0 0 0 1 cj - zj - 1 1 - M 0 0 M 0 3 M - 1 0 x4 12 [ 3] 0 0 1-2 2-5 4 1 x 2 1 0 1 0 0-1 1-2 1 x 3 1-2 0 1 0 0 0 1 c j - z j - 1 0 0 0 1 M - 1 M + 1-3 x 1 4 1 0 0 1/ 3-2/ 3 2/ 3-5/ 3 1 x 2 1 0 1 0 0-1 1-2 1 x3 9 0 0 1 2/ 3-4/ 3 4/ 3-7/ 3 c j - z j 2 0 0 0 1/ 3 1/ 3 M - 1/ 3 M - 2/ 3 33

2., M, : ;, min = xn + 1 + + xn + m + 0 x1 + + 0 xn a11 x1 + + a1 n x n + xn + 1 = b1 a21 x1 + + a2 n x n + xn + 2 = b2 am1 x1 + + am n x n + xn + m = bm x1, x2,, xn + m 0, = 0,,, :,,, 3 9 min z = - 3 x1 + x2 + x3 x1 + 2 x2 + x3 11-4 x1 + x2 + 2 x3 3-2 x1 + x3 = 1 x1, x2, x3 0, : min = x6 + x7 x1-2 x2 + x3 + x4 = 11-4 x1 + x2 + 2 x3 - x5 + x6 = 3-2 x1 + x3 + x7 = 1 x1, x2, x3, x4, x5, x6, x7 0 x6, x7, 1-7 = 0, x1 = 0, x2 = 1, x3 = 1, x4 = 12, x5 = x6 = x7 = 0 x6 = x7 = 0, ( 0, 1, 1, 12,0 ) T, 1-8 34

1-7 cj 0 0 0 0 0 1 1 C B X B b x 1 x 2 x 3 x 4 x 5 x 6 x 7 i 0 x4 11 1-2 1 1 0 0 0 11 1 x 6 3-4 1 2 0-1 1 0 3/ 2 1 x7 1-2 0 [1] 0 0 0 1 1 c j - z j 6-1 - 3 0 1 0 0 0 x 4 10 3-2 0 1 0 0-1 - 1 x6 1 0 [ 1] 0 0-1 1-2 1 0 x 3 1-2 0 1 0 0 0 1 - cj - zj 0-1 0 0 1 0 3 0 x 4 12 3 0 0 1-2 2-5 0 x 2 1 0 1 0 0-1 1-2 0 x3 1-2 0 1 0 0 0 1 c j - z j 0 0 0 0 0 0 1 1 1-8 c j - 3 1 1 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 i 0 x 4 12 [3 ] 0 0 1-2 4 1 x 2 1 0 1 0 0-1 - 1 x3 1-2 0 1 0 0 - c j - z j - 1 0 0 0 1-3 x 1 4 1 0 0 1/ 3-2/ 3 1 x2 1 0 1 0 0-1 1 x 3 9 0 0 1 2/ 3-4/ 3 c j - z j 2 0 0 0 1/ 3 1/ 3 1-8 x1 = 4, x2 = 1, x3 = 9, z = - 2 5. 2,,, x l = 0,,,, B1, B2, B1,,,? 35

, 1974 ( Bland), : (1 ) cj - zj > 0 x k, k = min( j cj - z j > 0 ) (2 ),, 5. 3 max z = C X; A X = b, X0 ; cj - zj 0, ( j = 1, 2,, n), x1, x2,, xm, n x i = bi - ai j x j, i = 1, 2,, m j = m+ 1, m z = ci bi i = 1 n + cj j = m+ 1 m - ci ai j i = 1 n = z0 + ( cj j = m+ 1 - zj ) x j (1-37) m z = i = 1 ci bi - n j = m+ 1 xj m ci ai j - cj xj i = 1 n = z0 - ( zj j = m+ 1 - cj ) x j (1-38), ( 1-37 ), cj (1-38 ), zj - zj 0, ( j = 1, 2,, n) - cj 0, ( j = 1,2,, n),, (1-37 ) ( 1-38 ), cj - zj 0 zj - cj 0, ( j = 1, 2,, n) 1-9 1-9 max z = CX A X = b, X0 min z = C X A X = b, X0 c j - z j 0 z j - c j 0 0 0 36 5. 4 (1 ),, 1-10

1-10 x j 0 xj 0 xj x j = - xj ; x j 0 x j = x j - x j ; x j, x j 0 b0 b < 0 = - 1 xs i x a i ( ) x s i,x a i max z min z xs i z = - z,max z 0 xa i - M, (2 ) max, 1-9 1-9 37

6,, (1 ), ; (2 ) ; (3 ), 10 100, 2. 9 m,2. 1 m 1. 5m 7. 4m,,, 2. 9m, 2. 1m 1. 5m, 0. 9m 100, 100, 90m,, 1-11 1-11 ( m) 2. 9 1 2 1 2. 1 0 2 2 1 1. 5 3 1 2 3 7. 4 7. 3 7. 2 7. 1 6. 6 0 0. 1 0. 2 0. 3 0. 8 100, x1, x2, x3, x4 : min z = 0 x1 + 0. 1 x2 + 0. 2 x3 + 0. 3 x4 + 0. 8 x5, x5 1-11, x1 + 2 x2 + x4 = 100 2 x3 + 2 x4 + x5 = 100 3 x1 + x2 + 2 x3 + 3 x5 = 100 x1, x2, x3, x4, x5 0 x6, x7, x8 ; 1-12 : 30 ; 10 ; 50 90 100 11 C PH ABD,,, 1-13 1-14,? 38 AC A C, AP A P,

1-13 : AC 1 2 A, AP 1 4 A, BC1 4 B, BP 1 2 B (1-39) AC + AP + AH = A (1-40) BC + BP + B H = B (1-39 ) ( 1-40 ) - 1 2 AC + 1 2 AP + 1 2 A H 0 1-12 c j 0-0. 1-0. 2-0. 3-0. 8 - M - M - M i CB XB b x1 x2 x3 x4 x5 x6 x7 x8 - M x 6 100 1 2 0 1 0 1 0 0 100 1 - M x 7 100 0 0 2 2 1 0 1 0 - - M x8 100 [3] 1 2 0 3 0 0 1 100 3 4M - 0. 1 + 3 M - 0. 2 + 4M - 0. 3 + 3M - 0. 8 + 4 M 0 0 0 - M x 6 200/ 3 0 5/ 3-2/ 3 1-1 1 0-1/ 3 - M x 7 100 0 0 2 [2] 1 0 1 0 200 3 100 2 0 x1 100/ 3 1 1/ 3 2/ 3 0 1 0 0 1/ 3 - - 0. 1 + - 0. 2 + 0-0. 3 + 3M - 0. 8 0 0-4/ 3M 5/ 3M 4/ 3M - M x 6 50/ 3 0 [5/ 3] - 5/ 3 0-3/ 2 1-1/ 2-1/ 3 150 15-0. 3 x4 50 0 0 1 1 1/ 2 0 1/ 2 0 0 x1 100/ 3 1 1/ 3 2/ 3 0 1 0 0 1/ 3-0. 1 + 0. 1 - - 0. 65-0. 15-0 0 0-4/ 3M 5/ 3M 5/ 3M 3/ 2M 3/ 2 M 0. 1 x 2 10 0 1-1 0-9/ 10 3/ 5-3/ 10-1/ 5 100 1-0. 3 x4 50 0 0 1 1 1/ 2 0 1/ 2 0 0 x1 30 1 0 1 0 13/ 10-1/ 5 1/ 10 2/ 5 0 0 0 0-0. 74 - M+ 0. 06 - M+ 0. 12 - M - 0. 02 39

, 1-13 (/ kg ) A B C 50% P 25% C 25% P 50% 50 35 D 25-1 4 AC + 3 4 AP - 1 4 A H 0-3 4 BC + 1 4 BP + 1 4 BH 0-1 2 B C + 1 2 B P - 1 2 B H 0 1-14 ( kg ) / (/ kg) C 100 65 P 100 25 H 60 35 1-14 A BD C 100kg, P 100kg, H 60kg AC + BC + DC 100 AP + BP + DP 100 AH + B H + DH 60 9,, x1,, x9 x1 = AC x2 = AP x3 = A H x4 = BC x5 = BP x6 = B H x7 = DC x8 = DP x9 = DH : - 1 2 x1 + 1 2 x2 + 1 2 x3 0-1 4 x1 + 3 4 x2-1 4 x3 0-3 4 x4 + 1 4 x5 + 1 4 x6 0-1 2 x4 + 1 2 x5-1 2 x6 0 x1 + x4 + x7 100 x2 + x5 + x8 100 x3 + x6 + x9 60 x1,, x9 0 40

, : 50( x1 + x2 + x3 )A 35( x4 + x5 + x6 )B 25( x7 + x8 + x9 )D : 65( x1 + x4 + x7 ) C 25( x2 + x5 + x8 ) P 35( x3 + x6 + x9 ) H max z = 50 ( x1 + x2 + x3 ) + 35( x4 + x5 + x6 ) + 25 ( x7 + x8 + x9 ) - 65 ( x1 + x4 + x7 ) - 25( x2 + x5 + x8 ) - 35 ( x3 + x6 + x9 ) = - 15 x1 + 25 x2 + 15 x3-30 x4 + 10 x5-40 x7-10 x9, x10 x16, : max z = - 15 x1 + 25 x2 + 15 x3-30 x4 + 10 x5-40 x7-10 x9 + 0( x10 + x1 1 + x1 2 + x13 + x14 + x15 + x16 ) - 1 2 x1 + 1 2 x2 + 1 2-1 4 x1 + 3 4 x2-1 4 x3 + x10 = 0 x3 + x11 = 0-3 4 x4 + 1 4 x5 + 1 4-1 2 x4 + 1 2 x5-1 2 x6 + x12 = 0 x6 + x13 = 0 x1 + x4 + x7 + x14 = 100 x2 + x5 + x8 + x15 = 100 x3 + x6 + x9 + x16 = 60 xi 0, i = 1, 2,, 16,, : A 200kg, C 100kg; P 50kg; H 50 kg z = 500 / 12 ( i = 1,, 5 ), di j ( i = 1,, 5; j = 1,, 6 ) Si, ai, Ci ; rj ( j = 1,, 6 ), r j ; C i, H i (/ )1, 6 ki,, x i j, x i j i j ; yi j i j, wi j i j, : 41

(1 ), : 5 ai x i j rj ( j = 1,, 6 ) i = 1 5 i = 1 ai x i j r j ( j = 1,,6 ) (2 ) yi j di j ( i = 1,, 5; j = 1,, 6 ) (3 ) wi j = wi, j - 1 + xi j + x i j - yi j ( i = 1,, 5; j = 1,, 6 ) ; wi 0 = 0, wi 6 = ki (4 ) x i j 0, x i j 0, yi j 0, ( i = 1,, 5; j = 1,, 6) wi j 0 ( i = 1,, 5; j = 1,, 5) (5 ) : max z = 13 5 6 i = 1 j = 1 [ Si y i j - Ci x i j - C i x, : i j ] - 5 5 H i w i j i = 1 j = 1 A,, 115% ; B,, 125 %, 4 ; C,, 140 %, 3 ; D,,, 6% 10,,? (1 ),, x i A, xi B, xi C, xi D ( i = 1, 2,, 5)i A, B, C, D,, 1-15 1-15 A x 1 A x 2 A x 3 A x 4 A B C x 2 C D x1d x2d x3 D x4d x5d x 3 B 42

(2 ) D,, : 100000, x1 A + x1 D = 100000 : A D x1 D (1 + 6% ) x2 A + x2 C + x2 D = 1.06 x1 D : A D : x1 A ( 1 + 15% ) x2 D (1 + 6% ) x3 A + x3 B + x3 D = 1.15 x1 A + 1.06 x2 D :, : x4 A + x4 D = 1.15 x2 A + 1.06 x3 D x5 D = 1.15 x3 A + 1.06 x4 D, BC, : x3 B 40000 x2 C30000 (3 ), max z = 1.15 x4 A + 1.40 x2 C + 1.25 x3 B + 1.06 x5 D (4 ), : max z = 1.15 x4 A + 1.40 x2 C + 1.25 x3 B + 1.06 x5 D x1 A + x1 D = 100000-1. 06 x1 D + x2 A + x2 C + x2 D = 0-1. 15 x1 A - 1. 06 x2 D + x3 A + x3 B + x3 D = 0-1. 15 x2 A - 1. 06 x3 D + x4 A + x4 D = 0-1. 15 x3 A - 1. 06 x4 D + x5 D = 0 x2 C 30000 x3 B 40000 xi A, x i B, x i C, xi D 0 i = 1, 2,, 5 (5 ) : x1 A = 34783, x1 D = 65217 : x2 A = 39130, x2 C = 30000, x2 D = 0 : x3 A = 0, x3 B = 40000, x3 D = 0 : x4 A = 45000, x4 D = 0 : x5 D = 0 43

143750, 43.75% 1. 1,? (1 ) max z = x1 + 3 x2 ( 2) min z = x1 + 1. 5 x2 5 x1 + 10 x2 50 x1 + x2 1 x1, x2 0 x2 4 x1 + 3 x2 3 x1 + x2 2 x1, x2 0 (3 ) max z = 2 x1 + 2 x2 ( 4) max z = x1 + x2 x1 - x2-1 - 0. 5 x1 + x2 2 x1, x2 0 x1 - x2 0 3 x1 - x2-3 x1, x2 0 1. 2, (1 ) min z = - 3 x1 + 4 x2-2 x3 + 5 x4 (2 ) max s = zk/ pk 4 x1 - x2 + 2 x3 - x4 = - 2 x1 + x2 + 3 x3 - x4 14-2 x1 + 3 x2 - x3 + 2 x4 2 x1, x2, x3 0, x4 zk n m = i k x i k i = 1 k = 1 m - x i k = - 1( i = 1,, n) k = 1 x i k 0 ( i = 1,, n; k = 1,, m) 1. 3,, (1 ) max z = 2 x1 + 3 x2 + 4 x3 + 7 x4 ( 2) max z = 5 x1-2 x2 + 3 x3-6 x4 2 x1 + 3 x2 - x3-4 x4 = 8 x1-2 x2 + 6 x3-7 x4 = - 3 x1, x2, x3, x4 0 x1 + 2 x2 + 3 x3 + 4 x4 = 7 2 x1 + x2 + x3 + 2 x4 = 3 x1, x2, x3, x4 0 1. 4, 44

(1 ) max z = 2 x1 + x2 ( 2) max z = 2 x1 + 5 x2 3 x1 + 5 x2 15 6 x1 + 2 x2 24 x1, x2 0 x1 4 2 x2 12 3 x1 + 2 x2 18 x1, x2 0 1. 5 1. 4 ( 1),,, 1. 6 M, (1 ) max z = 2 x1 + 3 x2-5 x3 (2 ) min z = 2 x1 + 3 x2 + x3 x1 + x2 + x3 = 7 x1 + 4 x2 + 2 x3 8 2 x1-5 x2 + x3 10 3 x1 + 2 x2 6 x1, x2, x3 0 x1, x2, x3 0 (3 ) max z = 10 x1 + 15 x2 + 12 x3 (4 ) max z = 2 x1 - x2 + 2 x3 5 x1 + 3 x2 + x3 9 x1 + x2 + x3 6-5 x1 + 6 x2 + 15 x3 15-2 x1 + x3 2 2 x1 + x2 + x3 5 2 x2 - x3 0 x1, x2, x3 0 x1, x2, x3 0 1. 7 z z * z * max z = c1 x1 + c2 x2 a1 1 x1 + a1 2 x2 b1 a2 1 x1 + a2 2 x2 b2 x1, x2 0 :1c1 3, 4c2 6, 8b1 12, 10b2 14, - 1a11 3, 2a12 5, 2a21 4, 4a22 6 1. 8 1-16, a1 a2 a3 d c1 c2, (1 ) ; (2 ), ; (3 ) ; (4 ),, x1, x6 1-16 b x 1 x 2 x 3 x 4 x 5 x 6 x3 d 4 a1 1 0 a2 0 x 4 2-1 - 3 0 1-1 0 x 6 3 a 3-5 0 0-4 1 c j - z j c 1 c 2 0 0-3 0 45

1. 9 : 1 6001000 60 2 10001400 70 3 14001800 60 4 18002200 50 5 2200200 20 6 200600 30,, 1. 10 A B C A B C,,, 1-17 1-17 ( / ) ( ) A 60 % 15% 2. 00 2000 B 1. 50 2500 C 20 % 60% 50 % 1. 00 1200 (/ ) 0. 50 0. 40 0. 30 3. 40 2. 85 2. 25,? 1. 11,, A, B A, A1, A2, B1, B2, B3 ; B A, B A, B, B1 ; A2 B2,,, ( 1-18 ),, 1-18 ( ) A 1 5 10 6000 300 A 2 7 9 12 10000 321 B 1 6 8 4000 250 B2 4 11 7000 783 B 3 7 4000 200 ( / ) 0. 25 0. 35 0. 50 (/ ) 1. 25 2. 00 2. 80 46

2 1, : max z = C X ; A Xb; X0 Xs = ( xs1, xs2,, xs m ) T, : max z = C X + OX S ; A X + I X S I mm X S = b; X, X S 0, XB B, ( A, I) ( B, N) N, X = X B X N, C = ( CB, CN ), C CB, CN,, XB = X B 1 X S 1 ; X N = X N 1 X S2 ; X S = X S 1 X S 2 ; A = B N ; N = N1 B, N, S max z = CB X B + CN X N = CB X B + CN 1 X N 1 + CS 1 X S 1 ( 2-1) B X B + N X N = B X B + N1 X N 1 + S2 X S 2 = b ( 2-2) XB, X N 0 ( 2-3) (2-2), B X B = b - N1 X N 1 - S2 X S 2 ; B - 1, (2-4)(2-1 ), S2 X B = B - 1 b - B - 1 N1 X N1 - B - 1 S2 X S2 ( 2-4), z = CB B - 1 b+ ( CN1 - CB B - 1 N1 ) X N 1 + ( CS 2 - CB B - 1 I) X S ( 2-5) 1 XN = 0, X ( 1 ) = B- b : 0 S2, z = CB B - 1 b (1 ) ( CN 1 - CB B - 1 N1 )1 cj - zj ( j = 1, 2,, n) CS 2 = 0, I, X S 2 - CB B - 1, X B (2-5 ) 0, CB - CB B - 1 B = 0, C - CB B - 1 A - CB B - 1 (2 ), 47

( B - 1 b) i = min i ( B - 1 Pj ) i ( B - 1 Pj ) i > 0 = ( B - 1 b) i ( B - 1 Pj ) i ( 2-6) ( B - 1 b) i ( B - 1 b)i, ( B - 1 Pj ) i ( B - 1 Pj ) i 1,, (3 ) (2-4), ( 2-5) : XB + B - 1 N1 X N 1 + B - 1 X S 2 = B - 1 b - z + ( CN 1 - CB B - 1 N1 ) X N 1 - CB B - 1 X S 2 = - CB B - 1 b - z 0 I B - 1 N1 B - 1 1 0 CN - CB B - 1 N1 - CB B - 1 X B X N 1 = B - 1 b - CB B - 1 b ( 2-7) (2-7 ) 2-1, ( 0, 1) T, X S 2 2-1 XB X N X S R HS B - 1 B = 1 B - 1 N 1 B - 1 B - 1 b 0 CN 1 - CB B - 1 N1 - CB B - 1 - CB B - 1 b 2-1, B - 1,, B - 1 2,, B - 1 B - 1 : A = 48 P1 = 11 21 m1 11 12 1 m 21 22 2 m,, 1 m1 m2 m m, 11, : 1 = - 1/ 11 21/ 11 - m1/ 11

E1 = 1/ 1 1 0 0-21/ 11 1 - m1/ 11 1, E1 P1 = 1 0 ; E1 A = 2 22 ( 1 ), : 2 = 1-1 ( 1 2 ) / 22 ( 1 ) 0 0 1/ 22 ( 1 ) 0, E2 E1 A = 0 - ( m2 1 ) / 22 ( 1 ) 1, En E2 E1 A = 1 1 1 0 1 1 ( 1 2 ) 1 ( 1 m ) 0 ( 1 ) 2 2 ( 1 ) 2 m 0 ( 1 ) m2-1 ( 1 2 ) / 2 ( 1 2 ) 1/ 22 ( 1 ) - ( m2 1 ) / 2 ( 1 2 ) 1 0 13 ( 2 ) 1 ( 2 m ) ( 1 ) m m, E2 = 0 1 23 ( 2 ) 2 ( 2 m ) 0 0 ( m3 2 ) ( m 2 m ) En E2 E1 B B - 1 1 max z = 2 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5 x1 + 2 x2 + x3 = 8 4 x1 + x4 = 16 4 x2 + x5 = 12 = A - 1 :, B0 = ( P3, P4, P5 ) = 1 0 0 0 1 0 0 0 1, XB 0 = CB 0 = (0,0,0 ) ; X N 0 = N 0 = CN 0 - CB 0 B - 1 0 N0 = ( 2, 3) - (0, 0, 0 ) x2, = min x1 x2 ; CN 0 = ( 2, 3 ) 1 0 0 0 1 0 0 0 1 ( B - 1 0 b) i ( B0-1 P2 ) i x5, x2 P2 = 1 2 4 0 0 4 = ( 2, 3) B - 1 0 P2 > 0 = min 8 4, -, 12 4 2 0 4 x3 x4 x5 = 3, 4, ; 49

1 = - 1/ 2 0 1/ 4, B - 1 = E1 B - 1 0 = ( x1, x5 ): N1 = : B1 B - 1 1 N1 = B - 1 1 b = 1 0-1/ 2 0 1 0 0 0 1/ 4 = ( P3, P4, P2 ) 1 0-1/ 2 0 1 0 0 0 1/ 4 1 0 4 0 0 1 1 0-1/ 2 0 1 0 0 0 1/ 4 1 0 4 0 0 1 1 0 0 0 1 0 0 0 1 ; : 8 16 12 = = = 1-1/ 2 4 0 0 1/ 4 2 16 3 1 0-1/ 2 0 1 0 0 0 1/ 4 x3 X1 = x4, XN 1 = x1 ; CB 1 = (0,0,3), CN 1 = ( 2, 0) x3 x2 : : N 1 = CN 1 - CB 1 B1-1 N1 = (2, 0 ) - ( 0, 0, 3) = ( 2, - 3/ 4) x1, : 1 0-1/ 2 0 1 0 0 0 1/ 4 1 0 4 0 0 1 1 4 0 = min ( B1-1 b) i ( B - 1 1 P1 ) i B - 1 1 P1 > 1 = min 2 1, 16 4, 3 0 x3, B2 = ( P1, P4, P2 ) x1 P1 =, 1, 2 = 1 0 0-4 1 0 50 0 0 1 : 1 0-1/ 2 0 1 0 0 0 1/ 4 : ( x3 : = B - 1 2 b= 1-4 0 1 0-1/ 2-4 1 2 0 0 1/ 4 1 0-1/ 2-4 1 2 0 0 1/ 4, x5 ) = 2 B - 1 2 = E2 B - 1 1 = 8 16 12 = 2 8 3

N 2 = CN 2 - CB 2 B2-1 N2 = ( 0, 0) - (2, 0, 3 ) = ( - 2,1/ 4 ) x5, = min ( B3-1 b) i ( B - 1 3 P1 ) i 1 0-1/ 2-4 1 2 0 0 1/ 4 B - 1 3 P1 > 0 = min -, 8 2, 3 1/ 4 = 4 x4, B3 = ( P1, P5, P2 ) x5 B - 1 2 P5 = 1/ 4 1/ 2-1/ 8 B3 B - 1 3 = E3 B - 1 2 = X N 3 1 1/ 4 0 0 1/ 2 0 0-1/ 8 1 = ( x3, x4 ) : - 1/ 2 2 1/ 4 1 0-1/ 2-4 1 2 0 0 1/ 4 N 3 = CN 3 - CB 3 B - 1 3 N3 = (0,0 ) - ( 2, 0, 3), X * = x1 x5 x2 = ( - 3/ 2, - 1/ 8 ) = B - 1 3 b= : z * = CB B - 1 3 b= ( 2, 0, 3) 0 1/ 4 0-2 1/ 2 1 1/ 2-1/ 8 0 4 4 2 = 14 1 0 0 0 0 1, 2, 3 = = 0 1/ 4 0-2 1/ 2 1 1/ 2-1/ 8 0 0 1/ 4 0-2 1/ 2 1 1/ 2-1/ 8 0 8 16 12 = 4 4 2 1 0 0 1 0 0 3 1 1,, y1, y2, y3 A, B, : 1 4 A, 2,, 51

y1 + 4 y2 2, 2 y1 + 4 y3 3, = 8 y1 + 16 y2 + 12 y3,,,,, min = 8 y1 + 16 y2 + 12 y3 y1 + 4 y2 2 2 y1 + 4 y3 3 yi 0, i = 1, 2, 3 1 ( ) 1 1, CN - CB B - 1 N - CB B - 1 ( 2-8) CN - CB B - 1 N0 ( 2-9) - CB B - 1 0 (2-10) (2-9), ( 2-10 ) (1 ) ( 2-9 ), (2-10) CB B - 1,, Y = CB B - 1 (2-10 ), Y0 (2 ) X B 0CB - CB B - 1 B = 0 C - CB B - 1, 52 (3 ) Y ( 2-10 ), A0 (2-11 )b, C - CB B - 1 A = C - Y A0 Y AC - Y = - CB B - 1 (2-11) - Yb = - CB B - 1 b (2-12) Yb = CB B - 1 b = z Y, (4 ) min = Yb

Y AC Y0 {max z = CX A Xb, X0} : A, C, b 1 1, A = 1 2 4 0 0 4 ; C = ( 2, 3) ; b = 8 16 12 min = Y (8, 16, 12 ) T 1 2 Y 4 0 ( 2, 3) 0 4 Y 0 Y = ( y1, y2, y3 ) min = 8 y1 + 16 y2 + 12 y3 y1 + 4 y2 2 2 y1 + 4 y3 3 y1, y2, y3 0 4 ; 4. 1 max z = c1 x1 + c2 x2 + + cn x n a11 a12 a1 n am1 am2 am m x1 x2 b1 bm xn x1, x2,, xn 0 min = y1 b1 + y2 b2 + + ym b m 53

a11 a12 a1 n ( y1, y2,, ym ) ( c1, c2,, cn ) am1 am2 am n y1, y2,, ym 0, 2-2 2-2 xj y j x1 x2 xn min y 1 y 2 y m a 11 a 12 a 1 n a 21 a 22 a 2 n a m1 a m2 a mn max z c 1 c 2 c n max z = min b 1 b 2 b m 2-2,, 90 1 2-2, 2-3 2 2-3 2-3 x j yj x 1 x 2 b y1 1 2 8 y 2 4 0 16 y 3 0 4 12 c 2 3 max z = 2 x1 + 3 x2 min = 8 y1 + 16 y2 + 12 y3 x1 + 2 x2 8 4 x1 16 4 x2 12 x1, x2 0 y1 + 4 y2 2 2 y1 + 4 y3 3 y1, y2, y3 0,, 54

n max z = cj x j j = 1 n ai j x j j = 1 = bi, i = 1,2,, m xj 0, j = 1, 2,, n : n max z = cj x j j = 1 y i (2-13) n ai j x j bi, j = 1 i = 1, 2,, m n - ai j x j - bi, i = 1, 2,, m j = 1 x j 0, j = 1,2,, m y i (2-14) i = 1, 2,, m : m min = i = 1 bi y i m m ai j y i = 1 i = 1 m + i = 1 i + ( - bi y i ) y i, y i 0, i = 1, 2,, m m min = bi ( y i - y i ) i = 1 m i = 1 ( - ai j y i )cj, j = 1, 2,, n ai j ( y i - y i )cj, j = 1,2,, n (2-13) (2-14) yi = y i - y i, y i, y i 0, yi y i, m min = bi y i i = 1 m ai j y i cj, j = 1,2,, n i = 1 yi, i = 1, 2,, m,, 2-4 55

2-4 ( ) max z n 0 0 m = ( ) min n = m 0 0 3 min z = 2 x1 + 3 x2-5 x3 + x4 x1 + x2-3 x3 + x4 5 2 x1 + 2 x3 - x4 4 x2 + x3 + x4 = 6 x1 0 ; x2, x3 0; x4,, y1, y2, y3 ; 2-4,, 4. 2 max z= 5 y1 + 4 y2 + 6 y3 y1 + 2 y2 2 y1 + y3 3-3 y1 + 2 y2 + y3-5 y1 - y2 + y3 = 1 y1 0, y2 0, y3 (1 ) max z = C X ; A Xb; X0, min = Yb; Y AC; Y0, min = max ( - ) max( - ) = - Yb; - Y A- C; Y0, 56

min( - ) = - CX ; - A X- b; X0 min( - ) = max max = max z = C X ; A Xb; X0 ( 2) X, Y C XYb max z = C X ; A Xb; X0 X,, A Xb Y,, Y, Y, X, Y A XYb min = Yb; Y AC; Y0 Y AC Y A XC X C XY AXYb (3 ) ( ), () ( ), ( ) ( ) () min = - x1 x1 - x2 1 - x1 + x2 1 x1, x2 0 - x2 max z = y1 + y2 y1 - y2-1 - y1 + y2-1 y1, y2 0 ( 4) X^, Y^, C X^ = Y^b, X^, Y^ C X^ = Y^b, 2 : Y YbC X^, C X^ = Y^b, YbY^bY^, : X, C X^ = Y^bC X X^ 57

(5 ), ; X^, B C - CB B - 1 A0 Y^ AC, Y^ = CB B - 1 Y^, = Y^b = CB B - 1 b X^,, z = C Y^ = CB B - 1 b Y^b = CB B - 1 b= C X^ Y^ (6 ) X^, Y^ Y^ X S = 0 Y S X^ = 0, X^, Y^ max z = C X min = Yb A X + X S = b X, XS 0 C C = Y A - Y S Y A - Y S = C Y, Y S 0, z = ( Y A - Y S ) X = Y A X - Y S X (2-15), b = A X + X S, = Y ( A X + X S ) = Y A X + Y X S (2-16) Y S X^ = 0, Y^ X S = 0 ; Y^b = Y^ A X^ = C X^, 3 X^, Y^ X^, Y^, 3, C X^ = Y^ A X^ = Y^b (2-15 ), (2-16), Y^ X S = 0, Y S X^ = 0 (7 ) max z = C X ; A X + X S = b; X, X S 0 min = Yb; Y A - Y S = C; Y, Y S 0, 2-5 2-5 X B X N X S 0 C N - C B B - 1 N - C B B - 1 Y S1 - Y S2 - Y 58

Y S1 XB, Y S2 X N B, A = ( B, N) ; max z = CB X B + CN X N B XB + N X N + X S = b XB, X, X S 0 min = Yb Y B - Y S1 Y N - Y S1 = CB = CN Y, Y S1, Y S2 0 Y S = ( Y S1, Y S2 ) XB = B - 1 b (2-17) (2-18) CN - CB B - 1 N - CB B - 1 : Y = CB B - 1, (2-17), ( 2-18) 4 Y S1 = 0 - Y S2 = CN - CB B - 1 N max z = x1 + x2 - x1 + x2 + x3 2-2 x1 + x2 - x3 1 x1, x2, x3 0, X = ( 0, 0, 0) ; min = 2 y1 + y2 - y1-2 y2 1 y1 + y2 1 y1 - y2 0 y1, y2 0,, 5 min = 2 x1 + 3 x2 + 5 x3 + 2 x4 + 3 x5 x1 + x2 + 2 x3 + x4 + 3 x5 4 2 x1 - x2 + 3 x3 + x4 + x5 3 xj 0, j = 1, 2,, 5 y * 1 = 4/ 5, y * 2 = 3/ 5 ; z = 5 59

max z = 4 y1 y1 + 3 y2 + 2 y2 2 y1 - y2 3 2 y1 + 3 y2 5 y1 + y2 2 3 y1 + y2 3 y1, y2 0 y * 1, y * 2,,, ; x * 2 = x * 3 = x * 4 = 0 y1, y2 0;, x * 1 + 3 x * 5 = 4 2 x * 1 + x * 5 = 3 x * 1 = 1, x * 5 = 1; X * = (1, 0, 0, 0, 1 ) T ; * = 5 5 CB B - 1,, z = CB B - 1 b, CN - N Y = CB B - 1, Y? B {max z = C X A Xb, X0}, (2-12) y * i z * = CB B - 1 b= Y * b z * b = CB B - 1 = Y *, 2-1 1 1 ( 1-5 ), y * 1 = 1. 5, y * 2 = 0. 125, y * 3 = 0,, 1. 5 ; A 1kg, 0. 125 ; B 1kg, 2-1,,, ( 4, 2 ) ( 4, 2.5 ), z = 24 + 32. 5 = 15. 5, 1. 5 A 1kg,, 60

(4,2 ) ( 4. 25,1. 875 ), z = 2 4. 25 + 31. 875 = 14. 125 0. 125 B 1kg,, y * i i,, 1. 5,1 kg A 0. 125, 1kg B,,,, ;, 6 :, b,,, (2 ) (3 ),, :, cj - CB B - 1 Pj 0,,,,, max z = C X B, B = ( P1 A X = b X0 X B = ( x1, x2,, xm ), P2,, Pm ),, X B = B - 1 b B - 1 b, ( B - 1 b) i < 0,,, (1 ) x1, x2,, xm i = ci - zi = ci - CB B - 1 Pj = 0, i = 1, 2,, m (2 ) xm + 1,, xn j = cj - zj = cj - CB B - 1 Pj 0, j = m + 1,, n x l, xk,,,,, : (1 ), b,,, b,, 61

, (2 ) min{( B - 1 b) i ( B - 1 b) i < 0} = ( B - 1 b) l x i (3 ) xl, lj < 0( j = 1,2,, n), l j ( j = 1, 2,, n) lj 0, = min x k l j j cj - zj l j < 0 = ck - zk l k, (4 ) l k,, (1 )( 4) 6 min = 2 x1 + 3 x2 + 4 x3 x1 + 2 x2 + x3 3 2 x1 - x2 + 3 x3 4 x1, x2, x3 0, max z = - 2 x1-3 x2-4 x3 - x1-2 x2 - x3 + x4 = - 3-2 x1 + x2-3 x3 + x5 = - 4 xj 0, j = 1, 2,,5, 2-6 2-6 c j - 2-3 - 4 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 x4-3 - 1-2 - 1 1 0 0 x5-4 [ - 2 ] 1-3 0 1 c j - z j - 2-3 - 4 0 0 2-6, b, x5 62 : ( 2), min( - 3, - 4) = - 4 : ( 3), = min - 2-2, -, - 4-3 = - 2-2 = 1

x1-2, 2-7 2-7,, b, 2-8 2-7 cj - 2-3 - 4 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 x 4-1 0 [ - 5/ 2] 1/ 2 1-1/ 2-2 x 1 2 1-1/ 2 3/ 2 0-1/ 2 c j - z j 0-4 - 1 0-1 2-8 c j - 2-3 - 4 0 0 CB X B b x1 x2 x3 x4 x5-3 x 2 2/ 5 0 1-1/ 5-2/ 5 1/ 5-2 x1 11/ 5 1 0 7/ 5-1/ 5-2/ 5 c j - z j 0 0-3/ 5-8/ 5-1/ 5 2-8, b,, X * = (11/ 5, 2/ 5, 0, 0, 0) T y1 Y * = ( y * 1, y * 2 ) = ( 8/ 5, 1/ 5) : y2, (1 ),,,, (2 ),,,,,, (3 ),,,,, 7, i j, bi, cj, cj ; i j ; bi :, ;, 8 63

,,,,, B,,,, 2-9 2-9,, 7. 1 br, b r = br + br X B = B - 1 ( b+ b) b= (0,,br, 0,,0 ) T X B 0,,,, X B B - 1 B - 1 ( b+ b) = B - 1 b+ B - 1 b 0 br b bi 0 = = B - 1 b+ B - 1-1 rbr - i rbr - m rbr = br 0 br 0-1 r - i r - m r + - i rbr 0, i = 1, 2,, m - i rbr - bi, i = 1, 2,, m - i r > 0,br- bi/ - i r ; - i r < 0,br - bi/ - i r ; 64 max{ - bi/ - i r - i r > 0} br min i { - bi/ - i r - i r < 0} 1 1 b2 b2,

B - 1 b+ B - 1 b2 = 4 + 0. 5 b2 0 0 4 0. 25 0 0 2-0. 125 0 b2-4/ 0. 25 = - 16,b2-4/ 0. 5 = - 8,b2 2/ 0. 125 = 16 b2 [ - 8,16] ; b2 [8, 32] 7 1-5 1 1, 1. 5, 4,, B - 1 b 0 0. 25 0 4 0 B - 1 b = - 2 0. 5 1 0 = - 8 0. 5-0. 125 0 0 2 1-5, 2-10 2-10 c j 2 3 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 2 x1 4 + 0 1 0 0 0. 25 0 0 x 5 4-8 0 0 [ - 2 ] 0. 5 1 3 x2 2 + 2 0 1 0. 5-0. 125 0 c j - z j 0 0-1. 5-0. 125 0 2-10 b,2-11 2-11 c j 2 3 0 0 0 CB X B b x1 x2 x3 x4 x5 2 x 1 4 1 0 0 0. 25 0 0 x3 2 0 0 1-0. 25-0. 5 3 x 2 3 0 1 0 0 0. 25 c j - z j 0 0 0-0. 5-0. 75 4, 3, z * = 42 + 33 = 17 () 2-11 x3 = 2, 2 7. 2 cj cj (1 ) cj x j, j = cj - CB B - 1 Pj 65

j = cj m - i j y i i = 1 cj cj,, j = cj + cj - CB B - 1 Pj 0 cj + cj Y P j, cj Y P j - cj, cj (2 ) cr x r cr CB, cr cr, CB, ( CB + CB ) B - 1 A = CB B - 1 A + ( 0,,Cr,, 0 ) B - 1 A, cr cr, = CB B - 1 A + Cr ( r1, r2,, r n ) j = cj - CB B - 1 A - cr - r j, j = 1, 2,, n, j 0 cr max j - r j < 0, cr j/ - r j ; - r j > 0, cr j/ r j j = 1, 2,, n { j/ - r j - r j > 0} cr min j { j/ - r j - r j < 0} 8 1 1 1-5 x2 c2 c2,, c2 1-5 2-12 2-12 cj 2 3 + c2 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 2 x 1 4 1 0 0 0. 25 0 0 x 5 4 0 0-2 0. 5 1 3 + c 2 x 2 2 0 1 0. 5-0. 125 0 cj - zj 0 0-1. 5 - c 2 / 2 c 2 / 8-1/ 8 0 2-12 c2-1. 5/ 0. 5;c2 1 c2-1. 5 - c2/ 20 c2/ 8-1/ 80-3 c2 1 x2 c2 [0,4 ], 7. 3 i j i j, 9 1 1 66

,,, A, B 6kg, 3kg, 2 ; 5? : (1 ) x 3, P 3 = (2, 6, 3 ) T, x 3 3 = c 3 - CB B - 1 P 3 = 5 - (1. 5,0. 125,0 ) ( 2, 6, 3) T = 1. 25 > 0 (2 ) x 3 B - 1 P 3 = 0 0. 25 0-2 0. 5 1 0. 5-0. 125 0 2 6 3 = 1. 5 2 0. 25 (1 ), (2 )1-5, 2-13( a) 2-13(a) cj 2 3 0 0 0 5 C B X B b x 1 x 2 x 3 x 4 x 5 x 3 2 x 1 4 1 0 0 0. 25 0 1. 5 0 x 5 4 0 0-2 0. 5 1 [ 2] 3 x 2 2 0 1 0. 5-0. 125 0 0. 25 cj - zj 0 0-1. 5-0. 125 0 1. 25 b,, (3 ) x 3, x5,, 2-13 ( b), : x1 = 1, x2 = 1. 5, x 3 = 2 16. 5 2. 5 2-13( b) c j 2 3 0 0 0 5 CB X B b x1 x2 x3 x4 x5 x 3 2 x 1 1 1 0 1. 5-0. 125-0. 75 0 0 x 3 2 0 0-1 0. 25 0. 5 1 3 x 2 1. 5 0 1 0. 75-0. 1875-0. 125 0 c j - z j 0 0-0. 25-0. 4375-0. 625 0 10 1 1,, P 1 = (2, 5, 2 ) T, 4,?, x 1 x 1, x 1 x1 67

B - 1 P 1 = x 1 x1 2-14 0 0. 25 0-2 0. 5 1 0. 5-0. 125 0 2 5 2 = 1. 25 0. 5 0. 375 c 1 - CB B - 1 P 1 = 4 - (1. 5,0. 125,0 ) ( 2, 5, 2) T = 0. 375, 2-14 C B X B b x 1 x 2 x 3 x 4 x 5 2 x1 4 1. 25 0 0 0. 25 1 0 x 5 4 0. 5 0-2 0. 5 1 3 x 2 2 0. 375 1 0. 5-0. 125 0 c j - z j 0. 375 0-1. 5-0. 125 0 2-14 x 1, 2-15 2-15 C B X B b x 1 x 2 x 3 x 4 x 5 4 x 1 3. 2 1 0 0 0. 2 0 0 x5 2. 4 0 0-2 0. 4 1 3 x 2 0. 8 0 1 0. 5-0. 2 0 c j - z j 0 0-1. 5-0. 2 0 2-15,3. 2 ;, 0. 8 15. 2 :, 11 10 P 1 = ( 4, 5, 2) T, 4? 10, x 1 x1, B - 1 P 1 = 0 0. 25 0-2 0. 5 1 0. 5-0. 125 0 4 5 2 = 1. 25-3. 5 1. 375 x 1 c 1 - CB B - 1 P 1 = 4 - (1. 5, 0. 125, 0) ( 4, 5, 2 ) T = - 2. 625 1-15 x1, 2-16 68

2-16 C B X B b x 1 x 2 x 3 x 4 x 5 2 x 1 4 1. 25 0 0 0. 25 0 0 x 5 4-3. 5 0-2 0. 5 1 3 x 2 2 1. 375 1 0. 5-0. 125 0 c j - z j - 2. 625 0-1. 5-0. 125 0 2-16 x 1 x1, 2-17 2-17 CB X B b x 1 x2 x3 x4 x5 4 x 1 3. 2 1 0 0 0. 2 0 0 x 5 15. 2 0 0-2 1. 2 1 3 x 2-2. 4 0 1 0. 5-0. 4 0 c j - z j 0 0-1. 5 0. 4 0 2-17 x6 2-17x2 x6 x6,, 0 x 1 + x2 + 0. 5 x3-0. 4 x4 + 0 x5 = - 2. 4 - x2-0. 5 x3 + 0. 4 x4 + x6 = 2. 4 x2, 2-17, 2-18 2-18 C B X B b x 1 x 2 x 3 x 4 x 5 x 6 4 x 1 3. 2 1 0 0 0. 2 0 0 0 x 5 15. 2 0 0-2 1. 2 1 0 - M x6 2. 4 0-1 - 0. 5 [ 0. 4 ] 0 1 c j - z j 0 3 - M - 0. 5 M - 0. 8 + 0. 4 M 0 0 x4, x6, 2-19 2-19, x2, x5, 2-19,,0. 667 ;, 2. 667, 10. 67 69

2-19 c j 4 3 0 0 0 - M C B X B b x 1 x 2 x 3 x 4 x 5 x 6 4 x 1 2 1 0. 5 0. 25 0 0 0. 5 0 x 5 8 0 [3 ] - 0. 5 0 1-3 0 x 4 6 0-2. 5-1. 25 1 0 2. 5 cj - zj 0 1-1 0 0 - M + 2 4 x 1 0. 667 1 0 0. 33 0-0. 33 0 3 x2 2. 667 0 1-0. 167 0 0. 33-1 0 x 4 12. 667 0 0 1. 667 1 0. 83 0 cj - zj 0 0-0. 83 0-0. 33 - M + 3, 8 *,, ai j, bi, cj,,, : (1 ) t t = 0, ; (2 ), t ; (3 ) t, b b, ;, ; ; (4 ), t, ( 3 ), b, 8. 1 c 12 t0 max z( t) = ( 3 + 2 t) x1 x1 4 2 x2 12 3 x1 + 2 x2 18 x1, x2 0 + ( 5 - t) x2 70

max z( t) = ( 3 + 2 t) x1 + ( 5 - t) x2 x1 + x3 = 4 2 x2 + x4 = 12 3 x1 + 2 x2 + x5 = 18 x j 0, j = 1, 2,, 5 t = 0,, 2-20 2-20 c j 3 5 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 x3 2 0 0 1 1/ 3-1/ 3 5 x 2 6 0 1 0 1/ 2 0 3 x1 2 1 0 0-1/ 3 1/ 3 c j - z j 0 0 0-3/ 2-1 c 2-20, 2-21 2-21 cj 3 + 2 t 5 - t 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 x3 2 0 0 1 1/ 3-1/ 3 5 - t x 2 6 0 1 0 1/ 2 0 3 + 2 t x1 2 1 0 0-1/ 3 1/ 3 c j - z j 0 0 0-3/ 2 + 7 6 t - 1-2 3 t t, t 3/ 2 7/ 6 = 9, 4 0, 4 0, 0t9/ 7, ( 2, 6, 7 2, 0, 0) T t = 9/ 7 t > 9/ 7, 4 > 0, x4, 2-22 2-22 cj 3 + 2 t 5 - t 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 x 4 6 0 0 3 1-1 5 - t x 2 3 0 1-3/ 2 0 1/ 2 3 + 2 t x 1 4 1 0 1 0 0 0 0 9/ 2 0-5/ 2 cj - zj - 7 2 t + 1 2 t 71

t t 5/ 2 = 5, 5 0, 5 0, 9/ 7t5, ( 4, 1/ 2 3, 0, 6, 0) T t = 5 t > 5, 5 > 0, x5,, 2-23 2-23 cj 3 + 2 t 5 - t 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 0 x 4 12 0 2 0 1 0 0 x 5 6 0 2-3 0 1 3 + 2 t x 1 4 1 0 1 0 0 cj - zj 0 5 - t - 3-2 t 0 0 2-23 t, 2, 3 < 0, t5, ( 4, 0, 0, 12, 6 ) T 8. 2 b 13, t0, max z = x1 max z = x1 t = 0,, 2-24 2-24 + 3 x2 x1 + x2 6 - t - x1 + 2 x2 6 + t x1, x2 0 + 3 x2 x1 + x2 + x3 = 6 - t - x1 + 2 x2 + x4 = 6 + t x1, x2, x3, x4 0 cj 1 3 0 0 C B X B b x 1 x 2 x 3 x 4 1 x 1 2 1 0 2/ 3-1/ 3 3 x 2 4 0 1 1/ 3 1/ 3 c j - z j 0 0-5/ 3-2/ 3 B - 1 b= 2/ 3-1/ 3 1/ 3 1/ 3 - t t = - t 0 72

2-24, 2-25 2-25 c j 1 3 0 0 C B X B b x 1 x 2 x 3 x 4 1 x 1 2 - t 1 0 2/ 3-1/ 3 3 x 2 4 0 1 1/ 3 1/ 3 cj - zj 0 0-5/ 3-2/ 3 2-25, t t2, b0 0t2, ( 2 - t, 4, 0, 0) T t > 2, b1 < 0; x1,, 2-26 2-26 c j 1 3 0 0 C B X B b x 1 x 2 x 3 x 4 0 x4-6 + 3 t - 3 0-2 1 3 x 2 6 - t 1 1 1 0 c j - z j - 2 0-3 0 2-26, t > 6, ; 2t6, ( 0, 6 - t, 0, - 6 + 3 t) T 2. 1 (1 ) max z = 6 x1-2 x2 + 3 x3 2 x1 - x2 + 2 x3 2 x1 + 4 x3 4 x1, x2, x3 0 (2 ) min z = 2 x1 + x2 3 x1 + x2 = 3 4 x1 + 3 x2 6 x1 + 2 x2 3 x1, x2 0 2. 2, 2-27, 73

2-27 c j 3 5 4 0 0 0 CB XB b x1 x2 x3 x4 x5 x6 x 2 8/ 3 2/ 3 1 0 1/ 3 0 0 x5 14/ 3-4/ 3 0 5-2/ 3 1 0 x 6 20/ 3 5/ 3 0 4-2/ 3 0 1 cj - zj - 1/ 3 0 4-5/ 3 0 0 x 2 15/ 41 8/ 41-10/ 41 x3-6/ 41 5/ 41 4/ 41 x 1-2/ 41-12/ 41 15/ 41 cj - zj 2. 3 (1 ) min z = 2 x1 + 2 x2 + 4 x3 2 x1 + 3 x2 + 5 x3 2 3 x1 + x2 + 7 x3 3 x1 + 4 x2 + 6 x3 5 x1, x2, x3 0 (3 ) min z = n m n ci j x i j i = 1 j = 1 x i j j = 1 m x i j i = 1 x i j 0 = i, i = 1,, m = bj, j = 1,, n 2. 4,? ( 2) max z = x + 2 x2 + 3 x3 + 4 x4 - x1 + x2 - x3-3 x4 = 5 6 x1 + 7 x2 + 3 x3-5 x4 8 12 x1-9 x2-9 x3 + 9 x4 20 x1 x2 0, x3 0, x4 n ( 4) max z = cj x j j = 1 n i j x j bi, i = 1,, m1 m j = 1 n i j x j = bi, i = m1 + 1, m1 + 2,, m j = 1 x j 0, j = 1,, n1 n x j, j = n1 + 1,, n (1 ), ; (2 ), ; (3 ), 2. 5 1 max z1 ( y * 1,, y * m ) 74 n = cj x j j = 1 n i j x j bi, i = 1, 2,, m j = 1 x j 0, j = 1, 2,, n

ki 2, 2. 6 max z2 n = ci x j j = 1 n i j x j bi j = 1 xj 0, j = 1, 2,, n max z2 max z1 + ki, i = 1,2,, m m + ki y * i i = 1 max z = c1 x1 + c2 x2 + c3 x3 11 21 x1 + 1 2 x2 2 2 + 13 x3 + 1 23 0 x4 + 0 1 xj 0, j = 1,,5, 2-28, : (1 ) 11, 12, 13, 2 1, 22, 2 3, b1, b2 ; (2 ) c1, c2, c3 x5 = b1 b2 2-28 X B b x1 x2 x3 x4 x5 x3 3/ 2 1 0 1 1/ 2-1/ 2 x 2 2 1/ 2 1 0-1 2 c j - z j - 3 0 0 0-4 2. 7 max z = 2 x1 + x2 + 5 x3 + 6 x4 2 x1 + x3 + x4 8 2 x1 + 2 x2 + x3 + 2 x4 12 x j 0, j = 1,, 4 y * 1 = 4, y * 2 = 1,, 2. 8 (1 ) min z = x1 + x2 (2 ) min z = 3 x1 + 2 x2 + x3 + 4 x4 2 x1 + x2 4 x1 + 7 x2 7 x1, x2 0 2 x1 + 4 x2 + 5 x3 + x4 0 3 x1 - x2 + 7 x3-2 x4 2 5 x1 + 2 x2 + x3 + 6 x4 15 x1, x2, x3, x4 0 y1 y2 75

2. 9 max z = - 5 x1 + 5 x2 + 13 x3 - x1 + x2 + 3 x3 20 12 x1 + 4 x2 + 10 x3 90 x1, x2, x3 0,,? (1 ) 20 30; (2 ) 90 70; (3 ) x3 13 8; (4 ) x1-1 12 0 5 ; (5 ) 2 x1 + 3 x2 + 5 x3 50; (6 ) 10 x1 + 5 x2 + 103 100 2. 10,,, A, B, C, 2-29 : 2-29 / A 8 2 10 300 B 10 5 8 400 C 2 13 10 420 / 3 2 2. 9 (1 ),? (2 ), B, 60, 1. 8, B? (3 ),, A - 12 ; B - 5 ; C - 10, 2. 1 ; A - 4, B - 4, C - 12, 1. 87 A, B, C,? (4 ),, A - 9, B - 12, C - 4, 4. 5,? 76 2. 11 t (1 ) max z( t) = (3-6 t) x1 + (2-2 t) x2 + (5-5t) x3 ( t0) x1 + 2 x2 + x3 430 3 x1 + 2 x3 460 x1 + 4 x2 420 x1, x2, x3 0

(2 ) max z( t) = (7 + 2 t) x1 + (12 + t) x2 + (10 - t) x3 ( t0) x1 + x2 + x3 20 2 x1 + 2 x2 + x3 30 x1, x2, x3 0 (3 ) max z( t) = 2 x1 + x2 ( 0t25) x1 10 + 2 t x1 + x2 25 - t x2 10 + 2 t x1, x2 0 (4 ) max z( t) = 21 x1 + 12 x2 + 18 x3 + 15 x4 ( 0t59) 6 x1 + 3 x2 + 6 x3 + 3 x4 30 + t 6 x1-3 x2 + 12 x3 + 6 x4 78 - t 9 x1 + 3 x2-6 x3 + 9 x4 135-2 t x j 0, j = 1,2,3,4 77

3,,, 1,,,,,, m A i, i = 1, 2,, m, ( ) ai, i = 1, 2,, m, n B j, j = 1, 2,, n, bj, j = 1, 2,, n, Ai Bj ( )ci j,, 3-1, 3-2 3-1 3-2 1 2 n 1 2 n 1 a1 2 a 2 m b 1 b 2 b n a m 1 c 11 c 12 c 1 n 2 c 21 c 22 c 2 n m cm1 cm2 cm n xi j A i B j,,, m min z = m i = 1 xi j i = 1 n j = 1 ci j x i j = bj, j = 1, 2,, n ( 3-1) n xi j j = 1 = ai, i = 1, 2,, m ( 3-2) xi j 0 mn, ( m + n), 78

u1 u2 um v1 v2 x11 x12 x1 n x 21 x22 x2 n xm1 xm2 x m n 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 vn 1 1 1 m n xi j P i j, i m + j 1, Pi j = ( 01010) T = ei + em + j, : n bj = xi j j = 1 m i = 1 n j = 1 n = x i j j = 1 m i = 1 m = ai m + n - 1 m + n - 1,,, i = 1 2, : (1 ) ( mn) m + n - 1 (2 ),,,, (3 ), (4 ) ( 2), ( 3), 1 : A1 7, A2 4, A3 9 : B1 3, B2 6, B3 5, B4 6 3-3,,, 3-3, 3-4 79

3-3 B 1 B 2 B 3 B 4 A 1 3 11 3 10 A 2 1 9 2 8 A3 7 4 10 5 3-4 B1 B2 B3 B4 A 1 7 A2 4 A3 9 3 6 5 6 2. 1 m i = 1 ai = n j = 1 bj = d x i j 0, i = 1,, m, j = 1,, n 0x i j min( aj, bj ),, : ( Vogel) 1.,, 1 : 3-3 1, A2 B1 a2 > b1, A2 B1, 1 3-4 ( A2, B1 ) 33-5 3-3 B1 3-6 : 3-6 2, A2 3-7, 3-8 1 B3, 80

3-5 B 1 B 2 B 3 B 4 A 1 7 A 2 3 4 A3 9 3 6 5 6 3-6 B1 B2 B3 B4 A1 3 11 3 10 A 2 1 9 2 8 A3 7 4 10 5 3-7 B 1 B 2 B 3 B 4 A 1 7 A2 3 1 4 A 3 9 3 6 5 6 3-8 B 1 B 2 B 3 B 4 A 1 3 11 3 10 A2 1 9 2 8 A 3 7 4 10 5 : 3-8 3;,,, 3-9 86 3-9 B 1 B 2 B 3 B 4 A 1 4 3 7 A 2 3 1 4 A 3 6 3 9 3 6 5 6, : (1 ),, 81

,,,, m n, ( n + m),,, ( m + n - 1 ) ( m + n - 1) (2 ) ( m + n - 1 ) xi j 1 1 Pi j 1 1 = ei 1 + em + j 1 xi j 1 1, i1 j1, ei 1 em + j 1, Pi 1 j 1,, ( m + n - 1) ( m + n - 1) ( m + n - 1),, 2. 4 2. :,,,,,,,, : : 3-3,, 3-10 3-10 B1 B2 B3 B4 A 1 3 11 3 10 0 A 2 1 9 2 8 1 A 3 7 4 10 5 1 2 5 1 3 :, 3-10 B2 B2 4, A3 B2 3-11B2 3-12 82

3-11 B 1 B 2 B 3 B 4 A 1 7 A2 4 A 3 6 9 3 6 5 6 : 3-12, 1 3-13 3-12 B 1 B 2 B 3 B 4 A 1 3 11 3 10 0 A 2 1 9 2 8 1 A 3 7 4 10 5 2 2 1 3 3-13 B 1 B 2 B 3 B 4 A 1 5 2 7 A 2 3 1 4 A3 6 3 9 3 6 5 6 :, 2. 2 ( ) ci j - CB B - 1 Pi j, i,, jn, ci j - CB B - 1 Pi j 0, 1., 3-13,, 90,, 83

3-1 ( a), ( b), (c) 3-1 ( m + n - 1 ) ( ) ( ) Pi j, i, jn Pi j = ei + em + j = ei + em + k - em + k + el - el + em + s - em + s + eu - eu + em + j = ( ei + em + k ) - ( el + em + k ) + ( el + em + s ) - ( eu + em + s ) + (eu + em+ j ) = Pi k - Pl k + Pl s - Pu s + Pu j Pi k, Pl k, Pl s, Pu s, Pu j B ( 3-2) : 3-9,, ( A1, B1 ), A1 1 B1, : ( A1, B3 )1, ( A2, B3 ) 1, ( A2, B1 )1, ( A1, B1 ), 3-14 3-2 3-14 ( + 1)3 + ( - 1)3 + ( + 1)2 + ( - 1)1 = 1 () 1( A1, B1 ),,, 3-15 84

3-15 (11) ( 11 ) - (13) - ( 23 ) - (21) - ( 11 ) 1 (12) ( 12 ) - (14) - ( 34 ) - (32) - ( 12 ) 2 (22) ( 22 ) - (23) - ( 13 ) - (14) - ( 34 ) - (32) - ( 22) 1 (24) ( 24 ) - (23) - ( 13 ) - (14) - ( 24 ) - 1 (31) ( 31 ) - (34) - ( 14 ) - (13) - ( 23 ) - (21) - ( 31) 10 (33) ( 33 ) - (34) - ( 14 ) - (13) - ( 33 ) 12,, 2. 3 2.,, u1, u2,, um ; v1, v2,, vn m + n B x a ( m + n)( m + n) xa ca = 0, CB B - 1 = ( u1, u2,, um ; v1, v2,, vn ) xi j Pi j = ei + em + j, CB B - 1 Pi j = ui + vj i j = ci j - CB B - 1 Pi j = ci j - ( ui + vj ) 0 ci j - ( ui + vj ) = 0, i, jb, 1 x23, x34, x21, x32, x13, x14 xa, : xa ca - u1 = 0 ca = 0 u1 = 0 x23 c23 - ( u2 + v3 ) = 0 2 - ( u2 + v3 ) = 0 x34 c34 - ( u3 + v4 ) = 0 5 - ( u3 + v4 ) = 0 x21 c21 - ( u2 + v1 ) = 0 1 - ( u2 + v1 ) = 0 x32 c32 - ( u3 + v2 ) = 0 4 - ( u3 + v2 ) = 0 x13 c13 - ( u1 + v3 ) = 0 3 - ( u1 + v3 ) = 0 x14 c14 - ( u1 + v4 ) = 0 10 - ( u1 + v4 ) = 0 7 u1 ui, vj = 0 u2 = - 1, u3 = - 5, v1 = 2, v2 = 9, v3 = 3, v4 = 10 i j = ci j - ( ui + vj ), i, jn 1 : 3-9, 3-16 3-9 85

, 3-16 3-16 B1 B2 B3 B4 A 1 3 10 A 2 1 2 A 3 4 5 : 3-16, ui, vj, 3-17 3-17 B 1 B 2 B 3 B 4 u i A 1 3 10 0 A2 1 2-1 A 3 4 5-5 vj 2 9 3 10 u1 = 0, ui + vj = ci j, i, jb ui, vj 3-17, u1 = 0, u1 + v3 = 3 v3 = 3, u1 + v4 = 10 v4 = 10; v4 = 10, u3 + v4 = 5 u3 = - 5, ui, vj : i j = ci j - ( ui + vj ) i, jn 11 = c1 1 - ( u1 + v1 ) = 3 - ( 0 + 2 ) = 1 12 = c1 2 - ( u1 + v2 ) = 11 - (0 + 9) = 2 3-17,, 3-18 3-18 B 1 B 2 B 3 B 4 u i A 1 3 1 2 11 0 3 10 0 0 1 9 2 8 A2 0 1 0-1 - 1 A 3 7 10 0 4 12 10 5 0-5 v j 2 9 3 10 86

3-18, 2. 3,,, 3-18 (2, 4 ),, 3-19 3-19 A 1 A 2 3 A 3 B1 B2 B3 B4 6 4 ( + 1) 3 ( - 1) 1 ( - 1) ( + 1 ) 3 6 5 6 3 7 4 9 (2,4 ) ( - 1 ) = min ( 1, 3) = 1( ),,, 3-20 3-20 B 1 B 2 B 3 B 4 A1 5 2 7 A 2 A 3 3 6 1 3 4 9 3 6 5 6 3-20,, 3-21, 3-20 85 3-21 B1 B2 B3 B4 A 1 0 2 A 2 2 1 A3 9 12 87

2. 4 1. 2. 1,? 1 3. 3 ( ) 0, 3-21 ( 1, 1) 0, 1 3-20 ( 1, 1 ), ( 1, 1) + - ( 1, 4 ) - - ( 2, 4 ) + - ( 2, 1) - - ( 1, 1) + = min(2,3 ) = 2, 3-22 3-22 B 1 B 2 B 3 B 4 A 1 2 5 7 A 2 1 3 4 A3 6 3 9 3 6 5 6 2., 0, : (1 ), ( i, j), Ai B j, ( m + n - 1 ) 0 3-23, 3-24, 2, B2, 6, A3 6 ( 3, 2 ) 6, 3-24 B2 A3 3-23 ( 1, 2), ( 2, 2), ( 3, 3), ( 3, 4)0 3-23 B 1 B 2 B 3 B 4 A1 7 A2 4 A 3 3 6 9 3 6 5 6 88

3-24 B 1 B 2 B 3 B 4 A 1 3 11 4 5 A 2 7 7 3 8 A3 1 2 10 6 (2 ), ( - 1 ), 0,,, ( - 1 ) 0, = 0 3,, m i = 1 ai = bj,, m min z = i = 1 m i = 1 n j = 1 n j = 1 ai > bj ci j x i j n j = 1 n x i j ai, ( i = 1, 2,, m) j = 1 m x i j = bj, ( j = 1, 2,, n) i = 1 xi j 0, x i, n + 1 Ai, : n j = 1 n + 1 xi j + x i, n + 1 = j = 1 xi j = ai, ( i = 1,, m) m x i j = bj ( j = 1,, n) i = 1 m xi, n + 1 i = 1 m = ai i = 1 n - bj = bn + 1 j = 1 89