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

作業割当の費用最小化【午前2解説】

正解の理由

解法ステップ

1. 各要員の各プログラムに対する所要月数を計算する。
   • A: x: $4/2=2$、y: $2/2=1$、z: $2/2=1$
   • B: x: $4/2=2$、y: $2/2=1$、z: $2/2=1$
   • C: x: $4/1=4$(不適)、y: $2/1=2$、z: $2/1=2$
2. 「全プログラムを2か月以内に完了する」条件より、Cはxを担当できないことを確定する。
3. xはAまたはBに割り当てる必要がある。xをAにする場合、Aは2か月を使い他の割当は不可。xをBにする場合も同様。
4. それぞれの場合について残りのy,zの割当を考え、各要員の契約期間（月数）に単価を掛けて総コストを計算する。
5. 全通りを比較して最小となる組合せ（x→B、y→A、z→C または y↔z交換）を選ぶ。

選択肢別の誤答解説

• ア: 3,200千円
  この値は達成不可能です。最も安い月単価のC（400千円／月）を最大限活用しても、xをCに割り当てられないため総額はこれを下回れません。仮にxをB(1,800)として残りをCにするとCの時間超過で制約違反になります。
• イ: 3,400千円
  3,400千円に相当する割当（例えばxをB、yとzを一人にまとめて低コストで処理）は、いずれの要員でも時間制約や生産性の観点で成り立ちません。y,zを同一要員にまとめられるのはAまたはBであり、その場合合計は3,800千円となります。
• ウ: 3,600千円
  x→B（2か月×900=1,800）、y→A（1か月×1,000=1,000）、z→C（2か月×400=800）で合計3,600千円。yとzを入れ替えても同額で達成可能。
• エ: 3,700千円
  これは x→A（2か月×1,000=2,000）かつ片方をCに割り当てた場合（900+800等）で出る値ですが、xをBにするとより安くできるため最小にはなりません。

よくある誤解

• Cを単価が安いからといってxも担当可能と誤認する。Cの生産性ではxは4か月かかり、2か月制約を満たさないため不可です。
• 「残りをBに割り当てる」と表現してBに複数プログラムを割り当てる案をそのまま採ると、Bの作業時間が2か月を超えないか確認せず誤りになる（xを割り当てればBは他を担当できない）。
• 月数を整数に丸めるかどうかで結論が変わると思い込む。今回のデータでは所要月が整数になっているが、一般には小数も扱える点を意識すること（本問は生産性の商で整数になるため問題は単純）。

補足コラム

FAQ