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

工期短縮の最小追加費用【午前2解説】

正解の理由

• A→C: $5+6=11$日
• A→D→E: $5+3+5=13$日
• B→E: $10+5=15$日

• B→E: $7+5=12$ 日
• A→D→E: $4+3+5=12$ 日
• A→C: $4+6=10$ 日 となり、全経路が12日以下になり目標達成します。合計費用は $9+2=11$ 万円で、選択肢の中では最小です。したがって正答は イ（11万円）です。

解法ステップ

1. 各経路の標準所要日数を列挙する（A→C, A→D→E, B→E）。
2. 全体短縮目標を決める：現在の最長所要日数から短縮日数を引く（今回 $15-3=12$ 日）。
3. 目標日数以下にするために短縮対象を検討。まず最長経路上の作業（B, E）を検討し、コスト効率の良い作業から順に短縮候補に入れる。
4. 短縮を組み合わせた後に、他経路の所要日数が目標を超えないかを必ず確認する（経路間の「移動するクリティカルパス」を考慮）。
5. 複数の組合せについて合計費用を計算し、最小となる組合せを選ぶ。

選択肢別の誤答解説

• ア（9万円）: B を3日短縮する費用 $3\times 3=9$ 万円と一致しますが、B3 のみでは A→D→E が $13$ 日のまま残り、プロジェクト全体は $13$ 日で短縮目標の $12$ 日に達しません。したがって不十分です。
• イ（11万円）: 前節の通り B を3日短縮（9万円）＋A を1日短縮（2万円）で合計11万円、全経路が $12$ 日以下になり目標を満たします。最小費用となるため正解です。
• ウ（12万円）: 例えば B を2日短縮（6万円）＋E を1日短縮（6万円）で合計12万円とすると、B→E と A→D→E はともに $12$ 日になり目標は達成しますが、費用は11万円より高いため最小ではありません。
• エ（14万円）: 例えば B3（9万円）＋D1（5万円）等の組合せで14万円になる場合がありますが、B3+A1の11万円より高く非最適です。また B2+D1 の組合せ（6+5=11万円）を「11万円の最小解」と誤認する場合がありますが、B2+D1 では B→E が $13$ 日のままで目標未達です（この点に注意）。

よくある誤解

• 「最長経路だけ短縮すれば良い」は誤り。最長経路を短縮しても、他の経路が新たに最長となる可能性があり、全経路が目標以下になるように検討する必要があります。
• 単純に1日あたりコストが安い活動だけを選べば良いわけではない。コスト効率だけでなく、どの経路の長さを変えるか（経路間のバランス）を考慮することが重要です。
• 「部分的に短縮できる日数の上限」を確認しないと、実現不可能な組合せで答えてしまうことがあります（各作業には短縮可能日数の上限あり）。

補足コラム

FAQ