出典は列挙するだけでなく、脚注などを用いてどの記述の情報源であるかを明記してください。記事の信頼性向上にご協力をお願いいたします。(2023年5月)
線型計画法(せんけいけいかくほう、英語: linear programming、略称: LP)は、数理計画法において、いくつかの1次不等式および1次等式を満たす変数の値の中で、ある1次式を最大化または最小化する値を求める方法である。線形計画法の対象となる最適化問題を線型計画問題という。 線型計画法はいくつかの理由で最適化の重要な分野である。オペレーションズリサーチの多くの実際的な問題は線型計画問題として記述できる。ある特殊なケースのネットワークフロー問題
概要
2変数 x 1 ( ≥ 0 ) {\displaystyle x_{1}(\geq 0)} 、 x 2 ( ≥ 0 ) {\displaystyle x_{2}(\geq 0)} の場合、与えられた定係数 a i j {\displaystyle a_{ij}\ } と b i {\displaystyle b_{i}\ } 、 c j {\displaystyle c_{j}\ } 、および不等式制約 a 11 x 1 + a 12 x 2 ≤ b 1 a 21 x 1 + a 22 x 2 ≤ b 2 {\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}\leq b_{2}\\\end{matrix}}}
の下、次式 c 1 x 1 + c 2 x 2 {\displaystyle c_{1}x_{1}+c_{2}x_{2}\ }
の最大値およびそれを実現する x 1 {\displaystyle x_{1}\ } と x 2 {\displaystyle x_{2}\ } を求める問題が、典型的な線型計画問題である。
3変数 x 1 {\displaystyle x_{1}\ } 、 x 2 {\displaystyle x_{2}\ } 、 x 3 {\displaystyle x_{3}\ } の場合、3次元座標空間上に描かれた立体図形を切るような平面のうち、 x 3 {\displaystyle x_{3}\ } 切片(平面と x 3 {\displaystyle x_{3}\ } 軸との交点)の値が最大あるいは最小となるような平面を求めることになる。
最適解の取り得る範囲を整数に限定した線型計画法は、整数計画法と呼ばれる。 線型計画問題の例として以下の問題をとりあげる。農業を営む人が、小麦と大麦のための A {\displaystyle A\ } 平方キロメートルの農地を持っていると仮定する。農家は限度 F {\displaystyle F\ } で肥料、限度 P {\displaystyle P\ } で殺虫剤を使用することができる。これらはそれぞれ単位面積あたり小麦が ( F 1 , P 1 ) {\displaystyle (F_{1},P_{1})\ } 、大麦が ( F 2 , P 2 ) {\displaystyle (F_{2},P_{2})\ } を必要とする。小麦の販売価格を S 1 {\displaystyle S_{1}\ } 、大麦の販売価格を S 2 {\displaystyle S_{2}\ } 、小麦を育てる領域を x 1 {\displaystyle x_{1}\ } 、大麦を育てる領域を x 2 {\displaystyle x_{2}\ } とすると、線型計画問題として大麦と小麦をどれだけ育てればいいかを表すことができる。
線型計画問題の例