「ベンダース分解法」の版間の差分

2007年7月14日 (土) 03:12時点における版

【べんだーすぶんかいほう (Benders decomposition method)】

行列 $A\,$ , ベクトル $b\,$ と $c\,$ , スカラー値関数 $f\,$ , ベクトル値関数 $g\,$ と有界閉集合 $Y\,$ により定義される次のような制約付き問題に対する 2 段階の反復法.

min.	$c^{\top }x+f(y)\,$
s.t.	$Ax+g(y)\leq b,\,$
	$x\geq 0,\quad y\in Y.\,$

変数 $y\,$ を固定した線形計画問題の最適値関数を $\phi (y)\,$ とするとき, 等価な問題

min.	$\phi (y)\,$
s.t.	$y\in Y\cap \{y\,$ 　\|　 $\exists x\geq 0\,$ 　s.t. $Ax+g(y)\leq b\}\,$

の目的関数と実行可能集合が有限回の反復で確定できることに基づいている.

@@ 1行目: / 1行目: @@
 【べんだーすぶんかいほう (Benders decomposition method)】
-行列 $A$, ベクトル $b$ と $c$, スカラー値関数 $f$, ベクトル値関数 $g$ と有界閉集合 $Y$ により定義される次のような制約付き問題に対する 2 段階の反復法.
+行列 <math>A\,</math>, ベクトル <math>b\,</math> と <math>c\,</math>, スカラー値関数 <math>f\,</math>, ベクトル値関数 <math>g\,</math> と有界閉集合 <math>Y\,</math> により定義される次のような制約付き問題に対する 2 段階の反復法. <br><br>
-\[
+<table align = center>
-\begin{array}{ll}
+  <tr><td>min.　</td> <td><math>c^{\top} x + f(y)\,</math></td></tr>
-   \mbox{min.} &  c^{\top} x + f(y) \\
+  <tr><td>s.t.　</td> <td><math>A x + g(y) \leq b,\,</math></td></tr>
-   \mbox{s.t.} &  A x + g(y) \leq b, \\
+  <tr><td></td> <td><math>x \geq 0, \quad y \in Y.\,</math></td></tr>
-               &  x \geq 0, \quad y \in Y.
+</table>
-\end{array}
-\]
-変数 $y$ を固定した線形計画問題の最適値関数を $\phi(y)$ とするとき, 等価な問題
+変数 <math>y\,</math> を固定した線形計画問題の最適値関数を <math>\phi(y)\,</math> とするとき, 等価な問題<td><td>
-\[
-\begin{array}{ll}
-        \mbox{min.} & \hspace*{-2mm} \phi(y)  \\
-         \mbox{s.t.} &  \hspace*{-2mm} y \in Y \cap
-     \left\{ y \bigm| \exists \, x \geq 0
-               \mbox{ s.t. } A x + g(y) \leq b \right\}
-\end{array}
-\]
+<table align = center>
+  <tr><td>min.　</td> <td><math>\phi(y)\,</math></td></tr>
+  <tr><td>s.t.　</td> <td><math>y \in Y \cap \{ y\,</math>　|　<math>\exists x \geq 0\,</math>　s.t.<math>A x + g(y) \leq b\}\,</math></td></tr>
+</table>
 の目的関数と実行可能集合が有限回の反復で確定できることに基づいている.

「ベンダース分解法」の版間の差分

2007年7月14日 (土) 03:12時点における版

案内メニュー

検索