トップ > 数理計画用語集 > Dantzig-Wolfe 分解

数理計画用語集

Dantzig-Wolfe 分解

読み:だんつぃぐうぉるふぶんかい
関連列生成法

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

equation

において,実行可能領域 equation の端点が equation ,端線が equation であるとする.このとき,実行可能領域 equationequationと表現できる.これを用いると,元の線形計画問題は,次のように定式化できる.

equation