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

要点まとめ

• 結論→ 原料A,Bの制約下で製品Xを40個、製品Yを20個生産すると利益が最大の7000円になる（各制約を同時に満たす角点解）。
• 根拠→ 目的関数 $100x+150y$ を制約 $2x+y\le 100,x+2y\le 80$ の角点で評価すると、$(40,20)$ が最大値を与えるため最適解となる。
• 差がつくポイント→ 目的関数の傾きと制約線の傾きを比較し、最適解が制約の交点にあるかを判断することで解答スピードが上がる。

正解の理由

よくある誤解

• 「利益比（単位あたり利益）だけで決める」：単純に利益/原料比で大きい方を優先すると他の原料制約を無視して誤答になります。
• 「交点計算を省略して軸上の最大値だけ見る」：軸上（片方0）の解が最適とは限らないため、交点評価を忘れると見落とします。
• 「目的関数の傾きを誤って比較する」：傾きの大小関係を誤ると、最適位置（交点／辺上）を誤判断します。

解法ステップ

1. 変数定義：製品Xを $x$ 個、製品Yを $y$ 個とする。
2. モデル化：目的関数 $Z=100x+150y$、制約 $2x+y\le 100,x+2y\le 80,x\ge 0,y\ge 0$ を立てる。
3. 角点を列挙：座標は (0,0)、(50,0)（A制約から）、(0,40)（B制約から）、および2つの制約の交点。
4. 交点を解く：2x+y=100 と x+2y=80 を連立して解く。
   • $2x+y=100$
   • $x+2y=80$
     2式目を2倍して $2x+4y=160$、これから1式を引くと $3y=60$ より $y=20$。
     これを用いて $x=80-2y=80-40=40$。よって交点は $(40,20)$.
5. 目的関数を評価：
   • $(50,0):Z=100\times 50+150\times 0=5000$
   • $(0,40):Z=100\times 0+150\times 40=6000$
   • $(40,20):Z=100\times 40+150\times 20=7000$
6. 最大値は7000円（$(40,20)$）なのでこれが最適解。

選択肢別の誤答解説

• ア: 5,000 — これは $(50,0)$ のときの利益で、原料Aの制約を使い切ってYは0の場合の値です。だがBの制約に余裕があり改善可能です。
• イ: 6,000 — これは $(0,40)$ のときの利益で、原料Bの制約を使い切ってXが0の場合の値です。Aの制約に余裕がありさらに改善できます。
• ウ: 7,000 — 正解。2つの資源制約が同時に等号となる交点 $(40,20)$ が与える最大利益です。
• エ: 8,000 — 実現不可能な値です。どの角点でも到達せず、どの組合せでも制約を満たして8000円を超えることはできません。

補足コラム

• 角点定理（基本定理）により線形計画の最適解は必ず角点にあるため、グラフ法で角点を調べれば解が得られます。
• 目的関数の傾きは $y=-(100/150)x+C/150$ より傾き $-2/3$。制約線の傾き $-2$（A）と $-1/2$（B）の間にあるため、最適は両制約の交点になります。
• 大規模問題や変数が多い場合は単体法（シンプレックス法）を使うと効率的に解けます。

FAQ