Grafos: flujo máximo a coste mínimo con algoritmo de BUSACKER-GOWEN | | UPV

Título: Grafos: flujo máximo a coste mínimo con algoritmo de BUSACKER-GOWEN

Descripción: Resolución de problema ejemplo de de flujo máximo a coste mínimo en un grafo mediante el algoritmo de BUSACKER-GOWEN. Miralles Insa, CJ. (2021). Grafos: flujo máximo a coste mínimo con algoritmo de BUSACKER-GOWEN. Universitat Politècnica de València. http://hdl.handle.net/10251/167539

Descripción automática: En este video, el profesor explica el problema del flujo máximo a coste mínimo en teoría de grafos, utilizando un algoritmo específico. El objetivo es enviar la máxima cantidad de flujo desde un nodo inicial a uno final en una red, minimizando el coste asociado al traslado.

Se define el problema y se muestra la aplicación del algoritmo a través de un ejemplo práctico. Se diferencian dos grafos: uno de costes y otro de flujos. Se describe el funcionamiento del algoritmo, que incluye dos pasos: hallar la ruta más económica y luego mover la mayor cantidad de flujo permitida por esa ruta. Se utiliza un algoritmo conocido para encontrar caminos óptimos y, cuando se presentan costes negativos, se recurre a otro algoritmo reconocido.

Iterando este proceso, se van saturando caminos y ajustando el grafo de costes, bloqueando las rutas ya saturadas y buscando alternativas. Eventualmente, se llega a una solución donde no se pueden trazar más rutas y se obtiene el flujo óptimo al coste mínimo. En el video se realiza la interpretación de la solución, restando del grafo inicial los flujos obtenidos para esclarecer la distribución final. El resultado es un flujo total de 53 unidades con un coste de 584.000 euros.

Se concluye subrayando que el método utilizado es heurístico y puede adaptarse a las preferencias del decisor, atendiendo al carácter multiobjetivo del problema.

Autor/a: Miralles Insa Cristóbal Javier



Universitat Politècnica de València UPV: https://www.upv.es
Más vídeos en:    / valenciaupv  
Accede a nuestros MOOC: https://upvx.es

#Grafos #Flujo máximo #Coste mínimo #Algoritmo de BUSACKER-GOWEN #ORGANIZACION DE EMPRESAS #1207 - Investigación operativa