Alla ricerca di un algoritmo per ridurre al minimo il costo dei traversali di bordo in un grafico bipartite soggetto a vincoli

Question

Ho una serie di urne che possono contenere diverse quantità di sabbia. I portatori possono offrire la sabbia a ciascuna urna soggetta a una tassa di trasporto per unità di sabbia. Ogni porter ha una quantità finita di sabbia è in grado di consegnare a ciascuna urna. L'obiettivo è riempire le urne con tutta la sabbia disponibile riducendo al minimo il costo totale. Ecco un esempio motivante:

I cerchi neri mostrano i portatori. Il valore nel centro dei cerchi del portiere mostra la quantità totale di sabbia che possono trasportare. I quadrati grigi mostrano urne. Il valore nel centro delle urne mostra la quantità di sabbia che un'urna può contenere. Porter_urn Bords mostra il costo del trasporto di 1 unità di sabbia a un dato urna. Usando questo esempio, Porter 1, che ha 100 unità di sabbia potrebbe trasportare 1 unità di sabbia per un costo di 50 a URN 3, che può contenere un totale di 65 unità di sabbia. Sarebbe molto costoso!

C'è un algoritmo per risolvere questo problema di ottimizzazione? Sembra che forse un flusso massimo problema o forse un Multi-zack problema? O qualche altro algoritmo dalla ricerca di operazioni?

Answer 1

Questo è dritto su un problema di flusso minimo-costo .Tutto ciò che manca è un vantaggio dalla fonte a ciascun porter con costo zero e capacità pari al portiere, e un bordo di costo zero da ogni urna al lavandino con capacità uguale a quell'urn.