首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 93 毫秒
1.
首次将亏基和无比值检验列主元规则相结合,执行亏基对偶单纯形算法得到一个原始可行基,以充分发挥这两种算法的优势,从而为亏基原始单纯形算法提供一个新的I阶段算法,以使其进一步克服退化所带来的困扰.数值试验表明,亏基和无比值主元规则的结合,能有效地减少总迭代次数和运行时间,其效率远远优于传统两阶段单纯形算法.  相似文献   

2.
通过摄动技术来使问题强制获得对偶可行性,执行亏基对偶单纯形算法得到一个原始可行基,并采用修正的主元规则,以充分发挥这两种算法的优势,从而为亏基原始单纯形算法提供一个新的I阶段算法,以使其进一步克服退化所带来的困扰.初步的数值试验表明,亏基和摄动两种算法优势的结合,能有效地克服退化的影响,能有效地减少总迭代次数和运行时间,其效率远远优于传统两阶段单纯形算法.  相似文献   

3.
将摄动算法和亏基单纯形算法相结合,以充分发挥这两种算法的优势,从而为亏基对偶单纯形算法提供一个新的Ⅰ阶段算法,以使其进一步克服退化所带来的困扰.数值试验结果表明,新算法能够降低退化带来的不良影响,减少总迭代次数和运算时间,其效率不仅远远优于传统的单纯形算法,且优于原有的亏基单纯形算法,是一个非常吸引人且充满希望的新尝试.  相似文献   

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

5.
在最钝角原理基础上建立了新的主元标规则,它按最钝角原理赋予一组非基本变量较高优先权,先在其中选择进基变量,直到其相应的检验数均满足符号条件;如果此时剩下的检验数均已满足条件,则已达到最优.在亏基架构中引入新的主元规则,能有效地减少每次迭代可选的非基变量的个数.数值试验表明,新算法的效率优于亏基原始单纯形算法,表明了最钝角原理的可行性和有效性.  相似文献   

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

7.
为克服单纯形算法中退化现象带来的困扰,本文在文[1]的基础上进一步提出亏基有界变量单纯形算法,并证明了算法的收敛性.  相似文献   

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

9.
本文提出一个基于最钝角原理的松弛算法求解线性规划问题。该算法依据最钝角原理略去部分约束得到一个规模较小的子问题,用原始单纯形算法解之;再添加所略去的约束恢复原问题,若此时全部约束条件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解。初步的数值试验表明,新算法比传统两阶段单纯形算法快得多。  相似文献   

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

11.
The computational Grid is currently gaining in popularity, and it enables computers scattered all over the world to be connected by the Internet as if they are part of a large computational infrastructure. While the computational Grid gathers more and more computational resources and the number of the applications for the computational Grid is increasing, load balancing for the computational Grid is still not effective enough. Because the computers are connected by a wide area network on the computational Grid, the significant communication latency and the frequency of large wave throughputs make it difficult to achieve effective load balancing. Thus, in this paper, we propose an algorithm to predict networking loads on the computational Grid to make the use of computational resources more efficient. The proposed algorithm based on the Markov model is evaluated using an actual networking load. As a result, the Markov model based algorithm offers the most accurate predictions compared with the related work. This revised version was published online in July 2006 with corrections to the Cover Date.  相似文献   

12.
This article presents an outcome-space pure cutting-plane algorithm for globally solving the linear multiplicative programming problem. The framework of the algorithm is taken from a pure cutting-plane decision set-based method developed by Horst and Tuy for solving concave minimization problems. By adapting this method to an outcome-space reformulation of the linear multiplicative programming problem, rather than applying directly the method to the original decision-set formulation, it is expected that considerable computational savings can be obtained. Also, we show how additional computational benefits might be obtained by implementing the new algorithm appropriately. To illustrate the new algorithm, we apply it to the solution of a sample problem.  相似文献   

