LoginSignup
20

More than 5 years have passed since last update.

献立を組合せ最適化で考える

Last updated at Posted at 2016-01-04

問題

医者から1週間の食事のカロリー制限をしなさいと言われました。
また、必要な栄養素A、栄養素Bの最低取得量も指示されました。
なるべく、好きなものを食べるにはどうしたらいいでしょうか?

定式化

組合せ最適化問題の中の割当問題になります。
料理の候補は与えられているものとし、その中からどれを選ぶかを0-1変数$x$で表すことにしましょう。

変数 $x_i \in \{0, 1\}$ $i$番目の料理を選ぶかどうか
目的関数 $\sum_i{好み_i x_i}$ $\rightarrow$ 最大
制約条件 $\sum_i{x_i} = 7 $ 7日分を選ぶ
$\sum_i{カロリー_i x_i} \le 90 $ カロリー制限
$\sum_i{栄養素A_i x_i} \ge 95 $ 最低取得量
$\sum_i{栄養素B_i x_i} \ge 95 $ 最低取得量

pythonで解いてみる

最適化ライブラリは、pulpを使います。
まず、ダミーデータを作成してみましょう。

python
import numpy as np, pandas as pd
from pulp import *
menu = ['牛丼', '親子丼', 'カツ丼', '鉄火丼', 'ねぎとろ丼', 'ちらし寿司',
        '麻婆茄子', 'ドリア', 'オムライス', 'チャーハン', 'カレーライス']
n = len(menu)
np.random.seed(1)
a = pd.DataFrame({
        '料理名': menu,
        'カロリー': np.random.randint(10,20,n),
        '栄養素A': np.random.randint(10,20,n),
        '栄養素B': np.random.randint(10,20,n),
        '好み': np.random.randint(10,20,n),
    })
print(a)
料理名 好み カロリー 栄養素A 栄養素B
0 牛丼 18 15 14 10
1 親子丼 13 18 15 16
2 カツ丼 19 19 12 19
3 鉄火丼 18 15 14 19
4 ねぎとろ丼 17 10 12 17
5 ちらし寿司 13 10 14 16
6 麻婆茄子 16 11 17 19
7 ドリア 15 17 17 11
8 オムライス 11 16 19 10
9 チャーハン 19 19 11 11
10 カレーライス 13 12 17 18

解いてみましょう。

python
m = LpProblem(sense=LpMaximize) # 最大化問題
a['x'] = [LpVariable('x%d'%i, cat=LpBinary) for i in range(n)] # 選択する/しない
m += lpDot(a.好み, a.x) # 好みを最大化
m += lpSum(a.x) == 7 # 1週間分の献立
m += lpDot(a.カロリー, a.x) <= 90
m += lpDot(a.栄養素A, a.x) >= 95
m += lpDot(a.栄養素B, a.x) >= 95
m.solve()
if m.status == 1: # Optimal
    a['val'] = a.x.apply(lambda v: value(v)) # 結果
    print(a[a.val == 1].料理名)
>>>
0         牛丼
3        鉄火丼
4      ねぎとろ丼
5      ちらし寿司
6       麻婆茄子
7        ドリア
10    カレーライス

Docker

Dockerでちょっと試してみたい場合、下記を実行してブラウザでホストを開くと、Jupyterが起動します。ライブラリもいろいろインストールしています。

docker run -d -p 80:8888 tsutomu7/jupyter

以上

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
20