( ) ? () 1.1 ( 3 ) j x j 10 j 1 10 j = 1,..., 10 x 1 + x x 10 =

Similar documents

( ) () () ( ) () () () ()

2 1/2 1/4 x 1 x 2 x 1, x 2 9 3x 1 + 2x 2 9 (1.1) 1/3 RDA 1 15 x /4 RDA 1 6 x /6 1 x 1 3 x 2 15 x (1.2) (1.3) (1.4) 1 2 (1.5) x 1

min. z = 602.5x x 2 + 2

最適化手法第1回 [3mm] 整数計画法 (1) [3mm]

f(x) x S (optimal solution) f(x ) (optimal value) f(x) (1) 3 GLPK glpsol -m -d -m glpsol -h -m -d -o -y --simplex ( ) --interior --min --max --check -

nakata/nakata.html p.1/20

*2015カタログ_ブック.indb

Taro13-宇城（改）.jtd

Taro13-芦北（改）.jtd

数理計画法入門サンプルページこの本の定価判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.

OR 2 Excel OK. 1a: Excel2007 Office. Excel b OK. 2.,,. ツールアドイン 1b: Excel2003 :,.,.,.,,,.,,. 1. Excel2003.

海生研ニュース

森林航測72号

Microsoft Word J.^...O.|Word.i10...j.doc

…p…^†[…ﬁﬂF”¯ Pattern Recognition

資料5：聖ウルスラ学院英智小・中学校　提出資料（1）

食肉の知識

食事編_表1_4_0508

Microsoft Word - 表紙資料２－４

NewBead_no17_4c_pdf.indd

財団法人母子健康協会第三十回シンポジウム

シンデレラ合宿

製品案内　価格表　2014/4/1

３．ごみの減量方法.PDF

s t 1, 2,..., 10 s t a, b,..., k t s 1, 2,..., 10 1 a, b,..., k 1 s t ts 1 0 ( 2.25) ½ ¾ ½¼ x 1j = 1 x 2c = 1 x 3e = 1

Solution Report

../dvi98/me98enve.dvi

離散最適化基礎論第 11回組合せ最適化と半正定値計画法

.N...[..7...doc

橡０３春の号.doc

橡０３夏の号.doc

n 2 n (Dynamic Programming : DP) (Genetic Algorithm : GA) 2 i

数値計算：有限要素法

cable_nyuko_ indd

薬局におけるインシデント事例の集計･分析結果

<8A7797EE8AFA945B CD82E882B182DD2E696E6464>

香南市・香美市のニラ

●板橋区‐体協ニュース８５号／本文　１２０７３０

æœ•é†©ä½‘å®–é†¸æ−žã†®ã†�ã‡†ã†®æ··å’‹æŁ´æŁ°è¨‹çﬂ»ã…¢ã…⁄ã…«

n 2 + π2 6 x [10 n x] x = lim n 10 n n 10 k x 1.1. a 1, a 2,, a n, (a n ) n=1 {a n } n=1 1.2 ( ). {a n } n=1 Q ε > 0 N N m, n N a m

0 (1 ) 0 (1 ) 01 Excel Excel ( ) = Excel Excel = =5-5 3 =5* 5 10 =5/ 5 5 =5^ 5 5 ( ), 0, Excel, Excel 13E E

) km 200 m ) ) ) ) ) ) ) kg kg ) 017 x y x 2 y 5x 5 y )

50. (km) A B C C 7 B A 0

◎【教】⑯梅津正美先生【本文】／【教】⑯梅津正美先生【本文】

8 OR (a) A A 3 1 B 7 B (game theory) (a) (b) 8.1: 8.1(a) (b) strategic form game extensive form game 1

転がり軸受　総合カタログ

例題で学ぶオペレーションズリサーチ入門サンプルページこの本の定価判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.

第3章非線形計画法の基礎

(1.2) T D = 0 T = D = 30 kn 1.2 (1.4) 2F W = 0 F = W/2 = 300 kn/2 = 150 kn 1.3 (1.9) R = W 1 + W 2 = = 1100 N. (1.9) W 2 b W 1 a = 0

( ) a C n ( R n ) R a R C n. a C n (or R n ) a 0 2. α C( R ) a C n αa = α a 3. a, b C n a + b a + b ( ) p 8..2 (p ) a = [a a n ] T C n p n a

