La méthode hongroise 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.
Il utilise la programmation linéaire (PL) pour effectuer une série d'étapes qui peuvent être automatisées. Ainsi, des outils tels que le logiciel statistique R (entre autres) disposent de plusieurs packages très utiles pour ces problèmes d'optimisation.
Origine de la méthode hongroise
Son créateur était le mathématicien hongrois (d'où son nom) Harold W. Kuhn en 1955. Un autre mathématicien, James Munkres, l'a révisé en 1957. Avec cette évolution, il a reçu d'autres noms tels que l'algorithme d'allocation de Munkres ou Kuhn-Munkres. .
En revanche, cette méthode a un précédent chez deux auteurs, Dénes König et Jenő Egerváry, tous deux juifs et hongrois. Le premier a développé la théorie des graphes sur laquelle est basé cet algorithme. Le second a généralisé le théorème de König et a permis à Kuhn de développer la méthode.
Étapes de la méthode hongroise
Les étapes à suivre permettent de réaliser la méthode hongroise de manière simple à l'aide d'un tableur. De plus, ce schéma que nous montrons nous permettra de voir de manière globale le processus que nous développerons en détail dans l'exemple final.
- Comme étapes préliminaires, vous devez affecter des personnes (lignes) à une série de projets (colonnes). De plus, il faut calculer les différents coûts de chaque projet selon qui le réalise et construire une matrice (C) avec ces informations.
- Dans la matrice (C) nous recherchons la valeur minimale de chaque ligne. Nous soustrayons cela de tous les éléments de la ligne et effectuons la même opération avec les colonnes. Une nouvelle matrice (C`) apparaîtra avec les résultats des opérations précédentes.
- Ensuite, nous créons le « graphe des égalités », qui nous permet de choisir les tâches et les projets les moins coûteux. L'optimum serait les éléments dont le résultat était nul. S'il est vrai qu'il n'y a pas d'élément avec une valeur nulle affectée à plus d'une ligne, l'algorithme se termine.
- Dans le cas contraire, une nouvelle affectation doit être effectuée. Une nouvelle matrice est réalisée sur laquelle une série de modifications sont appliquées, comme nous le verrons dans l'exemple. Nous recréons le graphique et continuons jusqu'à ce que nous ayons une matrice qui a au moins un zéro dans chaque ligne et dans des positions non répétitives.
- Avec ces informations, nous avons déjà les personnes et les projets assignés (les zéros) qui optimisent le problème. Si une tâche est déjà affectée dans une ligne précédente, elle est ignorée dans la suivante. Pour calculer le coût minimum, nous ajoutons les coûts de la matrice initiale qui apparaissent à la position de ces zéros.
Exemple de méthode hongroise
Regardons un exemple simple de la méthode hongroise de. Imaginons que nous ayons trois travailleurs et qu'ils doivent être affectés à trois projets. Nous créons la matrice initiale (C) et les valeurs de coût dans chaque cellule. Pour cela, vous devez utiliser les informations disponibles dans l'entreprise. Une fois que nous avons tout cela, nous commençons le processus. Une feuille de calcul peut vous aider.
Nous calculons les minimums de chaque ligne et les soustrayons des éléments de cette ligne et faisons de même avec les colonnes (étapes 1 et 2). Dans la matrice résultante (C`), nous traçons des lignes de telle sorte qu'elles couvrent tous les zéros et se coupent à leur tour (étape 3). Nous voyons qu'il y a deux lignes, mais la plus grande valeur du nombre de lignes ou de colonnes est de trois. Nous devons continuer.
Maintenant, nous choisissons le plus petit des nombres découverts, dans cet exemple c'est deux (bleu foncé). Nous le soustrayons des précédents et l'ajoutons à ceux qui se trouvent à l'intersection des lignes. Dans notre cas, il s'agit de deux autres (E3, T1). Nous nous retrouvons avec une nouvelle matrice (étape 4). Nous redessinons les lignes et comptons. Il y a trois lignes, comme le nombre de lignes ou de colonnes. L'algorithme est terminé.
Nous commençons par la ligne ou la colonne avec le moins de zéros (E1, T1). Si une tâche est déjà affectée, elle ne peut pas être réaffectée, par exemple, avec E2 vous ne pouvez pas utiliser le premier zéro de T1, puisque cette tâche a été affectée à E1. Le coût total, dans la méthode hongroise, sera la somme des coûts de la matrice originale (étape 1) située dans la même position que les zéros choisis (étape 5).
