応用情報技術者 2010年 秋期 午前2 問52

クリティカルパス短縮【午前2解説】

正解の理由

解法ステップ

1. 各作業の所要日数を整理
   A=5、B=3、C=5、D=10、E=5、F=12、G=3、H=6、ダミー＝0。
2. 「最早時刻（forward pass）」で各イベントの時間を求める（開始イベント時刻＝0）。
   • A の完了（中間イベント1） = $0+5=5$
   • B 経由（上段中間） = $5+3=8$
   • C 経由（下段中間） = $5+5=10$
   • 上段中間への D 経由 = $10+10=20$ → 上段中間の最早時刻 = $\max (8,20)=20$
   • 上段右側（E の完了） = $20+5=25$
   • 下段右側（F の完了） = $10+12=22$
   • 下段右側は上段右側からのダミー（0）も入るため最早時刻 = $\max (22,25+0)=25$
   • 最終イベントへ G 経由 = $25+3=28$
   • 最終イベントへ H 経由 = $25+6=31$
     よって元のプロジェクト所要日数は $31$ 日（最長経路は A→C→D→E→(ダミー)→H で合計 $31$）。
3. D を 6日に短縮した場合（D=6）で再計算：
   • 上段中間への D 経由 = $10+6=16$ → 上段中間 = $\max (8,16)=16$
   • 上段右側（E の完了） = $16+5=21$
   • 下段右側（F の完了） = $10+12=22$
   • 下段右側は上段右側からのダミーを受けるため最早時刻 = $\max (22,21)=22$
   • 最終イベントへ G 経由 = $21+3=24$
   • 最終イベントへ H 経由 = $22+6=28$
     よって短縮後の所要日数は $28$ 日。
4. 全体の短縮量 = $31-28=3$ 日 → 選択肢は ウ（3日）。

• A→B→E→G = $5+3+5+3=16$
• A→B→E→(ダミー)→H = $5+3+5+0+6=19$
• A→C→F→H = $5+5+12+6=28$
• A→C→D→E→G = $5+5+10+5+3=28$
• A→C→D→E→(ダミー)→H = $5+5+10+5+0+6=31$ ← 元の最長

選択肢別の誤答解説

• ア（1日）: 元の所要日数やダミーの影響を正しく計算していれば得られない値。D を 4日短縮しても他の経路との比較で 1日になる根拠はない。
• イ（2日）: 同上。D の短縮幅 4日を直接使って 2日にする理由がない（他経路との比較で生じる端数でもない）。
• ウ（3日）: 正しい。元は 31日で、D を 4日短縮しても次長の経路（A→C→F→H）が 28日なので、全体は 3日短縮。
• エ（4日）: 「D を 4日短縮したからプロジェクトも 4日短縮される」と単純に考えた誤り。別経路がボトルネックとなる場合は全体短縮はその差ではない。

よくある誤解

• ダミー矢印（所要日数 0）を無視してしまう：ダミーは順序制約を表し、最早時刻の算出に影響を与えるため無視すると誤った最長経路になる。
• 「短縮した作業だけ見れば短縮量 = 差分」と考える：全体はネットワークの最長経路同士の比較で決まるため、短縮がすべて有効になるとは限らない。
• すべての“経路和”をただ列挙して最大を取ればよいと誤解：AOA（アローダイアグラム）ではイベントの最早時刻は incoming の最大値なので、ダミーや合流の扱いを正しく反映する必要がある。

補足コラム

• この問題は CPM（Critical Path Method）の基本練習です。実務では「どの作業を短縮すれば全体が短縮されるか」を判断する際、影響範囲（どのイベントの最早/最遅時刻に影響するか）を確認します。
• 本例では D を短縮しても最終的にプロジェクトを決めるボトルネックが A→C→F→H（28日）に移行したため、D の短縮効果は 4日→実際は 3日になる、という典型的な「次長経路へ移行する」ケースです。
• 最早時刻（ES）と最遅時刻（LS）を出せば、各作業の余裕時間（フロート）が求まり、どの作業を短縮すべきかを定量的に判断できます。

FAQ