Comment by tgv
The parent comment doesn't seem to be versed in complexity theory, so I tried to keep it simple.
But I think the simplex method is much older. Apparently, it dates back to 1947. Why do say it wasn't known until the 80s? Are we talking about different things?
As nullc mentioned, the simplex method can take exponential time in some pathological examples (a space of measure 0, if that matters). The first P-time linear programming algo (and proof) was the ellipsoid method of Khachian in the 1980s. I have the impression it wasn't really practical. A later P-time interior-point method by Karmarkar is used sometimes today (it beats simplex on certain types of problems) from what I understand. But, I'm nowhere near expert in this area.