next up previous
suivant: Le problème de l'arrondi monter: Problèmes faisant intervenir le précédent: Problèmes faisant intervenir le

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
\begin{figure}
\leavevmode
\begin{center}
\psfig{figure=res4.eps,width=10.0cm}
\end{center}
\end{figure}


next up previous
suivant: Le problème de l'arrondi monter: Problèmes faisant intervenir le précédent: Problèmes faisant intervenir le
Bruno Garcia 2000-12-17