3. スラック緩和#
3.1. 導入#
制約式に対して，補助的な非負変数を導入することにより，その制約条件を緩和するテクニックがある． これはスラック緩和と呼ばれる． このテクニックは，例えば実行不可能な問題に対してその原因追及に役立つ．
3.2. スラック緩和#
以下のような不等式があるとする．
(1)#\[g(x) \leq b\]
このとき非負変数 \(s\) を導入する．
(2)#\[g(x) - s \leq b\]
この非負変数はスラック変数と呼ばれる． このスラック変数を目的関数に組み入れることで， 「緩和している制約式を可能な限り満たすようにする」というようなことを表現できる．
(3)#\[\begin{split}& \mathrm{Minimize\colon}~ s \\
& \mathrm{subject~to\colon}~ \\
& g(x) - s \leq b\end{split}\]
符号が逆の不等式制約 \(g(x) \geq b\) の場合はスラック緩和する制約式は以下のようになる．
(4)#\[g(x) + s \geq b\]
等式制約 \(g(x) = b\) の場合は二つのスラック変数 \(s_+, s_-\) を導入すると便利である．
(5)#\[g(x) + s_+ - s_- = b\]
3.3. 例題#
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()
関連
引用書式