Solución de red de flujo de probabilidad de asignación

Question

Tengo un problema de asignación con la matriz de costo C, por ejemplo:

21 30 26 16 20
27 29 28 20 38
39 25 21 19 23
28 24 30 29 16
30 33 32 17 31

donde c [i] [j] significa costo para el trabajador i para hacer trabajo j.

¿Cómo puedo resolver esto con un algoritmo de flujo de red? Agradecería cualquier pista.

Answer 1

En caso de que todavía esté buscando una solución, puede resolver esto como un Problema de flujo de costo mínimo:

1. Cree un nodo fuente conectado a sus n trabajadores por bordes con capacidad 1 y costo 0
2. Conecte cada trabajador i a cada trabajo j por bordes de la capacidad 1 y costo c [i] [j
3. Finalmente, conecte cada trabajo a un nodo de sumidero con bordes de capacidad 1 y costo 0

Su problema es equivalente a minimizar el costo de empujar las unidades de flujo N a través de la red de la fuente al fregadero.