Algoritmos de trayectoria central para el problema de programación lineal continua

Abstract

Estudia una familia de algoritmos de punto interior, conocido como algoritmos de trayectoria central, para el problema de programación lineal. Presenta tres algoritmos basados en esta metodología: el algoritmo de trayectoria central de pasos cortos, el algoritmo de trayectoria central predictor-corrector, el algoritmo de trayectoria central de pasos largos y un algoritmo alternativo llamado algoritmo de trayectoria central no factible. Además, presentamos pruebas de convergencia para cada uno de ellos, una experiencia numérica básica es también presentada.

In the present thesis work we will study a family of algorithms of inner point, known like algorithms central trajectory, for the problem of linear programming which in the call forms standard. Using a rnethodology widely used for the prograrnrning problems nonlinear call rnethods of barrier and penalty but specialized to the linear case, it is so we generated a family of algorithrns of inner point for the problem of linear progratuming.

We presented three algorithrns based on this methodology: the algorithm of central trajectmy of half-steps, the deflection algorithm of central trajectory, the algorithm of central trajectory of lengthened paces andan alternative algorithrn called algorithm of nonfeasible central trajectory. In addition we presented tests of convergence for each one of thern. Basic a numerical experience also is presented.