1. 自由変数の非負変数への分解#
1.1. 導入#
自由変数は \(2\) つの非負変数 \(x^+(\geq 0)\) と \(x^-(\geq 0)\) で次のように分解できる．
自由変数 \(x\) が非負か負であるかによって，\(x^+\) と \(x^-\) のどちらか一方が選択され， 選択されなかった方は \(x\) に寄与しない分解である． もしそのように配慮されて書けるならば，上記のように場合分けでなく，次のように線形で表現できる．
このように書き下すためには以下の論理条件が課されている必要がある．
線形定式化として上記を書き下すには，以下の方法が考えられる．
自由変数を制約条件式で明示的に分解する方法
自由変数の分解を目的関数で配慮する方法
これらについて以下に言及する．
1.2. 制約条件による明示#
書き下したい条件式は \(x^+\) と \(x^-\) のどちらか一方が \(0\) であるような条件式である． もう少し厳密に言えば，\(x=0\) を表すために，両方とも \(0\) である場合も許容しなければならない． これを表す制約条件として次を立式できる．
しかしこれは非線形であり，線形に定式化できていない．
線形に定式化するには，次のように Big M を用いればよい．
ここで \(z\) は \(0\) か \(1\) をとるバイナリ変数である． 各値について上記の制約条件式は次を意味している． 但し \(x^+\) と \(x^-\) が非負変数であることを考慮している．
\(z\) |
\(x^+ \leq M_+ \cdot z\) |
\(x^- \leq M_- \cdot (1-z)\) |
|---|---|---|
\(0\) |
\(x^+=0\) |
\(x^-\leq M_-\) |
\(1\) |
\(x^+ \leq M_+\) |
\(x^-=0\) |
よって \(x=x^+-x^-\) であったから， \(M_+\) と \(M_-\) がそれぞれ \(x\) の上界と下界を表すものと解釈すれば， 論理条件 (3) が表現できているとわかる．
以上によって非線形定式化を線形定式化に帰着できた．
注釈
制約条件式 (3) を機械的に演繹する一つの方法として次がある． \(x\) に対して，\(x^+,-x^-\) は非負と負の部分をそれぞれ担うものだった． つまり二つの領域があり，これらを指示するバイナリ変数として \(z\) を立てる． \(z=1\) が非負の領域で，\(z=0\) が負の領域を指示する． 式として表すと次である．
ここで非線形項は連続変数 \(x\) とバイナリ変数 \(z\) の積のみ \(x\cdot z\) になった． これは 論理式の線形表現 の 連続変数との積 で述べている状況である． よって非負変数 \(x^{\pm}\) について，\((y,U,L)=(x^+,M_+,M_-)\) の対応の下で上記の非線形式を整理できる． これを実行すると，制約条件式 (3) が演繹される．
以上のように，数理最適化で特有な式変形に習熟しておくと，ひとまず立式するだけでも，線形な定式化へと帰着できる道筋が見えてくる．
1.3. 目的関数による配慮#
もし問題に目的関数が存在して最小化問題であれば， \(x^+\) と \(x^-\) の重みが正の適当な線形結合を加味することで， 明示的に制約条件を書くことを省略できる． また仮に最大化問題であれば，重みが負の線形結合とすればよい．
このようにした目的関数による配慮での解決手段は， 例えば 絶対値最小化問題 を LPによる定式化 で記述する場合に用いることになる．
関連
引用書式