106 4 4.1 1 25.1 25.4 20.4 17.9 21.2 23.1 26.2 1 24 12 14 18 36 42 24 10 5 15 120 30 15 20 10 25 35 20 18 30 12 4.1 7 min. z = 602.5x 1 + 305.0x 2 + 2

Similar documents

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

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

最適化手法第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 -

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

nakata/nakata.html p.1/20

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

広報ひめじ2015年9月号

広報ひめじ2015年8月号

森林航測72号

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

MacOSXLambdaJava.aw

2004 Copyright by Tatsuo Minohara Programming with Mac OS X in Lambda 21 - page 2

サービス付き高齢者向け住宅賠償責任保険.indd

目　　　　次

dos0901_148~155_IP

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

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

/ 2 ( ) ( ) ( ) = R ( ) ( ) 1 1 1/ 3 = 3 2 2/ R :. (topology)

シンデレラ合宿

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

３．ごみの減量方法.PDF

日本内科学会雑誌第102巻第10号

Q 23 A Q Q15 76 Q23 77

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

13koki_koza.indd

0ﾆ0・ﾓgqNｬX1TJf・

Step1 Step2 Step3 Step4 Step5 COLUMN.1 Step1 Step2 Step3 Step4 Step5 Step6 Step7 Step8 COLUMN.2 Step1 Step2 Step3 Step4 Step5 COLUMN.3 Step1 Step2 Ste

