Dantzig-Wolfe 分解#

読み: だんつぃぐうぉるふぶんかい
英名:

線形計画問題において，実行可能領域の端点，端線の情報を用いて得られる等価な別の定式化．例えば次の線形計画問題

(13)#\[\begin{split}\begin{array}{ll} \min & c^\top x \\ \text{s.t.} & Ax \le b \end{array}\end{split}\]

において，実行可能領域 \(Ax \le b\) の端点が \(v_i, \ i \in I\)，端線が \(d_j, \ j \in J\) であるとする．このとき，実行可能領域 \(Ax \le b\) は

(14)#\[\left\{ \sum_{i \in I}{\lambda_i v_i} + \sum_{j \in J}{\mu_j d_j} \ \mid \ \sum_{i \in I}{\lambda_i} = 1, \ \lambda_i \ge 0, \ \mu_j \ge 0 \right\}\]

と表現できる．これを用いると，元の線形計画問題は次のように定式化できる．

(15)#\[\begin{split}\begin{array}{ll} \min & c^\top \left( \sum_{i \in I}{\lambda_i v_i} + \sum_{j \in J}{\mu_j d_j} \right) \\ \text{s.t.} & \sum_{i \in I}{\lambda_i} = 1, \ \lambda_i \ge 0, \ \mu_j \ge 0 \end{array}\end{split}\]