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

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

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

${\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\,$

という $n\,$個の独立な部分問題を順次解いて, もとの問題の解を求める.