线性规划问题的算法综述

综述了线性规划问题近年来的算法研究最新进展,给出了一些典型算法的求解思想及其时间复杂度,综合分析了各算法的优缺点。并为后续研究提供了一个借鉴方向。     

线性规划的无比值检验criss-CROSS算法

Zionts提出的求解线性规划问题的criss-cross算法实际是一阶段算法,不过与传统一阶段算法不同,它交替进行原始和对偶迭代,而产生的既可以是原始可行解,也可以是对偶可行解.为了提高计算效率,文章提出了一种采用无比值检验规则的新criss-crOss算法,基于新算法编制的一个稠密软件在对40个小问题进行的数值试验中,就迭代次数而言,以2.12的比率胜过了传统的两阶段算法.     

求解线性规划的一个非内点算法

利用NCP函数和光滑化方法将线性规划的K-K-T条件化为一个光滑方程组,构造了一个非内点原-对偶路径跟踪算法,并分析了其全局及局部收敛性;同时通过计算标准线性规划考题,验证了它的可行性及有效性。     

简单线性规划问题的一种新算法

在线性规划问题逐维选优强多项式算法的基础上,结合简单线性规划问题的特性,提出了线性规划问题的分块选优算法:根据目标函数梯度在可行域的低维约束平面上投影,确定它在可行域内的等值面,得出简单线性规划问题的最优解集.     

大型0—1目标规划的启发式算法

提出了一个０－１线性目标规划新的启发式算法,该算法以新的算法准则及评价标准,改进了旧算法中的系数限制,并能通用于任何０－１线性目标规划问题,特别能够有效地解决大规模０－１线性目标规划问题。     

多目标线性规划的交互式线性加权内点算法

将内点算法应用于多目标规划的交互方法中,提出一种基于线性加权评价函数的解决多目标线性规划问题的新算法。在利用内点算法进行迭代计算的过程中,不断根据决策者的当前偏好信息随时修正权重系数,逐步引导迭代过程达到决策者满意的解。     

求解一类互补问题的不可行内点法与其计算复杂性

给出了求解一类非单调线性互补问题的不可行行内点法的基本步骤,证明了该算法的收敛性,讨论了算法的计算复杂性,给出了进求解单调性互补问题的不可行内点法的推广。     

法向消元和线性规划强多项式算法

为了求最优集(不只是求零维的最优点),提出了行满秩线性代数方程组的法向消元解法,指出它与点和法向量组的逐次投影等价,并进一步将其发展成最小投影法,用来判定原始等式约束平面和若干坐标超平面的交的可行性;通过逐次投影在等式约束平面上建立序结构,逐维选优和判定可行性,使线性规划单纯形迭代解法所进行的Rn空间中平面组合穷举的计算变成逐次降维的等式约束平面上低维平面的形和位判定的代数计算,得到线性规划问题的低于O(mn3)的强多项式直接算法.     

多目标线性规划的模糊折衷算法

通过推广求解多目标线性规划问题的平均算子法,提出了多目标线性规划的模糊折衷算法,证明了多目标线性规划的模糊折衷算法求得的解是有效解.此外,提出了多目标线性规划的两阶段算法,即:若多目标线性规划的模糊折衷算法指定的最小满意度不恰当,则可能会导致交互过程复杂化;若用最小算子法求得的解作为多目标线性规划模糊折衷算法中决策者指定的目标函数最小满意度,则可能使多目标线性规划的模糊折衷算法的计算量减小,另一方面能够弥补最大(最小)算子法求得的解可能为非有效解的不足.此外,用实例验证了多目标线性规划两阶段算法求得的解为有效解.     

对偶线性规划问题的一类解法

通过线性互补问题(LCP)的一个等价系统——Pang函数的区间斜率的构造，得到了LCP问题的Krawczyk区间算子的迭代算法，证明了该算法是可以在计算机上得以确认的一种检验方法；同时阐述了如何将对偶线性规划问题转化为LCP问题的方法，由此获得计算对偶线性规划问题的区间迭代算法，由算例可知，其数值结果是很好的。     

一类不可微多目标规划的Kuhn－Tucker条件的充分必要性

