Ps22Pdf

( ) 158 10, :,,,, ( MBA),,, ( CIP) /. :, 1999 ISBN 7302037884.... 022 CIP ( 1999) 63321 : (, 100084) ht tp: / / w ww. tup. tsinghua. edu. cn : : : 7871092 1/ 16: 18. 5: 456 : 2000 1 1 2000 1 1 : ISBN 7302037884/ T P2129 : 00016000 : 21. 00

20,,, :,, ; ;, ;,, ;,,,,,,,,,,, 20 70 20, 150,,,, 20 1991 10, 1993 1995 1997,,,,,,,,,,,,,, 7,, 20,,

,,,,,, :,,,,,,,,,, 1997 9

,,,,, 20 40,,,,,,,,,, 10, 9, : ; ; ; ; ;,,,,,,,,,,, 96,,,, ( 1, 3, 5, 6 ) ( 4, 7,

8, 9, 10 ) ( 1, 2 ),,,,,

1 1 1. 11 1. 23 1. 34 2 6 2. 16 2. 27 2. 313 2. 423 2. 531 2. 636 2. 746 2. 8DEA 52 2. 956 64 3 71 3. 171 3. 272 3. 375 3. 401 80 3. 587 3. 690 94 4 99 4. 199 4. 2102 4. 3105 4. 4107 4. 5115 117

5 120 5. 1120 5. 2121 5. 3129 5. 4139 5. 5143 5. 6148 151 6 155 6. 1155 6. 2159 6. 3163 6. 4171 6. 5183 187 7 192 7. 1192 7. 2194 7. 3194 7. 4197 7. 5200 7. 6202 204 8 206 8. 1206 8. 2206 8. 3214 8. 4217 220 9 223 9. 1223 9. 2224 9. 3M M 1 226 9. 4M M C 228 9. 5230

9. 6232 235 10 236 10. 1236 10. 2236 10. 3238 10. 4242 10. 5246 10. 6252 256 259 1259 2272 283

1 1. 1 1914, ( Lanchest er ). 1917, ( Erlang),. 20 20. 20 30. ( G. B. Dant zing) 1947,,. 1939 (. B. KA H TOP OB ),,,. 20 30,.,,,. ( operational research ),, O. R., operat ions research,. O. R. :,,. O. R.,,.,, ;, ; ;.,,, 47% 29%., 400%.,.,.,,.,. ( RAN D),.,,. 20 50,,, ; 20 60,. 20 50,,. 1957, ; 1958., 1

,,.,. 20 60,. 1965 ; 1970 ; 70,, ; ; ; 70,.,,.,,.,.,.. ( P. M. Morse) ( G. E. Kimball) :,.,,,.,.,.,.,. :,,,.,..,. :,,. ( 1948 ), ( 1952 ) ( 1956 ) ( 1957 ). 1986, 38. 1980. 1959, ( IF ORS),, 1982., ( EU RO ) 1976, ( AP ORS) 1985., ( T omlinson) : ( 1),. ( 2),. ( 3),. ( 4),,. ( 5),,. ( 6). 2

1. 2,.. 1.,.,,.,.,,.,,,,,. 2...,.,,.,,.,,,. : ( 1) ; ( 2) ; ( 3) ; ( 4).,,,.,, ;,.,,. ;. 3.,,.,.,,.,,.,,,.,. 4.,,,,.,.,,,., 3

,,.,,.,,,,,.,,.,,, :. : ; :. : ( 1),., ( )., ( ),,,, ( ), ( ). ( 2),,. ( ),,,,. ( 3)..,,.,,,,. ( 4). 50,,.,,.,,,.,. 1. 3,,,.,,., 4

; ( ) ;, ;,,.,. 1. 1 1. 1, ( )..,.,,,,,.,,.,. 5

2 2. 1, ( ),, ;,,.,.,. 20 30,,.. 1947,.,.. 1961,,. 1., 2. 1.,? 2. 1 2 3 24 3 2 26 ( / ) 4 3.. x 1 x 2, x 1, x 2 : Z= 4x 1+ 3x2. 2x 1 + 3x 2 24 3x 1 + 2x 2 26 x 1, x 2 0, maxz= 4x 1+ 3x 2 s. t. subject to. s. t. 2x 1+ 3x 224 3x 1+ 2x 226 x 1, x 20. 2, 3 A 1, A 2, A 3, A 1 = 60 6

, A 2= 40, A 3= 60, 4 B 1, B 2, B 3, B 4, : B1= 30, B 2= 50, B3 = 40, B 4= 40. 2. 2.,? 2. 2 ( : / ) B 1 B 2 B 3 B 4 A1 5 6 10 3 60 A2 4 1 9 7 40 A 3 4 2 3 8 60 30 50 40 40,. A B j x j ( = 1, 2, 3, j = 1, 2, 3, 4), : min Z = 5x1 1 + 6x1 2 + 10x 13 + 3x 14 + 4x 21 + x 22 + 9x 23 + 7x 24 + 4x 31 + 2x 32 + 3x 33 + 8x3 4, x 1 1 + x 12 + x 1 3 + x 14 = 60 x 2 1 + x 22 + x 2 3 + x 24 = 40 x 3 1 + x 32 + x 3 3 + x 34 = 60 s. t. x 1 1 + x 21 + x 3 1 = 30 x 1 2 + x 22 + x 3 2 = 50 x 1 3 + x 23 + x 3 3 = 40 x 1 4 + x 24 + x 3 4 = 40 x j 0 ( = 1, 2, 3, j = 1, 2, 3, 4). 1 2 : ( 1) ( 1 x, 2 x j ), ; ( 2),.,.,.,.,,,,. DEA. 2. 2. 1 2. 2,, ; 7

,, = ;,., : max( min ) Z = c1x 1 + c2x 2 + + cx, ( 2. 1) s. t. a 1 1x 1 + a 12x 2 + + a 1x ( =, ) b1 a 2 1x 1 + a 22x 2 + + a 2x ( =, ) b2 a m1x 1 + a m2x 2 + + am x ( =, ) bm x 1, x 2,, x 0., max Z = s. t. cj x j, j = 1 aj x j = b ( = 1, 2,, m) j = 1 x j 0 ( j = 1, 2,, ). ( 2. 2) ( 2. 3) b1 a 1j x 1 b = b2, P j = a 2j, X = x 2, C = ( c1, c2,, c), A = bm a mj a1 1 a 12 a 1 a2 1 a 22 a 2 = ( P 1, P 2,, P ), 0 = am 1 a m2 a m, : : x m max Z = CX, s. t. P j x j = b j = 1 x j 0 ( j = 1, 2,, ). max Z = CX, AX = b X 0. 0 0. A, b, C, X., : ( 1) A rank( A) = m, 0< m<.,,,. ( 2) b0. b< 0, - 1.. ( 1), min Z= CX. 8 0

Z = - Z, max Z = - CX. ( 2). - = ( 0). + = ( 0). 0. x k, x k= x k - x k, x k0, x k0 31. 1 max Z = 4x 1 + 3x2, s. t. 2x 1 + 3x 2 24 3x 1 + 2x 2 26 x 1, x 2 0. x 3, x 4, : max Z = 4x 1 + 3x 2 + 0x 3 + 0x 4, s. t. 4.. 2x 1 + 3x 2 + x 3 = 24 3x 2 + 2x 2 + x 4 = 26 x 1, x 2, x 3, x 4 0. min Z = - x 1 + 2x 2-3x 3, s. t. x 1 + 2x 2 + 3x 3 7 - x 1 + x 2 - x 3-2 - 3x 1 + x 2 + 2x 3 = 5 x 1, x 3 0, x 2. Z = - Z, max Z = x 1-2( x 2 - x 2 ) + 3x 3 + 0x 4 + 0x5, s. t. 2. 2. 2 x 1 + 2( x 2 - x 2 ) + 3x 3 + x 4 = 7 x 1 - ( x 2 - x 2 ) + x 3 - x 5 = 2-3x 1 + ( x 2 - x 2 ) + 2x 3 = 5 x 1, x 2, x 2, x 3, x 4, x 5 0. max Z = cj x j, ( 2. 4) j = 1 9

s. t. a j x j = b= 1, 2,, m j = 1 x j 0j = 1, 2,,. : ( 2. 5) ( 2. 6) X= ( x 1, x 2,, x ) T : ( 2. 4).. ( 2. 5) ( 2. 6) : A ( 2. 5) m, rank( A) = m, B A mm ( B 0), B. : B, B m. A B, A ( - m). : P j x j ;. : 0, ( 2. 5). : ( 2. 6).,. C m. : ( 2. 4),. :, ;.,. 2. 1. 2. 2. 3,. ( 1) 2. 2. 1. 1. 2. 1 :,.,, 2. 2, O Q 1 Q 2 Q 3. :, Z, 2. 2. : Z, Q 2 ( 6, 4), Z, Z = 36. 2. 1, Q 2, X = ( 6, 4) T, Z = 36.. 1 Z = 4x 1+ 6x 2,, 2. 2 Q 3Q 2.. 10

max Z = x 1 + x 2, s. t. x 1 + 2x2 4 x 1, x 2 0. 2. 3.. max Z = x 1 + x 2, x 1 + x 2 3 s. t. x 1 + 2x2 8 x 1, x 2 0. 2. 4,. 2. 3 2. 4 ( 2),, ( ) ( )., :,. 2. 2. 4,. : K E, X ( 1), X ( 2 ) K ( X ( 1) X ( 2) ) X = X ( 1 ) + ( 1- ) X ( 2 ) K ( 01), K. : X ( 1), X ( 2),, X ( k ) E k, 1, 2,, k( 0 1, = 1, 2,, k; = 1) X = 1X ( 1) + 2X ( 2 ) + + kx ( k), X X ( 1), X ( 2),, X ( k). : K, X K ; X ( 1 ) K, X ( 2) K X = X ( 1 ) + ( 1- ) X ( 2 ) ( 01), X K. 1,. D = {X AX= b, X0}. X ( 1) D, X ( 2) D X ( 1 ) X ( 2), AX ( 1) = b, X ( 1) 0, AX ( 2) = b, X ( 2) 0. X X ( 1) X ( 2), 01, 11

X= X ( 1) + ( 1- ) X ( 2) 0, AX = A[ X ( 1 ) + ( 1- ) X ( 2) ] AX= b. X D, D. 2 X= ( x 1, x 2,, x ) T. ( 1). = AX ( 1) + ( 1- ) AX ( 2) = b+ ( 1- ) b= b, X ( 2) X k, P 1, P 2,, P k, rank ( A) = m, km. k= m,, X = ( x 1, x 2,, x k, 0,, 0) T ; k< m,, ( - k) ( m- k) P 1, P 2,, P k ( ). 3X., X, :, ;,. [ 3],. K, XK, K.. 4,. X ( 1), X ( 2),, X ( k), X ( 0) D Z = CX ( 0). X ( 0),. X ( 0), X ( 0 ) X ( 1), X ( 2),, X ( k), k X ( 0) = = 1 X ( ) 1, ( = k CX ( 0) = = 1 k 1, 2,, k), CX ( ). CX ( m) = max( C X ( 1 ), C X ( 2),, C X ( k) ), k CX ( 0 ) = = 1 C X ( ) k C X ( 0) C X ( m)., C X ( 0), C X ( 0 ) C X ( m ), C X ( 0) = C X ( m). X ( m ) Z., : ( 1),. = 1 = 1 C X ( m ) = C X ( m), = 1. ( 2), ( C m ). ( 3),.,,,. 12

m,,.,, ( ),. 2. 3 2. 3. 1 : max Z = CX, AX = b s. t. X 0., B, A ( B, N ). B= ( P 1,, P m ). B X B = ( x 1, x 2,, x m) T ; N = ( P m+ 1, P m + 2,, P ), X N = ( x m + 1, x m + 2,, x ) T. X = X B X N C= ( CB, CN ), CB X B, CN X N.. max Z = CX = ( CB, CN ) X B X N, ( B, N ) X B X N X B, X N 0. max Z = CB XB + CN XN, ( 2. 7) ( 2. 8) B - ( 2. 7), X N = 0, X B = B - 1, = b BX B + N XN = b X B, XN 0. ( 2. 8) ( 2. 9) X B = B - 1 b - B - 1 N XN, ( 2. 10) Z = CBB - 1 b - ( CBB - 1 N - CN ) X N. ( 2. 11) 1 b, X = Z= CBB - 1 b. CBB - 1 B- CB = 0, XB XN = Z= CBB - 1 b - ( CBB - 1 B - CB) XB - ( CBB - 1 N - CN ) X N B - 0 1 b = CBB - 1 b - ( CB B - 1 A - C) X. ( 2. 12) ( 2. 10) ( 2. 11) :. 13

