| 释义 |
丹齐格-沃尔夫分解算法 丹齐格-沃尔夫分解算法 求解可分解的大规模线性规划问题的算法。对于可分解的线性规划问题(称为母规划),可以分解成几个规模较小的子规划。分解算法的过程是从母规划的一个基可行解开始,作对应的乘数,并将母规划分解成几个子规划。通过解几个子规划来判断这一基可行解是否为最优的。若不是最优的,就利用单纯形法对母规划进行换基迭代,得到一个新的基可行解,再作相应的乘数……经有限次计算就可以得到母规划的最优解。这种把一个大规模的线性规划问题分解成几个有关系的规模较小的规划问题来计算的方法,最早是福特(LesterRandolphFord,1927— )和富尔克森(DelbertRayFulkerson,1924—1976)在解多种商品网络流时提出。丹齐格(GeorgeBernardDantzig,1914—2005)和沃尔夫(PhilipWolfe)在他们工作基础上提出求线性规划问题的分解算法。分解原理已成为解决大系统最优化问题的有力工具。出处：管理学卷 • 运 筹 学 • 数学规划 |