線形計画法の式は？

2024年6月8日

線形計画法（Linear Programming、LP）の一般的な形式は、以下のように表されます：

最小化問題：

$$text{minimize} quad c^Tx$$minimizecTx
$$text{subject to} quad Ax leq b$$subjecttoAxb
$$quad quad quad x geq 0$$x0

最大化問題：

$$text{maximize} quad c^Tx$$maximizecTx
$$text{subject to} quad Ax leq b$$subjecttoAxb
$$quad quad quad x geq 0$$x0

ここで、各記号の意味は次の通りです：

• $x$x：最適化問題の変数ベクトル（$n$n次元）
• $c$c：目的関数の係数ベクトル（$n$n次元）
• $A$A：制約条件の係数行列（$m times n$m×n行列）
• $b$b：制約条件の右辺ベクトル（$m$m次元）
• $x geq 0$x0：変数 $x$x の非負条件

この形式では、目的関数 $c^Tx$cTx を最小化あるいは最大化するという目標のもとで、制約条件 $Ax leq b$Axb の下で最適解を探索します。制約条件は不等式制約であり、変数 $x$x は非負の値を取る必要があります。

線形計画法は、このような形式の最適化問題を解く手法であり、目的関数や制約条件を具体的な数値で与えることで、具体的な問題に適用することができます。