logo móvil
Contáctanos

Problemas de flujo máximo generalizado inverso

Autores: Tayyebi, Javad; Deaconu, Adrian

Idioma: Inglés

Editor: MDPI

Año: 2019

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro