Tesis
Programación lineal: un algoritmo primal-dual de paso largo usando el método de la función barrera
Fecha
2020Registro en:
Luna, J. & Montoro, E. (2020). Programación lineal: un algoritmo primal-dual de paso largo usando el método de la función barrera. Tesis para optar el grado de Magíster en Matemática Aplicada con mención en Matemática Computacional. Unidad de Posgrado, Facultad de Ciencias Matemáticas, Universidad Nacional Mayor de San Marcos, Lima, Perú.
Autor
Luna Valdez, Juan Honorato
Institución
Resumen
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.