サプライ・チェイン最適化について 研究者・実務家が知っておくべきこと 東京海洋大学 久保幹雄

本日の内容 数理計画 在庫理論 モデリングのための十戒

数理計画 定式化の強さと多面体論（妥当不等式，側面） 拡張定式化と射影 分解法の基本原理（列生成，Lagrange緩和の理論的背景）

強い定式化 MIP問題 実行可能解の集合 X 多面集合PX　がXの定式化 強い定式化

妥当不等式，切除平面，側面 弱い定式化の 制約（妥当不等式） 側面 緩和解 x* 解 x conv (X) 整数多面体 切除平面

最大安定集合問題の多面体表現 問題 整数多面体 conv (X) 次元（アフィン独立な点－１）＝３

小数解と側面 緩和多面体 小数解 側面 側面の証明：次元＝２

拡張定式化と射影 は X の定式化 = Q は X の拡張定式化

ロットサイズ決定問題 標準定式化のフローモデル 生産量(t) 在庫量(t) 在庫量(t-1) 期 t 需要量(t) 弱い定式化の原因 生産量(t)≦大きな数 “Large M” ×段取りの有無(t) 在庫量（t-1)+生産量(t)=需要量(t)+在庫量（t) 0-1変数

ロットサイズ決定問題 施設配置定式化のフローモデル s期に生産してt期まで在庫される量 期 s 期 t 需要量(t) s期に生産してt期まで在庫される量 ≦需要量(t)×段取りの有無(t) s期に生産してt期まで在庫される量 = 需要量(t)

施設配置定式化と多面体の概念図 拡張された空間の多面体 （施設配置定式化） 射影 オリジナルの空間の整数多面体

定式化のサイズと強さの比較 標準定式化 施設配置定式化 変数の数 変数の数 弱い定式化 強い定式化 =線形計画緩和が 整数多面体と一致 制約の数 制約の数 (S,l)不等式 切除平面 追加した 制約の数 n: 期数 強い定式化

分解（decomposition） Y,Z が容易に解ける（or 強い定式化が可能 or 側面同定可能） Y,Z に対する 1) 強い定式化 2)拡張定式化 3)切除平面法 例：多品目ロットサイズ決定問題 Z 資源制約（単一点フローモデル） 品目ごとに強い（拡張）定式化 （ or 切除平面法） Y

分解（列生成，Lagrange緩和） Y だけが容易に解ける． Z の定式化 => 列生成法，Lagrange緩和 主問題 (Z) Dx≧dに対する双対変数π 解（列） x 子問題 (Y)

列生成法 端点ベクトル 主問題 被約費用が大きい 列はプールから除く 被約費用が負の解を =>双対変数π を算出 すべて列プールに追加 子問題 => 下界と新しい解 x を与える．

Lagrange緩和 ステップサイズ 主問題 ：劣勾配法で双対変数π を更新 子問題 => 下界と新しい解 x を与える． 下界 劣勾配法 => 収束遅い & 下界上昇の保証なし => 特に実務では頑強性に注意！

Lagrange緩和と列生成の関係 子問題 端点の中から 最適解を選ぶ 主問題 同値なLP 列生成 = 切除平面の追加 L(π) π

Bundle法 最良下界のπ： 安定化を入れた Lagrange双対問題 安定化を入れた列生成法の主問題

数理計画を使うのための戒め 定式化することと解けることは別物である．特にLarge Mを使用した無謀な定式化は避けるべき． Lagrange緩和で多用される劣勾配法は脆弱であるので，実務には使うべきではない．Bundle法やVolume法を実装する元気がないなら列生成法が良い． できたら強い定式化だけで解けることが望ましい．（研究者は小難しい解法を使いたがる．） 教科書モデルで実務が解けると思うなかれ． 実装＋テストを学生，部下，下請けに丸投げするなかれ．言い換えれば，テスト問題例だけを解けるようにチューニングした結果を信じるなかれ．

（安全）在庫理論 新聞売り子モデル 非定常モデル エシェロン（梯形）在庫の概念とその利点 シミュレーションと最適化の融合法 安全在庫配置モデル

新聞売り子モデル 新聞１刊が売れ残ったときの在庫費用 新聞１刊が品切れしたときの品切れ費用 新聞の需要量を表す確率変数 分布関数 新聞１刊が売れ残ったときの在庫費用 新聞１刊が品切れしたときの品切れ費用 新聞の需要量を表す確率変数 分布関数 最適発注量 s* 分布の仮定なし！ （正規分布でないといけないという誤解が多い）

非定常モデル（需要過程）

非定常モデル（予測，発注量） 指数平滑法による予測 発注量 リード時間

非定常モデル（安全在庫量） 在庫量 標準偏差 安全在庫係数 安全在庫量

STD[I] L

エシェロン（梯形）在庫

エシェロン（梯形）在庫 通常の在庫費用の計算 エシェロン在庫による費用計算

メタヒューリスティクス データ構造とアルゴリズム（メタヒューリスティクスの選択よりもこれが大事！） 類似の問題に対する過去の研究（全く新しい問題というのはそんなにはない！過去の研究を調べることは研究者としての最低のマナー！）

メタヒューリスティクスのコツ メタヒューリスティクスの数理 （共立出版 to appear）参照 グラフ分割：Tabu Search+戦略的振動 最大安定集合（最大クリーク）：平坦探索 グラフ彩色：Fixed-K Tabu Search (+Genetic Algorithm) 巡回セールスマン：k-opt, Lin-Kernighan opt（近傍の制限がミソ） 多制約ナップサック：戦略的振動+critical event Tabu Search or MIPベースメタヒューリスティクス 2次割当：Tabu Search or Ant Colony (差分の計算がミソ） 数分割：差分法