基本情報技術者試験「線形計画法」の問題
x≧0、y≧0、x≦3、y≦2、x+y≦4 の制約のもとで、目的関数 z=3x+2y を最大にする。zの最大値はいくらか。
ア最大値は9になる
イzの最大値は13
ウ最大値は11
エ10である
正解
ウ．最大値は11
線形計画では最適解は実行可能領域の頂点で得られる。各頂点のzは(3,0)で9、(3,1)で11、(2,2)で10、(0,2)で4。最大は(3,1)の3×3+2×1=11なので正しい。
?選択肢ごとの解説
ア ×9は頂点(3,0)でのzであり、x+y≦4の余地を使ってyを1まで増やせば11に達するのを見落とした誤りである。
イ ×13は制約x+y≦4を無視して(3,2)を採用した値(3×3+2×2=13)だが、(3,2)はx+y=5>4で実行不可能である。
ウ ○線形計画では最適解は実行可能領域の頂点で得られる。各頂点のzは(3,0)で9、(3,1)で11、(2,2)で10、(0,2)で4。最大は(3,1)の3×3+2×1=11なので正しい。
エ ×10は頂点(2,2)でのzで、こちらも頂点だが最大ではない。(3,1)の11の方が大きい。
✎くわしく
線形計画法では制約が作る凸多角形(実行可能領域)の頂点に最適解が現れる。各制約直線の交点を列挙し、目的関数を評価して比較する。制約を満たさない点(ここでは(3,2))を候補に入れない実行可能性の確認が要点である。
✓本番での押さえどころ
試験のコツ
全頂点(制約直線の交点)を洗い出し、各点が全制約を満たすか確認してから目的関数を比較する。
覚え方
線形計画は『多角形の角を全部試す』。最大・最小は必ず角(頂点)に現れる、と覚える。
よくある誤り
制約x+y≦4を見落として(3,2)で13とする、または1つの頂点だけ見て9や10で打ち切る誤りが多い。
基礎理論の他の問題
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0108