基本情報技術者 2023年 科目A 問13

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

正解の理由

解法ステップ

1. ネットワーク図で各経路の所要日数を合計する。
   • A→B→E→G = 4 + 6 + 5 + 5 = 20日
   • A→C→G = 4 + 8 + 5 = 17日
   • A→D→F→G = 4 + 4 + 4 + 5 = 17日
2. 最長経路（クリティカルパス）を特定する（ここでは A→B→E→G）。
3. クリティカルパス上で1日短縮できる作業を候補にし、費用増加率を比較する。
4. 最低の費用増加率を持つ作業を短縮する（E の 2.5 が最小）。

選択肢別の誤答解説

• ア: B
  • B はクリティカルパス上にあるが、費用増加率は 6 と高く、E（2.5）よりコストが大きい。したがって最小費用にはならない。
• イ: C
  • C はクリティカルパス上にはない（A→C→G の経路は 17日）。C を短縮してもプロジェクト全体の最長経路は変わらず、遅れは解消されない。
• ウ: D
  • D も非クリティカル（経路は 17日）。短縮しても全体所要日は短くならない。
• エ: E
  • クリティカルパス上で費用増加率が最小（2.5）。1日短縮する際の増加費用が最も少なく済むため最適。

よくある誤解

• 非クリティカルな作業を短縮すれば遅れが解消されると考える誤り。非クリティカル経路は既に余裕（スラック）があるため、短縮しても最長経路が変わらなければ意味がない。
• 遅れのある作業（ここでは A）だけを短縮すればよいと単純に思う誤解。A を短縮できれば効果はあるが、費用が最も安い作業を選ぶのがコスト最小化の基本。
• 単位当たり費用（費用増加率）と総費用を混同すること。ここでは「1日あたりの増加費用」が問題なので単位費用の比較が正解の判断基準。

補足コラム

• この種の問題は「クラッシュ（crashing）」と呼ばれる手法で、クリティカルパス上の作業を短縮する際の時間とコストのトレードオフを扱います。一般的には、必要短縮日数を満たすためにクリティカルパス上の作業を単位当たり費用の安い順に短縮していきます。
• 一般化すると、短縮すべき作業は次の最適化問題で求められます： $$\min \sum _i{c}_i{x}_i\text{subject to}\sum _{i\in CP}{x}_i\ge D,0\le x_i\le {\Delta }_i$$ ここで $c_i$ は単位短縮費用、$x_i$ は短縮日数、$D$ は回復すべき遅れ、${\Delta }_i$ は作業ごとの短縮可能上限です。今回の問題は $D=1$、上限の制約がない（または1日可能）単純ケースです。

FAQ