> > <., vs. > x 2 x y = ax 2 + bx + c y = 0 2 ax 2 + bx + c = 0 y = 0 x ( x ) y = ax 2 + bx + c D = b 2 4ac (1) D > 0 x (2) D = 0 x (3

<82D282A982C1746F95F18D908F57967B95B E696E6464>

秋植え花壇の楽しみ方

MY16_R8_DI_ indd

Transcription:

5 1! (Linear Programming, LP) LP OR LP 1.1 1.1.1 1. 2. 3. 4. 5. ( ) ( ) 1.1

6 1 1.1 ( ) 1 110 2 98 3 85 4 90 5 73 6 62 7 92 8 88 9 79 10 75 1.1.2 4? 900 40 80 120 () 1.1 ( 3 ) j x j 10 j 1 10 j = 1,..., 10 x 1 + x 2 + + x 10 = 900 [] x 1 120, x 2 120, x 3 120 [] x 4 80, x 5 80, x 6 80 [] x 7 40, x 8 40, x 9 40, x 10 40 []

1.1. 7 110x 1 + 98x 2 + 85x 3 + 90x 4 + 73x 5 + 62x 6 + 92x 7 + 88x 8 + 79x 9 + 75x 10 minimize 110x 1 + 98x 2 + 85x 3 + 90x 4 + 73x 5 + 62x 6 + 92x 7 + 88x 8 + 79x 9 + 75x 10 subject to x 1 + x 2 + + x 10 = 900 x j 120, j = 1, 2, 3 x j 80, j = 4, 5, 6 x j 40, j = 7, 8, 9, 10 (1.1) () ( ) (1.1) (1.1) 1.1 (1.1) 900 160 240 360 1.1.3 20 y 1 y 2 y 3

8 1 20 0.8y 1 x 1 1.2y 1 0.8y 1 x 2 1.2y 1 0.8y 1 x 3 1.2y 1 0.8y 2 x 4 1.2y 2 0.8y 2 x 5 1.2y 2 0.8y 2 x 6 1.2y 2 0.8y 3 x 7 1.2y 3 0.8y 3 x 8 1.2y 3 0.8y 3 x 9 1.2y 3 0.8y 3 x 10 1.2y 3 y 1 = 3y 3 y 2 = 2y 3 minimize 110x 1 + 98x 2 + 85x 3 + 90x 4 + 73x 5 + 62x 6 + 92x 7 +88x 8 + 79x 9 + 75x 10 subject to x 1 + x 2 + + x 10 = 900 0.8y 1 x 1 1.2y 1 0.8y 1 x 2 1.2y 1 0.8y 1 x 3 1.2y 1 0.8y 2 x 4 1.2y 2 0.8y 2 x 5 1.2y 2 0.8y 2 x 6 1.2y 2 0.8y 3 x 7 1.2y 3 0.8y 3 x 8 1.2y 3 0.8y 3 x 9 1.2y 3 0.8y 3 x 10 1.2y 3 y 1 = 3y 3 y 2 = 2y 3 (1.2) (1.2) (1.1) (1.1) (1.2) 1.2 ( ) x x x 1 1 1

1.2. 9 (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 (1.3). a m1 x 1 + a m2 x 2 + + a mn x n = b m x 1 0, x 2 0,..., x n 0 x 1, x 2,..., x n ( ) (decision variable) (b 1,..., b m ) (right hand side) 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 ) (1.3)) 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.4) maximize subject to c x Ax = b x 0 (1.5) 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

10 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 (1.6). 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 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.7) (1.8) 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.8) (1.8) x 1 = x + 1 x 1 ( x + 1 0, x 1 0) 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.9)

