１章前半.

Presentation on theme: "１章前半."— Presentation transcript:

1 １章前半

2 １節 数理最適化とは 実際の問題を数式で書き下して、最適解を得るための方法論。
１節　数理最適化とは 実際の問題を数式で書き下して、最適解を得るための方法論。 通常、１つの目的関数と満たすべき条件を記述した複数の制約式で構成される。 目的関数は問題の総費用や総利益を表すので、これを最大化、最小化することが目的。

3 数理最適化問題の種類 線形最適化問題(linear optimization)
非線形最適化問題(nonlinear optimization) 二次最適化問題(quadratic optimization) 整数最適化問題(integer optimization) 混合整数最適化問題(mixed integer optimization) NP-Hard

4 ２節　線形最適化問題 目的関数 maximize 15x1 +18x2 +30x3 subject to 2x1 + x2 +x3 ≤ 60 x1 +2x2 +x3 ≤ 60 x3 ≤ 30 x1, x2, x3 ≥ 0 制約式 このように変数x1,x2,x3を定数倍したものを足し合わせた形を線形といい、制約式の下で目的関数を最大化・最小化する問題を線形最適化問題という。

5 ２節　線形最適化問題② 変数の組x1, x2, x3 を解(solution) と呼び，すべての制約式を満たす解を実行可能解(feasible solution) と呼ぶ。 実行可能解の中で目的関数を最大化（もしくは最小化）するものを最適解(optimal solution) と呼ぶ． 最適解における目的関数の値を，最適目的関数値(optimal objective function value) または単に最適値(optimal value)と呼ぶ。

6 Python/Gurobiを用いた解法手順
２節　線形最適化問題③ Python/Gurobiを用いた解法手順 Gurobiのモジュールを読み込む モデルの定義 変数の定義 モデルのアップデート 制約式の記述 目的関数の記述 Optimizeメソッドで解く 最適解、最適値の出力

7 ２節 線形最適化問題④ from gurobipy import * model = Model ( " lo1 " )
２節　線形最適化問題④ from gurobipy import * model = Model ( " lo1 " ) x1 = model.addVar (name="x1" ) x2 = model.addVar (name="x2" ) x3 = model.addVar (ub=30, name="x3" ) model.update( ) model.addConstr (2* x1 + x2 + x3 <= 60) model.addConstr ( x1 + 2*x2 + x3 <= 60) model.setObjective (15* x1 + 18* x2 + 30*x3 , GRB.MAXIMIZE) model.optimize( ) print "Opt.Value=" ,model.ObjVal for v in model.getVars ( ): print v.VarName , v .X 実行結果 Opt. Value= x1 10.0 x2 10.0 x3 30.0

8 ３節　整数最適化問題 鶴と亀とタコが何匹かずついる。 頭の数を足すと32，足の数を足すと80になる． 亀とタコの数の和を一番小さくするような匹数を求めよ．

9 ３節 整数最適化問題② 定式化① minimize y + z subject to x + y + z = 32
３節　整数最適化問題② 鶴がx匹、亀がy匹、タコがz匹いたとする。目的関数をy+zが 最小になるようにとれば、以下のように定式化できる。 これを解くと、 最適解が x= y=0 z= となり、現実ではありえない答えになってしまう 　　定式化① minimize y + z subject to x + y + z = 32 2x +4y +8z = 80 x, y, z ≥ 0　

10 ３節 整数最適化問題③ 定式化② minimize y + z subject to x + y + z = 32
３節　整数最適化問題③ 最適解が整数になるように、x,y,zがそれぞれ整数である という制約を付け加えると、以下のようになる。 　　定式化② minimize y + z subject to x + y + z = 32 2x +4y +8z = 80 　　　　　　x, y, z は非負の整数　

11 ３節 整数最適化問題④ from gurobipy import * model = Model ( " seisu " )
３節　整数最適化問題④ from gurobipy import * model = Model ( " seisu " ) x = model.addVar ( vtype=" I " ) y = model.addVar ( vtype=" I " ) z = model.addVar ( vtype=" I " ) model.update ( ) model.addConstr ( x + y + z == 32) model.addConstr (2* x + 4*y + 8* z == 80) model.setObjective ( y + z , GRB.MINIMIZE) model.optimize ( ) print "Opt.Val.=" , model.ObjVal print " (x , y , z)=" , x .X, y .X, z .X 実行結果 Opt. Val.= 4.0 (x,y,z)=

12 ４節　輸送問題 5人の顧客（需要地点）に対して，3つの工場で生産した製品を 運ぶ必要がある。工場の生産可能量（容量），顧客への輸送費 用，ならびに各顧客における需要量は，表のようになっている。 どのような輸送経路を選択すれば，総費用が最小になるか？ 顧客 i 1 2 3 4 5 需要量 di 80 270 250 160 180 工場 j 輸送費用 cij 容量 Mj 6 8 10 500 9 7 表：工場の容量、輸送費用、需要量

