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

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$ が $30$、$A_2$ が $40$、$A_3$ が $20$ であり、各工場は供給量をすべて出荷する。各店舗の需要量は $B_1$ が $35$、$B_2$ が $40$、$B_3$ が $35$ であり、各店舗へは需要量を超えて輸送しない。工場 $A_i$ から店舗 $B_j$ へ製品 $1$ 単位を輸送する費用は次の表のとおりである。

総供給量が総需要量より少ないため、需要を満たせない店舗が出る。店舗 $B_1,B_2,B_3$ で不足する製品 $1$ 単位あたり、それぞれ $12$, $10$, $9$ の不足費用がかかる。輸送量は $0$ 以上の実数とする。輸送費用と不足費用の合計の最小値を求めよ。

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$ とした輸送表に北西隅法を用いて初期の実行可能解を作るとき、その総輸送費を求めよ。

あるプロジェクトは作業 $A,B,C,D,E,F,G,H,I$ の $9$ つからなる。各作業の所要日数と先行作業（その作業を始める前にすべて終わっていなければならない作業）は次のとおりである。

プロジェクトは時刻 $0$ に始まり、各作業は先行作業がすべて終わればすぐに始められ、同時に進められる作業の数に制限はないものとする。

この計画どおりのときのプロジェクトの最短完了日数を $T_1$ とする。次に、作業 $B$ は時刻 $3$ より前には始められず、さらに作業 $F$ の所要日数が $9$ 日に増えたとする（ほかの条件は変わらない）。このときのプロジェクトの最短完了日数を $T_2$ とする。$T_1,T_2$ をこの順に求めよ。