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

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

正解の理由

解法ステップ

1. 図に基づき、スタートからゴールまでの到達可能な全経路の所要日数を列挙する。
   • A＝5、B＝3、C＝5、D＝10（短縮前）、E＝5、F＝12、G＝3、H＝6、ダミー＝0
2. 各経路の合計を計算して、最長（クリティカル）経路を見つける。
3. D を 6日に短縮した場合に、該当経路の所要日数がどう変わるかを再計算する。
4. 再計算後の全経路の最大値を取り、短縮前との差を求める。

• 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$ ← 短縮前の最長経路

• A → C → D(6) → E → G = $24$
• A → C → D(6) → E →（ダミー）→ H = $27$

選択肢別の誤答解説

• ア: 1日
  D を 4日短縮したのに全体が 1日しか短縮されないとするのは、他の経路との比較をしていない誤りです。実際には別経路（A→C→F→H）が 28日で残るため、短縮量は 3日になります。
• イ: 2日
  同様に、D の短縮分（4日）と他経路（28日）との関係を誤認しています。短縮後の最長は 28日で、差は 3日です。
• ウ: 3日
  正しい。上で示した通り、短縮前の最長 31日が短縮後に 28日になり、差は 3日です。
• エ: 4日
  D 自体は 4日短縮されますが、プロジェクト全体が必ず同じだけ短縮されるわけではありません。別の経路がボトルネックになり得るため、全体短縮は 3日にとどまります。

よくある誤解

• 「ある作業を4日短縮したから全体も4日短縮される」
  → 個別作業の短縮幅とプロジェクト全体の短縮幅は一致しない。別経路が新たなクリティカルパスになる場合、全体短縮はそれより小さくなることがある。
• ダミー作業を見落とす／無視する
  → ダミーは所要日数 0 でも経路をつなぐため、経路の成立に影響する。ダミー経路を含む合成経路を正しく列挙する必要がある。

補足コラム

• クリティカルパス管理のポイント：プロジェクト短縮（クラッシング）では、各作業の短縮コストと「どれだけ全体に効くか（＝クリティカルかどうか）」を両方評価する必要があります。D のように最初はクリティカルだった作業を短縮しても、別経路が残るとそこで効果が頭打ちになります。
• 閾値（しきい値）の視点：本問では D の値が 7 日のとき A→C→D→E→（ダミー）→H と A→C→F→H が同じ 28 日になります。D を 7 日より小さくしても最終的な所要日は変わらず 28 日のままです（限界効果）。