13 ４節　輸送問題② 顧客の集合をI = {1, 2, , n}、 工場の集合をJ = {1, 2, , m}とする． 顧客iの需要量をdi、顧客i と工場j 間の1単位の輸送費用を Cij、工場jの容量をMj とする．工場jから顧客iへの輸送量を xijとすると、以下のように定式化できる。

14 ４節 輸送問題③ from gurobipy import *
４節　輸送問題③ from gurobipy import * d = { 1 : 80 , 2 : 270 , 3:250 , 4 : 160 , 5:180} M = { 1 : 500 , 2 : 500 , 3:500} I = [ 1 , 2 , 3 , 4 , 5 ] J = [ 1 , 2 , 3 ] I , d = multidict ({ 1 : 80 , 2 : 270 , 3:250 , 4 :160 ,5:180 }) J , M = multidict ({ 1 : 500 , 2 : 500 , 3:500 } ) c = { ( 1 , 1 ) : 4 , ( 1 , 2 ) : 6 , ( 1 , 3 ) : 9 , ( 2 , 1 ) : 5 , ( 2 , 2 ) : 4 , ( 2 , 3 ) : 7 , ( 3 , 1 ) : 6 , ( 3 , 2 ) : 3 , ( 3 , 3 ) : 4 , ( 4 , 1 ) : 8 , ( 4 , 2 ) : 5 , ( 4 , 3 ) : 3 , ( 5 , 1 ) : 10 , ( 5 , 2 ) : 8 , ( 5 , 3 ) : 4 , }

15 ４節 輸送問題④ model = Model ( " transportation " ) x = {} for i in I :
４節　輸送問題④ model = Model ( " transportation " ) x = {} for i in I : for j in J : x [ i , j ] = model.addVar ( vtype="C" , name="x(%s ,%s ) " % ( i , j ) ) model.update ( ) model.addConstr ( quicksum( x [ i , j ] for j in J ) == d [ i ] , name="Demand(%s ) " % i ) model.addConstr ( quicksum( x [ i , j ] for i in I ) <= M [ j ] , name="Capacity(%s ) " % j ) model.setObjective ( quicksum( c [ i , j ] * x [ i , j ] for ( i , j ) in x ) , GRB.MINIMIZE)

16 ４節 輸送問題⑤ model.optimize ( ) print "Optimal value : " , model.ObjVal
４節　輸送問題⑤ model.optimize ( ) print "Optimal value : " , model.ObjVal EPS = 1.e-6 for ( i , j ) in x : if x [ i , j ] .X > EPS: print " sending quantity %10s from factory %3s to customer %3s " % ( x [ i , j ] .X, j , i )

17 ４節 輸送問題⑥ 実行結果 Optimal value: 3370.0
４節　輸送問題⑥ 実行結果 Optimal value: sending quantity from factory 2 to customer 3 sending quantity from factory 3 to customer 3 sending quantity from factory 3 to customer 4 sending quantity from factory 2 to customer 2 sending quantity from factory 1 to customer 1 sending quantity from factory 3 to customer 5

18 ５節　双対問題 ４節の輸送問題について、工場の拡張を考えて みる．どの工場を拡張すればどのくらいの費用 の削減が期待できるだろうか？ また，各顧客からの追加注文に対しては，どのく らい追加費用を顧客からもらえば元がとれるだ ろうか？ 双対問題を考える！！

19 ５節 双対問題② 双対問題とは，もとの問題と表裏一体を成す線形最適化問題のこと。
５節　双対問題② 双対問題とは，もとの問題と表裏一体を成す線形最適化問題のこと。 双対問題で扱う双対変数は、制約となっている資源を１単位分増加させるとどれだけ利益が増えるかを示している。潜在価格(shadow price)とも呼ばれる。 ここでは工場の容量の余裕変数（スラック変数）と双対変数を調べることで、工場の拡張の効果と追加費用を求める。

20 ５節 双対問題③ 輸送問題のプログラムの最後に次の文を付け加える。 print "Const.Name : Slack , Dual"
５節　双対問題③ 輸送問題のプログラムの最後に次の文を付け加える。 print "Const.Name : Slack , Dual" for c in model.getConstrs ( ) : print "%s : %s , %s " %(c.ConstrName , c . Slack , c . Pi )

21 ５節 双対問題④ 実行結果 Const. Name: Slack , Dual Demand(1): 0.000000 , 4.000000
５節　双対問題④ 実行結果 Const. Name: Slack , Dual Demand(1): , Demand(2): , Demand(3): , Demand(4): , Demand(5): , Capacity(1): , Capacity(2): , Capacity(3): ,