McGregor-Macdonald, Simon2011-07-132022-10-272011-07-132022-10-2720002000https://ir.wgtn.ac.nz/handle/123456789/25454This thesis introduces path-following methods for linear programming and compares them to the simplex method. This comparison involves three aspects of each method: mathematical basis of the methodology, theoretical computational complexity and computational performance in practice. Path-following methods follow the central path through the interior of the feasible region, whereas the simplex method traces around the boundary. The computational complexity of path-following methods is shown to be polynomial, while the simplex method is exponential in the worst-case. The experience of practitioners gives overwhelming evidence of the performance of the simplex method, but implementations of path-following methods can be competitive with the simplex method.pdfen-NZLinear programmingThe simplex methodOperations ResearchText