A Eficiência Polionomial do Simplex para Redes: Aplicação em um problema do caminho mais curto
DOI:
https://doi.org/10.5935/1809-2667.20030015Palabras clave:
Algoritmo simplex para redes, Complexidade, Árvores de buscaResumen
Neste trabalho é apresentado um algoritmo simplex para rede de complexidade O(nm) que encontra uma árvore de caminhos mais curtos, de um nó para todos os outros nós em uma rede direcionada, de n nós e m arcos, ou encontra um ciclo negativo. O tempo de execução desse algoritmo, no pior caso, é tão rápido quanto qualquer algoritmo polinomial que resolva este problema.Descargas
Referencias
AHUJA, R. K; MAGNANTI, T. L; ORLIN, J. B. - Network Flows, Theory, Algorithms and Applications. Prentice-Hall, Inc, 1993.
BELLMAN R. On a Route Problem. Quarterly Applied Mathematics 16 p 87-90. 1958.
CUNNINGHAM, W. A Network Simplex Method. Math. Programming 11. p.105-116. 1976.
DIJKSTRA, E W. A Note on Two Problems in Connexion with Graphs. Numerishe Matematik, vol. 1. p 269-271. 1959.
FORD, L R. Network Flow Theory. The Rand corporation Report p.923, Santa Monica, CA. 1956.
GOLDFARB, D. AND JIN, Z. An O(nm) Time Network Simplex Algorithm For the Shortest Path Problem. Operations Research, vol.47, N0 3. p 445-448. 1999.
GOLDFARB, D; HAO, J. AND KAI, S.-R. Efficient Shortest Path Simplex Algorithms. Operations Research, vol. 38 No 4, p 624-628. 1990a.
GOLDFARB, D; JIANXIU H; KAI S. R. Anti-Stalling Pivot Rules For The Network Simplex Algorithm. Networks. John Wilev and Sons, Inc. vol.20 p 79-91. 1990b.
LAWLER, E L. Combinatorial optimization: networks and matroids. Holt, Rinehart and Winston, New York. 1956.
MARINHO, C.E.V. Eficiência Polinomial do Método Simplex para Redes: Análise Sobre um Problema do Caminho mais Curto (PCMC). Tese de Mestrado - UENF. Campos dos Goytacazes, RJ- Brasil. 2001.
MOORE, Z F. The Shortest Path Through a Maze. Proc. Internat. Sympos. On Theory of Switching, Part II, p. 285-292. 1957.
ORLIN, B. J. A Polynomial Time Primal Network Simplex Algorithm For Minimum Cost Flows. The Mathematical Programming Society Inc, Published by Elsevier Science B.V-p. 109-127. 1997.
TAHA, H. A. Operations Research: An Introduction. Prentice Hall Inc, 6th Edition. 1997.
Descargas
Número
Sección
Licencia
Los autores del manuscrito enviado a la revista Vértices, representados aquí por el autor correspondiente, aceptan los siguientes términos:
Los autores conservan los derechos de autor y otorgan a la revista Vértices el derecho de primera publicación.
Al mismo tiempo, el trabajo está licenciado bajo la Licencia Creative Commons Atribución 4.0 Internacional (CC BY 4.0), que permite a terceros copiar y redistribuir el material en cualquier medio o formato y mezclar, transformar y construir sobre su contenido para cualquier propósito legal, incluso comercial, siempre que el trabajo original se cite correctamente.
Los autores no recibirán ningún pago material por su manuscrito y la Essentia Editora lo pondrá a disposición en línea en modo de acceso abierto, a través de su propio sistema o de otras bases de datos.
Los autores están autorizados a celebrar contratos adicionales por separado para la distribución no exclusiva de la versión del trabajo publicado en la revista Vértices (por ejemplo, publicar en un repositorio institucional o como capítulo de libro), con reconocimiento de autoría y publicación inicial en esta revista.
Se permite y se alienta a los autores a difundir y distribuir en línea la versión posterior a la publicación (es decir, la versión final posterior al arbitraje) o la versión PDF del editor en distintas fuentes de información (por ejemplo, en repositorios institucionales, temáticos o páginas web personales) en cualquier momento después de la primera publicación del artículo por la revista Vértices.
La Essentia Editora puede realizar cambios normativos, ortográficos y gramaticales en los originales con el fin de mantener el estándar culto de la lengua, con el consentimiento final de los autores.
Las opiniones expresadas en el manuscrito son responsabilidad exclusiva de los autores.
Cómo citar
1.png)
