線形計画法とは？

線形計画法の意味

制約条件と目的関数がいずれも一次式で表せる問題について、制約を満たす範囲（実行可能領域）の中で目的関数を最大（最小）にする解を求める手法。解は実行可能領域の頂点（制約式の交点）のいずれかに存在するため、頂点の値を比較すれば最適解が得られる。

線形計画法の具体例

2製品の生産量を、機械時間と原材料の制約のもとで利益最大となるよう決める問題では、各制約式の交点で利益を計算して比較する。

線形計画法は試験でどう引っ掛けられる？

最適解は領域の内部ではなく端点（頂点）で発生する。この性質が計算問題の解法の鍵になる。

線形計画法と関連する用語

• TOC
• ゲーム理論

線形計画法が出た過去問

• 製品X，Yを1台製造するのに必要な部品数は，表のとおりである。製品1台当たりの利益がX，Yともに1万円のとき，利益は最大何万円になるか。ここで，部品Aは120個…

  正解：45

  要点：資源制約下の最適解は制約式の交点（端点）を比較して求める

  製品Xの台数をx、Yの台数をyとすると、部品Aの制約は3x+2y≦120、部品Bの制約はx+2y≦60となり、利益はx+yに比例する。2式の交点はx=30、y=15で、このとき合計45台となる。他の頂点はx=40・y=0で40台、x=0・y=30で30台なので、最大利益は45万円である。

  出典：平成29年度 秋期 ITストラテジスト試験 am2 問20（IPA）

• 製品X、Yを1台製造するのに必要な部品数は、表のとおりである。製品1台当たりの利益がX、Yともに1万円のとき、利益は最大何万円になるか。ここで、部品Aは120個…

  正解：45

  要点：線形計画では制約式の交点で利益が最大になるか確認する

  製品Xの製造台数をx、Yをyとすると、部品Aの制約は3x＋2y≦120、部品Bの制約はx＋2y≦60、利益はx＋yで表される。2式の交点は両辺の差を取ってx＝30、これをBの式に代入してy＝15となり、このとき利益は45万円になる。頂点（40,0）は40万円、（0,30）は30万円なので、最大値は45万円である。

  出典：令和1年度 秋期 ITストラテジスト試験 am2 問21（IPA）