Model Building in Mathematical Programming: Chapter 3 〜 3.2.3
Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。
宿題（12.1 Food manufacture 1）
はじめの1時間は宿題（12.1 Food manufacture 1）の答え合わせと議論になった。 僕の答案はColaboratoryで共有。 はじめ一部の条件の解釈を間違えていたけど、それ以外はだいたい正しそう（Colaboratoryは修正済）。
典型的な線形計画問題なので、英語の解釈を除いて定式化に悩むことはなかったが、補助変数を追加することの是非について議論になった。今回の例だと、
月末の在庫 = 初期在庫 + その月までの購入量 - その月までの使用量
となるが、「月末の在庫」にあえて変数を割り当てるかどうか。要は、等式制約しか入っておらず事前に展開することが可能なので、あえて「月末の在庫」変数を作る必要はないのではないか、という話。こういった補助変数を追加したほうが式の見た目がスッキリして解釈しやすくなるし、バグの混入も減らせる。では、計算量という観点で変数が増えるのは問題ないのかというと、あまり問題にならないことが多そう。ソルバー的には補助変数にまとめられているものをバラすのは簡単だが、あらかじめバラしてしまったものをまとめるのは難しい。なので、もちろん場合によるが、まずは変数の数が増えるとかはあまり気にせずに補助変数を追加しておけば良さそう。
Chapter 3
3.1 The importance of linearity
線形計画問題（目的関数も制約も線形な数理計画問題）は、他の問題に比べて解くのが簡単なので重要。もちろん、現実的な問題では、それでは間に合わないことも多いけど、非線形な問題の近似になるので、やっぱり重要。
3.2 Defining objectives
よく出てくる目的関数一覧
- 利益（最大化）
- コスト（最小化）
- 効用（最大化）
- 売上（最大化）
- ROI（最大化）
- NPV（最大化）
- 従業員数（最大化・最小化）
- 余剰（最小化）
- 顧客満足度（最大化）
- 生存確率（最大化）
- 堅牢性（最大化）
3.2.1 Single objectives
よく出てくる目的関数として「利益」や「コスト」を挙げたが、正確には「利益への貢献」、「変動コスト」とすべき。というのも、線型計画問題の場合は変数が連続量のみなので、固定コストは最適化できないので。これはなるほどなと思った。
あと、利益を最大化する問題では、製品 1単位あたりの貢献利益を
、需要を
とすると、利益は
で表せるが、単価が需要によって影響を受けるような場合、
が定数でないため、目的関数が線形でなくなってしまうので注意が必要。
3.2.2 Multiple Objective
多目的最適化（複数の目的関数を同時に最適化）の方法は、大別して以下の3つがある。
- 目的関数を個別に最適化する
- それぞれの目的関数を使って最適化問題を解き、結果を比較する
- 目的関数を制約に変換する
- 1つだけ残して、後は制約として取り入れる
- 目的関数の線形和を最適化する
- 重みの調整が大変で、経験的には、目的関数が3つか4つくらいまでは、勘がよければうまくいくことがあるらしい。データが大きく変わると重みも調整しないといけなくなるので、似たようなデータが来ることがわかっているような状況では良いかも、というコメントがあって、これもなるほどなと思った。
- 受託分析をしている立場から言うと、良い悪いはおいておいて「顧客に調整できる余地を残しておく」というのは重要だったりするので、そういう観点では他の2つよりも使い勝手は良いのかもしれない。
多目的最適化については、以下の Minimax を使うことが多いという意見も出た。例えば Optimization Night の梅谷先生の資料の電子ジャーナル購読では、各雑誌それぞれについて、充足率を最大化したいところを、最小充足率の最大化として定式化している。
3.3.3 Minimax Objectives
Minimax（ある値を最大値を最小化する）問題は、最大化したいものの上限を表す変数 を導入すれば、（最大化したい値が
以下であるという）線形な制約をもった最小化問題になる。一方で、Maximax問題は線形計画問題に帰着できず整数計画問題となるということが書かれていたが、そもそも Maximax 問題がどういうものなのかすらイメージできなかった。
TODO
- Chapter 3、 Chapter 4 を読む
