两类特殊线性规划算法的改进

本文拟将对线性规划中的对偶单纯形法和运输问题中的表上作业法中选取出基变量或者入基变量的准则进行改进,给出一种新的换基准则,按该方法进行优化运算,可以使这种两种算法的迭代次数减到最少,从而加快运算速度.尤其适合于大系统线性规划问题的求解.     

单纯形法换基准则有效性的讨论

单纯形法是求解线性规划问题的一种实用方法,换基准则对单纯形法的有效性起着重要作用,文章分析了文献2中提出的“单纯形最佳主元法”结论的欠妥,给出了判定单纯形法最有效迭代算法的充分条件,提出了求解线性规划问题改进的方向。     

约束条件含模糊数的线性规划的一种求解方法

讨论了约束条件中系数是模糊数的模糊线性规划的一种解法,利用Roubens的模糊数比较的概念,把系数是模糊数的线性规划问题转化为经典的线性规划问题,从而利用求解线性规划的单纯形法求解此类模糊线性规划．最后给出此种方法在实际中的应用．     

关于线性规划初始基本可行解的构造

最近,Smale证得,采用单纯形法求解线性规划问题,在概率平均意义下,转轴次数为变量数目的线性函数[1]。这一进展从理论上保证了采用单纯形法作为大型计算问题中的通用子程序的有效性。例如,在大型分枝定界问题中就是如此。因而,有必要对单纯形法的计算格式进行精细的研究。1984年,晏晓焰和李 从改进传统的两步法入手,提出计算线性规划问题初始基本可行解的一种简化算法。其基本结果表述为 定理1.设(LP)为标准形式的线性规划问题 (LP)min CTx S.T.Ax=b x≥0,则至多经过一次求逆运算和两次取主运算,可将A的增广矩阵化为其中m1=r(A),b≥0. …     

对偶单纯形法的一个注记

针对运筹学教学难点--对偶单纯形法,通过讨论证明了单纯形表中的列可以视为对偶问题的非基变量的检验数,并讨论了在对偶单纯形法迭代过程中的进基变量与出基变量的确定原则亦如同在单纯形法迭代过程中进基变量与出基变量的确定原则,得出结论是对偶单纯形法本质上就是单纯形法,只是在运用对偶单纯形法解线性规划时需要将单纯形表旋转90°.     

求解线性规划问题的单纯形“双进基”法

该文对线性规划问题中的单纯形法作了另一种改进，得到一种每次迭代两个非基变量“进基”，两个基变量“离基”的双进基法．其结果能用矩阵表示，迭代的步骤也并不比单纯形法复杂，但其迭代的次数要比单纯形法减少一半，如果一个线性规划用“单进基”法要迭代２ｎ次（２ｎ＋１次），那么，用“双进基”法只须迭代ｎ次（ｎ＋１次），从而加快了收敛于最优解的速度．     

求解线性规划问题最优解时常遇到的几种特殊情况

重点介绍了单纯形法在求解过程中常遇到的几种特殊情况.首先,在一个线性规划问题的最优解对应的单纯形表中,如果至少有一个非基变量的检验数为零,那么该线性规划问题的最优解可能不只一个,当求到另一个最优解时,则原问题必有多重最优解;其次,在单纯形表中,如果某一负检验数所对应的列向量的分量全部非正,则原问题无最优解;再次,在求解过程中,若原问题不可行,而对偶问题可行时,我们可以应用对偶单纯形法进行求解.     

对偶单纯形算法的改进

考虑问题(LP) (?)定义1设(?)(1)是(LP)的一组基,对应的基阵是B,对应的基解为(?),如果(LP)的检验数全部非正,即C_BB~-A-C≤0则称(1)式是问题(LP)的正则基,称X~0是(LP)的正则解。定义2如果线性规划问题(LP)的任意一个正则基所对应的非基变量的检验数都严格小于零,则称它的对偶问题是非退化。     

约束条件中含有梯形模糊数的线性规划的求解方法

利用一种新的模糊数排序准则,将约束条件中含有梯形模糊数的模糊线性规划转化为经典的线性规划,进而求得了原模糊线性规划的最优解.与现有方法相比,该方法运算简便,得到的经典线性规划约束条件个数少,降低了计算量,但最优解的质量没有降低.最后给出了此种方法在实际问题中的应用.     

解线性规划问题的一种半单纯形法

