Resumen

Este trabajo presenta un algoritmo para resolver un problema de flujo de coste mínimo (MCF) con un enfoque dual. El algoritmo mantiene la holgura complementaria en cada iteración y encuentra un camino de aumento actualizando el potencial de los nodos de forma iterativa. A continuación, el flujo puede aumentarse en la red original. En contraste con otros algoritmos populares, el algoritmo presentado no encuentra una red residual, ni encuentra un camino más corto. Además, nuestro algoritmo mantiene la información del potencial de nodo en cada iteración, y actualizamos el potencial de nodo dentro de iteraciones finitas para expandir la red admisible. Se presenta la validez de nuestro algoritmo. Los experimentos numéricos muestran que nuestro algoritmo es un algoritmo eficiente para el problema MCF, especialmente para la red con un pequeño intervalo de coste de flujo por unidad.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:algoritmo, potencial de nodos, flujo de coste mínimo, otros algoritmos populares, iteración, problema mcf, experimentos numéricos, red admisible, holgura complementaria, enfoque dual
• Keywords:algorithm, node potential, minimum cost flow, other popular algorithms, iteration, mcf problem, numerical experiments, admissible network, complementary slackness, dual approach