【Python MIP版】動的ロットサイズ決定問題の基本【dynamic lotsizing problem / Wagner-Whitinモデル（ワグナー・ウィッティンモデル）】

【はじめに】

動的ロットサイズ決定問題をざっくりいうと

ある製品の「需要量がシーズンによって変動する環境」で、
「どのシーズン」に「どれくらいの生産量を設定するか」 or 「在庫でまかなうか」
といったことを決めて何らかの目的(※)を達成しようとする問題のこと。

※総費用をできるだけ小さくする、など

イメージ図は以下の通り。

▲動的ロット問題の基本形のイメージ（単段階で単一品目のイメージ図）

※実際は、複数部品から製品が構成される、品目が複数ある、リード時間がある、等々、複雑な依存関係がでてくる。

※Wagner-Whitinモデル（ワグナー・ウィッティン モデル）について

簡単にいうと「生産量上限」がないもののこと。

「動的ロットサイズ決定問題」の「詳細な説明・理論部分」は「専門家や書籍」を探して自分で調べてみよう。

---

今回はこの問題を「Python MIP」でプログラムしてみる。

※Python-MIPのドキュメント

Python-MIP

【例題】

ある製品について６シーズン分の生産計画（はじめは在庫などすべて０）を考える。

■各種パラメータについて
・変動費用：製品１つ生産する際にかかる費用
・段取り費用：そのシーズンに生産を行う場合に発生する固定費用
・在庫保管費：在庫１個当たりにかかる保管費用
・需要量：そのシーズンに要求(消費)される製品の量
・生産量上限：そのシーズンに生産できる量の上限

※補足：「最終在庫量」の考え方について
「そのシーズンに最終的に残る製品量」という意味で使っている。
つまり、
「前シーズンの在庫」、「そのシーズンの生産量」、「そのシーズンの製品消費量(需要量)」によって決まる値。

■今回の目的
「シーズン１～６」までの「各生産量」をいい感じに調整して、
「変動費用」、「段取り費用」、「在庫保管費」の合計費用をできるだけ小さくしたい。

【目的関数 / 制約条件に対する数式】

結論から言うと「目的関数や制約条件に対する数式」は、次の通りに表現される。

■目的関数

■制約条件

以上を踏まえてプログラムを作っていく。実行環境は「Google Colab」。

計算効率の良いアルゴリズムを使ったり、実行速度やメモリ使用量などの観点から最適化したりするプログラムの書き方は、その道のプロ達に任せることにする。

ここではわかりやすく単純に、数式通りのプログラムを作っていく。

【１】Python-MIPのインストール

!pip install mip

【２】サンプルデータの作成

値としてわかっているサンプルデータを生成。

# 各シーズンのパラメータ
data_p = [0, 41, 73, 19, 73, 89, 92] # 変動費の単価
data_f = [0, 26, 23, 27, 19, 12, 22] # 段取り費用
data_s = [0, 17, 11, 19, 18, 10, 17] # 在庫保管費用の単価
data_d = [0, 14, 33, 46, 18, 31, 15] # 商品需要量
data_C = [0, 104, 93, 96, 94, 114, 116] # 生産上限

【３】Modelの作成

※「Python-MIP」での「Model」の作り方は以下参照

Classes — Python-MIP documentation

from mip import Model


# モデルオブジェクト作成
# Solverはデフォルト設定
m = Model("My_Model")

※補足：Python-MIPで使用できるソルバーについて
ソースコードを見ると以下のような記述がある。(2022/3/15時点)

# solvers
CBC = "CBC"
CPX = "CPX"  # we plan to support CPLEX in the future
CPLEX = "CPX"  # we plan to support CPLEX in the future
GRB = "GRB"
GUROBI = "GRB"
SCIP = "SCIP"  # we plan to support SCIP in the future

mip.constants.pyより抜粋

つまり今「Python-MIP」で使用可能なソルバーは「CBC：COIN-OR Branch-&-Cut」と「GRB,GUROBI：Gurobi（商用ソルバー）」の２つだけである。

ここでは「デフォルトのソルバー：ＣＢＣ」を使っていく。

【４】変数の定義

ますは「各シーズンの生産量変数」と「生産する/しないフラグ変数」を定義する。

「Python-MIP」では「add_ver()」を使って変数を生成する。

Classes — Python-MIP documentation

from mip import CONTINUOUS, BINARY

# 各シーズンにおける生産量
x = [m.add_var(var_type=CONTINUOUS, ub=data_C[i]) for i in range(len(data_C))]


# 生産ON/OFFフラグ
y = [m.add_var(var_type=BINARY) for i in range(len(data_C))]

print(x)
print(y)

【ここまでの実行結果例】
※変数：xの出力
[<mip.entities.Var at 0x7f4827b6ba90>,
<mip.entities.Var at 0x7f4827b6b590>,
<mip.entities.Var at 0x7f4827b6b5d0>,
<mip.entities.Var at 0x7f4827b6b990>,
<mip.entities.Var at 0x7f4827b6b890>,
<mip.entities.Var at 0x7f4827b8e810>,
<mip.entities.Var at 0x7f4827b8e790>]

※変数：yの出力
[<mip.entities.Var at 0x7f4827b8e690>,
<mip.entities.Var at 0x7f4827b6bfd0>,
<mip.entities.Var at 0x7f4827b8e7d0>,
<mip.entities.Var at 0x7f4827b6b650>,
<mip.entities.Var at 0x7f4827b6bb50>,
<mip.entities.Var at 0x7f4827b6bc10>,
<mip.entities.Var at 0x7f4827b6b6d0>]

▲どちらも「7つ（6シーズン＋ダミーシーズン）」のオブジェクト変数ができている

つぎに「最終在庫量」について。
ここでは数式通りに「最終在庫量」は「前シーズンの在庫量」、「用意した変数：x」、「需要量」で構成される変数としてみる。