Algoritmo primal - dual para programación lineal basado en el método del punto interior.

Abstract

En este trabajo se presenta un algoritmo que trabaja simultáneamente con el primal y dual y genera una sucesión de pares de soluciones factibles interiores. A lo largo de la sucesión generada, la dualidad Gap converge a cero a una tasa de convergencia al menos linealmente. El algoritmo está basado sobre aplicación de la clásica función barrera logarítmica al problema primal y dual.

This thesis presents an algorithm that Works simultaneously on Primal and Dual linear programming problems and generates a sequence of pairs of their interior feasible solutions. Along the sequence generated, the duality gap convergence ratio (1- B/n). Here n denotes the size of the problems and B un positive number depending on initial interior feasible solution.