基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

線形計画法は、1次式を満たす変数の値の中で式を最大化または最小化する値を求める方法です。在庫としてもつ原材料を使用して最大の利益を得るための販売量や、機械の稼働時間を最大限に生かして製造する製品など、限りある資源を最大限に活用したい場合にその組合せを得るために使用されます。

問題の条件を整理すると、

• 製品A:1トン＝P:4トン＋Q:9トン
• 製品B:1トン＝P:8トン＋Q:6トン

利益を最大化する、

• Pの在庫40トンをxトンの製品Aとyトンの製品Bの製造に割り当てる。
  →4x＋8y≦40
• Qの在庫54トンをxトンの製品Aとyトンの製品Bの製造に割り当てる。
  →9x＋6y≦54
• さらに、製品A，Bの利益は2万円，3万円で、計算で求められた条件下で利益を最大化したいので 2x＋3y→最大化

この3つの式を満たすx，yを求めることで最適な生産量を求められます。つまり答えは「イ」になります。

実際に「イ」の条件式を解くと次のようになります。

　{4x＋8y≦40 …①
　{9x＋6y≦54 …②

①の式を変形
　4x＋8y≦40
　x＋2y≦10
　2y≦－x＋10
　y≦－1/2x＋5 …③

基底解は、
　0＝－1/2x＋5
　1/2x＝5
　x＝10 …(10，0)

　y＝－1/2×0＋5
　y＝5 …(0，5)

②の式を変形
　9x＋6y≦54
　3x＋2y≦18
　2y≦－3x＋18
　y≦－3/2x＋9 …④

基底解は、
　0＝－3/2x＋9
　3/2x＝9
　x＝6 …(6，0)

　y＝－3/2×0＋9
　y＝9 …(0，9)

③と④の一次関数の直線が重なる点を求める。
　－1/2x＋5＝－3/2x＋9
　－1/2x＋3/2x＝9－5
　x＝4 …⑤

③の式に⑤を代入してyを求める。
　y＝－1/2×4＋5
　y＝－2＋5
　y＝3

上記の制約条件下で最大化された解は、(0，5)，(6，0)，(4，3)の3つになり、それぞれを目的関数2x＋3yに代入してみると、

　(0，5)→2×0＋3×5＝15
　(6，0)→2×6＋3×0＝12
　(4，3)→2×4＋3×3＝17

値が最大となるx＝4，y＝3がこの問題の最適解で、得られる最大利益は17万円とわかります。

この制約条件と最適解をXY座標で表すと次のようになります。