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

最遅開始時刻【午前2解説】

正解の理由

解法ステップ

1. ネットワークをノード単位で前方（最早）計算する。各アクティビティの最早開始（ES）＝所属ノードの最早時刻、最早終了（EF）＝ES＋所要日数。次ノードの最早時刻はそのノードへ入る活動の EF の最大値。
   • ノード1（開始）: 時刻 $0$。
   • A (1→2, 8): ES=0, EF=8 → ノード2最早=8
   • B (1→3, 5): ES=0, EF=5 → ノード3最早=5
   • C (1→5, 12): ES=0, EF=12 → ノード5最早=12
   • D (2→4,10): ES=8, EF=18 → ノード4候補=18
   • E (3→4,9): ES=5, EF=14 → ノード4候補=14
   • ダミー (5→4,0): EF=12 → ノード4候補=12 → ノード4最早 = max(18,14,12) = 18
   • G (4→7,12): ES=18, EF=30 → ノード7候補=30
   • F (2→7,8): ES=8, EF=16 → ノード7候補=16
   • H (5→6,5): ES=12, EF=17 → ノード6最早=17
   • I (6→7,4): ES=17, EF=21 → ノード7候補=21 → ノード7最早 = max(30,16,21) = 30
   • よってプロジェクトの最短所要日数 = 30 日（クリティカルパスは 1→2→4→7）。
2. 後方（最遅）計算を行う。終点ノードの最遅終了（LF）はプロジェクト所要日数に等しい（ここでは 30）。各アクティビティの最遅開始（LS）＝LS（終点ノード）＝LF−所要日数。始点ノードの最遅時刻は各出口の LS の最小値。
   • ノード7 LF = 30
   • 各終端活動の LS:
     • G (4→7,12): LS_G = 30−12 = 18 → ノード4 LF ≤ 18
     • F (2→7,8): LS_F = 30−8 = 22 → ノード2 LF ≤ 22
     • I (6→7,4): LS_I = 30−4 = 26 → ノード6 LF ≤ 26
   • ノード4 LF = 18（Gだけが制約）
   • D (2→4,10): LS_D = 18−10 = 8 → ノード2 LF ≤ 8（ただしノード2は他の出口との最小をとる）
   • E (3→4,9): LS_E = 18−9 = 9 → ノード3 LF = 9
   • ノード2 の出口 LS は D が 8、F が 22 → ノード2 LF = min(8,22) = 8
   • ノード6 LF = 26（I により）
   • H (5→6,5): LS_H = 26−5 = 21 → ノード5 LF ≤ 21
   • C (1→5,12): LS_C = ノード5 LF −12 = 21−12 = 9 → ノード1 LF の候補
   • 最終的に H の最遅開始は LS_H = 21
3. 作業 H を遅くとも開始しなければならない時刻は LS_H = 21 日であるため、選択肢は エ（21）。

選択肢別の誤答解説

• ア: 12
  誤りの典型は「作業 C の最早終了（12）」と混同して H の最遅開始とすることです。12 は作業 H の最早開始（ES_H）であり、これは“最も早く開始できる時刻”であって“遅くとも開始しなければならない時刻”ではありません。
• イ: 14
  どこかの途中ノードの最早／最遅時刻の差を誤って採用した値です。ネットワーク全体の後方計算を行わず局所的に計算すると出やすい誤答です。
• ウ: 18
  これはノード4 の最遅開始（LS_G が 18）と混同した結果生じる誤りです。H はノード5→6 にある活動であり、ノード4 に依存する G の時刻とは別に扱う必要があります。
• エ: 21（正答）
  前方・後方両方の計算により作業 H の最遅開始が $21$ 日であることが示されます。すなわち H はプロジェクト開始から遅くとも 21 日後に開始しなければ最短で終了できません。

よくある誤解

• 最早開始（ES）と最遅開始（LS）を混同する
  ES は「いつから始められるか」、LS は「遅くともいつまでに始めないと遅延するか」。両者は別の値であるため混同に注意。
• ダミー矢印を無視する
  ダミーは所要日数ゼロでも依存関係を表す重要要素で、ノードの最早時刻や最遅時刻に影響するため省略してはいけません。
• クリティカルパス長＝ある作業の最遅開始とは限らない
  クリティカルパス上の作業なら LS＝ES となるが、Hはクリティカルでないため LS はプロジェクト全体の所要日数から逆算する必要がある。

補足コラム

• ネットワーク図の表現には AOA（矢印表現）と AON（ノード表現）があります。本問題は AOA 形式で、ダミー矢印（所要日数 0）が使われています。ダミーは同じノード（AON）なら不要ですが、AOA では依存関係を表現するためにしばしば必要です。
• クリティカルパス法（CPM）の手順は「前方計算で最短所要日数と各ノードの最早時刻を得る → 後方計算で各ノードの最遅時刻を求める → 活動の余裕（スラック）を算出してクリティカル活動を特定する」です。

FAQ