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

2 つの倉庫 $P_1,P_2$ から 3 つの店舗 $Q_1,Q_2,Q_3$ へ、ある商品を輸送する。各倉庫の在庫量（送り出せる量の上限）は $P_1$ が $40$、$P_2$ が $50$ である。各店舗の需要量は $Q_1$ が $20$、$Q_2$ が $30$、$Q_3$ が $25$ で、需要はちょうど満たさなければならない。商品 1 単位あたりの輸送費（千円）は次の表のとおりである。

$$\begin{array}{cccc}& Q_1& Q_2& Q_3\\ P_1& 4& 6& 3\\ P_2& 5& 2& 7\end{array}$$

在庫量の合計と需要量の合計を比べ、供給が余る場合は輸送費 $0$ のダミーの店舗 $Q_4$ を表のいちばん右の列に加えて需給を釣り合わせる（$Q_4$ へ送る量は倉庫に残る量を表す）。このように釣り合わせた輸送表に北西隅法を用いて初期の実行可能解を作るとき、その解の総輸送費（千円）を求めよ。

2 つの倉庫 $P_1,P_2$ から 3 つの営業所 $Q_1,Q_2,Q_3$ へ、ある部品を輸送する。各倉庫から出荷できる量（上限）は $P_1$ が $50$、$P_2$ が $40$ であり、各営業所の需要量は $Q_1$ が $30$、$Q_2$ が $30$、$Q_3$ が $20$ である。各営業所には需要量ちょうどを届ける。部品 1 単位あたりの輸送費は次の表のとおりである。

供給量の合計と需要量の合計を比べ、余る分を受け入れるダミーの営業所 $Q_4$（各倉庫からの 1 単位あたりの輸送費は $0$）を表の右端の列として加えて需給を釣り合わせる。この表（行の順は $P_1,P_2$、列の順は $Q_1,Q_2,Q_3,Q_4$）に北西隅法を適用して初期の実行可能解を作るとき、その総輸送費を求めよ。

3 つの工場 $A_1,A_2,A_3$ から 3 つの店舗 $B_1,B_2,B_3$ へ、ある製品を輸送する。各工場の供給可能量（上限）は $A_1$ が $20$、$A_2$ が $30$、$A_3$ が $30$ であり、各店舗の需要量は $B_1$ が $15$、$B_2$ が $35$、$B_3$ が $25$ で、需要はちょうど満たさなければならない（工場は供給可能量をすべて出荷しなくてもよい）。製品 1 単位あたりの輸送費は次の表のとおりである。

工場 $A_i$ から店舗 $B_j$ への輸送量 $x_{ij}$ は $0$ 以上の実数とする。総輸送費 $\sum _{i=1}^3\sum _{j=1}^3{c}_{ij}{x}_{ij}$ の最小値を求めよ（$c_{ij}$ は表の輸送費）。

2 つの農場 $A_1,A_2$ から 3 つの市場 $B_1,B_2,B_3$ へ野菜を輸送する。農場の出荷量は $A_1$ が $30$ トン、$A_2$ が $20$ トンで、すべて出荷する。市場の需要量は $B_1$ が $15$ トン、$B_2$ が $25$ トン、$B_3$ が $10$ トンで、ちょうど満たす。$1$ トンあたりの輸送費（単位: 千円）は次の表のとおりである。

$$\begin{array}{cccc}& B_1& B_2& B_3\\ A_1& 4& 6& 8\\ A_2& 5& 3& 7\end{array}$$

輸送量は $0$ 以上の実数とし、総輸送費は各経路の「輸送量 $\times$ 単価」の和とする。北西隅法で初期の実行可能解を作り、ポテンシャル法で最適性を判定・改善して、総輸送費の最小値（単位: 千円）を求めよ。

2 つの農場 $P_1,P_2$ から 3 つの市場 $Q_1,Q_2,Q_3$ へ野菜を輸送する。出荷量は $P_1$ が $50$ トン、$P_2$ が $40$ トンで、すべて出荷する。需要量は $Q_1$ が $30$ トン、$Q_2$ が $35$ トン、$Q_3$ が $25$ トンで、ちょうど満たす。$1$ トンあたりの輸送費（単位：千円）は次の表のとおりである。
$$\begin{array}{ccccc}& Q_1& Q_2& Q_3& \text{出荷量}\\ P_1& 4& 6& 3& 50\\ P_2& 6& 5& 4& 40\\ \text{需要量}& 30& 35& 25& \end{array}$$
各輸送量は $0$ 以上の実数とし、輸送費は輸送量に比例するものとする。北西隅法で初期の実行可能解を作り、ポテンシャル法で最適性の判定と改善を行って、総輸送費の最小値（千円）を求めよ。