ダンツィク・ウルフ分解法のソースを表示

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

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

<math>
  \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}
\,</math>

に対する反復法. 制約条件 <math>\sum_{j=1}^{n} A_{j} x_{j} = a \,</math> の単体乗数ベクトル <math>\pi \,</math> に対して, 

<math>
        \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 
\, </math>

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