ロットサイズ決定問題と最短路問題 その２

以前の記事でも書いたように、単純なロットサイズ決定問題は最短路問題に変換して解くことができる。



以前と同じ例であるが、ネットワーク図を作成してみたので以下に掲載する。



これも以前に計算した通りであるが、1 → 2 → 5 → 6 と進むのが最短路（つまり 1, 2, 5 日目に生産を行う)であり、最短路長（ロットサイズ決定問題のコスト）は 43 となる。

ちなみに、以下の場合のコストも上記のネットワーク図から計算してみよう。
○1 度に生産(1 期に全期分の生産を行う)　: 1 → 6 でコストは 79
○JIT 生産(毎期にその期の需要分だけ生産を行う) : 1 → 2 → 3 → 4 → 5 → 6 でコストは 56

以下は DIMACS フォーマットファイルと msp ソルバーによる実行結果（もちろん実行は一瞬で終わる）
--------------------------------------------------------------------------------
○ dimacs format graph file
c Shortest Paths : Lotsizing Problem
c
p sp 6 15
c
c
a 1 2 13
a 1 3 22
a 1 4 50
a 1 5 55
a 1 6 79
a 2 3 6
a 2 4 20
a 2 5 23
a 2 6 39
a 3 4 24
a 3 5 28
a 3 6 48
a 4 5 6
a 4 6 22
a 5 6 7

○ query ファイル
c Shortest Paths : Lotsizing Problem
c
p aux sp p2p 1
q 1 6

○実行結果
c fixed source destination solution
c -----------------------------------------------------------
c 0 1 6 43