Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Methode hongroise Heure Problème d ? a ?ectation et algorithme hongrois N O P Section Notes complémentaires Objectifs o Reconna? tre un problème d ? a ?ectation o Comprendre et appliquer l ? algorithme hongrois Les problèmes d ? a ?ectation Les problèmes

Heure Problème d ? a ?ectation et algorithme hongrois N O P Section Notes complémentaires Objectifs o Reconna? tre un problème d ? a ?ectation o Comprendre et appliquer l ? algorithme hongrois Les problèmes d ? a ?ectation Les problèmes d ? a ?ectation sont des cas spéciaux du problème de transport o? la demande associée à chaque destination est égale à Il existe une méthode ??la méthode hongroise ? qui simpli ?e la résolution du problème d ? a ?ectation Les problèmes d ? a ?ectation cij i j Min ? ? cijxij ? xij i ? n ? xij j ? n xij ? La méthode hongroise Matrice des coûts USINE V P F M O P Ex Le coût d ? a ?ecter le V P P ? à l ? usine est de La méthode hongroise Étape Réduction des lignes créer une nouvelle matrice des coûts en choisissant le coût minimal sur chaque ligne et en le soustrayant de chaque coût sur la ligne Ex La première ligne devient - - - - V P USINE RÉDUIT DE F M O P La méthode hongroise Étape Réduction des colonnes créer une nouvelle matrice des coûts en choisissant le coût minimal dans chaque colonne et en le soustrayant de chaque coût dans la colonne USINE V P F M O P RÉDUIT DE CLa méthode hongroise Étape Déterminer le nombre minimal de lignes nécessaires sur les lignes et les colonnes pour couvrir tous les zéros Si ce nombre est égal au nombre de lignes ou colonnes la matrice est réduite aller à l ? étape Si ce nombre est inférieur au nombre de lignes ou colonnes aller à l ? étape La méthode hongroise Dans ce cas le nombre minimal de lignes est de USINE V P F M O P Donc on va à l ? étape La méthode hongroise Étape Trouver la cellule de valeur minimum non- couverte par une ligne Soustraire cette valeur de toutes les cellules noncouvertes Ajouter cette valeur aux cellules situées à l ? intersection de deux lignes Retourner à l ? étape La méthode hongroise V P F M O P USINE Valeur minimum La méthode hongroise USINE V P F M O P - La méthode hongroise Maintenant le nombre minimal de lignes est de USINE V P F M O P Donc on passe à l ? étape CLa méthode hongroise Étape Déterminer la solution optimale USINE Note P ne V P pourrait pas F être choisi car l ? a ?ectation de O ? ne serait M O pas de coût P minimal La méthode hongroise Résultat AFFECTATION V P USINE F M O P COÛT TOTAL COÛT Algorithme hongrois Exemple C C C C P P P P Algorithme hongrois Exemple Étape Réduction des lignes C C C C P P P P ? ? ? ? Algorithme hongrois Exemple Algorithme hongrois Exemple Étape Réduction des lignes Étape Réduction des colonnes C C C C