[Affectation] Algo. Hongrois

 Niveau école ingénieurPartager :
			        
[Affectation] Algo. Hongrois
Posté par 
mrcha  11-11-14 à 12:56
Bonjour à toutes et à tous,

Je suis en train de travailler la recherche opérationnelle et plus précisément les affectations par la méthode Hongroise. Je n'ai aucun souci sur la méthode, mon problème réside dans le fait que ma matrice de départ n'est pas carrée (5x6)...

J'ai pensé à supprimer une colonne arbitrairement mais je ne trouve pas le même cout d'affectation en fonction de la colonne que je supprime. J'ai ensuite pensé à soustraite toutes les colonnes par une colonne pour en annuler une mais j'ai des chiffres négatifs...

Avez vous une idée ?

Merci

 Posté par 
LeDinore : [Affectation] Algo. Hongrois  11-11-14 à 13:02
Le but est schématiquement d'affecter 5 "individus" (A,B,C,D,E) à 6 "postes" (F,G,H,I,J,K). 

Si tu introduis un individu virtuel, appelons le "V", qui a un coût/gain constant et nul pour chaque affectation, Est-ce qu'alors tu ne te ramènes pas au cas 6 par 6  ? 
 Posté par 
LeDinore : [Affectation] Algo. Hongrois  11-11-14 à 13:04
Remarque : supprimer une colonne et résoudre, puis itérer pour chaque colonne afin de garder le meilleur résultat...

... doit également conduire à l'optimum. Mais ça doit être plus long sauf erreur...
 Posté par 
LeDinore : [Affectation] Algo. Hongrois  11-11-14 à 13:13
Si tu cherches le minimum : 

A : J

B : H

C : I

D : K

E : G

* : F

Coût * = 115
 Posté par 
LeDinore : [Affectation] Algo. Hongrois  11-11-14 à 13:19
Et un maximum possible : 

A : H 

B : K 

C : F 

D : G 

E : J

V : I 

Gain * = 255
 Posté par 
mrchare : [Affectation] Algo. Hongrois  11-11-14 à 13:41
Bonjour LeDino et merci pour ta réponse,

J'ai bien pensé à ajoute une ligne X où tous les coefficients sont nuls mais du coup j'ai un 0 par colonne dés le départ, ça ne fausse pas mon cout ?

Merci encore
 Posté par 
LeDinore : [Affectation] Algo. Hongrois  11-11-14 à 13:51
Citation :
J'ai bien pensé à ajoute une ligne X où tous les coefficients sont nuls mais du coup j'ai un 0 par colonne dés le départ, ça ne fausse pas mon cout ? 

Tu ajoutes effectivement une ligne de zéro à ton tableau.

Cette ligne matérialise le fait que tu vas bien devoir affecter une colonne (poste choisi parmi F à K) à aucune ligne (individu), ce qui revient au même que de dire que tu l'affectes à un individu virtuel qui a un coût/gain nul (qui ne change pas ta fonction économique).

Choisir le poste non affecté, ou choisir de lui affecter un individu fantôme à valeur nulle... est-ce que ça ne revient pas au même ?

Réfléchis-y par toi-même : c'est toi qui dois le "voir" .
 Posté par 
mrchare : [Affectation] Algo. Hongrois  11-11-14 à 13:55
Oui oui effectivement !! Merci bien

Je retrouve un cout minimal de 115, comme toi 
 Posté par 
LeDinore : [Affectation] Algo. Hongrois  11-11-14 à 14:13
Cool.

Comme quoi hongrois qu'on va pas y arriver... et on y arrive .
  Posté par 
mrchare : [Affectation] Algo. Hongrois  11-11-14 à 16:08