ŠéŒØ‘÷†u…x…C…W…A…ﬁ…l…b…g…‘†[…NﬁüŒå†v(ﬂ|ŁŠ−Ù) 4. −mŠ¦ﬁI’—Ÿ_ 4.1 −mŠ¦ŁªŁz‡Ì„v”Z

160mm OR16-34 ORB16-34 OR16-35 ORB16-35 OR16-43 ORB16-43 OR16-44 ORB16-44 OR16-45 ORB16-45 OR16-46 ORB16-46 OR16-47 ORB16-47 OR16-48 ORB16-48 OR16-53

A A = a 41 a 42 a 43 a 44 A (7) 1 (3) A = M 12 = = a 41 (8) a 41 a 43 a 44 (3) n n A, B a i AB = A B ii aa

/ n (M1) M (M2) n Λ A = {ϕ λ : U λ R n } λ Λ M (atlas) A (a) {U λ } λ Λ M (open covering) U λ M λ Λ U λ = M (b) λ Λ ϕ λ : U λ ϕ λ (U λ ) R n ϕ

syuu_2_10_3.dvi

MHIガイドブック2009

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

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

n 第1章　章立ての部分は、書式(PC入門大見出し)を使います

AHPを用いた大相撲の新しい番付編成

平成23年度記録

Emacs ML let start ::= exp (1) exp ::= (2) fn id exp (3) ::= (4) (5) ::= id (6) const (7) (exp) (8) let val id = exp in

Solution Report

L P y P y + ɛ, ɛ y P y I P y,, y P y + I P y, 3 ŷ β 0 β y β 0 β y β β 0, β y x x, x,, x, y y, y,, y x x y y x x, y y, x x y y {}}{,,, / / L P / / y, P

nakayama15icm01_l7filter.pptx

広報ひめじ2013年6月号

八代高校同窓会関東支部

日本内科学会雑誌第101巻第12号

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

,, etc. ( ) [Marti & Stoeckel 04] [Lloyd Smith, Chuang & Munro 90], [Staat & Heitzer 03] worst-case detection [Elishakoff, Haftka & Fang 94] 2 [Cheng

1 (bit ) ( ) PC WS CPU IEEE754 standard ( 24bit) ( 53bit)

../dvi98/me98enve.dvi

,,.,,., II,,,.,,.,.,,,.,,,.,, II i

SmartLMSユーザーズガイド＜講師編＞

konicaminolta.co.jp PageScope Net Care

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

▼ RealSecure Desktop Protector 7

Transcription:

105 4 0 1? 1 LP 0 1 4.1 4.1.1 (intger programming problem) 1 0.5 x 1 = 447.7 448 / / 2 1.1.2 1. 2. 1000 3. 40 4. 20

106 4 4.1 1 25.1 25.4 20.4 17.9 21.2 23.1 26.2 1 24 12 14 18 36 42 24 10 5 15 120 30 15 20 10 25 35 20 18 30 12 4.1 7 min. z = 602.5x 1 + 305.0x 2 + 285.0x 3 + 322.5x 4 + 763.2x 5 + 970.2x 6 + 628.8x 7 s.t. 24x 1 + 12x 2 + 14x 3 + 18x 4 + 36x 5 + 42x 6 + 24x 7 = 1000 10x 1 + 5x 2 + 15x 3 + 120x 4 + 30x 5 + 15x 6 + 20x 7 2400 15x 1 + 25x 2 + 35x 3 + 20x 4 + 18x 5 + 30x 6 + 12x 7 1200 x j 0, j = 1,..., 7 (4.1) 1 x 1 x 3 x 5 x 7 x 2 x 4 x 6 x 1 = x 2 = 0, x 3 = 19.4, x 4 = 14.3, x 5 = 13.1, x 6 = x 7 = 0, z = 20125.9 4.2( ) 4.2 0 0 271.3 257.5 471.2 0 0 250 3.4 0 246.6 250 250 250 0 100 0 250 250 250 150 0 7 3 250 x j 250, j = 1,..., 7 x 1 = 0.1, x 2 = 0, x 3 = 17.6, x 4 = 13.9, x 5 = 6.9, x 6 = 6.0, x 7 = 0, z = 20659.53 1 1.1.2

4.1. 107 4.2( 250 ) 5 100 250 100 250 x j /? 7 128 LP 128 LP 10 1024 / x j / z j (j = 1,..., 7) 0 1 z j = 0 j z j = 1 j / (z j = 1 or 0) 24x 1 1 z 1 = 0 24x 1 = 0 z 1 = 1 100 24x 1 250 100z 1 24x 1 250z 1 / min. z = 602.5x 1 + 305.0x 2 + 285.0x 3 + 322.5x 4 + 763.2x 5 + 970.2x 6 + 628.8x 7 s.t. 24x 1 + 12x 2 + 14x 3 + 18x 4 + 36x 5 + 42x 6 + 24x 7 = 1000 10x 1 + 5x 2 + 15x 3 + 120x 4 + 30x 5 + 15x 6 + 20x 7 2400 15x 1 + 25x 2 + 35x 3 + 20x 4 + 18x 5 + 30x 6 + 12x 7 1200 100z 1 24x 1 250z 1, 100z 2 12x 2 250z 2 100z 3 14x 3 250z 3, 100z 4 18x 4 250z 4 100z 5 36x 5 250z 5, 100z 6 42x 6 250z 6 100z 7 24x 7 250z 7 x j 0, j = 1,..., 7 z j {0, 1}, j = 1,..., 7 (4.2)

108 4 4.2( ) z 1 = 1 z 2 = 0 z 3 = 1 z 4 = 1 z 5 = 1 z 6 = 1 z 7 = 0 x 1 = 4.2 x 2 = 0 x 3 = 17.9 x 4 = 13.9 x 5 = 6.9 x 6 = 3.6 x 7 = 0 4.1 4 250 350 4.1.2 maximize subject to n j=1 c jx j n j=1 a ijx j = b i, x j 0, i = 1,..., m (1.5) maximize subject to n j=1 c jx j n j=1 a ijx j = b i, x j 0, x j Z, i = 1,..., m (4.3) ( ) ((mixed) integer programming problem) 2 Z (1.5) (4.3) (1.5) x (4.3) x c x c x (1.5) (4.3) x x maximize x 1 + x 2 + x 3 subject to 0.27x 1 + 0.4x 2 + 3x 3 3.8 x 1 + 0.13x 2 3 0.11x 1 + x 2 x 3 1 x j 0, j = 1,..., 3 (4.4) x 1 = 2.80, x 2 = 1.51 x 3 = 0.81 2 ( )

4.1. 109 ( 3 ) (4.4) maximize x 1 + x 2 + x 3 subject to 0.27x 1 + 0.4x 2 + 3x 3 3.8 x 1 + 0.13x 2 3 0.11x 1 + x 2 x 3 1 x j 0, j = 1,..., 3 x j Z, j = 1,..., 3 (4.5) x 1 = 3, x 2 = 0 x 3 = 0 x x = x 3 4.1.3 LP IP 40 20 50 100 200 400 600 800 [0, 1] [1, 2] 10 4, OS: Linux 2.2.20 CPU: Intel Pentium 4 2.53GHz lp solve (Version 4.0) ( 4.3 4.4 ) IP LP 4.1.4 (branch and bounding method) 3 x x 4 800 IP 1

110 4 4.3 LP IP ( ) 20 50 100 200 400 600 800 1 0.020 0.033 0.063 0.133 0.048 0.170 0.322 2 0.112 0.064 0.078 0.043 0.048 0.113 0.223 3 0.042 0.022 0.091 0.113 0.065 0.157 0.172 4 0.022 0.011 0.045 0.054 0.049 0.245 0.194 5 0.010 0.074 0.053 0.120 0.050 0.161 0.160 6 0.050 0.024 0.079 0.051 0.048 0.261 0.165 7 0.020 0.064 0.089 0.113 0.047 0.166 0.303 8 0.102 0.020 0.040 0.024 0.047 0.088 0.260 9 0.041 0.012 0.064 0.115 0.047 0.175 0.177 10 0.020 0.053 0.078 0.024 0.081 0.081 0.163 0.044 0.038 0.068 0.079 0.053 0.162 0.214 1 0.02 0.15 0.31 2.16 29.55 380.60 1270.03 2 0.01 0.09 0.60 3.76 35.36 696.63 3 0.01 0.07 0.91 2.55 20.84 257.85 4 0.02 0.16 0.60 6.49 23.09 89.96 5 0.01 0.12 0.18 2.43 27.45 244.88 6 0.01 0.16 0.43 3.58 13.23 568.30 7 0.02 0.05 0.87 3.33 18.73 544.46 8 0.01 0.11 0.70 3.89 25.06 394.25 9 0.01 0.17 0.46 3.48 34.96 781.69 10 0.01 0.11 0.65 3.12 21.65 246.77 0.013 0.119 0.571 3.479 24.992 420.539 1270.03

4.1. 111 4.4 LP IP ( ) 1400 LP IP 1200 1000 time(sec) 800 600 400 200 0 0 100 200 300 400 500 600 700 800 n max c x s.t. Ax = b P 0 l 0 j x j u 0 j, (4.6) x Z n P 0 Z n n l u P 0 P 0 P 0 P 0 (4.7) P 0 s.t. Ax = b max c x l 0 j x j u 0 j, P 0 P 0 P 0 P 0 P 0 P 0 (x 0 1,..., x0 n) x 0 s ξ ξ ( )

112 4 P 0 P 1 P 1 x 0 s 2 P 1 max s.t. c x Ax = b l 0 j x j u 0 j, l s x s x 0 s x Z n ; j s P 2 max s.t. c x Ax = b l 0 j x j u 0 j, ; j s x 0 s + 1 x s u 0 s x Z n P 1 P 2 P 0 P 1 P 2 P 0 P 1 P 2 ( ) P j P j 3 case 1) P j case 2) P j case 3) P j x j ^x c x j c ^x P j c x j > c ^x ( )

