0-8

Model Building in Mathematical Programming: 5.1〜5.2

数理最適化

Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。

宿題 (12.24 Yield Management)

普通、航空機の座席の料金はファースト、ビジネス、エコノミーといた座席のクラスだけではなくて、購入時期にも依って変わります。出発がまだまだ先の場合は、そこそこの値段、少し近づいてくるとちょっと安くなって、直前になると高くなる、みたいなのはなんとなく知られていると思います。

今回の宿題では、この航空機の座席の値段を最適化しましょう、というのがお題でした。具体的には3週間後に出発する飛行機について、1週間ごとに座席の値段を調整できて、座席の値段によって需要が変わる場合に、どうすると利益を最大化できるか、という問題です。これを、複数のシナリオ（需要の予測値）があるとして、確率計画法で解きます。

設定が結構複雑なので、アドバイスにしたがって、はじめにいろいろな要件を無視して簡略化したモデルを定式化して、それを修正していく形で解きました。それもあって、書籍の解答例の定式化とは結構違ったものになったと思う。あとで比較してみよう。

それ以外に思ったのは、

  1. 確率計画法だと、すべての可能性を列挙しないといけないので、変数が爆発的に増えて計算がしんどくなる。と思ったけど、今回の例に関して言えば、そうでもない。今回は結局、確率計画法で列挙しなければいけないのが需要変数だけで、かつシナリオの数も3つ（正確には3つ x 期間 x 座席クラス x 取れる価格付けのオプション数）だったから。
  2. 設定が複雑になると、定式化が正しいか、制約はあらいだされているか、を確認するのが難しい。 そのため実案件では、クライアントに提示しては「なんとなく感覚とあわないなぁ」を繰り返す。だからこそ、はじめは汎用ソルバーを使って、とにかく修正を簡単にしておくのが大事。
  3. 予測値がどれくらい外れると、どれくらい最適化に影響するのか調べてみよう。

自分の解答は以下の通り。最後のまではやっていない。

colab.research.google.com

Chapter 5

5.1 Typical applications

線型計画法（というか数理計画法）の応用事例がまとまっている。これは知っておいたほうが良い。資源配分問題はほぼすべての業種で使われていて、それ以外には以下のような事例がある。これも後で具体例と紐づけて、ちゃんと整理しよう。

  1. 石油産業
    • 混合、販売など
  2. 化学産業
  3. 製造業
  4. 運輸業
    • 配送、積み替え、施設配置など
  5. 経理財務
  6. 農業
    • 混合、配送、価格最適化など
  7. 医療
    • スケジューリング、腫瘍への放射線の照射量など
  8. 鉱業
  9. マンパワー計画
  10. 食品エネルギー
    • 結構使われているらしい。
  11. 製紙産業
    • 祭壇ロスの最小化、古紙のリサイクルなど
  12. 広告業
    • 予算配分、メディアスケジューリングなど
  13. 軍事
    • ミサイル基地の配置など
  14. サプライチェーン
    • もろもろ。複数の要素が組み合わさっているので、個々で最適化しようとすると、うまく行かないケースがあるので注意が必要らしい。

教科書が古いので、最近の事例を知りたいという話をしてみたが、そんなに変わっていないらしい（実際には 5th Edition なので最近の事例も追加されている）。昔から結構色んな分野で話があるのに、社会実装が進んでいないという話を聞いてしみじみした。

5.2 Economic models

（正直な話をすると、前日ほぼ徹夜だったため、頭が働かなくなってしまったので、話がちゃんとはいってこなくって、あとで読み直した）

Input-Output モデルと呼ばれるモデルについての紹介。Leontief model とも呼ばれる。複数の産業が絡み合いかたを、それぞれの産業のInputとOutputという形で表現して、その関係性を調べる。例えば、

  1. 各産業でどれくらい生産すると、外需を満たせるか
  2. どれくらい労働力が必要化
  3. 各Outputは、いくらの価値があるか

などを線形計画法をつかって導き出す。最適化したい、というよりは、上記のような課題に合わせて、目的関数を選ぶようなイメージ。

例題は3個の産業だけで成り立っている仮想的な国だったが、実際の国の産業の数（要は、解きたい問題に応じて、同じ性質を持っているものを適当な粒度にまとめたもの）は半端ない。過去の例では、1000固程度までまとめて解析したことがあるらしいが、この1000個というのが（本書ではとても少ないと書かれているが）少ないのかどうか、感覚がなさすぎて、よくわからなかった。

産業がたかだか1000個であれば、簡単に解けそうに思えるかもしれないが、普通の線型計画法の問題と違って、出てくる行列がかなり密（50%くらい非ゼロだったりするらしい）なので、計算時間は結構かかるとのこと。

うちの会社は大きく3つないし4つの事業の組み合わせになっているので、これを使ってなにかしら分析できないだろうか、とか考えたりした。

TODO

  1. Chapter 5 の続きを読む
  2. 宿題（12.24 Yield Management）のコードの整理
  3. 事例の整理
  4. 前回考えていた「双対を知らないでも図形で列生成法を理解する」ができないか引き続き考える

結構やること多い。