はじめに

　最近、大学の授業で線形計画法という便利なものがあることを学んだので生協の学食で何を食べるのが最適か調べてみることにしました。

　なおこの記事ではJupyter NotebookでPython3を動かしています。

　また、下の記事を参考に書いているので当然下の記事の方が分かりやすいと思います。

[完全栄養マクドナルド食の線型計画による実装～もしマクドナルドだけで生活すると栄養バランスはどうなるのか？～][link-1]
[link-1]:https://qiita.com/youwht/items/9098d560f28d16aa5567

線形計画法とは

　"1次不等式および1次等式を満たす変数の値の中で、ある1次式を最大化または最小化する値を求める方法"です。(Wikipediaより引用)

　今回は三群点数法と呼ばれる、赤・緑・黄の点数を満たすこと、タンパク質を取ることのほかに、脂質、糖質、塩分を取りすぎないようにしながら一番安く食べる方法について考えます。

PuLPをインストール

　Pythonで線形計画法を行うにはPuLPライブラリを使うと便利らしいのでインストールします。コマンドプロンプトで pip install -U pulp と入れることでインストール出来ます。

コードを書く

まずはインストールしたPuLPをimportします。

import pulp
# ライブラリの読み込み

　次に線形計画法で解く問題を定義します。線形計画法ではある目的関数に対してその値を大きくする、もしくは小さくすることを目的とするのでそのようにコードを書きます。今回は金額を最小にすることが目的なのでMinimizeの方を選択しました。
　最大化をするときは下にコメントアウトしてあるMaxmizeの方を使用すればいいです。

# 問題を定義
# 最小化もしくは最大化を選択する
problem = pulp.LpProblem(name = "学食",sense=pulp.LpMinimize)
# problem = pulp.LpProblem(name = "学食",sense=pulp.LpMaximize)

　次に、学食で提供されているメニューをすべて打ち込みます。この作業は本当に不毛です。生協の学食のホームページを見てもどこかの大学で提供されているメニューまで書かれているため、自分の大学で提供されているメニューのみを絞り込めません。また、ホームページに載っていないメニューもあるため、すべて打ち込みました。実際はホームページからデータを取ってきたりした方が楽だと思います。

# メニュー名,カロリー[kCal],タンパク質[g],脂質[g],炭水化物[g],塩分[g],赤[点],緑[点],黄[点],金額[円]

