「ダンツィク・ウルフ分解法」の版間の差分
| 3行目: | 3行目: | ||
行列 <math>A_{j} \,</math>, <math>B_{j} \,</math>, ベクトル <math>a \,</math>, <math>b_{j} \,</math>, <math>c_{j} \,</math> により定義されるブロック型の線形計画問題 | 行列 <math>A_{j} \,</math>, <math>B_{j} \,</math>, ベクトル <math>a \,</math>, <math>b_{j} \,</math>, <math>c_{j} \,</math> により定義されるブロック型の線形計画問題 | ||
| + | |||
| + | <center> | ||
<math> | <math> | ||
\begin{array}{lll} | \begin{array}{lll} | ||
| 11行目: | 13行目: | ||
\end{array} | \end{array} | ||
\,</math> | \,</math> | ||
| + | </center> | ||
| + | |||
| + | |||
| + | に対する反復法. 制約条件 <math>\textstyle \sum_{j=1}^{n} A_{j} x_{j} = a \,</math> の単体乗数ベクトル <math>\pi \,</math> に対して, | ||
| − | |||
| + | <center> | ||
<math> | <math> | ||
\mbox{min.} \ \ ( A_{j}^{\top} \pi + | \mbox{min.} \ \ ( A_{j}^{\top} \pi + | ||
| 20行目: | 26行目: | ||
x_{j} \geq 0 | x_{j} \geq 0 | ||
\, </math> | \, </math> | ||
| + | </center> | ||
| + | |||
という <math>n \,</math>個の独立な部分問題を順次解いて, もとの問題の解を求める. | という <math>n \,</math>個の独立な部分問題を順次解いて, もとの問題の解を求める. | ||
2007年7月17日 (火) 15:57時点における版
【だんつぃくうるふぶんかいほう (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 \,} , 構文解析に失敗 (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 c_{j} \,} により定義されるブロック型の線形計画問題
構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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} \,}
に対する反復法. 制約条件 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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 \,}
個の独立な部分問題を順次解いて, もとの問題の解を求める.