5 1! (Linear Programming, LP) LP OR LP 1.1 1.1.1 1. 2. 3. 4. 4 5. 1000 4 1.1? 1.2 1 1 http://allrecipes.com/
6 1 1.1 ( ) () 1 0.5 1 0.75 200 () 1.5 1 0.5 1 50 ( ) 2 2 1 30 () 2.25 0.5 2 2.25 30 () 2 100 () 0.33 240 () 0.5 50 24 12 14 18 1 25.1 25.4 20.4 17.9 1.2 10 5 15 120 10 25 35 20 40 20 1.1.2 ( ) 1. 2. 1000 3. 40 4. 20
1.1. 7 x 1 x 2 x 3 x 4 z z = 25.1x 1 + 25.4x 2 + 20.4x 3 + 17.9x 4 x 1 + x 2 + x 3 + x 4 = 1000 24 24 10 10 48 20 20 10 x 1 24 + 5 x 2 12 + 15 x 3 14 + 120 x 4 40 60 18 0.417x 1 + 0.417x 2 + 1.071x 3 + 6.667x 4 2400 0.417x 1 + 2.083x 2 + 2.50x 3 + 1.111x 4 1200 min. z = 25.1x 1 + 25.4x 2 + 20.4x 3 + 17.9x 4 s.t. x 1 + x 2 + x 3 + x 4 = 1000 0.417x 1 + 0.417x 2 + 1.071x 3 + 6.667x 4 2400 0.417x 1 + 2.083x 2 + 2.50x 3 + 1.111x 4 1200 x j 0, j = 1,..., 4 (1.1) \ x j 0, j = 1,..., 4 " x 1 0, x 2 0, x 3 0, x 4 0 () ( ) (1.1) 1 1 (linear programming problem) (linear programming)
8 1 (1.1) x 1 = 432.0 x 2 = 0.0 x 3 = 280.0 x 4 = 288.0 z = 21705.0 0 4 12 15 1 1 15 (1.1) 2 3 x 2 0.417 0.333 2.083 1.667 x 1 = 229.6 x 2 = 447.1 x 3 = 0.0 x 4 = 323.3 z = 20647.6 x 3 0 4 4 100 x 1 100, x 2 100, x 3 100, x 4 100 min. z = 25.1x 1 + 25.4x 2 + 20.4x 3 + 17.9x 4 s.t. x 1 + x 2 + x 3 + x 4 = 1000 0.417x 1 + 0.417x 2 + 1.071x 3 + 6.667x 4 2400 0.417x 1 + 2.083x 2 + 2.50x 3 + 1.111x 4 1200 x j 100, j = 1,..., 4 (1.2) x 1 = 406.2 x 2 = 100.0 x 3 = 197.1 x 4 = 296.7 z = 22067.3 1.1 300 50 1.2 2 100 1.2 1.2.1 ( ) f(x) x X (1.3)
1.2. 9 f(x) X x (1.3) X x f(x) ( ) x x 1 1 1 1.2.2 (standard form) maximize c 1 x 1 + c 2 x 2 + + c n x n subject to a 11 x 1 + a 12 x 2 + + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + + a 2n x n = b 2. a m1 x 1 + a m2 x 2 + + a mn x n = b m x 1 0, x 2 0,..., x n 0 (1.4) b 1,..., b m (right hand side) a ij (i = 1,..., m; j = 1,..., n) a 11 a 12 a 1n a 21 a 22 a 2n..... a m1 a m2 a mn x 1 0, x 2 0,..., x n 0 (nonnegativity constraint) (x 1,..., x n ) (feasible solution) (optimal solution) (1.4)) \ " maximize subject to n c j x j j=1 n a ij x j = b i, j=1 x j 0, i = 1,..., m j = 1,..., n (1.5)
10 1 maximize subject to c x Ax = b x 0 (1.6) x = x 1. x n c = c 1. c n b = b 1. b m A = a 11 a 12 a 1n a 21 a 22 a 2n..... a m1 a m2 a mn 2 maximize c 1 x 1 + c 2 x 2 + + c n x n subject to a 11 x 1 + a 12 x 2 + + a 1n x n b 1 a 21 x 1 + a 22 x 2 + + a 2n x n b 2. a m1 x 1 + a m2 x 2 + + a mn x n b m x 1 0, x 2 0,..., x n 0 x n+1, x n+2,..., x n+m (1.7) maximize c 1 x 1 + c 2 x 2 + + c n x n subject to a 11 x 1 + a 12 x 2 + + a 1n x n + x n+1 = b 1 a 21 x 1 + a 22 x 2 + + a 2n x n + x n+2 = b 2. a m1 x 1 + a m2 x 2 + + a mn x n + x n+m = b m x 1 0,..., x n 0, x n+1 0,..., x n+m 0 (1.8) (1.9) x 1 maximize c 1 x 1 + c 2 x 2 + + c n x n subject to a 11 x 1 + a 12 x 2 + + a 1n x n = b 1 a 21 x 1 + a 22 x 2 + + a 2n x n = b 2. a m1 x 1 + a m2 x 2 + + a mn x n = b m x 2 0,..., x n 0 (1.9) x 1 = x + 1 x 1 ( x + 1 0, x 1 0) 2 c = (c 1,..., c n )
1.3. 11 (1.9) maximize c 1 x + 1 c 1x 1 + c 2x 2 + + c n x n subject to a 11 x + 1 a 11x 1 + a 12x 2 + + a 1n x n = b 1 a 21 x + 1 a 21x 1 + a 22x 2 + + a 2n x n = b 2. a m1 x + 1 a m1x 1 + a m2x 2 + a mn x n = b m x + 1 0, x 1 0,..., x n 0 (1.10) 1.3 max 3x 1 + 2x 2 4x 3 s.t. x 1 + x 3 2 x 1 + 2x 2 + x 3 5 x 1 0, 4 x 2 5, x 3 0 1.4 max x 1 + x 2 + x 3 s.t. 2x 1 x 2 + 3x 3 + x 4 = 6 x 1 4x 2 + 2x 3 + x 5 = 5 x 1, x 2, x 3, x 4, x 5 0 1.3 1.3.1 Lancaster(1992) (diet problem)
12 1 1.3 100g B1 C (kcal) (g) (g) (g) (g) (g) (g) (mg) (mg) (mg) 60 84 1.9 0.1 13.3 0.7 0 0.08 16 0 18 94.6 0.4 0.1 4.1 0.6 0 0.02 11 0 26 93 0.6 0.1 6.1 0.2 0 0.03 5 0 19 94 0.7 0.1 4.7 0.5 0 0.05 15 0 37 89.6 0.6 0.1 9 0.7 0.1 0.04 4 0 34 93 2.9 1.6 2.2 0.3 0 0.04 1 0 12 95.9 0.6 0.1 2.8 0.5 0 0.05 5 0 1.4 (100g ) 2003 3 15 1 2 3 4 5 6 7 ( ) 136.5 157.5 273.0 136.5 157.5 50.0 147.0? 1.3 3 B1 C 10g 0.5mg 50mg 4 1.4 j (j = 1,..., 7) x j (100g) x 1,..., x 7 B1 1.9x 1 + 0.4x 2 + 0.6x 3 + 0.7x 4 + 0.6x 5 + 2.9x 6 + 0.6x 7 C 0.08x 1 + 0.02x 2 + 0.03x 3 + 0.05x 4 + 0.04x 5 + 0.04x 6 + 0.05x 7 16.0x 1 + 11.0x 2 + 5.0x 3 + 15.0x 4 + 4.0x 5 + 1.0x 6 + 5.0x 7 136.5x 1 + 157.5x 2 + 273.0x 3 + 136.5x 4 + 157.5x 5 + 50.0x 6 + 147.0x 7 3 (http://food.tokyo.jst.go.jp/) 4 18 29 ( ) 1 70(55)g B1 1.1(0.8)mg C 100(100)mg
1.3. 13 min 136.5x 1 + 157.5x 2 + 273.0x 3 + 136.5x 4 + 157.5x 5 + 50.0x 6 + 147.0x 7 subject to 1.9x 1 + 0.4x 2 + 0.6x 3 + 0.7x 4 + 0.6x 5 + 2.9x 6 + 0.6x 7 10 0.08x 1 + 0.02x 2 + 0.03x 3 + 0.05x 4 + 0.04x 5 + 0.04x 6 + 0.05x 7 0.5 16.0x 1 + 11.0x 2 + 5.0x 3 + 15.0x 4 + 4.0x 5 + 1.0x 6 + 5.0x 7 50 x j 0, j = 1,..., 7 (1.11) (1.11) x 1 = 2.679 x 2 = 0.0 x 3 = 0.0 x 4 = 0.0 x 5 = 0.0 x 6 = 7.143 x 7 = 0.0 722.8 Stigler[7] Stigler 77 A B1 B2 C ( 1.5) No one recommends these diets for anyone, let alone everyone. 1.5 Stigler 535 lb. 107 lb. 13 lb. 134 lb. 25 lb. Dantzig (simplex method) 1947 1950 Dantzig 500 ([2]) 500 ( 1890L 5 ) 200 6 (bran) 2 ( 900g) 4 (blackstrap molasses) 2 ( 900g) Dantzig 5 1 6 Dantzig 3
14 1 Fletcher, Soden, Zinober[5] \ " 1. 2. 3. 4. LP 1.6 1.6 (g) 1( ) 2 3 4 5 50 50 112 50 50 125 0 63 63 63 200 0 100 200 200 200 0 100 200 100 70 70 0 70 70 75 75 265 75 75 1 1 99 1 1 100 100 0 100 100 150 95 0 82 82 10 10 10 10 10 10 10 54 10 10 75 0 38 38 38 75 259 75 75 75 20 254 667 57 57 50 223 53 50 98 200 0 100 100 100 (200) 297 220
1.3. 15 1.3.2 1.7 1.7 1 1 2 1 2 ( / ) A 4.5 2.0 1.5 1.2 8.0 2 B 1.0 3.0 0.5 1.0 2.0 4 C 0 1.0 0.5 0 4.0 8 ( ) 45 60 15 20 150 A B C 150 100 200 150 [] 1 x 1 2 x 2 1 x 3 2 x 4 x 5 A B C y 1 y 2 y 3 1 3 4 5 max 45x 1 + 60x 2 + 15x 3 + 20x 4 + 150x 5 s.t. 4.5x 1 + 2.0x 2 + 1.5x 3 + 1.2x 4 + 8.0x 5 y 1 0 1.0x 1 + 3.0x 2 + 0.5x 3 + 1.0x 4 + 2.0x 5 y 2 0 1.0x 2 + 0.5x 3 + 4.0x 5 y 3 0 2y 1 + 4y 2 + 8y 3 1500 y 1 150, y 2 100, y 3 200 x 1, x 2, x 3, x 4, x 5, y 1, y 2, y 3 0 (1.12) [ ] (1.12) x 1 = 18.8 x 2 = 20 x 4 = 21.2 x 3 = x 5 = 0 y 1 = 150 y 2 = 100 y 3 = 100
16 1 [8] 7 100a 1.8 1.9 1.8 4 6.9 71.0 2.0 33.0 5 2.6 0.0 28.0 0.0 6 70.0 0.0 0.0 0.0 29.8 10.4 13.8 19.8 1.9 4 260 5 280 6 290 [] x 1 (a) x 2 (a) x 3 (a) x 4 (a) [ ] max 29.8x 1 + 10.4x 2 + 13.8x 3 + 19.8x 4 s.t. x 1 + x 2 + x 3 + x 4 = 100 6.9x 1 + 71.0x 2 + 2.0x 3 + 33.0x 4 260 2.6x 1 + 28.0x 3 280 70.0x 1 290 x j 0, j = 1,..., 4 x 1 = 4.14 x 2 = 0 x 3 = 9.62 x 4 = 6.43 7 12 1 11 12
1.3. 17 7 1.10 1.10 1 2 3 4 5 6 7 106.08 111.39 104.81 92.53 97.09 105.63 142.20 ( ) 2 2.5 3.5 4 6 7.5 9 (%) 5 6 4 2 3 4 7 1.86 2.24 3.12 3.71 5.08 5.76 5.81 (%) 2.19 2.41 2.71 2.83 3.08 3.31 3.51 7 1 5% 4 40% 1 2 50 0.5 2.19 + 0.5 2.41 = 2.30( ) j (1 ) x j (j = 1,..., 7) 106.08x 1 + 111.39x 2 + 104.81x 3 + 92.53x 4 + 97.09x 5 + 105.63x 6 + 142.20x 7 1000 x 1 106.08x 1
18 1 106.08x 1 /1000 5 106.08x 1 + 6 111.39x 2 + 4 104.81x 3 + 2 92.53x 4 + 3 97.09x 5 1.86 106.80x 1 + 2.24 111.39x 2 + 3.12 104.81x 3 + 3.71 92.53x 4 + 4 105.63x 6 + 7 142.20x 7 5 1000 + 5.08 97.09x 5 + 5.76 105.63x 6 + 5.81 142.20x 7 4 1000 (2.19 106.08x 1 + 2.41 111.39x 2 + 2.71 104.81x 3 + 2.83 92.53x 4 + 3.08 97.09x 5 + 3.31 105.63x 6 + 3.51 142.20x 7 )/1000 106.08x 1 0.4 1000 111.39x 2 0.4 1000 104.81x 3 0.4 1000 92.53x 4 0.4 1000 97.09x 5 0.4 1000 105.63x 6 0.4 1000 142.20x 7 0.4 1000 maximize 0.232x 1 + 0.269x 2 + 0.284x 3 + 0.262x 4 + 0.299x 5 + 0.349x 6 + 0.499x 7 subject to 106.08x 1 + 111.39x 2 + 104.81x 3 + 92.53x 4 + 97.09x 5 + 105.63x 6 + 142.20x 7 1000 0.530x 1 + 0.668x 2 + 0.419x 3 + 0.185x 4 + 0.291x 5 + 0.423x 6 + 0.995x 7 5 0.197x 1 + 0.249x 2 + 0.327 + x 3 + 0.344x 4 + 0.493x 5 + 0.608x 6 + 0.826x 7 4 106.08x 1 400, 111.39x 2 400, 104.81x 3 400, 92.53x 4 400, 97.09x 5 400, 105.63x 6 400, 142.20x 7 400 x j 0 j = 1,..., 7 (1.13) ( 1 ) (x 1, x 2, x 3, x 4, x 5, x 6, x 7) = (0, 1.84, 3.82, 0, 0, 0, 2.78) 20 20 5 A 1 1.2 1.5 1 B 0.8 1.1 C 1.4 0.8
1.3. 19 ( 15 ) [] A x 1 x 2 x 3 B y 1 y 2 y 3 C z 1 z 2 z 3 A B C u A, u B, u C 8 u A = x 1 + 1 1.2 x 2 + 1 1.5 x 3 u B = y 1 + 1 0.8 y 2 + 1 1.1 y 3 u C = z 1 + 1 1.4 z 2 + 1 0.8 z 3 max u A + u B + u C s.t. u A x 1 1 1.2 x 2 1 u B y 1 1 0.8 y 2 1 u C z 1 1 1.4 z 2 1 x 1 + y 1 + z 1 = 20 x 2 + y 2 + z 2 = 20 x 3 + y 3 + z 3 = 5 x j 0, j = 1, 2, 3 y j 0, j = 1, 2, 3 z j 0, j = 1, 2, 3 1.5 x 3 = 0 1.1 y 3 = 0 0.8 z 3 = 0 (1.14) LP C B () (1.14) x 1 + x 2 + x 3 = 15 y 1 + y 2 + y 3 = 15 z 1 + z 2 + z 3 = 15 1.11 1.5 1. 3 8 (numeraire)
20 1 1.11 A 14.2 10 5 0 B 18.8 0 15 0 C 16.3 10 0 5 2. 15 min{u A, u B, u C } x, y, z min{x, y, z} x, y, z 1.6 K2 A 8% B 4% C 2% 4 1g 1.12 1g 1 A B C 0.03g 0.02g 0.01g 1.12 ( /g) A B C 1 8 0.03 0.02 0.01 2 10 0.06 0.04 0.01 3 11 0.10 0.03 0.04 4 14 0.12 0.09 0.04 20kg 1.7 A B C D P 1 d 1 P 2 d 2 p c 1 p c 2 p m 1 p m 2 P i (i = 1, 2) A B C D a A i a B i a C i a D i A B C D q A q B q C q D b 1.8 1. 80kg 20kg 30kg 2 20% 10% 10% ( ) 1kg 5 6
1.3. 21 2. 1kg 1200 2000 1600 120kg ( ) 3. 1 10kg ( 2 140kg ) 1500 4 1.9 1. K 1 500 1.13 1.13 1kg : 1kg : 1kg : 1kg : 1kg : 1kg : 1kg : 1kg : 300 500 600 0.8kg 250 0.5 kg 0.3 kg 800 2. 3000kg 1500kg 3. 1kg 200 1kg 300 ( ) 4. 1kg 100 120 1.3.3 1
22 1 4 1 20 18 9 1000 50 50 18=900 5 1.14 500 600 750 : : = 500 : 600 : 750 = 1 : 1.2 : 1.5 1.14 5 1 2 3 4 5 4 5 1 3 1 2 2 2 2 2 4 4 2 2 2 10 9 1.1.2 4 18.3
1.3. 23 x t t (t = 1,..., 5) y t t (t = 1,..., 5) u t t (t = 1,..., 5) v t t (t = 1,..., 5) w t t (t = 1,..., 5) 3 2 y 2 10 3 0.9y 2 3 x 3 3 y 3 y 3 = x 3 + 0.9y 2 (1.15) 3 3 x 3 18 20 18 60 x 3 20 = 0.015x 3( ) 0.15x 3 u 3 + v 3 + w 3, u 3 1, v 3 2, w 3 2 (1.16) u 1 + u 2 + u 3 + u 4 + u 5 + 1.2v 1 + 1.2v 2 + 1.2v 3 + 1.2v 4 + 1.2v 5 (1.15)(1.16)(1.17) +1.5w 1 + 1.5w 2 + 1.5w 3 + 1.5w 4 + 1.5w 5 (1.17) min 5 u t + t=1 5 1.2v t + t=1 5 1.5w t t=1 s.t. y 1 = x 1 y 2 = x 2 + 0.9y 1 y 3 = x 3 + 0.9y 2 y 4 = x 4 + 0.9y 3 y 5 = x 5 + 0.9y 4 y 5 1000 0.015x 1 u 1 + v 1 + w 1, 0.015x 2 u 2 + v 2 + w 2, 0.015x 3 u 3 + v 3 + w 3, 0.015x 4 u 4 + v 3 + w 4, 0.015x 5 u 5 + v 3 + w 5, u 1 4, u 2 5, u 3 1, u 4 3, u 5 1 v 1 2, v 2 2, v 3 2, v 4 2, v 5 2 w 1 4, w 2 4, w 3 2, w 4 2, w 5 2 x t 0, y t 0, u t 0, v t 0, w t 0, t = 1,..., 5 (1.18)
24 1 1.15 1 2 3 4 5 (u t ) 0 5 1 3 1 (v t ) 0 0 2 2 2 (w t ) 0 0 0 0 1.4 (x t ) 0 333.3 200.0 333.3 295 (y t ) 0 333.3 500.0 783.3 1000 (1.18) 1.15 5 4 5 0.02 0.2 1.16 0.02 1 1.16 1 2 3 4 5 0.02 (u t ) 4 5 1 3 1 (v t ) 0 0 0 0 1.7 (w t ) 0 0 0 0 0 (x t ) 266.7 333.3 66.7 200 180.28 (y t ) 266.7 594.7 649.4 836.5 1000 0.2 (u t ) 0 4.8 1 3 1 (v t ) 0 0 2 2 2 (w t ) 0 0 0 2 2 (x t ) 0 322.9 200.0 466.7 333.3 (y t ) 0 322.9 485.3 833.3 1000 5 100 1 5 1 0.25 5 2 10 4 40 5 20 100
1.3. 25 x 0 x t t (t = 1,..., 5) y t t (t = 1,..., 5) z t t (t = 1,..., 5) 2 2 x 2 5x 2 y 2 = y 1 + 5x 2 2 10 x 2 z 1 0.25y 1 2 y 2 y 1 z 2 = z 1 10 x 2 + 0.25y 1 x 2 z 1 min x 0 s.t. z 1 = x 0 x 1 z 2 = z 1 10 x 2 + 0.25y 1 z 3 = z 2 x 3 + 0.25y 2 z 4 = z 3 40 x 4 + 0.25y 3 z 5 = z 4 20 x 5 + 0.25y 4 y 1 = 5x 1 y 2 = y 1 + 5x 2 y 3 = y 2 + 5x 3 y 4 = y 3 + 5x 4 y 5 = y 4 + 5x 5 y 5 100 x 1 x 0, x 2 z 1, x 3 z 2, x 4 z 3, x 5 z 4 x t 0, y t 0, z t 0, t = 1,..., 5 (1.19) (1.19) x 1 = 13.1 x 2 = 0 x 3 = 6.3 x 4 = 0 x 5 = 0.6 y 1 = 65.3 y 2 = 65.3 y 3 = 97 y 4 = 97 y 5 = 100 z 1 = 0 z 2 = 6.3 z 3 = 16.3 z 4 = 0.6 z 5 = 4.3 x 0 = 13.1 1.10 100 1 1% 10 10 (=100/10) 3 10 + (100 20) 0.01 = 10.8
26 1 5 5 5% 1.11 [] = 0.8 [ ] + 0.2 [ ] 0.05 [] 4 15 1.17 4 1.17 1 2 3 4 7 3 7 5 15 1.4 1.4.1 max x 1 + x 2 s.t. x 1 + 2x 2 3 x 1 0, x 2 0 (1.20) x 1 + 2x 2 3 x 1 + 2x 2 0 (1.20) (x 1, x 2 ) (infeasible) (feasible) (feasible solution) (1.20) max x 1 + x 2 s.t. x 1 + 2x 2 3 x 1 0, x 2 0 (1.21) (1.21) (x 1, x 2 ) = (1, 1) (x 1, x 2 ) = (1, 1) 1 + 1 = 2 1 t (1 + t, 1) (1 + t) + 2 1 = 1 t 3
1.4. 27 (1 + t) + 1 = 2 + t t t 10 (unbounded) ^x d t ^x + td ^x ^x + td (1.21) max x 1 + x 2 s.t. x 1 + 2x 2 3 x 1 0, x 2 0 (1.22) (1.22) (1.21) d = (1, 0) (1.22) (0, 1.5) (infeasible) (feasible) (feasible solution) ( ) ( ) 1.4.2 LP (c 1, c 2 ) max c 1 x 1 + c 2 x 2 s. t. x 1 + x 2 6 2x 1 + x 2 10 x 2 3 x 1, x 2 0 (1.23) (1.23) ( x 1 x 2 ) S S x 1 {x 2 1.18 10
28 1 1.18 S x 2 A (0,3) (3,3) E (3.5,3) S B (4,2) C O D 0 (5,0) (6,0) F x 1 (c 1, c 2 ) \ " ( ) ( (1.24)) 1.21 max c 1 x 1 + c 2 x 2 s. t. x 1 + x 2 6 2x 1 + x 2 10 x 2 3 x 1, x 2 0 (1.24) 1.12 α max x 1 x 2 s. t. 2x 1 3x 2 3 αx 1 x 2 3α 3 x 1, x 2 0 α [] x 1 -x 2 αx 1 x 2 = 3α 3 α (3, 3)
1.4. 29 1.19 S (1) x 2 (C1,C2) 0 x 1 1.20 S (2) x 2 0 x 1 (C1,C2)
30 1 1.21 x 2 (C1,C2) 0 x 1 1.4.3 (1.23) (c 1, c 2 ) = (3, 2) (1.25) max 3x 1 + 2x 2 s. t. x 1 + x 2 + x 3 = 6 2x 1 + x 2 + x 4 = 10 (1.25) x 2 + x 5 = 3 x 1, x 2, x 3, x 4, x 5 0 3 x 1 + x 2 +x 3 = 6 2x 1 + x 2 +x 4 = 10 x 2 +x 5 = 3 (1.26) (1.26) 5 3 x 2 x 4 (1.26) 1 x 1 = x 2 x 3 + 6 2 x 1 +x 2 +x 3 = 6 x 2 2x 3 +x 4 = 2 x 2 +x 5 = 3 (1.27)
1.4. 31 (1.27) 2 x 3 = 0.5x 2 + 0.5x 4 + 1 1 x 1 +0.5x 2 +0.5x 4 = 5 x 2 2x 3 +x 4 = 2 x 2 +x 5 = 3 (1.28) (1.25) z = 3x 1 + 2x 2 (1.28) 1 x 1 z = 3 (5 0.5x 2 0.5x 4 ) + 2x 2 = 15 + 0.5x 2 1.5x 4 (1.29) x 2 x 4 (1.28) (1.29) x 2, x 4 z = 15 +0.5x 2 1.5x 4 x 1 = 5 0.5x 2 0.5x 4 x 3 = 1 0.5x 2 +0.5x 4 x 5 = 3 x 2 (1.30) (1.25) z z = 3x 1 + 2x 2 x 1 + x 2 + x 3 = 6 2x 1 + x 2 + x 4 = 10 (1.31) x 2 + x 5 = 3 (1.30) (1.31) 1.13 (1.31) (x 1, x 2,..., x 5 ) (1.30) (1.30) (x 1, x 2,..., x 5 ) (1.31) 1.4.4 (1.30) z, x 1, x 3, x 5 x 2 x 4 x 2 x 4 z, x 1, x 3, x 5 11 x 1, x 3, x 5 (basic variable) x 2, x 4 (nonbasic variable) 11 (dictionary)
32 1 0 (1.30) x 2 = x 4 = 0 x 1 = 5, x 3 = 1, x 5 = 3, z = 15 (1.31) (1.31) x 2 = x 4 = 0 x 1 + x 3 = 6 2x 1 + x 4 = 10 x 5 = 3 x 1 = 5, x 3 = 1, x 5 = 3 z = 3x 1 + 2x 2 z = 15 0 (basic solution) (feasible basic solution) (1.30) x 1 = 5, x 2 = 0, x 3 = 1, x 4 = 0, x 5 = 3 ( ) x 1 x 2 (x 1, x 2 ) = (5, 0) 1.18 D x 3 x 4 z = 16 x 3 x 4 x 1 = 4 +x 3 x 4 x 2 = 2 2x 3 +x 4 x 5 = 1 +2x 3 x 4 (1.32) x 1 = 4, x 2 = 2, x 3 = 0, x 4 = 0, x 5 = 1 x 1 -x 2 (x 1, x 2 ) = (4, 2) C 1.14 x 1,..., x 5 1.18 [ ] S
1.4. 33 1.4.5 D C z = 15 +0.5x 2 1.5x 4 x 1 = 5 0.5x 2 0.5x 4 x 3 = 1 0.5x 2 +0.5x 4 x 5 = 3 x 2 (1.30) z = 16 x 3 x 4 x 1 = 4 +x 3 x 4 x 2 = 2 2x 3 +x 4 x 5 = 1 +2x 3 x 4 (1.32) (1.30) ( ) x 2, x 4 0 (1.30) z = 15 + 0.5x 2 1.5x 4 x 2 0.5 x 2 0 x 4 0 x 2 0 t z = 15 +0.5t x 1 = 5 0.5t x 3 = 1 0.5t x 5 = 3 t (1.33) t z = 15 + 0.5t t t x 1, x 3, x 5 t t = 2 x 3 = 0 (1.30) 3 x 3 = 1 0.5x 2 + 0.5x 4 (1.32) (1.30) x 2 (1.32) (1.30) x 3 (1.32) (1.32) 16 15 + 0.5 2 1.15 (1.30) x 4 ( ) 0? 1.18?
34 1 (1.30) (1.32) (1.32) z = 16 x 3 x 4 x 3 x 4 0 (1.32) (1.32) (^x 1,..., ^x 5 ) (1.25) (1.32) z = 3^x 1 + 2^x 2 = 16 ^x 3 ^x 4 12 ^x 3 0, ^x 4 0 z = 3^x 1 + 2^x 2 16 16 16 0 (simplex method)
1.4. 35 1.22 1 1 6 2 1 10 0 1 3 3 2 1.4.6 1 1.22 max 3x 1 + 2x 2 s. t. x 1 + x 2 6 2x 1 + x 2 10 x 2 3 x 1, x 2 0 (1.34) (1.23) z = 16 x 3 x 4 x 1 = 4 +x 3 x 4 x 2 = 2 2x 3 +x 4 x 5 = 1 +2x 3 x 4 (1.32) 2 2.5 (1.32) z = 16 x 3 x 4 z = 3x 1 + 2x 2 z = 3x 1 + 2x 2 = 3(4 + x 3 x 4 ) + 2(2 2x 3 + x 4 ) 12 (5, 0, 1, 0, 3) (0, 0, 6, 10, 3) (3, 3, 0, 1, 0)
36 1 2 2.5 z = 3x 1 + 2.5x 2 = 3(4 + x 3 x 4 ) + 2.5(2 2x 3 + x 4 ) = 17 2x 3 0.5x 4 16 17 2 4? z = 20 5x 3 +x 4 x 1 = 4 +x 3 x 4 x 2 = 2 2x 3 +x 4 x 5 = 1 +2x 3 x 4 (1.35) x 4 x 4 0 x 1, x 2, x 4 z = 21 3x 3 x 5 x 1 = 3 x 3 +x 5 x 2 = 3 x 5 x 4 = 1 +2x 3 x 5 (1.36) 2.5 4 2.5 4 δ 2 + δ 2 + δ z = 3x 1 + (2 + δ)x 2 = 3(4 + x 3 x 4 ) + (2 + δ)(2 2x 3 + x 4 ) = 16 + 2δ + ( 1 2δ)x 3 + ( 1 + δ)x 4 (34 ) 0 δ 1 2δ 0 1 + δ 0 0.5 δ 1 1.5 3 1.16
1.5. 37 1.5 1.5.1 y 1 y 2 y 3 6y 1 + 10y 2 + 3y 3 1 1 1 1 1 y 1 + y 2 + y 3 2 y 1 + y 2 + y 3 2 y 1 + 2y 2 3 min 6y 1 + 10y 2 + 3y 3 s. t. y 1 + 2y 2 3 y 1 + y 2 + y 3 2 y 1, y 2, y 3 0 (1.37) y 1 = 1 y 2 = 1 y 3 = 0 ( ) 16 (1.37) (shadow price) (1.37) (1.34) (1.37) 1.5.3 1.5.2 (1.38) maximize c 1 x 1 + c 2 x 2 + + c n x n subject to a 11 x 1 + a 12 x 2 + + a 1n x n b 1 a 21 x 1 + a 22 x 2 + + a 2n x n b 2. a m1 x 1 + a m2 x 2 + + a mn x n b m x j 0, j = 1,..., n (1.38)
38 1 (1.39) (1.38) (dual problem) minimize b 1 y 1 + b 2 y 2 + + b m y m subject to a 11 y 1 + a 21 y 2 +... + a m1 y m c 1 a 12 y 1 + a 22 y 2 +... + a m2 y m c 2. a 1n y 1 + a 2n y 2 +... + a mn y m c n y i 0, i = 1,..., m (1.39) y i (i = 1,..., m) (dual variable) (primal problem) i y i j x j (1.5.4 ) () max s.t. c x Ax b x 0 ( ) min s.t. b y A y c y 0 a 11 a 12 a 1n c 1 b 1 a 21 a 22 a 2n A =..... c = c 2. b = b 2. a m1 a m2 a mn c n b m 1.17 1. (1.34) (1.37) 2. max 3x 1 x 2 + 4x 3 + 5x 4 s.t. x 1 + x 2 3x 3 4x 4 2 2x 1 4x 2 + x 3 2x 4 8 x 1, x 2, x 3, x 4 0 3. f(x) f(x) 1 () (1.38) (1.38) (1.39)
1.5. 39 (1.40) (1.38) maximize subject to n j=1 c jx j n j=1 a ijx j = b i, x j 0, i = 1,..., m j = 1,..., n (1.40) (1.40) minimize subject to m i=1 b iy i m i=1 a ijy i c j, j = 1,..., n (1.41) (1.41) y i (1.42) max 3x 1 + 2x 2 s. t. x 1 + x 2 + x 4 = 6 2x 1 + x 2 + x 5 = 10 x 2 + x 6 = 3 x 1, x 2, x 3, x 4, x 5 0 (1.42) (1.41) (1.42) min 6y 1 + 10y 2 + 3y 3 s. t. y 1 + 2y 2 3 y 1 + y 2 + y 3 2 y 1 0 y 2 0 y 3 0 (1.43) 3 (1.43) (1.37) (1.38) (1.39) (1.40) (1.41) 1.5.3 ( ) x 1,..., x n y 1,..., y m c 1 x 1 + c 2 x 2 + + c n x n b 1 y 1 + b 2 y 2 + + b m y m (1.44)
40 1 1.5.1 ( ) () (1.44) ( n n m ) m n m c j x j a ij y i x j = a ij x j y i b i y i j=1 j=1 i=1 (x 1,..., x n ) (y 1,..., y m ) i=1 j=1 i=1 c 1 x 1 + c 2 x 2 + + c n x n = b 1 y 1 + b 2 y 2 + + b m y m (x 1,..., x n ) (y 1,..., y m ) 1.1 ( ) (1.38) (x 1,..., x n) (1.39) (y 1,..., y m) n m c j x j = b i y i j=1 [ ] ( ) i=1 n+m z = z + c j x j (1.45) x j c j = 0 c j 0 z = j=1 n c j x j (1.46) j=1 z (x 1,..., x n) z = n c j x j (1.47) j=1 y i = c n+i 0, i = 1,..., m (1.48) y i, i = 1,..., m
1.5. 41 (1.45) z = z + z = z + = (z = z + j=1 n m c j x j + c n+i x n+i j=1 j=1 i=1 n m c j x j y i x n+i (1.49) i=1 n m c j x j y i (b i i=1 m b i y i ) + i=1 j=1 n a ij x j ) j=1 n m (c j + a ij y i )x j (1.50) (1.46) (1.50) n m c j x j = (z b i y i ) + j=1 i=1 j=1 i=1 n m (c j + a ij y i )x j i=1 c j + m b i y i = z i=1 m a ij y i = c j, i=1 j = 1,..., n c j 0 (D) (y 1,..., y m) [] 1.23
42 1 1.23 1.2 ( ) x = (x 1,..., x n) (1.38) y = (y 1,..., y m) (1.39) x y j = 1,..., n i = 1,..., m m a ij y i = c j x j = 0 (1.51) i=1 n a ij x j = b i y i = 0 (1.52) [ ] x y n c j x j j=1 j=1 j=1 n m m n m ( a ij y i )x j = ( a ij x j )y i b i y i (1.53) i=1 (1.51) (1.52) (1.53)) x y (1.53) (1.51) (1.52) i=1 j=1 i=1 [] x 1,..., x n, y 1,..., y m y i > 0 i () y i = 0 i 13 (1.37) 13 \ "
1.5. 43 (1.34) y 1 y 2 y 3 (1.34) (x 1, x 2 ) = (4, 2) (1.37) (y 1, y 2, y 3 ) = (1, 1, 0) x 1 + x 2 = 6, 2x 1 + x 2 = 10 0 y 1 + 2y 2 = 3 y 1 + y 2 + y 3 = 2 1 3 ( ) ( ) (1.38) (40 ) x n+i ^c n+i y i = ^c n+i 0 (1.34) (1.32) x 3 1 y 1 = 1 x 4 1 y 2 = 1 y 3 = 0 1.5.4 1.4.6 b 1 b 2 b m. = b 1 + ɛ 1 b 2 + ɛ 2. b m + ɛ m ɛ i (i = 1,..., m) z z = c 1 x 1 + c 2 x 2 + + c n x n = b 1 y 1 + b 2 y 2 + + b m y m
44 1 (b 1 + ɛ 1, b 2 + ɛ 2,..., b n + ɛ n ) z z = (b 1 + ɛ 1 )y 1 + (b 2 + ɛ 2 )y 2 + + (b m + ɛ m )y m z z = ɛ 1 y 1 + ɛ 2 y 2 + + ɛ m y m (1.54) 1.4.6 (1.34) z = 16 x 3 x 4 x 1 = 4 +x 3 x 4 x 2 = 2 2x 3 +x 4 x 5 = 1 +2x 3 x 4 (1.32) (x 1, x 2, x 3, x 4, x 5 ) = (4, 2, 0, 0, 1) (y 1, y 2, y 3 ) = (1, 1, 0) ɛ 3 (y 3 ) 0 (1.54) 0 y 1 1 ɛ 1 ɛ 1 ( ɛ 1 ) ɛ 1 = 0.2 x 1 x 2 x 5 z = 16.2 x 3 x 4 x 1 = 3.8 +x 3 x 4 x 2 = 2.4 2x 3 +x 4 x 5 = 0.6 +2x 3 x 4 (1.55) (x 1, x 2, x 3, x 4, x 5 ) = (4, 2, 0, 0, 1) (3.8, 2.4, 0, 0, 0.6) 16 16.2 ɛ 1 = 0.2 y 1 = 1 1 ɛ 1 1 ɛ 1 1 1
1.5. 45 1.24 (0 ɛ 1 0.6) ɛ 1 0 0.1 0.2 0.3 0.4 0.5 0.6 z 16.0 16.1 16.2 16.3 16.4 16.5 16.6 x 1 4.0 3.9 3.8 3.7 3.6 3.5 3.4 x 2 2.0 2.2 2.4 2.6 2.8 3.0 3.2 x 5 1.0 0.8 0.6 0.4 0.2 0.0-0.2 1.24 ɛ 1 0 x 1 x 2 x 5 x 2 x 1 x 5 ɛ 1 = 0.5 x 5 0 ɛ 1 0.5 x 3 x 5 ɛ 1 = 0.5 b = (6.5, 10, 3) z = 16.5 1.5x 4 0.5x 5 x 1 = 3.5 0.5x 4 +0.5x 4 x 2 = 3.5 x 4 x 3 = 0.0 +0.5x 4 +0.5x 4 (1.56) 1.25 ɛ 1 0.5 1.0 1.25 (ɛ 1 0.5) ɛ 1 0.5 0.6 0.7 0.8 0.9 1.0 z 16.5 16.5 16.5 16.5 16.5 16.5 x 1 3.5 3.5 3.5 3.5 3.5 3.5 x 2 3.0 3.0 3.0 3.0 3.0 3.0 x 3 0.0 0.1 0.2 0.3 0.4 0.5 ɛ 1 > 5 y 1 = 0 y 2 = 1.5 y 3 = 0 0 8 1.26 b 1 0 b 1 5 3 5 < b 1 6.5 1 b 1 > 6.5 0 1 3 3 2 5
46 1 1.26 Obj. value 16.0 12.0 8.0 4.0 0.0 2.0 4.0 6.0 8.0 Wood 1 1 3 + 1 3 + 0 2 = 6 6 1 5 1 5 1 5 6 8 max 3x 1 + 2x 2 + 8x 3 s. t. x 1 + x 2 + 3x 3 6 2x 1 + x 2 + 3x 3 10 x 2 + 2x 3 3 x 1, x 2, x 3 0 (1.57) 17.33 4.0 0.0 0.67 2.33 0.33 0.0