たかしくんは生産ラインを最適化したい

# 数理最適化を極めたい
以前書いた[たかしくん記事](https://qiita.com/canonno/items/29eb369d32c030fea367)で、数理最適化の面白さに気づいてしまいました。
今見直すとずいぶんとクレイジーな記事を書いているなと気づきます。
今回はpulpを使って生産ラインの最適化をやってみようと思います。

# 状況設定
## 追い込まれるたかしくん
たかしくんが勤めているTAKAHASHI Corpは、4つのプロテイン製品を生産している。
たかしくんはある日、急遽上司に呼び出され、3日後までの生産計画を作ることを命じられた。
作る製品4種類それぞれには特徴があり、原料同士の相性・危機の清掃・スイッチなどで、「これを作ると次これは作れない」という組み合わせがあるそうだ。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/666990/78b81c32-5258-5c01-a6e0-ce33e0ab3de7.png)


TAKAHASHI Corpが持っている生産ラインは3つ。
ラインの性能差や、ラインと製品との相性もあるため、一日で製造できる量もまちまちだ。
調査によると、一日で作れる量は次の通りらしい。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/666990/e76d6757-7099-5785-fc6c-c4e48e6c8be5.png)



最終的な製造計画のイメージは次の通り。
どのラインでどれを作るか。前後工程の相性もある以上、パズルを全力で解くため、
たかしくんは必死にExcelと向き合うのであった・・・。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/666990/b54e3f25-9ea3-9104-5ee7-242ddf31fedb.png)

## 生産ラインの条件を変数にする
pulpを使って数理最適化してみます。
基本的には[たかしくん記事](https://qiita.com/canonno/items/29eb369d32c030fea367)や[こちらの記事](https://docs.pyq.jp/python/math_opt/pulp.html)を基に作成しています。
さきほどのテーブルを条件として変数定義します。

将来的にはCSVを読み込ませて定義できると楽そう。

```py
!pip install pulp
from pulp import *

# 何日以内に、何をどれぐらい作るか
num_of_produce_dates = 3
aim_dict = {"a":7,"b":6,"c":3,"d":3}

# 組み合わせの禁則ルール
product_banned_combination_info_list = {"a":["b","d"],"b":["c","d"],"c":["d"],"d":["a"]}

# どのラインで、何をどれぐらい作れるか
line_info_dict = {"A":{"a":5,"b":3,"c":1,"d":0},"B":{"a":3,"b":0,"c":1,"d":2},"C":{"a":1,"b":2,"c":1,"d":1}}
```
後続の作業に必要となるため、itertoolsを使って「いつどこでなにを作る」という情報と、変数番号との対応表を作ります。
リスト×リストの組み合わせが便利に行えるようです。
[この記事](https://note.nkmk.me/python-math-factorial-permutations-combinations/#itertoolscombinations)がすっごく便利。

```py
import itertools
itsu_dokode_naniwo= list(v1 for v1 in itertools.product(range(0,num_of_produce_dates,1),list(line_info_dict.keys()), list(aim_dict.keys())))
hensu_taio = list((i,v2) for i,v2 in enumerate(itsu_dokode_naniwo))
```
中身はこんな感じ。ここ辞書型の方が良いのかまだ検証できておらず。
リファクタリングちゃんとやりたい。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/666990/61ee9c0e-032c-c304-0891-11445ab955c3.png)

## 最適化条件の定義
今回必要な制約条件は3つ。
> ①特定の日、特定のラインでは、一種類のモノしか作れない。
> ②2ライン合計の生産量が、求められる生産量を上回る。
> ③後続禁止の組み合わせが存在する。

これらを実装していきます。

まずは変数の定義。0-1のInteger型として定義。
```py
m = LpProblem() # 数理モデル
#変数名
x = [LpVariable('x%d%s%s'%(i,d,n), lowBound=0, upBound=1,cat="Integer") for (i,d,n) in itsu_dokode_naniwo]
m += lpSum(x) # 目的関数：なるべく稼働させないことを優先して
```

制約条件①「特定の日、特定のラインでは、一種類のモノしか作れない。」は次の通り。

```py
#同じ日に
for dy in range(0,num_of_produce_dates,1):
    #同じラインで作れるのは1種類以下
    for l in list(line_info_dict.keys()):
        m += lpSum(x[k]for k,(i,d,n) in hensu_taio if (i,d) == (dy,l)) <= 1
```
制約条件②「2ライン合計の生産量が、求められる生産量を上回る。」
制約条件③「後続禁止の組み合わせが存在する。」は両方とも製品軸なので、製品軸でfor文をぐるぐるしました。ただ、forの入れ子になりすぎているのでもっと賢いやり方ありそう。
知見求む。

```py
for p in list(aim_dict.keys()):
    # 制約条件②
    m += lpSum(x[k]*line_info_dict[d][n] for k,(i,d,n) in hensu_taio if n == p) >= aim_dict[p]

    # 制約条件③
    #後続で続いてはイケないものを確認
    for bp in product_banned_combination_info_list[p]:
        #連続した日に
        for dy in range(0,num_of_produce_dates-1,1):
            #あるラインで
            for l in list(line_info_dict.keys()):
                #組み合わせで作っちゃだめよ
                m += lpSum(x[k] for  k,(i,d,n) in hensu_taio if (i,d,n) == (dy, l, p) or (i,d,n) == (dy+1,l,bp)) <= 1
```

## 最適化計算して整理
ソルブしたあと計算結果を吐き出させます。
ここも将来CSVで吐き出させるとかやりたい。
m.statusは1なら計算成功。他は基本失敗。[このページ](https://docs.pyq.jp/python/math_opt/pulp.html)を参照しよう。

```py
m.solve()
print(m.status)

#見せるようのデータフレーム
import pandas as pd
df_line = pd.DataFrame(columns=list(line_info_dict.keys()),index=range(num_of_produce_dates))
df_prod = pd.DataFrame(columns=list(aim_dict.keys()),index=range(num_of_produce_dates))
df_line.fillna("-")
df_prod.fillna("-")

ans_list = []
ans_list = [(i,d,n) for k, (i,d,n) in hensu_taio if value(x[k]) > 0]
res = {"a":0,"b":0,"c":0,"d":0}

for i,d,n in ans_list:
    df_line.at[i,d] = n
    df_prod.at[i,n] = line_info_dict[d][n]
    
display(df_line)
display(df_prod)

```
displayの結果はこの通り。
上は生産計画、下は各製品の日ごとの生産量。
a,b,c,dいずれも7,6,3,3が生産目標に対し、8,6,3,3作れてますね。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/666990/01628eca-1aea-7235-0728-5b706b28d962.png)
今回a,bが癖ありで、次に作れる製品にかなり制約がありました。
aは基本最後に作ろうね、ということみたいですね。

こうしてたかしくんは無事、生産計画を作り終えたのでした。めでたしめでたし。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/666990/0f915bc6-8e29-6696-e890-5f2818ad7137.png)

