Algoritmia básica (AB)
El reto de diseñar algoritmos eficientes para resolver problemas puede resultar apasionante

sguenos en twitter

.

Veremos en clase alguna de las ideas básicas del algoritmo del simplex (ver transparencias 54 a 70 de la asignatura, o transparencias 16 a 36 de estas otras del material adicional).

No obstante, su implementación detallada dista de ser sencilla. Por ejemplo, en esta anotación del blog de Jeremy Kun puede encontrarse una descripción más detallada, con enlaces a temas relacionados y al código escrito por el autor del blog:

Linear Programming and the Simplex Algorithm

En cuanto a la solución en tiempo polinómico de los problemas de programación lineal, en esta anotación puede leerse algún párrafo extraído del libro de Dasgupta, Papadimitriou y Vazirani sobre los algoritmos de Khachiyan y Karmarkar:

Linear programming in polynomial time


Comentarios