Un padre de familia tiene cinco hijos (adolescentes) y les quiere asignar cinco tareas domésticas. La experiencia pasada le ha enseñando al padre que resulta contraproducente imponerle obligaciones a un hijo. Teniendo esto en mente, les pide a sus hijos que hagan una lista de sus preferencias entre las cinco tareas, como lo muestra la siguiente tabla.
| Niño | Tarea preferida |
| Rif | 3,4, o 5 |
| Mai | 1 |
| Ben | 1 o 2 |
| Kim | 1, 2, o 5 |
| Ken | 2 |
Ahora, la modesta meta del padre es terminar tantas tareas como sea posible, respetando al mismo tiempo las preferencias de sus hijos. Determine el número máximo de tareas que se pueden terminar y la asignación de las tareas a los hijos.
La Red aplicando el algoritmo de flujo máximo (Ford-Fulkerson) nos quedaría de la siguiente manera:
La cual nos indica que la mayor cantidad de tareas que se pueden terminar son 4 y quedarían distribuidas de la siguiente manera:
Rif tarea 3 Mientras que a Ken no se le podría asignar una tarea
Mai tarea 1 que le agradara.
Ben tarea 2
Kim tarea 5
No hay comentarios:
Publicar un comentario