線型計画問題
線型計画問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/05/28 18:23 UTC 版)
線型計画問題は、目的関数と制約条件が全て線型性を有する最適化問題である。 主問題では、目的関数は n 個の変数を線型に組み合わせたものである。m 個の制約条件があり、それぞれが n 個の変数の線型な組合せの上限を定めている。問題は、制約条件を満たしつつ、目的関数の値を最小化する変数の値の組合せを求めることである。解は n 個の値のベクトル（リスト）であり、それらの値を目的関数に入力することで最小値が得られる。 双対問題では、目的関数は m 個の値の線型な組合せであり、これらは主問題の m 個の制約条件（上限値）それぞれに対応している。n 個の双対制約条件（dual constraints）があり、それぞれが m 個の双対変数（dual variables）の線型な組合せの下限を定めている。この場合、目的関数の値を最大化する双対変数の値の組合せを求める。
※この「線型計画問題」の解説は、「双対問題」の解説の一部です。
「線型計画問題」を含む「双対問題」の記事については、「双対問題」の概要を参照ください。
線型計画問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/16 17:05 UTC 版)
数学的には線型計画問題は、目的関数（英語版）と制約条件（英語版）がすべて線型の最適化問題である。 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}\ } 軸との交点）の値が最大あるいは最小となるような平面を求めることになる。 最適解の取り得る範囲を整数に限定した線型計画法は、整数計画法（英語版）と呼ばれる。
※この「線型計画問題」の解説は、「線型計画法」の解説の一部です。
「線型計画問題」を含む「線型計画法」の記事については、「線型計画法」の概要を参照ください。
- 線型計画問題のページへのリンク
