スラック変数 (slack variable) は,数理計画法で定義された標準的な制約条件の形に適合させるために導入する変数.
例えば,線形計画問題では \(A\mathbf{x}=\mathbf{b}, \mathbf{x}\ge0\) が標準的な制約の形.
\(\mathbf{a_i}^\top\mathbf{x}\le b_i\) のような制約があったとき, \(\mathbf{a}_i^\top \mathbf{x} +\xi_i=b_i,\ \xi_i\ge0\) のように書き換える.このとき,\(\xi_i\) がスラック変数.
線形計画問題の \(\mathbf{x}\) には,スラック変数が加わり \[\mathbf{x}'=[x_1,\ldots,x_N,\xi_1,\ldots,\xi_L]^\top\] のようになり,行列 A は,例えば次のようになる. \[A'=\left(\begin{array}{cccccc}a_{11} & \cdots & a_{1N} & 1 & 0 \cdots & 0 \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ a_{M1} & \cdots & a_{MN} & 0 & \cdots 0 & 1\end{array} \right)\] ※ 右側の部分は,スラック変数が導入されたところだけが1になる.スラック変数が不要な条件では全て 0.
一方,\(\mathbf{a_i}^\top\mathbf{x}\ge b_i\) のような制約があったとき, \(\mathbf{a}_i^\top \mathbf{x} -\eta_i=b_i,\ \eta_i\ge0\) のように書き換える.このとき,\(\eta_i\) が剰余変数 (surplus variable).
-- しましま