修正单纯形法的计算量的注记

对文献［１］、［２］指出的修正单纯形法的计算量提出了异议,并给出了修正单纯形法应有的计算量。     

线性规划的σj迭代计算方法

本提出并证明了求解线性规划（LP）的单纯形法中检验数（σj）的迭代计算方法的定理,由此定理得到的迭代计算方法比传统的按定义式计算法的渐近时间复杂度降了一级,同时简化了计算过程并提高了计算效率。     

基于单单纯形法的模板优选研究

利用半单纯形法研究了建筑结构施工中各类模板的最优选取问题,建立了各类模板最优组合的数学模型及求解算法。对实际问题的算例表明该方法非常有效。     

线性规划单纯形法主元规则的几何分析

本文研究了线性规划单纯形法和对偶单纯形法主元规则的性质.利用直观的几何方法,结合对偶理论和灵敏度分析,得到了主元规则的特点,针对针对三种最常见的主元规则构造出不同的二维和三维例子,以此说明对每种主元规则都容易构造出其不优的反例,以及迭代次数多于约束个数的例子.所得结果有助于对单纯形法和对偶单纯形法的理解和研究.     

退化模糊变量线性规划的一个改进单纯形法

构造了一个与原始退化问题相关的新问题;结合秩函数,给出并证明了新问题的解与原始问题的解的一些关系;通过改进出基变量的选取方法,提出改进的单纯形法,顺利地求解出原始退化问题的最优解。     

变量有广义界线性规划的叠累单纯形法

本文建立变量有广义界线性规划一个新的转轴算法,称之为叠累单纯形算法,新算法其有三个主要特征：１对于检验数为“坏”的非基变量 ｘｓ,进行一轮子转轴运算,使得ｘｓ进基,转轴中具有“好”的检验数的变量始终保持“好”的检验数;２ｘ．进基的子转轴所产生的基既不是原始可行基,也不是对偶可行基,但子转轴结束时产生的基是原始可行的;３目标函数值在整个转抽运算中是单调下降,从而算法可有限步终止．     

单纯形方法的两个变种

考虑标准形式的线性规划问题: (LP) maxinlize z=c。rz s.t. 4z一6,zJ≥0,J∈E={1,…,w).其中_∈门“‘,6∈胪,c∈彤,且以为行满秩.设有一基矩阵力。::(“,。,…,‰),相应的基变量构成的向量为z一:(zJl,…,z‘)’.引入列指标集t,。=㈦,…,√,。)及填补集瓦=层一J。和行指标集 ,={。l(刀:6)。<0, 。一I,…,Ⅲ) 、 (1)及其补集7={I,…川。)一,.我们_仃如。卜‘类型的子问题: nlax…ze z。三0 ∑孕J (2a); 。∈”H s.t.。口==以:’6一≥:(以=’ⅡJ)zJ; (2b) i虿。a q≥O,V J∈,B; (2c) zj.≥0,V i∈,. (2d)著,非空,取行指标i使得 i:Arg…     

关于多目标线性规划单纯形法中寻找对偶解的讨论

本文我们讨论当用单纯形法得到一个多目标线性规划问题的有效解或弱有效解时,寻找对偶解的条件。     

单纯形法的旋转迭代算法及影子价格

本文对线性规划问题提出一种寻找初始可行基和判定可行解的统一方法，它在运用单纯形法时，在若干情况下不必引入人工变量而可在一种表格之下直接应用旋转运算而获得，之后就在同一张表格下完全和常规单纯形法一样求最优解，此法我们称之为“单纯形法的旋转迭代算法”，应用此法，我们容易求出影子价格。     

Hyper-Sparsity in the Revised Simplex Method and How to Exploit it

The revised simplex method is often the method of choice when solving large scale sparse linear programming problems, particularly when a family of closely-related problems is to be solved. Each iteration of the revised simplex method requires the solution of two linear systems and a matrix vector product. For a significant number of practical problems the result of one or more of these operations is usually sparse, a property we call hyper-sparsity. Analysis of the commonly-used techniques for implementing each step of the revised simplex method shows them to be inefficient when hyper-sparsity is present. Techniques to exploit hyper-sparsity are developed and their performance is compared with the standard techniques. For the subset of our test problems that exhibits hyper-sparsity, the average speedup in solution time is 5.2 when these techniques are used. For this problem set our implementation of the revised simplex method which exploits hyper-sparsity is shown to be competitive with the leading commercial solver and significantly faster than the leading public-domain solver.     

A Piecewise Linear Dual Phase-1 Algorithm for the Simplex Method

A dual phase-1 algorithm for the simplex method that handles all types of variables is presented. In each iteration it maximizes a piecewise linear function of dual infeasibilities in order to make the largest possible step towards dual feasibility with a selected outgoing variable. The algorithm can be viewed as a generalization of traditional phase-1 procedures. It is based on the multiple use of the expensively computed pivot row. By small amount of extra work per iteration, the progress it can make is equivalent to many iterations of the traditional method. While this is its most important feature, it possesses some additional favorable properties, namely, it can be efficient in coping with degeneracy and numerical difficulties. Both theoretical and computational issues are addressed. Some computational experience is also reported which shows that the potentials of the method can materialize on real world problems.     

如何利用单纯形表上的信息

本文分析了求解线性规划的基本方法－－单纯形法所使用的单纯形表，将表中所提供的信息分为直接信息和间接信息两类，论述了如何充分利用这些信息的方法。例如如何由最终表求原问题、如何利用表中的数据互相推演和校正等。这是一篇教学经验的总结，对初学者可能有一定的帮助。     

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

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

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

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

无比值检验的亏基原始Ⅰ阶段算法

首次将亏基和无比值检验列主元规则相结合,执行亏基对偶单纯形算法得到一个原始可行基,以充分发挥这两种算法的优势,从而为亏基原始单纯形算法提供一个新的I阶段算法,以使其进一步克服退化所带来的困扰.数值试验表明,亏基和无比值主元规则的结合,能有效地减少总迭代次数和运行时间,其效率远远优于传统两阶段单纯形算法.     

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

[5]建立了定理5—3、5—4、5—5，并据此证明了采用该的最大改进规则的单纯形算法是多项式算法。本举例证明了[5]中的定理5—3、5—4、5—5是错误的。     

一个新的单纯形类算法

提出了一个求解线性规划的新单纯形类算法。它不仅无须引入人工变量，而且在第一阶段中采用无比检验。因此新算法比Arsham最近提出的push-to—pull算法效率更高。此外，本算法的数值稳定性也优于push—to—pull算法。     

Primal-Dual Simplex Method for Multiobjective Linear Programming

We develop a primal-dual simplex algorithm for multicriteria linear programming. It is based on the scalarization theorem of Pareto optimal solutions of multicriteria linear programs and the single objective primal-dual simplex algorithm. We illustrate the algorithm by an example, present some numerical results, give some further details on special cases and point out future research. The paper was written during a visit of the first author to the University of Sevilla financed by a grant of the Andalusian Consejería de Educación. The research of the first author was partially supported by University of Auckland Grant 3602178/9275. The research of the second and third authors was partially financed by Spanish Grants BFM2001-2378, BFM2001-4028, MTM2004-0909 and HA2003-0121. We thank Anthony Przybylski for the implementation and making his results available. We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper.