基本情報技術者 2019年 秋期 午前（科目A） 問76

線形計画法（原料制約の利益最大化）【午前2 解説】

要点まとめ

• 結論→ 利益最大は7,000円。最適解は製品Xを40個、製品Yを20個生産し、原料AとBをともに使い切ることで得られます。
• 根拠→ 制約は $2x+y\le 100,x+2y\le 80,x,y\ge 0$ で、これらの交点 $(40,20)$ が実行可能領域の極点となり最大値を与えます。
• 差がつくポイント→ グラフ法で実行可能領域の極点（交点と軸上点）を必ず確認し、各点で目的関数を比較する習慣を付けること。

正解の理由

よくある誤解

• 「単純に単位利益が高い方だけ作れば良い」と考える誤り：資源消費比率により高利益製品を増産できない場合がある点を見落とします。
• 交点計算を省略して軸上の1点だけ評価するミス：必ず両制約の交点を計算して比較してください。
• 整数性を必要以上に心配する誤解：今回の係数・資源量では最適解は整数ですが、一般に整数計画が必要かは問題文を確認します。

解法ステップ

1. 変数定義：$x$ を製品X個数、$y$ を製品Y個数とする。
2. 不等式で制約を表す：$2x+y\le 100,x+2y\le 80,x\ge 0,y\ge 0$.
3. 目的関数を設定：$P=100x+150y$ を最大化。
4. 実行可能領域の頂点（極点）を求める：各制約の交点と軸交点を計算する。
5. 各頂点で $P$ を評価し最大値を選ぶ。

• $2x+y=100$ より $y=100-2x$。これを $x+2y=80$ に代入して解く：
  $x+2(100-2x)=80\Rightarrow -3x=-120\Rightarrow x=40$、従って $y=100-2\times 40=20$。
• 頂点での評価： $(0,0):0,(50,0):100\times 50=5000,(0,40):150\times 40=6000,(40,20):7000$。
• よって最大は $(40,20)$ で $7000$ 円。

選択肢別の誤答解説

• ア: 5,000 — 軸上の点 $(50,0)$（原料Aを全部使ってXのみ生産）で得られる利益。交点評価を忘れた誤り。
• イ: 6,000 — 軸上の点 $(0,40)$（原料Bを全部使ってYのみ生産）で得られる利益。交点の方が有利。
• 正解: ウ — 交点 $(40,20)$ での利益 $100\times 40+150\times 20=7000$ 円が最大。
• エ: 8,000 — 実行可能領域外の仮定（資源を超える組合せ）による過大評価。制約条件を満たしていない。

補足コラム

• なぜ極点（頂点）を見るのか：線形計画の基本定理により、線形目的関数は凸多角形（実行可能領域）上で必ず頂点で最大（または最小）となります。よって全ての頂点を評価すれば確実に最適解が得られます。
• 制約が2つならグラフ法で解くのが最短。変数が多ければ単体法などの一般手法を使います。
• この問題では最適解が整数になっていますが、一般問題で整数性が必要なら整数計画法を用います。

FAQ