共查询到18条相似文献,搜索用时 93 毫秒
1.
基于线性规划核心矩阵的单线形算法 总被引:1,自引:0,他引:1
本文讨论了线性规划中的核心矩阵及其特性,探讨了利用核心矩阵实现单纯形算法的可能性,并刊一步提出了一个基于核心矩阵的两阶段原始-对偶单纯形方法,该方法通过原始和对偶两个阶段的迭代,可以在有限次迭代中收敛到原问题的最优解或证明问题无解或无界。在试验的22个问题中,该算法的计算效率总体优于基于传统单纯形方法的MINOS软件。 相似文献
2.
线性规划的目标函数最速递减算法 总被引:4,自引:1,他引:4
在对偶单纯形方法的基础上,提出了线性规划的目标函数最速递减算法。它避开求初始可行基或初始基,以目标函数全局快速递减作为选基准则,将选基过程与换基迭代合二为一,从而大大减少了迭代次数。数值算例显示了该算法的有效性和优越性。 相似文献
3.
基于线性规划核心矩阵的单纯形算法 总被引:3,自引:0,他引:3
本文讨论了线性规划中的核心矩阵及其特性,探讨了利用核心矩阵实现单纯形算法的可能性,并进一步提出了一个基于核心矩阵的两阶段原始一对偶单纯形方法,该方法通过原始和对偶两个阶段的迭代,可以在有限次迭代中收敛到原问题的最优解或证明问题无解或无界.在试验的22个问题中,该算法的计算效率总体优于基于传统单纯形方法的MINOS软件. 相似文献
4.
线性规划联合算法的理论与应用 总被引:2,自引:4,他引:2
本在[1]的基础上.较系统的叙述了线性规划联合算法的步骤、相关理论及其应用,指出该算法具有避免人工变量、减少迭代次数、使用灵活、应用方便等特点。 相似文献
5.
唐建国 《数学的实践与认识》2006,36(4):135-143
为使线性规划的每个约束条件部分或全部地拥有原整个约束条件所包含的信息,将线性规划的约束条件“滚雪球”后得到与原约束条件等价的新约束条件,对新约束条件所构成的线性规划采用目标函数最速递减算法.有一定规模的随机数值算例显示了该算法只需进行m(约束条件数)次迭代即可求得最优解. 相似文献
6.
单纯形法一般采用行变换进行计算.本文给出了两种列变换的计算方法,一种与原始单纯形法等价,一种与对偶单纯形法等价,本文称之为对偶方法.这两种方法不引入松弛变量或剩余变量,计算规模小,有明显竞争优势. 相似文献
7.
一个求解线性规划的单纯形-内点算法 总被引:2,自引:0,他引:2
根据单纯形方法和大步长路径跟踪算法(Hertog,Roos和Terlaky1991),对于具有不等式约束的线性规划问题,引进了一个具有组合特性的内点算法.该方法保留了单纯形方法和内点算法的优点,克服了它们的不足,在任何情况下,这个方法都能快速收敛.数值结果也很好地验证了这个结论. 相似文献
8.
线性规划流动等值面算法 总被引:5,自引:1,他引:4
对于线性规划问题,本文给出了基于流动等值面的等价模型,提出了一种不可行流动等值面算法.新算法保留了传统单纯形算法的优点并克服了它的不足。初步数值结果表明新算法比传统方法更为有效. 相似文献
9.
线性规划的对偶基线算法 总被引: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. 相似文献
10.
算法的发现(Ⅲ)——非负独立集合问题与线性规划 总被引:2,自引:2,他引:0
本文讨论最大权非负独立集合问题(ξ,1)。它与等式型线性规划问题等价,因此后者在组合优化中有着明显的“合法”地位,沿着文(1,2)的思路,前者得到建党妆始基可行解的生成算法(ξ,3),它与后者的M法和二步法迥然不同。用对称差分解法自然得到一个算法(ξ,4),相当于改进单纯形算法,最后,还作了几点评证(ξ5)。 相似文献
11.
12.
13.
14.
本文在[1]的基础上,较系统地叙述了有界变量线性规划一种简易解法的基本思路、方法步骤、理论分析和应用举例。指出,因变量有界所引起的种种麻烦在这里通过单纯形表的小小变动便加以解决了。 相似文献
15.
A Dual Projective Pivot Algorithm for Linear Programming 总被引:1,自引:0,他引:1
Ping-Qi Pan 《Computational Optimization and Applications》2004,29(3):333-346
Recently, a linear programming problem solver, called dual projective simplex method, was proposed (Pan, Computers and Mathematics with Applications, vol. 35, no. 6, pp. 119–135, 1998). This algorithm requires a crash procedure to provide an initial (normal or deficient) basis. In this paper, it is recast in a more compact form so that it can get itself started from scratch with any dual (basic or nonbasic) feasible solution. A new dual Phase-1 approach for producing such a solution is proposed. Reported are also computational results obtained with a set of standard NETLIB problems. 相似文献
16.
M. Ehrgott J. Puerto A. M. Rodríguez-Chía 《Journal of Optimization Theory and Applications》2007,134(3):483-497
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. 相似文献
17.
István Maros 《Computational Optimization and Applications》2003,26(1):63-81
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. 相似文献
18.
提出了一个求解线性规划的新单纯形类算法。它不仅无须引入人工变量,而且在第一阶段中采用无比检验。因此新算法比Arsham最近提出的push-to—pull算法效率更高。此外,本算法的数值稳定性也优于push—to—pull算法。 相似文献