基本情報技術者 2009年 秋期 午前（科目A） 問51

プロジェクトの最短日数（クリティカルパス）【午前2 解説】

要点まとめ

• 結論：このネットワークの最短完了日数は31日で、最長経路（クリティカルパス）は A → B → G → （ダミー） → D → I に相当します（合計31日）。
• 根拠：イベントの最早時刻を順に計算すると，C に到達する最早時刻が20日，D 開始が20日，D(6日)+I(5日)で終了が31日となるためです。
• 差がつくポイント：ダミー作業（破線）は時間ゼロでも依存関係を作るため，見落とすと最早時刻やクリティカルパスが変わって誤答になります。

正解の理由

• 開始 → A = 3日 → A到達イベント t1 = 3日
• t1 → B = 6日 で Bイベント候補は 3+6 = 9日（ただし E→B のダミーで調整されても9日）
• B（9日） → G = 11日 で F到達イベントは 9+11 = 20日（A→F の14日では17日であり，G経由の20日が支配）
• F到達（20日）→（ダミー）→ Cイベント は 0日で到達時刻20日（C を B→C(8日) だけで計算すると 17日になるが，ダミーの到着が遅いため Cイベントは20日になる）
• Cイベント（20日）→ D = 6日 → D完了 26日 → I = 5日 → 終了 31日

よくある誤解

• 破線（ダミー）を「作業なし」として無視すると，CやDの開始時刻を早く見積もってしまい誤答になります。
• F に直接つながる経路（14日）だけ見て最長経路だと誤認しがちで，実際は B→G→F の経路が遅延要因になります。

解法ステップ

1. 開始イベントを時刻0として，A を実行して A到達イベントの最早時刻を求める（0+3=3）。
2. A到達から分岐する各作業（B,E,F）の最早到達時刻を計算する（B:3+6=9、E:3+5=8、F:3+14=17）。
3. ダミー（E→B）は0日だが依存関係を課すため，Bイベントは max(9, E到着8)＝9 のまま。
4. B からの出力（C,H,G）それぞれの到達時刻を計算（C:9+8=17、H:9+15=24、G:9+11=20）。
5. F 到達は A→F の17 と B→G→F の20 のうち大きい方（20）を採る。
6. F→C のダミーにより Cイベントは max(17（B→C） , 20（Fダミー）)=20 となる。
7. C→D(6)→I(5) を順に足すと終了は 20+6+5 = 31 日。これがプロジェクト全体の最短日数（クリティカルパス）です。

選択肢別の誤答解説

• ア: 27
  • よくある誤りは I（5日）や D（6日）を一部抜かしたり，ダミーの影響を逆に扱って短く見積もることです。正しく計算するともっと大きくなります。
• イ: 28
  • A→B→C→D→I の単純な経路合計（3+6+8+6+5）は28日ですが，F経由のダミー到着（20日）が C イベントを遅らせるため実際は28日より長くなります。
• ウ: 29
  • 29日は特定の経路の誤った部分和（例えば A→F の17日と D/I の合計計算ミス）から生じる数値ですが，ダミーと B→G の影響を正しく考慮すると成立しません。
• エ: 31（正解）
  • B→G→F の遅れ（20日）が C イベントを支配し，そのまま D(6)＋I(5) が続くため合計31日になります。

補足コラム

• AOA（アクティビティ・オン・アロー）表記では，破線のダミーは長さ0だが依存関係を表す重要な要素です。ダミーを無視するとクリティカルパス解析で誤った最早時刻が出ます。
• クリティカルパス法（CPM）は最早開始（ES）・最遅開始（LS）を求め，余裕（フロート）が0の経路がクリティカルパスです。本問は最早時刻だけで最長経路を見つければ答えが出ます。
• PERT と CPM の違い：PERT は確率論的に所要時間を扱うのに対し，CPM は固定時間での最長経路解析が中心です。本問は固定時間の CPM に相当します。

FAQ