menu = [["牛丼",698,23.8,15.2,108.0,2.8,2.6,0.3,5.9,418],
        ["辛みそ豚丼大",957,39.0,22.3,138.9,2.5,3.9,0.3,7.9,506],
        ["辛みそ豚丼中",720,28.5,16.0,107.1,1.8,2.8,0.2,6.1,418],
        ["辛みそ豚丼小",513,20.1,11.2,76.8,1.3,1.9,0.1,4.4,352],
        ["ガリたま唐揚げ丼",866,30.3,23.4,124.5,3.0,3.1,0.0,6.9,506],
        ["横国パワー丼",899,38.9,32.3,101.0,2.1,4.6,0.1,6.5,482],
        ["鶏照り丼小",440,16.9,4.3,78.1,1.5,1.0,0.1,4.3,385],
        ["鶏照り丼中",615,23.9,6.2,108.6,2.2,1.5,0.2,5.9,451],
        ["鶏照り丼大",810,32.6,8.7,141.0,3.1,2.0,0.3,7.7,539],
        ["鮭丼",553,18.5,7.1,97.8,2.6,1.4,0.0,5.5,506],
        ["チキンおろしダレ",268,23.4,15.5,6.0,1.1,2.7,0.1,0.2,308],
        ["チキン塩ダレ",294,23.2,18.3,6.4,1.7,2.7,0.1,0.6,308],
        ["白身魚フライタルタルソース",433,11.6,28.4,29.8,1.9,0.5,0.1,4.8,264],
        ["和風おろしハンバーグ",307,16.6,19.6,17.4,3.0,1.3,0.4,2.2,308],
        ["ササミチーズカツ",278,14.7,16.9,16.7,0.8,1.1,0.1,2.3,308],
        ["イエローチキンカレー",784,22.0,16.0,131.3,6.0,1.5,0.4,6.9,490],
        ["ヒレカツカレー小",560,13.1,15.4,89.1,4.0,0.2,0.2,6.3,374],
        ["ヒレカツカレー中",819,20.5,24.3,124.5,4.8,0.5,0.2,9.2,440],
        ["ヒレカツカレー大",1098,28.4,34.3,162.2,6.0,0.7,0.3,12.3,528],
        ["7種の野菜カレー",587,14.6,6.3,111.7,2.2,0.4,0.4,6.5,440],
        ["スパイシーポテト",160,2.0,6.2,23.0,1.0,0.0,0.9,0.9,110],
        ["春巻き",329,3.7,27.7,15.3,0.8,0.1,0.0,3.9,88],
        ["厚切りハムカツ",257,7.8,15.8,19.7,1.6,0.4,0.0,2.8,132],
        ["サバ塩焼き",319,16.9,26.3,0.4,2.3,2.7,0.0,0.0,198],
        ["バンバンジー豆腐",133,11.0,7.7,7.6,1.1,0.9,0.1,0.6,132],
        ["揚げだし豆腐",183,6.3,10.0,17.5,0.8,0.9,0.1,1.4,110],
        ["豚汁",72,4.3,2.6,7.2,1.4,0.4,0.3,0.2,88],
        ["豆腐とわかめの味噌汁",24,1.3,0.5,3.2,1.7,0.0,0.0,0.3,33],
        ["ライス小",221,3.9,0.0,48.1,0.0,0.0,0.0,2.8,66],
        ["ライス中",340,6.0,0.0,74.0,0.0,0.0,0.0,4.3,99],
        ["ライス大",459,8.1,0.0,99.9,0.0,0.0,0.0,5.7,132],
        ["きんぴらごぼう",40,0.8,0.8,7.6,0.8,0.0,0.3,0.3,66],
        ["半熟卵",83,6.8,5.7,0.2,0.2,1.0,0.0,0.0,66],
        ["ひじき煮",52,1.6,1.6,7.2,0.8,0.2,0.2,0.1,66],
        ["薩摩ハーブ鶏のレバー煮",81,9.4,1.3,8.1,1.3,0.6,0.0,0.4,88],
        ["ポテト&コーンサラダ",74,1.6,3.8,9.3,0.6,0.0,0.7,0.3,88],
        ["ほうれん草ひじき和え",50,4.0,1.5,4.5,0.5,0.4,0.1,0.1,88],
        ["オクラのお浸し",18,1.2,0.0,4.6,0.3,0.0,0.2,0.0,66],
        ["ほうれん草ゴマ和え",28,2.1,1.0,3.3,0.5,0.0,0.1,0.2,66],
        ["冷奴",53,5.3,3.5,2.0,0.0,0.7,0.0,0.0,66]]

全部載せるのは面倒なので麺類だけカットしました。

target_menu_list,kcal,tampaku,shishitsu =[],[],[],[]
tansui,salt,red,green,yellow,price = [],[],[],[],[],[]
eiyou_data = dict()
for row in menu:
    target_menu_list.append(row[0])
    kcal.append(row[1])
    tampaku.append(row[2])
    shishitsu.append(row[3])
    tansui.append(row[4])
    salt.append(row[5])
    red.append(row[6])
    green.append(row[7])
    yellow.append(row[8])
    price.append(row[9])
for row in menu:
    eiyou_data[row[0]] = row[1:]

　それぞれのメニューを要素ごとのリストにします。本来であれば、インターネットからデータを引っ張ってきて、そのままこのリストにぶち込めばいいだけです。
　さらに、変数の定義を書きます。リスト内包表記で書いていますが、それぞれのメニュー名の変数に対して一度に定義を行っているだけです。(かっこ)内の引数は1つ目のx(内包表記で書いているため実際はメニュー名)が変数(必須項目)、2つ目のcatは変数の種類で入力しないと連続した値を取れます。今回は0.5個などと頼めないため、整数と定義しています。
　3つ目と4つ目のlowBoundとupBoundは最大値と最小値です。入力しなければ負の無限大から正の無限大まで取ります。今回は非負整数なので最小値は0です。最大値は書いておきたかったので適当に大きな数を入れています。

# 変数の定義
xs = [pulp.LpVariable(x, cat='Integer', lowBound=0, upBound = 10**9) for x in target_menu_list]

　次に今回の目的関数を書きます。今回は値段を最小にすることが目的なのでpriceと入力して先に書いたpriceのところを読んでくれているはずです。

# 目的関数（最小or最大にすべき関数）(値段)
problem += pulp.lpDot(price, xs)

