As far as I can recall, the Simplex Algorithm is *not* running in polynomial time, although when randomly perturbing the input, it runs on average in polynomial time (this is also studied under the name "Smoothed Analysis of Algorithms", see for example the article by Spielman and Teng, Journal of the ACM, Vol. 51, No. 3, May 2004, pp. 385–463
http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CC0QFjAA&url=http%3A%2F%2Fwww.cs.duke.edu%2Fcourses%2Fspring07%2Fcps296.2%2Fpapers%2Fp385-a_spielman.pdf&ei=6BmXT7GONuas0QXig_2yDg&usg=AFQjCNE5PFNqSIUgHjNdVys2dX_drjkUAg&sig2=ItkEJelYbgxu-yO6NOuidA

There are however algorithms for linear programming which run in polynomial time, known as "[interior-point](https://en.wikipedia.org/wiki/Interior-point_method)" algorithms, because they traverse the interior of the simplex.