Um Algoritmo Dual Viável para Programação Linear

M.A.F. Menezes

Abstract


Neste trabalho estudamos um algoritmo de ponto-interior-inviável dual viável para programação linear devido a Menezes e Gonzaga [3], desenvolvendo uma estratégia preditora-corretora sob uma certa condição associada à viabilidade primal, com o objetivo de melhorar a eficiência do algoritmo mantendo a sua complexidade em iterações.

References


[1] L.M.G. Drummond, “Classical and Generalized Central Paths with Algorithmic Applications in Linear Programming”, Tese de Doutorado, IMPA/CNPq, 1997.

C.C. Gonzaga, Path-following methods for linear programming, SIAM Review, 34, No. 2 (1992), 167-224.

M.A.F. Menezes, “Um Algoritmo de Ponto-Interior-Inviável com Complexidade O(√nL) Iterações para Programação Linear”, Tese de Doutorado, COPPE/UFRJ, 1998.

S. Mizuno, M.J. Todd e Y. Ye, A surface of analytic centers and primaldual infeasible-interior-point algorithms for linear programming, Mathematics of Operations Research, 20, No. 1 (1995), 135-162.

R. Sheng e F.A. Potra, A quadratically convergent infeasible-interior-point algorithm for LCP with polynomial complexity, SIAM Journal on Optimization, 7, No. 2 (1997), 304-317.

Y. Ye, An O(√nL)-iteration combined phase I-phase II potential reduction algorithm for linear programming, Department of Management Sciences, The University of Iowa, Iowa City, Iowa 52242, 1992.

Y. Ye, On homogeneous and self-dual algorithms for LCP, Mathematical Programming 76 (1997), 211-221.

Y. Ye, M.J. Todd e S. Mizuno, An O(√nL)-iteration homogeneous and selfdual linear programming algorithm, Mathematics of Operations Research, 19, No. 1 (1994), 53-67.




DOI: https://doi.org/10.5540/tema.2005.06.01.0091

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia