製造業界のデータサイエンティスト奮闘記

製造業向けのビッグデータ分析やAIによるデータ解析、機械学習についてのブログ

生産計画をPython(PuLP)を使って最適化する

f:id:data_scientist:20181227160421j:plain
生産管理においては、MRP(資材所要量計画)という管理手法は古くからありますが、今でも製造業を中心に当たり前のように活用されています。MRPののちにERPとして製造から受注、出荷、財務、会計など企業内経営資源のほとんどを含むようになり、今では全体最適化の考え方が導入されている企業も多いでしょう。今回は企業内での全体最適というよりも、いち製造担当者が管理できるレベルの生産計画を最適化するための方法について書いてみたいと思います。

Excelでも最適化ソルバーというのもあるんですが、Excelは遅いうえに扱える変数や制約式の数が少ないので、PythonPuLPというライブラリを使った方法について紹介します。

数理最適化とは

いろいろと似たような用語が多くて混乱するんですが、数理最適化は数理計画問題とか最適化問題などと呼ばれ、様々な制約の下で目的の一次式(関数)が最小または最大になる値を求めるものです。代表的なものには下記のような問題があります。

  1. ナップサック問題:ナップサックの中にいくつかの品物を詰め込み、入れた品物の総価値を最大にする。
  2. 巡回セールスマン問題:セールスマンが全ての都市を訪問して出発地点に帰還する場合、最短経路で回れる訪問順序を求める。
  3. 生産計画問題:工場での生産においてコストを最小化したり、利益を最大化する。

これらの問題を解くために様々なアルゴリズムはありますが、アルゴリズムを選択する以前の課題として、問題をどのように定式化するかという点が重要なポイントになってきます。この手の問題の例でよくあるのが、「製品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

各月に出荷する製品をその月中に全て生産できるとは限らないので、前の月に生産した製品を在庫として保管して来月に出荷することも考えられます。このような状況の下で、要求された製品の出荷量と与えられた原料の利用可能量の制約を満たしつつ総コストを最小にするには、各月における各製品の生産量と在庫量をどのように決定すればよいでしょうか。

PythonPuLPでモデル化

実装する前にまず、各条件を定式化する必要があります。変数として各月における製品I、IIの生産量をそれぞれx_{{\rm I}1}, x_{{\rm II}1}, x_{{\rm I}2}, x_{{\rm II}2}, x_{{\rm I}3}, x_{{\rm II}3}、在庫量をy_{{\rm I}1}, y_{{\rm II}1}, y_{{\rm I}2}, y_{{\rm II}2}とします。

最小化するべき目的関数は、各生産量/在庫量とその単位量あたりのコストとの積の総和として表現することができます。

また、1ヶ月に利用できる原料が決められているので、各月ごとに各原料に関する制約が必要です。さらに、各製品に対して在庫量は次の月に持ち越せますので、それを踏まえた出荷量の制約を加えます。

以上のことから、次のように定式化することができます。

集合

Product = \{ {\rm I},{\rm II}\} 製品
Material = \{ A,B\} 原料
Period = \{ 1,2,3\} 期間

定数

use_{ij},i \in Product,j \in Material 製品iを生産するのに必要な原料jの使用量
out_{it},i \in \Pr oduct,t \in Period tヶ月目の製品iの出荷量
upper_{jt},j \in Material,t \in Period tヶ月目の原料jの利用可能量
cost{p_i},i \in Product 製品iの生産コスト
cost{i_i},i \in Product 製品iの在庫コスト

変数

x_{it},i \in Product,t \in Period 製品itヶ月目の生産量
y_{it},i \in Product,t \in Period 製品itヶ月目の在庫量

目的関数(最小化)

\displaystyle\sum_{t \in Period} \sum_{i \in Product} (costp_{it} x_{it} + costi_{it} y_{it}) 総コスト

制約

x_{it} \ge 0,\forall i \in Product,\forall t \in Period 生産量の非負制約
y_{it} \ge 0,\forall i \in Product,\forall t \in Period 在庫量の非負制約
\displaystyle\sum_{i \in Product} use_{ij} x_{it} \le upper_{jt}, \forall j \in Material,\forall t \in Period 原料の使用量の制約
x_{i1} - y_{i1} = out_{i1} 1ヶ月目の出荷量
x_{i2} + y_{i1} - y_{i2} = out_{i2} 2ヶ月目の出荷量
x_{i3} + y_{i2} = out_{i3} 3ヶ月目の出荷量

上記の数理モデルPythonPuLPライブラリを使って実装していきます。

# (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