Chez Ptit GarsAccueil > Informatique > RCP101 : Recherche opérationnelle et aide à la décision > Problème d’affectation
Problème d’affectation
mardi 21 juillet 2009, par
Affecter 4 personnes à 4 taches comment faire ?
Soit 4 personnes A, B,C,D
et 4 taches a,b,c,d
La méthode hongroise
tableau représentant les coefficients de préférence des différentes personnes :
| A | B | C | D | E | |
| a | 9 | 6 | 7 | 3 | 4 |
| b | 2 | 1 | 9 | 1 | 8 |
| c | 4 | 3 | 2 | 2 | 7 |
| d | 9 | 1 | 8 | 8 | 3 |
| e | 1 | 7 | 8 | 9 | 5 |
la personne ’a’ veut vraiment aller sur le poste A éventuellement C voir B mais ne veut pas aller en E ou D, etc...
la méthode hongroise est que c’est un algorithme de minimisation donc la première étape est de transformer la formulation du problème en introduisant _ la notion de regret.
Le regret est égal au max moins chaque note sur tout le tableau.
Exemple de la ligne 1
Le max égale 9
Les valeur d’origine : 9 6 7 3 4
on fait 9- a chaque valeur, ce qui nous donne :
| A | B | C | D | E | |
| a | 9-9 | 9-6 | 9-7 | 9-3 | 9-4 |
| b | 9-2 | 9-1 | 9-9 | 9-1 | 9-8 |
| c | 9-4 | 9-3 | 9-2 | 9-2 | 9-7 |
| d | 9-9 | 9-1 | 9-8 | 9-8 | 9-3 |
| e | 9-1 | 9-7 | 9-8 | 9-9 | 9-5 |
Ce qui nous donne le tableau final :
| A | B | C | D | E | |
| a | 0 | 3 | 2 | 6 | 5 |
| b | 7 | 8 | 0 | 8 | 1 |
| c | 5 | 6 | 7 | 7 | 2 |
| d | 0 | 8 | 1 | 1 | 6 |
| e | 8 | 2 | 1 | 0 | 4 |
Ensuite pour les colonnes, il faut avoir un 0 dans chaque colonne :
Colonne B, on enlève 2 (le min sur cette colonne)
Colonne E, on enlève 1 (le min sur cette colonne)
| A | B | C | D | E | ||
| a | 0 | 3 | 2 | 6 | 5 | |
| b | 7 | 8 | 0 | 8 | 1 | |
| c | 5 | 6 | 7 | 7 | 2 | |
| d | 0 | 8 | 1 | 1 | 6 | |
| e | 8 | 2 | 1 | 0 | 4 | |
| vi | 0 | 2 | 0 | 0 | 1 |
| A | B | C | D | E | |
| a | 0 | 1 | 2 | 6 | 4 |
| b | 7 | 6 | 0 | 8 | 0 |
| c | 5 | 4 | 7 | 7 | 1 |
| d | 0 | 6 | 1 | 1 | 5 |
| e | 8 | 0 | 1 | 0 | 3 |
Vi correspond au minimum de chaque colonne.
Idem pour les lignes :
| A | B | C | D | E | ui | |
| a | 0 | 1 | 2 | 6 | 4 | 0 |
| b | 7 | 6 | 0 | 8 | 0 | 0 |
| c | 5 | 4 | 7 | 7 | 1 | 1 |
| d | 0 | 6 | 1 | 1 | 5 | 0 |
| e | 8 | 0 | 1 | 0 | 3 | 0 |
| A | B | C | D | E | |
| a | 0 | 1 | 2 | 6 | 4 |
| b | 7 | 6 | 0 | 8 | 0 |
| c | 4 | 3 | 6 | 6 | 0 |
| d | 0 | 6 | 1 | 1 | 5 |
| e | 8 | 0 | 1 | 0 | 3 |
Vi correspond au minimum de chaque colonne.
Au final on doit avoir un 0 pour chaque ligne et chaque colonne
Algorithme d’affectation des zéros.
Considérer les lignes ayant le nombre minimum de zéro (lignes a, c, d, dans notre exemple comportent un zéro)
- Choisir la ligne ayant un nombre minimum de zéros, affecter le zéro à la liaison correspondante. Le zéro est dit encadré.
ex:Ligne, a, et affectons le zéro correspondant à la liaison aA, zéro (aA) encadré. - Du fait ce choix, il n’est plus possible d’utiliser le(s) zéro(s), s’il en existe, de la colonne ou de la ligne correspondant à ce zéro encadré nous dirons que ce(s) zéro(s) est(sont barré(s). ex : zéro (dA).
- Retour en 1 tant qu’il existe des zéros non encadrés ou non barrés.
Pour des raison d’affichage :
– les valeurs encadrée sont remplacé par du gras
Ligne a : aA, zéro (aA) encadré
Les 0 de la ligne a et de la colonne A sont barré
| A | B | C | D | E | |
| a | 0 | 1 | 2 | 6 | 4 |
| b | 7 | 6 | 0 | 8 | 0 |
| c | 4 | 3 | 6 | 6 | 0 |
| d |  |
6 | 1 | 1 | 5 |
| e | 8 | 0 | 1 | 0 | 3 |
Ligne c : cE, zéro (cE) encadré
Les 0 de la ligne c et de la colonne E sont barré
| A | B | C | D | E | |
| a | 0 | 1 | 2 | 6 | 4 |
| b | 7 | 6 | 0 | 8 | 0B |
| c | 4 | 3 | 6 | 6 | 0 |
| d | |
6 | 1 | 1 | 5 |
| e | 8 | 0 | 1 | 0 | 3 |
Ligne b : bC, zéro (bC) encadré
les 0 de la ligne b et de la colonne C sont barré
| A | B | C | D | E | |
| a | 0 | 1 | 2 | 6 | 4 |
| b | 7 | 6 | 0 | 8 | |
| c | 4 | 3 | 6 | 6 | 0 |
| d | |
6 | 1 | 1 | 5 |
| e | 8 | 0 | 1 | 0 | 3 |
Ligne e : eB, zéro (eB) encadré
Les 0 de la ligne e et de la colonne B sont barré
| A | B | C | D | E | |
| a | 0 | 1 | 2 | 6 | 4 |
| b | 7 | 6 | 0 | 8 | |
| c | 4 | 3 | 6 | 6 | 0 |
| d | |
6 | 1 | 1 | 5 |
| e | 8 | 0 | 1 | |
3 |