応用情報技術者 2011年 春期 午前2 問51

結合点の最遅通過日【午前2解説】

正解の理由

解法ステップ

1. 前方計算（最早時刻 ES）で各ノードの最早到達時刻を求める（開始ノード1を0日とする）。
   • ノード1 = 0
   • ノード2 = 0 + A(8) = 8
   • ノード3 = 0 + B(5) = 5
   • ノード5 = 0 + C(12) = 12
   • ノード4 = max(ノード2 + D, ノード3 + E, ノード5 + ダミー) = max(8+10, 5+9, 12+0) = max(18,14,12) = 18
   • ノード6 = ノード5 + H = 12 + 5 = 17
   • ノード7 = max(ノード2 + F, ノード4 + G, ノード6 + I) = max(8+8, 18+12, 17+4) = max(16,30,21) = 30
   • よってプロジェクトの最短完了日 = 30日
2. 後方計算（最遅時刻 LF）をノード7 = 30 から逆算する。
   • ノード7 LF = 30
   • ノード4 LF = ノード7 LF - G = 30 - 12 = 18
   • ノード6 LF = ノード7 LF - I = 30 - 4 = 26
   • ノード2 LF = min(（ノード4 LF - D）,（ノード7 LF - F）) = min(18-10=8, 30-8=22) = 8（ただしノード2のLFは他の制約で最小が採用される）
   • ノード3 LF = ノード4 LF - E = 18 - 9 = 9
   • ノード5 LF = min(ノード4 LF - ダミー(0), ノード6 LF - H) = min(18 - 0, 26 - 5) = min(18, 21) = 18
3. ノード5の最遅通過時刻は上記より $18$ 日であり、これより遅いとノード4の開始（および結果としてノード7の終了）を遅らせ、プロジェクト全体の最短日数を延ばしてしまいます。

選択肢別の誤答解説

• ア: 12
  ノード5の「最早通過時刻」は12日ですが、これは最遅通過可能日（余裕を考慮した上限）ではありません。12日は単にノード5が最早で到達可能な日を示す値であり、これより遅くできないわけではありません（ただし限界は別途求める必要があります）。
• イ: 14
  根拠が不明瞭な数値です。どの経路の余裕とも一致せず、前方・後方計算のどちらからも導けません。
• ウ: 18（正しい）
  ノード5の後方計算での最遅時刻は min(ノード4_LF - 0, ノード6_LF - 5) = min(18,21) = 18 となり、これがノード5を遅らせられる上限です。
• エ: 21（出題側の解答表記）
  21はノード5→6→7 経路（12+5+4 = 21）を根拠に導ける数値で、もしノード5がノード4に影響を与えない（すなわちダミー矢印による制約が無い）ならばノード5の上限は21になります。しかし図にある通りノード5からノード4へのダミー矢印が存在するため、ノード5はノード4の開始を待つ必要があり、その制約がより厳しく（小さく）働いて18が上限になります。したがって図示通りのネットワーク規則に従えば21は誤りです。

よくある誤解

• ダミー矢印（破線）を無視する
  ダミーは時間はゼロでも「順序制約」を表します。無視するとノードの最遅時刻や余裕の計算を誤ります。
• 最遅時刻の計算で「最大値」を取ってしまう
  後方計算で同一ノードに複数の後続がある場合、そのノードのLFは「後続LF − 所要時間」の最小値を取ります（遅く出来る上限は最も厳しい制約による）。
• 最早時刻（ES）と最遅時刻（LF）を混同する
  ESは「最短で到達できる時刻」、LFは「遅く通ってもプロジェクトを遅らせない上限」です。用途を混ぜないこと。

補足コラム

• AOA（Activity on Arrow、矢印が作業）図ではダミーアクティビティが出てきます。ダミーは実作業ではないが論理的な前後関係を表現するために重要です。AON（Activity on Node、ノードが作業）形式ではダミーは不要で論理関係は直接ノード間で表現できます。試験では図の形式を正しく読み取ることが得点の分かれ目になります。

FAQ