4.1. 113 4.5 P1 P11: P0 P12 P121: P2:»» P122:»ˆ Œ ^x x c ^x c x ɛ ɛ 2 max 5x 1 + 2x 2 s. t. 6x 1 + 2x 2 15 4x 1 + 4x 2 15 x 1 + 2x 2 5 x 1, x 2 0 x 1, x 2 Z (4.8) (4.8) P 0 max 5x 1 + 2x 2 s. t. 6x 1 + 2x 2 15 4x 1 + 4x 2 15 x 1 + 2x 2 5 x 1, x 2 0 (4.9) P 0 (x 0 1, x0 2 ) ( x 0 1 x 0 2) = ( 1.875 1.875 ) z 0 = 13.125 (4.8)

114 4 4.6 (4.8) 3 2 x 2 1 0 0 1 2 3 x 1 P 0 P 1 P 2 x 0 1 = 1.875 x 2 x 1 1 max 5x 1 + 2x 2 max 5x 1 + 2x 2 s. t. 6x 1 + 2x 2 15 s. t. 6x 1 + 2x 2 15 4x 1 + 4x 2 15 4x 1 + 4x 2 15 P 1 P 2 (4.10) x 1 + 2x 2 5 x 1 + 2x 2 5 x 1 2 x 1 1 x 1, x 2 0 x 1, x 2 0 P 1 P 1 : ( ) ( ) x 1 1 x 1 2 = 2 1.5 z 1 = 13 P 2 P 1 P 11 P 12 x 1 2 = 1.5 P 1

4.1. 115 4.7 P 1 P 2 3 2 x 2 1 P 2 P 1 0 0 1 2 3 x 1 x 2 2 x 2 1 max 5x 1 + 2x 2 s. t. 6x 1 + 2x 2 15 4x 1 + 4x 2 15 P 11 x 1 + 2x 2 5 x 1 2 x 2 2 x 1, x 2 0 P 12 max 5x 1 + 2x 2 s. t. 6x 1 + 2x 2 15 4x 1 + 4x 2 15 x 1 + 2x 2 5 x 1 2 x 2 1 x 1, x 2 0 (4.11) P 11 P 12 P 12 : ( ) ( ) x 12 1 x 12 2 = 2.17 1 z 12 = 12.83 P 11 P 12 P 121 P 122