X B + B - 1 NXN = B - 1 b Z + ( CBB - 1 N - CN ) X N = CBB - 1 b, 2. 3, B, T ( B). ( 2. 13) ( 2. 14) 2. 3 XB X N B - 1 b I B - 1 N CBB - 1 b 0 CBB - 1 N- CN N = CBB - 1 N - CN, = CBB - 1 A- C ( 2. 12) ( 2. 13) ( 2. 14), a 1m + 1 B - 1 N = Z = CBB - 1 b - N X N = CBB - 1 b - X. a 2m + 1 = ( 0, N ), a 1, m + 2 a 1, a 2, m + 2 a 2, a mm + 1 a m, m + 2 a m,, B - 1 b = b 1 b, 2 b m CB B - 1 N - CN = ( m+ 1, m + 2,, ), CBB - 1 b = b 0. ( 2. 13) ( 2. 14) : x 1 + a 1, m + 1x m+ 1 + + a 1kx k + x 2 + a 2, m + 1x m+ 1 + + a 2kx k + x m + a 1x = + a 2x = b 1 b 2 + a m, m + 1x m+ 1 + + a m kx k + + a mx = b m b 0. Z + m+ 1x m + 1 + m+ 2x m + 2 + + x =, 2. 3 T ( B) 2. 4. 2. 4 cj c1 c2 cm cm+ 1 c CB XB b x 1 x 2 x m x m+ 1 x c1 x 1 b 1 1 0 0 a 1, m+ 1 a 1 c 2 x 2 b 2 0 1 0 a 2, m+ 1 a 2 cm x m b m 0 0 1 a m, m+ 1 a m Z b 0 0 0 0 m+ 1 2. 4 2. 3,, b 0., Z = b m 0 = cb., m,, 14

2. 4,.,., x j m j = CB B - 1 P j - Cj = ca j - cj ( j = 1, 2,, )., T ( B), XB = ( x 1, x 2,, x m) T ( 0, 0,, 0), m I. 2. 3. 2 1. 5 max Z = 4x 1 + 3x 2, s. t. 2x 1 + 3x2 24 3x 1 + 2x2 26 x 1, x 2 0, x 3, x 4, max Z = 4x 1 + 3x 2 + 0x 3 + 0x 4, s. t. 2x 1 + 3x 2 + x 3 = 24 3x 2 + 2x 2 + x 4 = 26 x 1, x 2, x 3, x 4 0. :,., B1= ( P 3, P 4) = I, X B 1= ( x 3, x 4) T, CB 1= ( 0, 0), B - 1 1 = I, 0= B - 1 1 A= A, b= B - 1 1 b= b, = CB 1B - 1 1 A- C= - C, b0= CB 1B - 1 1 b= 0, 2. 5. 2. 5 cj 4 3 0 0 CB XB b x 1 x 2 x 3 x 4 0 x 3 24 2 3 1 0 0 x 4 26 3 2 0 1 Z 0-4 - 3 0 0 j,,. 2. 5, X ( 1) = ( x 1, x 2, x 3, x 4) T = ( 0, 0, 24, 26) T, Z ( 1) = 0. B1?,. :. x j j = CBB - 1 P j - Cj, : ( 1) j 0, B,, (, m+ k= 0, ). ( 2) s< 0 ( m+ 1s), B - 1 P s= ( a1 s, a 2s,, 15

a ms) T 0,,,. ( 3) j < 0 ( m+ 1j ), B,,. 2. 5, 1< 0, 2< 0,, x 1 x 2,. B1,. :. ( 1) x s: s= min {j j < 0, 0j }. ( 2) x r : x j 0 ( j = 1, 2,, ), x s.,., = min = b a a s> 0 = b r s a, x r, a r s. r s ( 3) ar s,. x s a 1s a 2s 0 0 a r s 1 r a m s 0. X B x r x s, B = ( P 1,, P r - 1, P s, P r + 1,, P m) T ( B ).,,,., 2. 5, s= min{j 1= - 4, 2= - 3}= 1, x 1. = min = b a a s> 0 = {24/ 2, 26/ 3}= 26/ 3, x 4, x 1 s x 4 a 21= 3, 2. 6. 2. 6 cj 4 3 0 0 CB XB b x 1 x 2 x 3 x 4 0 x 3 24 2 3 1 0 12 0 x 4 26 [ 3] 2 0 1 26/ 3 Z 0-4 - 3 0 0 j 0 x 3 20/ 3 0 [ 5/ 3] 1-2/ 3 4 4 x 1 26/ 3 1 2/ 3 0 1/ 3 13 Z 104/ 3 0-1/ 3 0 4/ 3 j X ( 2 ) = ( 26/ 3, 0, 20/ 3, 0) T, Z ( 2) = 104/ 3., x 2, x 3,, 2. 7. 16

2. 7 cj 4 3 0 0 CB XB b x 1 x 2 x 3 x 4 3 x 2 4 0 1 3/ 5-2/ 5 4 x 1 6 1 0-2/ 5 3/ 5 Z 36 0 0 1/ 5 6/ 5 j,, X = X ( 3 ) = ( 6, 4, 0, 0) T, Z = Z ( 3 ) = 36. x 3, x 4,, x 1= 6, x 2= 4, Z = 36. 6: max Z = 3x 1 + x 2, x 1 + x 2 4 - x 1 + x 2 2 s. t. 6x 1 + 2x 2 18 x 1, x 2 0. max Z = 3x 1 + x 2 x 1 + x 2+ x 3 = 4 - x 1 + x 2 + x 4 = 2 s. t. 6x 1 + 2x 2 + x 5= 18 x 1, x 2, x 3, x 4, x 5 0. 2. 8. 2. 8 cj 3 1 0 0 0 CB XB b x 1 x 2 x 3 x 4 x 5 0 x 3 4 1 1 1 0 0 4 0 x 4 2-1 1 0 1 0-0 x 5 18 [ 6] 2 0 0 1 3 Z 0-3 - 1 0 0 0 j 0 x 3 1 0 2/ 3 1 0-1/ 6 0 x 4 5 0 4/ 3 0 1 1/ 6 3 x 1 3 1 1/ 3 0 0 1/ 6 Z 9 0 0 0 0 1/ 2 j X = ( 3, 0, 1, 5, 0) T, Z = 9., x 1= 3, x 2= 0, Z = 9., x 2 2= 0, 17

,,., x 2, x 3,, X = ( 5/ 2, 3/ 2, 0, 3, 0) T, x 1= 5/ 2, x 2= 3/ 2, Z = 9. X= X + ( 1- ) X ( 01),. max Z, min Z, ( 1), ( 2) j 0 j 0 s< 0 s> 0,,. 2. 3. 3 2. 3. 2,,.,,.?,.. a j x j = b( = 1, 2,, m), j = 1 x + 1, x + 2,, x + m0, a 11x 1 + a 12x 2 + + a1 x + x + 1 = b1 a 21x 1 + a 22x 2 + + a2 x + x + 2 = b2 a m1x 1 + a m2x 2 + + amx + x + m = bm x 1, x 2,, x 0; x + 1, x + 2,, x + m 0., B= ( P + 1, P + 2,, P + m) = I,, x + 1, x + 2,, x + m. x 1, x 2,, x, X ( 0) = ( 0, 0,, 0, b1, b2,, bm) T.,,,, ;. 1., : :, : min W = x + 1 + x + 2 + + x + m, a1 1x 1 + a1 2x 2 + + a 1x + x + 1 = b1 ( LP 1) a2 1x 1 + a2 2x 2 + + a 2x + x + 2 = b2, LP 1: am 1x 1 + a m 2x 2 + + am x + x + m = bm x 1, x 2,, x 0; x + 1, x + 2,, x + m 0. ( 1) W= 0,,. ( 2) W0,,. :,,,. 7. 18

min Z = x 1 + 1. 5x 2, x 1 + 3x 2 3 s. t. x 1 + x 2 2 x 1, x 2 0. x 3, x 4, x 5, x 6, : min W = x 5 + x 6, x 1 + 3x 2 - x 3 + x 5 = 3 ( LP 1) x 1 + x 2 - x 4 + x 6 = 2 x 1, x 2, x 3, x 4, x 5, x 6 0., W= 0, x 1= 3/ 2, x 2= 1/ 2, x 3= x 4= x 5= x 6= 0, 2. 9. 2. 9 cj 0 0 0 0 1 1 CB XB b x 1 x 2 x 3 x 4 x 5 x 6 1 x 5 3 1 3-1 0 1 0 3 1 x 6 2 [ 1] 1 0-1 0 1 2 W 5 2 4-1 - 1 0 0 j 0 x 2 1 0 [ 2] - 1 1 1-1 1/ 2 1 x 6 2 1 1 0-1 0 1 2 W 2 0 2-1 1 0-2 j 0 x 2 1/ 2 0 1-1/ 2 1/ 2 1/ 2-1/ 2 0 x 1 3/ 2 1 0 1/ 2 3/ 2-1/ 2 3/ 2 W 0 0 0 0 0-1 - 1 j x 5= x 6 = 0, ( x 1, x 2, x 3, x 4 ) = ( 3/ 2, 1/ 2, 0, 0).,,, 2. 10. 2. 10 c j 1 1. 5 0 0 CB XB b x 1 x 2 x 3 x 4 1. 5 x 2 1/ 2 0 1-1/ 2 1/ 2 1 x 1 3/ 2 1 0 1/ 2-3/ 2 Z 9/ 4 0 0-1/ 4-3/ 4 j 2. 10, : x 1 = 3/ 2, x 2 = 1/ 2, Z = 9/ 4.,, W = 0, 19

( ),,,,. 2. M,, ( - M) ( M ), : m max Z = c1x 1 + c2x 2 + + cx + ( - M) x +, = 1 a1 1x 1 + a 1 2x 2 + + a 1x + x + 1 = b1 a2 1x 1 + a 2 2x 2 + + a 2x + x + 2 = b2 ( LP M ) am 1x 1 + a m2x 2 + + am x x + m = bm x 1, x 2,, x 0; x + 1, x + 2,, x + m 0.,.,. LP M LP M LP, :,, LP. : M : min Z = - 3x1 + x 2 + x 3, s. t. x 1-2x 2 + x 3 11-4x 1 + x 2 + 2x3 3-2x 1 + x 3 = 1 x 1, x 2, x 3 0. :, LP M ( + M). 2. 3. 4, ( 1),,,,,. ( 2) max, 2. 5. 2. 3. 5 2. 3. 1 2. 3,,.,.,,,,,.,,. 2. 3,. : : : B, B, B - 20 1 = B= I.

2. 5 : Y= CBB - X B X N N 0,,.,. B - = B - 0 1 b. 1, N, N = YN - CN. : s= min {j j < 0, 0j }, x s. B - 1 P s, 1 P s0,,.. : = min ( 1 B- b) ( B - 1 P s) ( B - 1 P s) > 0 = ( 1 B- b) r ( B - 1 P s) r. 21

x r. B1. : B - 1 1, B - 1 1 b.., B - 1 1, B B1, B - 1 1. B - 1 1 = EB - 1, E= ( e1,, er - 1,, er+ 1,, em), e 1, 0 m, = B, B -.. - a 1s/ a rs - a 2s/ a rs l / a r s - a ms/ a rs 8. A= ( P 1, P 2, P 3, P 4) = r. 1,, max Z = 4x 1 + 3x 2, s. t. 2x 1 + 3x2 24 3x 1 + 2x2 26 x 1, x 2 0. max Z = 4x 1 + 3x 2 + 0x 3 + 0x 4, s. t. 2x 1 + 3x 2 + x 3 = 24 3x 1 + 2x 2 + x 4 = 26 x 1, x 2, x 3, x 4 0. 2 3 1 0 3 2 0 1, b= B0= ( P 3, P 4) = I, B - 1 0 = B0= I, B - 1 0 b= X N 0= ( x 1, x 2) T, CN 0= ( 4, 3). : Y0= CB 0B - 0 1 = 0, N 0= Y0N 0- CN 0= ( -. = min ( B - 1 0 b) ( B - 1 0 P 1) 24 26, C= ( c1, c2, c3, c4) = ( 4, 3, 0, 0). 24 26, X B 0= ( x 3, x 4) T, CB 0= ( 0, 0), 4, - 3) = ( 1, 2 ),, x 1 ( B - 1 0 P 1) > 0 = min ( 12, 26/ 3) = 26/ 3. x 4. B1= ( P 3, P 1), X B 1= ( x 3, x 1) T, X N 1= ( x 2, x 4) T, CB1= ( 0, 4), CN 1= ( 3, 0). 20/ 3 1 = - 2/ 3 1/ 3,, B- 1 1 = E 1B - 1 0 = 1-2/ 3 0 1/ 3, X B 1= B- 1 1 b= 1-2/ 3 0 1/ 3 24 26 = 26/ 3. 22

