「習うより慣れろ」表計算で始める数理最適化:「生産計画」の例題 (1)

「数理最適化は表に始まり表に終わる」というのは私が勝手に作った言葉ですが、 我々が普通に Excel などを使って作る集計表を数理最適化にかけると、集計結果が意図した感じになるよう都合良く数字を書き込んでくれたりします。ここから始まるちょっとしたシリーズでは表計算から最短コースで数理最適化の本質(の端っこ)に迫ってみます。

製品を2つ作れるとして、それぞれは 3つの原料を決まった量だけ使います。各製品を単位あたり作ったときの利益と原料の在庫の表が次のように与えられています。製品は A,B 、原料は p,q,r としています。

製品 A を 1 単位作ると原料 p,q,r をそれぞれ 4,8,1 消費して、利益が 1 出ます(表を横に見る)。 製品 B も 1 単位生産で利益 1 を得ますが、所要する原料は微妙に異なっています。原料在庫も表に加えておきました。

さて、この表をちょっと拡張して製品の生産によって消費される原料の量や利益の欄を加えます。Excel の数式や関数を使って、オレンジのセルに値が入力されたら緑のセルに数字が出るようにしてみましょう。

足し算と掛け算でもよいですし、"SUMPRODUCT" なら、なお簡単。 「生産量」を示すオレンジのセルについては絶対参照をうまく使うと簡単ですね。。 とかいうのはこの Web 上に溢れる Excel 関連の情報源を辿って頂くとしましょう。

できました。次は A,B の生産量の欄に 5,6 と適当に入れた場合の表の値です。 在庫はまだ余裕で利益は 11。

「生産量」のセルをあれこれ触ると利益とか在庫残りがリアルタイムに変化します。 A の生産量を 7 にすると。。

利益がちょっと増えましたね。もっと増やすにはどうしましょう。 原料在庫が許す限り生産すればよいのです。 まだ余裕ありそうですので、思い切って 30 ずつ作ると、

あれあれ在庫をショートしてしまいました。これでは使えません。もうすこし減らして良いところを探りましょう。。

数理最適化を実感する上でこんなに良いツールはない、と良く思います。 これはただの Excel 演習で全然数理最適化じゃないだろうって？ 確かに。でも我々が数理最適化にやらせているのはこの「生産量」セルの値についての試行錯誤の肩代りであり、Excel をはじめとする表計算は数理最適化ソルバーの操作を実演し、実感する格好のツールなのです。

さてここからは数理最適化ソフトが必要で、各ソフト固有のやり方を覚える必要がありますが、 数理最適化ソルバーに、何をすべきかという「ゲームのルール」(数理モデル)を教えるのは、このExcel 上で SUMPRODUCT とか使って数式を定義する操作とやっていることは本質的に変わりません。数理最適化ソルバーに、変数は「生産量」のセルの値であるということ、「生産量」セルの値を使って在庫残りは 0 以上でなくてはならないという制約を定義し、利益を最大化したいのだ、と教え込むことができたとしましょう。解かせてみます。 数理最適化ソルバーの答が返したのは 製品A,B をそれぞれ 28,40 作る利益 52 の計画でした。

ご存知の方も多いと思いますが、じつはこの例、 数理最適化の教科書の「導入」の定番なのです(ふと思い立って私の周りにある本、和洋とりまぜて 11冊を調べてみたら、じつに 8 冊がこの例題に類するものを導入に使っていました)。 ただ A,B = 28,40 という、一つの結果から得られる情報には限りがありますから、 教科書の書かれた頃よりもおそらくは恵まれた計算機環境を手にしている、というアドバンテージを活かし、数字をいろいろ替えて試しながら数理最適化というやつのお手並みを体感してみましょう。 ぱっと見わかるのは q,r の在庫を使い切る答になっているということ（表で使い切られた原料は色付けしています）。原料がすべて余っているならば製品にしてしまえばよいわけで、これは確かに妥当な動作である感じがします。では原料 r の在庫を 105 に増やしてみましょう。

増やした r をまた使い切って 1 利益が増えました。 では思い切って r の在庫を 120 にしてみます。

あんまり素直に利益は増えません。r を使い切ることができてません。 原料 p,q の在庫が使い切られているところを見ると、今度は p,q が頭打ちになっているのだなとわかります。 原料 q の在庫を増やしてみましょう。

無事 q の在庫を使い切って利益を増やす答になっています。 こうやって試していると、(求めたかったはず)の生産量の値より、 どの在庫を使い切っているかというところから結果を理解する方が容易なことがわかります。 実は、数理最適化の教える知見の一つに、

  丁度満たされている制約(使い切っている在庫)によって答が決まる。

という事実があります。特に数理最適化が求めようとしている量の一次の式(定数倍の和)によって問題が表現されている線形計画法の場合、どの製品の在庫が使い切られているか、という情報は答の情報と等価である、とすら言えてしまいます。もちろんどの製品の在庫が使い切られているかを知るために目的関数を参照しているのですが、出てくる結果を陽に支配するのは制約式の方で、だから目的関数のウエイトをいじっても結果が付いてこない・・といったことが起きます。

教科書だと、次のような感じのグラフが出てきて

結果を「解析的に」(要するに筆算)で求め、 どうして最適と言えるのか説明したり、一般的な解き方を解説したり、さらには「双対変数」とかいうじつに不可思議な量の説明に入ってしまうのですが、じつは、こういう知識はツールとして実務的に数理最適化ソルバーを使い出す上では不要。 Excel 上に問題を表現した段階で、数理最適化を始める準備(数理モデル化)はもうできています。 「習うより慣れろ」でどんどん動かすことで、知見を得てゆきましょう。そうする中で教科書を読んだだけではわからない事実も見えてきます。

次回はこの生産計画のモデルをもうすこし触って、数理最適化の性質に迫ってみます。