13.
In this paper, a new trust region algorithm for nonlinear equality constrained LC^1 optimization problems is given. It obtains a search direction at each iteration not by solving a quadratic programming subproblem with a trust region bound, but by solving a system of linear equations. Since the computational complexity of a QP-Problem is in general much larger than that of a system of linear equations, this method proposed in this paper may reduce the computational complexity and hence improve computational efficiency. Furthermore, it is proved under appropriate assumptions that this algorithm is globally and super-linearly convergent to a solution of the original problem. Some numerical examples are reported, showing the proposed algorithm can be beneficial from a computational point of view.  相似文献   

14.
本文对带线性等式约束的LC^1优化问题提出了一个新的ODE型信赖域算法,它在每一次迭代时,不必求解带信赖域界的子问题,仅解一线性方程组而求得试验步。从而可以降低计算的复杂性,提高计算效率,在一定的条件下,文中还证明了该算法是超线性收敛的。  相似文献   

15.
Recently, a new algorithm for computing an optimal subadditive dual function to an integer program has been proposed. In this paper we show how to apply the algorithm to the set partitioning problem. We give several enhancements to the algorithm and we report computational experiments. The results show that it is tractable to obtain an optimal subadditive function for small and medium size problems. To the best of our knowledge this is the first work that reports computational experiments on computing an optimal subadditive dual function.  相似文献   

16.
The paper considers the hybrid flow-shop scheduling problem with multiprocessor tasks. Motivated by the computational complexity of the problem, we propose a memetic algorithm for this problem in the paper. We first describe the implementation details of a genetic algorithm, which is used in the memetic algorithm. We then propose a constraint programming based branch-and-bound algorithm to be employed as the local search engine of the memetic algorithm. Next, we present the new memetic algorithm. We lastly explain the computational experiments carried out to evaluate the performance of three algorithms (genetic algorithm, constraint programming based branch-and-bound algorithm, and memetic algorithm) in terms of both the quality of the solutions produced and the efficiency. These results demonstrate that the memetic algorithm produces better quality solutions and that it is very efficient.  相似文献   

17.
This paper presents a new trust region algorithm for solving nonsmooth nonlinear equation problems which posses the smooth plus non-smooth decomposition. At each iteration, this method obtains a trial step by solving a system of linear equations, hence avoiding the need for solving a quadratic programming subproblem with a trust region bound. From a computational point of view, this approach may reduce computational effort and hence improve computational efficiency. Furthermore, it is proved under appropriate assumptions that this algorithm is globally and locally super-linearly convergent. Some numerical examples are reported.  相似文献   

18.
本文提出一个求解非线性不等式约束优化问题的带有共轭梯度参数的广义梯度投影算法.算法中的共轭梯度参数是很容易得到的,且算法的初始点可以任意选取.而且,由于算法仅使用前一步搜索方向的信息,因而减少了计算量.在较弱条件下得到了算法的全局收敛性.数值结果表明算法是有效的.  相似文献   

19.
基于J.M.Peng研究一类变分不等式问题(简记为VIP)时所提出的价值函数,本文提出了求解强单调的VIP的一个新的信赖域算法。和已有的处理VIP的信赖域方法不同的是:它在每步迭代时,不必求解带信赖域界的子问题,仅解一线性方程组而求得试验步。这样,计算的复杂性一般来说可降低。在通常的假设条件下,文中还证明了算法的整体收敛性。最后,在梯度是半光滑和约束是矩形域的假设下,该算法还是超线性收敛的。  相似文献   

20.
文[1]提出精确解析法,用以求解任意变系数常微分方程,并利用初参数算法给出一个解的解析表达式.但利用初参数算法,对某一类问题,如长柱壳弯曲和振动等,它们的解将难以在计算机上得到.本文通过非均匀轴对称长圆柱壳弯曲问题,给出精确解析法的子结构算法,它能够计算初参数算法在计算机上不能解决的问题.问题最后和初参数算法一样能归结为求解一个低阶代数方程组.文末给出算例,表明本文算法的正确性,并和初参数算法作了比较.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号