0-8

Model Building in Mathematical Programming: 4.1

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

宿題(12.22 Efficiency Analysis)

いわゆる DEA (Data Envelopment Analysis, 包絡分析) の問題。自動車メーカーが複数のガレージとフランチャイズ契約を結んでいる設定で、各ガレージの効率を評価する.

DEA の概念は知っていたが、具体的な使いかたや解放は知らなかったので、勉強になった。 宿題を解く上で参考にさせてもらった こちらの解説記事 はとてもわかり易かったのでおすすめ。

DEA では、入力(店舗の広さやスタッフ数等)と出力(売上や利益等)の比 (出力 ÷ 入力) を効率値として評価する。 入力や出力が複数ある場合は、各ガレージが最も有利になるような重みで足し合わせて効率を計算するので、画一的な評価にならず、個性のあるガレージをちゃんと評価に反映できる。人事評価にも応用できるのでは?という意見も出たが、突拍子もない施策をおこなうことで、すきなだけ効率値を挙げられてしまうという問題もあり、なかなか一筋縄ではいかなさそう。

あとは、入力や出力をどのように選択するのか、という問題もある。EDAでは、最も効率のよい店舗の効率値が1となるような正規化をしているが、入出力の数が多いと、自由度が高すぎて、ほとんどの店舗の効率値が1なんて状況にもなりかねない。また、ある出力と関係のない指標を入力にいれてしまうと、なにを見ているのかわからなくなってしまう。このあたりの議論をしていたときに、産業連関表 というキーワードがでてきた(全く理解していない)。産業連関表の用途や使い方については こちらのOR学会の記事 が参考になるみたいなので、あとで読んでみる。

自分の答案は以下のとおり colab.research.google.com

Chapter 3

3.1 The importance of linearity

例えばマルチプラント(工場が複数あって、全体の利益や売上を最大化するような問題)だと、各プラント内での最適化と、プラント間での最適化の両方を同時に解く必要がある。こういった問題を定式化すると、各プラント内で閉じている部分と、プラント間にまたがる部分(例えば物品のやり取りや割当に関する制約)が出てくる。問題にこういった構造が入っていると、解きやすくなることがある(具体的な話は 4.2 以降)。

ちなみにこの本では、制約がブロック対角な部分と共通のだけで構成される構造をブロック対角構造、ブロック対角ではないが多期間問題で今月と次月だけがかぶっているような構造を階段構造(実際にはブロック対角構造に書き直せる)と読んでいる。ブロック対角な部分と共通のだけで構成される構造も紹介されていたが、呼び名を与えられていなかったのでかわいそうだった。

今回は自分が発表担当したので、当日の発表資料 も合わせてご覧ください。