応用情報技術者 2017年 春期 午前2 問52

余裕日数の算出【午前2解説】

正解の理由

解法ステップ

1. 図をイベント（ノード）と作業（矢印）に対応させる。ダミー矢印は所要日数0の作業として扱う。
   • イベント番号（説明用）: 0=start, 1=中央上, 2=左下, 3=最上, 4=中央やや右下, 5=右中央, 6=end
   • 作業（所要日数）：A(0→1:5), B(0→2:10), dummy(2→1:0), C(1→3:20), D(1→5:30), E(1→4:10), F(2→4:10), G(3→5:20), dummy(4→5:0), H(5→6:10)
2. 前進計算（Earliest event times, 最早発生時刻 Ei）を求める。各イベント Ei = max(先行イベントのEi + 先行作業の所要日数)
   • E0 = 0（開始）
   • E2 = E0 + 10 = 10（B）
   • E1 = max(E0 + 5, E2 + 0) = max(5, 10) = 10（A とダミー）
   • E3 = E1 + 20 = 30（C）
   • E4 = max(E1 + 10, E2 + 10) = max(20, 20) = 20（E, F）
   • E5 = max(E1 + 30, E3 + 20) = max(40, 50) = 50（D, G）
   • E6 = E5 + 10 = 60（H）
     → プロジェクト工期 = 60日
3. 後退計算（Latest event times, Li）を求める。L6 = 60、逆順に Li = min(後続イベントのLj - 該当作業日数)
   • L6 = 60
   • L5 = L6 - 10 = 50（H）
   • L3 = L5 - 20 = 30（G）
   • L4 = L5 - 0 = 50（ダミー4→5）
   • L1 = min(L3 - 20, L5 - 30, L4 - 10) = min(10, 20, 40) = 10（C,D,E）
   • L2 = min(L1 - 0, L4 - 10) = min(10, 40) = 10（ダミー, F）
   • L0 = min(L1 - 5, L2 - 10) = min(5, 0) = 0
4. 各作業の最早開始（ES = 起点イベントのEi）、最遅開始（LS = 終点イベントのLj − 所要日数）、余裕日数（Float = LS − ES または Lj − d − Ei）を計算する。
   • A: ES=0, LS=10−5=5, Float=5
   • B: ES=0, LS=10−10=0, Float=0
   • C: ES=10, LS=30−20=10, Float=0
   • D: ES=10, LS=50−30=20, Float=10
   • E: ES=10, LS=50−10=40, Float=40−10=30 ← 試験設問の対象
   • F: ES=10, LS=50−10=40, Float=30
   • G: ES=30, LS=50−20=30, Float=0
   • H: ES=50, LS=60−10=50, Float=0

選択肢別の誤答解説

• ア: 「作業Cを最も早く開始できるのは5日目である。」
  実際は作業Cの最早開始はイベント1のEi = 10日です。出発ノード（イベント1）はダミー経由でB終了（10日）の制約も受けるため、5日では開始できません。よって誤り。
• イ: 「作業Dはクリティカルパス上の作業である。」
  クリティカルパス上の作業は余裕日数が0の作業です。作業Dの余裕は10日（LS=20, ES=10）なのでクリティカルではありません。誤り。
• ウ: 「作業Eの余裕日数は30日である。」
  前述のように作業EはES=10、LS=40（=L4 − 10）で、余裕は30日です。正しい。
• エ: 「作業Fを最も遅く開始できるのは10日目である。」
  作業Fの最早開始は10日ですが、最遅開始はL4 − 10 = 40日です（余裕30日）。「最も遅く開始できるのは10日目」は誤り。

よくある誤解

1. ダミー矢印を無視する：ダミーは所要日数0でも依存関係を作るため、最早／最遅時刻に影響します（本問ではB→1のダミーによりイベント1の最早が10日になる）。
2. イベントの「最遅時刻」と活動の「最遅開始」を混同する：活動の最遅開始は終点イベントの最遅時刻 − 活動所要日数で求める（必ずしも起点イベントの最遅時刻と等しくない）。
3. クリティカル判定を「経路長の長さ」だけで行う：余裕が0かどうか（または始点・終点イベントの最早=最遅）で判断する。

補足コラム

• 本問はAOA（アローダイアグラム）形式の典型問題です。手順は常に「前進→プロジェクト期間算出→後退→フロート計算」。時間配分が厳しい試験では、イベント時刻だけ表にして前進・後退を行うとミスが減ります。
• 速算チェック：プロジェクト全体の工期 = 最長経路（本問は B → C → G → H = 10+20+20+10 = 60）。クリティカルパスはこの最長経路上の作業（余裕0）。

# イベントと作業の定義（start=0,...,end=6）
edges = {(0,1):5,(0,2):10,(2,1):0,(1,3):20,(1,5):30,(1,4):10,(2,4):10,(3,5):20,(4,5):0,(5,6):10}
# 前進・後退を手で計算すると上記の値になります（説明参照）

FAQ