OR#5.key

Size: px
Start display at page:

Download "OR#5.key"

Transcription

1 オペレーションズ リサーチ1 Operations Research 前学期 月曜 3限(3:00-4:30) 8 整数計画モデル Integer Programming 経営A棟106教室 山本芳嗣 筑波大学 大学院 システム情報工学研究科 整数計画問題 2 凸包 最小の凸集合 線形計画問題 変数の整数条件 ctx Ax b x 0 xj は整数 IP LP 3 4

2 Bx d!!!!!? P NP LP IP 5 6!! Ax b! NP-! (ORwiki)!!! 58 R.E. Gomory, Outline of an algorithm for integer solution to linear programming, Bulletin of American Mathematical Society 64 (58) ! 60! 60 A.H. Land and A.G. Doig, An automatic method for solving discrete programming problems, Econometrica 28 (60) ! T.C. Hu, E. Balas, M. Held, R. Karp, J. Edmonds, A.M. Geoffrion, M.W. Padberg, M. Groetschel, G.L. Nemhauser,...! 88R. Bixby (Cplex Optimization) CPLEX! 88B. Daniel (Dash Optimisation) Xpress! Z. Gu, E. Rothberg & R. Bixgy (Gurobi Optimization)

3 Cutting Plane Method LP Gomory Cut LP "i x i = β i + j N x i = β i + j N α ij x j α ij x j x i + j N( α ij )x j = β i x j [!]! x i + j N[ α ij ]x j β i x i + j N[ α ij ]x j [β i ] j N([ α ij ] ( α ij ))x j [β i ] β i j N(( α ij ) [ α ij ])x j β i [β i ] 0 x i = β i + j N α ij x j j N(( α ij ) [ α ij ])x j β i [β i ] 8.4 Branch-and-Bound Method (B&B) 2x 3 2x 2 3 2x + y =3 2x 2 + y 2 =3 x =(3/2) (/2)y x +(/2)y =3/2 x +[/2]y [3/2] x x 3 x 4 2

4 x 3, x 2 5 x 4, x 2 4 x 4, x2 3, x 4 x 4, x2 3, x 5 x 3, x2 4 x 4, x # # Branching Tree # 5 6

5 限定操作 もしも が見つかって いれば を見つけた 段階で x 3の領域を 調べる必要はなく こ の子問題を捨てること ができる # # 分枝の木 Branching Tree x 3 # 7 8 限定操作に見る緩和法の原理 もしも 連続緩和問題 or LP緩和問題 が見つかって 教科書p.2には 線形緩和 と書かれている いれば を見つけた 段階で x 3の領域を 調べる必要はなく こ の子問題を捨てること ができる 理由 領域 での目的関 数の最大値は その領 域の整数点での目的関 数の最大値以上 ctx Ax b x 0 xj は整数 ctx Ax b x 0 x 3 20

6 数独 数独は,2,...,の数字を8個のセルに割り振る問題 j i i 行 j 列の セル (i, j) どのセルにも入る数字はただ1つ どの行にも各数字が1つ どの列にも各数字が1つ どのブロックにも各数字が1つ 2 22 B 数字 s, 行 i, 列 j に対応した変数 xsij = s= j= xsij = xsij = xsij = 0 個のブロック 数字 s をセル (i,j) に入れる場合 そうでない場合 (i =, 2,..., ; j =, 2,..., ) B B2 B3 B4 B5 B6 B7 B8 B (s =, 2,..., ; i =, 2,..., ) (s =, 2,..., ; j =, 2,..., ) xsij = (s =, 2,..., ; k =, 2,..., ) (i,j) Bk i= 23 24

7 x sij = (i, j =, 2,..., ) s= x sij = (s, i =, 2,..., ) j= x sij = (s, j =, 2,..., ) i= (i,j) B k x sij = (s, k =, 2,..., ) p.7 i vi kg wi x sij {0, } (s, i, j =, 2,..., ) x sij = p v i /w i 2. w + + w k b<w + + w k + w k+ k 3. n v i x i i= n w i x i b i= x = = x k = 0 x i (i =,...,n) x k+ =(b w w k )/w k+ x k+2 = = x n =0 0 y z z k z k+ z n x x k x k+ x n w... w k w k+... w n b 0 0 v vk vk+ vn 27 28

