Um Algoritmo Dual Viável para Programação Linear
DOI:
https://doi.org/10.5540/tema.2005.06.01.0091Resumo
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
Como Citar
Edição
Seção
Licença
Política para Periódicos de Acesso Livre
Autores que publicam nesta revista concordam com os seguintes termos:
- Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
- Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
- Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).
- Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.