El Problema de flujo constante a costo mínimo en redes

Abstract

Dentro de los factores que influyeron en la realización del proyecto PAREIMM está la poca difusión de los temas de Redes en la Universidad de Sonora, y a la carencia de Software de este tipo. Lo que imposibilita que se puedan resolver numerosos problemas reales, que se plantean en el área. En la primera parte del trabajo se analizan y plantean problemas hasta llegar a obtener la red que los modela; el resolver dichos problemas es equivalente a encontrar un flujo de valor constante con costo mínimo. En el capitulo siguiente se establece toda la teoría completa necesaria para la demostración del teorema que garantiza la convergencia de cada uno de los dos algoritmos que resuelven el problema y que se implementaron. Los capítulos tres y cuatro, como ya se comento establecen cada uno el teorema central para cada algoritmo y se presenta la demostración detallada de él. Además, se da un panorama del tipo de estructuras y el manejo de la información que se utilizo en la implementación. También se presenta una corrida de escritorio con gráficas y con las estructuras de datos correspondientes para efectos de comparación. Al final del trabajo se presentan tres anexos importantes; el primero contiene los conceptos básicos de teoría de graficas que se requieren para entender el presente trabajo y el segundo contiene un pequeño manual del usuario, donde se explica de una manera sencilla como se opera cada uno de los programas y como se debe leer la solución al problema resuelto, también contiene este anexo el código de los programas. El ultimo de los anexos contiene los códigos de los programas implementados. Una importante observación es que en la realidad una solución de estos algoritmos puede no resolver completamente un problema real, debido a que las condiciones reales son mas complejas que las implementadas en la teoría y generalmente son afectados por otros factores difíciles de modelar completamente, pero las soluciones teóricas pueden dar un acercamiento a la solución real del problema.