对一类不可微多目标规划进行了讨论，得出了广义Ｋｕｈｎ－Ｔｕｃｋｅｒ条件是有效解的必要条件，并证明了对于目标及约束满足广义伪凸或正则拟凸条件的多目标规划，广义Ｋｕｈｎ－Ｔｕｃｋｅｒ条件也是有效解的充分条件。     

框式凸二次规划宽邻域原始-对偶势下降内点算法

基于线性规划原始-对偶势下降内点算法的思想,对框式凸二次规划提出一种新的内点算法宽邻域原始-对偶势下降内点算法.算法选取牛顿方向作为迭代方向,利用势函数选择迭代步长,分析算法的多项式迭代复杂性,并证明新算法具有较好的迭代复杂性O(nL).     

一类灰色二层线性多目标规划问题及其算法

将下层带多目标函数的二层线性规划与灰色理论相结合,提出了一类灰色二层线性多目标规划问题,给出了该问题的数学模型和相关概念。在约束域为非空紧集的条件下,证明了漂移型灰色二层线性多目标规划问题的最优解一定可以在约束域的极点达到,并提出了一个基于k次最好法的求解算法,证明了该算法具有全局收敛性,算例分析验证了所提算法是有效的。     

基于多目标规划和业务区分的多QoS约束路由算法

针对大多数QoS路由选择算法所存在的问题,采用多目标规划和业务区分的方法建立了满足多QoS需求和网络资源利用率的路由选择数学模型,对Fallback＋算法作了进一步扩充和改善．提出了一种新的Fallback＋＋算法,它不仅能满足多QoS约束,而且能高效地利用网络通信资源．分析得出该算法的时间复杂度和空间复杂度均为O（n＊N^2）．仿真实验验证了该模型和算法的有效性和正确性．     

二阶锥规划的Lagrange对偶及2维原始对偶单纯形法

目前对二阶锥规划算法的研究是数学规划领域的研究热点之一,在这方面的研究成果初具规模.文中着重研究两方面问题:一是详细推导二阶锥规划的Lagrange对偶问题;二是将2维二阶锥规划(即二阶锥约束都是2维的,但自变量的总维数是2r维的,r表示二阶锥约束的个数)转化成相应的标准形线性规划,给出其原始对偶单纯形法,并举例说明算法的应用,最后进行部分灵敏度分析.这一工作基本完善了2维二阶锥规划的单纯形类方法,即至此,2维二阶锥规划的原始单纯形法、对偶单纯形法和原始对偶单纯形法的理论已较完善.其他拓广的单纯形类方法可在将2维二阶锥规划转化成相应的标准形线性规划之后对应线性规划的拓广单纯形类方法直接得到.     

多目标0 1规划的元胞竞争决策算法

将元胞演化规则与竞争决策算法相结合,提出了一种求解多目标0-1规划问题的元胞竞争决策算法.大量数据测试和验证表明,该算法能有效提高非劣解的分布性和多样性.     

线性互补问题的一种混合整数线性规划解法

经典算法一般采用迭代过程求解线性互补问题,研究了线性互补问题的直接求解方法。把线性互补问题转化为一个混合整数线性规划,然后采用数学软件进行求解;数值实验结果表明,所给出的方法能够准确快速地求得原问题的最优解。     

一类无约束二层规划问题的区间算法

讨论了目标函数为一阶连续可微函数的无约束二层规划问题的区间算法,构造了二层规划问题目标函数的区间扩张和无解区域删除检验原则,建立了求解无约束二层规划问题的区间算法,并进行了数值实验。理论证明和数值实验均表明算法是可靠和有效的。     

线性规划的原-对偶内点算法数值实验初步

利用原-对偶内点算法的思想,初步给出了该算法的数值例子,对已有结果做了一个重要的补充。     

非单调线性互补问题的宽邻域预估校正算法

对P*(κ)阵线性互补问题提出了一种新的宽邻域预估校正内点算法.该算法是基于Mehrotra型预估校正算法思想,把线性规划问题拓展到非单调线性互补问题中(P*(κ)-LCP),并讨论了其计算复杂性.分析结果表明,所给算法是多项式时间算法.最后通过数值实验验证了算法的有效性.