Problemas de flujo máximo generalizado inverso
Autores: Tayyebi, Javad; Deaconu, Adrian
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
Problemas de flujo máximo generalizado inverso
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Flujo máximo
Problema generalizado de flujo máximo
Ganancia
Factores de pérdida
Problema inverso
Capacidades de arco
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
Una extensión natural de los problemas de flujo máximo se llama problema de flujo máximo generalizado teniendo en cuenta los factores de ganancia y pérdida para los arcos. Este artículo investiga un problema inverso correspondiente a este problema. Consiste en aumentar las capacidades de los arcos con el menor costo posible de manera que un flujo prescrito se convierta en un flujo máximo con respecto a las capacidades modificadas. El problema se denomina problema de flujo máximo generalizado (IGMF). Al principio, presentamos un método rápido que determina si el problema es factible o no. Luego, desarrollamos un algoritmo para resolver el problema bajo las distancias de tipo máximo en el tiempo. Además, demostramos que el problema es fuertemente NP-duro bajo distancias de tipo suma y proponemos un algoritmo heurístico para encontrar una solución casi óptima a estos problemas de NP-duros. Los experimentos computacionales muestran la precisión y eficiencia del algoritmo.
Descripción
Una extensión natural de los problemas de flujo máximo se llama problema de flujo máximo generalizado teniendo en cuenta los factores de ganancia y pérdida para los arcos. Este artículo investiga un problema inverso correspondiente a este problema. Consiste en aumentar las capacidades de los arcos con el menor costo posible de manera que un flujo prescrito se convierta en un flujo máximo con respecto a las capacidades modificadas. El problema se denomina problema de flujo máximo generalizado (IGMF). Al principio, presentamos un método rápido que determina si el problema es factible o no. Luego, desarrollamos un algoritmo para resolver el problema bajo las distancias de tipo máximo en el tiempo. Además, demostramos que el problema es fuertemente NP-duro bajo distancias de tipo suma y proponemos un algoritmo heurístico para encontrar una solución casi óptima a estos problemas de NP-duros. Los experimentos computacionales muestran la precisión y eficiencia del algoritmo.