Afficher la notice abrégée

dc.contributor.authorCurrie, James
dc.date.accessioned2019-06-07T17:53:58Z
dc.date.available2019-06-07T17:53:58Z
dc.date.issued1984-08
dc.identifier.citationCurrie, James D. The Complexity of the Simplex Algorithm; A thesis submitted to the Faculty of Graduate Studies and Research in partial fulfillment of the requirements for the degree of Master of Science, Department of Mathematics and Statistics, Carleton University, August 1984.
dc.identifier.urihttp://hdl.handle.net/10680/1695
dc.description.abstractThe thesis begins by giving background in linear programming and Simplex methods. Topics covered include the duality theorem, Lemke's algorithm, and the pathological programs of Klee-Minty. Because of the bad behaviour of Klee-Minty programs, the behaviour of the Simplex algorithm is only good on average. To take such an average, certain assumptions on the distribution of linear programs are introduced and discussed. A geometrical meaning is given for the number of steps Lemke's algorithm takes to solve a program. This gives rise to a formula bounding the average number of steps taken. This formula is heuristically justified in an original way. The formula is combinatorially simplified, to get a bound on the complexity of Simplex.en_US
dc.language.isoenen_US
dc.publisherCarleton Universityen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectSimplex algorithmen_US
dc.subjectLemke's algorithm
dc.subjectComplexity
dc.subjectLinear programming
dc.titleThe Complexity of the Simplex Algorithmen_US
dc.typeThesisen_US
dc.description.degreeMScen_US
dc.publisher.grantorCarleton University


Fichier(s) constituant ce document

Thumbnail

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée