Buscando un algoritmo para minimizar el costo de los recorridos de borde en un gráfico bipartito sujeto a restricciones

Question

Tengo un conjunto de urnas que pueden tener cada una de las diferentes cantidades de arena. Los porteros pueden entregar arena a cada urna sujeta a una tarifa de transporte por unidad de arena. Cada portero tiene una cantidad finita de arena que son capaces de entregarse a cada urna. El objetivo es llenar las urnas con toda la arena disponible al tiempo que minimiza el costo total. Aquí hay un ejemplo motivador:

círculos negros muestran porteros. El valor en el centro de los círculos de Porter muestra la cantidad total de arena que pueden transportar. Los cuadrados grises muestran las urnas. El valor en el centro de las urnas muestra la cantidad de arena que puede contener una urna. Los bordes de Porter_urn muestran el costo de transportar 1 unidad de arena a una urna dada. El uso de este ejemplo, Porter 1, que tiene 100 unidades de arena, podría transportar 1 unidad de arena por un costo de 50 a urn 3, que puede contener un total de 65 unidades de arena. ¡Eso sería muy caro!

¿Hay un algoritmo para resolver este problema de optimización? Parece que quizás sea un flujo máximo problema o quizás un Multi-Knapsack problema? ¿O algún otro algoritmo de la investigación de operaciones?

Answer 1

Esto es recto una problema de flujo de costo mínimo .Todo lo que falta es un borde de la fuente a cada porter, con un costo cero y la capacidad igual al portero, y un borde de costo cero de cada urn al fregadero con capacidad igual a esa urna.