Algoritmo de karmarkar y algoritmo primal-dual de puntos interiores para programacion lineal

Abstract

Este trabajo de tesis estudia dos algoritmos de punto interior para la programación lineal; el algoritmo de Karmarkar y el primal-dual en una de sus versiones iniciales. Se desarrolla en detalle ambos algoritmos y se prueba que son polinomiales en el peor caso, en con-traposición al algoritmo simplex que es un algoritmo exponencial en el peor caso, Estos algoritmos, como algunos de sus variantes más modernas, han demostrado tener un mejor desempeño (número de iteraciones y tiempo de CPU) que el algoritmo simplex para problema de programarán lineal de gran tamaño.