ベンダース分解法

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

行列 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A\,} , ベクトル $b\,$ と $c\,$, スカラー値関数 $f\,$, ベクトル値関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g\,} と有界閉集合 $Y\,$ により定義される次のような制約付き問題に対する 2 段階の反復法.

min.	構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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.

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y \in Y \cap \{ y\,} 　|　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \exists x \geq 0\,} 　s.t.構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A x + g(y) \leq b\}\,}

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