Primal-dual Simplex Algorithm for Linear Programming

Abstract

1School of Binjiang, Nanjing University of Information Science & Technology, Nanjing 210044, China 2Department of Mathematics, Southeast University, Nanjing 210000, China (Received March 03 2018, accepted August 19 2018) When the linear programming (LP) problem satisfies neither the primal feasibility nor the dual feasibility, the primal-dual simplex method can be used to solve the problem in order to avoid the defect of the increase of decision variables \u00a0caused \u00a0by \u00a0the \u00a0addition \u00a0of \u00a0artificial \u00a0variables \u00a0in \u00a0the \u00a0two-stage \u00a0algorithm. \u00a0In \u00a0this \u00a0paper, \u00a0we \u00a0use \u00a0PPSM (primitive - primitive simplex method) and DDSM(dual - dual simplex method) to solve these problems. Compared with the simplex method of two-stages, a better result is obtained.