Problème d'affectation

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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é. Le problème d'affectation peut être résolu en temps polynomial par l'algorithme hongrois, il appartient par conséquent à la classe de complexité P.

Applications pratiques[modifier | modifier le code]

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 chaque couple (tâche, employé) a un coût. Le but est de minimiser le coût total d'exécution des tâches.

Notes et références[modifier | modifier le code]


Articles connexes[modifier | modifier le code]

Problème des mariages stables