「重ね合わせ」タイプのモデル 基本:まんじゅう問題

欲しいものを「それだけ」手に入れるというのは難しいのが普通です。 「この皿だけ」食べたいと思っても定食を頼まなければならないとか、欲しいのは 2,3 曲なのに結局アルバム 2 枚も買う羽目になってしまったとか。とかくままならないのがこの世の中。 そんな「セット販売」しかない状況でも、賢く組みあわせて欲しいものを効率良く手に入れよう。 そういった意図が現れるところに「重ね合わせ」パターンはまず現れます。

一つ典型的な例を挙げましょう。 お客さんが来るので、まんじゅう、もなか、せんべいをそれぞれ 20個/枚 揃えたい。 買い物に行ったお菓子屋さんではこれらが詰め合わせセットになった袋 A,B,C を売っていました。 袋の中身は A にはまんじゅう2個、もなか3個、せんべい5枚、 B にはまんじゅう5個とせんべい2枚、 C にはもなかだけ4つ、 それぞれ入っています。 定価は 500円。B だけはタイムサービスで 500円のところ破格の 100円。 さて、どうやって買い物すればよいでしょう？

上が対応する数理最適化モデルを絵で表現してみたものです (コストを最小に、というのは明らかなので省いてます)。 数理最適化の教科書に出てくるような数式ではないですが、これもモデルの記述の一つ。 数式は数理最適化モデルを表現する便利な道具ですが、 「数理最適化モデルすなわち数式」ではなく、 ユーザーとソルバーが意思疎通する上でベストの手段とは限らないと私は考えています。 このケースではこの絵を例えば Excel とかを使ってインタラクティブに変化するように表すと 制約を体感できます。

最適な答を考えてみましょう。 まずは袋 B の安売りが気になりますね。 なにせ 100円です。10袋買ってまんじゅうとせんべいのニーズを満たして(それでも 1000円)、 もなかを袋 C で調達して、合計 3500円。 ただ、まんじゅう 50 個はちょっと買いすぎですからちょっと無駄が多い気がする。

数理最適化アルゴリズムの回答は、「すべて 3 袋ずつ買って 3300 円」でした。 なるほど。すべて 21 個/枚ずつ、というなかなか無駄のない答です。 まあ人間はもっと賢いので、「せんべい 20枚」という必要量の方を改変し、 8枚で済ませるようにして 2900円(袋B 4 つ、袋C5つ)で済ませてお金を浮かせそうです。 ちょっとモデルをいじってこういう判断をさせるにはどうするかという話もまた面白いのですが、 それは枝葉の話として「重ね合わせ」のモデルパターンの話に戻りましょう。

このモデルのように、「セット販売」のパターンそれぞれの購入量が決定すべき変数になっていて、 パターンを重ね合わせて意図を実現する、という数理最適化モデルの構造を、 私は「重ね合わせ」と称しています。一般化してみたのがこういう絵です。

広い意味での「セット販売」的な状況としてこういうのがあります。 例えば食べ物には栄養素が複数、含まれていますね。 所望の栄養素を所定の量だけ安く摂る、あるいは摂りすぎないようにするにはいろんな食べ物をどういう配分で 食べればよいでしょうか？これは「ダイエット問題」と名前が付いている古典的な例題です。 「摂りすぎない」という上から抑える制約がありますが、構造は「まんじゅう問題」と全く同じです。 他にも天然の「セット販売」と言えば、 重油とか軽油とか様々な成分を含む「原油」がそうで(産地によって値段と含まれる成分が違う)、 古くから石油会社の意思決定に数理最適化が使われてきた理由になっています。 人工的な話だと、時間割が与えられたとして所定の単位数を揃えるためには最低何日学校に行けばよいか、 とか(「曜日」がセット販売のパターン、各日に行われる授業に付属する単位が成分)、 有料 TV の契約をどういう風にすれば、見たい番組がもれなく見られるか、 といった想定が考えられます。

よく数理計画法の教科書の最初に 「部品が3つしかない2種類の製品を生産する計画」とか 「成分が2つの3種類の薬品を混合する計画」とかいう例題が現れるのも同じ流れで、 導入としてこの重ね合わせパターンの例題を採用しているためです。 ただ、ここまで来るとちょっと実務的なケースから程遠く、 逆にこのパターン、本当に役に立つのかすこし不安になってきます。 「原油」は自然が与えてくれた福音とも言うべきすばらしい例題ですが、 「まんじゅう問題」的なわざとらしい状況に出会うことはまずないし、 値段と栄養素だけで食べ物を選ぶのも何です(やってみると卵だけ食べる結果になるらしい、なるほど)。 単位を取るためだけに学校に行くのではないし、 昨今は欲しい番組だけオンライン配信してもらえる。 「セット販売」のうまい重ね合わせができて本当に嬉しいのか？

どうかご安心を。実はこの「セット販売重ね合わせ」の考え方がうまく使えて、 実務的に役に立つケースが多数あるのです。 コツはモデルの設定に「時間」や「経路」という要素を入れること。詳しくは次回以降に。