PuLP 演習1 ブレンド問題

* 参考元
    * https://pythonhosted.org/PuLP/CaseStudies/a_blending_problem.html

# 問題の説明

* Whiskas キャットフードというものがある
* これは、アンクル・ベン という人物によって製造されている
* アンクル・ベンは、缶に記載されている規定の栄養分析要件を満たしたい
* 一方で、できるだけ安価でキャットフードを生産したいと考えている
* 栄養基準を満たし、かつ使用されている原料の量を抑えたい

## 原料

* 鶏肉
    * $0.013/g
* 牛肉
    * $0.008/g
* 羊肉
    * $0.010/g
* 米
    * $0.002/g
* 小麦
    * $0.005/g
* ゲル
    * $0.001/g

## 栄養分析要件

* たんぱく質
    * 100gあたり8g以上含む
* 脂肪
    * 100gあたり6g以上含む
* 食物繊維
    * 100gあたり最大2g含む
* 塩
    * 100gあたり最大0.4g含む

## 栄養一覧

||たんぱく質|脂肪|食物繊維|塩|
|---|---|---|---|---|
|鶏肉|0.100g/1g|0.080g/1g|0.001g/1g|0.002g/1g|
|牛肉|0.200g/1g|0.100g/1g|0.005g/1g|0.005g/1g|
|羊肉|0.150g/1g|0.110g/1g|0.003g/1g|0.007g/1g|
|米|0.000g/1g|0.010g/1g|0.100g/1g|0.002g/1g|
|小麦|0.040g/1g|0.010g/1g|0.150g/1g|0.008g/1g|
|ゲル|0.000g/1g|0.000g/1g|0.000g/1g|0.000g/1g|

# 簡易定式化

* 単純なPythonモデルを構築するための単純化された問題について考える

## 決定変数の特定

* まず、鶏肉と牛肉の2つの材料だけでキャットフードを作りたいとする
* 決定変数を定義する

```math
x_1: キャットフードにおける牛肉の割合 \\
x_2: キャットフードにおける鶏肉の割合
```

* これらの変数に対する制限 (ゼロより大きい) に注意する必要があるが、Pythonの実装ではそれらを別々に入力したり、リストにしたり、他の制約とともにリストにしたりすることはしない

## 目的関数の定式化

* 目的関数は次のようになる
    * キャットフードにおける鶏肉と牛肉の合計金額が最低になるようにしたい

```math
min\hspace{5pt}0.013x_1 + 0.008x_2
```

## 制約の定義

* 割合なので、それぞれの変数の合計は100%にならなければならない

```math
x_1 + x_2 = 100
```

* 栄養要件を満たさなければならない

```math
0.100x_1 + 0.200x_2 \geq 8.0 \\
0.080x_1 + 0.100x_2 \geq 6.0 \\
0.001x_1 + 0.005x_2 \leq 2.0 \\
0.002x_1 + 0.005x_2 \leq 0.4
```

## 単純化された問題の解決

* ファイルの最初の部分には、プログラムの目的の概要を説明した短いコメント欄がある

```python:main.py
"""
PuLPモデラー用の簡略化されたWhiskasモデルPythonの定式化

Authors: michi_h 2019
"""
```

* PuLP関数をインポートする

```python:main.py
# PuLP モデラー関数のインポート
from pulp import *
```

* 問題データを作成する
    * prob という変数を LpProblem というクラスを使用して作成する
    * 2つパラメータがある
        * 問題の任意の名前
        * 解決しようとしているLP (Linear Programming) の種類 (LpMinimize (最小化), LpMaximize (最大化) のいずれか)

```python:main.py
# 問題データ作成
prob = LpProblem("The Whiskas Problem", LpMinimize)
```

* 問題変数を作成する
    * x1、x2という変数を、LpVariable というクラスを使用して作成する
    * 4つのパラメータを持つ
        * 変数が表すものの任意の名前
        * 変数の下限 (デフォルトはNone (負の無限大))
        * 変数の上限 (デフォルトはNone (正の無限大))
        * 本質的なデータのタイプ (離散 (LpInteger)、または連続 (LpContinuous) 、LpContinuous がデフォルト)

```python:main.py
# 下限を0とする鶏肉と牛肉の変数を作成する
x1 = LpVariable("ChickenPercent", 0)
x2 = LpVariable("BeefPercent", 0)
```

* 目的関数を設定する
    * 目的関数は最初に論理的に入力され、カンマに続いて目的関数が何であるかを説明する文字列が続く

