¿El algoritmo simplex es el mejor?

Ponente(s): Fernando Moreno Gomez, Doctor Cesar Alberto Escobar Gracia
El estudio de la complejidad de problemas relativos a algoritmos de programación lineal es uno de los objetivos de esta investigación. En particular, se estudia la resolubilidad de problemas con algoritmos de complejidad polinomial. Demostraremos que el método simplex, tiene convergencia exponencial en el peor de los casos, se estudia también la complejidad del método de Karmarkar el cual es un algorítmo de complejidad polinomial. Por lo cual demostraremos que hasta el momento no existe un algoritmo con el cual nos asegure un menor tiempo de convergencia en los problemas de programación lineal.