8 . v /w vk /wk vk+ /wk+ vn /wn primal k objective function kvalue = j= vj + vk+ (b j= wk )/wk+ 2. w + + wk b < w + + wk + wk+ for j =,... k (b w wk )/wk+ for j = k + 3. xj = 0 for j = k + 2,..., n. y = vk+ /wk+ vi ywi 2. zi = 0 dual feasibility * y = vk+ /wk+ 0 vi ywi = vi (vk+ /wk+ )wi = wi (vi /wi vk+ /wk+ ) 0 for i =,..., k * zi = 0 0 for i = k +,..., n wi y + (vi ywi ) = vi vi for i =,..., k * wi y + zi = wi y = vi ( wvk+ / wvii ) vi for i = k +,..., n k+ for i =,..., k for i = k +,..., n dual objective function k kvalue k k k = yb+ i= zi = (b i= wi )y+ i= vi = i= vi +vk+ (b i= wi )/wk+ は双対許容解で 主問題と双対問題の目的間数値が一致 弱双対定理の系 primal objective function value = dual objective function value 3の解は主問題の最適解 2 30 巡回セールスマン問題 p.8 地点 i と地点 j の距離 移動時間 wij が所与 弱双対定理の系 x : 主問題の許容解 y : 双対問題の許容解 ctx = ytb あるいは yt(b!ax)=0 ある地点から出発して全ての地点を丁 x は主問題の最 適解 y は双対問題の 最適解 度1回ずつ訪問して戻ってくる道筋 巡回路 ハミルトン閉路 の中で最 小の距離の道筋を求める問題 基盤配線 運搬経路計画 スケジューリング 基盤 孔 X線結晶構造解析 (タンパク質の構造解析) VLSI 設計 3 32

9 V : E : V S! = 2 n n! = 0 3 => 2 00 = (2 0 ) 0 (0 3 ) 0 = 0 30!. S S polyhedral combinatorics 7/02 ISBN-0: , ISBN-3:

10 p.2 n n m minimize w i y i + c ij x ij x ij y i i= n x ij = b j i= m x ij a i y i j= y i {0, } x ij 0 i= j= : i j : i (j =,...,m) (i =,...,n) (i =,...,n) (i =,...,n; j =,...,m) minimize a ij = i j 0 n c j x j j= n a ij x j j= i x j {0, } (i =,...,m) (j =,...,n) j (0,) [a ij]0, m n c c 2 c 3 x x x 2 x 3 x 4 x 5 x 6 x 7 x x = x + x 2 + x 3 z + z 2 + z 3 = 0 x B z B z 2 x 2 B 2 z 2 B 2 z 3 x 3 B 3 z 3 z,z 2,z 3 {0, } B B 2 B

11 (0,) c 2 c 3 c x = x + x 2 + x 3 z z 2 z 3 B B2 B3 x # # B z 2 x B z (B 2 B )z 3 x 2 (B 2 B )z 2 x 3 (B 3 B 2 )z 3 z,z 2,z 3 {0, } # 4 42 p.30 w x w x + α (a Ax) w x x : w x + α (a Ax) x w x + α (a Ax) =w x 43 44

12 w x β 0 w x + β (b Bx) w x β 0 x : β 0 x w x + β (b Bx) w x w x + α (a Ax)+β (b Bx) # # Branching Tree # 47

情報システム評価学 ー整数計画法ー

情報システム評価学 ー整数計画法ー 情報システム評価学 ー整数計画法ー 第 1 回目 : 整数計画法とは? 塩浦昭義東北大学大学院情報科学研究科准教授 この講義について 授業の HP: http://www.dais.is.tohoku.ac.jp/~shioura/teaching/dais08/ 授業に関する連絡, および講義資料等はこちらを参照 教員への連絡先 : shioura (AT) dais.is.tohoku.ac.jp

More information

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

最適化手法 第1回 [3mm] 整数計画法 (1) [3mm] 1 (1) & 2014 4 9 ( ) (1) 2014 4 9 1 / 39 2013 ( ) (1) 2014 4 9 2 / 39 OR 1 OR 2 OR Excel ( ) (1) 2014 4 9 3 / 39 1 (4 9 ) 2 (4 16 ) 3 (4 23 ) 4 (4 30 ) 5 (5 7 ) 6 (5 14 ) 7 1 (5 21 ) ( ) (1) 2014 4 9 4

More information

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

