Problème d'affectation
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
Le problème d'affectation est un problème classique de recherche opérationnelle. L'objectif est de déterminer un couplage maximum dans un graphe biparti valué.
[modifier] Applications pratiques
L'application la plus classique de ce problème est l'affectation de n employés à n tâches. Chaque employé ne peut être affecté qu'à une seule tâche et à un degré de compétence différent pour chacune d'entre elles. On cherche à trouver l'affectation qui maximise la compétence totale des employés sur les tâches.
[modifier] Méthodes de résolution
L'algorithme hongrois permet de résoudre ce problème avec une complexité de O(n3)
