OR-A 第2回

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

Download Report