Algorithme hongrois proposé par kuhn
Description
Il s'agit de l'algorithme Hongrois proposé par Kuhn.
Il s'agit d'une matrice carré, là où les valeurs infinies restent inchangées.
L'algorithme procède en trois étapes successives.
1- éliminer le plus petit élément de chacune des colonnes puis celui de chacune des lignes de la matrice des coûts.
2- Si, cette solution n'est pas optimale, on considère la ligne ayant un nombre minimal de zéros. On encadre l'un des zéros de cette ligne, puis on barre les zéros qui se trouvent sur la même ligne ou la même colonne que le zéro encadré. On procède de même pour toutes les lignes.
3- On marque toutes les lignes qui ne contiennent aucun zéro encadré
On marque les lignes qui ont un zéro encadré dans une colonne marqué
On marque les colonnes qui ont un ou plusieurs zéros barrés dans une ligne marquée.
On répète ces trois marquages successifs jusqu'à ce que l'on ne puisse plus affecter de nouveaux marquages.
On barre ensuite, les lignes non marquées ainsi que les colonnes marquées.
Dans le tableau réduit obtenu, on retranche la valeur de l'élément le plus petit aux colonnes non barrées et on l'ajoute aux lignes barrées.
On poursuit la procédure de traitement sur la matrice résultante en reprenant à la seconde phase jusqu'à l'obtention d'une solution optimale.
Il s'agit d'une matrice carré, là où les valeurs infinies restent inchangées.
L'algorithme procède en trois étapes successives.
1- éliminer le plus petit élément de chacune des colonnes puis celui de chacune des lignes de la matrice des coûts.
2- Si, cette solution n'est pas optimale, on considère la ligne ayant un nombre minimal de zéros. On encadre l'un des zéros de cette ligne, puis on barre les zéros qui se trouvent sur la même ligne ou la même colonne que le zéro encadré. On procède de même pour toutes les lignes.
3- On marque toutes les lignes qui ne contiennent aucun zéro encadré
On marque les lignes qui ont un zéro encadré dans une colonne marqué
On marque les colonnes qui ont un ou plusieurs zéros barrés dans une ligne marquée.
On répète ces trois marquages successifs jusqu'à ce que l'on ne puisse plus affecter de nouveaux marquages.
On barre ensuite, les lignes non marquées ainsi que les colonnes marquées.
Dans le tableau réduit obtenu, on retranche la valeur de l'élément le plus petit aux colonnes non barrées et on l'ajoute aux lignes barrées.
On poursuit la procédure de traitement sur la matrice résultante en reprenant à la seconde phase jusqu'à l'obtention d'une solution optimale.
Codes Sources
A voir également
- Algorithme hongrois proposé par kuhn
- Code maroc algorithme - Forum Visual Basic 6
- Algorithme d affectation - Forum Java
- Recherche d'un code ou de l'algorithme - Forum C / C++ / C++.NET
- Conversion algorithme en code vba - Forum VB.NET
- Algorithme keno excel ✓ - Forum Visual Basic 6
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.