一种基于核心矩阵的原始对偶算法

本文通过对线性规划问题中的核心矩阵的分析，提出了一种基于核心矩阵的原始对偶算法。该算法以核心矩阵为运算单元，一方面呈现了存储空间小，计算量小的特点；另一方面，该算法采用了一种新的转轴规则的外点算法，在保持原始可行的基础上，不断改善对偶解使其可行。数值实验结果表明该算法在迭代次数、转轴效率和存储空间上都有一定的提高。     

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

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

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

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

方向选择约束单纯形算法

一、引言人们一直致力于求解线性规划的单纯形算法的改进工作.1976年,Powell 发表过降低基维数的改进单纯形算法,这个算法是将基矩阵的一个块用基矩阵的其它块的乘积来表示,虽然实现了降低基维数,节省了存贮空间,却增加了计算次数,减慢了计算速度.Sethi and Thompson 针对线性规划问题也提出过竞争和非竞争约束(candidate andnoncandidate constraints)的概念.他们发现,随机生成的实验问题,其总约束中大约只有15%—25%是竞争约束,并提出了一个仅对竞争约束进行旋转运算的单纯形算法.他们的算法,对某些特殊的线性规划提高了求解速度,但并不减少基的维数,并不节省内存空间,增加了程序复杂性.1984年,Sethi and Thompson 又提出 PAPA 算法,再次利用线性规划问题通常只有少量竞争约束这个事实来提高求解速度.但 PAPA 算法往往要在原问题的可行域外运行.况且,上面提到的各种算法,均不能从理论上表明,它们较标准改进单纯形算法到底节省了多少存贮单元和节省了多少计算次数.     

线性规划的符号跟踪算法

分析了只含一个约束条件的线性规划最优基变量的特征，将其运用到搜寻含m个约束条件的线性规划的最优基变量，从而提出了线性规划的符号跟踪算法，为线性规划求解提供了新途径。     

二分单纯形算法中子规划问题的进一步研究

本对二分单纯形算法的子规划问题作进一步研究,提出一个新的子规划问题来改善问题的不可行性,并确定了相应的主元旋转规则,并编制了相应于新子规划的新二分算法,并对94个线性规划问题进行了数值实验,实验结果表明,新二分算法是一种改进的二分算法。     

线性规划联合算法的理论与应用

本在[1]的基础上．较系统的叙述了线性规划联合算法的步骤、相关理论及其应用，指出该算法具有避免人工变量、减少迭代次数、使用灵活、应用方便等特点。     

多层线性规划问题的整体优化算法

本文研究了求解多层线性规划问题的整体优化算法,利用流动等值面技术,证明了算法的有限终止性,并给出实际例子验证了算法的有效性.     

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

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

求解线性规划的一种单纯形矩阵法

线性规划的单纯形法一直是运筹学教学中的难点,是求解线性规划的一种重要方法.通过实例从代数角度探讨了单纯形法的迭代思想,提出了用单纯形矩阵求解线性规划的方法.同传统的单纯形表计算比较而言,此方法操作简单,不易出错,为线性规划的求解提供了一种行之有效的方法。