1.3. 11 1.2 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.3 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 (diet problem)? 1.2 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.3 (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.2 1 B1 C 1 (http://food.tokyo.jst.go.jp/)

12 1 10g 0.5mg 50mg 2 1.3 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 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.10) (1.10) 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[8] Stigler 77 A B1 B2 C ( 1.4) No one recommends these diets for anyone, let alone everyone. Dantzig (simplex method) 1947 1950 Dantzig 500 ([2]) 2 18 29 ( ) 1 70(55)g B1 1.1(0.8)mg C 100(100)mg

1.3. 13 1.4 Stigler 535 lb. 107 lb. 13 lb. 134 lb. 25 lb. 500 ( 1890L 3 ) 200 4 (bran) 2 ( 900g) 4 (blackstrap molasses) 2 ( 900g) Dantzig Fletcher, Soden, Zinober[6] 1. 2. 3. 4. LP 1.5 1.3.2 3 1 4 Dantzig 3

14 1 1.5 (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.6 1.6 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 150 [] 1 x 1 2 x 2 1 x 3 2 x 4 x 5 A B C y 1 y 2 y 3 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 x 1, x 2, x 3, x 4, x 5, y 1, y 2, y 3 0

1.3. 15 [11] 5 100a 1.7 1.8 1.7 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.8 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 20 20 5 A 1 1.2 1.5 1 B 0.8 1.1 C 1.4 0.8 ( 15 ) [] 5 12 1 11 12

16 1 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 6 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.11) LP A C () (1.11) x 1 + x 2 + x 3 = 15 y 1 + y 2 + y 3 = 15 z 1 + z 2 + z 3 = 15 1.9 1.9 A 12.5 5.0 5.0 5.0 B 15.0 15.0 0 0 C 10.7 0 15.0 0 6 numeraire

1.3. 17 1.4 K4 A 8% B 4% C 2% 4 1g 1.10 1g 1 A B C 0.03g 0.02g 0.01g 1.10 ( /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.5 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.6 1. 80kg 20kg 30kg 2 20% 10% 10% ( ) 1kg 5 6 2. 1kg 1200 2000 1600 120kg ( ) 3. 1 10kg ( 2 140kg ) 1500 4 1.7

18 1 1. K 1 500 1.11 1.11 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 1. 2. 10

1.3. 19 200 5 1 100 1 150 1.12 1.12 1 2 3 4 5 5 4 4 3 2 12 12 12 5 5 10 5 [ ] w t t (t = 1,..., 5) x t t (t = 2,..., 5) y t t (t = 2,..., 5) z t t (t = 1,..., 5) u t t (t = 1,..., 5) v t t (t = 1,..., 5)

20 1 [] min v 1 + v 2 + v 3 + v 4 + v 5 s.t. 1 100 w 1 u 1 0 1 100 w t + 1 150 x t u t 0, t = 2,..., 5 u 1 v 1 5, v 1 12 u 2 v 2 4, v 2 12 u 3 v 3 4, v 3 12 u 4 v 4 3, v 4 5 u 5 v 5 2, v 5 5 w 1 z 1 = 0 w t + 0.9z t 1 10x t z t = 0, t = 2,..., 5 10x t 0.9z t 1 0, t = 2,..., 5 w 5 = 0, z 5 = 0 x 2 y 2 = 0 x t + y t 1 y t = 0, t = 3,..., 5 y 5 200 w t 0, t = 1,..., 4 x t 0, t = 2,..., 5 y t 0, t = 2,..., 5 z t 0, t = 1,..., 5 u t 0, t = 1,..., 5 v t 0, t = 1,..., 5 (1.12) 1.13 1 2 3 4 5 (u t ) 5.00 4.00 7.55 8.00 1.61 (v t ) 0.00 0.00 3.55 5.00 0.00 (w t ) 500.00 370.00 732.90 800.00 0.00 (x t ) 45.00 33.30 0.00 131.36 (y t ) 45.00 76.05 72.25 200.00 (z t ) 500.00 370.00 732.90 1459.61 0.00 (1.12) 1.13 [ ] T L t (t = 1,..., T) T t (t = 1,..., T) B j (j = 1,..., n) ( ) c jt B j 1 p j t i t []

1.4. 21 B j x j t v t min s.t. n j=1 p jx j n j=1 c jtx j + (1 + i t )v t 1 v t = L t, t = 1,..., T v 0 = 0 x j 0, j = 1,..., n v t 0, t = 1,..., T 1.14 Σc x jt j (1+i t )v t-1 v t L t 1.8 [] = 0:8 [ ] + 0:2 [ ] - 0:05 [] 4 15 1.15 4 1.15 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.13)

22 1 x 1 + 2x 2 3 x 1 + 2x 2 0 (1.13) (x 1, x 2 ) (infeasible) (feasible) (feasible solution) (1.13) max x 1 + x 2 s.t. x 1 + 2x 2 3 x 1 0, x 2 0 (1.14) (1.14) (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 + t) + 1 = 2 + t t t 7 (unbounded) ^x d t ^x + td ^x ^x + td (1.14) max x 1 + x 2 s.t. x 1 + 2x 2 3 x 1 0, x 2 0 (1.15) (1.15) (1.14) d = (1, 0) (1.15) (0, 1.5) (infeasible) (feasible) (feasible solution) ( ) ( ) 7

1.4. 23 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.16) (1.16) ( x 1 x 2 ) S S x 1 x 2 1.16 1.16 S x 2 A (0,3) E (3,3) (3.5,3) S B (4,2) C O D 0 (5,0) (6,0) F x 1 (c 1, c 2 ) ( )

