OR-A 第2回

「ORーA」
2011/12/10
• 一般的な定式化の仕方
– 整数変数はなぜ登場するか?
– Indicator変数の使い方(今回の主題)
• Reading Assignment: 配布資料 「数理計画モ
デルの定式化」
1
整数変数がどうして登場するか
(1)分割不可能な離散的変量 Indivisible
(Discrete) Quantities :
本来、整数しかとりえない量;例えば、人数、
機械台数など
(2)デシジョン変数 Decision Variables :
複数の代替案の中からどの案を選択する
かを示す 例: 倉庫をたてる(どのタイプの)/たてない
γ=0
γ=1
γ=2
倉庫をたてない
タイプAの倉庫をたてる
タイプBの倉庫をたてる
2
整数変数がどうして登場するか
(3)インディケータ変数 Indicator
Variables: システムの状態を示す
(indicateする)ために、0-1変数と他の変
数、あるいは他の条件式と結びつける
3
インディケータ変数(Indicator Variables)
xA:ある(原料)配合において要素Aが含まれる比率
要素Aが配合に含まれる(xA>0)か、含まれないか(xA=
0)を、たとえば、0-1変数αを使って識別する。つまり、
α=1(0)ならAが含まれる(含まれない)、という形で、
インディケータ変数を使う。
たとえば、
(1) xA - α ≦ 0
という制約条件は、次の論理条件(もし・・・ならば・・・)を
数式的に表現することになる:
(2) xA>0 → α=1
4
(2)式の逆表現
(2)の逆、すなわち、
(3) α=1 → xA>0
(あるいは、その対偶のxA=0 → α=0)
という条件を(も)数式的に表現したい。
残念ながらこれはできないので、そのかわりに、「Aの配合
比率がこれ未満だったら入っていないも同然」という閾値
(threshold level)mを導入し、(3)を
(4) α=1 → xA≧m
に変換すると、(4)は次のように数式表現できる:
(5) xA - mα ≧ 0
注意: 数理計画では、通常、>や<を扱わず、≦や≧を扱
う。
5
演習問題1
(1)「もし要素Aが配合に含まれていたなら
ば、要素Bも配合に含まれていなければな
らない」、という条件を数式で表現せよ。
(2)さらに、その逆、すなわち、「もし要素B
が配合に含まれていたならば、要素Aも配
合に含まれていなければならない」という
条件も、あわせて成立しなければいけない
というときはどうすればよいか。
6
インディケータ変数を使って
不等式/等式の成立/不成立を示す
1. 「δ=1 → Σjajxj≦b」型論理条件の表現
0-1変数δを使って、不等式が成立するか
否かに関する論理条件を表現する。
論理条件
(11) δ=1 → Σjajxj≦b
は、次の不等式で表現できる:
(12) Σjajxj+Mδ≦M+b
ここに、M はΣjajxj-bの上界である。
7
(12)式の妥当性
• (12)式が(11)の論理条件を表現していること
を確かめるために、(12)式を書き換えると、
(12)’
Σjajxj-b≦M(1-δ)
となる。δ=1のときには右辺が0となり(12)’式
は
Σjajxj≦bとなり、論理条件(11)が満足される。
• 一方、δ=0のときには、Σjajxj-b≦Mとなるが、
Mの定義から、この式は常時満足される。論理
条件(11)を数式表現するとき、表現された数式
は、δ=0のときになにかを意味してはまずい。
換言すれば、δ=0のときは数式が意味を持っ
ては困ることに注意。
8
論理条件に対応する数式の「作成公式」
ステップ1 「δ=1→Σjajxj≦b」形の論理条件にする。
ステップ2 右辺bを左辺に移項しΣjajxj-b≦0の形に。
ステップ3 右辺0の代わりに、δの(1次)関数を考え
る。この関数はδ=1のとき0、そうでないときは制
約条件式が無意味、すなわち、すべての解が生成さ
れる制約条件式を満足するようにしたい。
このため、右辺を□(1-δ)の形(□は適当な定
数)にすると、Σjajxj-b≦M(1-δ)が望む制約条
件式となる。ただし、MはΣjajxj-bの上界値とする。
9
ステップ1
「δ(0-1変数)=1→Σjajxj≦b」の形に
注意1: 不等式の向きが逆、すなわち、≧ならば、
-1倍して、不等号の向きを変える。
注意2: 論理条件が、「Σjajxj≦b→δ=0」のとき
は、対偶をとって、「δ=1→Σjajxj>b」の形にし
た上で、閾値εを用いて、
「δ=1→Σjajxj≧b+ε」、すなわち、
「δ=1→Σj(-aj)xj≦-b-ε」
の形に変換されたものを与えられた論理条件と
考えればよい。
10
ステップ3
Σjajxj-b≦□(1-δ)
注意3: 望む制約条件式の右辺は、δが1のとき
0となって、論理条件が表現されことになる。一
方、δ=0のときには、□の定数を適当に決める。
M=左辺のとりうる値の上界とすれば、すべての
解がこの制約条件を満足し、したがって、制約条
件はなにも意味しないことになる。
注意4: 右辺の上界Mはあまり大きすぎない値が
望ましい。
11
「δ=0 → Σjajxj≦b」型
論理条件の表現
「公式」のステップ3の M(1-δ)の部分を、
Mδに置き換えれば同様な議論ができる
ステップ3’ ステップ2の形Σjajxj-b≦0の、
右辺の0をMδに置き換える。
12
論理条件(1)の逆の数式表現
(「逆は必ずしも真ならず」に注意)
(13) Σjajxj≦b →δ=1
対偶をとることによって、「δ=0→Σjajxj>b」とな
り、注意2のように、
「δ=0→Σj(-aj)xj≦-b-ε」、すなわち、
「δ=0→Σj(-aj)xj+b+ε≦0」
とする。あとは、ステップ3’にしたがって、
(14) Σj(-aj)xj+b+ε≦M ’δ
ここに、M ’はΣj(-aj)xj+b+εの上界値とする。
13
演習問題2
0-1インディケータ変数δを用いて、δが1の
とき以下の制約を満たすという条件を数式
として表現せよ。また、逆に、この制約が
満たされているとき、δが1になるという条
件を数式として表現せよ。いずれにせよ、
x1,x2は、0≦x1≦1, 0≦x2≦1の範囲にある
ものとする。
2x1+3x2≦1
14
必要十分条件の表現
必要十分条件「δ=1 ⇔ Σjajxj≦b」を数式的に表現す
るためにはどうすればよいか
「δ=1→Σjajxj≦b」 AND 「δ=1←Σjajxj≦b」
(12)
(14)
(12) Σjajxj+Mδ≦M+b
(14) Σj(-aj)xj+b+ε≦M ’δ
15
論理条件と0-1変数
δi が0-1のインディケータ変数とし、Xiが
δi=1という状態を示すこととする。
(A)
X1∨X2
δ1+δ2≧1
(B)
X1・X2
δ1=1,δ2=1
(C)
~X1
δ1=0(1-δ1=1)
(D)
X1→X2
δ1-δ2≦0
(E)
X1←→X2 δ1-δ2=0
16
演習問題3:生産
(Xi:製品i が生産されている)
以下の論理条件を表現したいとしよう:
(21) (XA∨XB)→(XC∨XD∨XE)
インディケータ変数δi を使い、δi が1(0)の
ときは、製品 i が作られている(作られてい
ない)ことを示すものとしよう。このとき、
(21)を数式的に表現することを考えたい。
(ヒント)δA+δB≧ 1 ⇒ δ=1
⇒ δC+δD+δE ≧ 1
17
施設配置問題
関東地方を中心に営業を行ってきた輸入品販売業の
K社では、関西地方に活動を拡大するため、京阪神地方
に倉庫の賃借を行う計画を立てている。賃借の候補とな
る倉庫はmカ所にあって、第i地点の倉庫Wi(i=1,・・・,m)の
月間処理能力はai(トン/月)で、その経費(賃借料や維
持費など毎月の固定費)はdi(千円/月)である。また、
関西一円に広がる消費地Dj(j=1,・・・,n)での輸入品の需
要量bj(トン/月)と、WiからDjへのトン当たり輸送費cij
(千円)が与えられたとして、すべての需要を満たし、毎
月の総費用(倉庫経費+輸送費)を最小にする倉庫配置
と輸送計画を求めたい。この問題を数理計画問題として
定式化せよ。
18
施設配置問題の定式化
• 目的関数(総費用最小):
最小化 z = Σi diyi + ΣiΣj
• 制約
Σj =1,…,n
Σi =1,…,m
cijxij
xij≦aiyi , ∀i (処理能力)
xij≧bj , ∀j (需要)
xij≧0, ∀i 、j
yi =0 or 1 ∀i
• 論理条件: yi =0 ⇒ Σj =1,…,n
xij≦0
(借りていない倉庫から送り出してはならない)
19
施設配置問題の定式化:別解
• 目的関数(総費用最小):
最小化 z = Σi diyi + ΣiΣj
• 制約
Σj =1,…,n
Σi =1,…,m
cijxij
xij≦ai ,i=1, 2 ,…, m
xij≦aiyi ∀i 、j
xij≧bj ,j=1, 2 ,…, n
xij≧0,yi =0 or 1 ∀i 、j
• 論理条件: yi =0 ⇒ xij≦0
20
問題例1 候補地1、2、3の中から一つ
選択し、候補地4、5の中から一つ選択
より正確には、
候補地1、2、3の中から一つ選択し、かつ、
候補地4、5の中から一つ選択
数 理 計 画 で は 、 制 約 条 件 は AND で か か る
δ1+ δ2+ δ3=1
δ4+ δ5=1
21
問題例2 候補地2を選択したときには、候
補地4または5の少なくともいずれか選択
δ2=1 ⇒ δ4+ δ5≧1
備考:この場合、別途δを導入する必要はない
δ2=1 ⇒ ーδ4ーδ5+1≦0
ーδ4ー δ5+1≦□(1ー δ2 )
ーδ4ーδ5+1≦(1ーδ2)
∴ δ2 ーδ4ー δ5≦0 (必ず、「検算」する)
22
問題例3 候補地2を選択したときには、
候補地4または5のいずれか1つを選択
δ2=1 ⇒ δ4+ δ5=1
間違った解答例:
1) δ4+ δ5=δ2 (δ2が0のとき、δ4+δ5=0?,No!)
2) δ2 ーδ=0,-δ4ー δ5 +δ =0
正しい考え方:
δ2=1 ⇒ ーδ4ー δ5+1≦0 ① (前と同じ) かつ
δ2=1 ⇒
δ4+ δ5ー1≦0 ②
δ4+ δ5ー1≦□(1ーδ2)
δ4 + δ5 ー 1 ≦ ( 1 ー δ2 )
∴ δ2 +δ4+ δ5≦2
②
∴ δ2 ーδ4ー δ5≦0
①
23
問題例4 候補地1または2を選択したと
きは、候補地3、4、5のいずれかを選択
解釈が4つありうる
解釈1:候補地1,2の少なくとも1つを選択したときは、候補地
3,4,5の少なくとも1つを選択
δ1+ δ2≧1 ⇒ δ3 + δ4+ δ5≧1
解釈2:候補地1,2のいずれか1つを選択したときには、候補
地3,4,5の少なくとも1つを選択
δ1+ δ2=1 ⇒ δ3 + δ4+ δ5≧1
解釈3:候補地1,2の少なくとも1つを選択したときは、候補地
3,4,5のいずれか1つを選択
δ1+ δ2≧1 ⇒ δ3 + δ4+ δ5=1
解釈4:候補地1,2のいずれか1つを選択したときには、候補
地3,4,5のいずれか1つを選択
δ1+ δ2=1 ⇒ δ3 + δ4+ δ5=1
24
問題例4(解釈1a) 候補地1,2の少なくとも
1つを選択したときは、候補地3,4,5の
少なくとも1つを選択
δ1+ δ2≧1 ⇒ δ3 + δ4+ δ5≧1
スマートな解答:
候補地i を選択するという事象をXi とすると、解釈1は
X 1∪X 2⇒X 3∪X 4∪X 5
と等価; ところが、これは、
X 1⇒X 3∪X 4∪X 5 、かつ、X 2⇒X 3∪X 4∪X 5
と等価
δ1=1 ⇒ δ3 + δ4+ δ5≧1
∴ δ3 + δ4+ δ5≧δ1
δ2=1 ⇒ δ3 + δ4+ δ5≧1
∴ δ3 + δ4+ δ5≧δ2
①
①
②
②
25
問題例4(解釈1b) 候補地1,2の少なくとも
1つを選択したときは、候補地3,4,5の
少なくとも1つを選択
δ1+ δ2≧1 ⇒ δ3 + δ4+ δ5≧1
「公式」に忠実な解答:
δ1+ δ2≧1 ⇒ δ=1 ⇒ δ3 + δ4+ δ5≧1
㊧の対偶
δ=0 ⇒ δ1+ δ2≦0
①
∴ δ1 + δ2 ≦ 2δ
①
㊨
δ=1 ⇒ δ3 + δ4+ δ5≧1 ②
∴ δ3 + δ4+ δ5≧δ
②
26
問題例4(解釈2) 候補地1,2のいず
れか1つを選択したときには、候補地
3,4,5の少なくとも1つを選択
δ1+ δ2=1 ⇒ δ3 + δ4+ δ5≧1
「公式」に忠実な解答:
δ1+ δ2=1 ⇒ δ=1 ⇒ δ3 + δ4+ δ5≧1
㊧
㊨
㊧の対偶
㊨
δ=0 ⇒ δ1+ δ2≦0 or δ1+ δ2≧2 ①
δ=0 ⇒ γ1+ γ2≧1
②
γ1=1 ⇒ δ1+ δ2≧2
③
γ2=1 ⇒ δ1+ δ2≦0
④
∴ γ1 + γ2 +δ ≧1
②
∴ δ1 + δ2 ー 2 γ1 ≧ 0 ③
∴ δ1 + δ2 + 2 γ2 ≦ 2 ④
δ=1 ⇒ δ3 + δ4+ δ5≧1
⑤
∴ δ3 + δ4+ δ5≧δ
⑤
27
OR条件の一般化,拡張
(A)
X1∨X2
δ1+δ2≧1
↓
複数項のOR条件
(A’)
X1∨X2∨・・・∨Xn
δ1+δ2 +・・・+δn≧1
複数項の中から少なくともk 個以上
(A’’) X1,X2,・・・,Xnの中からk 個以上
δ1+δ2 +・・・+δn≧k
OR条件ではないが,同様に,複数項の中から高々k 個
(A’’’) X1,X2,・・・,Xnの中から高々k 個
δ1+δ2 +・・・+δn≦k
28
OR条件の応用例
凸でない実行可能領域の表現
ABJO S1={x=(x1,x2): x2≦3,x1+x2≦4,x≧0}
ODH S2= {x=(x1,x2): ーx1+x2≦0, 3x1ーx2≦8,x≧0}
KFGO S3= {x=(x1,x2): x2≦1,x1≦5,x≧0}
• もしも問題の条件が、 x∈ S1 ∪S2∪S3のとき...
実行可能領域は
非凸!!!
数理計画問題の
定式化で
「または」と
書けない 29
線形計画問題の実行可能領域
ABJO S1={x=(x1,x2): x2≦3,x1+x2≦4,x≧0}
ODH S2= {x=(x1,x2): ーx1+x2≦0, 3x1ーx2≦8,x≧0}
KFGO S3= {x=(x1,x2): x2≦1,x1≦5,x≧0}
• もしも、問題の条件が、 x∈ S1 ∩S2∩S3のとき...
30
凸でない実行可能領域
ABJO S1={x=(x1, x2): x2≦3,x1+x2≦4,x≧0}
ODH S2= {x=(x1, x2): ーx1+x2≦0, 3x1ーx2≦8,x≧0}
KFGO S3= {x=(x1, x2): x2≦1,x1≦5,x≧0}
• もしも問題の条件が、 x∈ S1 ∪S2∪S3のとき...
• インディケータ変数δ1 ,δ2 ,δ3を導入:
δ1 =1⇒x∈ S1 , δ2 =1⇒x∈ S2 , δ3 =1 ⇒x∈ S3
換言すると、 δ1 =1 ⇒ (x2≦3)・(x1+x2≦4)・ (x≧0)
①
δ2 =1 ⇒(ーx1+x2≦0)・(3x1ーx2≦8)・(x≧0) ②
δ3 =1 ⇒ (x2≦1)・(x1≦5)・ (x≧0)
③
• ①、②、③に加えて、δ1 +δ2 +δ3 ≧1
31
凸でない実行可能領域(続き)
ABJO S1={x=(x1, x2): x2≦3,x1+x2≦4,x≧0}
• 論理条件①は、数式に変換可能
δ1 =1 ⇒ (x2≦3)・(x1+x2≦4)・(x≧0)
①
• δ1 =1 ⇒ x2≦3
①’
δ1 =1 ⇒ x1+x2≦4
①”
δ1 =1 ⇒ x≧0 (非負条件が別途考慮されているならば不要)
• 論理条件②、③も同様
• ①’、①”、②’、②”、③’、③”、xの非負条件に
加えて、 δ1 +δ2 +δ3 ≧1
32
SOS(特殊順序集合)変数制約
(SOS=Specially Ordered Set)
SOS 1=一連の変数の集まり(実数変数で
も整数変数でも可;SOS1変数群)の中か
らちょうど1個が0でない
SOS 2=順序が定められた一連の変数の
集 ま り ( 実 数 変 数 で も 整 数 変 数 で も可 ;
SOS2変数群)の中から,「隣りあう」高々2
個が0でない
33
SOS1変数制約
(SOS=Specially Ordered Set)
SOS 1=一連の変数の集まり(実数変数で
も整数変数でも可;SOS1変数群)の中か
らちょうど1個が0でない
実数変数: x1 ,x2 ,・・・,xn の中で1個が正
0-1変数: δ1+δ2 +・・・+δn = 1
どんな例があるか考えてみよう
34
OR条件の拡張の応用例
解の中の変数の数を制限する
• 正の値をとる変数の数を一定個数以下(以
上)にしたい
– 例:株式jへの投資金額xjの決定の決定にあたっ
て、投資対象の株式数をk以下に抑えたい
xj>0 ⇒ δj=1
xjーMjδj≦0
ただし、Mjは株式jへの投資金額xjの上限
δ1+ δ2 +・・・+δn ≦ k
35
SOS2変数制約
(SOS=Specially Ordered Set)
SOS 2=順序が定められた一連の変数の
集 ま り ( 実 数 変 数 で も 整 数 変 数 で も可 ;
SOS2変数群)の中から,「隣りあう」高々2
個が0でない
(λ1 ,λ2 ,・・・,λn )の中で「隣りあう」高々
2個が正
λ1+λ2 +λ3+λ4 + ・・・+λn = 1
36
SOS2制約の例
(SOS=Specially Ordered Set)
Minimize z = x12-4x1-2x2
s.t.
x1 + x2 ≦ 4
2x1 + x2 ≦ 5
- x1+4x2 ≧ 2
x1 , x2 ≧ 0
非線形関数を含むモデルが解けない場合に何ができるか
ヒント: Minimize z = y -4x1-2x2
y =・・・
(λ1 ,λ2 ,・・・,λn )≧0 の中で「隣りあう」高々2個が正
λ1+λ2 +λ3+λ4 + ・・・+λn = 1
37
非線形関数の折れ線近似
λ1
λ2
λ3
λ4
λ5
38
SOS2制約の例
(SOS=Specially Ordered Set)
Minimize z =y -4x1-2x2
s.t.
x1 + x2 ≦ 4
2x1 + x2 ≦ 5
- x1+4x2 ≧ 2
x1 , x2 ≧ 0
x1 = 0λ1+ 0.5λ2 +1λ3+ 1.5λ4 + ・・・+?λn
y = 0λ1+0.25λ2 +1λ3+2.25λ4 + ・・・+?λn
λ1 + λ2 + λ3 + λ4 + ・・・+ λn = 1
(λ1 ,λ2 ,・・・,λn )≧0 の中で「隣りあう」高々2個が正
39
非線形関数の折れ線近似
λ1
0
λ2
λ3
λ4
0.5
0.5
λ5
0
0
40
宿題10
宿題10.1 3次元3目並べ(配布資料p.16,問
4)の定式化を示せ.なお,余裕がある人は
Excel ソルバー、またはAMPLで解け.(ソ
ルバーファイル、または、AMPLのmod,run
ファイルは,メールの添付にて
[email protected]宛に題名「OR-A: 学籍
番号 氏名」で送付のこと)
宿題10.2 スライド44のシナリオを定式化せよ.
締切:2011年12月15日(木) 18時
森戸研メールボックス
41
3次元3目並べ(配布資料p.16)
• 各マスに1から27まで番号をつける
• 各 マ ス j ( j = 1,…,27) に 白 な ら 0 、 黒 な ら 1 と い う
0-1変数xjを定義
• 「線」に番号をつける(「線」は何本あるか?)
• 同色の線の本数を数え,その本数を最小化する
42
線形計画モデルの特殊形
最大値の最小化
• 通常の線形計画モデル
Min z =cx =Σj=1,…,ncjxj
s.t.
Ax≦b,x≧0
• 最大値の最小化
Min (Maxi=1,…,mΣj=1,…,ncijxj)
s.t.
Ax≦b,x≧0 (通常の1次制約式)
• 最大値の最小化は通常のLPに変換可能
Min
z
s.t.
Σj=1,…,ncijxj ー z≦0,
i=1,…,m
Ax≦b,x≧0 (通常の1次制約式) 43
特殊な定式化の応用
宿題10.2 以下のシナリオを定式
化せよ
• ある議会の議員定員はM人である
• 議員はN(<M)個の選挙区から選挙され
る
• 選挙区jの人口(選挙権を持つ人の人口)
pjは既知である
• 人口1人当たりの議員数(逆に、議員1人
当たりの人口、でもよい)の最大値と最小
値の差を最小化する議員定数の配分(各
選挙区の議員定数)を決めたい
44