- Quelle est la méthode hongroise?
- Étape 1: soustrayez les minima de chaque ligne
- Étape 2: soustrayez les minimums de chaque colonne
- Étape 3: couvrir tous les zéros avec un nombre minimum de lignes
- Étape 4: créer des zéros supplémentaires
- Allocation optimale
- Exemple
- Étape 1: soustrayez les minima de chaque ligne
- Étape 2: soustrayez les minimums de chaque colonne
- Étape 3: couvrir tous les zéros avec un nombre minimum de lignes
- Étape 4: créer des zéros supplémentaires
- Étape 3 (répéter)
- Allocation optimale
- Références
La méthode hongroise est un algorithme utilisé dans les problèmes d'allocation lorsque vous souhaitez minimiser les coûts. Autrement dit, il est utilisé pour trouver le coût minimum en affectant plusieurs personnes à diverses activités en fonction du moindre coût. Chaque activité doit être attribuée à une personne différente.
Un problème d'allocation est un type particulier de problème de programmation linéaire, où le but est de minimiser le coût ou le temps de réalisation d'un certain nombre de travaux par plusieurs personnes.
Source: pixabay.com
L'une des caractéristiques importantes du problème d'allocation est qu'un seul travail (ou travailleur) est affecté à une machine (ou un projet).
Cette méthode a été développée par le mathématicien hongrois D. Konig. Pour cette raison, elle est connue sous le nom de méthode hongroise pour les problèmes d'affectation. Il est également connu sous le nom d'algorithme d'allocation de Kuhn-Munkres.
Tout problème d'allocation peut être facilement résolu en appliquant cette méthode qui se compose de deux phases:
- Avec la première phase, des réductions de lignes et des réductions de colonnes sont effectuées.
- Dans la deuxième phase, la solution est optimisée sur une base itérative.
Quelle est la méthode hongroise?
La méthode hongroise comprend quatre étapes. Les deux premières étapes ne sont exécutées qu'une seule fois, tandis que les étapes 3 et 4 sont répétées jusqu'à ce qu'une allocation optimale soit trouvée.
Une matrice carrée d'ordre n par n est considérée comme une donnée d'entrée, qui ne doit contenir que des éléments non négatifs.
Pour un problème donné, si le nombre de lignes de la matrice n'est pas égal au nombre de colonnes, une ligne factice ou une colonne factice doit être ajoutée, selon le cas. Les coûts d'allocation pour ces cellules factices sont toujours attribués à zéro.
Étape 1: soustrayez les minima de chaque ligne
Pour chaque ligne du tableau, l'élément avec la valeur la plus faible est sélectionné et soustrait de chaque élément de cette ligne.
Étape 2: soustrayez les minimums de chaque colonne
De même, l'élément avec la valeur la plus faible est sélectionné pour chaque colonne et soustrait de chaque élément de cette colonne.
Étape 3: couvrir tous les zéros avec un nombre minimum de lignes
Tous les zéros de la matrice résultant de l'étape 2 doivent être couverts en utilisant un nombre minimum de lignes horizontales et verticales, soit par lignes, soit par colonnes.
Si un total de n lignes est nécessaire pour couvrir tous les zéros, où n est égal à la taille n fois n de la matrice, une allocation optimale entre les zéros sera obtenue et donc l'algorithme s'arrête.
Sinon, si moins de n lignes sont nécessaires pour couvrir tous les zéros du tableau, passez à l'étape 4.
Étape 4: créer des zéros supplémentaires
Le plus petit élément de la matrice (appelé k) qui n'est pas couvert par l'une des lignes réalisées à l'étape 3 est sélectionné.
La valeur de k est soustraite de tous les éléments qui ne sont pas couverts par les lignes. Par la suite, la valeur de ka est ajoutée à tous les éléments couverts par l'intersection de deux lignes.
Les éléments couverts par une seule ligne sont laissés tels quels. Après avoir effectué cette étape, vous revenez à l'étape 3.
Allocation optimale
Une fois l'algorithme arrêté à l'étape 3, un ensemble de zéros est choisi de telle sorte que chaque ligne et chaque colonne n'ait qu'un seul zéro sélectionné.
Si dans ce processus de sélection il n'y a pas de zéro unique dans une ligne ou une colonne, l'un de ces zéros sera choisi. Les zéros restants dans cette colonne ou cette ligne sont supprimés, répétant la même chose pour les autres affectations également.
S'il n'y a pas d'attribution de zéro unique, il existe plusieurs solutions. Cependant, le coût restera le même pour différents ensembles d'affectations.
Toutes les lignes ou colonnes factices qui ont été ajoutées sont supprimées. Les zéros choisis dans cette matrice finale correspondent donc à l'affectation idéale requise dans la matrice d'origine.
Exemple
Considérons une entreprise où il y a quatre activités (A1, A2, A3, A4) qui doivent être exercées par quatre travailleurs (T1, T2, T3, T4). Une activité doit être attribuée par travailleur.
La matrice suivante montre le coût d'affectation d'un certain travailleur à une certaine activité. L'objectif est de minimiser le coût total de la tâche composée de ces quatre activités.
Étape 1: soustrayez les minima de chaque ligne
Vous commencez par soustraire l'élément avec la valeur minimale dans chaque ligne des autres éléments de cette ligne. Par exemple, le plus petit élément de la première rangée est 69. Par conséquent, 69 est soustrait de chaque élément de la première rangée. La matrice résultante est:
Étape 2: soustrayez les minimums de chaque colonne
De la même manière, l'élément avec la valeur minimale de chaque colonne est soustrait des autres éléments de cette colonne, obtenant la matrice suivante:
Étape 3: couvrir tous les zéros avec un nombre minimum de lignes
Nous allons maintenant déterminer le nombre minimum de lignes (horizontales ou verticales) nécessaires pour couvrir tous les zéros de la matrice. Tous les zéros peuvent être couverts en utilisant 3 lignes:
Puisque le nombre de lignes requis est de trois et qu'il est inférieur à la taille de la matrice (n = 4), nous continuons avec l'étape 4.
Étape 4: créer des zéros supplémentaires
Le plus petit élément non couvert par les lignes est sélectionné, dont la valeur est 6. Cette valeur est soustraite de tous les éléments non couverts et cette même valeur est ajoutée à tous les éléments couverts par l'intersection de deux lignes. Cela donne la matrice suivante:
Comme indiqué dans la méthode hongroise, la troisième étape doit être répétée.
Étape 3 (répéter)
Là encore, le nombre minimum de lignes nécessaires pour couvrir tous les zéros de la matrice est déterminé. Cette fois, quatre lignes sont nécessaires:
Comme le nombre de lignes nécessaires est de 4, égal à la taille de la matrice (n = 4), nous avons une allocation optimale entre les zéros de la matrice. Par conséquent, l'algorithme s'arrête.
Allocation optimale
Comme l'indique la méthode, la sélection faite des zéros suivants correspond à une affectation optimale:
Cette sélection de zéros correspond à l'allocation optimale suivante dans la matrice de coût d'origine:
Par conséquent, le travailleur 1 doit effectuer l'activité 3, le travailleur 2, l'activité 2, le travailleur 3, l'activité 1 et le travailleur 4 doit effectuer l'activité 4. Le coût total de cette affectation optimale est de 69 + 37 + 11 + 23 = 140.
Références
- Algorithme hongrois (2019). L'algorithme hongrois. Tiré de: hungarianalgorithm.com.
- Étude (2019). Utilisation de l'algorithme hongrois pour résoudre les problèmes d'attribution. Tiré de: study.com.
- Emplois de sagesse (2018). Méthode hongroise de résolution du problème d'affectation - Techniques quantitatives de gestion. Tiré de:isdomjobs.com.
- Geeks pour les geeks (2019). Algorithme hongrois pour le problème d'affectation. Tiré de: geeksforgeeks.org.
- Karleigh Moore, Nathan Landman (2019). Algorithme de correspondance maximum hongrois. Brillant. Tiré de: brilliant.org.