基于线性规划核心矩阵的单纯形算法

本文讨论了线性规划中的核心矩阵及其特性,探讨了利用核心矩阵实现单纯形算法的可能性,并进一步提出了一个基于核心矩阵的两阶段原始一对偶单纯形方法,该方法通过原始和对偶两个阶段的迭代,可以在有限次迭代中收敛到原问题的最优解或证明问题无解或无界．在试验的22个问题中,该算法的计算效率总体优于基于传统单纯形方法的MINOS软件．     

基于线性规划核心矩阵的单线形算法

本文讨论了线性规划中的核心矩阵及其特性,探讨了利用核心矩阵实现单纯形算法的可能性,并刊一步提出了一个基于核心矩阵的两阶段原始－对偶单纯形方法,该方法通过原始和对偶两个阶段的迭代,可以在有限次迭代中收敛到原问题的最优解或证明问题无解或无界。在试验的２２个问题中,该算法的计算效率总体优于基于传统单纯形方法的ＭＩＮＯＳ软件。     

基于最钝角规则的亏基对偶单纯形Ⅰ阶段算法

对偶单纯形算法或原始对偶单纯形算法都需要一个初始对偶可行基．就此目的而言，基于最钝角行主元规则的对偶Ⅰ阶段算法非常有效[15].本文将其思想应用于亏基情形，建立一个不含比值检验的新的亏基对偶Ⅰ价段算法．初步的数值实验表明，该算法可在总体上减少运行时间和迭代次数，极具竞争性．     

单纯形算法的两种部分定价策略

根据Hu和Johnson的原始一对偶单纯形算法原理,提出了两种部分定价策略.给定一组原始一对偶可行解,首先,选择与原始问题简约价值系数为负且对偶松弛变量取零值相应的非基变量作为部分定价变量,再用Dantzig准则的单纯形算法求解该原始子问题.其次,针对原始退化问题,选择相应于原始问题简约价值系数小于某个适当小正数的非基变量进行部分定价,然后应用Bland准则的单纯形算法求解原始子问题,以克服退化可能引起的循环现象.最后,对来自NETLIB和MIPLIB的一些典型算例执行初步数值试验,结果表明,与经典单纯形算法相比,提出的算法具有更好的计算表现.     

线性规划的目标函数最速递减算法

在对偶单纯形方法的基础上，提出了线性规划的目标函数最速递减算法。它避开求初始可行基或初始基，以目标函数全局快速递减作为选基准则，将选基过程与换基迭代合二为一，从而大大减少了迭代次数。数值算例显示了该算法的有效性和优越性。     

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

基于单纯形方法的双层线性规划全局优化算法

通过分析双层线性规划可行域的结构特征和全局最优解在约束域的极点上达到这一特性,对单纯形方法中进基变量的选取法则进行适当修改后,给出了一个求解双层线性规划局部最优解方法,然后引进上层目标函数对应的一种割平面约束来修正当前局部最优解,直到求得双层线性规划的全局最优解.提出的算法具有全局收敛性,并通过算例说明了算法的求解过程.     

一类带反凸约束的非线性比式和问题的全局优化算法

本文针对一类带有反凸约束的非线性比式和分式规划问题,提出一种求其全局最优解的单纯形分支和对偶定界算法.该算法利用Lagrange对偶理论将其中关键的定界问题转化为一系列易于求解的线性规划问题.收敛性分析和数值算例均表明提出的算法是可行的.     

双层规划问题基于对偶理论的遗传算法

针对下层为线性规划的非线性双层规划问题，提出了一种基于下层对偶理论的遗传算法。首先利用下层对偶问题可行域的极点对上层变量的取值域进行划分，使得每一个划分区域对应一个极点。根据原一对偶问题最优解的关系，确定每个划分区域对应的下层最优解。其次利用罚函数方法处理了上层约束，设计了一个依赖于种群变化的动态罚因子。对20个测试问题的数值结果表明，所提出的算法是可行有效的。     

线性规划的最钝角松弛算法

本文提出一个基于最钝角原理的松弛算法求解线性规划问题。该算法依据最钝角原理略去部分约束得到一个规模较小的子问题,用原始单纯形算法解之;再添加所略去的约束恢复原问题,若此时全部约束条件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解。初步的数值试验表明,新算法比传统两阶段单纯形算法快得多。     

线性约束凸规划的鞍梯度法

求线性约束凸规划问题的最优解。方法：在鞍梯度法的基础上提出了一个具有全局收敛性的原一对偶外点算法。结果：每步迭代利用Lagrange函数的鞍梯度构造搜索方向，生成次可行解序列，由此得到的序列的极限就是原-对偶问题的最优解。结论：即使从原一对偶问题的不可行点开始迭代算法也收敛。     

求解约束规划的一个非线性Lagrange函数

本文提出了一个求解不等式约束优化问题的非线性Lagrange函数,并构造了基于该函数的对偶算法.证明了当参数σ小于某一阈值σ_0时,由算法生成的原始-对偶点列是局部收敛的,并给出了原始-对偶解的误差估计.此外,建立了基于该函数的对偶理论.最后给出了算法的数值结果.     

正定二次规划的一个对偶算法

给出了一个正定二次规划的对偶算法．算法把原问题分解为一系列子问题,在保持原问题的Wolfe对偶可行的前提下,通过迭代计算,由这一系列子问题的最优解向原问题的最优解逼近．同时给出了算法的有限收敛性．     

基于亏基的摄动原始单纯形Ⅰ阶段算法

通过摄动技术来使问题强制获得对偶可行性,执行亏基对偶单纯形算法得到一个原始可行基,并采用修正的主元规则,以充分发挥这两种算法的优势,从而为亏基原始单纯形算法提供一个新的I阶段算法,以使其进一步克服退化所带来的困扰.初步的数值试验表明,亏基和摄动两种算法优势的结合,能有效地克服退化的影响,能有效地减少总迭代次数和运行时间,其效率远远优于传统两阶段单纯形算法.     

互补基解性质的应用研究

对线性规划互补基解性质进行了研究,得到了由线性规划问题最优基对应的单纯形表直接获得对偶线性规划问题最优基对应的单纯形表的一个有效方法,给出了应用实例.     

线性规划的约束条件“滚雪球”算法

为使线性规划的每个约束条件部分或全部地拥有原整个约束条件所包含的信息,将线性规划的约束条件“滚雪球”后得到与原约束条件等价的新约束条件,对新约束条件所构成的线性规划采用目标函数最速递减算法.有一定规模的随机数值算例显示了该算法只需进行m(约束条件数)次迭代即可求得最优解.     

一种改进的双层规划内点算法(英文)

本文针对线性双层规划问题提出一个由KMY算法演变而来的原对偶内点算法.与现在很多线性双层规划单纯型算法不同,作者提出的算法从一可行初始点穿过约束多面体内部直接得到近似最优解,当约束条件和变量数目增加时,本算法的迭代次数和计算时间变化很小.所以大大提高实际可操作性能和运算效率.     

线性规划无穷多最优解的讨论

利用线性规划单纯形表对线性规划原问题存在无穷多最优解和对偶问题存在无穷多最优解的情况进行了讨论,并分析了对偶问题存在无穷多最优解情况下的影子价格的方向性。最后以实例说明了各种情况。对初学者加深理解及决策者决策参考有一定帮助     

竞争市场均衡问题的内点算法

本文应用最优化方法求解经济学中的经典问题-竞争市场均衡问题.本文对Ye的算法(Ye首先提出了解Fisher问题的原始-对偶路径跟踪算法)做了改进,分别给出了步长调整和迭代方向分解后的原始-对偶路径跟踪算法,并对算法做了理论证明和复杂性分析.最后分析了初始点的求法,做了初步的数值计算.计算结果表明算法能在有效时间内求得问题的解.     

单纯形法解装卸工问题

本文提出装卸工问题,对一种特殊情况下的装卸工问题用单纯形方法求得了它的最优解和最优值.