```python:main.py
# 目的関数がprob に最初に追加される
prob += 0.013 * x1 + 0.008 * x2, "1缶あたりの材料のコスト"
```

* 制約を設定する
    * 制約式の最後に、カンマに続いて制約の簡単な説明を入力して、制約を論理的に入力する

```python:main.py
# 5つの制約を入力
prob += x1 + x2 == 100, "割合合計"
prob += 0.100 * x1 + 0.200 * x2 >= 8.0, "たんぱく質の条件"
prob += 0.080 * x1 + 0.100 * x2 >= 6.0, "脂質の条件"
prob += 0.001 * x1 + 0.005 * x2 <= 2.0, "食物繊維の条件"
prob += 0.002 * x1 + 0.005 * x2 <= 0.4, "塩の条件"
```

* 情報を書き出す
    * 全ての問題データが入力されたので、writeLP() 関数を使用して、情報をコードブロックの実行元ディレクトリの.lp ファイルにコピーできる
    * コードが正常に実行されたら、この.lp ファイルをテキストエディタで開いて、今までの手順が何をしているのかを確認できる

```python:main.py
# 問題データを.lp ファイルに書き出す
prob.writeLP("WhiskasModel.lp")
```

* 問題を解く
    * LPは、PuLPの選択したソルバーを使用して解かれる

```python:main.py
# PuLPの選択したソルバーが使用され、問題が解かれる
prob.solve()
```

* 結果を出力する (ステータス)
    * prob.status の値は整数値で返却される
    * これを、辞書を使用して意味のあるテキストに変換する必要がある

```python:main.py
# 解いた結果のステータスが表示される
print("Status:", LpStatus[prob.status])
```

* 結果を出力する (変数)
    * 変数と、それらの解決された最適値を表示することができる

```python:main.py
# 最適化された各変数の値が表示される
for v in prob.variables():
    print(v.name, "=", v.varValue)
```

* 結果を出力する (目的関数値)
    * 最適化された目的関数値が表示される

```python:main.py
# 最適化された目的関数値が表示される
print("Total Cost of Ingredients per can = ", value(prob.objective))
```

* 総プログラム

```python:main.py
"""
PuLPモデラー用の簡略化されたWhiskasモデルPythonの定式化

Authors: michi_h 2019
"""

# PuLP モデラー関数のインポート
from pulp import *

# 問題データ作成
prob = LpProblem("The Whiskas Problem", LpMinimize)

# 下限を0とする鶏肉と牛肉の変数を作成する
x1 = LpVariable("ChickenPercent", 0)
x2 = LpVariable("BeefPercent", 0)

# 目的関数がprob に最初に追加される
prob += 0.013 * x1 + 0.008 * x2, "1缶あたりの材料のコスト"

# 5つの制約を入力
prob += x1 + x2 == 100, "割合合計"
prob += 0.100 * x1 + 0.200 * x2 >= 8.0, "たんぱく質の条件"
prob += 0.080 * x1 + 0.100 * x2 >= 6.0, "脂質の条件"
prob += 0.001 * x1 + 0.005 * x2 <= 2.0, "食物繊維の条件"
prob += 0.002 * x1 + 0.005 * x2 <= 0.4, "塩の条件"

# 問題データを.lp ファイルに書き出す
prob.writeLP("WhiskasModel.lp")

# PuLPの選択したソルバーが使用され、問題が解かれる
prob.solve()

# 解いた結果のステータスが表示される
print("Status:", LpStatus[prob.status])

# 最適化された各変数の値が表示される
for v in prob.variables():
    print(v.name, "=", v.varValue)

# 最適化された目的関数値が表示される
print("Total Cost of Ingredients per can = ", value(prob.objective))
```

* このファイルを実行すると、鶏肉が33.33%、牛肉が66.67%、1缶あたりの材料総コストが96セントであることを示す出力が生成される

```python:result
Status: Optimal
BeefPercent = 66.666667
ChickenPercent = 33.333333
Total Cost of Ingredients per can =  0.966666665
```

# 全ての問題解決

## 決定変数の特定

* 決定変数は缶に入れる異なる原料のパーセント
* 缶は100gなので、これらのパーセンテージは含まれている各成分のg単位の量も表している
* パーセンテージは0から100の間でなければならない

