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

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

最早開始時刻を順に計算する。$A,B$ は $0$ 日目に開始できる。$C$ は $A$ の終了後なので $0+4=4$、$D$ は $B$ の終了後なので $0+6=6$。$E$ は $C,D$ の両方の終了後なので $\max (4+5,6+3)=\max (9,9)=9$。よって最短完了時刻は $9+2=11$ 日である。

最遅開始時刻を後ろから計算すると、$E$ は $11-2=9$、$C$ は $9-5=4$、$D$ は $9-3=6$、$A$ は $4-4=0$、$B$ は $6-6=0$ となり、すべての作業で最早開始時刻と一致する。したがって全余裕はすべて $0$ で、クリティカルパスは
$$A\to C\to E(4+5+2=11),B\to D\to E(6+3+2=11)$$
の $2$ 本である。ほかに経路はない。

手順2：両方のクリティカルパスを同時に 1 日短くする最も安い方法を選ぶ。

工期を $1$ 日短くするには、$2$ 本の経路をどちらも $1$ 日短くしなければならない。方法は次の $2$ 通りである。
- 共通の作業 $E$ を $1$ 日短縮：$6$ 万円
- 経路 $A\to C\to E$ で最も安い $A$（$3$ 万円）と、経路 $B\to D\to E$ で最も安い $B$（$2$ 万円）を $1$ 日ずつ短縮：$3+2=5$ 万円

安いのは $A$ と $B$ を短縮する方法で、$5$ 万円。これで工期は $10$ 日になり、$2$ 本とも $10$ 日で依然としてクリティカルである。$A$ は短縮上限 $1$ 日に達し、$B$ はあと $1$ 日短縮できる。

手順3：もう 1 日短くする。

残っている選択肢は次のとおり。
- $E$ を $1$ 日短縮：$6$ 万円
- 経路 $A\to C\to E$ では $A$ が上限に達したので $C$（$5$ 万円）、経路 $B\to D\to E$ では $B$（$2$ 万円）を短縮：$5+2=7$ 万円

安いのは $E$ の短縮で $6$ 万円。これで $2$ 本の経路はともに $9$ 日になり、目標の工期 $9$ 日が達成される。

手順4：合計する。
$$5+6=11(\text{万円})$$

（確認：$A,C,E,B,D$ の短縮日数を $a,c,e,b,d$ とすると、$a+c+e=2$、$b+d+e=2$ が必要である。$e=0$ のときの最小費用は $a=1,c=1,b=2$ の $3+5+4=12$ 万円、$e=1$ のときは $a=1,b=1$ の $3+2+6=11$ 万円なので、最小値は $11$ 万円である。）

よって、追加費用の最小値は $11$ 万円である。

プロジェクトの経路は $A\to C\to E$（$4+5+2=11$ 日）と $B\to D\to E$（$6+3+2=11$ 日）の2本で、どちらも $11$ 日なので両方とも臨界経路である。完了日数を $9$ 日にするには、両方の経路をそれぞれ $2$ 日ずつ短縮する必要がある。

短縮の方法を比べる。
- $E$ を $1$ 日短縮（$6$ 万円）すると両方の経路が $1$ 日縮む。残りの $1$ 日は、経路 $ACE$ では $A$（$3$ 万円）か $C$（$5$ 万円）、経路 $BDE$ では $B$（$2$ 万円）か $D$（$4$ 万円）で縮める。安い方を選ぶと $A$ と $B$ で $3+2=5$ 万円。合計は $6+5=11$ 万円。
- $E$ を使わない場合、経路 $ACE$ を $2$ 日縮めるには $A$ $1$ 日と $C$ $1$ 日で $3+5=8$ 万円（$C$ を $2$ 日なら $10$ 万円）。経路 $BDE$ は $B$ を $2$ 日縮めて $4$ 万円。合計は $8+4=12$ 万円。

以上より最小は $11$ 万円である。

検算：$A=3$ 日、$B=5$ 日、$E=1$ 日にすると、$ACE=3+5+1=9$、$BDE=5+3+1=9$ となり、条件を満たす。費用は $3+2+6=11$ 万円。短縮の上限（$A$:1、$B$:2、$E$:1）も超えていない。