,, etc. ( ) [Marti & Stoeckel 04] [Lloyd Smith, Chuang & Munro 90], [Staat & Heitzer 03] worst-case detection [Elishakoff, Haftka & Fang 94] 2 [Cheng ( ) ( ) OPTIS 2006 p.1/17 ,, etc. ( ) [Marti & Stoeckel 04] [Lloyd Smith, Chuang & Munro 90], [Staat & Heitzer 03] worst-case detection [Elishakoff, Haftka & Fang 94] 2 [Cheng et al. 02], [Craig et al.

More information

. p.1/34

. p.1/34 . p.1/34 (Optimization) (Mathematical Programming),,. p.2/34 1 1.1 1.2 1.3 2 2.1 2.2 2.3 2.4 2.5 3 4 5. p.3/34 1 1.1 1.2 1.3 2 2.1 2.2 2.3 2.4 2.5 3 4 5. p.4/34 4x + 2y 6, 2x + y 6, x 0, y 0 x, yx + yx,

More information

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

( ) () () ( ) () () () () 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

More information

OR学会チュートリアル はじめよう整数計画

OR学会チュートリアル はじめよう整数計画 OR 学会春季研究発表会チュートリアル 数理計画法 (RAMP) 研究部会企画 はじめよう整数計画法 藤江哲也 兵庫県立大学大学院経営研究科 04 年 3 月 7 日 ( 金 ) 大阪大学豊中キャンパス OR 学会誌 0 年 4 月号 本チュートリアルの目指すところ はじめてコース 初級コース 初中級コース 中級コース 上級コース 初めてラケットを持つ方のコースです 簡単なルールやマナーなども覚えます

More information

! Aissi, H., Bazga, C., & Vaderpoote, D. (2009). Mi max ad mi max regret versios of combiatorial optimizatio problems: A survey. Europea joural of ope

! Aissi, H., Bazga, C., & Vaderpoote, D. (2009). Mi max ad mi max regret versios of combiatorial optimizatio problems: A survey. Europea joural of ope mi max regret l m ( ) ! Aissi, H., Bazga, C., & Vaderpoote, D. (2009). Mi max ad mi max regret versios of combiatorial optimizatio problems: A survey. Europea joural of operatioal research, 197(2), 427-438.!

More information

1 911 9001030 9:00 A B C D E F G H I J K L M 1A0900 1B0900 1C0900 1D0900 1E0900 1F0900 1G0900 1H0900 1I0900 1J0900 1K0900 1L0900 1M0900 9:15 1A0915 1B0915 1C0915 1D0915 1E0915 1F0915 1G0915 1H0915 1I0915

More information

> > <., 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

> > <., 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 13 2 13.0 2 ( ) ( ) 2 13.1 ( ) ax 2 + bx + c > 0 ( a, b, c ) ( ) 275 > > 2 2 13.3 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 >

More information

Microsoft PowerPoint - mp11-06.pptx

Microsoft PowerPoint - mp11-06.pptx 数理計画法第 6 回 塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 第 5 章組合せ計画 5.2 分枝限定法 組合せ計画問題 組合せ計画問題とは : 有限個の もの の組合せの中から, 目的関数を最小または最大にする組合せを見つける問題 例 1: 整数計画問題全般

More information

三者ミーティング

三者ミーティング Corral Puzzle の 整数計画法による解法と評価 第 11 回組合せゲーム パズル研究集会 2016 年 月 7 日 ( 月 ) 大阪電気通信大学 弘中健太鈴木裕章上嶋章宏 2016//7 第 11 回組合せゲーム パズル研究集会 2 発表の流れ 研究の背景 整数計画法と先行研究 2 Corral Puzzle ルールと定義 定式化 2 種類の閉路性の定式化 7 1 6 評価 計測結果と考察

More information

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

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 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

More information

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

最適化手法 第5回 [3mm] 整数計画法 (5) [3mm] 5 (5) 2014 5 8 ( ) (5) 2014 5 8 1 / 60 Gomory Chvátal 2013 ( ) (5) 2014 5 8 2 / 60 3x 1 + 4x 2 x 1,x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z x 2 3x 1 +11x 2 = 66 ( ) 3 4 3x 1 x 2 = 12

More information

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

OR 2 Excel 2 3.. 4. OK. 1a: Excel2007 Office. Excel2003 1.. 1b. 2.. 3. OK. 2.,,. ツール アドイン 1b: Excel2003 :,.,.,.,,,.,,. 1. Excel2003. OR 2 Excel 1 2 2.1 Excel.,. 2.2, x mathematical programming optimization problem, OR 1., 1 : f(x) h i (x) = 0, i = 1,..., m, g j (x) 0, j = 1,..., l, f(x) h i (x) = 0, i = 1,..., m, g j (x) 0, j = 1,...,

More information

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

n 2 n (Dynamic Programming : DP) (Genetic Algorithm : GA) 2 i 15 Comparison and Evaluation of Dynamic Programming and Genetic Algorithm for a Knapsack Problem 1040277 2004 2 25 n 2 n (Dynamic Programming : DP) (Genetic Algorithm : GA) 2 i Abstract Comparison and

More information

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 -

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 - GLPK by GLPK http://mukun mmg.at.infoseek.co.jp/mmg/glpk/ 17 7 5 : update 1 GLPK GNU Linear Programming Kit GNU LP/MIP ILOG AMPL(A Mathematical Programming Language) 1. 2. 3. 2 (optimization problem) X

More information

nakata/nakata.html p.1/20

nakata/nakata.html p.1/20 http://www.me.titech.ac.jp/ nakata/nakata.html p.1/20 1-(a). Faybusovich(1997) Linear systems in Jordan algebras and primal-dual interior-point algorithms,, Euclid Jordan p.2/20 Euclid Jordan V Euclid

More information

研修コーナー

研修コーナー l l l l l l l l l l l α α β l µ l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l

More information

9 ZIMPL 言語と SCIP による数理最適化 Mathematical Optimization with ZIMPL and SCIP ネットワーク情報学部 School of Network and Information 高野祐一 Yuichi TAKANO Keywords : Mat

9 ZIMPL 言語と SCIP による数理最適化 Mathematical Optimization with ZIMPL and SCIP ネットワーク情報学部 School of Network and Information 高野祐一 Yuichi TAKANO Keywords : Mat 9 ZIMPL 言語と SCIP による数理最適化 Mathematical Optimization with ZIMPL and SCIP ネットワーク情報学部 School of Network and Information 高野祐一 Yuichi TAKANO Keywords : Mathematical optimization, Software, Modeling language,

More information

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

( ) ? () 1.1 ( 3 ) j x j 10 j 1 10 j = 1,..., 10 x 1 + x x 10 = 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,...,

More information

1 Ricci V, V i, W f : V W f f(v ) = Imf W ( ) f : V 1 V k W 1

1 Ricci V, V i, W f : V W f f(v ) = Imf W ( ) f : V 1 V k W 1 1 Ricci V, V i, W f : V W f f(v = Imf W ( f : V 1 V k W 1 {f(v 1,, v k v i V i } W < Imf > < > f W V, V i, W f : U V L(U; V f : V 1 V r W L(V 1,, V r ; W L(V 1,, V r ; W (f + g(v 1,, v r = f(v 1,, v r

More information

Microsoft PowerPoint - 13.ppt [互換モード]

Microsoft PowerPoint - 13.ppt [互換モード] 13. 近似アルゴリズム 1 13.1 近似アルゴリズムの種類 NP 困難な問題に対しては多項式時間で最適解を求めることは困難であるので 最適解に近い近似解を求めるアルゴリズムが用いられることがある このように 必ずしも厳密解を求めないアルゴリズムは 大きく分けて 2 つの範疇に分けられる 2 ヒューリスティックと近似アルゴリズム ヒュ- リスティクス ( 発見的解法 経験的解法 ) 遺伝的アルゴリズム

More information

漸化式のすべてのパターンを解説しましたー高校数学の達人・河見賢司のサイト

漸化式のすべてのパターンを解説しましたー高校数学の達人・河見賢司のサイト https://www.hmg-gen.com/tuusin.html https://www.hmg-gen.com/tuusin1.html 1 2 OK 3 4 {a n } (1) a 1 = 1, a n+1 a n = 2 (2) a 1 = 3, a n+1 a n = 2n a n a n+1 a n = ( ) a n+1 a n = ( ) a n+1 a n {a n } 1,

More information

1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The Boston Public Schools system, BPS (Deferred Acceptance system, DA) (Top Trading Cycles system, TTC) cf. [13] [

1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The Boston Public Schools system, BPS (Deferred Acceptance system, DA) (Top Trading Cycles system, TTC) cf. [13] [ Vol.2, No.x, April 2015, pp.xx-xx ISSN xxxx-xxxx 2015 4 30 2015 5 25 253-8550 1100 Tel 0467-53-2111( ) Fax 0467-54-3734 http://www.bunkyo.ac.jp/faculty/business/ 1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The

More information

untitled

untitled ,, 2 2.,, A, PC/AT, MB, 5GB,,,, ( ) MB, GB 2,5,, 8MB, A, MB, GB 2 A,,,? x MB, y GB, A (), x + 2y () 4 (,, ) (hanba@eee.u-ryukyu.ac.jp), A, x + 2y() x y, A, MB ( ) 8 MB ( ) 5GB ( ) ( ), x x x 8 (2) y y

More information

nlp1-04a.key

nlp1-04a.key 自然言語処理論 I. 文法 ( 構文解析 ) その 構文解析 sytctic lysis, prsig 文の構文的な構造を決定すること句構造文法が使われることが多い文法による構文木は一般に複数ある 構文木の違い = 解釈の違い 構文解析の目的 句構造文法の規則を使って, 文を生成できる構文木を全て見つけだすこと 文法が入力文を生成できるかどうかを調べるだけではない pro I 構文解析とは 構文木の違い

More information

9. 05 L x P(x) P(0) P(x) u(x) u(x) (0 < = x < = L) P(x) E(x) A(x) P(L) f ( d EA du ) = 0 (9.) dx dx u(0) = 0 (9.2) E(L)A(L) du (L) = f (9.3) dx (9.) P

9. 05 L x P(x) P(0) P(x) u(x) u(x) (0 < = x < = L) P(x) E(x) A(x) P(L) f ( d EA du ) = 0 (9.) dx dx u(0) = 0 (9.2) E(L)A(L) du (L) = f (9.3) dx (9.) P 9 (Finite Element Method; FEM) 9. 9. P(0) P(x) u(x) (a) P(L) f P(0) P(x) (b) 9. P(L) 9. 05 L x P(x) P(0) P(x) u(x) u(x) (0 < = x < = L) P(x) E(x) A(x) P(L) f ( d EA du ) = 0 (9.) dx dx u(0) = 0 (9.2) E(L)A(L)

More information

II

II II 16 16.0 2 1 15 x α 16 x n 1 17 (x α) 2 16.1 16.1.1 2 x P (x) P (x) = 3x 3 4x + 4 369 Q(x) = x 4 ax + b ( ) 1 P (x) x Q(x) x P (x) x P (x) x = a P (a) P (x) = x 3 7x + 4 P (2) = 2 3 7 2 + 4 = 8 14 +

More information

数値計算:有限要素法

数値計算:有限要素法 ( ) 1 / 61 1 2 3 4 ( ) 2 / 61 ( ) 3 / 61 P(0) P(x) u(x) P(L) f P(0) P(x) P(L) ( ) 4 / 61 L P(x) E(x) A(x) x P(x) P(x) u(x) P(x) u(x) (0 x L) ( ) 5 / 61 u(x) 0 L x ( ) 6 / 61 P(0) P(L) f d dx ( EA du dx

More information

1 105 2 4 50 3 ISBN 4 25 2013 1 ISBN 5 128p ISBN978-4-8340-0013-9 ISBN 2

1 105 2 4 50 3 ISBN 4 25 2013 1 ISBN 5 128p ISBN978-4-8340-0013-9 ISBN 2 1 2 39 3 14 13 16 17 36 21 30 32 1 1 105 2 4 50 3 ISBN 4 25 2013 1 ISBN 5 128p ISBN978-4-8340-0013-9 ISBN 2 39 32p ISBN978-4-251-00517-5 62p ISBN978-4-00-110579-7 1 33p ISBN978-4-477-01141-7 3 32p ISBN978-4-591-01270-3

More information

0 00 000 000 ISBN 0 0 0 ISBN 0 0 0 ISBN---.00-

0 00 000 000 ISBN 0 0 0 ISBN 0 0 0 ISBN---.00- 0 0 0 --- -0--0-- 00 0 00-0 0 0 0 0 000-00- 0 00 000 000 ISBN 0 0 0 ISBN 0 0 0 ISBN---.00- 0 00 000 000 ISBN 0 0 0 ISBN 0 0 0 ISBN---.00- ISBN 0 0 0 ISBN 0 0 0 0 00 000 000 ISBN---.00- 0 00 000 000 ISBN

More information

496

496 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 ISBN4-258-17041-0

More information

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

More information

ISBN 0 00 00 00 0 0 ISBN 0 0 ISBN---.000-0

ISBN 0 00 00 00 0 0 ISBN 0 0 ISBN---.000-0 ISBN 0 00 00 00 0 0 ISBN 0 0 ISBN---.000-0 0 ISBN 0 00 00 00 0 0 ISBN 0 0 ISBN---.000-0 ISBN 0 00 00 00 0 0 ISBN 0 0 ISBN---.000-0 ISBN 0 00 00 00 0 0 ISBN 0 0 ISBN---.000-0 ISBN 0 00 00 00 0 0 ISBN 0

More information

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

More information

知能科学:ニューラルネットワーク

知能科学:ニューラルネットワーク 2 3 4 (Neural Network) (Deep Learning) (Deep Learning) ( x x = ax + b x x x ? x x x w σ b = σ(wx + b) x w b w b .2.8.6 σ(x) = + e x.4.2 -.2 - -5 5 x w x2 w2 σ x3 w3 b = σ(w x + w 2 x 2 + w 3 x 3 + b) x,

More information

知能科学:ニューラルネットワーク

知能科学:ニューラルネットワーク 2 3 4 (Neural Network) (Deep Learning) (Deep Learning) ( x x = ax + b x x x ? x x x w σ b = σ(wx + b) x w b w b .2.8.6 σ(x) = + e x.4.2 -.2 - -5 5 x w x2 w2 σ x3 w3 b = σ(w x + w 2 x 2 + w 3 x 3 + b) x,

More information

例 e 指数関数的に減衰する信号を h( a < + a a すると, それらのラプラス変換は, H ( ) { e } e インパルス応答が h( a < ( ただし a >, U( ) { } となるシステムにステップ信号 ( y( のラプラス変換 Y () は, Y ( ) H ( ) X (

例 e 指数関数的に減衰する信号を h( a < + a a すると, それらのラプラス変換は, H ( ) { e } e インパルス応答が h( a < ( ただし a >, U( ) { } となるシステムにステップ信号 ( y( のラプラス変換 Y () は, Y ( ) H ( ) X ( 第 週ラプラス変換 教科書 p.34~ 目標ラプラス変換の定義と意味を理解する フーリエ変換や Z 変換と並ぶ 信号解析やシステム設計における重要なツール ラプラス変換は波動現象や電気回路など様々な分野で 微分方程式を解くために利用されてきた ラプラス変換を用いることで微分方程式は代数方程式に変換される また 工学上使われる主要な関数のラプラス変換は簡単な形の関数で表されるので これを ラプラス変換表

More information

3345 チュートリアル 1 HP テンソル代数 テンソル解析 - - 連続体力学の数理的基礎 - 第 4 講テンソル解析 - テンソル場の微積分 - 登坂宣好 第 4 講概要 2, 3 1 筆者紹介 1971 Engineering Science gradient divergence rota

3345 チュートリアル 1 HP テンソル代数 テンソル解析 - - 連続体力学の数理的基礎 - 第 4 講テンソル解析 - テンソル場の微積分 - 登坂宣好 第 4 講概要 2, 3 1 筆者紹介 1971 Engineering Science gradient divergence rota 3345 チュートリアル 1 HP テンソル代数 テンソル解析 - - 連続体力学の数理的基礎 - 第 4 講テンソル解析 - テンソル場の微積分 - 登坂宣好 第 4 講概要 2, 3 1 筆者紹介 1971 Engineering cience gradient divergence rotation nabla 3 1 2 3 4 5 6 ol.20, No.4 2015 27 1 [1,2]

More information

Microsoft PowerPoint - 15意思決定科学3_LP復習.pptx

Microsoft PowerPoint - 15意思決定科学3_LP復習.pptx 意思決定科学 線形計画法 堀田敬介 205/0/9,Fr. はじめに 問題の見直し問題の本質を再考 モデルの妥当性評価現実との乖離の検証 問題モデル化解く解釈 評価 提案 解決 問題 目的の明確化 代替案立案モデル構築 結果の解釈 評価代替案評価 選択 意思決定 最適化モデル 線形計画法 凸 2 次計画法 錐計画法 整数計画法 線形計画法 例題 : 効率的なアルバイト 時給 200 円の清掃作業,

More information

ii 3.,. 4. F. (), ,,. 8.,. 1. (75%) (25%) =7 20, =7 21 (. ). 1.,, (). 3.,. 1. ().,.,.,.,.,. () (12 )., (), 0. 2., 1., 0,.

ii 3.,. 4. F. (), ,,. 8.,. 1. (75%) (25%) =7 20, =7 21 (. ). 1.,, (). 3.,. 1. ().,.,.,.,.,. () (12 )., (), 0. 2., 1., 0,. 24(2012) (1 C106) 4 11 (2 C206) 4 12 http://www.math.is.tohoku.ac.jp/~obata,.,,,.. 1. 2. 3. 4. 5. 6. 7.,,. 1., 2007 (). 2. P. G. Hoel, 1995. 3... 1... 2.,,. ii 3.,. 4. F. (),.. 5... 6.. 7.,,. 8.,. 1. (75%)

More information

CVaR

CVaR CVaR 20 4 24 3 24 1 31 ,.,.,. Markowitz,., (Value-at-Risk, VaR) (Conditional Value-at-Risk, CVaR). VaR, CVaR VaR. CVaR, CVaR. CVaR,,.,.,,,.,,. 1 5 2 VaR CVaR 6 2.1................................................

More information

双対問題

双対問題 一次式とノルムで構成された最適化問題とその双対問題 第一部ゲージ最適化問題とその応用問題 2018 年 7 月 25 日 ( 本資料は 7 月 30 日に改訂 ) 京都大学大学院情報学研究科 山下信雄 本講演の概要 第 1 部一般化ゲージ最適化問題とその応用問題 第 2 部ゲージ関数とその諸性質 第 3 部一般化ゲージ最適化問題の双対問題 I. ラグランジュ双対問題とFenchel 双対問題 II.

More information

2 1 1 α = a + bi(a, b R) α (conjugate) α = a bi α (absolute value) α = a 2 + b 2 α (norm) N(α) = a 2 + b 2 = αα = α 2 α (spure) (trace) 1 1. a R aα =

2 1 1 α = a + bi(a, b R) α (conjugate) α = a bi α (absolute value) α = a 2 + b 2 α (norm) N(α) = a 2 + b 2 = αα = α 2 α (spure) (trace) 1 1. a R aα = 1 1 α = a + bi(a, b R) α (conjugate) α = a bi α (absolute value) α = a + b α (norm) N(α) = a + b = αα = α α (spure) (trace) 1 1. a R aα = aα. α = α 3. α + β = α + β 4. αβ = αβ 5. β 0 6. α = α ( ) α = α

More information

Microsoft PowerPoint - no1_19.pptx

Microsoft PowerPoint - no1_19.pptx 数理計画法 ( 田地宏一 ) Inroducion o ahemaical Programming 教科書 : 新版数理計画入門, 福島雅夫, 朝倉書店 011 参考書 : 最適化法, 田村, 村松著, 共立出版 00 工学基礎最適化とその応用, 矢部著, 数理工学社 006,Linear and Nonlinear Opimizaion: second ediion, I.Griba, S.G.

More information

…p…^†[…fiflF”¯ Pattern Recognition

…p…^†[…fiflF”¯   Pattern Recognition Pattern Recognition Shin ichi Satoh National Institute of Informatics June 11, 2019 (Support Vector Machines) (Support Vector Machines: SVM) SVM Vladimir N. Vapnik and Alexey Ya. Chervonenkis 1963 SVM

More information

( ) FAS87 FAS FAS87 v = 1 i 1 + i

( ) FAS87 FAS FAS87 v = 1 i 1 + i ( ) ( 7 6 ) ( ) 1 6 1 18 FAS87 FAS87 7 1 FAS87 v = 1 i 1 + i 10 14 6 6-1 - 7 73 2 N (m) N L m a N (m) L m a N m a (m) N 73 9 99 18 4-2 - 4 143 2 145 3 37 4 37 4 40 6 40 6 41 10 41 10 13 10 14 4 24 3 145

More information

main.dvi

main.dvi SGC - 70 2, 3 23 ɛ-δ 2.12.8 3 2.92.13 4 2 3 1 2.1 2.102.12 [8][14] [1],[2] [4][7] 2 [4] 1 2009 8 1 1 1.1... 1 1.2... 4 1.3 1... 8 1.4 2... 9 1.5... 12 1.6 1... 16 1.7... 18 1.8... 21 1.9... 23 2 27 2.1

More information

第6章 実験モード解析

第6章 実験モード解析 第 6 章実験モード解析 6. 実験モード解析とは 6. 有限自由度系の実験モード解析 6.3 連続体の実験モード解析 6. 実験モード解析とは 実験モード解析とは加振実験によって測定された外力と応答を用いてモードパラメータ ( 固有振動数, モード減衰比, 正規固有モードなど ) を求める ( 同定する ) 方法である. 力計 試験体 変位計 / 加速度計 実験モード解析の概念 時間領域データを利用する方法

More information

スライド タイトルなし

スライド タイトルなし アルゴリズム入門 (8) ( 近似アルゴリズム ) 宮崎修一京都大学学術情報メディアセンター 近似アルゴリズムとは? 効率よく解ける問題 ( 多項式時間アルゴリズムが存在する問題 ) ソーティング 最短経路問題 最小全域木問題 効率よく解けそうにない問題 (NP 困難問題 ) 最小頂点被覆問題 MX ST MX CUT 本質的に問題が難しいのだが 何とか対応したい 幾つかのアプローチ ( 平均時間計算量

More information

17 ( :52) α ω 53 (2015 ) 2 α ω 55 (2017 ) 2 1) ) ) 2 2 4) (α β) A ) 6) A (5) 1)

17 ( :52) α ω 53 (2015 ) 2 α ω 55 (2017 ) 2 1) ) ) 2 2 4) (α β) A ) 6) A (5) 1) 3 3 1 α ω 53 (2015 ) 2 α ω 55 (2017 ) 2 1) 2000 2) 5 2 3 4 2 3 5 3) 2 2 4) (α β) 2 3 4 5 20 A 12 20 5 5 5) 6) 5 20 12 5 A (5) 1) Évariste Galois(1811-1832) 2) Joseph-Louis Lagrange(1736-1813) 18 3),Niels

More information

広報さっぽろ 2016年8月号 厚別区

広報さっぽろ 2016年8月号 厚別区 8/119/10 P 2016 8 11 12 P4 P6 P6 P7 13 P4 14 15 P8 16 P6 17 18 19 20 P4 21 P4 22 P7 23 P6 P7 24 25 26 P4 P4 P6 27 P4 P7 28 P6 29 30 P4 P5 31 P5 P6 2016 9 1 2 3 P4 4 P4 5 P5 6 7 8 P4 9 10 P4 1 b 2 b 3 b

More information

untitled

untitled 1 ( 12 11 44 7 20 10 10 1 1 ( ( 2 10 46 11 10 10 5 8 3 2 6 9 47 2 3 48 4 2 2 ( 97 12 ) 97 12 -Spencer modulus moduli (modulus of elasticity) modulus (le) module modulus module 4 b θ a q φ p 1: 3 (le) module

More information

( ) (, ) arxiv: hgm OpenXM search. d n A = (a ij ). A i a i Z d, Z d. i a ij > 0. β N 0 A = N 0 a N 0 a n Z A (β; p) = Au=β,u N n 0 A

( ) (, ) arxiv: hgm OpenXM search. d n A = (a ij ). A i a i Z d, Z d. i a ij > 0. β N 0 A = N 0 a N 0 a n Z A (β; p) = Au=β,u N n 0 A ( ) (, ) arxiv: 1510.02269 hgm OpenXM search. d n A = (a ij ). A i a i Z d, Z d. i a ij > 0. β N 0 A = N 0 a 1 + + N 0 a n Z A (β; p) = Au=β,u N n 0 A-. u! = n i=1 u i!, p u = n i=1 pu i i. Z = Z A Au

More information

Microsoft PowerPoint - 13approx.pptx

Microsoft PowerPoint - 13approx.pptx I482F 実践的アルゴリズム特論 13,14 回目 : 近似アルゴリズム 上原隆平 (uehara@jaist.ac.jp) ソートの下界の話 比較に基づく任意のソートアルゴリズムはΩ(n log n) 時間の計算時間が必要である 証明 ( 概略 ) k 回の比較で区別できる場合の数は高々 2 k 種類しかない n 個の要素の異なる並べ方は n! 通りある したがって少なくとも k n 2 n!

More information

目    次

目    次 1 2 3 t 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 IP 169 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

More information

PowerPoint Presentation

PowerPoint Presentation 最適化手法 第 回 工学部計数工学科 定兼邦彦 http://researchmap.jp/sada/resources/ 前回の補足 グラフのある点の隣接点をリストで表現すると説明したが, 単に隣接点の集合を持っていると思ってよい. 互いに素な集合のデータ構造でも, 単なる集合と思ってよい. 8 3 4 3 3 4 3 4 E v 重み 3 8 3 4 4 3 {{,},{3,8}} {{3,},{4,}}

More information

/ 2 n n n n x 1,..., x n 1 n 2 n R n n ndimensional Euclidean space R n vector point R n set space R n R n x = x 1 x n y = y 1 y n distance dx,

/ 2 n n n n x 1,..., x n 1 n 2 n R n n ndimensional Euclidean space R n vector point R n set space R n R n x = x 1 x n y = y 1 y n distance dx, 1 1.1 R n 1.1.1 3 xyz xyz 3 x, y, z R 3 := x y : x, y, z R z 1 3. n n x 1,..., x n x 1. x n x 1 x n 1 / 2 n n n n x 1,..., x n 1 n 2 n R n n ndimensional Euclidean space R n vector point 1.1.2 R n set

More information

1 4 1 ( ) ( ) ( ) ( ) () 1 4 2

1 4 1 ( ) ( ) ( ) ( ) () 1 4 2 7 1995, 2017 7 21 1 2 2 3 3 4 4 6 (1).................................... 6 (2)..................................... 6 (3) t................. 9 5 11 (1)......................................... 11 (2)

More information

01

01 2 0 0 7 0 3 2 2 i n d e x 0 7. 0 2. 0 3. 0 4. 0 8. 0 9. 1 0. 1 1. 0 5. 1 2. 1 3. 1 4. 1 5. 1 6. 1 7. 1 8. 1 9. 2 0. 2 1. 2 3. 2 4. 2 5. 2 6. O k h o t s k H a m a n a s u B e e f 0 2 http://clione-beef.n43.jp

More information

<4D F736F F D B B83578B6594BB2D834A836F815B82D082C88C60202E646F63>

<4D F736F F D B B83578B6594BB2D834A836F815B82D082C88C60202E646F63> Visual Basic でわかるやさしい有限要素法の基礎 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. http://www.morikita.co.jp/books/mid/092001 このサンプルページの内容は, 初版 1 刷発行当時のものです. URL http://www.morikita.co.jp/soft/92001/ horibe@mx.ibaraki.ac.jp

More information

Microsoft PowerPoint - 資料04 重回帰分析.ppt

Microsoft PowerPoint - 資料04 重回帰分析.ppt 04. 重回帰分析 京都大学 加納学 Division of Process Control & Process Sstems Engineering Department of Chemical Engineering, Koto Universit manabu@cheme.koto-u.ac.jp http://www-pse.cheme.koto-u.ac.jp/~kano/ Outline

More information

1 n 1 1 2 2 3 3 3.1............................ 3 3.2............................. 6 3.2.1.............. 6 3.2.2................. 7 3.2.3........................... 10 4 11 4.1..........................

More information

ii 3.,. 4. F. ( ), ,,. 8.,. 1. (75% ) (25% ) =7 24, =7 25, =7 26 (. ). 1.,, ( ). 3.,...,.,.,.,.,. ( ) (1 2 )., ( ), 0., 1., 0,.

ii 3.,. 4. F. ( ), ,,. 8.,. 1. (75% ) (25% ) =7 24, =7 25, =7 26 (. ). 1.,, ( ). 3.,...,.,.,.,.,. ( ) (1 2 )., ( ), 0., 1., 0,. (1 C205) 4 10 (2 C206) 4 11 (2 B202) 4 12 25(2013) http://www.math.is.tohoku.ac.jp/~obata,.,,,..,,. 1. 2. 3. 4. 5. 6. 7. 8. 1., 2007 ( ).,. 2. P. G., 1995. 3. J. C., 1988. 1... 2.,,. ii 3.,. 4. F. ( ),..

More information

Microsoft PowerPoint - DA2_2017.pptx

Microsoft PowerPoint - DA2_2017.pptx // データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (II)/ 全点対最短路 トポロジカル ソート順による緩和 トポロジカル ソート順に緩和 閉路のない有向グラフ限定 閉路がないならトポロジカル ソート順に緩和するのがベルマン フォードより速い Θ(V + E) 方針 グラフをトポロジカル ソートして頂点に線形順序を与える ソート順に頂点を選び, その頂点の出辺を緩和する 各頂点は一回だけ選択される

More information

a n a n ( ) (1) a m a n = a m+n (2) (a m ) n = a mn (3) (ab) n = a n b n (4) a m a n = a m n ( m > n ) m n 4 ( ) 552

a n a n ( ) (1) a m a n = a m+n (2) (a m ) n = a mn (3) (ab) n = a n b n (4) a m a n = a m n ( m > n ) m n 4 ( ) 552 3 3.0 a n a n ( ) () a m a n = a m+n () (a m ) n = a mn (3) (ab) n = a n b n (4) a m a n = a m n ( m > n ) m n 4 ( ) 55 3. (n ) a n n a n a n 3 4 = 8 8 3 ( 3) 4 = 8 3 8 ( ) ( ) 3 = 8 8 ( ) 3 n n 4 n n

More information

waseda2010a-jukaiki1-main.dvi

waseda2010a-jukaiki1-main.dvi November, 2 Contents 6 2 8 3 3 3 32 32 33 5 34 34 6 35 35 7 4 R 2 7 4 4 9 42 42 2 43 44 2 5 : 2 5 5 23 52 52 23 53 53 23 54 24 6 24 6 6 26 62 62 26 63 t 27 7 27 7 7 28 72 72 28 73 36) 29 8 29 8 29 82 3

More information