Accueil > Informatique > RCP101 : Recherche opérationnelle et aide à la décision > Problème d’affectation

Problème d’affectation

mardi 21 juillet 2009, par frederic

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)

  1. 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é.
  2. 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).
  3. 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 \not{0} 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 \not{0} 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 \not{0}
c 4 3 6 6 0
d \not{0} 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 \not{0}
c 4 3 6 6 0
d \not{0} 6 1 1 5
e 8 0 1 \not{0} 3