Excelでソルバーを使って整数計画問題（献立問題）を解く

みなさん，こんにちは。
シンノユウキ（shinno1993）です。

Excelを用いて最適化問題を解く方法を解説する連載の３回目。前回はExcelのソルバー機能を使って線形計画問題を解く方法を紹介しました。

今回は変数の値が整数である整数最適化問題を献立作成を題材として解いてみたいと思います。

では行きましょう！

前回やったこと

前回の記事では，Excelのソルバー機能を使って線形計画問題を解いてみました。３つの食品をどれだけ摂取すると，栄養素摂取量を満たしながら価格を最小化できるのか？についての問題でした。

この場合，食品の摂取量は0.1g単位で変化しても問題ないので，比較的簡単に最適な値を見つけることができました。

しかし，たとえば料理を組み合わせて献立を作成する場合，料理は提供する皿単位で考える必要があります（大盛り・小盛りはないとする）。そういった場合，変数は整数にならなければなりません。それを解決するのが整数計画問題です。

整数計画問題は，最適化問題のうち，変数の一部もしくは全てが整数であるという制約を受ける問題のことです。多くの場合，線形計画問題に含まれます。

また今回題材としている献立問題のような，変数が整数としかなりえない場合でも活用することができます。また，以下で扱う献立問題は，同じ料理を複数回使うことができますが，たとえば使う/使わないの２値に限定することで，数ある料理の中からベストな組み合わせを探索することもできます。

それ以外に活用しようとする場合，たとえば，Yse/Noのような２値しかとらないような要素をモデルに取り込むことができるので，意思決定の際などにも用いやすくなります。

では以下で実際に問題を解いていきましょう。

複数の料理を組み合わせて，栄養素摂取量の制約条件を満たす組み合わせを探します。その際，エネルギー摂取量を2,000kcal以上で最小化するように設定します。

料理の栄養素摂取量および制約条件は以下です：

料理名	エネルギー（kcal）	たんぱく質（g）	脂質（g）	炭水化物（g）	食物繊維（g）	食塩相当量（g）
ご飯	252.0	3.8	0.5	55.7	0.5	0.0
おにぎり（うめ）	160.5	2.9	0.4	35.4	0.9	0.3
釜あげうどん	342.1	7.5	0.6	67.1	1.4	2.0
トースト（バター）	232.9	5.4	10.8	28.0	1.4	0.8
親子丼	483.9	20.7	8.1	76.2	1.4	2.5
きのこのみそ汁	55.4	3.5	2.1	6.8	3.2	1.0
みそ汁（豆腐，わかめ）	37.3	3.2	1.3	3.5	0.7	1.2
きのこの炒め物	42.9	3.1	2.6	5.6	6.7	1.0
野菜サラダ	130.7	4.3	10.7	5.0	1.3	0.4
野菜ソテー	166.3	13.7	6.5	12.1	3.3	1.2
きゅうりの酢の物	73.6	11.7	0.4	5.6	1.0	1.5
きんぴらごぼう	121.9	1.9	5.1	18.0	4.6	1.7
ごぼうのサラダ	102.2	1.4	7.5	7.7	3.2	2.0
ハンバーグ	340.5	15.8	22.0	17.9	1.3	1.2
卵焼き	95.3	6.4	5.7	3.5	0.4	0.6
魚のムニエル	305.1	16.5	19.0	15.1	1.8	0.9
かつおのたたき	101.2	19.3	0.4	4.0	0.5	1.3
豚肉の生姜焼き	197.7	16.4	11.7	3.6	0.4	0.6

制限条件

成分値等を入力したExcelファイルを用意しましたので，こちらをDLして活用してください。

上記からDLできるExcelファイルは，献立問題と成分表の２つのシートがあります：

●シート「献立問題」

ソルバーを実行するシートです。変数セルや制限条件，目的条件が入力されています。

●シート「成分表」

シート「成分表」には，各料理１個あたりの成分値が入力されています。数値は今回の問題を作成するにあたってのサンプルです。

今回のExcelファイルでは，ソルバーのパラメーター等が設定されています。「ソルバー」を実行すると，下記の入力済みのダイアログが表示されるはずです：

目的セル：エネルギー摂取量の入力されているセルを参照しています。今回はエネルギー摂取量を最小にしたいので，目標値には「最小値」を選択します。
変数セル：個数の入力されているセルを選択します。
制約条件：エネルギー摂取量およびPFC比率，食物繊維と食塩相当量を制約条件にしています。また，最下部に$B$3:$B$20 = 整数とありますが，ここで変数を整数にすることを設定しています。下記のように制約条件を追加する際に整数にしたいセルを参照し，「int」を選択してください。

これでソルバーを実行すると，以下の様な結果が得られます：

今回はExcelのソルバーを利用して，整数計画問題を解いてみました。

ソルバーの設定等については，前回のものと殆ど変わりはありません。ただ制約条件に指定したセルの値に整数を加えることが前回までの違いになります。