Algorithme hongrois, ou comment les mathématiques aident à assigner des devoirs

Bonjour mes amis! Dans cet article, je voudrais parler d'un algorithme intéressant de la discipline «recherche opérationnelle», à savoir sur la méthode hongroise et comment résoudre les problèmes d'affectation avec son aide. Je vais aborder la théorie dans quels cas et pour quelles tâches cet algorithme est applicable, je l’analyserai pas à pas sur mon exemple inventé, et partagerai ma modeste esquisse du code pour son implémentation dans le langage R. Commençons!

Quelques mots sur la méthode

Afin de ne pas peindre beaucoup de théorie avec des termes et des définitions mathématiques, je propose d'envisager quelques options pour construire le problème d'affectation, et je pense que vous comprendrez immédiatement dans quels cas nous appliquerons la méthode hongroise:

• La tâche de nommer des employés à des postes. Il est nécessaire de répartir les travailleurs à des postes afin que l'efficacité maximale soit atteinte, ou qu'il y ait un coût de travail minimal.
• Affectation de machines aux sections de production. La répartition des machines de sorte que lors de leur fonctionnement la production soit aussi rentable que possible, ou le coût de leur maintenance est minime.
• La sélection des candidats pour divers postes vacants est estimée. Nous analyserons cet exemple ci-dessous.

Comme vous pouvez le voir, il existe de nombreuses options pour lesquelles la méthode hongroise est applicable, et des tâches similaires se posent dans de nombreux domaines d'activité.

En conséquence, la tâche doit être résolue de sorte qu'un interprète (personne, machine, outil, ...) ne puisse effectuer qu'un seul travail, et chaque travail a été effectué par un seul interprète.

Une condition nécessaire et suffisante pour résoudre un problème est son type fermé. C'est-à-dire lorsque le nombre d'interprètes = le nombre d'œuvres (N = M). Si cette condition n'est pas remplie, vous pouvez ajouter des interprètes fictifs ou des œuvres fictives dont les valeurs dans la matrice seront nulles. Cela n'affectera pas la solution du problème, il ne lui donnera que le type fermé nécessaire.

Algorithme pas à pas par exemple

Énoncé du problème: Qu'une conférence scientifique importante soit planifiée. Pour le diriger, vous devez configurer le son, la lumière, les images, enregistrer les invités et préparer les pauses entre les représentations. Il y a 5 organisateurs pour cette tâche. Chacun d'eux a certaines estimations de la performance d'un travail particulier (supposons que ces estimations soient définies comme la moyenne arithmétique des évaluations de leurs employés). Il est nécessaire de répartir les organisateurs afin que leur score total soit maximal. La tâche a la forme suivante:


Si le problème est résolu au maximum (comme dans notre cas), alors dans chaque ligne de la matrice, il est nécessaire de trouver l'élément maximum, de le soustraire de chaque élément de la ligne correspondante et de multiplier la matrice entière par -1. Si le problème est résolu au minimum, cette étape doit être ignorée.


Dans chaque ligne et dans chaque colonne, il ne devrait y avoir qu'un seul zéro sélectionné. (c'est-à-dire que lorsque zéro a été choisi, les zéros restants dans cette ligne ou dans cette colonne ne sont plus pris en compte). Dans ce cas, cela ne peut pas être fait:


( Si le problème est résolu au minimum, vous devez commencer par cette étape ). Nous continuons la solution plus loin. Réduction de la matrice par lignes (recherchez l'élément minimum dans chaque ligne et soustrayez-le de chaque élément, respectivement):


Parce que Étant donné que tous les éléments minimaux sont nuls, la matrice n'a pas changé. Nous effectuons la réduction des colonnes:


Encore une fois, nous cherchons à ce que dans chaque colonne et dans chaque ligne, il n'y ait qu'un seul zéro sélectionné. Comme on peut le voir ci-dessous, dans ce cas, il est impossible de le faire. J'ai présenté deux options pour choisir les zéros, mais aucune n'a donné le résultat souhaité:


Nous continuons la décision. Biffez les lignes et les colonnes qui ne contiennent aucun élément ( IMPORTANT! Le nombre de croisements doit être minimal ). Parmi les éléments restants, nous recherchons le minimum, le soustrayons des éléments restants (qui ne sont pas barrés) et ajoutons aux éléments qui sont situés à l'intersection des lignes et des colonnes barrées (ce qui est marqué en vert y est soustrait; ce qui est marqué en or y est résumé; puis, ce qui n'est pas peint - ne pas toucher):


Comme vous pouvez le voir maintenant, dans chaque colonne et ligne, il n'y a qu'un seul zéro sélectionné. Nous complétons la solution du problème!


Remplacez dans le tableau initial l'emplacement des zéros sélectionnés. Ainsi, nous obtenons le plan optimal, ou optimal, dans lequel les organisateurs sont répartis entre le travail et la somme des estimations s'est avérée maximale:


Si vous résolvez le problème et qu'il vous est toujours impossible de choisir des zéros pour qu'il n'y en ait qu'un dans chaque colonne et ligne, nous répétons l'algorithme à partir de l'endroit où la réduction par lignes a été effectuée (l'élément minimum dans chaque ligne).

Implémentation du langage de programmation R

L'algorithme hongrois est implémenté à l'aide de récursions. J'espère que mon code ne causera pas de difficultés. Vous devez d'abord compiler trois fonctions, puis lancer les calculs.

Les données pour résoudre le problème proviennent du fichier example.csv qui a la forme:



Le résultat du programme:

En conclusion

Merci beaucoup d'avoir pris le temps de lire mon article. Je fournirai tous les liens utilisés ci-dessous. J'espère que vous avez appris quelque chose de nouveau par vous-même ou mis à jour vos anciennes connaissances. Tout succès, bonne et bonne chance!

Ressources utilisées

1. Wikipédia pris d' assaut
2. Et d' autres bons sites
3. A souligné pour moi-même certaines informations de cet article.