平成29年度秋期 ITパスポート試験問1

この問題の解説と、これまでの解答の記録です。

問1

頻出度★★★

表は，技術者A，B，C がそれぞれ製品X，Y，Z を製造する場合の1日の生産額を示している。各技術者は1日に1製品しか担当できないとき，1日の最大生産額は何万円か。ここで，どの製品も必ず生産するものとする。単位　万円／日

出典　平成29年度秋期 ITパスポート試験問1

解説

問 1

不正解ア
20万円は、例えばA→X(6)・B→Y(6)・C→Z(8)=20 のような正しい割当ての一例だが、これは最大ではない。最善(22万円)より低い。
不正解イ
21万円は、例えばA→X(6)・B→Z(7)・C→Y(8)=21 や A→Y(7)・B→X(6)・C→Z(8)=21 で到達できる合計だが、いずれも最大の22万円には届かない。
ウ
正解これは割当問題(組合せ最適化)である。各技術者は1製品だけを担当し、かつX・Y・Zをすべて必ず生産するので、技術者と製品を1対1に対応させる(全単射)。3人・3製品なので割当ては3!=6通り。すべて計算すると、A→Z(8万円)・B→X(6万円)・C→Y(8万円)のとき合計8+6+8=22万円となり、これが最大である。よって正解は「ウ 22」。
不正解エ
23万円は、どの割当て(全単射6通り)でも到達できない。各列(技術者)の最大値だけを見ると8・7・8に見えるが、それらは製品Zに集中しており、同じ製品を重複して選ぶことになり制約に反する。制約を守った割当ての上限は22万円で、23万円は過大。

ここがポイント

割当問題(組合せ最適化): 行(製品)と列(技術者)を1対1に対応させ合計を最大化する。列ごとの最大値を単純に足すと同じ製品/技術者を重複選択してしまい成立しないので、3!=6通りの割当てを比較して最大を選ぶ。
制約の読み取り: 「各技術者は1日1製品」かつ「どの製品も必ず生産」= 技術者と製品の全単射。この条件下で最大合計は22万円。

用語

解答問1ウ