線形計画法（LP）とは？

線形計画法（LP）の意味

複数の制約条件のもとで利益最大化や費用最小化を図る最適な資源配分を、1次式（線形の式）で定式化して求める数理計画手法。応用情報では、制約条件の不等式を立て、実行可能領域の頂点で目的関数を評価する計算問題として頻出する。

線形計画法（LP）の具体例

2種類の製品を作るのに使える原材料と作業時間に上限がある工場で、利益を最大化する各製品の生産量の組合せを、不等式で表した制約条件のもとで求める。

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

実行可能領域（制約を満たす範囲）の「境界上の頂点」のいずれかで目的関数が最適値をとる、という性質を使わずに力任せに探索しようとして計算を誤りやすい。

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

• シンプレックス法

線形計画法（LP）が出た過去問

• 工場で，ある原料から生産している3種類の製品A，B及びCの単位量当たりの製造時間，原料所要量及び利益額を表に示す。この工場の月間合計製造時間は最大240時間であ…

  正解：線形計画法

  要点：資源制約下で利益を最大化する配分は線形計画法で解く。

  製造時間と原料という限られた資源の制約のもとで、利益の合計を最大にする各製品の生産量を求める問題である。制約条件も目的とする利益も生産量の一次式で表せるため、線形計画法が適用できる。図解法やシンプレックス法で最適解を求める典型的な問題である。

  出典：平成30年度 秋期 応用情報技術者試験 午前 問76（IPA）

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

  正解：45

  要点：線形計画法の最適解は制約式の交点（端点）で得られる

  製品X、Yの台数をx、yとすると、制約は部品Aが3x＋2y≦120、部品Bがx＋2y≦60で、利益はx＋yとなる。2式の交点はx＝30、y＝15で、このとき利益は45万円になる。頂点（0,30）で30、（40,0）で40なので、最大は45万円である。

  出典：令和3年度 秋期 応用情報技術者試験 午前 問76（IPA）

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

  正解：45

  要点：線形計画では制約式の交点など頂点を調べて最大利益を求める

  製品Xの生産台数をx、Yをyとすると、制約は部品Aが3x＋2y≦120、部品Bがx＋2y≦60で、利益はx＋yを最大化する線形計画問題となる。2式の交点は両辺を引いて2x＝60よりx＝30、これを代入してy＝15。このときの利益は45万円で、他の頂点（x＝40,y＝0で40万円、x＝0,y＝30で30万円）より大きい。よってウが正解。

  出典：令和6年度 春期 応用情報技術者試験 午前 問75（IPA）

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

  正解：45

  要点：線形計画では制約式の交点など頂点を調べて最大利益を求める

  製品Xの製造台数をx、Yをyとすると、制約は部品Aが3x＋2y≦120、部品Bがx＋2y≦60で、目的はx＋yの最大化となる。両式の差をとると2x≦60よりx≦30で、交点はx＝30、y＝15。このとき利益は45万円で、他の頂点（x＝40,y＝0で40万円、x＝0,y＝30で30万円）を上回るのでウが正解。

  出典：令和7年度 秋期 応用情報技術者試験 午前 問75（IPA）