共查询到20条相似文献,搜索用时 0 毫秒
1.
Ping-qi Pan 《计算数学(英文版)》1999,17(3):233-242
1.IntroductionThedualsimplexalgorithm[1,91andtheprimal-dualsimplealgorithm[6]arewellknownandefficientsimplexvariants.However,bothofthemneedaninitialdualfeasiblebasistogetstarted,andthereforecannotbedirectlyappliedtosolvingproblemsthatdonothavesuchane... 相似文献
2.
本文建立变量有广义界线性规划一个新的转轴算法,称之为叠累单纯形算法,新算法其有三个主要特征:1对于检验数为“坏”的非基变量 xs,进行一轮子转轴运算,使得xs进基,转轴中具有“好”的检验数的变量始终保持“好”的检验数;2x.进基的子转轴所产生的基既不是原始可行基,也不是对偶可行基,但子转轴结束时产生的基是原始可行的;3目标函数值在整个转抽运算中是单调下降,从而算法可有限步终止. 相似文献
3.
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. 相似文献
4.
线性规划流动等值面算法 总被引:5,自引:1,他引:4
对于线性规划问题,本文给出了基于流动等值面的等价模型,提出了一种不可行流动等值面算法.新算法保留了传统单纯形算法的优点并克服了它的不足。初步数值结果表明新算法比传统方法更为有效. 相似文献
5.
PRIMAL PERTURBATION SIMPLEX ALGORITHMS FOR LINEAR PROGRAMMING 总被引:2,自引:0,他引:2
Ping-qi Pan 《计算数学(英文版)》2000,18(6):587-596
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… 相似文献
6.
本文研究了线性规划的求解问题.利用对偶转化的方法,获得了一个计算效率高的新的无人工变量通用算法.该新算法比最近提出的无人工变量算法push-to-pull算法效率更高. 相似文献
7.
一个求解线性规划的单纯形-内点算法 总被引:2,自引:0,他引:2
根据单纯形方法和大步长路径跟踪算法(Hertog,Roos和Terlaky1991),对于具有不等式约束的线性规划问题,引进了一个具有组合特性的内点算法.该方法保留了单纯形方法和内点算法的优点,克服了它们的不足,在任何情况下,这个方法都能快速收敛.数值结果也很好地验证了这个结论. 相似文献
8.
9.
10.
11.
12.
胡国雷 《高等学校计算数学学报》2000,22(2):117-122
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)式的… 相似文献
13.
14.
线性规划的最钝角CRISS-CROSS算法 总被引:1,自引:0,他引:1
1 引言 考虑如下标准线性规划问题 minimize c~Tx (1) subject to Ax=b, x≥0 其中A∈R~(m×n) (m相似文献
15.
线性规划的对偶基线算法 总被引:6,自引:0,他引:6
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. 相似文献
16.
提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的. 相似文献
17.
18.
一个改进的线性规划预校正算法 总被引:6,自引:0,他引:6
本文我们提出了一个改进型线性规划预校正算法,我们的预步和校正步方向与Mizuno-Todd-Ye[4]的方向是不同的.我们的算法的迭代复杂度为,然而在校正步,我们降低对偶间隙一个常数因子. 相似文献
19.
一类凸规划的多项式预估校正内点法 总被引:2,自引:0,他引:2
1、引言 1990年由Mehrotra对线性规划问题提出了一个称为预估校正的方法,并在1992年给出了其数值算法.1993年Mizuno,Todd和Y.Ye.给出了改进的预估校正内点法,使得一个预估步后只跟一个校正步.1994年F.A.Potra给出了不可行预估校正内点法,使得可以从一个不可行的初始点开始算法的迭代,并证明了其为二次收敛. 相似文献
20.
无约束广义几何规划的一种最新算法 总被引:4,自引:0,他引:4
1 引 言近十几年来 ,几何规划新的有效数值求解方法成果很少 ,但几何规划在工程中的应用却十分广泛 ,随着线性、二次规划和非线性规划的各种新的数值方法的出现 ,必将把几何规划推向新阶段 .本文充分利用广义几何规划的特点 ,根据目标函数的梯度及 Hessian阵具有简单的特殊表达式 ,再结合信赖域算法构造了一种特殊算法 ,每次迭代只需解一类特殊的线性方程组 ,并在相对弱的条件下证明了全局收敛性和局部二次收敛性 ,具有比采用一般非线性规划求解速度快、精度高、占用内存少等优点 .考虑如下无约束的广义几何规划问题minh(t) = mj=1cj n… 相似文献