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

車両 1 ～ 5 と、それらが巡回する部品工場 A～F の対応は同じで、今度は下の表が示すように毎日、 消耗品を所定のケース数だけ届けねばならない、という状況を考えます。

前回のように「とにかく届ければ(車が行きさえすれば)よい」というわけではなく、 車両にも積載量の上限（それぞれ80ケースとします）があると考えます。 結果のイメージを Excel を使って作ってみましょう。

肌色のセルに値を入れて、タテ計が需要に揃うように、 ヨコ計が車両の積載量の上限 80 を越えないようにすればよいのです。 Excel の式を定義しておけば、セルの値を入れるとタテ計とヨコ計が一瞬で更新されるのはよいのですが、 計画を立てるというのは、結局 ５（車両）× ６（工場） = 30 個のマスに値を「手で」入れてゆくことに他なりません。 値の組み合わせはそれなりに膨大なので、何か指針が要ります。 前回の最適化結果によると、車1と車4 に頼めばとにかく全部回り切れる。 ただ、

のように車１と車４だけで運ぼうとすると、車１の容量オーバー。 確かに需要量合計が 170 ケースで二台分の容量をわずか超えてますので車３台が必要な理屈です。 安易ですが工場C をカバーしてくれている車 3 を使って

という感じで結果を一つ導くことができます。

では、Excel の数式相当の情報を数理モデルとして食べさせて、 数理最適化に集計値になるようなセルの値を「逆算」してもらいましょう。 積載量を守り、需要を満たす範囲で使用する車の台数をできるだけ少なくしなさい、とすると

という答が出ます。 車１、車４ で運ばせることを軸として手で作った答とずいぶん様相が違うのですが、 ちゃんと制約は満たせていて、どうやら 3 台で運ぶ方法は一通りではないらしいとわかります。 最適な方法というのは一つしかないような気がするものですが、実務的の問題で答が沢山あり得る状況はむしろ普通です。 パズルを解くようにしてたった一つの答を探しあてる、というよりも沢山のあり得る答の中から気持的にしっくり来るものを絞り込んでゆく。それこそが実務の現場における数理最適化の醍醐味とも言えます。

まず、各車が実際に運んでいる量を見ましょう。最初に作った車1,3,4 を使う 結果も、数理最適化が出した車1,2,3 を使う結果もどうにもバランスが悪い。 最も運ぶ量が少ない車は最大積載量の半分も運んでいません。 各車の最低積載量が 50 という制約を付けて、最適化に再度探索させてみましょう。

全然違う車両の組みあわせ車５を使って 車両の負担は同じような感じの結果が出ました。 でも、ちょっと待ってください、 工場 A の需要 40 を車1と車5 の二台でまかなうようになってしまっています。 到着が前後したりすると品物を受け入れる工場側の手間は増えます。 一工場に対して担当車両は一つにまとめましょう。 それには、車両の台数の他、肌色のマス目で 0 以外が入っている個数をできる だけ小さくしなさい、という目的関数を加えます。次が出てくる答の一例です。

あれあれ、工場Ａを担当する車両は一台になりましたが、今度は工場B の担当がばらけていて、 結局値が書いてあるマス目の数は変化していません。

最適解がこれだということは、そもそも最低積載量が50 で、 一顧客に一台の車両、という答があり得ない、ということを示しています。 所望の答を得るためには、制約を緩めるしかありません。 50ケースという最低積載量がきつかったようなので、45ケースとしてみると、 無事一つの車両が一つの工場を担当する結果となりました。

実務の世界では、このようにそもそも答が存在するかどうかわからない問題を解くことは普通です。 数理最適化はうまく使うとこのように全体を見通した知識で膨大な試行錯誤からユーザーを開放し、 問題と「対話」するように結果に迫ることができます。