基于单纯形法的线性规划问题改进解法

依据单纯形法解决问题的思路,提出一种关于解决线性规划问题的改进算法-表上矩形作业法.通过对表上矩形作业法思路及实际应用的阐述,得出了其相对于单纯形法的优缺点.     

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

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

对偶单纯形法的一个注记

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

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

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

改进单纯形表算法

改进单纯形法,是求解线性规划问题的主要算法之一,与一般单纯形法相比,具有节约计算机内存,计算速度快等优点,但在教学中,却不象一般单纯形法,有单纯形表可循,通过表的计算便可掌握算法要领,改进单纯形的学习,需按照算法,一步一步地迭代,既繁琐,又容易出错,难于掌握。所述改进单纯形表算法,采用表上作业,便于初学者对改进单纯形法的理解。该算法可作为改进单纯形法的过渡算法在教学中使用,也可以直接用于求解线性规划的实际问题。     

单纯形法的改进及其应用

利用单纯形法的思想,将现有的单纯形法进行改进,给出单纯形表的矩阵形式,用矩阵的行的初等变换来实现求解过程,使方法更容易理解和掌握,求解过程更简捷,并通过例子来展示此种方法的优越性。     

用"规划求解"工具求解线性规划

线性规划问题的求解方法,各教材中都是重点介绍单纯形法,这种方法通过建立初始单纯形表,并对其进行叠代计算,可以求得问题的解,但由于是手工操作往往比较繁锁,本文针对微型计算机在我国普及程度越来越广这一事实,介绍一个用微型计算机求解线性规划的方法。     

构造LP初始单纯形表的虚拟方法及其迭代步骤

通过对单纯形法的分析 ,给出了构造初始单纯形表的虚拟方法 ,同时提出了几条优化的原则     

单纯形方法和对偶单纯形方法的一个注记

对于每一个线性规划问题,证明了仅在一张单纯形表中采用单纯形法或对偶单纯形法就可以把该线性规划问题和它的对偶问题求解出来,同时用Lingo加以了验证。     

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

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

线性规划的一种外点单纯形算法

提出了一种求解线性规划(LP) 的改进的单纯形法，其迭代过程产生的一部分极点可能出现在可行域外成为不可行极点，因此称之为外点单纯形法.虽然该方法还不能通过复杂性分析证明只需至多n次迭代便可收敛到最优解，但比较Dantzig的沿可行域内边界进行的单纯形法，一般能更快地迭代到达最优点，且在选择旋转主元时，计算量只有温和的增加.     

单纯形最佳主元法的几点重要注记

通过理论分析和实例验证，对单纯形最佳主元法进行了剖析，指出了人们对这种方法的几点误解．模拟测试结果表明单纯形最佳主元法的运算量与一般单纯形法大致相同．     

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

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

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

提出了一种求解线性规划问题的方法,即对约束Ax=b求初始基可行解时,不必引入人工变量而直接用旋转运算获得,之后利用传统单纯形法求最优解,并给出了该方法的实算例子.     

关于单纯形方法的一点注记

通过高斯－约当消元法,对极小化的标准形式的线性规划问题,求得某个单位矩阵的基B对应的基本解,但此基本解既不是原始问题的可行解,也不是对偶问题的可行解,在此情形下作者给出了直接求解某一类线性规划问题的扩充的单纯形法。     

单纯形法的一种改进

为减少转换次数,节省计算时间及工作量,给出了线性规划问题单纯殂法的一种改进方法。     

一种求解LP问题的两阶段基点迭代转移方法

利用线性规划的线性、几何平面这一两面性结构特点,定义了LP问题的一种特殊基点转移矩阵及其转移运算,并建立了单纯形基点的定向迭代转移模型,从而提出了一种求解LP问题的两阶段基点定向转移搜索方法.另外,借助新提出的可行域局部ε-正则化方法,将退化基点迭代转移转化为非退化基点迭代转移,彻底消除了基点退化对极点转移搜索过程的不利影响.     

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

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

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

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