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

3 つの工場 $A_1,A_2,A_3$ から 3 つの販売店 $B_1,B_2,B_3$ へ、ある製品を輸送する。各工場の生産量は $A_1$ が $25$、$A_2$ が $35$、$A_3$ が $40$ で、すべて輸送しなければならない。各販売店の需要量は $B_1$ が $30$、$B_2$ が $45$、$B_3$ が $25$ で、ちょうど需要量を受け取らなければならない。製品 $1$ 単位あたりの輸送費用は次の表のとおりである。ただし、$A_3$ から $B_1$ への輸送費用 $t$ だけは未定であり、$t$ は $t\ge 0$ を満たす実数とする。

輸送量は $0$ 以上の実数とし、総輸送費用の最小値を $f(t)$ とする。「すべての $t^{\prime }\ge t$ について $f(t^{\prime })=f(t)$ が成り立つ」ような $t(\ge 0)$ の最小値 $t_0$ を求めよ。

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}$ は表の輸送費）。

3 つの倉庫 $A_1,A_2,A_3$ から 4 つの店舗 $B_1,B_2,B_3,B_4$ へ、ある商品を輸送する。倉庫の在庫量は $A_1$ が $30$、$A_2$ が $40$、$A_3$ が $30$ であり、在庫はすべて出荷する。店舗の需要量は $B_1$ が $20$、$B_2$ が $30$、$B_3$ が $25$、$B_4$ が $25$ であり、需要はちょうど満たす（総在庫量と総需要量はともに $100$ で等しい）。倉庫 $A_i$ から店舗 $B_j$ へ $1$ 単位輸送する費用 $c_{ij}$ は次の表のとおりである。

ただし、経路 $A_3\to B_4$ は輸送能力に制限があり、この経路で輸送できる量は $10$ 以下である。ほかの経路には輸送量の上限はない。$A_i$ から $B_j$ への輸送量 $x_{ij}$ は $0$ 以上の実数とし、総輸送費用 $\sum _{i=1}^3\sum _{j=1}^4{c}_{ij}{x}_{ij}$ を最小にする。総輸送費用の最小値を求めよ。

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

需給を釣り合わせるため、輸送費がすべて $0$ のダミーの店舗 $Q_4$ を表の最も右の列に加える。行の順を $P_1,P_2$、列の順を $Q_1,Q_2,Q_3,Q_4$ とした輸送表に北西隅法を用いて初期の実行可能解を作るとき、その総輸送費を求めよ。

頂点 $1,2,\dots ,7$ からなる有向グラフがあり、各有向辺 $i\to j$ の長さ（正の整数）は次のとおりである。ここに書かれていない辺はない。

経路の長さを、通る辺の長さの和と定める。頂点 $1$ から頂点 $7$ への最短路の長さを $L$、長さがちょうど $L$ である頂点 $1$ から頂点 $7$ への経路の本数を $N$ とするとき、組 $(L,N)$ を求めよ。