```math
x_1: キャットフードにおける鶏肉の割合\\
x_2: キャットフードにおける牛肉の割合\\
x_3: キャットフードにおける羊肉の割合\\
x_4: キャットフードにおける米の割合\\
x_5: キャットフードにおける小麦の割合\\
x_6: キャットフードにおけるゲルの割合
```

## 目的関数の定式化

* キャットフード1缶あたりの原材料の総コストを最小限に抑える

```math
min\hspace{5pt}$0.013x_1 + $0.008x_2 + $0.010x_3 + $0.002x_4 + $0.005x_5 + 0.001x_6
```

## 制約の定義

* パーセンテージの合計が100%になっていなければならない

```math
x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 100
```

* 栄養分析要件を満たさなければならない
    * 100gあたり8g以上のたんぱく質
    * 100gあたり6g以上の脂肪
    * 100gあたり2g以下の食物繊維
    * 100gあたり0.4g以下の塩

```math
0.100x_1 + 0.200x_2 + 0.150x_3 + 0.000x_4 + 0.040x_5 + 0.000x_6 \geq 8.0 \\
0.080x_1 + 0.100x_2 + 0.110x_3 + 0.010x_4 + 0.010x_5 + 0.000x_6 \geq 6.0 \\
0.001x_1 + 0.005x_2 + 0.003x_3 + 0.100x_4 + 0.150x_5 + 0.000x_6 \leq 2.0 \\
0.002x_1 + 0.005x_2 + 0.007x_3 + 0.002x_4 + 0.008x_5 + 0.000x_6 \leq 0.4
```

## 完全な問題の解決

* ファイルの目的と制作者の名前、日付についてコメントをつける
* PuLP のインポートも同様

```python:main2.py
"""
PuLPモデラー用の完全なWhiskasモデルPythonの定式化

Authors: michi_h 2019
"""

from pulp import *
```

* 変数を作成する
    * 問題データや問題変数を作成する前に、変数を作成する

```python:main2.py
# 材料のリスト
Ingredients = ['CHICKEN', 'BEEF', 'MUTTON', 'RICE', 'WHEAT', 'GEL']

# 各材料のコスト
costs = {'CHICKEN': 0.013, 
         'BEEF': 0.008, 
         'MUTTON': 0.010, 
         'RICE': 0.002, 
         'WHEAT': 0.005, 
         'GEL': 0.001}

# 各材料におけるたんぱく質の含有量
proteinPercent = {'CHICKEN': 0.100, 
                  'BEEF': 0.200, 
                  'MUTTON': 0.150, 
                  'RICE': 0.000, 
                  'WHEAT': 0.040, 
                  'GEL': 0.000}

# 各材料における脂質の含有量
fatPercent = {'CHICKEN': 0.080, 
              'BEEF': 0.100, 
              'MUTTON': 0.110, 
              'RICE': 0.010, 
              'WHEAT': 0.010, 
              'GEL': 0.000}

# 各材料における食物繊維の含有量
fibrePercent = {'CHICKEN': 0.001, 
                'BEEF': 0.005, 
                'MUTTON': 0.003, 
                'RICE': 0.100, 
                'WHEAT': 0.150, 
                'GEL': 0.000}

# 各材料における塩の含有量
saltPercent = {'CHICKEN': 0.002, 
               'BEEF': 0.005, 
               'MUTTON': 0.007, 
               'RICE': 0.002, 
               'WHEAT': 0.008, 
               'GEL': 0.000}
```

* 問題の作成

```python:main2.py
# 問題データを含むprob 変数を作成する
prob = LpProblem("The Whiskas Problem", LpMinimize)
```

* 辞書のデータ変数を作成し、それを参照する変数を作成する
    * それぞれの辞書のデータの中の値は、ぞれぞれの材料の割合を表すので、0 ～ 100 でなければならないが、下限を設定すれば、後から合計100%とする制約を追加するので、結果として0 ～ 100 の条件は守られる

```python:main2.py
# 辞書のデータ変数を参照する変数を作成する (下限0)
ingredient_vars = LpVariable.dicts("Ingr", Ingredients, 0)
```

* 目的関数の設定
    * lpSumは結果リストの合計の要素を追加する

```python:main2.py
# 目的関数はprob に最初に追加される
prob += lpSum([costs[i] * ingredient_vars[i] for i in Ingredients]), "1缶あたりの合計コスト"
```

* 制約の設定