# ちなみに
## 3倍の生産量を3倍の期間で
ここからはおもちゃタイム。
3倍の期間で3倍量作るってなったらどうなるんだろう、と思い実験。
条件と結果だけ示しますね。

```py
!pip install pulp
from pulp import *

# ここを全部
num_of_produce_dates = 9
aim_dict = {"a":21,"b":18,"c":9,"d":9}

# おなじ
product_banned_combination_info_list = {"a":["b","d"],"b":["c","d"],"c":["d"],"d":["a"]}

# おなじ
line_info_dict = {"A":{"a":5,"b":3,"c":1,"d":0},"B":{"a":3,"b":0,"c":1,"d":2},"C":{"a":1,"b":2,"c":1,"d":1}}
```
結果。なんかのびのび作っている感じがしますね。休みの期間を設けるほどの余裕。
a,b,c,dそれぞれ21,18,9,10作っており余裕の表情です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/666990/786c73c0-15ce-f447-1ddf-41e89527e0b2.png)

## 3倍の生産量を3倍のライン数で
今度は期間は3日間で同じとし、ライン数を9本にしてやってみます。
スペックはA,B,Cそれぞれ全く同じものが増設されたと仮定します。
贅沢ですね。

```py
!pip install pulp
from pulp import *

# 期間同じ、目標だけ3倍
num_of_produce_dates = 3
aim_dict = {"a":21,"b":18,"c":9,"d":9}

# おなじ
product_banned_combination_info_list = {"a":["b","d"],"b":["c","d"],"c":["d"],"d":["a"]}

# ライン3倍
line_info_dict = {"A":{"a":5,"b":3,"c":1,"d":0},"B":{"a":3,"b":0,"c":1,"d":2},"C":{"a":1,"b":2,"c":1,"d":1},
                  "D":{"a":5,"b":3,"c":1,"d":0},"E":{"a":3,"b":0,"c":1,"d":2},"F":{"a":1,"b":2,"c":1,"d":1},
                  "G":{"a":5,"b":3,"c":1,"d":0},"H":{"a":3,"b":0,"c":1,"d":2},"I":{"a":1,"b":2,"c":1,"d":1},}
```
結果。Iラインが使われずじまい。
aの製造がめんどくさいのか、「とにかく最終日にみんなでつくっちゃおう！片付けめんどくさいから！！」という気概を感じますね。
a,b,c,dそれぞれ21,18,9,10作って成功です。
ちなみにライン数を8に減らすと最適化できなかったので、ギリギリなんだなと。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/666990/26756f1f-5d38-418d-24eb-b72f2b476023.png)

# おわりに
数理最適化おもしろーーーーい！
あとはインターフェースとか上手く作れるといいな。