分解算法(decomposition algorithm),理学-数学-运筹学-线性规划,分解算法是解决大规模线性规划的重要方法,其基本思想是将原来大规模问题分解成一系列子问题,通过求解子问题来改进解,最终导出原问题的解。一个简单例子是当系数矩阵是块对角矩阵时,原问题就等价于求解一系列的线性规划子问题。由美国数学家G.B.丹齐克和P.沃尔夫(Philip Wolfe,美国,1927-8-11∼2016-12-29)在1960年提出的Dantzig-Wolfe分解算法是其中最重要一种。设和。Dantzig-Wolfe分解算法首先将(P)的约束分解成两个集合和的交;利用凸多面体的表示定理,中的点可表示为式中和分别是的极点和极方向;由此可将规划(P)等价写为关于变量的线性规划,称为主规划。