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

手順1：通常時の工期とクリティカルパスを求める。

開始から終了までの経路は次の $2$ つである。

• 経路 $A\to C\to E$：$3+4+3=10$ 日
• 経路 $B\to D\to E$：$5+2+3=10$ 日

どちらも $10$ 日なので、通常の工期は $10$ 日であり、$2$ つの経路がともにクリティカルパスである（すべての作業の全余裕が $0$）。

手順2：何日短縮すればよいか。

目標は $8$ 日なので、$10-8=2$ 日短縮する。そのためには、$2$ つのクリティカルパスをどちらも $2$ 日ずつ短くしなければならない（片方だけ短くしても、もう片方が $10$ 日のままなら工期は縮まない）。

手順3：1 日短縮するための候補とその費用を比べる。

両方の経路を同時に $1$ 日短くする方法は次の $2$ 種類である。

• 共通の作業 $E$ を $1$ 日短縮：$8$ 万円
• 経路 $A\to C\to E$ から $1$ つ（$A$ か $C$）、経路 $B\to D\to E$ から $1$ つ（$B$ か $D$）を $1$ 日ずつ短縮

1 日目： 最も安いのは $A$（$3$ 万円）と $B$（$2$ 万円）の組で、$3+2=5$ 万円。これは $E$ の $8$ 万円より安いので、$A$ と $B$ を $1$ 日ずつ短縮する。工期は $9$ 日になる。$A$ はこれで短縮上限（$1$ 日）に達する。

2 日目： $A$ はもう短縮できないので、経路 $A\to C\to E$ 側の候補は $C$（$5$ 万円）、経路 $B\to D\to E$ 側の最安は $B$（$2$ 万円、あと $1$ 日短縮できる）。組 $C,B$ の費用は $5+2=7$ 万円で、$E$ の $8$ 万円より安い。よって $C$ と $B$ を $1$ 日ずつ短縮し、工期は $8$ 日になる。

手順4：合計費用。

$$5+7=12\text{（万円）}$$

（確認：$E$ を $1$ 日使う場合は、$E$ の $8$ 万円に加えて残り $1$ 日を $A,B$ で $3+2=5$ 万円となり、合計 $13$ 万円で $12$ 万円より高い。）

短縮後の所要日数は $A:2,B:3,C:3,D:2,E:3$ で、経路 $A\to C\to E$ は $2+3+3=8$ 日、経路 $B\to D\to E$ は $3+2+3=8$ 日となり、工期は $8$ 日である。

したがって、追加費用の最小値は $12$ 万円である。

通常の所要日数でのクリティカルパスを調べる。経路 $A\to C\to E$ は $3+4+3=10$ 日、経路 $B\to D\to E$ は $5+2+3=10$ 日で、どちらも $10$ 日である。完了を $8$ 日にするには、両方の経路をそれぞれ $2$ 日以上短縮しなければならない。

短縮の方法を場合分けする。

(1) $E$ を短縮しない場合（経路ごとに独立に考える）
- 経路 $A\to C\to E$ を $2$ 日短縮する。単価の安い順に $A$ を $1$ 日（$3$ 万円）、$C$ を $1$ 日（$5$ 万円）とすると $8$ 万円。$C$ を $2$ 日だと $10$ 万円なので、最小は $8$ 万円。
- 経路 $B\to D\to E$ を $2$ 日短縮する。$B$ を $2$ 日（$2\times 2=4$ 万円）が最安で $4$ 万円。
- 合計は $8+4=12$ 万円。

(2) $E$ を $1$ 日短縮する場合
- $E$ の短縮は両方の経路を同時に $1$ 日縮める。費用は $8$ 万円。
- 残りの各経路をあと $1$ 日ずつ短縮する。最安は $A$ が $3$ 万円、$B$ が $2$ 万円で、合計 $8+3+2=13$ 万円。

(1)(2) より最小は $12$ 万円である。

検算として、$A$ を $1$ 日、$C$ を $1$ 日、$B$ を $2$ 日短縮すると、$A=2$、$C=3$、$B=3$ となる。経路 $A\to C\to E$ は $2+3+3=8$ 日、経路 $B\to D\to E$ は $3+2+3=8$ 日で、条件を満たす。費用は $3+5+4=12$ 万円。