Remerciez-le!

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

466 Heure 22 : Problème d’affectation et algorithme hongrois N.O.P. Section 7.3

466 Heure 22 : Problème d’affectation et algorithme hongrois N.O.P. Section 7.3.3 Notes complémentaires Objectifs : J Reconnaître un problème d’affectation ; J Comprendre et appliquer l’algorithme hongrois. 467 Les problèmes d’affectation Les problèmes d’affectation sont des cas spéciaux du problème de transport où la demande associée à chaque destination est égale à 1. Il existe une méthode, “la méthode hongroise” qui simplifie la résolution du problème d’affectation. 468 1 2 3 2 1 i j Les problèmes d’affectation 3 (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) cij Min ∑ ∑ cijxij ∑ xij = 1 i = 1, … , n ∑ xij = 1 j = 1, … , n xij ≥ 0 469 USINE V.P. 1 2 3 4 F 24 10 21 11 M 14 22 10 15 O 15 17 20 19 P 11 19 14 13 Matrice des coûts Ex. Le coût d’affecter le V.P. «P» à l’usine 4 est de 13. La méthode hongroise 470 USINE V.P. 1 2 3 4 RÉDUIT DE: F 14 0 11 1 10 M 4 12 0 5 10 O 0 2 5 4 15 P 0 8 3 2 11 Étape 1: 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: 24-10=14, 10-10=0, 21-10=11, 11-10=1 La méthode hongroise 471 USINE V.P. 1 2 3 4 F 14 0 11 0 M 4 12 0 4 O 0 2 5 3 P 0 8 3 1 RÉDUIT DE: 0 0 0 1 Étape 2: 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. La méthode hongroise 472 Étape 3: 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 5. Si ce nombre est inférieur au nombre de lignes (ou colonnes), aller à l’étape 4. La méthode hongroise 473 USINE V.P. 1 2 3 4 F 14 0 11 0 M 4 12 0 4 O 0 2 5 3 P 0 8 3 1 Dans ce cas, le nombre minimal de lignes est de 3. Donc, on va à l’étape 4. La méthode hongroise 474 Étape 4: Trouver la cellule de valeur minimum non-couverte par une ligne. Soustraire cette valeur de toutes les cellules non- couvertes. Ajouter cette valeur aux cellules situées à l’intersection de deux lignes. Retourner à l’étape 3. La méthode hongroise 475 USINE V.P. 1 2 3 4 F 14 0 11 0 M 4 12 0 4 O 0 2 5 3 P 0 8 3 1 Valeur minimum La méthode hongroise 476 USINE V.P. 1 2 3 4 F 15 0 12 0 M 4 11 0 3 O 0 1 5 2 P 0 7 3 0 + 1 - 1 La méthode hongroise 477 USINE V.P. 1 2 3 4 F 15 0 12 0 M 4 11 0 3 O 0 1 5 2 P 0 7 3 0 Maintenant, le nombre minimal de lignes est de 4. Donc, on passe à l’étape 5. La méthode hongroise 478 USINE V.P. 1 2 3 4 F 15 0 12 0 M 4 11 0 3 O 0 1 5 2 P 0 7 3 0 Étape 5: Déterminer la solution optimale. Note: P1 ne pourrait pas être choisi car l’affectation de «O» ne serait pas de coût minimal. La méthode hongroise 479 AFFECTATION V.P. USINE COÛT F 2 10 M 3 10 O 1 15 P 4 13 COÛT TOTAL 48 Résultat: La méthode hongroise 480 Algorithme hongrois : Exemple C1 C2 C3 C4 P1 P2 P3 P4 60 200 400 330 360 250 90 170 50 170 300 120 180 200 130 200 481 C1 C2 C3 C4 P1 P2 P3 P4 60 200 400 330 360 250 90 170 50 170 300 120 180 200 130 200 Étape 1 : Réduction des lignes ∆=60 ∆=130 ∆=50 ∆=90 Algorithme hongrois : Exemple 482 C1 C2 C3 C4 P1 P2 P3 P4 0 110 270 270 300 160 0 110 0 120 250 30 130 70 0 70 Étape 1 : Réduction des lignes Algorithme hongrois : Exemple 483 C1 C2 C3 C4 P1 P2 P3 P4 0 110 270 270 300 160 0 110 0 120 250 30 130 70 0 70 Étape 2 : Réduction des colonnes ∆=0 ∆=0 ∆=70 ∆=110 Algorithme hongrois : Exemple 484 C1 C2 C3 C4 P1 P2 P3 P4 0 0 160 220 190 90 0 110 0 50 250 30 20 70 0 0 Étape 2 : Réduction des colonnes Algorithme hongrois : Exemple 485 C1 C2 C3 C4 P1 P2 P3 P4 0 0 160 220 190 90 0 110 0 50 250 30 20 70 0 0 Étape 3 : Matrice Réduite 3 lignes et il en faut 4 ⇒ Étape 4 Algorithme hongrois : Exemple 486 C1 C2 C3 C4 P1 P2 P3 P4 0 0 160 220 190 90 0 110 0 50 250 30 20 70 0 0 C1 C3 C4 C2 P1 P3 P4 P2 Algorithme hongrois : Exemple Étape 3 : Matrice Réduite 487 C1 C2 C3 C4 P1 P2 P3 P4 0 0 160 220 190 90 0 110 0 50 250 30 20 70 0 0 Étape 4 : Nouvelle réduction Réduction Algorithme hongrois : Exemple 488 C1 C2 C3 C4 P1 P2 P3 P4 0 0 160 220 190 90 0 110 0 50 250 30 20 70 0 0 Étape 4 : Nouvelle réduction Réduction Réduction de 20 unités des nombres en vert Ajout de 20 unités sur les nombres en orange Algorithme hongrois : Exemple 489 C1 C2 C3 C4 P1 P2 P3 P4 0 0 160 200 170 90 0 90 0 30 230 50 0 70 20 0 Étape 3 : matrice réduite ? Algorithme hongrois : Exemple 490 C1 C2 C3 C4 P1 P2 P3 P4 0 0 160 200 170 90 0 90 0 30 230 50 0 70 20 0 Étape 3 : matrice réduite ? 4 lignes ⇓ Solution optimale ⇓ Étape 5 Algorithme hongrois : Exemple 491 C1 C2 C3 C4 P1 P2 P3 P4 0 0 160 200 170 90 0 90 0 30 230 50 0 70 20 0 Étape 3 : matrice réduite ? C1 C3 C4 C2 P1 P3 P4 P2 Algorithme hongrois : Exemple 492 C1 C2 C3 C4 P1 P2 P3 P4 0 0 160 200 170 90 0 90 0 30 230 50 0 70 20 0 Étape 3 : matrice réduite ? C1 C3 C4 C2 P1 P3 P4 P2 Algorithme hongrois : Exemple 493 C1 C2 C3 C4 P1 P2 P3 P4 0 160 200 170 90 90 0 30 230 50 70 20 0 Étape 5 : solution optimale 0 0 0 Algorithme hongrois : Exemple 494 C1 C2 C3 C4 P1 P2 P3 P4 0 160 200 170 90 90 0 30 230 50 70 20 0 Étape 5 : solution optimale 0 0 0 C1 C2 C3 C4 P1 P2 P3 P4 60 200 400 330 360 250 90 170 50 170 300 120 180 200 130 200 Solution = 530 Algorithme hongrois : Exemple 495 Algorithme hongrois : Problème de maximisation 496 Algorithme hongrois : Problème de maximisation C1 C2 C3 C4 P1 P2 P3 P4 60 200 400 330 360 250 90 170 50 170 300 120 180 200 130 200 On doit ajouter une étape initiale : Choisir le plus grand nombre et trouver l’écart de tous les éléments par rapport à ce nombre; i.e. on trouve la matrice des pénalités. Le problème initial est alors équivalent au problème de minimiser les pénalités. Max C1 C2 C3 C4 P1 P2 P3 P4 340 200 0 70 40 150 310 230 350 230 100 280 220 200 270 200 Min 497 Algorithme hongrois Explication théorique 498 Algorithme hongrois : explication théorique Min ∑ ∑ cijxij ∑ xij = 1 i = 1, … , n ∑ xij = 1 j = 1, … , n xij ≥ 0 Max ∑ ui + ∑ vj ui + vj ≤ cij i = 1, … , n et j = 1, … , n 499 C1 C2 C3 C4 P1 P2 P3 P4 60 200 400 330 360 250 90 170 50 170 300 120 180 200 130 200 ui + vj + eij = cij 0 + 0 + eij = 300 Algorithme hongrois : explication théorique 500 C1 C2 C3 C4 P1 P2 P3 P4 60 200 400 330 360 250 90 170 50 170 300 120 180 200 130 200 Étape 1 : Réduction des lignes ∆=60 ⇒ u1 = minj c1j = 60 ∆=130 ⇒ u2 = minj uploads/Industriel/ methode-hongroise.pdf