A NEW PERTURBATION SIMPLEX ALGORITHM FOR LINEAR PROGRAMMING

1.IntroductionThedualsimplexalgorithm[1,91andtheprimal-dualsimplealgorithm[6]arewellknownandefficientsimplexvariants.However,bothofthemneedaninitialdualfeasiblebasistogetstarted,andthereforecannotbedirectlyappliedtosolvingproblemsthatdonothavesuchane...     

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

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

A largest-distance pivot rule for the simplex algorithm

We propose a new pivot rule for the simplex algorithm, which is demonstrative in the dual space intuitively. Although it is based on normalized reduced costs, like the steepest-edge rule and its variants, the rule is much simpler and cheaper than the latter. We report computational results obtained with the 47 largest Netlib problems in terms of the number of rows and columns, all of the 16 Kennington problems, and the 17 largest BPMPD problems. Over the total 80 problems, a variant of the rule outperformed the Devex rule with iterations and time ratio 1.43 and 3.24, respectively.     

线性规划流动等值面算法

对于线性规划问题,本文给出了基于流动等值面的等价模型,提出了一种不可行流动等值面算法．新算法保留了传统单纯形算法的优点并克服了它的不足。初步数值结果表明新算法比传统方法更为有效．     

PRIMAL PERTURBATION SIMPLEX ALGORITHMS FOR LINEAR PROGRAMMING

1. IntroductionExtensive research in linear programming, such as [1,2,9,10,if, 12,13,14,19], hasbeen to improve pivot rules to reduce the number of iterations required. Relatively lesseffort was made on perturbing problem data with pivot rules unaltered (for instance, theself--dual parametric method [7] and perturbation--based methods [3,5]). And, becauseof the papametrization, the latter do not proceed as simply as the conventional simplexalgorithm itself.Recently, Pan [17] proposes new pert…     

一个新的线性规划无人工变量算法

本文研究了线性规划的求解问题.利用对偶转化的方法,获得了一个计算效率高的新的无人工变量通用算法.该新算法比最近提出的无人工变量算法push-to-pull算法效率更高.     

一个求解线性规划的单纯形-内点算法

根据单纯形方法和大步长路径跟踪算法（Ｈｅｒｔｏｇ，Ｒｏｏｓ和Ｔｅｒｌａｋｙ１９９１），对于具有不等式约束的线性规划问题，引进了一个具有组合特性的内点算法．该方法保留了单纯形方法和内点算法的优点，克服了它们的不足，在任何情况下，这个方法都能快速收敛．数值结果也很好地验证了这个结论．     

框式线性规划的原—对偶仿射尺度算法

本文对框式线性规划问题设计了一个原－对偶仿射尺度算法，并证明该算法的迭代复杂性面式同时。     

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

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

框式线性规划非精确不可行内点算法

本文为框式线性规划给出了一个非精确不可行内点算法．该算法使用的搜索方向仅需要达到一个相对的精度，这样的搜索方向可以通过Krylov子空间迭代法，比如CG或QMR得到，本文最后证明了算法的全局收敛性。     

线性规划基于预-校正的组合同伦多项式算法

本文针对线性规划问题提出了一个新的内点方法——组合同伦内点方法，并采用预估校正算法来跟踪组合同伦路径从而得到问题的ε-解.最后讨论了该算法的收敛性，并证明了该算法为多项式算法。     

求解一类广义线性规划的分裂算法

1　引　　言我们知道,描述常义线性规划问题的数学模型为:mincTxs.tAx=bx≥0　　在经济问题中,线性规划中的向量c往往表示为价格,而在许多实际规划问题中价格向量c往往会在一定范围内扰动.这时,我们可以考虑这样一类广义线性规划问题:minx{maxy∈YyTx}s.tAx=b　x∈X(1)其中,A∈Rm×n,b∈Rm,X={x∈Rn|x≥0},Y是Rn中的一个凸闭子集.有关广义线性规划问题的求解,何在文献[1]中作过一些讨论.我们通过对线性约束Ax=b引入乘子可得到广义线性规划问题(1)定义在X×Y×Rm上的Lagrange函数为:L(x,y,η)=yTx-ηT(Ax-b)(2)　　如果x*是(1)式的…     

框式线性规划的多项式预估校正内点算法

本文研究带线性约束的框式线性规划问题,给出了一个预估校正内点算法,分析了该算法的多项式计算复杂性,并证明其迭代复杂度为Ο(nL).     

线性规划的最钝角CRISS-CROSS算法

1 引言 考虑如下标准线性规划问题 minimize c~Tx (1) subject to Ax=b, x≥0 其中A∈R~(m×n) (m相似文献   

线性规划的对偶基线算法

In this paper,we studied the dual form of the basic line algorthm for linear programs.It can be easily implemented in tableau that similar to the primal/dual simplex method.Different from primal simplex method or dual simplex method,the dual basic line algorithm can keep primal feasibility and dual feasibility at the same time in a tableau,which makes it more efficient than the former ones.Principles and convergence of dual basic line algorthm were discussed.Some examplex and computational experience were given to illustrate the efficiency of our method.     

一类线性乘积规划问题的分支定界缩减方法

提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的.     

线性规划的单纯形法及其发展

本文给出了一种新的原对偶单纯形法,并通过它分析了隐藏在经典单纯形法中的对偶信息．我们重新评价经典单纯形法并详细讨论了它与现代单纯形法之间的联系．两个修改版本一并给出．新算法具有计算量小和实施简单等特点,计算效果也不错．初步数值实验表明现代单纯形法比经典方法具有明显的优越性．     

一个改进的线性规划预校正算法

本文我们提出了一个改进型线性规划预校正算法，我们的预步和校正步方向与Mizuno－Todd-Ye[4]的方向是不同的．我们的算法的迭代复杂度为，然而在校正步，我们降低对偶间隙一个常数因子．     

一类凸规划的多项式预估校正内点法

1、引言 1990年由Mehrotra对线性规划问题提出了一个称为预估校正的方法,并在1992年给出了其数值算法．1993年Mizuno,Todd和Y．Ye．给出了改进的预估校正内点法,使得一个预估步后只跟一个校正步．1994年F．A．Potra给出了不可行预估校正内点法,使得可以从一个不可行的初始点开始算法的迭代,并证明了其为二次收敛．     

无约束广义几何规划的一种最新算法

1　引　　言近十几年来 ,几何规划新的有效数值求解方法成果很少 ,但几何规划在工程中的应用却十分广泛 ,随着线性、二次规划和非线性规划的各种新的数值方法的出现 ,必将把几何规划推向新阶段 .本文充分利用广义几何规划的特点 ,根据目标函数的梯度及 Hessian阵具有简单的特殊表达式 ,再结合信赖域算法构造了一种特殊算法 ,每次迭代只需解一类特殊的线性方程组 ,并在相对弱的条件下证明了全局收敛性和局部二次收敛性 ,具有比采用一般非线性规划求解速度快、精度高、占用内存少等优点 .考虑如下无约束的广义几何规划问题minh(t) = mj=1cj n…