オペレーションズ・リサーチの問題

初期解の総輸送費
$$4\cdot 30+6\cdot 20+3\cdot 15+7\cdot 25=120+120+45+175=460.$$

手順 1：ポテンシャルを求める。 基底セル $(1,1),(1,2),(2,2),(2,3)$ で $u_i+v_j=c_{ij}$ とする。未知数が 1 つ多いので $u_1=0$ とおくと
- $(1,1)$: $u_1+v_1=4$ より $v_1=4$
- $(1,2)$: $u_1+v_2=6$ より $v_2=6$
- $(2,2)$: $u_2+v_2=3$ より $u_2=-3$
- $(2,3)$: $u_2+v_3=7$ より $v_3=10$

手順 2：非基底セルの $c_{ij}-u_i-v_j$ を調べる。
- $(1,3)$: $9-0-10=-1$
- $(2,1)$: $5-(-3)-4=4$

$(1,3)$ が負なので、ここに輸送量を入れると費用が下がる。まだ最適ではない。

手順 3：閉路に沿って輸送量を移す。 $(1,3)$ から出発する閉路は $(1,3)\to (2,3)\to (2,2)\to (1,2)\to (1,3)$ で、符号は $(1,3)+,(2,3)-,(2,2)+,(1,2)-$ である。移す量 $\theta$ は $-$ のセルの輸送量の最小値で $\theta =\min (25,20)=20$。
新しい解は
$$x_{11}=30,x_{13}=20,x_{22}=35,x_{23}=5(x_{12}=0\text{ は非基底になる}).$$
行和 $30+20=50$、$35+5=40$、列和 $30,35,25$ で条件を満たす。総輸送費は
$$4\cdot 30+9\cdot 20+3\cdot 35+7\cdot 5=120+180+105+35=440$$
（$460+(-1)\cdot 20=440$ とも一致）。

手順 4：もう一度最適性を判定する。 基底セル $(1,1),(1,3),(2,2),(2,3)$ で $u_1=0$ とすると $v_1=4$, $v_3=9$, $u_2=7-9=-2$, $v_2=3-(-2)=5$。
- $(1,2)$: $6-0-5=1\ge 0$
- $(2,1)$: $5-(-2)-4=3\ge 0$

すべての非基底セルで $c_{ij}-u_i-v_j\ge 0$ なので、この解は最適である。

よって総輸送費の最小値は $440$ 万円である。

初期解の総費用は $30\cdot 4+20\cdot 6+15\cdot 3+25\cdot 7=120+120+45+175=460$ である。

基底変数は $x_{11},x_{12},x_{22},x_{23}$ である。$u_1=0$ とおき、基底変数について $u_i+v_j=c_{ij}$ を解くと $v_1=4,v_2=6,u_2=-3,v_3=10$ となる。

非基底変数の被約費用 $c_{ij}-u_i-v_j$ は次のとおり。
- $(1,3)$: $9-0-10=-1<0$
- $(2,1)$: $5+3-4=4$

$(1,3)$ が負なので最適でなく、$x_{13}$ を基底に入れる。閉路は $(1,3{)}^{+}\to (2,3{)}^{-}\to (2,2{)}^{+}\to (1,2{)}^{-}$ である。減らす側の変数は $x_{23}=25,x_{12}=20$ なので、$\theta =\min (25,20)=20$。

更新後は $x_{11}=30,x_{13}=20,x_{22}=35,x_{23}=5,x_{12}=0$ となる。総費用は $120+20\cdot 9+35\cdot 3+5\cdot 7=120+180+105+35=440$ で、$460-20\cdot 1=440$ とも一致する。

再びポテンシャルを求める。基底変数は $x_{11},x_{13},x_{22},x_{23}$ で、$u_1=0$ より $v_1=4,v_3=9,u_2=-2,v_2=5$ となる。

非基底変数の被約費用は次のとおり。
- $(1,2)$: $6-0-5=1>0$
- $(2,1)$: $5+2-4=3>0$

すべて $0$ 以上なので最適である。

検算として、供給は $P_1$: $30+20=50$、$P_2$: $35+5=40$、需要は $Q_1$: $30$、$Q_2$: $35$、$Q_3$: $20+5=25$ で、すべて条件を満たす。

最小総輸送費は $440$ 万円。