Worst case behavior of the steepest edge simplex method |
| |
Authors: | Donald Goldfarb William Y Sit |
| |
Institution: | The City College of the City University of New York, New York, NY 10031, U.S.A. |
| |
Abstract: | At each nondegenerate iteration of the steepest-edge simplex method one moves from a vertex of the polyhedron, P, of feasible points to an adjacent vertex along an edge that is steepest with respect to the linear objective function ψ. In this paper we show how to construct a sequence of linear programs (Pn,ψn) in n variables for which the number of iterations required by the steepest edge simplex method is 2n−1. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|