本文提出解线性规划问题的一种方法，主要是对约束Ａｘ＝ｂ求初始基可行解时，不必引入人工变量而可直接用旋转运算获得，之后就完全和单纯形法一样求最优解，并提出了判定无可行解的方法和准则，对算法的理论问题也作了证明和解释。     

单纯形方法中转轴运算的新法则

本文借助于一类有向图中最短路的直观特征与单纯形方法的理论分析,在求解线性规划的单纯形方法中,给出了一个新的转轴法则。新法则不但能减少迭代步数,而且能消除己知的指数算例。同时也得到了Karmarkar算法与其它算法无法比拟的实验结果。     

二分单纯形算法中子规划的改进

二分单纯形算法中,线性规划问题的最优解是通过求解一系列子问题来实现的,本文针对二分单纯形算法中的子规划问题作进一步研究,提出了一个新的了规划问题来改善问题的不可行性,并确定出了相应的主元旋转规则,给出了相应的子算法,同时进行了数值实验,实验结果表明,调用新子算的二分法与原始二分法相比,迭代次数和计算时间均有所改善,可视为原始二分算法的一种改进算法。     

关于解线性规划问题的一种半单纯形法的注记

指出某文献解线性规划问题的一种半单纯形法的定理2是错误的,给出了理论分析和实例说明.进一步分析发现,所谓的＂半单纯形法＂与经典的两阶段法本质上是相同的,只不过人工变量没有显示出来,枢轴列的选择准则稍有不同.为此,本文在枢轴行和枢轴列的选择上对半单纯形法（或两阶段法第一阶段）进行了改进,数值试验结果表明,改进后的单纯形算法在计算效率上明显优于半单纯形法.     

关于解线性规划问题的一种半单纯形法的注记

指出某文献解线性规划问题的一种半单纯形法的定理2是错误的,给出了理论分析和实例说明.进一步分析发现,所谓的＂半单纯形法＂与经典的两阶段法本质上是相同的,只不过人工变量没有显示出来,枢轴列的选择准则稍有不同.为此,本文在枢轴行和枢轴列的选择上对半单纯形法（或两阶段法第一阶段）进行了改进,数值试验结果表明,改进后的单纯形算...     

求解高维凸二次规划的向量锥方法

本文介绍一种求解高维凸二次规划的可行方向方法．该方法的可行下降方向是由ε有效广义约束向量所张成的锥构造的，它可通过求解一个低维的线性规划得到．最优步长可由简单的公式给出，不必进行精确的线性搜索。只要在最优点处的有效约束数少于４０个，采用本文方法求解高维凸二次规划就具有计算量少，机时节省的优点．对文中给定的算例，向量锥方法比Ｌｅｍｋｅ 互补旋转法，Ｗｏｌｆｅ既约梯度法和Ｗｏｌｆｅ方法节省机时约７０－８０％．     

线性规划问题的基元素可交换性分析

本文讨论了线性规划问题基元素的可交换性,从理论上阐述了具有n个规划变量,m个约束条件的标准形式的线性规划问题,它的基本可行解的个数不超过从n个向量中每次取出m个不同向量的组合数.从而为线性规划问题的单纯形解法提供了理论依据.     

解线性规划的广义起作用集法

给出了解线性规划的广义起作用集法。从极点出发的搜索方向是该点处所有下降棱方向的一种凸组合。一般情况下,迭代路径置于容许集的表面上,而不是象单纯形法那样迭代点沿着棱移动。由于广义方法的迭代通常要跳过一些极点,因此收敛速度比单纯形法有明显的提高。     

一种线性规划问题单纯形法的改进算法

目的降低用单纯形法求解线性规划问题时计算机的运算量和存储量。方法基于高斯消元法和试算法的思想,在不用引入人造基的前提下,对算法进行改进。结果提出了一种改进的算法,并对算法进行了详细的分析。结论该算法能有效的避免循环,数值试验表明了该算法的有效性。     

变量有上界的线性规划的对偶单纯形方法

给出变量有上界的线性规划问题的对偶单纯形算法, 该算法包含了一般线性规划问题的对偶单纯形算法, 为解变量有上界的线性规划问题提供了又一种方法.     

求解线性规划的单纯形方法与折线搜索技术

本文给出了一个求解线性规划的折线搜索法,该方法是在单纯形方法中增加了折线搜索技术。新方法能够减少迭代次数,也能消除已有的指数算例。