ECOLE SUPERIEURE DE MANAGEMENT
Recherche opérationnelle 3eme Année Management
Responsable de module : Dr. HAID ZAHIA
Semestre 02 année universitaire 2022/2023
PROBLEME D’AFFECTATION
Le problème dit «problème d'affectation» est tout à fait classique et apparemment bien
résolu. Il s'agit, sur un graphe biparti valu, de trouver un couplage maximum de valeur
extremum
Une situation classique où apparaît un graphe biparti est le problème de l'affectation.
On dit qu'un couplage M est parfait lorsque tout sommet de G est incident à une arête
de M.
Problème de l'affectation
Donnée : Un graphe G=(V,E)biparti avec des poids w:E→R sur les arêtes.
Tâche : Trouver un couplage parfait de poids minimal.
Ce problème apparaît dans quantité de situation .Comme précédemment, les sommets
du graphe biparti peuvent être des employés d'une part et des tâches à effectuer de
l’autre (on suppose qu'il y a autant d'employés que de tâches). Les poids peuvent
modéliser le coût de réalisation de la tâche par un employé donné. On veut réaliser
toutes les tâches avec un coût minimal, en supposant que tout employé peut réaliser
n'importe quelle tâche.
Il Ya de nombreux algorithmes qui résolvent ce problème avec cette complexité .On peut
également appliquer l'algorithme hongrois auquel il a été fait mention ci-dessus.
1) Formulation mathématique sous la forme d’un programme linéaire (la
modélisation)
À tout couple tâche/agent (i ,j), on associe une variable d’affectation, xij , binaire, qui
prend la valeur 1 si la tâche i est affectée à l’agent j et 0 sinon. Le coût total de
réalisation des tâches s’exprime alors par la somme :
Σn i=1 Σ j=1m cij . xij
Le nombre d’agents réalisant la tâche i est donné par : Σn i=1 xij , pour tout i = 1 à n
et le nombre de tâches réalisées par l’agent j est donné par : Σm j=1 xij , pour tout j =
1 à m. On peut donc modéliser le problème d’affectation sous la forme :
Min Σn i=1 Σm j=1 cij .xij
Σn i=1 xij ≤ 1 ∀ i = 1…..n
s.c Σm j=1 xij ≤ 1 ∀ j = 1…..m
xij ∈ {0,1} ∀ i = 1...n ∀ j = 1...m
2- Résolution d’un problème d’affectation
Condition d’existence d’un plan d’affectation (condition de la matrice
carré) : c'est-à-dire n=m
Remarque : Si ce n’est pas le cas, on peut y remédier en ajoutant des éléments (sommets)
fictifs et en définissant cij =0 ∀ i ou j fictif
2-1- La méthode hongroise "
La méthode hongroise " associé à KHÜN MUNKRES (1955) est un algorithme qui
permet de minimiser les coûts dans un problème d'optimisation basé sur la
programmation linéaire.
L'objectif de la méthode hongroise est de trouver le coût minimum d'un ensemble de
tâches qui doivent être effectuées par les personnes les plus appropriées
2-2- L’algorithme Hongrois
La méthode hongroise " est un algorithme spécialisé permettant de résoudre le
problème d’affectation. Il s’agit d’une procédure itérative qui transforme la matrice des
coûts en une suite de matrices équivalentes, jusqu’à ce que l’obtention d’une solution
optimale soit évidente.
La matrice finale est telle que toutes les entrées sont soit positives ou nulles et qu’une
affectation faisant appel seulement aux entrées nulles est possible. Cette affectation de
coût 0 est alors nécessairement optimale.
L’algorithme Hongrois peut être décrit de la façon suivante :
1. Dans chacune des rangées, identifier le coût minimal et soustraire celui-ci de
chacun des coûts dans la rangée correspondante.
2. Dans chacune des colonnes, identifier le coût minimal et soustraire celui-ci de
chacun des coûts dans la colonne correspondante.
3. Vérifier si une affectation de coût 0 est possible. Une façon de procéder à cette
vérification est d’identifier le nombre minimum de lignes horizontales et
verticales permettant de « barrer » ou couvrir toutes les entrées nulles. Si ce
nombre minimum correspond au nombre de rangées dans la matrice, alors une
affectation de coût 0 est possible et il faut aller ensuite à l’étape 6; sinon il faut
continuer à l’étape 4.
4. Ajouter des entrées nulles dans la matrice de la façon suivante :
Identifier le plus petit coût non couvert dans la matrice.
Soustraire le plus petit coût non couvert de chacune des entrées
non couvertes dans la matrice
Ajouter le plus petit coût non couvert aux entrées se trouvant à
l’intersection d’une ligne horizontale et verticale (les entrées qui
sont couvertes par deux lignes).
Il faut noter que les coûts dans les entrées couvertes par une seule
ligne ne changent pas.
5. Répéter les étapes 3 et 4 jusqu’à ce qu’une affectation de coût 0 soit possible.
6. Procéder à l’affectation optimale en considérant, une à une, les entrées de coût
nul. Pour ce faire, toujours donner la préférence aux rangées et aux colonnes
ayant une seule entrée de coût nul. À chaque fois qu’une entrée est choisie,
éliminer la rangée et la colonne correspondante. Répéter jusqu’à ce que toutes les
rangées et colonnes aient été éliminées.
EXEMPLE :
La matrice originale des coûts est la suivante :
1 2 3 4 5
A 5 4 3 5 1
B 9 8 1 2 3
C 7 6 3 5 4
D 2 3 4 7 6
E 6 2 6 1 2
T.A.F :
1. Formulez le problème.
2. Trouver l’affectation optimale
La solution :
1. La formulation du problème :
Min z = 5 x11+ 9 x12 +7 x13 +2x14 +6 x15 +4 x21 +8 x22+ 6 x23 +3 x24 +2 x25 + 3 x31 +1x32 +
3x33+ 4 x34+ 6 x35 + 5 x41 + 2x42 + 5 x43 +7 x44 +1 x45 +1x51 + 3x52 +4 x53 +6x54 +2 x55
Les contraintes :
x11+x12+x13+x14+x15 ≤ 1 x11+x21+x31+x41+x51 ≤ 1
x21+x22+x23+x24+x25 ≤ 1 x12+x22+x32+ x42+x52 ≤ 1
Oi x31+x32+x33+x34+x35 ≤ 1 DJ x13+x23+x33+x43+x53 ≤ 1
x41+x42+x43+x44+x45 ≤ 1 x14+x24+x34+x44+x54 ≤ 1
x51+x52+x53+x54+x55 ≤ 1 x15+x25+x35+x45+x55 ≤ 1
xij ≥ 0 xij ≥ 0
2. l’affectation optimale :
Condition d’existence d’un plan d’affectation (condition de la matrice carré) : c'est-à-
dire n=m 5=5 vérifier
la méthode Hongrois
étape 01 : soustraire les lignes
1 2 3 4 5
A 4 3 2 4 0
B 8 7 0 1 2
C 4 3 0 2 1
D 0 1 2 5 4
E 5 1 5 0 1
étape 02 : soustraire les colonnes
1 2 3 4 5
A 4 2 2 4 0
B 8 6 0 1 2
C 4 2 0 2 1
D 0 0 2 5 4
E 5 0 5 0 1
étape 03 : test de la solution
A partir de la matrice résultante, identifier (en surlignant ) le nombre
minimum de lignes horizontales et verticales afin de couvrir tous les zéros de la
matrice.
1 2 3 4 5
A 4 2 2 4 0
B 8 6 0 1 2
C 4 2 0 2 1
D 0 0 2 5 4
E 5 0 5 0 1
On note que le nombre de lignes et de colonnes couvrant tous les 0 est de 2
lignes verticales et 2 ligne horizontale, ce qui donne au total 4 lignes inférieur à 5
la dimension de la matrice. Par conséquent nous ne disposons pas encore de la
solution optimale. Nous devrons alors passer à une 4 eme étape
étape 04 : test de la solution
dans cette étape on Ajoute des entrées nulles dans la matrice de la façon suivante :
Identifier le plus petit coût non couvert dans la matrice.
Soustraire le plus petit coût non couvert de chacune des entrées
non couvertes dans la matrice
Ajouter le plus petit coût non couvert aux entrées se trouvant à
l’intersection d’une ligne horizontale et verticale (les entrées qui
sont couvertes par deux lignes).
Il faut noter que les coûts dans les entrées couvertes par une seule
ligne ne changent pas.
1 2 3 4 5
A 3 1 2 3 0
B 7 5 0 0 2
C 3 1 0 1 1
D 0 0 3 5 5
E 5 0 6 0 2
On constate que le nombre minimum de lignes pour couvrir tous les zéros de la
matrice est égal à 5 . Par conséquent on a une solution optimale.
Les entrées de la solution optimale correspondent aux entrées nulles de la matrice
ci-contre. Autrement dit, les affectations optimales sont :
étape 05 : le choix des zéros (l’affectation)
1 2 3 4 5
A 3 1 2 3 0
B 7 5 0 0 2
C 3 1 0 1 1
D 0 0 3 5 5
E 5 0 6 0 2
l’employé 5 affecté à la tache A
l’employé 4 affecté à la tache B
l’employé 3 affecté à la tache C
l’employé 1 affecté à la tache D
l’employé 2 affecté à la tache E
Le cout total d’affectation : 1+2+3+2+2 = 10
