夏ゼミ1章前半

実際の問題を数式で書き下して、最適解を得
るための方法論。
 通常、１つの目的関数と満たすべき条件を記
述した複数の制約式で構成される。
 目的関数は問題の総費用や総利益を表すの
で、これを最大化、最小化することが目的。

線形最適化問題(linear optimization)
 非線形最適化問題(nonlinear optimization)
 二次最適化問題(quadratic optimization)

NP-Hard
整数最適化問題(integer optimization)
 混合整数最適化問題(mixed integer
optimization)

maximize 15x1 +18x2 +30x3
subject to 2x1 + x2 +x3 ≤ 60
x1 +2x2 +x3 ≤ 60
x3 ≤ 30
x1, x2, x3 ≥ 0
目的関数
制約式
このように変数x1,x2,x3を定数倍したものを足し合わせた
形を線形といい、制約式の下で目的関数を最大化・最小
化する問題を線形最適化問題という。
変数の組x1, x2, x3 を解(solution) と呼び，す
べての制約式を満たす解を実行可能解
(feasible solution) と呼ぶ。
 実行可能解の中で目的関数を最大化（もしくは
最小化）するものを最適解(optimal solution)
と呼ぶ．
 最適解における目的関数の値を，最適目的関
数値(optimal objective function value) また
は単に最適値(optimal value)と呼ぶ。

Python/Gurobiを用いた解法手順
1. Gurobiのモジュールを読み込む
2. モデルの定義
3. 変数の定義
4. モデルのアップデート
5. 制約式の記述
6. 目的関数の記述
7. Optimizeメソッドで解く
8. 最適解、最適値の出力
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
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= 1230.0
x1 10.0
x2 10.0
x3 30.0
鶴と亀とタコが何匹かずついる。
頭の数を足すと32，足の数を足すと80になる．
亀とタコの数の和を一番小さくするような匹数を求めよ．
鶴がx匹、亀がy匹、タコがz匹いたとする。目的関数をy+zが
最小になるようにとれば、以下のように定式化できる。
minimize
定式化①
y+z
subject to x + y + z = 32
2x +4y +8z = 80
x, y, z ≥ 0
これを解くと、
最適解が
x=29.3333
y=0
z=2.66667
となり、現実では
ありえない答え
になってしまう
最適解が整数になるように、x,y,zがそれぞれ整数である
という制約を付け加えると、以下のようになる。
minimize
定式化②
y+z
subject to x + y + z = 32
2x +4y +8z = 80
x, y, z は非負の整数
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
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)= 28.0 2.0 2.0
5人の顧客（需要地点）に対して，3つの工場で生産した製品を
運ぶ必要がある。工場の生産可能量（容量），顧客への輸送費
用，ならびに各顧客における需要量は，表のようになっている。
どのような輸送経路を選択すれば，総費用が最小になるか？
顧客 i
1
2
3
4
5
需要量
di
80
270
250
160
180
工場 j
容量
Mj
輸送費用 cij
1
4
5
6
8
10
500
2
6
4
3
5
8
500
3
9
7
4
3
4
500
表：工場の容量、輸送費用、需要量
顧客の集合をI = {1, 2, . . . , n}、
工場の集合をJ = {1, 2, . . . , m}とする．
顧客iの需要量をdi、顧客i と工場j 間の1単位の輸送費用を
Cij、工場jの容量をMj とする．工場jから顧客iへの輸送量を
xijとすると、以下のように定式化できる。
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
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 ,
}
1.
2.
3.
4.
5.
6.
7.
8.
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 ( )
for i in I :
model.addConstr ( quicksum( x [ i , j ] for j in J ) == d [ i ] ,
"%i)
name="Demand(%s )
10.
for j in J :
model.addConstr ( quicksum( x [ i , j ] for i in I ) <= M [ j ] , name="Capacity(%s )
"%j)
11.
model.setObjective ( quicksum( c [ i , j ] * x [ i , j ] for ( i , j ) in x ) , GRB.MINIMIZE)
9.
1.
2.
3.
4.
5.
6.
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 )
実行結果
Optimal value: 3370.0
sending quantity 230.0 from factory 2 to customer 3
sending quantity 20.0 from factory 3 to customer 3
sending quantity 160.0 from factory 3 to customer 4
sending quantity 270.0 from factory 2 to customer 2
sending quantity 80.0 from factory 1 to customer 1
sending quantity 180.0 from factory 3 to customer 5
４節の輸送問題について、工場の拡張を考えて
みる．どの工場を拡張すればどのくらいの費用
の削減が期待できるだろうか？
また，各顧客からの追加注文に対しては，どのく
らい追加費用を顧客からもらえば元がとれるだ
ろうか？
双対問題を考える！！
双対問題とは，もとの問題と表裏一体を成す
線形最適化問題のこと。
 双対問題で扱う双対変数は、制約となってい
る資源を１単位分増加させるとどれだけ利益
が増えるかを示している。潜在価格(shadow
price)とも呼ばれる。
 ここでは工場の容量の余裕変数（スラック変
数）と双対変数を調べることで、工場の拡張の
効果と追加費用を求める。

輸送問題のプログラムの最後に次の文を付け加える。
1.
2.
3.
print "Const.Name : Slack , Dual"
for c in model.getConstrs ( ) :
print "%s : %s , %s " %(c.ConstrName , c .
Slack , c . Pi )









実行結果
Const. Name: Slack , Dual
Demand(1): 0.000000 , 4.000000
Demand(2): 0.000000 , 5.000000
Demand(3): 0.000000 , 4.000000
Demand(4): 0.000000 , 3.000000
Demand(5): 0.000000 , 4.000000
Capacity(1): 420.000000 , 0.000000
Capacity(2): 0.000000 ,-1.000000
Capacity(3): 140.000000 , 0.000000

Download Report