Algoritmos en pocas palabras, 2ª edición

Capítulo 8. Algoritmos de flujo de red

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: [e-mail]

Muchos problemas pueden presentarse como una red de vértices y perímetros, con una capacidad asociada a cada perímetro por el que fluyen mercancías. Los algoritmos de este capítulo surgen de la necesidad de resolver estas clases específicas de problemas. Ahuja (1993) contiene un amplio análisis de numerosas aplicaciones de los algoritmos de flujo de red:

Asignación

Dado un conjunto de tareas a realizar y un conjunto de empleados, que pueden costar distintas cantidades en función de la tarea asignada, asigna los empleados a las tareas minimizando el gasto total.

Emparejamiento bipartito

Dado un conjunto de candidatos que han sido entrevistados para un conjunto de puestos vacantes, encuentra un emparejamiento que maximice el número de candidatos seleccionados para puestos de trabajo para los que están cualificados.

Caudal máximo

Dada una red que muestra la capacidad potencial de transporte de mercancías entre dos lugares, calcula el flujo máximo soportado por la red.

Transporte

Determina la forma más rentable de enviar mercancías desde un conjunto de fábricas proveedoras a un conjunto de tiendas minoristas.

Transbordo

Determinar la forma más rentable de enviar mercancías desde un conjunto de fábricas proveedoras a un conjunto de tiendas minoristas, utilizando potencialmente un conjunto de almacenes como estaciones de ...