2. 最大値最小化問題#
2.1. 導入#
最大値最小化問題とは次のように目的関数に \(\mathrm{max}\) 関数が含まれ， これを最小化する非線形な問題である．
(1)#\[\begin{split}& \mathrm{Minimize\colon}~ \max_{i\in I}z[i] \\
& \mathrm{subject~to\colon}~ \\
& z[i] = \sum_{j\in J} c[j]\cdot x[i,j],~ \forall i\in I\end{split}\]
重要
モデリング言語 SIMPLE では min 関数や max 関数が用意されているが，通常これらを用いることは推奨されない．
これらの関数を使うことによって問題が非線形になってしまい求解が難しくなってしまうことと，整数変数を用いた問題に適用できなくなってしまうことが主な理由である．
2.2. LP による定式化#
最大値最小化問題は \(\mathrm{max}\) 関数のために非線形な問題となっているが， 以下のように定式化することで，最大値最小化問題と等価な LP で表現できることを説明する．
このためにまず次に着目する．
(2)#\[\mathrm{Minimize\colon}~ \max_{i\in I}z[i]\]
これは次と等価である．
(3)#\[\begin{split}& \mathrm{Minimize\colon}~ \zeta \\
& \mathrm{subject~to\colon}~ \\
& \zeta \geq z[i],~ \forall i \in I\end{split}\]
何故ならば \(\mathrm{max}_{i\in I}z[i]\) 関数とは， 各 \(z[i]\) の値以上のうちで最小の値 \(\zeta\) を求めることに等しいからである．
後は今の問題の場合には \(z[i]\) とは \(\sum_{j\in J} c[j]\cdot x[i,j]\) に等しかったから， 最大値最小化問題を LP として以下のように表現できる．
(4)#\[\begin{split}& \mathrm{Minimize\colon}~ \zeta \\
& \mathrm{subject~to\colon}~ \\
& \zeta \geq\sum_{j\in J} c[j]\cdot x[i,j]\end{split}\]
関連
引用書式