輸送問題とそのバリエーション

transportation problem(輸送問題)

\begin{aligned} &\text{minimize} && \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} \\ &\text{subject to} && \sum_{j=1}^{n} x_{ij}= S_i \\ & && \sum_{i=1}^{n} x_{ij}= D_j \\ & && x_{ij} \geq 0 \end{aligned}

fixed charge transportation problem(FCTP)

\begin{aligned} &\text{minimize} && \sum_{i=1}^{m} \sum_{j=1}^{n} (c_{ij} x_{ij} + d_{ij} y_{ij}) \\ &\text{subject to} && \sum_{j=1}^{n} x_{ij}= S_i \\ & && \sum_{i=1}^{m} x_{ij}= D_j \\ & && y_{ij} = 1 \ \text{if} \ x_{ij} \gt 0 \\ & && y_{ij} = 0 \ \text{if} \ x_{ij} = 0 \\ & && x_{ij} \geq 0 \end{aligned}

fixed charge transportation problemは輸送問題に加えて枝に固定のコストが追加されたものです.
枝(i, j)を使うと流量 {x_{ij}}に関係なく {d_{ij}}が固定コストとしてかかります.

pure fixed charge transportation problem(PFCTP)

\begin{aligned} &\text{minimize} && \sum_{i=1}^{m} \sum_{j=1}^{n} d_{ij} y_{ij} \\ &\text{subject to} && \sum_{j=1}^{n} x_{ij}= S_i \\ & && \sum_{i=1}^{m} x_{ij}= D_j \\ & && y_{ij} = 1 \ \text{if} \ x_{ij} \gt 0 \\ & && y_{ij} = 0 \ \text{if} \ x_{ij} = 0 \\ & && x_{ij} \geq 0 \end{aligned}

pure fixed charge transportation problemはfixed charge transportation problemから流量にかかるコストが取り除かれたものです.
プログラミングコンテストチャレンジブックの最小費用流のコラムに,「流量×コストの和を最小化ではなく、流量が正である辺のコストの和を最小化したい場合」とありますが,たぶんこの問題です(正確にはこの問題に容量制約がついたもの).

pure constant fixed charge transportation problem(PC-FCTP)

\begin{aligned} &\text{minimize} && \sum_{i=1}^{m} \sum_{j=1}^{n} d y_{ij} \\ &\text{subject to} && \sum_{j=1}^{n} x_{ij}= S_i \\ & && \sum_{i=1}^{m} x_{ij}= D_j \\ & && y_{ij} = 1 \ \text{if} \ x_{ij} \gt 0 \\ & && y_{ij} = 0 \ \text{if} \ x_{ij} = 0 \\ & && x_{ij} \geq 0 \end{aligned}

pure constant fixed charge transportation problemはpure fixed charge transportation problemの固定コストがすべて同じ値のものです.
 {d}を1とすれば,SupplyからDemandにものを送る際に使う枝の数を最小化する問題になります.

PC-FCTPをPulpで解く

PC-FCTPはNP-Hardなのですが,小規模なら厳密解が求められます.
試しにpulpで解いてみます.

結果

Status: Optimal
Total Cost:13.0
Assignment:
Left:0 -> Right:7(8.0)
Left:1 -> Right:8(6.0)
Left:2 -> Right:3(7.0)
Left:3 -> Right:4(10.0)
Left:3 -> Right:7(1.0)
Left:4 -> Right:0(11.0)
Left:5 -> Right:6(13.0)
Left:6 -> Right:8(6.0)
Left:7 -> Right:6(13.0)
Left:8 -> Right:5(11.0)
Left:8 -> Right:9(9.0)
Left:9 -> Right:1(11.0)
Left:9 -> Right:2(10.0)
2sec

参考