最適化一口話

仕事として数理最適化を実践している立場から、その中身や可能性について概説しております。

「習うより慣れろ」で始める数理最適化:「集合被覆」の例題

車両 1~5 と、部品工場A ~ F との対応を示している表があります。 どんな状況が想定されるでしょうか? f:id:optimizationTanabe:20161109170927p:plain

ここはあるメーカーの本社組み立て工場。 操業には部品工場(A~F)からの部品を仕入れて来る必要があって、 この表は仕入れをしている 5台の車のそれぞれが、 今日、仕入れ先のどこを回ることになっているかを示しています。なぜこの表が必要になったかというと、 急ぎで今日中に各部品工場すべてに届けたいものが生じたのです。仕入れのついでに持っていってもらうことにしようと思いますがどの車に頼めば、すべての部品工場を網羅できる(カバーできるか)か決めたい、とします。 すべての部品工場を網羅している車はないので、複数の車に頼む必要がありますが、できるならば最小限の車に頼むことで済ませたいのです。

この問題は「集合被覆問題」というなかなか使いでのある数理最適化の例題になるので Excel を入口にして、数理最適化という道を辿ってみます。 まず、どの車に頼むかどうかの選択をセルに入力すると、部品工場がカバーできるかがわかる、という表を作りましょう。以下はイメージです。

f:id:optimizationTanabe:20161109171012p:plain

さて、これを例えば Excel で作るにはどうすればよいかです。方法は一つではないですが、○×のままだとしんどい。文字を数字に置き換えて、Excel の数式が使えるようにする案が定番として浮上します。慣れている方ならば、元の表と連動させて、次のような表を新たに作ることは造作もないことかと思います。 具体的には、黄色のセルに、各車両に実際頼むかどうかを 0-1 で入れ、IF 関数を使って、○を 1 で、空白セルを 0 で置き換え(オレンジの部分)、緑のセルには SUMPRODUCT を使って、各工場がカバーされたら 1 以上の値が入るようにしておきます(下図)。

f:id:optimizationTanabe:20171218140300p:plain

黄色のセルを変化させると、緑のセルの値が瞬時に変化するはずです。 ま、実際この程度ならばこの表を見ながら試行錯誤するので十分ですが、せっかくですから数理最適化で「逆算」してみましょう。逆算とはすなわち数理最適化に、黄色のセルに1が入る数(車両に頼む数)を最小限にとどめつつ、緑のセルの値がすべて1以上の値になるようにします。

f:id:optimizationTanabe:20161109171150p:plain

ここからは数理最適化ソフトが必要になります。それぞれ固有のやり方を覚える必要がありますが、黄色のセルを「変数」と定義して、緑のセルに定義されている数式を制約、黄色のセルの和を目的関数として教えます。 数理最適化ソルバーが導いた答は次です。

f:id:optimizationTanabe:20161109171240p:plain

車1と車4に頼めば無駄なく(緑のセルに1が丁度入る)回ることができることがわかります。Excel 技を使って、元の○×の表に結果を書き込んでみましょう。

f:id:optimizationTanabe:20161109171312p:plain

「数式臭さ」が抜けて、普通に人に見せてわかる、イメージした通りの表になっています。途中は○とか×を 1 と 0 に置き換えて途中の計算をわざわざ数字にしていました。これを理屈っぽく言うと「数理モデル化を行った」ということになりますが、これはつまるところ、Excel の数式を使うためで「便利」だからにすぎません。数理最適化でも同じ事情です。数理最適化でむやみやたらと数式に頼った記述は避けるべきと私は思っています。黄色のセルにはあくまで 0 か 1 しか入れることができず、0.4 とかいう値は入れられません(頼む、頼まないの二択なのに、意味が変になりますよね)。こういう変数を離散変数( 0-1 変数 ) と呼び、字義通り 0 とか 1 という意味ではなく、モデルの作り手により '○' とか'×' という意味を付与されています。

前回は「生産量」、という量そのものを変数にしましたが、実際の意思決定の場面では、このように「やる/やらない」とか、「どれを選ぶ」とかを決めることも多く、そこから現れる、離散変数を含む数理最適化問題は数理最適化の一大研究分野となっています。

今回は、「急ぎで各部品工場すべてに届けたい」という、突発的なニーズに対応しましたが、次は同じ表から出発して定常的なニーズに対応したモデルにしてみましょう。