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

通常時の経路と工期. 先行関係から、開始から終了までの経路は次の $3$ つである（$F$ が最後の作業で、$F$ の先行は $C,E$、$E$ の先行は $B,D$、$C,D$ の先行は $A$）。
- $A\to C\to F$: $4+5+3=12$ 日
- $A\to D\to E\to F$: $4+3+4+3=14$ 日
- $B\to E\to F$: $6+4+3=13$ 日

最早開始時刻で計算すると、$A,B$ は $0$、$C,D$ は $4$、$E$ は $\max (6,4+3)=7$、$F$ は $\max (4+5,7+4)=11$ で、完了は $14$ 日目である。工期はすべての経路の長さの最大値に等しい。

定式化. 各作業の短縮日数を $a,b,c,d,e,f$ とする。工期を $11$ 日以下にする条件は、どの経路の長さも $11$ 以下であること、すなわち
$$a+c+f\ge 1(1),a+d+e+f\ge 3(2),b+e+f\ge 2(3)$$
である。ただし $a,b,c,d,e,f$ は整数で $0\le a\le 1,0\le b\le 2,0\le c\le 2,0\le d\le 1,0\le e\le 2,0\le f\le 1$。このもとで
$$30a+20b+25c+10d+15e+40f$$
を最小化する。

場合分け.
- $f=1$ のとき（費用 $40$）: $(1)$ は成り立ち、残りは $a+d+e\ge 2$, $b+e\ge 1$。
- $e=0$: $b\ge 1$, $a=d=1$ で $40+20+30+10=100$。
- $e=1$: $a+d\ge 1$ で最も安いのは $d=1$、合計 $40+15+10=65$。
- $e=2$: 他は不要で $40+30=70$。

この場合の最小は $65$。
- $f=0$ のとき: $(1)$ $a+c\ge 1$, $(2)$ $a+d+e\ge 3$, $(3)$ $b+e\ge 2$。
- $e=0$: $a+d\ge 3$ だが $a+d\le 2$ なので不可能。
- $e=1$（費用 $15$）: $(2)$ より $a=d=1$、$(3)$ より $b\ge 1$。$(1)$ は $a=1$ で成り立つ。合計 $15+30+10+20=75$。
- $e=2$（費用 $30$）: $(3)$ は成り立ち、残りは $a+d\ge 1$, $a+c\ge 1$。$a=1$ なら両方成り立ち追加 $30$。$a=0$ なら $d\ge 1$ かつ $c\ge 1$ が必要で追加 $10+25=35$。よって最小は $30+30=60$。

以上より、最小値は $a=1,e=2$（他は $0$）のときの $30\cdot 1+15\cdot 2=60$ である。

確認. このとき所要日数は $A$ が $3$ 日、$E$ が $2$ 日となり、各経路は $A\to C\to F$: $3+5+3=11$、$A\to D\to E\to F$: $3+3+2+3=11$、$B\to E\to F$: $6+2+3=11$ で、工期はちょうど $11$ 日になる。

したがって、追加費用の合計の最小値は $60$（千円）である。

経路は 3 本ある（所要日数は通常時）: $A\to C\to F$ が $4+5+3=12$、$A\to D\to E\to F$ が $4+3+4+3=14$、$B\to E\to F$ が $6+4+3=13$。プロジェクト日数は 3 経路の最大値。

短縮日数を $s_X$ として、$11$ 日以下にする条件は
(P1) $s_A+s_C+s_F\ge 1$、(P2) $s_A+s_D+s_E+s_F\ge 3$、(P3) $s_B+s_E+s_F\ge 2$。
費用は $30s_A+20s_B+25s_C+10s_D+15s_E+40s_F$（$s_A,s_D,s_F\le 1$、$s_B,s_C,s_E\le 2$）。

場合分け（$s_E$ で）:
- $s_E=2$（費用 30）: P3 は満たされる。P2 はあと 1 日、P1 は 1 日必要。$A$ 1 日（30）で P1・P2 を同時に満たせる → 合計 60。$D$（10）+$C$（25）なら合計 65、$F$（40）なら合計 70。最小は 60。
- $s_E=1$（費用 15）: P3 に追加 1 日（$B$:20 または $F$:40）、P2 に追加 2 日が必要。$F$ を使うと 15+40 に P2 の残り 1 日 $D$(10) を加えて 65。$B$ を使うと 15+20 に P2 の 2 日（$A+D$=40 など）で 75 以上。最小 65。
- $s_E=0$: P3 のため $s_B=2$（40）または $F$ を使い、P2 の 3 日を $A,D,F$ から確保する必要があり、80 以上。

よって最小は $60$。検算: $s_A=1,s_E=2$ のとき、$A=3,C=5,F=3$ で P1 $=11$、$A=3,D=3,E=2,F=3$ で P2 $=11$、$B=6,E=2,F=3$ で P3 $=11$。すべて 11 日以下で費用 $30+30=60$。