116 4 P 121 max 5x 1 + 2x 2 s. t. 6x 1 + 2x 2 15 4x 1 + 4x 2 15 x 1 + 2x 2 5 x 1 3 x 2 1 x 1, x 2 0 P 122 max 5x 1 + 2x 2 s. t. 6x 1 + 2x 2 15 4x 1 + 4x 2 15 x 1 + 2x 2 5 2 x 1 2 x 2 1 x 1, x 2 0 (4.12) P 121 P 122 P 122 : ( ) ( ) x 122 1 x 122 2 = 2 1 z 122 = 12 ( 2 1 ) P 2 P 2 : ( x 2 1 x 2 2) = ( 1 2.75 ) z 2 = 10.5 z 2 = 10 12 P 2 ( 2 1 ) (4.8) 4.2 P 0 x 0 1 x 0 2 4.2 4.2.1 4.8 4.8 ( ) 1 70 100 2 90 110 3 50 60 4 120 150 200( )

4.2. 117 j (j = 1,..., 4) 0-1 x j x j = 1 j x j = 0 max 100x 1 + 110x 2 + 60x 3 + 150x 4 s.t. 70x 1 + 90x 2 + 50x 3 + 120x 4 200 x j {0, 1}, j = 1,..., 4 (4.13) (4.13) (napsack problem) (4.13) 2 5 1 6 4 1 5 4 6 1 2 5 7 3 4 6 8 ( 4.9) 4.9 5 100 120 6 40 75 7 20 8 15 1 5 max 100x 1 + 110x 2 + 60x 3 + 150x 4 + 120x 5 + 75x 6 s.t. 70x 1 + 90x 2 + 50x 3 + 120x 4 +100x 5 + 40x 6 + 20x 7 + 15x 8 200 x 1 + x 5 1, x 4 + x 6 1 x 1 x 7 0 x 2 x 7 0 x 5 x 7 0 x 3 x 8 0 x 4 x 8 0 x 6 x 8 0 x j {0, 1}, j = 1,..., 8 (4.14)

118 4 (4.13) (4.14) (x 1, x 2, x 3, x 4 ) = (1, 0, 0, 1) (x 1, x 2, x 3, x 4, x 5, x 6, x 7, x 8 ) = (1, 0, 1, 0, 0, 1, 1, 1) 4.3 3 4.10 4.10 1 2 3 4 2.5 1.0 0.8 1.1 3.01 1.1 0.96 1.1 1. 2. ( ) 1 1 5 4.2.2 8 1 1 4.11 4.11 1 2 3 4 5 6 7 8 ( ) A 20 B 18 C 32 D 9 E 22 5 (greedy method)