24 1 1.17 S (1) x 2 (C1,C2) 0 x 1 1.18 S (2) x 2 0 x 1 (C1,C2)

1.4. 25 ( (1.17)) 1.19 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.17) 1.19 x 2 (C1,C2) 0 x 1 1.9 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)

26 1 1.4.3 (1.16) (c 1, c 2 ) = (3, 2) (1.18) max 3x 1 + 2x 2 s. t. x 1 + x 2 + x 3 = 6 2x 1 + x 2 + x 4 = 10 (1.18) 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.19) (1.19) 5 3 x 2 x 4 (1.19) 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.20) (1.20) 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.21) (1.18) z = 3x 1 + 2x 2 (1.21) 1 x 1 z = 3 (5 0.5x 2 0.5x 4 ) + 2x 2 = 15 + 0.5x 2 1.5x 4 (1.22) x 2 x 4 (1.21) (1.22) 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.23)

1.4. 27 (1.18) z z = 3x 1 + 2x 2 x 1 + x 2 + x 3 = 6 2x 1 + x 2 + x 4 = 10 (1.24) x 2 + x 5 = 3 (1.23) (1.24) 1.10 (1.24) (x 1 ; x 2 ; : : : ; x 5 ) (1.23) (1.23) (x 1 ; x 2 ; : : : ; x 5 ) (1.24) 1.4.4 (1.23) z, x 1, x 3, x 5 x 2 x 4 x 2 x 4 z, x 1, x 3, x 5 8 x 1, x 3, x 5 (basic variable) x 2, x 4 (nonbasic variable) 0 (1.23) x 2 = x 4 = 0 x 1 = 5, x 3 = 1, x 5 = 3, z = 15 (1.24) (1.24) 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.23) 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.16 D 8 (dictionary)

28 1 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.25) 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.11 x 1 ; : : : ; x 5 1.16 [ ] S 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.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.25) (1.23) ( ) x 2, x 4 0 (1.23) 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.26)

1.4. 29 t z = 15 + 0.5t t t x 1, x 3, x 5 t t = 2 x 3 = 0 (1.23) 3 x 3 = 1 0.5x 2 + 0.5x 4 (1.25) (1.23) x 2 (1.25) (1.23) x 3 (1.25) (1.25) 16 15 + 0.5 2 1.12 (1.23) x 4 ( ) 0? 1.16? (1.23) (1.25) (1.25) z = 16 x 3 x 4 x 3 x 4 0 (1.25) (1.25) (^x 1,..., ^x 5 ) (1.18) (1.25) z = 3^x 1 + 2^x 2 = 16 ^x 3 ^x 4 9 ^x 3 0, ^x 4 0 z = 3^x 1 + 2^x 2 16 16 16 9 (5; 0; 1; 0; 3) (0; 0; 6; 10; 3) (3; 3; 0; 1; 0)

30 1 (simplex method) 1.4.6 1 1.20 1.20 1 1 6 2 1 10 0 1 3 3 2 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.27) (1.16) 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.25)

1.5. 31 2 2.5 (1.25) 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 ) 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.28) 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 f (1.29) 3 3 1.5 1.5.1

32 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.30) y 1 = 1 y 2 = 1 y 3 = 0 ( ) 16 (1.30) (shadow price) (1.30) (1.27) (1.30) 1.5.3 1.5.2 (1.31) 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.31) (1.32) (1.31) (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.32)