給食 最適化 PuLP

給食 最適化

給食に関する最適化問題の例として、以下の問題を考えてみます。

ある学校では、毎日ランチとしてA,B,Cの3種類のメニューから1つを提供します。

各メニューには以下のような栄養素が含まれます。

栄養素メニューAメニューBメニューC
カロリー700 kcal600 kcal800 kcal
タンパク質30 g25 g20 g
脂質10 g15 g20 g
炭水化物50 g40 g60 g

また、各クラスには生徒が20名ずつ在籍しており、1日に必要な栄養素の量は以下の通りとします。

栄養素必要量
カロリー10000 kcal
タンパク質500 g
脂質200 g
炭水化物700 g

このとき、1日の給食で提供する各メニューの量を決定し、必要な栄養素を満たすことができる最小のコストを求める最適化問題を考えます。

解法

下記のコードでは、変数a,b,cをそれぞれメニューA,B,Cの提供量とし、目的関数 2a + 3b + 4c を最小化するように設定しています。

制約条件は、各栄養素の必要量を満たすように設定しています。

最後に、PuLPのsolve()メソッドを呼び出して最適化問題を解き、結果を出力しています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import pulp

# 問題の定義
problem = pulp.LpProblem('school_lunch', pulp.LpMinimize)

# 変数の定義
a = pulp.LpVariable('a', lowBound=0, cat='Continuous')
b = pulp.LpVariable('b', lowBound=0, cat='Continuous')
c = pulp.LpVariable('c', lowBound=0, cat='Continuous')

# 目的関数の定義
problem += 2 * a + 3 * b + 4 * c

# 制約条件の定義
problem += 700 * a + 600 * b + 800 * c >= 10000
problem += 30 * a + 25 * b + 20 * c >= 500
problem += 10 * a + 15 * b + 20 * c >= 200
problem += 50 * a + 40 * b + 60 * c >= 700

# 問題の解法
status = problem.solve()

# 解の出力
print('Result:')
print(f'a: {pulp.value(a)}')
print(f'b: {pulp.value(b)}')
print(f'c: {pulp.value(c)}')
print(f'Minimum Cost: {pulp.value(problem.objective)}')

実際に上記のコードを実行すると、以下のような結果が得られます。

[実行結果]
Result:
a: 15.0
b: 0.0
c: 2.5
Minimum Cost: 40.0

この結果から、メニューAを15人分、メニューBを0人分、メニューCを2.5人分提供することで、必要な栄養素を満たすことができ、最小のコストは40であることがわかります。