LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@michi_h

PuLP 演習1 ブレンド問題

Posted at

問題の説明

  • 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つの材料だけでキャットフードを作りたいとする
  • 決定変数を定義する
x_1: キャットフードにおける牛肉の割合 \\
x_2: キャットフードにおける鶏肉の割合
  • これらの変数に対する制限 (ゼロより大きい) に注意する必要があるが、Pythonの実装ではそれらを別々に入力したり、リストにしたり、他の制約とともにリストにしたりすることはしない

目的関数の定式化

  • 目的関数は次のようになる
    • キャットフードにおける鶏肉と牛肉の合計金額が最低になるようにしたい
min\hspace{5pt}0.013x_1 + 0.008x_2

制約の定義

  • 割合なので、それぞれの変数の合計は100%にならなければならない
x_1 + x_2 = 100
  • 栄養要件を満たさなければならない
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

単純化された問題の解決

  • ファイルの最初の部分には、プログラムの目的の概要を説明した短いコメント欄がある
main.py
"""
PuLPモデラー用の簡略化されたWhiskasモデルPythonの定式化

Authors: michi_h 2019
"""
  • PuLP関数をインポートする
main.py
# PuLP モデラー関数のインポート
from pulp import *
  • 問題データを作成する
    • prob という変数を LpProblem というクラスを使用して作成する
    • 2つパラメータがある
      • 問題の任意の名前
      • 解決しようとしているLP (Linear Programming) の種類 (LpMinimize (最小化), LpMaximize (最大化) のいずれか)
main.py
# 問題データ作成
prob = LpProblem("The Whiskas Problem", LpMinimize)
  • 問題変数を作成する
    • x1、x2という変数を、LpVariable というクラスを使用して作成する
    • 4つのパラメータを持つ
      • 変数が表すものの任意の名前
      • 変数の下限 (デフォルトはNone (負の無限大))
      • 変数の上限 (デフォルトはNone (正の無限大))
      • 本質的なデータのタイプ (離散 (LpInteger)、または連続 (LpContinuous) 、LpContinuous がデフォルト)
main.py
# 下限を0とする鶏肉と牛肉の変数を作成する
x1 = LpVariable("ChickenPercent", 0)
x2 = LpVariable("BeefPercent", 0)
  • 目的関数を設定する
    • 目的関数は最初に論理的に入力され、カンマに続いて目的関数が何であるかを説明する文字列が続く
main.py
# 目的関数がprob に最初に追加される
prob += 0.013 * x1 + 0.008 * x2, "1缶あたりの材料のコスト"
  • 制約を設定する
    • 制約式の最後に、カンマに続いて制約の簡単な説明を入力して、制約を論理的に入力する
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 ファイルをテキストエディタで開いて、今までの手順が何をしているのかを確認できる
main.py
# 問題データを.lp ファイルに書き出す
prob.writeLP("WhiskasModel.lp")
  • 問題を解く
    • LPは、PuLPの選択したソルバーを使用して解かれる
main.py
# PuLPの選択したソルバーが使用され、問題が解かれる
prob.solve()
  • 結果を出力する (ステータス)
    • prob.status の値は整数値で返却される
    • これを、辞書を使用して意味のあるテキストに変換する必要がある
main.py
# 解いた結果のステータスが表示される
print("Status:", LpStatus[prob.status])
  • 結果を出力する (変数)
    • 変数と、それらの解決された最適値を表示することができる
main.py
# 最適化された各変数の値が表示される
for v in prob.variables():
    print(v.name, "=", v.varValue)
  • 結果を出力する (目的関数値)
    • 最適化された目的関数値が表示される
main.py
# 最適化された目的関数値が表示される
print("Total Cost of Ingredients per can = ", value(prob.objective))
  • 総プログラム
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セントであることを示す出力が生成される
result
Status: Optimal
BeefPercent = 66.666667
ChickenPercent = 33.333333
Total Cost of Ingredients per can =  0.966666665

全ての問題解決

決定変数の特定

  • 決定変数は缶に入れる異なる原料のパーセント
  • 缶は100gなので、これらのパーセンテージは含まれている各成分のg単位の量も表している
  • パーセンテージは0から100の間でなければならない
x_1: キャットフードにおける鶏肉の割合\\
x_2: キャットフードにおける牛肉の割合\\
x_3: キャットフードにおける羊肉の割合\\
x_4: キャットフードにおける米の割合\\
x_5: キャットフードにおける小麦の割合\\
x_6: キャットフードにおけるゲルの割合

目的関数の定式化

  • キャットフード1缶あたりの原材料の総コストを最小限に抑える
min\hspace{5pt}$0.013x_1 + $0.008x_2 + $0.010x_3 + $0.002x_4 + $0.005x_5 + 0.001x_6

制約の定義

  • パーセンテージの合計が100%になっていなければならない
x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 100
  • 栄養分析要件を満たさなければならない
    • 100gあたり8g以上のたんぱく質
    • 100gあたり6g以上の脂肪
    • 100gあたり2g以下の食物繊維
    • 100gあたり0.4g以下の塩
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 のインポートも同様
main2.py
"""
PuLPモデラー用の完全なWhiskasモデルPythonの定式化

Authors: michi_h 2019
"""

from pulp import *
  • 変数を作成する
    • 問題データや問題変数を作成する前に、変数を作成する
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}
  • 問題の作成
main2.py
# 問題データを含むprob 変数を作成する
prob = LpProblem("The Whiskas Problem", LpMinimize)
  • 辞書のデータ変数を作成し、それを参照する変数を作成する
    • それぞれの辞書のデータの中の値は、ぞれぞれの材料の割合を表すので、0 ～ 100 でなければならないが、下限を設定すれば、後から合計100%とする制約を追加するので、結果として0 ～ 100 の条件は守られる
main2.py
# 辞書のデータ変数を参照する変数を作成する (下限0)
ingredient_vars = LpVariable.dicts("Ingr", Ingredients, 0)
  • 目的関数の設定
    • lpSumは結果リストの合計の要素を追加する
main2.py
# 目的関数はprob に最初に追加される
prob += lpSum([costs[i] * ingredient_vars[i] for i in Ingredients]), "1缶あたりの合計コスト"
  • 制約の設定
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, "塩の条件"
  • 後は単純化された問題の解決と方法は変わらない
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))
  • 総プログラム
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セント
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
2
0
0

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
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?