線形計画法（LP）とは？

線形計画法（LP）の意味

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

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

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

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

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

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

• シンプレックス法

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

• 製品X及びYを生産するために2種類の原料A、Bが必要である。製品1個の生産に必要となる原料の量と調達可能量は表に示すとおりである。製品XとYの1個当たりの販売利…

  正解：7,000

  要点：線形計画では制約式の交点が最適解の候補になる

  製品Xの生産数をx、Yをyとすると、原料Aの制約は2x＋y≦100、原料Bの制約はx＋2y≦80となる。利益100x＋150yを最大にする点は二つの制約が同時に等号になる交点で、連立して解くとx＝40、y＝20が得られる。このとき利益は100×40＋150×20＝4,000＋3,000＝7,000円となる。片方の製品だけを作る場合はX単独で5,000円、Y単独で6,000円にとどまるため、7,000円が最大である。

  出典：令和1年度 秋期 基本情報技術者試験 午前 問76（IPA）

• 製品X及びYを生産するために2種類の原料A, Bが必要である。製品1個の生産に必要となる原料の量と調達可能量は表に示すとおりである。製品XとYの1個当たりの販売…

  正解：7,000

  要点：線形計画では制約式の交点が最適解の候補になる

  製品Xの生産数をx、Yをyとすると、原料Aの制約は2x＋y≦100、原料Bの制約はx＋2y≦80となる。利益100x＋150yが最大となるのは二つの制約が同時に等号となる点で、連立して解くとx＝40、y＝20が得られる。このとき利益は100×40＋150×20＝4,000＋3,000＝7,000円である。片方だけを作る場合はX単独で5,000円、Y単独で6,000円にとどまる。

  出典：令和4年度 s 基本情報技術者試験 kamokuA 問57（IPA）