　最後に制約条件を書きます。今回の制約条件は三群点数表における一食分を超えること、タンパク質を取ること、脂質、糖質、塩分を取りすぎないようにすることです。黄色の食べ物を取りながら炭水化物を取りすぎないという制約は自分でもよく分かりませんが、まぁいいです。

# 制約条件の定義　(赤・緑・黄・食塩)
# 書き方として、必ず、等号を入れて、<=.==,>= などの書き方にすること！
# 赤
problem += pulp.lpDot(red, xs) >= 8/3
# 緑
problem += pulp.lpDot(green, xs) >= 1 
# 黄
problem += pulp.lpDot(yellow, xs) >= 10.5/3
# 食塩
problem += pulp.lpDot(salt, xs) <= 7.5/3
# タンパク質
problem += pulp.lpDot(tampaku, xs) >= 60/3
# 脂質
problem += pulp.lpDot(shishitsu, xs) <= 50/3
# 炭水化物
problem += pulp.lpDot(tansui, xs) <= 120

　三群点数は以下のページを参考にしました。他の値は体重や総カロリー量によって変わるのでおおよその値です。

制約を書けたら問題を解いてもらいます。この時に問題が解けていた(最適解が得られていた)らOptimalと出力されます。

status = problem.solve()
print(pulp.LpStatus[status])
# {-3: 'Undefined',
#  -2: 'Unbounded',
#  -1: 'Infeasible',
#  0: 'Not Solved',
#  1: 'Optimal'}

あとは結果を出力するだけです。うまく書けないので長くなっています...

# カロリー[kCal],タンパク質[g],脂質[g],炭水化物[g],塩分[g],赤[点],緑[点],黄[点]
cal,tam,shi,tan,nacl,aka,midori,kiiro,nedan = 0,0,0,0,0,0,0,0,0
for i in range(len(menu)):
    k = menu[i][0]
    x = xs[i]
    cal += eiyou_data[k][0]*x.value()
    tam += eiyou_data[k][1]*x.value()
    shi += eiyou_data[k][2]*x.value()
    tan += eiyou_data[k][3]*x.value()
    nacl += eiyou_data[k][4]*x.value()
    aka += eiyou_data[k][5]*x.value()
    midori += eiyou_data[k][6]*x.value()
    kiiro += eiyou_data[k][7]*x.value()
    nedan += eiyou_data[k][8]*x.value()
print("Result")
for x in xs:
    if x.value() != 0:
        print(str(x) + " × "+ str(int(x.value())))
print("エネルギー"+str("{:.1f}".format(cal))+" kcal")
print("タンパク質 "+str("{:.1f}".format(tam))+" g")
print("脂質 "+str("{:.1f}".format(shi))+" g")
print("炭水化物 "+str("{:.1f}".format(tan))+" g")
print("食塩 "+str("{:.1f}".format(nacl))+" g")
print("赤 "+str("{:.1f}".format(aka))+" 点")
print("緑 "+str("{:.1f}".format(midori))+" 点")
print("黄 "+str("{:.1f}".format(kiiro))+" 点")
print("値段 "+str("{:.0f}".format(nedan))+" 円")

結果

結果は以下のようになりました。

Result
ライス小 × 1
薩摩ハーブ鶏のレバー煮 × 1
ポテト&コーンサラダ × 1
オクラのお浸し × 2
冷奴 × 3
エネルギー571.0 kcal
タンパク質 33.2 g
脂質 15.6 g
炭水化物 80.7 g
食塩 2.5 g
赤 2.7 点
緑 1.1 点
黄 3.5 点
値段 572 円

　この制約では同じものを3つも頼んでしまうことがあるようです。変数で定義したupBoundの値を1にすることで複数個の注文を出来ないようにすることが出来ます。
　しかし、この制約だと、これ以外の解は得られませんでした。(ステータスがInfeasibleと出力されました)
　そのため、一番きつそうな制約である塩分を一食当たり3.0gまで許容します(日本人は塩分の取り過ぎと言われています)

すると結果は

Result
ライス小 × 1
半熟卵 × 1
薩摩ハーブ鶏のレバー煮 × 1
ポテト&コーンサラダ × 1
ほうれん草ひじき和え × 1
オクラのお浸し × 1
冷奴 × 1

エネルギー580.0 kcal
タンパク質 32.2 g
脂質 15.8 g
炭水化物 76.8 g
食塩 2.9 g
赤 2.7 点
緑 1.0 点
黄 3.6 点
値段 528 円

となりました。

おいしい

オクラのお浸し、食べてから写真を取ることに気づいてしまった...