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

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

树形异构网格的启发任务调度算法

讨论了在网格资源计算能力和网络通信速度异构的树形网格环境下任务调度问题,导出了线性方程并且根据调度任务大小进行了模型的优化,提出一个基于线性规划的任务分配启发式算法。实验结果表明:在异构树形计算网格环境下实现任务调度时,该算法的性能明显优于其他算法。     

双链路故障时的共享路径保护

在波长路由光网络中,网络的存活性已经受到越来越多的重视.对单链路故障时的保护已经不能满足某些关键性业务对网络存活性的要求,因而研究了双链路故障时的共享路径保护技术.在动态业务下,将共享路径保护问题归结为整数线性规划.在节点无波长转换能力的情况下,分别提出了为当前业务计算最优路径和固定路径两种策略下的整数线性规划.数值结果表明,相对于专用保护,双链路故障时的共享路径保护能够节约30%左右的波长链路资源.     

紧急输送策略的线性规划模型

以美国南弗洛里达州递避飓风袭击为例建立了紧急输送情况下的线性规划模型。其中具体建立了以SCEPD(美国南弗洛里达州紧急情况预防部门)提出的公路反向，地区分块撤离，使用小路等三个最受人们关注的策略的模型。模型的灵敏度分析能很好地解释建立更多的临时避难所、限制车辆等策略对撤离的影响。在相近的环境下，中模型解得的结果很接近官方预测的结果，并且本的模型能对更广泛的情况进行分析．可给SCEPD提供一定参考。     

k-边覆盖对策及其核心

本文针对从图的k-边覆盖问题引出的合作对策模型，利用线性规划对偶理论得到了其核心非空的一个充分条件和构造核心分配的多项式时间算法，并将这一结果推广到了一般的k-集合覆盖对策模型中．     

基于线性规划的最小扰动标准单元合法化算法

在传统的标准单元总体布局完成之后,一个很重要的步骤是消除标准单元之间的重叠,即合法化过程.文章以对总体布局结果的最小扰动为优化目标,考虑标准单元布局合理位置的约束,通过采用线性规划建模求解,有效地解决了布局合法化问题.与启发式算法相比,该模型从理论上给出了对布局造成最小扰动的最优解.实验表明,该合法化算法在ISPD02的例子中基于mPL6的总体布局能够比Fastplace3.0的合法化结果有平均3.8%的线长减少.     

一类扩展线性规划问题的推广

研究文［１］的扩展线性规划问题的更一般的情形：ｍｉｎｚ＝∑ｎｊ＝１ｃｊ｜ｘｊ｜，ｓ．ｔＡｘ＝ｂ，ｘｊ≥０，ｊ∈Ｉ｛１，２，…，ｎ｝。给出其不扩展单纯形表的单纯形算法。     

图的最大二等分问题的非线性规划算法

基于图的最大二等分问题的半定规划松驰模型 ,本文提出一个非线性规划算法求解该模型 ,得到该半定规划松驰模型的一个次优解 ,并且给出算法的收敛性证明 .数值试验表明该方法可以有效地求解图的最大二等分问题的松驰模型