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

みなさん,こんにちは。
シンノユウキ(shinno1993)です。

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

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

では行きましょう!

前回やったこと

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

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

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

整数計画問題とは?

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

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

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

実際にやってみる

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

問題の概要

複数の料理を組み合わせて,栄養素摂取量の制約条件を満たす組み合わせを探します。その際,エネルギー摂取量を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
制限条件
  • エネルギー:2,000kcal以上
  • たんぱく質:13~20%E
  • 脂質:20~30%E
  • 炭水化物:50~65%E
  • 食物繊維:18g以上
  • 食塩相当量:7.5g

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

献立問題サンプル.xlsx

Excelシートの構成

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

シート「献立問題」

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

シート「成分表」

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

ソルバーの実行

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

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

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

まとめ

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

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

連載目次

  1. Excelに「ソルバー」アドインを追加しよう!
  2. Excelでソルバーを使って線形計画問題(栄養問題)を解く
  3. Excelでソルバーを使って整数計画問題(献立問題)を解く現在のページ
  4. Excelでソルバーを使って食事最適化法を試してみる
  5. ExcelのソルバーをVBAで自動化する方法
タイトルとURLをコピーしました