読み方 ： せんけいけいかくほう

線形計画法 【LP】 Linear Programming / リニアプログラミング

概要

線形計画法（LP）とは、様々な制約条件のもとで目的関数を最適化(最大化あるいは最小化)する解を求める数理計画法のうち、制約も目的関数もすべて一次式(一次不等式、一次等式)で表されるもの。

解説 複数の変数の関係について、不等式で表される制約条件が複数与えられ、等式で与えられる目的関数があるとき、目的関数の値が最大あるいは最小となるような変数の値の組み合わせを求める。

制約条件は、例えば「x+2y<12」「2x+y<12」といった形で一次不等式の形で与えられ、目的関数は「x+y」のようにやはり一次式として表される。この例の場合、制約条件を満たすxとyの値の組み合わせの中で「x=4,y=4」という組み合わせの場合に目的関数の値が最大値である8を取る。

解が存在するような問題設定の場合、2変数ならば制約条件を満たす値が含まれる領域を平面に図示すると多角形（多変数の場合は凸多面体）となり、そのうちの頂点のいずれかが解となる。多変数や多条件の場合に効率良く解を探索する計算手順（アルゴリズム）にはシンプレックス法や内点法などがある。

線形計画法のうち、解を整数に限定したものを「整数計画法」という。条件や目的関数に線形（一次式）ではないものを含む手法は「非線形計画法」（NLP：Non-Linear Programming）という。現実世界では様々な制約の下で最大の効用を得る問題は多くあり、生産や輸送、人員配置の計画などに広く応用されている。

(2021.8.3更新)

他の用語辞典による「線形計画法」の解説 （外部サイト）

資格試験などの「線形計画法」の出題履歴

▼ 基本情報技術者試験
【令7修7 問58】 “1次式で表現される制約条件の下にある資源を，どのように配分したら1次式で表される効果の最大が得られるか” という問題を解く手法はどれか。
【令6修1 問58】 工場で，ある原料から生産している3種類の製品A，B及びCの単位量当たりの製造時間，原料所要量及び利益額を表に示す。この工場の月間合計製造時間は最大240時間であり，投入可能な原料は月間150kgである。
【令5修7 問58】 “1次式で表現される制約条件の下にある資源を，どのように配分したら1次式で表される効果の最大が得られるか” という問題を解く手法はどれか。
【令4修12 問76】 ある工場で製品A，Bを生産している。製品Aを1トン生産するのに，原料P，Qをそれぞれ4トン，9トン必要とし，製品Bについてもそれぞれ8トン，6トン必要とする。
【令4修1 問77】 工場で，ある原料から生産している3種類の製品A，B及びCの単位量当たりの製造時間，原料所要量及び利益額を表に示す。この工場の月間合計製造時間は最大240時間であり，投入可能な原料は月間150kgである。
【令3修12 問77】 “1次式で表現される制約条件の下にある資源を，どのように配分したら1次式で表される効果の最大が得られるか” という問題を解く手法はどれか。
【平30修12 問77】 “1次式で表現される制約条件の下にある資源を，どのように配分したら次式で表される効果の最大が得られるか” という問題を解く手法はどれか。
【平30修1 問77】 ある工場で製品A，Bを生産している。製品Aを1トン生産するのに，原料P，Qをそれぞれ4トン，9トン必要とし，製品Bについてもそれぞれ8トン，6トン必要とする。
【平29修7 問77】 工場で，ある原料から生産している3種類の製品A，B及びCの単位量当たりの製造時間，原料所要量及び利益額を表に示す。この工場の月間合計製造時間は最大240時間であり，投入可能な原料は月間150kgである。
【平28修7 問76】 “1次式で表現される制約条件の下にある資源を，どのように配分したら1次式で表される効果の最大が得られるか” という問題を解く手法はどれか。
【平28修1 問77】 工場で，ある原料から生産している3種類の製品A，B及びCの単位量当たりの製造時間，原料所要量及び利益額を表に示す。この工場の月間合計製造時間は最大240時間であり，投入可能な原料は月間150kgである。
【平26修12 問77】 “1次式で表現される制約条件の下にある資源を，どのように配分したら1次式で表される効果の最大が得られるか” という問題を解く手法はどれか。
【平26修1 問75】 工場で，ある原料から生産している3種類の製品A，B及びCの単位量当たりの製造時間，原料所要量及び利益額を表に示す。この工場の月間合計製造時間は最大240時間であり，投入可能な原料は月間150kgである。
【平25修12 問74】 ある工場で製品A，Bを生産している。製品Aを1トン生産するのに，原料P，Qをそれぞれ4トン，9トン必要とし，製品Bについてもそれぞれ8トン，6トン必要とする。
【平25修7 問74】 “1次式で表現される制約条件の下にある資源を，どのように配分したら1次式で表される効果の最大が得られるか” という問題を解く手法はどれか。
【平24修6 問76】 工場で，ある原料から生産している3種類の製品A，B及びCの単位量当たりの製造時間，原料所要量及び利益額を表に示す。この工場の月間合計製造時間は最大240時間であり，投入可能な原料は月間150kgである。
【平24春 問75】 ある工場で製品A，Bを生産している。製品Aを1トン生産するのに，原料P，Qをそれぞれ4トン，9トン必要とし，製品Bについてもそれぞれ8トン，6トン必要とする。
【平22修12 問75】 ある工場で製品A，Bを生産している。製品Aを1トン生産するのに，原料P，Qをそれぞれ4トン，9トン必要とし，製品Bについてもそれぞれ8トン，6トン必要とする。
【平22修7 問74】 工場で，ある原料から生産している3種類の製品A，B及びCの単位量当たりの製造時間，原料所要量及び利益額を表に示す。この工場の月間合計製造時間は最大240時間であり，投入可能な原料は月間150kgである。