4.2. 119 0{1 x j (j A, B, C, D, E) min 20x A + 18x B + 32x C + 9x D + 22x E s.t. x A + x C + x D + x E 1 x A + x B 1 x C + x E 1 x A + x C + x E 1 x C + x D + x E 1 x A + x C 1 x A + x D + x E 1 x B + x C + x D 1 x j {0, 1}, j {A, B, C, D, E} x A = x D = x E = 1 x B = x C = 0 2.6.2 (69 ) 2.6.2 2 LP LP (set covering problem) 4.4 12 6 4.12 4.12 A 1 2 3 4, 8 3.0 B 3 4 0.9 C 5 6 7 1.5 D 8 10 11 2.1 E 4 9 10 1.8 F 6 11 12 1.4 3 4

120 4 4.2.3 1.00001kg 1kg 500g 200g 6 (4.13) 4.13 1 2 20 50 100 80 10 1 x 1 2 x 2 U(x 1, x 2 ) max U(x 1, x 2 ) s.t. 20x 1 + 50x 2 100000 x 1 = 100z 1 x 2 = 80z 2 x j 0 j = 1, 2 z j Z j = 1, 2 1 1 2 500 max U(x 1, x 2 ) s.t. 20x 1 + 50x 2 + 500f 1 + 500f 2 100000 x 1 = 100z 1 x 2 = 80z 2 z j Mf j, j = 1, 2 x j 0, j = 1, 2 z j Z, j = 1, 2 f j {0, 1}, j = 1, 2 M ( M 50 ) z 1 = 0 f 1 = 1 4.2.4 4.14

4.2. 121 4.14 d 3 d 2 transacton cost d 1 q q q quantity: x 1 2 3 7 24 1 x j v j L ( )c j p j min s.t. n j=1 p jx j n j=1 c jx j + L x j 0, q 3 j y j x j 0-1 z j0 z j1 z j2 λ j0 λ j1 λ j2 λ j3 6 7

122 4 min s.t. n j=1 p jx j + n j=1 y j n j=1 c jx j + L x j = q 1 λ j1 + q 2 λ j2 + q 3 λ j3, y j = d 1 λ j1 + d 2 λ j2 + d 3 λ j3, λ j0 + λ j1 + λ j2 + λ j3 = 1, λ 0j z 1j, λ 1j z 1j + z 2j, λ 2j z 2j + z 3j, λ 3j z 3j, z 1j + z 2j + z 3j = 1, x j 0, y j 0, λ 0j, λ 1j, λ 2j, λ 3j 0, z 1j, z 2j, z 3j {0, 1}, 4.2.5 24 24 5 8 13 13 17 17 22 22 5 5 8 2 13 22 2 17 5 (2 ) 8

4.2. 123 4.15 (1 0 ) 7/5 Sun. 7/6 Mon. 7/18 Sat. 1 2 3 4 5 6 7 8 9 10 66 67 68 69 70 5 4 5 7 3 5 4 5 7 3 5 4 5 7 3 2 3 3 2 2 3 3 3 2 2 2 3 3 3 2 A 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 B 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 C 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 D 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 E 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.. W 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 X 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 4.16 A 40 70 12 12 50 { 1 B 70 100 8 12 80 { 1 C 20 50 5 12 30 { { D 10 40 5 12 0 { { E 10 70 5 12 0 { {.. W 10 50 8 12-50 1 { X 10 50 8 12-50 1 { 4.15 4.16 i j

124 4 x ij (i = A, B,, X; j = 1, 2,..., 70) x i,j 0-1 x ij = { 1, i j 0, i j (4.15) x A1 = 1 7 5 A 0 7 5 A x A4 = 0, x A5 = 0 8 5 4 5 7 3 A 2 40 70 5x A1 + 4x A2 + 5x A3 + 7x A4 + 3x A5 + 5x A6 + 4x A7 + + 7x A69 + 3x A70 40 5x A1 + 4x A2 + 5x A3 + 7x A4 + 3x A5 + 5x A6 + 4x A7 + + 7x A69 + 3x A70 70 (4.16) A 12 13 5x A1 + 4x A2 + 5x A3 12, 4x A2 + 5x A3 + 7x A4 12, 5x A3 + 7x A4 + 3x A5 12, 7x A4 + 3x A5 + 5x A6 12, 3x A5 + 5x A6 + 4x A7 + 5x A8 12 5x A6 + 4x A7 + 5x A8 12 (4.17). 4x A67 + 5x A68 + 7x A69 12, 5x A68 + 7x A69 + 3x A70 12 A 12 A 7 5 (1 x A2 ) + (1 x A3 ) + (1 x A4 ) 3(x A1 x A2 ) (x A1 = 1) (x A2 = 0) 3 (x A2 = x A3 = x A4 = 0) (x A1 = 1) (x A2 = 1) 0 8 x A4 x A5

4.2. 125 (1 x A2 ) + (1 x A3 ) + (1 x A4 ) 3(x A1 x A2 ) (1 x A3 ) + (1 x A4 ) 2(x A2 x A3 ) (1 x A4 ) + (1 x A5 ) + (1 x A6 ) 3(x A3 x A4 ). (1 x A68 ) + (1 x A69 ) 2(x A67 x A68 ) (4.18) 3 A X (4.16) (4.17) (4.18) W W A B G H x W1 x A1 + x B1 + x G1 + x H1,. (4.19) x W70 x A70 + x B70 + x G70 + x H70 X x A1 + x B1 + + x X1 2 x A2 + x B2 + + x X2 3 x A70 + x B70 + + x X70 2 (4.20) M 50(5x A1 + 4x A2 + 5x A3 + 7x A4 + 3x A5 + 5x A6 + 4x A7 + + 7x A69 + 3x A70 ) + 80(5x B1 + 4x B2 + 5x B3 + 7x B4 + 3x B5 + 5x B6 + 4x B7 + + 7x B69 + 3x B70 ) 50(5x X1 + 4x X2 + 5x X3 + 7x X4 + 3x X5 + 5x X6 + 4x X7 + + 7x X69 + 3x X70 ) M (4.21) 70 24 = 1680 24 (2 + 68 + 67) + 2 70 + 70 + 1 = 3499

126 4 4.5 2 1 2 15 A 4.6 A 12