A Primal-Dual Simplex Algorithm for Solving Linear Programming Problems with Symmetric Trapezoidal Fuzzy Numbers

Two existing methods for solving a class of fuzzy linear programming (FLP) problems involving symmetric trapezoidal fuzzy numbers without converting them to crisp linear programming problems are the fuzzy primal simplex method proposed by Ganesan and Veeramani [1] and the fuzzy dual simplex method proposed by Ebrahimnejad and Nasseri [2]. The former method is not applicable when a primal basic feasible solution is not easily at hand and the later method needs to an initial dual basic feasible solution. In this paper, we develop a novel approach namely the primal-dual simplex algorithm to overcome mentioned shortcomings. A numerical example is given to illustrate the proposed approach.

参数不定区间估计的对偶线性规划方法

将参数不定区间估计 (PIE)问题变换成一组对偶线性规划 (DLP)问题 ,提出了求解这组DLP问题的改进单纯形方法 .该方法利用变量间的对偶关系 ,直接计算初始基本可行解 ,省去了初始基本可行解的搜索步骤 .此外 ,在确定旋入和旋出变量时都采用了目标值最大减少规则 ,减少了旋转迭代次数 .针对由PIE问题所导出的全部DLP问题都具有相同的目标函数和约束矩阵 ,给出了单搜索过程求解全部DLP问题的联合单纯形法 .

对偶单纯形法的一个注记

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

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

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

关于使用最大改进规则的对偶单纯形算法

本文举例证明了文 [3]的定理 10 - 1是错误的。

求解线性规划问题的一种新方法

本文介绍一种求解线性规划问题的新方法,该方法的特点是初始基不必是可行基。

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

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

可控负荷与混合储能的集成控制与优化方法

目前的研究中,微电网中负荷与储能、分布式电源运行控制之间的结合不够紧密,缺乏储荷间的一体化控制方法,以减小微电网对储能系统的依赖,降低对混合储能系统配置的容量需求。提出了一种可控负荷与混合储能的集成控制方法,设计负荷储能混合控制系统(HLSS),详细介绍了HLSS的结构,控制流程,就HLSS内部功率最优分配策略进行重点叙述,综合考虑微电网功率平衡、用户体验与经济运行,建立采用基于对偶单纯型的两段式迭代算法求解的多目标优化模型。仿真表明,CL可以解决HESS大容量应用时的高成本问题,而HESS的精确调节性能可以补偿CL的非线性功率特性。

关于求线性规划初始正则解的一个新方法的注记

在线性规划问题的求解中,对基变量取负值的情形,文献[6]提出一种求初始正则解的新方法.该文对这种方法作了进一步讨论,指出它实质上是由原有单纯形法和对偶单纯形法两个阶段组成.第一阶段通过引入非负右手边向量构造辅助线性规划问题,然后用单纯形法求解这个辅助问题获得原问题的一个正则解(如果存在);第二阶段由此正则解出发,用对偶单纯形法求得原问题的最优解(如果存在).通过大规模例子对这种算法进行数值试验,结果表明它的计算效率非常低,因而对这种方法进行了改进.

线性规划的原始松弛——对偶MBU单纯形算法

线性最优化广泛应用于经济与管理的各个领域.对于含有等式约束的线性规划问题,单纯形算法需要构造辅助的第一阶段问题求得问题的一个可行基.本文提出了一种原始松弛—对偶MBU单纯形算法(来求解第一阶段问题).首先,忽略不等式约束构造一个原始可行的松弛子问题,再用原始单纯形法求解该子问题;然后用对偶MBU单纯形法求解第一阶段问题.通过大规模数值试验对这种算法进行计算检验,数值结果表明,与经典单纯形算法相比,本文所提出的算法简便可行且具有更高的计算效率.

寻求线性规划初始可行基的一种新算法

本文将单纯形法与对偶单纯形法及其思想结合运用，通过构造变动的目标函数，在不引入（或少引入）人工变量的情况下，探索出一种寻求线性规划初始可行基的新算法。

线性规划的符号跟踪算法

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

线性规划初始对偶可行基本解的一种求法

运用对偶单纯形法求解线性规划问题时,需要先给定一个初始对偶可行的基本解.然而在线性规划问题的约束条件Ax=b中,矩阵A一般不含m阶单位矩阵,此时初始对偶可行的基本解不易求得.文中通过对线性规划问题增加人工变量和一个约束条件,给出一步便能求出其初始对偶可行基本解的简便方法,进而通过对偶单纯形法进行迭代解决线性规划问题.

关于“线性规划的符号跟踪算法”的注记

指出"线性规划的符号跟踪算法"实际上是第一阶段单纯形算法的一种变式,所获得的初始基有4种可能情况,并通过反例进行了说明。由此初始基出发,为使符号跟踪算法能正常运行下去,对该算法的步骤作了修正和补充。为了进一步验证符号跟踪算法的计算性能,通过MATLAB编程在计算机上实现大规模数值试验。结果表明,与经典单纯形算法相比,符号跟踪算法平均每次迭代花费更多的执行时间,计算效率较低。

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

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

规范形式LP问题的改进对偶单纯形法

通过分析对偶单纯形法迭代的实质,就所给LP问题的规范形式,不引进剩余变量而直接得出另一种改进的对偶单纯形法,使变量个数不增且运算规模缩小.

对偶单纯形两阶段法

在用对偶单纯形法解线性规划问题时,必须找到初始正则解.为避免人工约束的引入,利用变量代换,给出不增加变量个数的对偶单纯形两阶段法.

变量有界线性目标规划的对偶算法

本文讨论了变量有界的线性目标规划问题,给出了求解这类问题的一个对偶算法,此方法与变量有界线性规划问题的对偶算法相类似。文中证明了算法的有效性,并举例说明了计算过程。

对于单纯形法矩阵描述的认识

从修正单纯形法的提出、对偶单纯形法的出现、对偶问题最优解的确定以及灵敏度分析的基本依据等四个方面阐述了对单纯形法矩阵描述的认识,充分显示出单纯形法矩阵描述在线性规划发展中的重要性.

目标超平面上的一种原始-对偶单纯形算法

对于目标最优值已知的情形,提出一次迭代到目标超平面上获得相应的对偶可行基,然后应用Samaras等的原始-对偶算法在目标超平面上进行对偶迭代.在确定枢轴列时,采用无比值检验方法,节省了计算工作量.为防止Samaras等的原始-对偶算法在原始可行点退化情形下可能发生的循环现象,加快迭代进程,引入MBU对偶单纯形算法进行迭代,直到对偶间隙严格缩少.中大规模数值试验结果表明,与经典单纯形算法相比,该算法在大部分算例上使用更少的迭代次数和执行时间,具有更高的计算效率.