Dantzig–Wolfe decomposition，Dantzig–Wolfe算法解决特殊的线性规划问题，它是George Dantzig和Phil Wolfe在1960年建立起来和并得到发展，依靠Delayed Column Generation算法改进为了解决大规模线性规划问题。在重复使用单纯形法(Simplex Algorithm)解决大多数的线性规划问题，发现很多的列(变量)是多余的，基于这样的事实，提出主要问题包含最少的活动列(基本矩阵basis)，然后使用子问题去生成列(变量)填入基本矩阵来改进目标函数。
1.需要条件

线性规划的约束矩阵必须具有特殊的形式，约束集合必须被定义为connecting, coupling, complicating三种约束且约束系数不为零。剩下约束被建立为系数不为零的独立子矩阵，简单的描述：

其中D矩阵表示的是耦合约束关系而F表示独立的子矩阵。

2.算法的步骤

1. Starting with a feasible solution to the reduced master program, formulate new objective functions for each subproblem such that the subproblems will offer solutions that improve the current objective of the master program.

1.建立已简化矩阵的可行解，公式化子问题的目标函数，子问题的解会改善主规划的目标；

2. Subproblems are re-solved given their new objective functions. An optimal value for each subproblem is offered to the master program.

2.重新计算子问题新的目标函数，每一个子问题的解提供给主规划；

3. The master program incorporates one or all of the new columns generated by the solutions to the subproblems based on those columns' respective ability to improve the original problem's objective.

3.主规划集成1个或者所有新列，这些新列由子问题根据自身优化生成的解，从而来改进初始主规划的目标函数。

4. Master program performs x iterations of the simplex algorithm, where x is the number of columns incorporated.

4.主规划重复x的单纯形法的迭代，x表示的列已经被集成进去了为止；

5. If objective is improved, goto step 1. Else, continue.

5.主规划的目标函数被优化，否则继续循环；

6. The master program cannot be further improved by any new columns from the subproblems, thus return.

6.通过改进各个子问题的目标解，主规划还不能被继续优化，那么返回。

3.应用

Dantzig–Wolfe decomposition在数学建模语言AMPL、GAMS得到过实现，该算法如果子问题目标解完全独立，那么可以对子问题平行同时处理。

参考文献：

[1]George B. Dantzig and Philip Wolfe. Decomposition Principle for Linear Programs. Operations Research 8 (1960) pp 101–111

[2]wiki英文介绍：http://en.wikipedia.org/wiki/Dantzig%E2%80%93Wolfe_decomposition

转载本文请联系原作者获取授权，同时请注明本文来自方晓汾科学网博客。
链接地址：https://blog.sciencenet.cn/blog-87352-313745.html

上一篇：简单的flex-java的程序
下一篇：多属性决策问题(Multi-attribute Decision-making Problem)