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

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: '【べんだーすぶんかいほう (Benders decomposition method)】 行列 $A$, ベクトル $b$ と $c$, スカラー値関数 $f$, ベクトル値関数 $g$ と有界閉...')
 
 
(3人の利用者による、間の3版が非表示)
1行目: 1行目:
−
【べんだーすぶんかいほう (Benders decomposition method)】
+
'''【べんだーすぶんかいほう (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>
  
−
\[
+
<table align = center>
−
\begin{array}{ll}
+
  <tr><td>min.　</td> <td><math>\phi(y)\,</math></td></tr>
−
        \mbox{min.} & \hspace*{-2mm} \phi(y) \\
+
  <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>
−
        \mbox{s.t.} &  \hspace*{-2mm} y \in Y \cap  
+
</table>
−
    \left\{ y \bigm| \exists \, x \geq 0  
+
の目的関数と実行可能集合が有限回の反復で確定できることに基づいている.
−
              \mbox{ s.t. } A x + g(y) \leq b \right\}
 
−
\end{array}
 
−
\]
 
  
−
の目的関数と実行可能集合が有限回の反復で確定できることに基づいている.
+
[[Category:非線形計画|べんだーすぶんかいほう]]

2008年11月13日 (木) 21:42時点における最新版

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

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

min.　
s.t.　

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

min.　
s.t.　 　|　　s.t.

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

「https://orsj-ml.org/orwiki/wiki/index.php?title=ベンダース分解法&oldid=10995」から取得