「ダンツィク・ウルフ分解法」の版間の差分
(新しいページ: ''''【だんつぃくうるふぶんかいほう (Dantzig-Wolfe decomposition method)】''' 行列 $A_{j}$, $B_{j}$, ベクトル $a$, $b_{j}$, $c_{j}$ により定義され...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (3人の利用者による、間の3版が非表示) | |||
| 1行目: | 1行目: | ||
'''【だんつぃくうるふぶんかいほう (Dantzig-Wolfe decomposition method)】''' | '''【だんつぃくうるふぶんかいほう (Dantzig-Wolfe decomposition method)】''' | ||
| − | 行列 | + | 行列 <math>A_{j} \,</math>, <math>B_{j} \,</math>, ベクトル <math>a \,</math>, <math>b_{j} \,</math>, <math>c_{j} \,</math> により定義されるブロック型の線形計画問題 |
| − | + | ||
| + | |||
| + | <center> | ||
| + | <math> | ||
\begin{array}{lll} | \begin{array}{lll} | ||
\mbox{min.} & \displaystyle{\sum_{j=1}^{n} c_{j}^{\top} x_{j} } & \\ | \mbox{min.} & \displaystyle{\sum_{j=1}^{n} c_{j}^{\top} x_{j} } & \\ | ||
| 9行目: | 12行目: | ||
& \displaystyle{x_{j} \geq 0,} & j = 1, \ldots, n | & \displaystyle{x_{j} \geq 0,} & j = 1, \ldots, n | ||
\end{array} | \end{array} | ||
| − | \ | + | \,</math> |
| − | に対する反復法. 制約条件 | + | </center> |
| − | + | ||
| − | \mbox{min.} \ | + | |
| + | に対する反復法. 制約条件 <math>\textstyle \sum_{j=1}^{n} A_{j} x_{j} = a \,</math> の単体乗数ベクトル <math>\pi \,</math> に対して, | ||
| + | |||
| + | |||
| + | <center> | ||
| + | <math> | ||
| + | \mbox{min.} \ \ ( A_{j}^{\top} \pi + | ||
c_{j} )^{\top} x_{j} | c_{j} )^{\top} x_{j} | ||
| − | \quad \mbox{s.t.} \ | + | \quad \mbox{s.t.} \ \ B_{j} x_{j} = b_{j}, |
| − | + | x_{j} \geq 0 | |
| − | \ | + | \, </math> |
| − | という | + | </center> |
| + | |||
| + | |||
| + | という <math>n \,</math>個の独立な部分問題を順次解いて, もとの問題の解を求める. | ||
| + | |||
| + | [[Category:非線形計画|だんつぃくうるふぶんかいほう]] | ||
2008年11月12日 (水) 15:47時点における最新版
【だんつぃくうるふぶんかいほう (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 \,}
個の独立な部分問題を順次解いて, もとの問題の解を求める.