[科普中国]-丹齐格-沃尔夫分解算法

丹齐格一沃尔夫分解算法(Dantzig-Wolfedecomposition algorithm)是求解可分解的大规模线性规划问题的算法。对于可分解的线性规划问题(称为母规划)，可以分解成几个规模较小的子规划。分解算法的过程是从母规划的一个基可行解开始，作对应的乘数，并将母规划分解成几个子规划。

概念丹齐格一沃尔夫分解算法(Dantzig-Wolfedecomposition algorithm)是求解可分解的大规模线性规划问题的算法。对于可分解的线性规划问题(称为母规划)，可以分解成几个规模较小的子规划。分解算法的过程是从母规划的一个基可行解开始，作对应的乘数，并将母规划分解成几个子规划。通过 解几个子规划来判断这一基可行解是否为最优的。若不是最优的，就利用单纯形法对母规划进行换基迭代，得到一个新的基可行解，再作相应的乘数……经有限次计算就可以得到母规划的最优解。这种把一个大规模的线性规划问题分解成几个有关系的规模较小的规划问题来计算的方法， 最早是福特(Lester Randolph Ford，1927— )和富尔克森 (Delbert Ray Fulkerson，1924—1976)在解多种商品网络流时提出。丹齐格(George Bernard Dantzig，1914—2005)和沃尔夫(Philip Wolfe)在他们工作基础上提出求线性规划问题的分解算法。分解原理已成为解决大系统最优化问题的有力工具。1

线性规划用线性方程或线性不等式规划，由若干约束条件组合并具有一定目标的系统，以求得最优解的数学方法。线性规划是最优化方法之一。用数学语言表达，就是在n个变量(x1，x2，……，xn)必须满足一些线性等式和(或)不等式的条件下，寻求x1，……，xn的一个线性关系的最优解。如在一定的人力、物力、财力、时间等条件下，寻求完成最大的任务量或最小的支出。这个方法是在1947年，美国学者丹西格提出“单纯形法”以后，作为运筹学的一个分支科目发展起来。线性规划的数学模型主要由两个部分组成：(一)约束条件。即对系统所考虑的控制因素加以限制的条件，或者说该系统达到目标时对各因素的限制条件。(二)目标函数。指系统的最优要求。目标为极大化，则目标函数值取极大值，如利润、产值、产量等;目标若极小化，目标函数值取极小值，如成本、工时、距离等。具体问题线性规划的数学模型是各式各样的，为了方便，人们建立了标准化的约束条件和目标函数的数学模型。线性规划的求解方法主要有图解法和单纯形法。图解法即用几何图形的分析方法求解，简便直观，但只适用于两个变量的线性规划问题。单纯形法的计算基础是线性代数。单纯形法是逐步求解的，先求可行解(也可能没有可行解)，再逐步改善可行解，使目标函数达到极值(最大或最小值)就是最优解。单纯形法借助计算机可以求解成百上千个变量的线性规划。应用线性规划的系统必须具备下列条件：(一)目标函数可以用极值形式表达。(二)达到目标有不同方法可供选择。(三)目标是有限制条件的。(四)约束条件和目标函数能用线性方程表示。(五)模型中的生产活动有比例性和加法性。模型中的变量是非负值。线性规划应用广泛，从技术问题到工农商、运输、军事等计划管理的决策，从小范围的工作安排到宏观的国民经济计划。在大型的社会舆论调查和读者调查的方案设计以及优化中也是适用的。2

应用——大系统问题亦称“大系统”。是现代控制理论的一个重要分支。是指 专门研究那些规模大、层次多、结构杂、因素繁及目标、功能多样，且伴有 随机性质系统的综合自动化、最优化问题的理论、技术和方法。如经济计划 管理系统、大型联合企业生产的计算机系统和管理系统、环境保护系统等。 是控制论、系统工程、运筹学的继续和发展，产生于20世纪70年代，其主要 内容有：对大系统作出各种系统的分析、评价，寻找最优化方案。在对大系 统的分析、综合中，采用“分解——协调”的方法，先将复杂的大系统分解 为若干简单的小系统，实现小系统最优化，然后再根据大系统的总目标，实 现各小系统协调，以便寻得大系统最优化。

丹齐格美国数学家。生于俄勒冈。其父亲T.丹齐格也是一位数学家，曾以发表著作《数，科学的语言》(有中译本)而著称。1936年丹齐格毕业于马里兰大学，之后进入密执安大学攻读研究生课程。1937年成为美国劳工统计局的统计职员，在那里接触到第二次世界大战时期关于美国经济投入产出模型的研究。不久进入伯克利加利福尼亚大学，跟随著名统计学家内曼攻读博士学位。后来由于美国空军组建统计控制中心的需要而中止研究生学业，作为文职人员加入空军。1946年回到伯克利，获得博士学位。之后成为美国空军审计长的一名数学顾问。1952年又转到兰德公司进行研究。20世纪60年代以后到斯坦福大学任教授。丹齐格的主要贡献在线性规划方面。1947年，他首次提出线性规划的名称，他创立的线性规划和单纯形法在经济学、环境科学和统计学中有重要应用，从而在美国得到迅速发展，在世界上也处于领先地位，因此他被冠以“线性规划之父”的头衔。他还研究整数规划和非线性规划，提出对称的对偶性概念，并研究了对偶规划问题。其代表作为《线性规划与推广》(1963)。为了纪念他的贡献，美国工业与应用数学学会和数学规划学会联合设立一种以丹齐格命名的国际奖，奖励在线性规划方面的开创性工作，1982年首次颁奖。

本词条内容贡献者为:

尹维龙 - 副教授 - 哈尔滨工业大学