```python:main2.py
# prob 変数に制約を追加する
prob += lpSum([ingredient_vars[i] for i in Ingredients]) == 100, "合計割合"
prob += lpSum([proteinPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 8.0, "たんぱく質の条件"
prob += lpSum([fatPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 6.0, "脂質の条件"
prob += lpSum([fibrePercent[i] * ingredient_vars[i] for i in Ingredients]) <= 2.0, "食物繊維の条件"
prob += lpSum([saltPercent[i] * ingredient_vars[i] for i in Ingredients]) <= 0.4, "塩の条件"
```

* 後は単純化された問題の解決と方法は変わらない

```python:main2.py
# 問題データを.lp ファイルに書き出す
prob.writeLP("WhiskasModel.lp")

# PuLPの選択したソルバーが使用され、問題が解かれる
prob.solve()

# 解いた結果のステータスが表示される
print("Status:", LpStatus[prob.status])

# 最適化された各変数の値が表示される
for v in prob.variables():
    print(v.name, "=", v.varValue)

# 最適化された目的関数値が表示される
print("Total Cost of Ingredients per can = ", value(prob.objective))
```

* 総プログラム

```python:main2.py
"""
PuLPモデラー用の完全なWhiskasモデルPythonの定式化

Authors: michi_h 2019
"""

from pulp import *

# 材料のリスト
Ingredients = ['CHICKEN', 'BEEF', 'MUTTON', 'RICE', 'WHEAT', 'GEL']

# 各材料のコスト
costs = {'CHICKEN': 0.013,
         'BEEF': 0.008,
         'MUTTON': 0.010,
         'RICE': 0.002,
         'WHEAT': 0.005,
         'GEL': 0.001}

# 各材料におけるたんぱく質の含有量
proteinPercent = {'CHICKEN': 0.100,
                  'BEEF': 0.200,
                  'MUTTON': 0.150,
                  'RICE': 0.000,
                  'WHEAT': 0.040,
                  'GEL': 0.000}

# 各材料における脂質の含有量
fatPercent = {'CHICKEN': 0.080,
              'BEEF': 0.100,
              'MUTTON': 0.110,
              'RICE': 0.010,
              'WHEAT': 0.010,
              'GEL': 0.000}

# 各材料における食物繊維の含有量
fibrePercent = {'CHICKEN': 0.001,
                'BEEF': 0.005,
                'MUTTON': 0.003,
                'RICE': 0.100,
                'WHEAT': 0.150,
                'GEL': 0.000}

# 各材料における塩の含有量
saltPercent = {'CHICKEN': 0.002,
               'BEEF': 0.005,
               'MUTTON': 0.007,
               'RICE': 0.002,
               'WHEAT': 0.008,
               'GEL': 0.000}

# 問題データを含むprob 変数を作成する
prob = LpProblem("The Whiskas Problem", LpMinimize)

# 辞書のデータ変数を参照する変数を作成する (下限0)
ingredient_vars = LpVariable.dicts("Ingr", Ingredients, 0)

# 目的関数はprob に最初に追加される
prob += lpSum([costs[i] * ingredient_vars[i] for i in Ingredients]), "1缶あたりの合計コスト"

# prob 変数に制約を追加する
prob += lpSum([ingredient_vars[i] for i in Ingredients]) == 100, "合計割合"
prob += lpSum([proteinPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 8.0, "たんぱく質の条件"
prob += lpSum([fatPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 6.0, "脂質の条件"
prob += lpSum([fibrePercent[i] * ingredient_vars[i] for i in Ingredients]) <= 2.0, "食物繊維の条件"
prob += lpSum([saltPercent[i] * ingredient_vars[i] for i in Ingredients]) <= 0.4, "塩の条件"

# 問題データを.lp ファイルに書き出す
prob.writeLP("WhiskasModel.lp")

# PuLPの選択したソルバーが使用され、問題が解かれる
prob.solve()

# 解いた結果のステータスが表示される
print("Status:", LpStatus[prob.status])

# 最適化された各変数の値が表示される
for v in prob.variables():
    print(v.name, "=", v.varValue)

# 最適化された目的関数値が表示される
print("Total Cost of Ingredients per can = ", value(prob.objective))
```

* 最適解は、牛肉60%、ゲル40%で、目的関数値は1缶あたり52セント

```python:result2
Status: Optimal
Ingr_BEEF = 60.0
Ingr_CHICKEN = 0.0
Ingr_GEL = 40.0
Ingr_MUTTON = 0.0
Ingr_RICE = 0.0
Ingr_WHEAT = 0.0
Total Cost of Ingredients per can =  0.52
```