一种简易的单纯形表

通过对单纯形法的分析和研究,提出了一种简易的单纯形表,并利用矩形法则进行计算而得到一种改进的单纯形法.结果表明该法简单易行,并减少了计算量和存储量.     

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

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

单纯形上积分型Stancu算子对连续函数的逼近

本文首先构造了单纯形上积分型Stancu算子,其讨论了它对连续函数的逼近,运用Mamedov-Shisha和Devore-Freud量化方法,得到了该算子对连续函数及连续可微函数的逼近度,并给出它的Vonorovskya型渐近公式。     

单纯形上Bernstein多项式的一些性质

设Ｂ_m（ｆ，·）为函数ｆ在ｄ维单纯形σ上的ｎ阶Ｂｅｒｎｓｔｅｉｎ多项式，本文对ｆ∈Ｃ^ｒ（σ）及ｆ∈Ｃ^r+2（σ）给出了ｆ的各阶编导数用Ｂ_n（ｆ，·）相应偏导数逼近的误差估计．同时也考虑了整系数Ｂｅｒｎｓｔｅｉｎ多项式的Ｌ_p模估计     

单纯形上Bernstein多项式的迭代根限

本文评述了近年来有关冠心病中医理论研究的６个方面的问题，即阳气虚阴寒盛理论、血瘀理论、痛则不通理论、心胃病理论、诱发因素理论。结合传统中医理论和现代药理及临床实验研究进行了分析评价。     

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

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

单纯形上的q-Stancu多项式的最优逼近阶

构造了单纯形上的多元q-Stancu多项式,它是著名的Bernstein多项式和Stancu多项式的推广.建立该类多项式逼近连续函数的上、下界估计,进而给出其对连续函数的最优逼近阶(饱和阶)及其特征刻画.此外,还研究了该类多项式逼近连续函数的饱和类.     

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

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

单纯形方法的两个变种

考虑标准形式的线性规划问题: (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.     

单纯形法检验数的新计算方法

单纯形法仍然是求解线性规划最具竞争力的算法之一,改进它的计算效率仍具有理论和现实意义.本文通过改进检验数的计算方式,提出了一种实施单纯形法新的计算方式.这种计算方式方便简单,无论采用单纯形表还是采用数值迭代计算都可以提高计算效率.     

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

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

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

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

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.     

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.     

含自由变量LP问题的改进单纯形法

对于含自由变量的LP问题,为了得到比单纯形法[1]更有效的算法,通过研究在单纯形法迭代过程中,将自由变量化为非负变量再实施运算的规律,提出一种能节省存贮空间和提高运算速度的改进单纯形法。数值实验表明新算法是有效的。     

A Simplex Approach for Finding Local Solutions of a Linear Bilevel Program by Equilibrium Points

In this paper, a linear bilevel programming problem (LBP) is considered. Local optimality conditions are derived. They are based on the notion of equilibrium point of an exact penalization for LBP. It is described how an equilibrium point can be obtained with the simplex method. It is shown that the information in the simplex tableaux can be used to get necessary and sufficient local optimality conditions for LBP. Based on these conditions, a simplex type algorithm is proposed, which attains a local solution of LBP by moving in equilibrium points. A numerical example illustrates how the algorithm works. Some computational results are reported.     

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.