线性规划的分解原则和算法及其并行计算

摘要

1 引 言 并行计算机和并行计算的研究始于七十年代,而并行最优化算法的研究在八十年代中期才得到普遍的重视。近年来随着并行体系结构计算技术的飞速发展,并行最优化的研究也得到迅速的发展,它不仅使求解超大规模最优化问题(包括连续和离散)成为可能,而且对新算法和并行体系计算机结构的研究也产生重要的影响。另一方面,它在军事、工业、交通运输、能源,管理、决策和信息系统的处理等方面均有直接应用的前景,同时它在理论上对运筹学、管理科学、经济决策,系统分析和计算机科学等学科的发展有着重要的推动作用。 本文研究在内点意义下线性规划的分解原则和算法及其并行计算。众所周知,基于单纯形法的线性规划的分解原则是利用凸多面体中的任意一点可以表示为其顶点的凸组合和极射线的非负组合的性质,把原问题转化为求解一系列规模较小的线性规划问题。