Le problème des représentants

Soit une entreprise comptant $n$ employés $E_1$, $E_2$, ..., $E_n$. Ceux-ci sont répartis dans $m$ corps de métiers et $r$ catégories socio-professionnelles ; un employé pouvant appartenir à plusieurs corps de métiers mais à une et une seule catégorie socio-professionnelle. Lors des élections des représentants du personnel (modèle grand-breton), chaque corps de métier doit désigner 1 représentant pour le bureau sachant que chaque catégorie socio-professionnelle $j$ ne peut avoir plus de $u_j$ membres siégeant. La question que l'on va résoudre en utilisant un flot maximal est la suivante :

Existe-t-il un bureau compatible avec ces contraintes ?

Pour répondre à cette (légitime) interrogation, on va utiliser le graphe suivant. On associe à chaque corps de métier $C_i$ un sommet $c_i$ et un arc $(s,\,c_i)$ de capacité maximale 1 représentant le fait que chaque corps de métier désigne 1 représentant. A l'autre bout du graphe, chaque catégorie socio-professionnelle $P_j$ se voit représentée par un sommet $p_j$ auquel on associe immédiatement l'arc $(p_j,\,t)$ de capacité maximale $u_j$, nombre maximal de membres de la catégorie professionnelle autorisés à siéger au bureau. Finalement chaque employé $E_k$ est modélisé par le sommet correspondant $e_k$. L'appartenance d'un employé à ses corps de métier est représentée par des arcs du type $(c_i,\,e_k)$ de capacité maximale 1, alors que son appartenance à une catégorie socio-professionnelle est trahie par un arc unique du type $(e_k,\,p_j)$. Le bureau est réalisable s'il existe un flot de valeur $m$ compatible avec le réseau ainsi constitué, ce qui implique que $\sum u_j \geqslant m$. Un tel flot, s'il existe, pourra être obtenu en résolvant un problème de flot maximum sur le réseau, car $n$ est une borne max pour la valeur du flot. La figure suivante illustre un réseau modélisant ce problème de représentation.

Figure 5.4: Modélisation du problème des représentants dans un réseau