Procurando por um algoritmo para minimizar o custo de travessuras de borda em um gráfico bipartido sujeito a restrições

Question

Eu tenho um conjunto de urnas que podem realizar diferentes quantidades de areia. Os porteiros podem entregar areia a cada urna sujeita a uma taxa de transporte por unidade de areia. Cada porteiro tem uma quantidade finita de areia, elas são capazes de entregar a cada urna. O objetivo é preencher as urnas com toda a areia disponível, minimizando o custo total. Aqui está um exemplo motivador:

Black Circles mostram porteiros. O valor no centro dos círculos de Porter mostram a quantidade total de areia que eles podem transportar. Quadrados cinzentos mostram urnas. O valor no centro das urnas mostram a quantidade de areia que uma urna pode segurar. Porter_urn bordas mostram o custo de transportar 1 unidade de areia para uma determinada urna. Usando este exemplo, Porter 1, que tem 100 unidades de areia poderiam transportar 1 unidade de areia por um custo de 50 a urna 3, que pode conter um total de 65 unidades de areia. Isso seria muito caro!

Existe um algoritmo para resolver esse problema de otimização? Parece que talvez um fluxo máximo problema ou talvez um Multi-Knapsack problema? Ou algum outro algoritmo da pesquisa de operações?

Answer 1

Isto é direto de um problema de fluxo de custo mínimo .Tudo o que está faltando é uma borda da fonte a cada porteiro com custo zero e capacidade igual ao porteiro, e uma borda de custo zero de cada urna para a pia com capacidade igual a essa urna.