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

'''【だんつぃくうるふぶんかいほう (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}
\]
に対する反復法. 制約条件 $\sum_{j=1}^{n} A_{j} x_{j} = a$ の単体乗数ベクトル $\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$個の独立な部分問題を順次解いて, もとの問題の解を求める.