ダンツィク・ウルフ分解法

【だんつぃくうるふぶんかいほう (Dantzig-Wolfe decomposition method)】

行列 $A_{j}\,$, $B_{j}\,$, ベクトル $a\,$, $b_{j}\,$, $c_{j}\,$ により定義されるブロック型の線形計画問題

${\begin{array}{lll}{\mbox{min.}}&\displaystyle {\sum _{j=1}^{n}c_{j}^{\top }x_{j}}&\\{\mbox{s.t.}}&\displaystyle {\sum _{j=1}^{n}A_{j}x_{j}=a,}&\\&\displaystyle {B_{j}x_{j}=b_{j},}&j=1,\ldots ,n,\\&\displaystyle {x_{j}\geq 0,}&j=1,\ldots ,n\end{array}}\,$

に対する反復法. 制約条件 $\textstyle \sum _{j=1}^{n}A_{j}x_{j}=a\,$ の単体乗数ベクトル 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \pi \,} に対して,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{min.} \ \ ( A_{j}^{\top} \pi + c_{j} )^{\top} x_{j} \quad \mbox{s.t.} \ \ B_{j} x_{j} = b_{j}, x_{j} \geq 0 \, }

という 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n \,} 個の独立な部分問題を順次解いて, もとの問題の解を求める.