In this paper we present a new method combining interior and exterior approaches to solve linear programming problems. With the assumption that a feasible interior solution to the input system is known, this algorithm...In this paper we present a new method combining interior and exterior approaches to solve linear programming problems. With the assumption that a feasible interior solution to the input system is known, this algorithm uses it and appropriate constraints of the system to construct a sequence of the so called station cones whose vertices tend very fast to the solution to be found. The computational experiments show that the number of iterations of the new algorithm is significantly smaller than that of the second phase of the simplex method. Additionally, when the number of variables and constraints of the problem increase, the number of iterations of the new algorithm increase in a slower manner than that of the simplex method.展开更多
Recently we have proposed anew method combininginterior and exterior approaches to solve linear programming problems. This method uses an interior point, and from there connected to the vertex of the so called station...Recently we have proposed anew method combininginterior and exterior approaches to solve linear programming problems. This method uses an interior point, and from there connected to the vertex of the so called station cone which is also a solution of the dual problem. This allows us to determine the entering vector and the new station cone. Here in this paper, we present a new modified algorithm for the case, when at each iteration we determine a new interior point. The new building interior point moves toward the optimal vertex. Thanks to the shortened from both inside and outside, the new version allows to find quicker the optimal solution. The computational experiments show that the number of iterations of the new modified algorithm is significantly smaller than that of the second phase of the dual simplex method.展开更多
For a closed orientable surface Sg of genus not smaller than 2,C(Sg) is the curve complex on S g whose vertices consist of the isotopy classes of nontrivial circles on Sg. It has been showed that any two vertices in C...For a closed orientable surface Sg of genus not smaller than 2,C(Sg) is the curve complex on S g whose vertices consist of the isotopy classes of nontrivial circles on Sg. It has been showed that any two vertices in C(Sg) can be connected by an edge path,and C(Sg) has an infinite diameter. We show that for 0 ≤i≤3g-5,two i-simplices can be connected by an(i +1)-path in C(Sg),and the diameter of C(Sg) under such a distance is infinite.展开更多
文摘In this paper we present a new method combining interior and exterior approaches to solve linear programming problems. With the assumption that a feasible interior solution to the input system is known, this algorithm uses it and appropriate constraints of the system to construct a sequence of the so called station cones whose vertices tend very fast to the solution to be found. The computational experiments show that the number of iterations of the new algorithm is significantly smaller than that of the second phase of the simplex method. Additionally, when the number of variables and constraints of the problem increase, the number of iterations of the new algorithm increase in a slower manner than that of the simplex method.
文摘Recently we have proposed anew method combininginterior and exterior approaches to solve linear programming problems. This method uses an interior point, and from there connected to the vertex of the so called station cone which is also a solution of the dual problem. This allows us to determine the entering vector and the new station cone. Here in this paper, we present a new modified algorithm for the case, when at each iteration we determine a new interior point. The new building interior point moves toward the optimal vertex. Thanks to the shortened from both inside and outside, the new version allows to find quicker the optimal solution. The computational experiments show that the number of iterations of the new modified algorithm is significantly smaller than that of the second phase of the dual simplex method.
基金supported by National Natural Science Foundation of China(Grant Nos.10931005 and 11101058)the National Science Foundation for Post-doctoral Scientists of China(Grant No.2011M500049)
文摘For a closed orientable surface Sg of genus not smaller than 2,C(Sg) is the curve complex on S g whose vertices consist of the isotopy classes of nontrivial circles on Sg. It has been showed that any two vertices in C(Sg) can be connected by an edge path,and C(Sg) has an infinite diameter. We show that for 0 ≤i≤3g-5,two i-simplices can be connected by an(i +1)-path in C(Sg),and the diameter of C(Sg) under such a distance is infinite.
