Model Building in Mathematical Programming: 6.1 〜 6.3
Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。
Optimization Night #3 等に現をうかしていたため、2周分まとめての更新です。
Chapter 6
6.1 Validating a model
モデルの検証ちゃんとやりましょうというお話。とっても大事。モデルは大きく分けて3つある。
- Infeasible models
- 実行可能解が存在しないような場合、たいてい間違っている。なぜなら、数理最適化って今人手でやっている仕事を置き換えることが多いから。いま人手でやっているのは最適とは限らないが実行可能解のはず。定式化が間違っている可能性が高い。
- ちなみに、違反している制約を列挙するのは簡単だが、その原因を見つけるのは数式からだけだととても難しい。なぜなら、infeasibleになるのは制約1つではなく制約の組み合わせに依って発生するから。
- だからこそ、制約を聞きつつ、過去データ（人手でやってきた記録）を入手しておくのがとても大事。過去データを入力してみて、違反している制約がないか確認する。
- unbounded models
- 今度はいくらでも解を良くできてしまう場合。だいたいの場合、制約を追加し忘れている。
- ソルバーがある程度頑張ったところで解を出力してくれるので、その解を見ながら、抜けている制約を検討する。結構極端な値になるので、制約を見つけるのは簡単なことが多そう。
- solvable models
- 最適解がえられたとしても油断してはいけない。現実的な解がえられているか見極める必要がある。
- ただ、ひとまず最適解がえられていれば、それをもとに結果がおかしくないか検証して、抜けている制約をあぶり出したりできるのでうれしい。
梅谷先生の資料のように、モデルはイテレーションを回しながら作り上げていくのだ。
6.2 Economic interpretations
ここでは具体例を通じて双対問題の解説をしつつ用語を整理している。
- reduced costs: 被役費用。最適解近傍で、変数の値を微少量動かしたときに、最適解の値がどれくらいかわるか
- shadow price: 制約を微少量動かしたときに、最適解がどれくらいかわるか
双対問題や双対変数に具体的な解釈を与えるのはいいが、一般性があるわけでもないので、微妙だと思うんだけどどうだろう。 この章はちゃんと理解できているか微妙なので、もう一度読む。
6.3 Sensitivity analysis and the stability of a model
6.3.1 Right-hand side ranges
いわゆる感度分析。制約を動かした時、一定の範囲内であれば、 shadow price にしたがって最適値が変化する。 一方、一定の範囲を超えてしまうと、それが成り立たなくなる。
なぜかといえば、下図のように有効な制約が変わるから。LPは一般的に複数の制約の交点が解になっている。制約を徐々に動かしていく（例えば図のABをA'B'に動かすイメージ）と、その制約の組が変わる（図のDやCEに到達する）ことがあって、それ以降は shadow price に従わなくなる。
6.3.2 Objective ranges
制約ではなくて目的関数にあらわれる係数をかえるとどうなるか、という話。下図でいうと、目的関数の等高線PQの傾きを変える。ただ、具体的な応用例があまりイメージできなかった。予測値とかを使っていてブレる可能性がある場合にどれくらい安定的かとか考えるときに使うのかな？
6.3.3 Ranges on interior coefficients
もちろん制約式の中の係数も変化できるけど、それほど有用ではないっぽい。ほんとかな。
6.3.4 marginal rates of substitution
制約を動かしたときに、変数がどう動くかを見るのも重要。ちょっとややこしいので、輪読会の中でもこんがらがっていたので整理。
考えるのは以下のLPで、式(6.45)の右辺 4 を少し動かしたときに、最適解の や
はどう変化するか。
この問題の実行可能領域は下図の通りになっていて、式(6.45)を変化させるのは、(0,4) と A を結ぶ直線を動かすことに対応している。
最適解は A なので、 や
がどう変化するかというのは、 つまりA がどう動くかというはなしで、この場合は 式(6.46)の表す直線（ 図でいうと A と (2, 1) を結ぶ直線）の上を動くことになる。具体的には、
が -1 だけ動いて
が +2 動くことになる。
これは marginal rates of substitution と呼ばれる量らしい。現実問題だと、例えばある原材料の供給量が増えたり減ったりしたときに、製造計画をどう変えるべきか、という話に対応するので、とても重要。
6.3.5
結局、現実的な問題だと、最適な解よりも（状況の変化に対して）安定な解が求められることが多い。そうですよね。
TODO
- 宿題: 12.15
