共查询到18条相似文献,搜索用时 78 毫秒
1.
2.
本文研究了线性规划单纯形法和对偶单纯形法主元规则的性质.利用直观的几何方法,结合对偶理论和灵敏度分析,得到了主元规则的特点,针对针对三种最常见的主元规则构造出不同的二维和三维例子,以此说明对每种主元规则都容易构造出其不优的反例,以及迭代次数多于约束个数的例子.所得结果有助于对单纯形法和对偶单纯形法的理解和研究. 相似文献
3.
单纯形法一般采用行变换进行计算.本文给出了两种列变换的计算方法,一种与原始单纯形法等价,一种与对偶单纯形法等价,本文称之为对偶方法.这两种方法不引入松弛变量或剩余变量,计算规模小,有明显竞争优势. 相似文献
4.
5.
线性规划的对偶基线算法 总被引: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. 相似文献
6.
7.
本文研究了线性规划的灵敏度分析方法.运用灵敏度分析的方法,分析了单纯形法求解过程中新增变量的动态变化所需的条件,并从具体的二维和三维例子出发,构造出一系列的高维线性规划问题.用单纯形法求解这些问题时,使用某种主元规则(如最大改进规则)的迭代次数可以比约束数目多一至三次. 相似文献
8.
9.
本文在[1]的基础上,较系统地叙述了有界变量线性规划一种简易解法的基本思路、方法步骤、理论分析和应用举例。指出,因变量有界所引起的种种麻烦在这里通过单纯形表的小小变动便加以解决了。 相似文献
10.
11.
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. 相似文献
12.
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. 相似文献
13.
基于线性规划核心矩阵的单纯形算法 总被引:3,自引:0,他引:3
本文讨论了线性规划中的核心矩阵及其特性,探讨了利用核心矩阵实现单纯形算法的可能性,并进一步提出了一个基于核心矩阵的两阶段原始一对偶单纯形方法,该方法通过原始和对偶两个阶段的迭代,可以在有限次迭代中收敛到原问题的最优解或证明问题无解或无界.在试验的22个问题中,该算法的计算效率总体优于基于传统单纯形方法的MINOS软件. 相似文献
14.
Artur Świętanowski 《Computational Optimization and Applications》1998,10(3):271-281
The purpose of this paper is to present a new steepest edge (SE) approximation scheme for the simplex method. The major advantages are its simplicity of recurrences and implementation, low computational overhead (compared to both the exact SE method and the DEVEX approximation scheme), and surprisingly good performance.The paper contains a brief account of the exact SE algorithm, the new recurrences developed in the same framework and some discussion on the possible reasons for the method's apparent success. Finally, numerical experiments are presented to assess the practical value of the method. The results are very promising. 相似文献
15.
对于含自由变量的LP问题,为了得到比单纯形法[1]更有效的算法,通过研究在单纯形法迭代过程中,将自由变量化为非负变量再实施运算的规律,提出一种能节省存贮空间和提高运算速度的改进单纯形法。数值实验表明新算法是有效的。 相似文献
16.
Chang T. S. Adachi J. Wang X. Chen T.R. 《Journal of Optimization Theory and Applications》2002,113(3):487-512
In linear programming, the simplex method has been viewed for a long time as an efficient tool. Interior methods have attracted a lot of attention since they were proposed recently. It seems plausible intuitively that there is no reason why a good linear programming algorithm should not be allowed to cross the boundary of the feasible region when necessary. However, such an algorithm is seldom studied. In this paper, we will develop first a framework of a multiplier-alike algorithm for linear programming which allows its trajectory to move across the boundary of the feasible region. Second, we illustrate that such a framework has the potential to perform as well as the simplex method by showing that these methods are equivalent in a well-defined sense, even though they look so different. 相似文献
17.
18.
An efficient algorithm is proposed for finding all solutions of nonlinear equations using linear programming (LP). This algorithm is based on a simple test (termed the LP test) for nonexistence of a solution to a system of nonlinear equations in a given region. In the conventional LP test, the system of nonlinear equations is transformed into an LP problem, to which the simplex method is applied. However, although the LP test is very powerful, it requires many pivotings for each region. In this paper, we use the dual simplex method in the LP test, which makes the average number of pivotings per region much smaller (less than one, for example) and makes the algorithm very efficient. By numerical examples, it is shown that the proposed algorithm can find all solutions of systems of 200 nonlinear equations in practical computation time. 相似文献