Problème d'affectation

Le problème peut être énoncé de la manière suivante[1]. Étant donné un ensemble d'agents ${\displaystyle S}$ et un ensemble de tâches ${\displaystyle T}$, On modélise le problème par un graphe biparti ${\displaystyle G=((S,T),E)}$, avec une fonction de poids sur les arêtes ${\displaystyle c:E\rightarrow \mathbb {R} }$. Le problème d'affectation consiste donc à trouver un couplage ${\displaystyle F\subseteq E}$, avec ${\displaystyle |F|=|T|}$, et minimisant la somme ${\displaystyle \sum _{e\in F}c(e)}$ des poids des arêtes de ${\displaystyle F}$.

L'algorithme hongrois, parfois appelé algorithme de Kuhn-Munkres, résout le problème en temps polynomial. On peut aussi écrire le problème sous forme d'un problème d'optimisation linéaire. Sa solution sera entière car la matrice ainsi définie est totalement unimodulaire.

L'application la plus classique de ce problème est, en ordonnancement de tâches, l'affectation de ${\displaystyle n}$ machines à ${\displaystyle m}$ tâches. Chaque machine ne peut être affectée qu'à une seule tâche et chaque couple (tâche;machine) a un coût. Le but est de minimiser le coût total d'exécution des tâches.

L'algorithme d'Edmonds pour les couplages traite le problème du couplage de cardinal maximum dans tous les graphes en temps polynomial.

Le problème d'affectation est aussi lié au problème du flot de coût minimum.

• Problème des mariages stables