3. スラック緩和#
3.1. 説明#
制約式に対して，補助的な非負変数を導入することにより，その制約条件を緩和するテクニックがある． これはスラック緩和と呼ばれる． このテクニックは，例えば実行不可能な問題に対してその原因追及に役立つ．
以下のような不等式があるとする．
(3.9)#\[g(x) \leq b\]
このとき非負変数 \(s\) を導入する．
(3.10)#\[g(x) - s \leq b\]
この非負変数はスラック変数と呼ばれる． このスラック変数を目的関数に組み入れることで， 「緩和している制約式を可能な限り満たすようにする」というようなことを表現できる．
(3.11)#\[\begin{split}& \mathrm{Minimize:}~ s \\
& \mathrm{subject~to:}~ \\
& g(x) - s \leq b\end{split}\]
符号が逆の不等式制約 \(g(x) \geq b\) の場合はスラック緩和する制約式は以下のようになる．
(3.12)#\[g(x) + s \geq b\]
等式制約 \(g(x) = b\) の場合は二つのスラック変数 \(s_+, s_-\) を導入すると便利である．
(3.13)#\[g(x) + s_+ - s_- = b\]
3.2. 例題#
1from pysimple import Variable, Problem, Options
2
3p = Problem(type=min) # `type=min` は省略可能
4x1 = Variable(lb=0.0, ub=100)
5x2 = Variable(lb=0.0, ub=100)
6s = Variable(lb=0.0)
7x = Variable(lb=0.0)
8y = Variable(lb=0.0)
9
10p += 8 * x1 + 3 * x2 >= 15
11p += 10 * x1 + 5 * x2 - s <= 10
12p += s
13
14p.options.method = Options.Method.SIMPLEX # `p.options.method = 'simplex'` でも可
15p.solve()