@Article{JICS-13-190, author = {Wenya Gu, Xiangrui Meng, Xiaochen Zhu, Xinfa Qiu and Pingqi Pan}, title = {The primal-dual simplex algorithm base on the most obtuse angle principle}, journal = {Journal of Information and Computing Science}, year = {2018}, volume = {13}, number = {3}, pages = {190--194}, abstract = {1School of Binjiang, Nanjing University of Information Science & Technology, Nanjing 210044, China 2School of Applied Meteorology, Nanjing University of Information Science & Technology, Nanjing 210044, China 3Department of Mathematics, Southeast University, Nanjing 210000, China (Received March 12 2018, accepted August 28 2018) Abstract  We  present  a  relaxation  algorithm  for  solving  linear  programming  (LP)  problems  under  the framework of the primal-dual simplex algorithm. Each iteration, based on a heuristic representation of the optimal basis (the principle of the most obtuse Angle), the algorithm constructs and solves a sub-problem, whose objective function is the same as the original problem, but only contains partial constraints.The primal- dual simplex algorithm is used to solve the sub-problem. If the sub-problem has an optimal solution or the sub-problem has no feasible solution, the constraint is added according to the principle of the obtuse Angle and then the final solution of the old sub-problem is taken as the starting point. Our preliminary numerical experiments show that the proposed algorithm can effectively reduce the number of iterations compared with the  traditional  two-stage  simplex  algorithm.  Iterations  for  sub-problems  take  up  a  significant  proportion, which greatly reduces the CPU time required for each iteration. The new algorithm has potential advantages in solving large-scale problems. It's a very promising new algorithm. }, issn = {3080-180X}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/jics/22444.html} }