: Y1 = CB 1B - 1 1 = ( 0, 4/ 3), N 1 = Y1N 1 - CN 1 = ( 0, 4/ 3) 4/ 3) = ( 2, 4),, x 2. B - 1 1 P 2 = 1-2/ 3 0 1/ 3 5/ 3, 26/ 3 2/ 3) = min ( 4, 13) = 4. 3 2 = 5/ 3 2/ 3 > 0, = min ( B - 1 1 b) ( B - 1 1 P 2) 3 0 2 1 - ( 3, 0) = ( - 1/ 3, B - 1 1 P 2> 0 = min ( 20/ 3 x 3. B2= ( P 2, P 1 ). X B 2= ( x 2, x 1) T, X N 2 = ( x 3, x 4 ) T, CB 2 = ( 3, 4), CN 2= ( 0, 0). 2 = 3/ 5-2/ 5, E 2 = 3/ 5-2/ 5-2/ 5 3/ 5, X B2= B- 1 2 b= 0 1 : Y2 = CB 2B - 1 2 = ( 3, 4) 3/ 5 0-2/ 5 1, B - 1 2 = E 2B - 1 1 = 3/ 5-2/ 5-2/ 5 3/ 5 24 26 = 4 6. 3/ 5 0-2/ 5 1 1-2/ 3 0 1/ 3 = 3/ 5-2/ 5-2/ 5 3/ 5 = ( 1/ 5, 6/ 5), N 2 = Y2N 2 - CN 2 = ( 1/ 5, 6/ 5) 1 0 - ( 0, 0) = ( 6/ 5, 1/ 5) 0,, B2, X = x 1 x 2 = 4 6, Z = Y2b = ( 1/ 5, 6/ 5) 24 26 = 36.,. 2. 4. 1 2. 4 91,.,,,,,? y 1, y 2,,,,., 4,,,,, : 2y 1 + 3y 2 4. 3y 1 + 2y 2 3. min W = 24y1 + 26y 2. min W = 24y1 + 26y 2, 23

2y 1 + 3y 2 4 s. t. 3y 1 + 2y 2 3 y 1, y 2 0.., m,, b( = 1,, m). j ( j = 1, 2,, ) aj, cj.,? x j j, : max Z = c1x 1 + c2x 2 + + cx, ( 2. 15) a 11x 1 + a 12x 2 + + a 1x b1 s. t. a 21x 1 + a 22x 2 + + a 2x b2 ( 2. 16) a m1x 1 + a m2x 2 + + a mx bm x j 0 ( j = 1, 2,, ).,,,,,. y ( ) ( = 1, 2, 3,, m), j, a1 j, a 2j,, a mj, min W = b1y 1 + b2y 2 + + bmy m, ( 2. 17) s. t. a 11y 1 + a 21y 2 + + a m1y m c1 a 12y 1 + a 22y 2 + + a m2y m c2 a 1y 1 + a 2y 2 + + a my m c. ( 2. 18),,. 2. 4. 2 1., max Z = CX, ( 2. 19) s. t. AX b X 0. ( 2. 20) min W = Yb, min W = b T Y T ( 2. 21) YA C s. t. Y 0. s. t. A TY T C T ( 2. 22) Y T 0, A, b, C,. 101. 24

: A = 2 3 3 2, C = ( 4, 3), b = 24 26. min W = b T Y T = ( 24, 26) A T Y T = 2 3 3 2 min W = 24y 1 + 26y 2, 2y 1 + 3y 2 4 3y 1 + 2y 2 3 y 1, y 2 0. y 1 y 2 4 3 : ( 1) ; ( 2) ; ( 3), ; ( 4),. 2. 11. 2. 11 y 1 y 2., y x j x 1 x 2 x min W y 1 a11 a 12 a 1 b1 y 2 a21 a 22 a 2 b2 y m a m1 a m2 a m b m max Z c 1 c 2 c,,. 112. 12. 2. 12 y x j x 1 x 2 b y 1 3 4 8 y 2 2 0 16 y 3 1 2 12 C 3 5 25

: : max Z= 3x 1+ 5x 2, min W = 8y 1+ 16y 2+ 12y 3, s. t. 3x 1+ 4x 28 2x 116 x 1+ 2x 212 x 1, x 20. 2. s. t. 3y 1+ 2y 2+ y 33 4y 1+ 2y 35 y 1, y 2, y 30.,? AX= b AXb, ( 2. 23) - AX- b, max Z = CX, s. t. max Z = s. t. AX = b X 0. AX b CX, - AX - b X 0 ( 2. 23) ( 2. 24) ( 2. 25) Y ( 2. 24), Y ( 2. 25), min W = Y A - Y b - Y A C Y, Y0, Y b, min W = ( Y - Y ) b, ( Y - Y ) A C Y, Y0. Y= Y - Y, Y., min W = Yb, YA C Y., 2. 13. 2. 13 ( 2. 26) ( ) max Z 0 0 m = ( ) min W = m 0 0 26

12. min Z = 3x1 + 2x 2-4x 3 + x 4, s. t. 2. 13, : x 1 + x 2-3x 3 + x 4 10 2x 1 + 2x3 - x 4 8 x 2 + x 3 + x 4 = 6 x 1 0, x 2, x 3 0, x 4. max W = 10y 1 + 8y 2 + 6y3, s. t. 2. 4. 3 Y ( 0) b. y 1 + 2y 2 3 y 1 + y 3 2-3y 1 + 2y2 + y 3-4 y 1 - y 2 + y 3 = 1 y 1 0, y 2 0, y 3.. (. ) X ( 0), Y ( 0), CX ( 0 ) max Z = CX, AX b, X 0 min W = Yb, YA C, Y 0. X ( 0 ), AX ( 0) b. Y ( 0 ), Y ( 0) AC. CX ( 0 ) Y ( 0 ) AX ( 0 ) Y ( 0) b CX ( 0 ) Y ( 0) b., ( ), ( ).,. X ( 0 ), Y ( 0 ), CX ( 0) = Y ( 0) b, X ( 0 ), Y ( 0)..,, max Z= CX, AXb, X0, max Z= CX+ 0X L, AX+ X L= b, X0, XL 0. X, B CBB - 1 ( A, I ) - ( C, 0) 0, CBB - 1 A- C0, CBB - 1 0. Y = CBB - 1, Y AC, Y 0. Y = CBB - 1 min W = Yb, YAC, Y0. W = Y b= CBB - 1 b, 27

Z= CX = CBB - 1 b. Y b= CX., X, Y,. X, Y, X, Y Y X L= 0 YsX = 0. : : max Z = CX, min W = Yb, AX + XL = b YA - Ys = C X, X L 0. Y, Ys 0. Z= CX = ( YA- Ys) X= YAX- YsX. ( 2. 27) W = Yb = Y( AX + X L) = YAX + YXL. ( 2. 28) = > X, Y, CX= Yb, ( 2. 27) ( 2. 28), Y AX - YsX = Y AX + Y X L. - YsX = Y X L. Y, Ys 0, X, X L 0, YsX = 0 Y X L = 0. < = Y X L= 0, YsX = 0. ( 2. 27) ( 2. 28) CX = Y AX = Y b. X, Y. max Z= CX, AX+ X L= b, X, X L0. min W = Yb, YA- Ys= C, Y, Ys0., 2. 14. 2. 14 XB XN XL 0 CBB - 1 N- CN CBB - 1 Ys1 Ys2 Y Ys1 XB, Ys2 X N. B, A= ( B, N), max Z = CB XB s. t. 28 + CN X N, BXB + N XN + XL = b X B, X N, X L 0. min W = Yb,

s. t. YB - Ys1 = CB YN - Ys2 = CN Y, Ys1, Ys2 0, Ys= ( Ys1, Ys2). ( 2. 29) ( 2. 30) X= ( X B, X N, X L) T = ( B - 1 b, 0, 0) T, = ( B, N, L ) = ( 0, CBB - 1 N - CN, CB B - 1 ). Y= CBB - 1, ( 2. 29), ( 2. 30) Ys1= 0, Ys2= CBB - 1 N - CN, ( Y, Ys1, Ys2) = ( CBB - 1, 0, CBB - 1 N - CN ). 13 max Z = x 1 + x 2, s. t.. - 2x 1 + 2x 2 + 3x 3 6-3x 1 + x 2 - x 3 5 x 1, x 2, x 3 0.,, X = ( 0, 0, 0) T, min W = 6y 1 + 5y 2, s. t. - 2y 1-3y 2 1 2y 1 + y 2 1 3y 1 - y 2 0 y 1, y 2 0. y 1, y 20,,,,. : min W = 2x 1 + 3x 2 + 5x 3 + 2x 4 + 3x 5, s. t. x 1 + x 2 + 2x 3 + x 4 + 3x 5 4 2x 1 - x 2 + 3x 3 + x 4 + x 5 3 x j 0, j = 1, 2,, 5. y 1 = 4/ 5, y 2 = 3/ 5, Z = 5,. 2. 4. 4,,,.,,,.,. ( CBB - ( B - 1 A- C0),, 1 b0),.,,. : :. 29

. z j - cj 0,. : b,,,. b, : ( 1) min { ( B - 1 b) < 0}= r, x r. ( 2) x r., a rj ( j = 1, 2,, ). a rj 0,, = min - a j a rj < 0 = - s, rj a r s x s. ( 3) a rs,,.. 14. min Z = 12y 1 + 8y2 + 16y 3 + 12y 4, s. t. 2y 1 + y 2 + 4y 3 2 2y 1 + 2y2 + 4y4 3 y 0 ( = 1, 2, 3, 4). max Z = - 12y 1-8y 2-16y 3-12y 4 + 0y 5 + 0y 6, s. t. - 2y 1 - y 2-4y 3 + y 5 = - 2-2y 1-2y 2-4y 4 + y 6 = - 3 y 1, y 2, y 3, y 4, y 5, y 6 0., 2. 15. 2. 15 cj - 12-8 - 16-12 0 0 CB XB b y 1 y 2 y 3 y 4 y 5 y 6 0 y 5-2 - 2-1 - 4 0 1 0 0 y 6-3 - 2-2 0 [ - 4] 0 1 Z 0 12 8 16 12 0 0 j 0 y 5-2 - 2 [ - 1] - 4 0 1 0-12 y 4 3/ 4 1/ 2 1/ 2 0 1 0-1/ 4 Z - 9 6 2 16 0 0 3 j - 8 y 2 2 2 1 4 0-1 0-12 y 4-1/ 4-1/ 2 0 [ - 2] 1 1/ 2-1/ 4 Z - 13 2 0 8 0 2 3 j - 8 y 2 3/ 2 1 1 0 2 0-1/ 2-16 y 3 1/ 8 1/ 4 0 1-1/ 2-1/ 4 1/ 8 30 Z - 14 0 0 0 4 4 2 j

, y= ( y 1, y 2, y 3, y 4) T = ( 0, 3/ 2, 1/ 8, 0) T. Z = - Z = 14. :,.,,. 2. 4. 5 CB B -, B {max Z = CX AX b, X 0}, Y = 1, m Z = CBB - 1 b = Y b = by, = 1 Z = y,, y. b,, ( CBB - 1 ).,,, ( shadow price ).,. ( ).,.,,,,.,,.. y,, ;,,.,,,,.,.,.,. ( 1),,.,.,.,,.,,. ( 2). ( 3).,, ;,,.,. 31

( 4). 2. 5, a j, b, cj,,,.,,,,?,?,?., B., : ( 1) B ( B - 1 b0) ; ( 2) B ( CB B - 1 A- C0). ( B). 2. 5. 1cj ( 1) cj x j. cj cj + cj, B, j = CBB - 1 P j - ( cj + cj ) 0, cj CBB - B, cj. 1 P j - cj = j. ( 2. 31) ( 2) cr x r. crcr+ cr, CB,, = ( CB + CB ) B - 1 A - C = CB B - 1 A + ( 0,, cr,, 0) B - 1 A - C = CB B - 1 A - C + cr ( a r1, a r 2,, a r m). = + cr( a r1, a r 2,, a r m). j + cra j = rj, ( j = 1, 2,, )., j = j + cra r j 0, ( j = 1, 2,, ). ( 2. 32) ( 2. 31) cr : max {- j / a r j a rj > 0} cr min j j {- j / a r j a rj < 0}. cr, B,. 151 2. 7, x 1 c1 c1,, c1. c1+ c1 2. 6, 2. 16. B, 32 1/ 5-2/ 5 c1 0 6/ 5 + 3/ 5 c1 0,

- 2 c11/ 2. 2. 16 cj 4+ c1 3 0 0 C B X B b x 1 x 2 x 3 x 4 3 x 2 4 0 1 3/ 5-2/ 5 4+ c1 x 1 6 1 0-2/ 5 3/ 5 Z 36+ 6 c1 0 0 1/ 5-2/ 5 c1 6/ 5+ 3/ 5 c1 j x 1 c1 [ 2, 4. 5],. 6 c1. 2. 5. 2 bk, bk B - 1, A, C,,. bk- > bk+ bk, X B = B - 1 ( b+ b), b = ( 0, 0,, bk, 0,, 0) T. X B0, B. bk : B - 1 ( b+ b) = B - 1 b+ B - 1 b, B - 1 b= ( b 1, b 2,, b m) T, 0, B - 1 b= B - 1 bk 0 = bk a 1k a mk B - 1 b+ B - 1 b0, b + a k bk0, = 1, 2,, m. ( 2. 33) B. ( 2. 33), bk : max{- b / a k a k > 0} bk min {- b / a k a k < 0}., bk. bk., B, 161 b2. 2. 7, 4 3/ 5-2/ 5 6 + - 2/ 5 3/ 5., B, B - 1 b + B - 1 0 0 b2 b2 = 0, 4-2/ 5 6 + 3/ 5 b2 0. 33

4-2/ 5 b2 0 6 + 3/ 5 b2 0. - 10 b2 10. b2 [ 16, 36]. 2. 5. 3 ( 1) aj, b,.. 17 1,., P 1 = ( 1, 2) T, 6.? P 1, x 1, x 1 x 1, P 1 B - 1 P 1 =, 3/ 5-2/ 5-2/ 5 3/ 5 1 = CB B - 1 P 1 - c1 = ( 3, 6) 3 = ( 3, 6) 4 = ( 3, 6) 1 2 = - 1/ 5 4/ 5-1/ 5 4/ 5-6 = - 9/ 5. 3/ 5-2/ 5-0 = - 3/ 5, - 2/ 5 3/ 5-0 = 12/ 5. 2. 6, 2. 17. 2. 17, c j 6 3 0 0 CB XB b x 1 x 2 x 3 x 4 3 x 2 4-1/ 5 1 3/ 5-2/ 5-6 x 1 6 [ 4/ 5] 0-2/ 5 3/ 5 15/ 2 Z 48-9/ 5 0-3/ 5 12/ 5 j 2. 17 [ 4/ 5], 2. 18 2. 19. 2. 18 c j 6 3 0 0 CB XB b x 1 x 2 x 3 x 4 3 x 2 11/ 2 0 1 [ 1/ 2] - 1/ 4 11 6 x 1 15/ 2 1 0-1/ 2 3/ 4 - Z 123/ 2 0 0-3/ 2 15/ 4 j 34

2. 19 cj 6 3 0 0 CB XB b x 1 x 2 x 3 x 4 0 x 3 11 0 2 1-1/ 2 6 x 1 13 1 1 0 1/ 2 Z 78 0 3 0 3 j 2. 19. 13, 0, 78. 17, ( ).,,.. ( 2) a j, B, B a rj a rj + a rj, ( CBB - 1 ) r CB B - 1 r. j = CBB - 1 P j - cj = j + ( CB B - 1 ) r a rj, B, ar j. 2. 5. 4 a rj - j ( CBB - 1 ) r, :. ( 2. 34),., (, ) ;,,,. 181 : 1 3, 1 4, 30,. 3x 1 + 4x 2 30. x 1= 6, x 2= 4, 34,.,. x 1= 6+ 2/ 5x 3-3/ 5x 4 x 2= 4-3/ 5x 3+ 2/ 5x 43x 1+ 4x 230, - 6/ 5x 3-1/ 5x 4-4. x 5, 2. 7,, 2. 20., 22/ 3, 2, 106/ 3. 35

2. 20 cj 4 3 0 0 0 CB XB b x 1 x 2 x 3 x 4 x 5 3 x 2 4 0 1 3/ 5-2/ 5 0 4 x 1 6 1 0-2/ 5 3/ 5 0 0 x 5-4 0 0 [ - 6/ 5] - 1/ 5 1 Z 36 0 0 1/ 5 6/ 5 0 3 x 2 2 0 1 0-1/ 2 1/ 2 4 x 1 22/ 3 1 0 0 2/ 3-1/ 3 0 x 3 10/ 3 0 0 1 1/ 6-5/ 6 Z 106/ 3 0 0 0 6/ 7 1/ 6 2. 6 2. 6. 1,.,,?. m A, = 1, 2,, m,, ( ) a, B j, j = 1, 2,,, bj, A B j cj, 2. 21 2. 21 B 1 B 2 B A 1 c 11 c 12 c 1 a 1 A 2 c21 c22 c2 a 2 Am cm1 cm2 cm a m b1 b2 b x j A B j, : m, a = = 1 bj j = 1, min Z = m = 1 j = 1 cj x j, 36

s. t. m x j = 1 : = bj, j = 1, 2,, x j = a, = 1, 2,, m j = 1 x j 0, ( = 1, 2,, m; j = 1, 2,, ). min Z = CX, s. t. AX = b X 0. C= ( c11, c12,, c1, c2 1, c22,, c2,, cm1, cm 2,, cm), X= ( x 11, x 12,, x 1, x 21, x 22,, x 2,, x m1, x m 2,, x m ) T, b= ( a 1, a 2,, am, b1, b2,, b) T, x 11x1 2x 1 x 21x 22x 2x m1xm 2x m A = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 m A x j P j P j = e+ em+ j. A rank ( A) = m+ - 1, A m+ - 1. m+ - 1,., 0x j min( a, bj ), max, min,,. m x j m+ - 1.,, m,,. A,,,. 2. 6. 2 ( ) ;,.,... 18 A 1, A 2, A 3 2. 22.? B 1, B 2, B3, B 4, B5, 37

2. 22 : / B 1 B 2 B 3 B 4 B 5 ( ) A1 7 10 8 6 4 40 A 2 5 9 7 12 6 40 A3 3 6 5 8 11 90 ( ) 30 40 60 20 20 :,,. 1.. 18. 2. 22 3, A 3 30 B1, B 1, B1, 2. 23. 2. 23 ( : ) ( : / ) B 1 B 2 B 3 B 4 B 5 ( ) B 1 B 2 B 3 B 4 B 5 A1 40 7 10 8 6 4 A2 40 5 9 7 12 6 A3 30 90 3 6 5 8 11 ( ) 30 40 60 20 20 4, A 1 20 B 5, B 5. 5, A 3 60 B 3, B 3. A 3, A 3,, ( m+ - 1), 0, ( A 2, B 3) 0 ;,, 2. 24 2. 27 2. 24 ( : ) ( : / ) B 1 B 2 B 3 B 4 B 5 ( ) A 1 20 40 7 10 8 6 4 A 2 40 5 9 7 12 6 A 3 30 90 3 6 5 8 11 ( ) 30 40 60 20 20 B 1 B 2 B 3 B 4 B 5 38

2. 25 ( : ) ( : / ) B 1 B 2 B 3 B 4 B 5 ( ) B 1 B 2 B 3 B 4 B 5 A 1 20 40 7 10 8 6 4 A 2 0 40 5 9 7 12 6 A 3 30 60 90 3 6 5 8 11 ( ) 30 40 60 20 20 2. 26 ( : ) ( : / ) B 1 B 2 B 3 B 4 B 5 ( ) B 1 B 2 B 3 B 4 B 5 A 1 20 20 40 7 10 8 6 4 A 2 0 0 40 5 9 7 12 6 A 3 30 60 90 3 6 5 8 11 ( ) 30 40 60 20 20 2. 27 ( : ) ( : / ) B 1 B 2 B 3 B 4 B 5 ( ) B 1 B 2 B 3 B 4 B 5 A 1 20 20 40 7 10 8 6 4 A 2 40 0 0 40 5 9 7 12 6 A 3 30 60 90 3 6 5 8 11 ( ) 30 40 60 20 20 Z= 206+ 204+ 409+ 07+ 012+ 303+ 605= 950. 9. 5.,.,. ( m+ - 1).,,,, ( m+ - 1), 0. 2.,.,,,.,,.,. : ; ( 1), 39

( 2),,, ; ( 3), ( 1) ( 2),. 18, 2. 28 2. 39. 2. 28 : / 2. 29 : / B 1 B 2 B 3 B 4 B 5 A 1 7 10 8 6 4 2 A 2 5 9 7 12 6 1 A 3 3 6 5 8 11 2 2 3 2 2 2 B 1 B 2 B 3 B 4 B 5 A1 40 A2 40 A3 40 90 30 40 60 20 20 2. 30 : / 2. 31 : / B 1 B 2 B 3 B 4 B 5 A 1 7 10 8 6 4 2 A 2 5 9 7 12 6 1 A 3 3 6 5 8 11 2 2-2 2 2 B 1 B 2 B 3 B 4 B 5 A1 40 A2 40 A 3 30 40 90 30 40 60 20 20 2. 32 : / 2. 33 : / B 1 B 2 B 3 B 4 B 5 A 1 7 10 8 6 4 2 A 2 5 9 7 12 6 1 A 3 3 6 5 8 11 3 - - 2 2 2 B 1 B 2 B 3 B 4 B 5 A1 40 A2 40 A3 30 40 20 90 30 40 60 20 20 2. 34 : / 2. 35 : / B 1 B 2 B 3 B 4 B 5 A 1 7 10 8 6 4 2 A 2 5 9 7 12 6 1 A 3 3 6 5 8 11 - - - 1 6 2 B 1 B 2 B 3 B 4 B 5 A1 20 40 A2 40 A 3 30 40 20 90 30 40 60 20 20 2. 36 : / 2. 37 : / B 1 B 2 B 3 B 4 B 5 A 1 7 10 8 6 4 4 A 2 5 9 7 12 6 1 A 3 3 6 5 8 11 - - - 1-2 B 1 B 2 B 3 B 4 B 5 A1 20 20 40 A2 0 40 A3 30 40 20 90 30 40 60 20 20 40

2. 38 : / 2. 39 : / B 1 B 2 B 3 B 4 B 5 A 1 7 10 8 6 4 - A 2 5 9 7 12 6 1 A 3 3 6 5 8 11 - - - 7-6 B 1 B 2 B 3 B 4 B 5 A1 20 20 40 A2 40 0 40 A3 30 40 20 90 30 40 60 20 20, Z= 206+ 204+ 204+ 407+ 06+ 303+ 406+ 205= 9. 1.,.. :, ( 1).,,, 90,,. ( 2). 2. 40,,. 2. 40 B 1 B 2 B 3 B 4 B 5 A1 30 30 60 A2 40 30 70 A3 30 30 40 100 40 60 60 30 40,,.,, ( ) j = CBB - 1 P j - cj = ( u + v j ) - cj, j J N., j 0,.,. 1. 2. 27. 2. 27, 2. 41, 2. 27. ( A 1, B 2) ( A 1, B2 ) ( A 1, B4 ) ( A 2, B 4) ( A 2, B 2) ( A 1, B 2), A 1 1 B2,?, A 1 1 B4, A 2 1 B4, A 2 B 2., 10-6+ 12-9= 7,,. 7-7 ( A 1, B 2) 41

.,, 2. 42. 2. 41 : / B 1 B 2 A1 6 4 A 2 9 7 12 A3 3 5 B 3 B 4 B 5 2. 42 B 1 B 2 B 3 B 4 B 5 A1-8 - 7-7 A2 0 4 A 3 1 2-3 2. 42, 3,. 2.,.,.., CB B - 1 m +. u 1, u 2,, u m, v 1, v 2,, v. j = CBB - 1 P j - cj, P j = e+ em+ j,, j = ( u+ v j ) - cj. ( ) j = ( u + vj ) - cj = 0(, j J B). m+ m+ - 1 u + vj = cj (, j J B).,,, u vj ( = 1, 2,, m; j = 1, 2,, ), ( ).. 2. 43). 2. 41,. 2. 41,, u vj ( 2. 43 : / B 1 B 2 B 3 B 4 B 5 u A1 6 4 u1 A2 9 7 12 u2 A 3 3 5 u 3 vj v1 v 2 v 3 v4 v5 42

u + v j = cj (, j J B ), u 1 + v 4 = 6 u 1 + v 5 = 4 u 2 + v 2 = 9 u 2 + v 3 = 7 u 2 + v 4 = 12 u 3 + v 1 = 3 u 3 + v 3 = 5, u 2 = u 2 = 12 u 3 = 10 v1 = - 7 v2 = - 3 v3 = - 5 v4 = 0 v5 = - 2. 6 j = ( u + vj ) - cj (, j J N ),, 2. 44. 2. 44 : / B 1 B 2 B 3 B 4 B 5 u A1-8 - 7-7 6 A2 0 4 12 A3 1 2-3 10 vj - 7-3 - 5 0-2,. :,,. :,,, 18 ( A 2, B 5)., = min { }. 0, 2. 45, 2. 46. 2. 45 B 1 B 2 B 3 B 4 B 5 A 1 20 20 40 A 2 40 0 0 40 A 3 30 60 90 30 40 60 20 20 B 1 2. 46 B 2 B 3 B 4 B 5 A 1-4 - 3-3 A 2 0-4 A 3 1-12 - 7 ( A 3, B 2), 2. 47, 2. 48. 2. 48, 8,. Z = 206+ 204+ 204+ 407+ 06+ 303+ 406+ 205= 9. 1. : 43

( 1) 0,,. ( 2)., 0,. :,,, 0., r ( r> 1), r r - 1 0., 18. 2. 47 B 1 B 2 B 3 B 4 B 5 A 1 20 20 40 A 2 40 0 40 A 3 30 40 20 90 30 40 60 20 20 B 1 2. 48 B 2 B 3 B 4 B 5 A 1-4 - 4-3 A 2 0-1 - 4 A 3-2 - 7 2. 6. 3, m a = = 1 bj..,,.,, min Z = s. t. m m a > = 1 = 1 j = 1 j = 1 bj j = 1 cj x j, x j a ( = 1, 2,, m) j = 1 m x j = bj ( j = 1, 2,, ) = 1 x j 0 ( = 1, 2,, m, j = 1, 2,, )., B+ 1, x, + 1A, 44 j = 1 + 1 x j + x, + 1 = j = 1 x j = a ( = 1, 2,, m).

m = 1 m x, + 1 = a - = 1 bj = b+ 1. j = 1 0,, c, + 1 = 0, = 1, 2, 3,, m, : min Z s. t. m + 1 = = 1 j = 1 cj x j, + 1 x j = a ( = 1, 2,, m) j = 1 m x j = bj ( j = 1, 2,, + 1) = 1 x j 0 ( = 1, 2,, m, j = 1, 2,, + 1).,, A m + 1, a m+ 1 A m + 1Bj. m am + 1 = bj - a. j = 1 = 1 cm+ 1, j = 0( j = 1, 2,, ), 19. 2. 49.. 2. 49 : / B 1 B 2 B 3 B 4 ( ) A1 6 3 12 6 10 A2 4 3 9-12 A 3 9 10 13 10 10 ( ) 6 14 0 5 ( ) 10 14 6, 32, 25,. 12, 42,., A 4, 10., A 1, 6, A 4, M( M ), A 4,,. 2. 50., 0. 2. 49 ( A 2, B4) A 2 B 4, 2. 50 M. 2. 50, 2. 51. A 1 B 2 B 4 8 2, A 2 B1 B 2 6, A 3 B 4 10. Z = 83+ 26+ 64+ 63+ 510+ 510= 178. 45

2. 50 B 1 B 1 B 2 B 3 B 4 B 4 A 1 6 6 3 12 6 6 10 A 2 4 4 3 9 M M 12 A 3 9 9 10 13 10 10 10 A 4 M 0 M 0 M 10 10 6 4 14 6 5 7 2. 51 B 1 B 1 B 2 B 3 B 4 B 4 A 1 8 2 10 A 2 6 6 12 A 3 5 5 10 A 4 4 6 0 10 6 4 14 6 5 7 2. 7,.,,,.,,,,,.,.. ( ). 1,,. x 1 x 2, : max Z = 4x 1 + 3x2, s. t. 2x 1 + 3x 2 24 3x 1 + 2x 2 26 x 1, x 2 0. x 1 = 6, x 2 = 4, z = 36. 6, 4, 36., : ( 1),,, ; ( 2), ; ( 3) 30. 46

, ( 1) ( 2) ( 3),?, x 1 x 2,, : 2x 1+ 3x 224. d - 1, d + 1.. ( 1) - x 1+ x 2+ d - 1 - d + 1 = 0. d - 2 d + 2,,, ( 2), : 3x 1+ 2x 2+ d - 2 - d + 2 = 26. d - 3 d + 3, 30 30, ( 3), : 4x 1+ 3x 2+ d - 3 - d + 3 = 30. :, min Z 1 = d - 1, min Z 2 = d + 2 + d - 2 - min Z 3 = d - 3. min Z 1= d - 1 ; min Z 2= d + 2 + d - 2 ; min Z 3= d - 3. s. t. 2x 1 2. 7. 1. + 3x 2 24 - x 1 + x 2 + d - 1 - d + 1 = 0 3x 1 + 2x 2 + d - 2 - d + 2 = 26 4x 1 + 3x 2 + d - 3 - d + 3 = 30 x 1, x 2 0, d + 0, d - 0, = 1, 2, 3., 1., x.,, d + d -. d +, ; d -. ( 1) ( 2) ( 3) ( 4), d + d -., d + 0,, d - = 0; d - 0, d + = 0,, d + d - = 0., d + d -. 2., 47

( 1),.,,,,,. ( 2) ( 3) ( 4).,., f ( X ) + d - - d + = b, d - = 0, f ( X ) b, d + = 0, f ( X ) b, d + = d - = 0, f ( X ) = b. 3.,,,,. P 1, P 2,, P k+ 1, P kp k+ 1, ( k= 1, 2,, K ) P k,. P 1 P k+ 1,, P 2 P 1,,, rk,. 4..,. f ( X ) + d - - d + = b, : ( 1), min ( d + + d - ) ; ( 2), min ( d + ) ; ( 3), min ( d - ). ( 1) ( 2) ( 3) P 1, P 2, P 3, min Z = P 1d - 1 + P 2( d + 2 + d - 2 ) + P 3d - 3, s. t. 2x 1 + 3x 2 24, min Z = s. t. - x 1 + x 2 + d - 1 - d + 1 = 0 3x 1 + 2x 2 + d - 2 - d + 2 = 26 4x 1 + 3x 2 + d - 3 - d + 3 = 30 x 1, x 2 0, d + 0, d - 0, = 1, 2, 3. L P r r = 1 a j x j j = 1 K ( r k d - k + rk d + k ), k = 1 b= 1, 2,, m ckj x j + d k - - d + k = g kk = 1, 2,, K j = 1 x j 0 j = 1, 2,, ; d - k, d + k 0 k = 1, 2,, K.,, 48 ( 1) ( 2) ( 3) ( 4)

,, P 0. P 0,.,,,. 2. 7. 2,.. 20. ( 1)., 2. 6, OAB., ( d +, d - ) 0,. 2. 6 ( 2) d +, d -. ( 3)., P 1, min d - 1,, d - 1 = 0 OBC; P 2, OBC min ( d + 2 + d - 2 ),, C( 24/ 5, 24/ 5) ( 2), ( d + 2 + d - 2 ), d + 2 = 0, d - 2 = 2;, P 3, C, d - 3 = 0, d + 3 = 18/ 5.,, x 1 = 24/ 5, x 2= 24/ 5, 168/ 5= 33. 6. d + d -, ( ),. 2. 7. 3,,.,. 21. : min Z = P 1d - 1 + P 2( d + 2 + d - 2 ) + P 3d - 3, 49

2x 1 + 3x 2+ x 3 = 24 - x 1 + x 2 + d - 1 - d + 1 = 0 s. t. 3x 1 + 2x 2 + d - 2 - d + 2 = 26 4x 1 + 3x 2 + d - 3 - d + 3 = 30 x 0, d + 0, d - 0, = 1, 2, 3. 1 : x 3, d - 1, d - 2, d - 3, 2. 52. 2. 52 cj 0 0 0 P 1 P 2 P 3 0 P 3 0 CB X B b x 1 x 2 x 3 d - 1 d - 2 d - 3 d + 1 d + 2 d + 3 0 x 3 24 2 3 1 0 0 0 0 0 0 8 P 1 d - 1 0-1 [ 1] 0 1 0 0-1 0 0 0 P 2 d - 2 26 3 2 0 0 1 0 0-1 0 13 P 3 d - 3 30 4 3 0 0 0 1 0 0-1 10 P 1-1 1-1 j P 2 3 2-2 P 3 4 3-1 2. 52 :,,,,, K j = zj - cj = k= 1, x 1 akj P k - cj ( j = 1, 2,, ). 0 1 = z 1 - c1 = ( 2, - 1, 3, 4) P 1 P 2-0 = - P 1 + 3P 2 + 4P 3. 1 K 4. K. 2 : P 3-1 3. P 1 P K. k( 1kK ), k- 1,,. 3., 2. 52 P 1 3 : 2,. ( 1). k( 1kK ), 50

k- 1,. ( 2),,., x 2, d - 1, a 22., 2. 53, 2. 2, 3, 2. 55, 2. 53 cj 0 0 0 P 1 P 2 P 3 0 P 2 0 CB X B b x 1 x 2 x 3 d - 1 d - 2 d - 3 d + 1 d + 2 d + 3 0 x 3 24 5 0 1-3 0 0 3 0 0 24/ 5 0 x 2 0-1 0 0 1 0 0-1 0 0 - P 2 d - 2 26 5 0 0-2 1 0 2-1 0 26/ 5 P 3 d - 3 30 [ 7] 0 0-3 0 1 3 0-1 30/ 7 P 1-1 j P 2 5-2 2-2 P 3 7-3 3-1 2. 54 cj 0 0 0 P 1 P 2 P 3 0 P 2 0 CB X B b x 1 x 2 x 3 d - 1 d - 2 d - 3 d + 1 d + 2 d + 3 0 x 3 18/ 7 0 0 1-6/ 7 0-5/ 7 6/ 7 0 [ 5/ 7] 18/ 5 0 x 2 30/ 7 0 1 0 4/ 7 0 1/ 7-4/ 7 0-1/ 7 - P 2 d - 2 32/ 7 0 0 0 1/ 7 1-5/ 7-1/ 7-1 5/ 7 32/ 5 0 x 1 30/ 7 1 0 0-3/ 7 0 1/ 7 3/ 7 0-1/ 7 - P 1-1 j P 2 1/ 7-5/ 7-1/ 7-2 5/ 7 P 3-1 2. 55 cj 0 0 0 P 1 P 2 P 3 0 P 2 0 CB X B b x 1 x 2 x 3 d - 1 d - 2 d - 3 d + 1 d + 2 d + 3 0 d + 3 18/ 5 0 0 7/ 5-6/ 5 0-1 6/ 5 0 1-0 x 2 24/ 5 0 1 1/ 5 2/ 5 0 0-2/ 5 0 0 15/ 2 P 2 d - 2 2 0 0-1 1 1 0-1 - 1 0 2 0 x 1 24/ 5 1 0 1/ 5-3/ 5 0 0 3/ 5 0 0 - P 1-1 j P 2-1 1-1 - 2 P 3-1 51

2. 55 x 1 = 24/ 5, x 2 = 24/ 5, z = 168/ 5, d - 2 = 2, d + 3 = 18/ 5, d + 1 = d - 1 = d + 2 = d - 3 = 0, 2. 6 C( 24/ 5, 24/ 5). 2. 8. 1DEA 2. 8DE A ( ),..,, ( ) ( ).,, ;,.. 1978 ( A. Charnes) ( W. W. Cooper) ( E. Rh odes) ( t he meth od of dat a envelopment analysis), DEA.. DEA C 2 R,. 1985 C 2 GS. 1986, C 2 W. 1987 C 2 WH.. DEA,.,, ( x 1, x 2, x 3) ( y 1, y 2) 2. 56. 2. 56 x 1( ) 4 15 27 x 2 ( ) 15 4 5 x 3( ) 8 2 4 y 1( ) 60 22 24 y 2( ) 12 6 8,. v x, u r r y r, j 52

3 = 1 2 v x j, r= 1 u ry rj, h j = 2 u ry r j r = 1 3 vx j = 1 v 1, v 2, v 3 u 1, u 2, j hj.. h j ( j = 1, 2, 3) 1, max h j 1., k h k= 1,, ; hk < 1,,,., ( 3 ) : h 1 = max H = h 3, s. t. 60u 1 + 12u 2, h 2 = 40v1 + 15v 2 + 8v3 h j 1, j = 1, 2, 3 u r 0, r = 1, 2, v0, = 1, 2, 3. 22u 1 + 6u 2, h 3 = 15v 1 + 4v 2 + 8v3 24u1 + 8u 2 27v 1 + 5v 2 + 4v3,,,. DEA,.,.,., DEA., C 2 R,. 2. 8. 2C 2 R ( ), m p ( m, p ), 2. 57. 2. 57. 1 2 j 1 v 1 x 11 x 12 x 1j x 1 2 v 2 x 21 x 22 x 2j x 2 m vm x m1 x m2 x mj x m 1 u 1 y 11 y 12 y 1j y 1 2 u 2 y 21 y 22 y 2j y 2 p u p y p 1 y p2 y p j y p 53

: x j j, x j > 0; y rj j r, y rj > 0; v ( ) ; u r r ( ) ; = 1, 2,, m; j = 1, 2,, ; r = 1, 2,, p. x j y rj, ; v u r. V= ( v 1, v 2,, vm) T U= ( u 1, u 2,, u p ) T, h j = p u ry rj r = 1 m, j = 1, 2,,. v x j = 1, V U, : h j 1, j = 1, 2,,. j 0 ( 1j 0), V U, j 0, h j 1, : max h j 0 = p r= 1 u ry rj 0 m v x j 0 = 1, p r = 1 u ry rj m v x j = 1 1, j = 1, 2,,. V = ( v 1, v2,, v m) T 0 U = ( u 1, u 2,, u p) T 0., j 0,., y rj 0y r 0, x j 0x j 0, Yj 0Y0, X j 0X 0,, max VP = UT Y0 V T X 0, ( P ) s. t. U T Yj V T X j 1, j = 1, 2,, V 0, U 0. X j = ( x 1j, x 2j,, x mj ) T, Yj = ( y 1j, y 2j,, y p j ) T, j = 1, 2,,. ( P ),,., 54

t = 1 V T X 0, = tv, = tu, U T Y0 V T X 0 U T Yj V T X j = T Y0 = T Yj 1, j = 1, 2,, T X j T X 0 = 1, 0, 0. ( P ) ( P ) s. t. max VP = T Y0, T X j - T Yj 0, j = 1, 2,, T X 0 = 1, 0, 0. 1( P ) ( P ) : ( 1) V 0, U 0 ( P ), 0 = t 0 V 0, 0 = t 0 U 0 ( P ),, 1 t 0 =. V 0 T X 0 ( 2) 0, 0 ( P ), V 0, U 0 ( P ),. 1 ( P ) 0, 0 VP = 0 T Y0 = 1, j 0 DEA. 2( P ) 0 > 0, 0 > 0 VP = 0T Y0= 1, j 0 DEA., j 0 ( P ) ( D ) s. t. DEA, DEA. min VD =, Xj j + S - = X 0 j = 1 Yj j - S + = Y0 j = 1 j 0j = 1, 2,, S + 0, S - 0,. 2( P ) ( D ) V D = V P 1. 3( D ) ( 1) ( D ) V D = 1, j 0 DEA ;. ( 2) ( D ) V D = 1, 0, S 0-, S 0+, 0, S 0 - = 0, S 0+ = 0, j 0 DEA ;. 22,, K ( ) L( ), Y( ), 2. 58.. 55

2. 58 1( K) v1 1. 5 1 3 2( L) v 2 4 3 7 1( Y) u 1 5 4 8 ( 1) DEA : ( D ) s. t. min V D =, 1. 5 1 + 2 + 3 3 + s - 1 = 1. 5 4 1 + 3 2 + 7 3 + s - 2 = 4 5 1 + 4 2 + 8 3 - s + 3 = 5 j 0, j = 1, 2, 3, s - 1 0, s - 2 0, s + 3 0. ( D ) 0 = ( 0, 1. 25, 0) T, 0 = 0. 93, s 0-1 = 0. 15, s 0-2 = s 0 + 3 = 0. 0 < 1, DEA. ( 2) DEA ( D ) s. t. min V D =, 1. 5 1 + 2 + 3 3 + s - 1 = 4 1 + 3 2 + 7 3 + s - 2 = 3 5 1 + 4 2 + 8 3 - s + 3 = 4 j 0, j = 1, 2, 3, s - 1 0, s - 2 0, s + 3 0. ( D ) 0= ( 0, 1, 0) T, 0 = 1, s 0-1 = s 0-2 = s 0 + 3 = 0., DEA. ( 3) DEA ( D ) s. t. min V D =, 1. 5 1 + 2 + 3 3 + s - 1 = 3 4 1 + 3 2 + 7 3 + s - 2 = 7 5 1 + 4 2 + 8 3 - s + 3 = 8 j 0, j = 1, 2, 3, s - 1 0, s - 2 0, s + 3 0. ( D ) 0= ( 0, 2, 0) T, 0 = 0. 85, s 0-1 = 0. 57, s 0-2 = s 0+ 3 = 0. 0 < 1,, DEA.,,. 2. 9,,.,. 56

2. 9. 1 23, 1 000,, 0. 5 ; 0. 1 0. 002. 50% 0. 5%, 1. 00 ; 10% 0. 4%, 0. 30. 2 500,,,? x 1, x 2,, x 1+ x 2= 71 0000. 5 x 1+ x 2= 3 500., 50% x 1+ 10% x 271 0000. 1, 5x 1+ x 27 000., 5x 1+ 4x 214 000., x 22 500., z= x 1+ 0. 3x 2., : min z = x 1 + 0. 3 x 2, x 1 + x 2 = 3 500 5x 1 + x 2 7 000 s. t. 5x 1 + 4x 214 000 x 2 2 500 x 1, x 2 0. x 1 = 1 000, x 2 = 2 500, z = 1 750. 2. 9. 2 24A, B, C,, 2. 59.,. 2. 59 A B C 1 2 1 430 3 0 2 460 1 4 0 420 ( ) 30 20 50 A, B, C x 1, x 2, x 3,, max Z = 30x 1 + 20x 2 + 50x3, 57

x 1 + 2x 2 + x 3 430 3x1 + 2x 3 460 x 1 + 4x 2 420 x j 0 ( j = 1, 2, 3). x 4, x 5, x 6, : max Z = 30x 1 + 20x2 + 50x 3 + 0x 4 + 0x 5 + 0x6, x 1 + 2x 2 + x 3 + x 4 = 430 3x 1 + 2x 3 + x 5 = 460 x 1 + 4x 2 + x 6 = 420 x j 0 ( j = 1, 2, 3, 4, 5, 6)., 2. 60. 2. 60 cj 30 20 50 0 0 0 CB XB b x 1 x 2 x 3 x 4 x 5 x 6 20 x 2 100-1/ 4 1 0 1/ 2-1/ 4 0 50 x 3 230 3/ 2 0 1 0 1/ 2 0 0 x 6 20 2 0 0-2 1 1 Z 13500 40 0 0 10 20 0, : A, B 100, C 230, 13500. : 10 /, 20 /, 20. ( 1).,.,? 2. 61. 2. 61 3 / 17 / 8 / 16 / b1 b2, B, b1 58 b2. B - 1 = 1/ 2-1/ 4 0 0 1/ 2 0-2 1 1,

B - 1 b= = 1/ 2-1/ 4 0 0 1/ 2 0-2 1 1 b1/ 2-460/ 4 230-2b1 + 880 230 b1 440. b1 0. : 230 440,. 430,,, 440-430= 10. B - 1 b = 1/ 2-1/ 4 0 0 1/ 2 0-2 1 1 440 b2 860. : 860-460= 400. 430 b2 420 460 420 0, 10 /, 10 1010= 100 ; 20 /, 400 20 400= 8 000., 310= 30 17400= 6 800( ), 100-30= 70( ) 8 000-6 800= 1 200( )., 810= 80 16400= 6 400( ), 100-80= 20( ) 8 000-6 400= 1 600( )., 10, 400 70+ 1 600= 1 670( ). ( 2), A,, A. A c1. x 1, x 1 CB B - 1 P 1- c1< 0. ( 10, 20, 0) 1 3 1 - c1 < 0, c1 > 70. A 70.? ( 3), B 60, x 260, x 7 x 2+ x 7= 60, 2. 61, 2. 62,. 2. 63. A, B 60, C 230, 12 700, 800. 59

( 2. 63), 10 / 0 /.,, 80.,, 20 / 25 /.,.. 80 180. 2. 62 cj 30 20 50 0 0 0 0 C B X B b x 1 x 2 x 3 x 4 x 5 x 6 x 7 20 x 2 100-1/ 4 1 0 1/ 2-1/ 4 0 0 50 x 3 230 3/ 2 0 1 0 1/ 2 0 0 0 x 6 20 2 0 0-2 1 1 0 0 x 7-40 1/ 4 0 0-1/ 2 1/ 4 0 1 Z 13500 40 0 0 10 20 0 0 2. 63 cj 30 20 50 0 0 0 0 CB XB b x 1 x 2 x 3 x 4 x 5 x 6 x 7 20 x 2 60 0 1 0 0 0 0 1 50 x 3 230 3/ 2 0 1 0 1/ 2 0 0 0 x 6 180 1 0 0 0 0 1-4 0 x 4 80-1/ 2 0 0 1-1/ 2 0-2 Z 12700 45 0 0 0 25 0 20 100,. 2. 9. 3 25,., 15%, ;, 45%,, 2 ;, 65%,, 1. 5 ;,, 35%, 1. 3, (, )?,, x j j, = 1, 2, 3; j = 1, 2, 3, 4..,, 3., 60

x 1 1 + x 12 = 3., 2, x 122.,, 1. 15x 11,,,, x 2 1+ x 2 3-1. 15x 1 1= 0., 1. 5, x 231. 5.,, 1. 45x 12,, 1. 15x 21,,,, x 31+ x 3 4-1. 45x 1 2-1. 15x 2 1= 0., 1, x 341.,. 1. 65x 23, 1. 15x 311. 35x 34., max z = 1. 65x 23 + 1. 15x 31 + 1. 35x 34, x 11 + x 1 2 = 3 x 12 2 x 21 + x 2 3-1. 15x 11 = 0 s. t. x 23 1. 5 x 31 + x 3 4-1. 45x 12-1. 15x 21 = 0 x 34 1 x j 0 = 1, 2, 3; j = 1, 2, 3, 4. 2. 9. 4 26100 85, A, B, C 55, 60, 70( ).,, ( ) 2. 64, 2. 65, 2. 66, ( ). 2. 64 0 12 10 0 2. 65 A B C 10 14 12 15 12 18 2. 66 A B C A 0 14 11 B 10 0 4 C 8 12 0 61

,,., : ( 1) Q; ( 2) Q ; ( 3) A Q a+ Q ; ( 4) Bj Q bj + Q ;,,. 185, Q 185., A, B, C. 2. 67,, 2. 68, 2 210. 2. 67 A B C 0 12 10 14 12 285 10 0 15 12 18 270 A 10 15 0 14 11 185 B 14 12 10 0 4 185 C 12 18 8 12 0 185 185 185 240 245 255 2. 68 A B C 185 55 45 285 185 85 270 A 185 185 B 160 25 185 C 185 185 185 185 240 245 255 2. 9. 5 27,,,. 2. 69.,, 1 8%. : ( 1) 550 ; ( 2) ; ( 3), 18% ; ( 4) 20%, ; ( 5) 4. 2. 69 ( ) 1 2 3 4 ( ) 8 6 4 3 10 20 40 30 10 22 52 30,? x 1, x 2, x 3, x 4 1, 2, 3, P 1, P 2, P 3 P 4 : 62

P 1 550 ; P 2 ; P 3 18% ; P 4 20%, ; : ( 1) 550 8( 10-108% + x 1) + 6( 20- x 1+ x 2) + 4( 40- x 2+ x 3) + 3( 30- x 3+ x 4) + d - 1 - d + 1 = 550. ( 2) 1 10-108% + x 1 + d - 2 - d + 2 = 10, 2 20- x 1+ x 2 + d - 3 - d + 3 = 22, 3 40- x 2+ x 3 + d - 4 - d + 4 = 52, 4 30- x 3+ x 4 + d - 5 - d + 5 = 30. ( 3) 18% 2 x 1+ d - 6 - d + 6 = 2218%, 3 x 2+ d - 7 - d + 7 = 4018%, 4 x 3+ d - 8 - d + 8 = 3018%. ( 4) 20%, x 1+ x 2+ x 3+ d - 9 - d + 9 = 10020%. : min Z= P 1d + 1 + P 2( d + 2 + d + 3 + d + 4 + d + 5 ) + P 3( d - 6 + d - 7 + d - 8 ) + P 4( d + 9 + d - 9 ). 2. 9. 6 281997,. ( ), ( ) ( ) ; ( ) ( ). 2. 70( 1997 ). 2. 70 932. 66 583. 08 936. 84 1306. 56 980. 45 581. 64 849. 31 1444. 30 401. 8 294. 2 443. 20 461. 00 179. 29 49. 76 144. 20 181. 41 2196. 09 930. 22 1659. 04 2662. 21 1. 0000 0. 7140 0. 9285 1. 0000 1 3 2 1 63

, DEA min V D =, 932. 66 1+ 583. 08 2+ 936. 84 3+ 1306. 56 4+ s - 1 = 936. 84 980. 45 1+ 581. 64 2+ 849. 31 3+ 1444. 40 4+ s - 2 = 849. 31 s. t. 401. 8 1+ 294. 2 2+ 443. 20 3+ 461. 00 4+ s - 3 = 443. 20 179. 29 1+ 49. 76 2+ 144. 20 3+ 181. 41 4- s + 1 = 144. 20 2196. 09 1+ 930. 22 2+ 1659. 04 3+ 2662. 21 4- s + 2 = 1659. 04 j 0, j = 1, 2, 3, 4, s - 0= 1, 2, 3, s + r 0r = 1, 2. = 0. 9285, 1= 0. 8043, 2= 3= 4= 0, s - 1 = 119. 71, s - 2 = 0, s - 3 = 88. 17, s + 1 = 0, s + 2 = 107. 24.. 2. 1, ( 1) max Z= 2x 1+ 3x2, ( 2) min Z = - x 1- x 2, ( 3) m ax Z= x 1+ x 2, x 1+ 2x28 x 1- x 2-1 x 1- x 21 s. t. x 1 4 x 2 3 s. t. 0. 5x 1 + x 2 2 x 1, x 2 0. s. t. 3x 1 - x 2-3 x 1, x 2 0. x 1, x 2 0. 2. 2. ( 1) max Z= 2x 1-3x2+ x 3, x 1 - x 2 + x 3 5 s. t. 4x 1 - x 2 + 3x 3 = 6 3x 1+ x 2+ x 310 x 1, x 20, x 3. ( 2) min Z = 2x 1- x 2+ 2x 3, - x 1 + x 2 + x 3 = 4 s. t. - x 1 + x 2-2x 3 8 x 1 0, x 2 0, x 3. ( 3) max Z= - x - y, x + y2 s. t. x 3 x, y. 2. 3,. ( 1) max Z= 2x 1+ 3x2+ 4x 3+ 7x 4, 2x 1 + 3x 2 - x 3-4x 4 = 8 s. t. x 1-2x 2 + 6x 3-7x 4 = - 3 x 1, x 2, x 3, x 4 0. ( 2) min Z = 5x 1-2x 2+ 3x 3-6x 4, 64

. s. t. x 1+ 2x2+ 3x 3+ 4x 4= 7 2x 1 + x 2 + x 3 + 2x 4 = 3 x 1, x 2, x 3, x 4 0. 2. 4, ( 1) max Z= x 1+ 2x 2, s. t. 3x 1+ x 227 4x 1 + 3x 2 36 x 1, x 2 0. 2. 5: ( 1) max Z = - x 1+ 2x 2+ x 3, s. t. 2x 1+ x 2+ x 34 x 1+ 2x26 x 1, x 2, x 3 0. ( 2) min Z = - 3x 1+ x 2, s. t. - x 1 + x 2 2 3x 1 - x 26 x 1, x 20. ( 3) max Z = 3x 1+ 5x 2+ x 3, s. t. - 4x 1 + 2x 2 + x 3 14 - x 1 + x 2 - x 3 4 ( 2) min Z= - 2x 1-3x 2, s. t. x 1+ 2x 26 3x 1 + x 2 15 x 1, x 2 0. x 1, x 2, x 30. 2. 6M,. ( 1) min Z = 2x 1+ 5x 2, s. t. 2x 1 + x 2 + x 3 6 x 2+ 3x 39 x 1, x 20. ( 2) max Z= x 1+ 2x 2+ 3x 3, s. t. 5x 1 + 3x 2 + x 3 9-5x 1 + 6x 2 + 15x 3 15 2x 1+ x 2 + x 3 5 x 1, x 2, x 30. 2. 7: ( 1) max Z = 5x 1+ 2x 2+ 3x 3, s. t. x 1+ 5x2+ 2x 3= 30 x 1-5x2- x 1, x 2, x 3 0. 6x 340 ( 2) min Z = 5x 1-5x 2-13x 3, s. t. - x 1 + x 2 + 3x 3 20 12x 1+ 4x 2+ 10x 390 x 1, x 2, x 30. 2. 8. ( 1) max Z= 2x 1+ x 2+ 5x 3, 65

s. t. 2x 1+ 3x 2+ 5x 32 3x 1 + x 2 + 7x 3 3 x 1 + 6x 3 5 x 1, x 2, x 3 0. ( 2) max Z= x 1+ x 2+ x 3, s. t. 2x 1 + x 2 + 5x 3 12 x 1 + 2x 2 + 7x 3 = 6 x 1 + 6x 3 4 x 1, x 2, x 3 0. ( 3) min Z = 4x 1 + 2x 2 + 3x 3, s. t. 2x 1 + x 2 + 5x 3 6 x 1 + 2x 2 + 7x 3 = 4 x 1 + x 3 2 x 1, x 20, x 30. 2. 9. ( 1) min Z = x 1 + x 2, s. t. 2x 1 + x 2 4 x 1 + 7x 3 7 x 1, x 2 0. ( 2) max Z = 2x 1 - x 2 + x 3, s. t. 2x 1 + 3x 2-5x 3 4 - x 1 + 9x 2 - x 3 3 4x 1+ 6x 2+ 3x 38 x 1, x 2, x 30. 2. 10 max Z = - 5x 1 + 5x 2 + 13x 3, s. t. - x 1 + x 2 + 3x 3 20 12x 1 + 4x 2 + 10x 3 90 x 1, x 2, x 30.,,? ; ( 1) 20 30; ( 2) 90 70; ( 3) x 3 13 8; ( 4) x 1-1 0 12 5 ; ( 5) 10x 1+ 5x 2+ 10x 3100 ; ( 6) 2x 1+ 3x 2+ 5x 350. 2. 11, : : ( ), ( ), ( ) ; : 100 ; : 30 000 ; : 30 ; : 1 10/ 3, 1 40/ 3, 1 79/ 3 66

: 2 3 1 ;. 20, 1000,? 2. 12,. 2. 132. 71( a) ( b) ( c),? 2. 71( a) B 1 B 2 B 3 B 4 B 5 B 6 A 1 20 5 25 A 2 25 30 55 A 3 15 15 40 10 80 A 4 20 20 20 30 45 15 40 30 ( b) B 1 B 2 B 3 B 4 B 5 B 6 A 1 30 30 A 2 10 25 35 A 3 15 25 5 20 65 A 4 20 20 10 40 25 5 50 20 ( c) B 1 B 2 B 3 B 4 A 1 6 4 10 A 2 4 8 6 18 A 3 2 9 11 4 10 15 10 2. 14. ( 1) 2. 72 B 1 B 2 B 3 B 4 B 1 B 2 B 3 B 4 A 1 3 2 2 2 1 A 2 6 10 8 5 4 A 3 6 7 6 6 8 4 3 4 4 67

( 2) 2. 73 B 1 B 2 B 3 B 1 B 2 B 3 A1 12 5 1 8 A 2 14 2 4 0 A3 4 3 6 7 9 10 11 2. 15 100,,.,, 2. 74,? 2. 74 B 1 B 2 B 3 B 1 B 2 B 3 A 1 100 600 700 500 A 2 500 800 500 850 A 3 400 400 150 300 200 300 500 2. 163 3. 3 3 000, 5 000 4 000. 1 4 000, 4. j 2. 75.? 2. 75 j B 1 B 2 B 3 B 4 A1 15 13 12 14 A2 18 17 15 12 A3 13 10 9 10 2. 17. ( 1) min Z = P 1( d - 1 + d + 1 ) + P 2( d - 2 + d - 3 ), 15x 1 + 25x 2 + d - 1 - d + 1 = 600 s. t. x 1+ 3x2+ d - 2 - d + 2 = 60 x 1 + 3x 2 + d - 3 - d + 3 = 40 x 1, x 2 0, d + 0, d - 0, = 1, 2, 3. ( 2) min Z = P 1 d - 1 + P 2 d - 2, x 1 - x 2 + d - 1 - d + 1 = 50 s. t. 2x 1 + 3x 2 + d - 2 - d + 2 = 0 x 1 + x 2 1 000 x 1, x 2 0, d + 0, d - 0, = 1, 2. 2. 18. 68

( 1) min Z = P 1d - 1 + P 2d + 2 + P 3( d - 3 + d + 3 ), s. t. 3x 1 + x 2 + d - 1 - d + 1 = 60 x 1- x 2+ 2x 3+ d - 2 - d + 2 = 10 x 1 + x 2 - x 3 + d - 3 - d + 3 = 20 x 0, d + 0, d - 0 ( = 1, 2, 3). ( 2) min Z = P 1d - 1 + P 2d + 4 + 5P 3d - 2 + 3P 3d - 3 + P 4d + 1, s. t. x 1 + x 2 + d - 1 - d + 1 = 80 x 1 + d - 2 - d + 2 = 60 x 2+ d - 3 - d + 3 = 45 x 1 + x 2 + d - 4 - d + 4 = 90 x 1, x 2 0; d + 0, d - 0 ( = 1, 2, 3, 4). 2. 19, A, B, C., 6, 8 10. 200 ;, 500, 650 800. 12, 10 6. : P 1: 1. 610 4 ; P 2: ; P 3 : 24 ; P 4: ;,. 2. 20 3,,,. 1 500. j 2. 76 ( = 1, 2; j = 1, 2, 3). 2. 76 1 2 3 1 10 4 12 3000 2 8 10 3 4000 2000 1500 5000 6 : ( 1) 3. ( 2) 75%. ( 3). ( 4) 2 1, 1 000. ( 5) 1 3 2 1,. ( 6) 1 2. 2. 21( ) : ( 1) 100, 160 400, A B. A 1, 2, 2, 100 ; B 1, 1, 5, 150.,? ( 2). 5 000., 69

1 000, 20 000. 2. 77. 2. 77 ( ) ( ) 2. 85 3. 10 3. 05 3. 25 2. 90 2. 95,,. 2 000, 3? 70

3 31 2,,.,,.,,,,.,.,., ( ). : x 1, x 2,, x, Z = cj x j j = 1, a j x j b( = 1, 2,, m) j = 1 x j 0 ( j = 1, 2,, ) x j.,., ( 01 ), ( 1 ) ( 0 ). 01 01.,.,.,.,, ( ),,?,,,.,.,.,,,,. X, X, X, d. cx cx cx, cx - cx cx - cx. 71

cx - cx d, X X.,,,?,.., 35, = 10, 10! > 310 6, = 20, 20! > 210 1 8,,,,.,., 01,. 32 1. 1A 1, A 2, B 1, B 2. 3. 1. A 1, A 2,? 3. 1 B 1 B 2 ( ) A 1 6 1 15 A 2 4 3 20 25 10 x 1, x 2 A 1 A 2,, max Z = 15x 1 + 20x2, 6x 1 + 4x 2 25 x 1 + 3x 2 10 x 1 0, x 2 0,.,,. 2. 25, 3. 2, A, C, E, ; B D, ; C D, C D. 15,,? 72

3. 2 ( ) ( ) A 6. 0 10. 0 B 4. 0 8. 0 C 2. 0 7. 0 D 4. 0 6. 0 E 5. 0 9. 0,, x j ( j = 1, 2, 3, 4, 5) A, B, C, D, E, x j = 0j 1j ( j = 1, 2, 3, 4, 5). A, C, E, x 1+ x 3+ x 5= 1., B D x 2+ x 4= 1. C D, C D, D C., x 3= 1, x 4= 1; x 3= 0, x 4= 0 x 4= 1.,, x 3x 4( x 3- x 40). 6x 1+ 4x2+ 2x 3+ 4x 4+ 5x 515. max Z= 10x 1+ 8x 2+ 7x 3+ 6x 4+ 9x 5. max Z= 10x 1+ 8x 2+ 7x 3+ 6x 4+ 9x 5, x 1+ x 3+ x 5= 1 x 2+ x 4= 1 x 3- x 40 6x 1+ 4x 2+ 2x 3+ 4x 4+ 5x 515 x j 0 1, ( j = 1, 2,, 5)., 1, 0 1., 01., 01.. m x 1, x 2,, x, max Z = cj x j, ( 31) j = 1 73

, cj a j x j b( = 1, 2,, m) j = 1 x j = 0 1( j = 1, 2,, ). ( 32) ( 33) j, a j j, b. k( k),, ( 32) k x j = 1. j = 1 k( k), ( 32) k x j 1. j = 1, k. k( k),, ( 32) k x j 1. j = 1 j, ( 32) x j x. j,, ( 32) x = x j ( j ). r t, br, ( 32) r t bt ar j x j br + ym j = 1 at j x j bt + ( 1 - y) M. j = 1 y 01, M., y = 0, r,., x j r. y = 1, x j,,,,.,, y 0 1. m k( 1< k< m), ( 32) a j x j b+ ( 1 - y ) M( = 1, 2,, m) j = 1 m y k. = 1 y 01, M, k. 74

,, 01,. 3. 3A 1, A 2, A 3, A 4, B 1, B 2, B 3, B4., 3. 3.,? 3. 3 A1 A2 A3 A4 B 1 B 2 B 3 B 4 3 14 10 5 10 4 12 10 9 14 15 13 7 8 11 9,, x j (, j = 1, 2, 3, 4) A B j, x j = 1 A Bj 0 A Bj, min Z = 3x 11 + 14x 1 2 + 10x 13 + 5x 14 + 10x 21 + 4x 22 + 12x 2 3 + 10x 24 + 9x 31 + 14x 32 + 15x 3 3 + 13x 34 + 7x 41 + 8x 42 + 11x 43 + 9x 44 x 11 + x 12 + x 1 3 + x 14 = 1 x 21 + x 22 + x 2 3 + x 24 = 1 x 31 + x 32 + x 3 3 + x 34 = 1 ( A ) x 41 + x 42 + x 4 3 + x 44 = 1 x 11 + x 21 + x 3 1 + x 41 = 1 x 12 + x 22 + x 3 2 + x 42 = 1 x 13 + x 23 + x 3 3 + x 43 = 1 ( B j ) x 14 + x 24 + x 3 4 + x 44 = 1 x j = 0 1(, j = 1, 2, 3, 4). 01.,, 35. 33, 75

,,. :,., Z.,.,, x ( b ), x [ b ] x [ b ] + 1,,.,, Z.,,,. Z Z,,. 1. ( 1),, x 1 = 25, x 2 = 25, 3. 4 ( ) ( 31 B ) Z= 875, Z= 0. 3. 1 ( 2) x 1, x 2 ( x 1= 25), x 12 x 13,, ( 1) ( 2), ( 1) max Z= 15x 1+ 20x 2, 6x 1+ 4x 225 x 1+ 3x 210 x 12 x 1, x 20. ( 2) max Z= 15x 1+ 20x 2, 6x 1+ 4x 225 x 1+ 3x 210 x 13 x 1, x 20., R 1 ( 2< x 1< 3). R2, 31., ( 3) ( 1). ( 2),. 3. 4 ( ) ( ) ( ). ( 1), x 1= 2, x 2= 267 max Z= 833. 76

3. 4 Cj 15 20 0 0 0 CB XB b x 1 x 2 x 3 x 4 x 5 ( ) 15 x 1 5/ 2 1 0 3/ 14-2/ 7 20 x 2 5/ 2 0 1-1/ 14 3/ 7 Z 175/ 2 0 0 25/ 14 30/ 7 15 x 1 5/ 2 1 0 3/ 14-2/ 7 0 ( ) 20 0 x 2 x 5 5/ 2-1/ 2 0 0 1 0-1/ 14 [ - 3/ 14] 3/ 7 2/ 7 0 1 Z 175/ 2 0 0 25/ 14 30/ 7 0 15 x 1 2 1 0 0 0 1 ( ) 20 0 x 2 x 5 8/ 3 7/ 3 0 0 1 0 0 1 1/ 3-4/ 3-1/ 3-14/ 3 Z 250/ 3 0 0 0 20/ 3 25/ 3 ( 1) x 2,, ( 1) x 22 x 23, ( 1), ( 3) ( 4), ( 3) max Z= 15x 1+ 20x 2, 6x 1+ 4x 225 x 1+ 3x 210 x 12 x 22 x 1, x 20. ( 4) max Z= 15x 1+ 20x 2, 6x 1+ 4x 225 x 1+ 3x 210 x 12 x 23 x 1, x 20. ( 4) ( 4),, ( 3), x 1 = 2, x 2= 2 max Z= 70.,.,, 70( Z= 70 ( 3) ).,, Z= 70.,, Z= max{0, 70}= 70. ( 5),,. ( 4), x 1= 1, x 2= 3 max Z= 75., ( 4), Z= max{70, 75}= 75. 32. ( 6) ( 2), x 1= 3, x 2= 175 max Z= 80. x 2, Z= 80> Z= 75,, ( 2), ( 5) ( 6). 77

( 5) max Z= 15x 1+ 20x 2, 6x 1+ 4x 225 x 1+ 3x 2 10 x 13 x 21 x 1, x 20. ( 6) max Z= 15x 1+ 20x 2, 6x 1+ 4x 225 x 1+ 3x 2 10 x 13 x 22 x 1, x 20. ( 7) ( 5), x 1= 35, x 2= 1 max Z= 725( 33). Z = 725< Z = 75,.,. ( 8) ( 6),,. 3. 2 3. 3 78

,,,, x 1 = 1, x 2 = 3. Z = 75. 33,.,, ( ),,. 33 ( 3) ( 4) ( 5),,,..,. 34 79

, 1 : ( 1). ( 2),,. ( 33 ( 6) ).,,., ( 33 ( 3) ( 4) ).,, ( 33 ( 5) ).,, ( 33 ( 2) ). 3. 4.,,.,..,,,,,.,,, 4. 3401 01,,, 341, 0 1 ( ),, ( ),,,. 4. 401 : max Z= 17x 1+ 10x 2+ 16x 3, 4x 2+ 2x 36 5x 1+ x 2+ 2x 36 4x 1-2x 2+ 3x37 5x 1+ 2x 2+ 3x37 x j = 0 1( j = 1, 2, 3). ( 1) ( x 1, x 2, x 3 ), 2 3 = 8 : ( 0, 0, 0) ( 0, 0, 1) ( 0, 1, 0) ( 0, 1, 1) ( 1, 0, 0) ( 1, 0, 1) ( 1, 1, 0) ( 1, 1, 1). ( 2)., ( x 1, x 2, x 3) = 80

( 0, 0, 0),, Z= 0.,, Z 0, 17x 1 + 10x 2 + 16x3 0. A A. A. ( 3)., A 3. 5, 5.,, ;,,.,, Z,. 3. 5, ( 0, 0, 1), Z= 16, A. 3. 5 ( x 1, x 2, x 3) 17x 1+ 10x 2+ 16x 316. A Z ( 0, 0, 0) 0 ( 0, 0, 1) 16 ( 0, 1, 0) ( 0, 1, 1) 26 ( 1, 0, 0) ( 1, 0, 1) ( 1, 1, 0) 27 ( 1, 1, 1) A ( 1, 1, 0), Z= 27,. 17x 1+ 10x 2+ 16x 327.,. 3. 5, ( x 1, x 2, x 3) = ( 1, 1, 0), Z = 27, 4,,., x j A (, Z= 10x 2+ 16x 3 + 17x 1),,,, 3. 6. 01 35., 01,,. 81

3. 6 ( x 2, x 3, x 1) A Z ( 0, 0, 0) 0 ( 0, 0, 1) 17 ( 0, 1, 0) ( 0, 1, 1) ( 1, 0, 0) ( 1, 0, 1) 27 ( 1, 1, 0) ( 1, 1, 1) 3501 82

342 01. 0 1,,. 01., 01 : max S = Cj X ( Cj 0), = 1 aj x j b( = 1, 2,, m) = 1 x j = 0 1( j = 1, 2,, ). ( 1), - 1, ; ( 34) ( 2) x j Cj > 0, x j = 1- y j x j, y j 01, y j Cj 0; ( 3), - 1, ; ( 4),., j = 1 a j x j = b aj x j = 1 - b a j x j - b. k a j x j = b( = 1, 2,, k), ( k+ 1) = 1 : a j x j b( = 1, 2,, k) = 1 k - = 1 j = 1 aj x j - b. 01 ( 34). 01 : 0(,, S = 0 ).,, ;, 0 1, ( ),., ( ), 0,., ( ),, ;,,.,,,, 0 1,.,,,. 4,. ( 1) 4. k = 1 83

x 1= 1- y 1, x 2= 1- y 2, x 3= 1- y 3,, max Z = 43-17y1-10y 2-16y 3, - 4y2 - y 30-5y 1 - y 2-2y 3-2 - 4y 1+ 2y2-3y 32-5y 1-2y2-3y 3-3 y 1, y 2, y 3 0 1. max Z= 43+ max S, S = - 17y 1-10y 2-16y 3. : ( 2) y 1, y 2, y 3 max S = - 17y1-10y 2-16y 3, - 4y2-2y 30-5y 1 - y 2-2y 3-2 - 4y 1+ 2y2-3y 32-5y 1-2y2-3y 3-3 y 1, y 2, y 3 0 1., ( y 1, y 2, y 3) = ( 0, 0, 0),,,, S = 0, S= 0.., 1,,. 1,?,.,,. y 1= 1, 0, - 40-200, 0-51- 10-20- 2, 0-41+ 20-302, 0-51- 20-30- 3. y 2= 1, 0. 0 = 0-41- 200, 0-50- 11-20 \ - 2, 1-40+ 21-302, 0-50- 21-30 \ - 3. y 3= 1, 0, 1 = 2 84

- 40-210, 0-50- 10-21- 2, 0-40+ 20-312, 0 0-50- 20-31- 3. = 0 y 1= 1 y 3= 1. C1= - 17< C3= - 16,, C3 C1 S,, y 3= 1 y 3= 0, : ( 1) ( y 3= 1) max S = - 16-17y1-10y 2, - 4y 22-5y 1- y 20-4y 1+ 2y25-5y 1-2y20 y 1, y 2 0 1. ( 2) ( y 3= 0) max S = - 17y1-10y 2, - 4y 20-5y 1- y 2-2 - 4y 1+ 2y22-5y 1-2y2-3 y 1, y 2 0 1. ( 3) ( 1). y 1= y 2= 0, ( 1),,, ( y 1, y 2) = ( 0, 0), y 3= 1, ( y 1, y 2, y 3) = ( 0, 0, 1), S= - 16, S = - 16,. ( 4) ( 2). y 1= y 2= 0, ( y 1, y 2) = ( 0, 0). ( 2)? y j : ( a), ; ( b), Cj. Cj > S - Cy ( K ). K ( a), 1., ( a). ( b), 1,,, ( )., ( 2), y 1, y 2,, y 2 C1 = - 17-16 - ( - 160) = - 16, C2 = - 10 > - 16 - ( - 160) = - 16. ( a ) ( b ),, y 2= 1 y 2= 0, 3. 6 85

86 3. 701

( 2) : ( 3) ( y 2= 1) max S = - 10-17y1, - 5y 1-1 - 4y 10-5y 1-1 y 1 0 1. ( 4) ( y 2= 0) max S = - 17y1, - 5y 1-2 - 4y 12-5y 1-3 y 1 0 1. ( 5) ( 3). y 1= 0,. y 1= 1, ( a ), ( b), S> S= - 16, ( 3). ( 4). ( 3),. ( 6),,., S = - 16( y 1, y 2, y 3) = ( 0, 0, 1). x 1= 1- y 1, x 2 = 1 - y 2, x 3= 1- y 3, max Z = 43+ max S, ( x 1, x 2, x 3) = ( 1, 1, 0), max Z= 27. 36. 01 3. 7 35 : ( ) A 1, A 2,, A, B1, B 2,, B,,. A B j ( ) Cj,,? X j A B j, X j = min Z = 1 A B j 0 A B j = 1 j = 1 Cj X j ( Cj X j = 1( = 1, 2,, ) j = 1 X j = 1( j = 1, 2,, ) = 1 X j 0 1., 0), Cj C= ( Cj ). C.., ( DKo nig),. : ( Cj ) ( ) 87

k ( k, ) ( bj ), ( bj ), k.. 4,. : ( Cj ), ( bj )., ( Cj ). 4, = 4, - 4-2 ( Cj ) = 3 14 10 5 10 4 12 10 9 14 15 13-3 - 4-9 0 11 7 2 6 0 8 6 0 5 6 4 0 11 3 0 6 0 4 4 0 5 2 2 = ( bj ). 7 8 11 9-7 0 1 4 2 0 1 0 0 :. ( bj ), ( ),,,, ; ( ) ( ), ( )., ( bj ).,, 1, 0,,. 4, ( bj ) = 4=, ( x j ) = 11 3 6 4 4 5 2 2 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 A 1 B4, A 2 B 2, A 3 B 1, A 4 B 3. Z = 4 = 1 j = 1. <,. 4 Cj x j = 5 + 4 + 9 + 11 = 29. 53. 7. 1, 2 88 ( Cj ) = 12 7 9 7 9 8 9 6 6 6 7 17 12 14 12 15 14 6 6 10 4 10 7 10 6. - 7-6 - 7-6 - 4. 1

5 0 2 0 2 2 3 0 0 0 5 2 2 2 3 0 10 5 7 5 9 8 0 0 4 2 10 5 7 5 9 8 4 = ( bj ) 0 6 3 6 2 6 3 6 2 3. 7 B 1 B 2 B 3 B 4 B 5 A 1 12 7 9 7 9 A 2 8 9 6 6 6 A3 7 17 12 14 12 A4 15 14 6 6 10 A5 4 10 7 10 6 4, = 5,. 3 :. : ( 1) ; ( 2) ; ( 3) ; ( 4) ( 2) ( 3), ; ( 5),,.. 5, 5, 1, 3, 1, 2, 4, 1 : 5 2 2 2 3 10 5 7 5 9 8 4 6 3 6 2 4 : ( bj ),. :,,,, 2. 5 4 : 89

5 2 2 7 0 2 0 2 2 3 4 3 0 0 0 10 5 7 5-2 0 8 3 5 3 9 8 4 11 8 0 0 4 6 3 6 2-2 0 4 1 4 0 + 2 7 2 2 5=, ( x j ) = 4 3 8 3 5 3. 11 8 4 4 1 4 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0. 0 0 1 0 0 0 0 0 0 1 A 1 B 2, A 2 B 4, A 3 B 1, A 4 B 3, A 5 B 5. Z = ( 7+ 6+ 7+ 6+ 4) + ( 2+ 2-2) = 32.,, ( ), ( ),., max Z = = 1 j = 1 max {cj }, ( M- Cj ). M- Cj 0. = 1 j = 1 ( M - Cj ) X j = MXj - = 1 j = 1 = M - Cj X j. = 1 j = 1 Cj X j, Cj = M - Cj, M = Cj X j = 1 j = 1, min ( M - Cj ) Xj max = 1 j = 1 max Z= Cj X j = 1 j = 1 Cj X j = 1 j = 1 = M - min ( M - Cj ) X j = 1 j = 1.,,, ( ),. 36 6( ), 90