Programación lineal: un algoritmo primal-dual de paso largo usando el método de la función barrera

Abstract

Desarrolla y describe el método punto interior primal-dual para resolver el problema de programación lineal. Dicho método se caracteriza por utilizar funciones barrera, para el problema primal y para el dual y así deducir el sistema no lineal primal-dual, cuya solución define la trayectoria central del método de punto interior. Otra característica es que se utiliza una matriz de escalamiento para deducir dos direcciones de descenso, una para el espacio primal y otra para el espacio dual, y que forman la descomposición ortogonal de la versión escalada de la matriz asociada a las restricciones lineales del problema primal. Se presenta un algoritmo denominado de “Paso Largo“, que implementa el método y se demuestra que el número total de iteraciones que ejecuta es de orden polinomial.