整数計画法の計算式

2024年6月8日

整数計画法の一般的な形式は、以下のように表されます：

最小化問題：

$$text{minimize} quad c^Tx$$minimizecTx
$$text{subject to} quad Ax leq b$$subjecttoAxb
$$quad quad quad x in mathbb{Z}^n$$x∈Zn

最大化問題：

$$text{maximize} quad c^Tx$$maximizecTx
$$text{subject to} quad Ax leq b$$subjecttoAxb
$$quad quad quad x in mathbb{Z}^n$$x∈Zn

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

• $x$x：最適化問題の変数ベクトル（$n$n次元）
• $c$c：目的関数の係数ベクトル（$n$n次元）
• $A$A：制約条件の係数行列（$m times n$m×n行列）
• $b$b：制約条件の右辺ベクトル（$m$m次元）
• $mathbb{Z}^n$Zn：整数値を持つ$n$n次元ユークリッド空間

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

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