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

Autores

  • M.A.F. Menezes

DOI:

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

Resumo

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.

Referências

[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.

Downloads

Publicado

2005-06-01

Como Citar

Menezes, M. (2005). Um Algoritmo Dual Viável para Programação Linear. Trends in Computational and Applied Mathematics, 6(1), 91–99. https://doi.org/10.5540/tema.2005.06.01.0091

Edição

Seção

Artigo Original