生産計画をPython(PuLP)を使って最適化する
生産管理においては、MRP(資材所要量計画)という管理手法は古くからありますが、今でも製造業を中心に当たり前のように活用されています。MRPののちにERPとして製造から受注、出荷、財務、会計など企業内経営資源のほとんどを含むようになり、今では全体最適化の考え方が導入されている企業も多いでしょう。今回は企業内での全体最適というよりも、いち製造担当者が管理できるレベルの生産計画を最適化するための方法について書いてみたいと思います。
Excelでも最適化ソルバーというのもあるんですが、Excelは遅いうえに扱える変数や制約式の数が少ないので、PythonのPuLPというライブラリを使った方法について紹介します。
数理最適化とは
いろいろと似たような用語が多くて混乱するんですが、数理最適化は数理計画問題とか最適化問題などと呼ばれ、様々な制約の下で目的の一次式(関数)が最小または最大になる値を求めるものです。代表的なものには下記のような問題があります。
- ナップサック問題:ナップサックの中にいくつかの品物を詰め込み、入れた品物の総価値を最大にする。
- 巡回セールスマン問題:セールスマンが全ての都市を訪問して出発地点に帰還する場合、最短経路で回れる訪問順序を求める。
- 生産計画問題:工場での生産においてコストを最小化したり、利益を最大化する。
これらの問題を解くために様々なアルゴリズムはありますが、アルゴリズムを選択する以前の課題として、問題をどのように定式化するかという点が重要なポイントになってきます。この手の問題の例でよくあるのが、「製品A/Bの価格がAp/Bp[¥]で、原材料X/YをXw/Yw[kg]づつ使うときに、利益が最大化する生産数を求めよ」といった例題です。とはいえ製造の担当者が大元の生産数を決めるということなどまずありえないわけで、製造担当者向けに使えそうな問題を引用してみます。*1
問題
2種類の原料A、Bを加工して2種類の製品I、 IIを生産している工場が、3ヶ月間の生産計画を立てようとしています。各製品を1単位生産するために必要な原料の使用量、各製品の生産/在庫コスト、各製品の月ごとの出荷量、各原料の月ごとの利用可能量は以下のように与えられています。
原料使用量
Ⅰ Ⅱ A 2 7 B 5 3 生産/在庫コスト
Ⅰ Ⅱ 生産 75 50 在庫 8 7 製品の出荷量
I II 1ヶ月目 30 20 2ヶ月目 60 50 3ヶ月目 80 90 原料の利用可能量
A B 1ヶ月目 920 790 2ヶ月目 750 600 3ヶ月目 500 480 各月に出荷する製品をその月中に全て生産できるとは限らないので、前の月に生産した製品を在庫として保管して来月に出荷することも考えられます。このような状況の下で、要求された製品の出荷量と与えられた原料の利用可能量の制約を満たしつつ総コストを最小にするには、各月における各製品の生産量と在庫量をどのように決定すればよいでしょうか。
PythonのPuLPでモデル化
実装する前にまず、各条件を定式化する必要があります。変数として各月における製品I、IIの生産量をそれぞれ、在庫量をとします。
最小化するべき目的関数は、各生産量/在庫量とその単位量あたりのコストとの積の総和として表現することができます。
また、1ヶ月に利用できる原料が決められているので、各月ごとに各原料に関する制約が必要です。さらに、各製品に対して在庫量は次の月に持ち越せますので、それを踏まえた出荷量の制約を加えます。
以上のことから、次のように定式化することができます。
集合
製品 | |
原料 | |
期間 |
定数
製品を生産するのに必要な原料の使用量 | |
ヶ月目の製品の出荷量 | |
ヶ月目の原料の利用可能量 | |
製品の生産コスト | |
製品の在庫コスト |
変数
製品のヶ月目の生産量 | |
製品のヶ月目の在庫量 |
目的関数(最小化)
総コスト |
制約
生産量の非負制約 | |
在庫量の非負制約 | |
原料の使用量の制約 | |
1ヶ月目の出荷量 | |
2ヶ月目の出荷量 | |
3ヶ月目の出荷量 |
上記の数理モデルをPythonのPuLPライブラリを使って実装していきます。
# (1)ライブラリ呼び出し import pulp # (2)問題の定義 lp = pulp.LpProblem("総コスト", pulp.LpMinimize) # (3)変数の設定 x11 = pulp.LpVariable("製品Iの1ヶ月目の生産量", 0) x12 = pulp.LpVariable("製品Iの2ヶ月目の生産量", 0) x13 = pulp.LpVariable("製品Iの3ヶ月目の生産量", 0) x21 = pulp.LpVariable("製品IIの1ヶ月目の生産量", 0) x22 = pulp.LpVariable("製品IIの2ヶ月目の生産量", 0) x23 = pulp.LpVariable("製品IIの3ヶ月目の生産量", 0) y11 = pulp.LpVariable("製品Iの1ヶ月目の在庫量", 0) y12 = pulp.LpVariable("製品Iの2ヶ月目の在庫量", 0) y21 = pulp.LpVariable("製品IIの1ヶ月目の在庫量", 0) y22 = pulp.LpVariable("製品IIの2ヶ月目の在庫量", 0) # (4)目的関数の生成 lp += 75 * x11 + 50 * x21 + 8 * y11 + 7 * y21 + 75 * x12 + 50 * x22\ + 8 * y12 + 7 * y22 + 75 * x13 + 50 * x23 # (5)制約条件の生成 # 非負制約 lp += x11 >= 0 lp += x12 >= 0 lp += x13 >= 0 lp += x21 >= 0 lp += x22 >= 0 lp += x23 >= 0 lp += y11 >= 0 lp += y12 >= 0 lp += y21 >= 0 lp += y22 >= 0 # 原料の制約 lp += 2 * x11 + 7 * x21 <= 920 lp += 5 * x11 + 3 * x21 <= 790 lp += 2 * x12 + 7 * x22 <= 750 lp += 5 * x12 + 3 * x22 <= 600 lp += 2 * x13 + 7 * x23 <= 500 lp += 5 * x13 + 3 * x23 <= 480 # 出荷量の制約 lp += x11 - y11 == 30 lp += x21 - y21 == 20 lp += x12 + y11 - y12 == 60 lp += x22 + y21 - y22 == 50 lp += x13 + y12 == 80 lp += x23 + y22 == 90 # (6)最適化問題の確認 print(lp) # (7)求解 lp.solve() # (8)結果の確認 print("x11=", x11.value()) print("x12=", x12.value()) print("x13=", x13.value()) print("x21=", x21.value()) print("x22=", x22.value()) print("x23=", x23.value()) print("y11=", y11.value()) print("y12=", y12.value()) print("y21=", y21.value()) print("y22=", y22.value()) print("cost=", lp.objective.value())
特徴的な書き方として、PuLPでは「モデル += … <= 値」で制約条件を追加していきます。他には、「>=」も使えますが、「!=」は使えません。
結果
x11= 38.0 x12= 67.862069 x13= 64.137931 x21= 20.0 x22= 86.896552 x23= 53.103448 y11= 8.0 y12= 15.862069 y21= 0.0 y22= 36.896552 cost= 21199.172415999998
これで最適な生産量が求められました。21199がコスト最小となります。
補足ですが、この問題を整数計画問題として解きたい場合は、LpVariableの0となっているところをcat="Integer"とすれば整数のみで解けるようになります。
実装そのものはシンプルなので、定式化の部分をいかに上手く表現するかがポイントです。上手く表現されていないと値が収束せずに発散することもあるので気を付けていきたいと思います。
参考文献
*1:福島雅夫,数理計画入門,朝倉書店,1996