はじめに

数理最適化を初めて学ぶ勉強資料の2回目です。
1回目は以下からご覧下さい。

[第1回] 最適化とは？ - 数理最適化を学ぶ勉強資料
https://qiita.com/ttlabo/private/e6970c6e85cce9ff4e34

典型問題とは

数理最適化問題として様々な問題が考えられますが、数理最適化においては、一般に典型問題(または標準問題)と呼ばれるいわゆる教科書のような問題または代表的な問題を分類し、それをまとめたものがあります。
これらを典型問題(または標準問題)と呼びます。

参考テキストでは、7クラス24問題に分けて説明されています。

グラフ・ネットワーク問題クラス
　・最小全域木問題
　・最大安定集合問題
　・最大カット問題
　・最短路問題
　・最大流問題
　・最小費用流問題

経路問題クラス
　・運搬経路(配送最適化)問題
　・巡回セールスマン問題
　・中国人郵便配達問題

集合被覆・分割問題クラス
　・集合被覆問題
　・集合分割問題
　・組合せオークション問題

スケジューリング問題クラス
　・ジョブショップ問題
　・勤務スケジューリング問題

切り出し・詰め込み問題クラス
　・ナップサック問題
　・ピンパッキング問題
　・n次元パッキング問題

配置問題クラス
　・施設配置問題
　・容量制約なし施設配置問題

割当・マッチング問題クラス
　・2次割当問題
　・一般化割当問題
　・最大マッチング問題
　・重みマッチング問題
　・安定マッチング問題

上記の分類分けのうち、いくつかを具体的に説明します。

ロジスティクス・ネットワーク設計問題
工場や倉庫などの拠点の配置/削減、生産ライン能力、生産量、在庫量、輸送量などを決定する問題。物流最適化問題の中で最も費用対効果が大きい。
輸送量だけに着目すると輸送最適化問題となる。

配送最適化(運搬経路)問題
複数のオーダーを複数の車両(ビークル)を使って配送する問題。オーダーとは、決められた荷物を配送元から配送先へ運ぶオペレーション。オーダーには、配送元の出荷可能時間帯や配送先に入庫可能時間帯などの制約条件が付く場合もある。難しい問題のため、近似解で解かれることが多い。

船舶スケジューリング問題
車両の代わりに船舶を用いた配送最適化問題。入港制限など海上独特の制約もあるが、構造としては配送最適化問題と同じ。

クルースケジューリング問題(勤務スケジューリング問題)
トラック、鉄道、航空機などの乗務員のスケジュールやアルバイト・パート、看護師の勤務シフトを求める問題。

最小費用流問題
各時刻の需要を満たすように、船舶や車両を用いて物資が余っているところから不足しているところへ最小の費用で運ぶ問題。使用済みのレンタカーや空きパレットなどを需要地に戻す問題等。

安全在庫問題
需要のばらつきに備えて、在庫費用と品切れリスクのバランスを取る問題。調達先を複数にして災害などを考慮するようなモデルもある。

ロットサイズ決定問題
段取り費用が発生するなど、製品をまとめて作成すると効率が良い場合に、在庫費用とトレードオフでどれだけまとめて作るかを決定する問題。

ジョブショップ問題(フローショップ問題)
ジョブを機械に割り当てる問題。処理順序が決まっている場合は、フローショップ問題という。

パッキング問題
コンテナなどの入れ物に荷物を効率よく詰め込む問題。切り出し(カッティング=資源の分割)と詰め込み問題(パッキング=入れ物に荷物を詰める)は表裏一体であり、問題としては同じ。

収益管理問題
時間経過により陳腐化する商品に対し、価格を操作し(上げて)収益を最大化する問題。航空運賃やホテルの宿泊費など。

最適化問題に取り組むには、これらの典型問題を知り、それぞれの特徴や解法を応用することで、手元の問題をより的確に解決することができます。

終わりに

次回は第3回目、いよいよPythonで最適化問題の例題を解いていきます。
引き続きお読み頂けたら幸いです。

当記事については、著者も最適化の入門者です。誤解・誤植等至る所にあると思いますので、お気軽にご意見やご指摘などお寄せ下さい。

出典

本記事では、数理最適化モデルについて参考テキスト「Pythonによる問題解決シリーズ　データ分析ライブラリーを用いた最適化モデルの作り方」を情報元にしています。テキストの詳細は以下です。

■参考テキスト
「Pythonによる問題解決シリーズ　データ分析ライブラリーを用いた最適化モデルの作り方」
　斉藤努[著] ／近代科学社[出版]