À la recherche d'un algorithme pour minimiser les coûts des traversées de bord dans un graphique bipartite soumis à des contraintes

Question

J'ai un ensemble d'urnes pouvant chacun tenir des quantités différentes de sable. Les porteurs peuvent livrer du sable à chaque urne soumis à des frais de transport par unité de sable. Chaque porteur a une quantité finie de sable qu'ils sont capables de livrer à chaque urne. L'objectif est de remplir les urnes avec tout le sable disponible tout en minimisant le coût total. Voici un exemple de motivation:

Les cercles noirs présentent des porteurs. La valeur au centre des cercles de porteurs montre la quantité totale de sable qu'ils peuvent transporter. Les carrés gris indiquent des urnes. La valeur au centre des urnes montre la quantité de sable qu'une urne peut contenir. Porter_Enworn Les bords montrent le coût du transport 1 unité de sable à une urne donnée. En utilisant cet exemple, Porter 1, qui compte 100 unités de sable pourrait transporter 1 unité de sable pour un coût de 50 à URN 3, qui peut contenir un total de 65 unités de sable. Ce serait très cher!

Y a-t-il un algorithme pour résoudre ce problème d'optimisation? Il semble peut-être qu'un Un flux maximum problème ou peut-être un Multi-Knapsack problème? Ou un autre algorithme de la recherche sur les opérations?

Answer 1

Ceci est tout droit sur un Problème de flux de coût minimum .Tout ce qu'il manque, c'est un bord de la source à chaque porteur avec des coûts et une capacité zéro égaux au porteur, et un bord de coût zéro de chaque urne à l'évier avec une capacité égale à cette urne.