Spatial topology rule is the primary method to insure the consistency and validity of spatial topology relation in GIS software. Topology rule can be divided into three categories according to geographic entity’s geo...Spatial topology rule is the primary method to insure the consistency and validity of spatial topology relation in GIS software. Topology rule can be divided into three categories according to geographic entity’s geometric shape: point topology rule, line topology rule and polygon topology rule. At first, this paper summarizes the various linear geographic entities’ topological relations which have practical application, then designs a series of linear entity topology rules detailedly. Based on these rules, this paper proposes a topology rule checking algorithm using quadtree, which is designed on the basis of MAPGIS7.4 spatial data model. The algorithm has already been applied to MAPGIS platform and gained good effects.展开更多
The history of homologous linear rule investigation is reviewed simply. The author puts forward a problem worth paying attention to in the recent potential homologous linear rule investigation, especially some mistake...The history of homologous linear rule investigation is reviewed simply. The author puts forward a problem worth paying attention to in the recent potential homologous linear rule investigation, especially some mistakes made in these investigations on mathematical foundations. The author also exposes the mathematical arbitrariness of some papers on their potential homologous linear rule investigation.展开更多
In this paper, we find two formulas for the solutions of the following linear equation , where is a real matrix. This system has been well studied since the 1970s. It is known and simple proven that there is a solutio...In this paper, we find two formulas for the solutions of the following linear equation , where is a real matrix. This system has been well studied since the 1970s. It is known and simple proven that there is a solution for all if, and only if, the rows of A are linearly independent, and the minimum norm solution is given by the Moore-Penrose inverse formula, which is often denoted by;in this case, this solution is given by . Using this formula, Cramer’s Rule and Burgstahler’s Theorem (Theorem 2), we prove the following representation for this solution , where are the row vectors of the matrix A. To the best of our knowledge and looking in to many Linear Algebra books, there is not formula for this solution depending on determinants. Of course, this formula coincides with the one given by Cramer’s Rule when .展开更多
Despite it is often available in practice, information of optimal value of linear programming problems is ignored by conventional simplex algorithms. To speed up solution process, we propose in this paper some vari...Despite it is often available in practice, information of optimal value of linear programming problems is ignored by conventional simplex algorithms. To speed up solution process, we propose in this paper some variants of the bisection algorithm, explo展开更多
In this paper, we propose a modified centered climbing algorithm (MCCA) for linear programs, which improves the centered climbing algorithm (CCA) developed for linear programs recently. MCCA implements a specific clim...In this paper, we propose a modified centered climbing algorithm (MCCA) for linear programs, which improves the centered climbing algorithm (CCA) developed for linear programs recently. MCCA implements a specific climbing scheme where a violated constraint is probed by means of the centered vector used by CCA. Computational comparison is made with CCA and the simplex method. Numerical tests show that, on average CPU time, MCCA runs faster than both CCA and the simplex method in terms of tested problems. In addition, a simple initialization technique is introduced.展开更多
The purpose of this paper is to introduce a new pivot rule of the simplex algorithm. The simplex algorithm first presented by George B. Dantzig, is a widely used method for solving a linear programming problem (LP). O...The purpose of this paper is to introduce a new pivot rule of the simplex algorithm. The simplex algorithm first presented by George B. Dantzig, is a widely used method for solving a linear programming problem (LP). One of the important steps of the simplex algorithm is applying an appropriate pivot rule to select the basis-entering variable corresponding to the maximum reduced cost. Unfortunately, this pivot rule not only can lead to a critical cycling (solved by Bland’s rules), but does not improve efficiently the objective function. Our new pivot rule 1) solves the cycling problem in the original Dantzig’s simplex pivot rule, and 2) leads to an optimal improvement of the objective function at each iteration. The new pivot rule can lead to the optimal solution of LP with a lower number of iterations. In a maximization problem, Dantzig’s pivot rule selects a basis-entering variable corresponding to the most positive reduced cost;in some problems, it is well-known that Dantzig’s pivot rule, before reaching the optimal solution, may visit a large number of extreme points. Our goal is to improve the simplex algorithm so that the number of extreme points to visit is reduced;we propose an optimal improvement in the objective value per unit step of the basis-entering variable. In this paper, we propose a pivot rule that can reduce the number of such iterations over the Dantzig’s pivot rule and prevent cycling in the simplex algorithm. The idea is to have the maximum improvement in the objective value function: from the set of basis-entering variables with positive reduced cost, the efficient basis-entering variable corresponds to an optimal improvement of the objective function. Using computational complexity arguments and some examples, we prove that our optimal pivot rule is very effective and solves the cycling problem in LP. We test and compare the efficiency of this new pivot rule with Dantzig’s original pivot rule and the simplex algorithm in MATLAB environment.展开更多
In this article, we report the derivation of high accuracy finite difference method based on arithmetic average discretization for the solution of Un=F(x,u,u′)+∫K(x,s)ds , 0 x s < 1 subject to natural boundary co...In this article, we report the derivation of high accuracy finite difference method based on arithmetic average discretization for the solution of Un=F(x,u,u′)+∫K(x,s)ds , 0 x s < 1 subject to natural boundary conditions on a non-uniform mesh. The proposed variable mesh approximation is directly applicable to the integro-differential equation with singular coefficients. We need not require any special discretization to obtain the solution near the singular point. The convergence analysis of a difference scheme for the diffusion convection equation is briefly discussed. The presented variable mesh strategy is applicable when the internal grid points of the solution space are both even and odd in number as compared to the method discussed by authors in their previous work in which the internal grid points are strictly odd in number. The advantage of using this new variable mesh strategy is highlighted computationally.展开更多
The known Fourier-Chernikov algorithm of linear inequality system convolution is complemented with an original procedure of all dependent (redundant) inequalities deletion. The concept of “almost dependent” inequali...The known Fourier-Chernikov algorithm of linear inequality system convolution is complemented with an original procedure of all dependent (redundant) inequalities deletion. The concept of “almost dependent” inequalities is defined and an algorithm for further reducing the system by deletion of these is considered. The concluding algorithm makes it possible to hold actual-time convolution of a general inequality system containing up to 50 variables with the rigorous method of dependent inequalities deletion and up to 100 variables with the approximate method of one. The main application of such an approach consists in solving linear inequality system in an explicit form. These results are illustrated with a series of computer experiments.展开更多
文摘Spatial topology rule is the primary method to insure the consistency and validity of spatial topology relation in GIS software. Topology rule can be divided into three categories according to geographic entity’s geometric shape: point topology rule, line topology rule and polygon topology rule. At first, this paper summarizes the various linear geographic entities’ topological relations which have practical application, then designs a series of linear entity topology rules detailedly. Based on these rules, this paper proposes a topology rule checking algorithm using quadtree, which is designed on the basis of MAPGIS7.4 spatial data model. The algorithm has already been applied to MAPGIS platform and gained good effects.
文摘The history of homologous linear rule investigation is reviewed simply. The author puts forward a problem worth paying attention to in the recent potential homologous linear rule investigation, especially some mistakes made in these investigations on mathematical foundations. The author also exposes the mathematical arbitrariness of some papers on their potential homologous linear rule investigation.
文摘In this paper, we find two formulas for the solutions of the following linear equation , where is a real matrix. This system has been well studied since the 1970s. It is known and simple proven that there is a solution for all if, and only if, the rows of A are linearly independent, and the minimum norm solution is given by the Moore-Penrose inverse formula, which is often denoted by;in this case, this solution is given by . Using this formula, Cramer’s Rule and Burgstahler’s Theorem (Theorem 2), we prove the following representation for this solution , where are the row vectors of the matrix A. To the best of our knowledge and looking in to many Linear Algebra books, there is not formula for this solution depending on determinants. Of course, this formula coincides with the one given by Cramer’s Rule when .
文摘Despite it is often available in practice, information of optimal value of linear programming problems is ignored by conventional simplex algorithms. To speed up solution process, we propose in this paper some variants of the bisection algorithm, explo
文摘In this paper, we propose a modified centered climbing algorithm (MCCA) for linear programs, which improves the centered climbing algorithm (CCA) developed for linear programs recently. MCCA implements a specific climbing scheme where a violated constraint is probed by means of the centered vector used by CCA. Computational comparison is made with CCA and the simplex method. Numerical tests show that, on average CPU time, MCCA runs faster than both CCA and the simplex method in terms of tested problems. In addition, a simple initialization technique is introduced.
文摘The purpose of this paper is to introduce a new pivot rule of the simplex algorithm. The simplex algorithm first presented by George B. Dantzig, is a widely used method for solving a linear programming problem (LP). One of the important steps of the simplex algorithm is applying an appropriate pivot rule to select the basis-entering variable corresponding to the maximum reduced cost. Unfortunately, this pivot rule not only can lead to a critical cycling (solved by Bland’s rules), but does not improve efficiently the objective function. Our new pivot rule 1) solves the cycling problem in the original Dantzig’s simplex pivot rule, and 2) leads to an optimal improvement of the objective function at each iteration. The new pivot rule can lead to the optimal solution of LP with a lower number of iterations. In a maximization problem, Dantzig’s pivot rule selects a basis-entering variable corresponding to the most positive reduced cost;in some problems, it is well-known that Dantzig’s pivot rule, before reaching the optimal solution, may visit a large number of extreme points. Our goal is to improve the simplex algorithm so that the number of extreme points to visit is reduced;we propose an optimal improvement in the objective value per unit step of the basis-entering variable. In this paper, we propose a pivot rule that can reduce the number of such iterations over the Dantzig’s pivot rule and prevent cycling in the simplex algorithm. The idea is to have the maximum improvement in the objective value function: from the set of basis-entering variables with positive reduced cost, the efficient basis-entering variable corresponds to an optimal improvement of the objective function. Using computational complexity arguments and some examples, we prove that our optimal pivot rule is very effective and solves the cycling problem in LP. We test and compare the efficiency of this new pivot rule with Dantzig’s original pivot rule and the simplex algorithm in MATLAB environment.
文摘In this article, we report the derivation of high accuracy finite difference method based on arithmetic average discretization for the solution of Un=F(x,u,u′)+∫K(x,s)ds , 0 x s < 1 subject to natural boundary conditions on a non-uniform mesh. The proposed variable mesh approximation is directly applicable to the integro-differential equation with singular coefficients. We need not require any special discretization to obtain the solution near the singular point. The convergence analysis of a difference scheme for the diffusion convection equation is briefly discussed. The presented variable mesh strategy is applicable when the internal grid points of the solution space are both even and odd in number as compared to the method discussed by authors in their previous work in which the internal grid points are strictly odd in number. The advantage of using this new variable mesh strategy is highlighted computationally.
文摘The known Fourier-Chernikov algorithm of linear inequality system convolution is complemented with an original procedure of all dependent (redundant) inequalities deletion. The concept of “almost dependent” inequalities is defined and an algorithm for further reducing the system by deletion of these is considered. The concluding algorithm makes it possible to hold actual-time convolution of a general inequality system containing up to 50 variables with the rigorous method of dependent inequalities deletion and up to 100 variables with the approximate method of one. The main application of such an approach consists in solving linear inequality system in an explicit form. These results are illustrated with a series of computer experiments.
