pythonのPuLPを用いて線形計画問題を解いてみる

就活のネタ作りにwebアプリを作成しようと思い立ったので、PuLPを用いりたいと思います。
作成するアプリは題して「コスパ君」です。

学校の食堂のメニューの一個一個に

「赤色1点、緑色0.3点、黄色３点」

みたいな感じで栄養バランスを点数にして表示しています。
これを組み合わせることにより

「１食の目安、赤2点・緑1点・黄色８点」
と記載されているので、如何に値段を抑えつつこの目標点数を超えることが出来るかを計算するアプリを作りたいと思います。


#導入

まずはPuLPをpipで導入します

```
pip install pulp
```

#コーディング
適当なエディタを使ってコードを書いていきます。


```python:pulp.py

import pulp

prob = pulp.LpProblem('CalcFood', pulp.LpMinimize)
list =[(0.2, 0.1, 0.3, 300), (0.3, 0.1, 0.3, 400), (0.2, 0.4, 0.1, 150), (0.1, 0.4, 0.4, 300), (0.4, 0.3, 0.4, 500)]


x = []
for i in range(len(list)):
    x.append(pulp.LpVariable('x[%s]'%i, 0, 5, 'Integer'))

prob1 = 0
for j in range(len(list)):
    prob1 += (list[j][3] * x[j])  
prob += prob1



prob1 = 0
prob2 = 0
prob3 = 0
for i in range(len(list)):
    prob1 += list[i][0] * x[i]
    prob2 += (list[i][1] * x[i])
    prob3 += (list[i][2] * x[i])
print(prob1)
prob += prob1 >=2.0  # 制約条件　赤
prob += prob2 >=1.0  # 制約条件　緑
prob += prob3 >=3.0  # 制約条件　黄


print(prob)

status = prob.solve()
print(pulp.LpStatus[status])

for i in range(len(x)):
    print("x[", i, "]", pulp.value(x[i]))
```

汚いコードですがそこまで長くないので先に載せておきます。
本来線形計画問題なら変数を定義してごにょごにょ書いていくのですが、食堂のメニューは増えることもあるので、増えるたびに変数増やすのはナンセンスです。
そこで、リストを増やすだけで勝手に変数も増えて、計算してくれるようにしています。


コードの解説行っていきます。

#オブジェクトの作成

```
prob = pulp.LpProblem('CalcFood', pulp.LpMinimize)
```
で線形計画のオブジェクトを作成します。第1引数の'CalcFood'のところは適宜名前を付けて下さい。計算には微塵にも影響ないので自分がわかれば大丈夫です。
第２引数には
pulp.LpMinimize（最小化問題）かpulp.LpMaximize（最大化問題）
を選択します。

#データの準備
次にデータを準備してあげます。
(0.2,　0.1,　0.3,　300)が左から順にメニュー1個の（赤,緑,黄,値段）で表しています。
webアプリ化するときにはデータベースから引っ張ってくるように変更予定です。



#変数の作成

```
x = []
for i in range(len(list)):
    x.append(pulp.LpVariable('x[%s]'%i, 0, 5, 'Integer'))
```

で変数を作成しています。空のリストを準備して、そこにデータの個数分のPuLP型の変数を入れていきます。

```
pulp.LpVariable('x[%s]'%i, 0, 5, 'Integer')
```
ですが、第２引数が変数が取り得る最小値・第３引数が変数が取り得る最大値です。
今回の問題で置き換えると、同じ食べ物を０〜５の範囲の整数で選択できるってことです。
つまり同じ食べ物を５個まで重複して食べるってことになります。
実際に運用するときにはちゃんと変更しておきます、、、笑

#目的関数の作成

```
prob1 = 0
for j in range(len(list)):
    prob1 += (list[j][3] * x[j])  
prob += prob1

```

ここが少し戸惑いました。
わざわざprob1という無駄な変数を準備しています。

最初は


```
for j in range(len(list)):
    prob += (list[j][3] * x[j])  
```
だけにしていたのですが、「Overwriting previously set objective」
とエラーを吐かれた為、prob1を準備しました。本来はprobに+=で追加していけばいいのですが、for文で回すと追加せずにオーバーライドしているみたいなので迂回しました。

誰かここのスマートな書き方教えてください。

#制約条件の作成

```
prob1 = 0
prob2 = 0
prob3 = 0
for i in range(len(list)):
    prob1 += list[i][0] * x[i]
    prob2 += (list[i][1] * x[i])
    prob3 += (list[i][2] * x[i])
print(prob1)
prob += prob1 >=2.0  # 制約条件　赤
prob += prob2 >=1.0  # 制約条件　緑
prob += prob3 >=3.0  # 制約条件　黄
```

この部分です。目的関数と同じく、for文で回しているためprob1,prob2,prob3の変数を準備して迂回しています。

#結果の確認
```
status = prob.solve()
print(pulp.LpStatus[status])

for i in range(len(x)):
    print("x[", i, "]", pulp.value(x[i]))
```
prob.solve()で問題を解きます。
また　print(pulp.LpStatus[status])　で結果の確認（最適解or不実行解）の表示がされます。
実際に解けた場合は　pulp.value(x[i]))　で値を表示してやる必要があります。

#実行結果

```
CalcFood:
MINIMIZE
300*x_0_ + 400*x_1_ + 150*x_2_ + 300*x_3_ + 500*x_4_ + 0
SUBJECT TO
_C1: 0.2 x_0_ + 0.3 x_1_ + 0.2 x_2_ + 0.1 x_3_ + 0.4 x_4_ >= 2

_C2: 0.1 x_0_ + 0.1 x_1_ + 0.4 x_2_ + 0.4 x_3_ + 0.3 x_4_ >= 1

_C3: 0.3 x_0_ + 0.3 x_1_ + 0.1 x_2_ + 0.4 x_3_ + 0.4 x_4_ >= 3

VARIABLES
0 <= x_0_ <= 5 Integer
0 <= x_1_ <= 5 Integer
0 <= x_2_ <= 5 Integer
0 <= x_3_ <= 5 Integer
0 <= x_4_ <= 5 Integer

Optimal
x[ 0 ] 3.0
x[ 1 ] 0.0
x[ 2 ] 5.0
x[ 3 ] 4.0
x[ 4 ] 0.0
```

#まとめ
こんな感じで40行足らずのコードで変数の数が変動する線形計画問題解けちゃいました。pythonのライブラリは偉大です。
あとはこれとdjangoに結びつけてweb上から結果を確認したり、食べ物の要素を追加できるようにしてみたいと思います。

ps.目的関数と制約条件の書き方が適当なのでいい方法あれば教えてください。