Methode Hongroise .pdf



Nom original: Methode Hongroise.pdfTitre: heure_22Auteur: nafore

Ce document au format PDF 1.2 a été généré par Microsoft PowerPoint / Acrobat PDFWriter 4.0 pour Windows, et a été envoyé sur fichier-pdf.fr le 04/05/2015 à 14:36, depuis l'adresse IP 197.200.x.x. La présente page de téléchargement du fichier a été vue 2724 fois.
Taille du document: 49 Ko (8 pages).
Confidentialité: fichier public


Aperçu du document


Heure 22 :

Les problèmes d’affectation

Problème d’affectation et algorithme
hongrois

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.

N.O.P. Section 7.3.3
Notes complémentaires
Objectifs :
o
o

Reconnaître un problème d’affectation ;
Comprendre et appliquer l’algorithme hongrois.

Il existe une méthode, “la méthode
hongroise” qui simplifie la résolution du
problème d’affectation.

466

Les problèmes d’affectation
(1,1)
i

(1,1)
(1,1)

La méthode hongroise

cij

1

1

2

2

3

467

3

(1,1)

Matrice des coûts

(1,1)

USINE

j

(1,1)

Min ∑ ∑ cijxij

V.P.

1

2

3

4

F

24

10

21

11

M

14

22

10

15

∑ x ij = 1

i = 1, … , n

O

15

17

20

19

∑ x ij = 1

j = 1, … , n

P

11

19

14

13

Ex. Le coût
d’affecter le
V.P. «P» à
l’usine 4 est
de 13.

xij ≥ 0
468

469

La méthode hongroise

La méthode hongroise

É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.

É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.

Ex. La première ligne devient: 24-10=14, 10-10=0, 21-10=11, 11-10=1

USINE

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

470

V.P.

1

2

3

4

F
M
O

14
4
0

0
12
2

11
0
5

0
4
3

P

0
0

8
0

3
0

1
1

RÉDUIT
DE:

471

La méthode hongroise

La méthode hongroise
Dans ce cas, le nombre minimal de lignes est de 3.

É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.

USINE
V.P.

1

2

3

4

F

14

0

11

0

M

4

12

0

4

O
P

0
0

2
8

5
3

3
1

Donc, on
va à
l’étape 4.

472

La méthode hongroise

473

La méthode hongroise

Étape 4:
Trouver la cellule de valeur minimum non-couverte par
une ligne.

USINE
V.P.

1

2

3

4

Soustraire cette valeur de toutes les cellules noncouvertes.

F

14

0

11

0

M

4

12

0

4

Ajouter cette valeur aux cellules situées à l’intersection
de deux lignes.

O
P

0
0

2
8

5
3

3
1

Retourner à l’étape 3.

474

La méthode hongroise

475

La méthode hongroise
Maintenant, le nombre minimal de lignes est de 4.

+1

-1

Valeur
minimum

USINE
USINE

V.P.

1

2

3

4

F

15

0

12

0

V.P.

1

2

3

4

M

4

11

0

3

F

15

0

12

0

O
P

0
0

1
7

5
3

2
0

M

4

11

0

3

O
P

0
0

1
7

5
3

2
0

476

Donc, on
passe à
l’étape 5.

477

La méthode hongroise

La méthode hongroise

Étape 5:
Déterminer la solution optimale.

Résultat:
AFFECTATION
V.P.
USINE

USINE
Note: P1 ne
pourrait pas
être choisi car
l’affectation de
«O» ne serait
pas de coût
minimal.

V.P.

1

2

3

4

F

15

0

12

0

M

4

11

0

3

O
P

0
0

1
7

5
3

2
0

F
M
O
P

2
3
1
4

10
10
15
13

COÛT TOTAL
478

Algorithme hongrois : Exemple

COÛT

48
479

Algorithme hongrois : Exemple
Étape 1 : Réduction des lignes

C1

C2

C3

C4

C1

C2

C3

P1

60

170

330 360

P2

130

200

200

P3

50

300

170

P4

120

90

C4

P1

60

170

330 360

∆=60

400

P2

130

200

200

400

∆=130

180

P3

50

300

170

180

∆=50

250 200

P4

120

90

250 200

∆=90

480

Algorithme hongrois : Exemple

481

Algorithme hongrois : Exemple

Étape 1 : Réduction des lignes

Étape 2 : Réduction des colonnes

C1

C2

C3

C4

C1

C2

C3

C4

P1

0

110

270

300

P1

0

110

270

300

P2

0

70

70

270

P2

0

70

70

270

P3

0

250

120 130

P3

0

250

120 130

P4

30

0

110

P4

30

0

160

160

110

∆=0 ∆=0 ∆=70 ∆=110

482

483

Algorithme hongrois : Exemple

Algorithme hongrois : Exemple

Étape 2 : Réduction des colonnes

Étape 3 : Matrice Réduite

C1

C2

C3

C4

C1

C2

C3

C4

P1

0

110

220

190

P1

0

110

220

190

P2

0

70

0

160

P2

0

70

0

160

P3

0

250

50

20

P3

0

250

50

20

P4

30

0

90

0

P4

30

0

90

0

3 lignes et il en faut 4


Étape 4

484

Algorithme hongrois : Exemple

485

Algorithme hongrois : Exemple
Étape 4 : Nouvelle réduction

Étape 3 : Matrice Réduite
C1

C2

C3

C4

C1

C2

C3

C4

P1

0

110

220

190

C1

P1

P2

0

70

0

160

C2

P2

P1

0

110

220

190

P2

0

70

0

P3

0

250

50

20

160

P3

P3

0

250

50

C3

20

P4

30

0

90

0

C4

P4

P4

30

0

90

0
Réduction

486

487

Algorithme hongrois : Exemple

Algorithme hongrois : Exemple

Étape 4 : Nouvelle réduction

Étape 3 : matrice réduite ?

C1

C2

C3

C4

P1

0

110

220

190

P2

0

70

0

160

P3

0

250

50

20

P4

30

0

90

0

Réduction de 20 unités
des nombres en vert
Ajout de 20 unités sur les
nombres en orange

C1

C2

C3

C4

P1

0

90

200

170

P2

20

70

0

160

P3

0

230

30

0

P4

50

0

90

0

Réduction

488

489

Algorithme hongrois : Exemple

Algorithme hongrois : Exemple

Étape 3 : matrice réduite ?

Étape 3 : matrice réduite ?

C1

C2

C3

C4

0

90

200

170

C1

C2

C3

C4

0

90

200

170

4 lignes
P1
P2

20

70

0

160

P3

0

230

30

0

P4

50

0

90



P1

Solution optimale

P2

20

70

0

160



P3

0

230

30

0

Étape 5

0

P4

50

0

90

0

C1

P1

C2

P2

C3

P3

C4

P4

490

491

Algorithme hongrois : Exemple

Algorithme hongrois : Exemple

Étape 3 : matrice réduite ?

Étape 5 : solution optimale

C1

C2

C3

C4

C2

C3

C4

P1

0

90

200

170

P2

20

70

0

160

P1

0

90

200

170

P2

20

70

0

160

C2

P2

P3

0

230

30

0

C3

P3

P3

0

230

30

0

0

C4

P4

P4

50

0

90

0

P4

50

0

90

P1

C1
C1

492

493

Algorithme hongrois : Exemple
Étape 5 : solution optimale

Algorithme hongrois :
C1

C2

C3

C4

P1

0

90

200

170

P2

20

70

0

P3

0

230

P4

50

0

C1

C2

C3

C4

P1

60

170

330 360

160

P2

130

200

200

400

30

0

P3

50

300

170

180

90

0

P4

120

90

250 200

Problème de maximisation

Solution = 530
494

495

Algorithme hongrois : Problème de maximisation
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

60

170

330 360

P2

130

200

200

P3

50

300

170

P4

120

90

Min

C1

C2

C3

C4

P1

340

230

70

40

400

P2

270

200

200

0

180

P3

350

100

230 220

250 200

P4

280

310

150 200

Algorithme hongrois
Explication théorique

496

Algorithme hongrois : explication théorique

497

Algorithme hongrois : explication théorique

Min ∑ ∑ cijxij
∑ x ij = 1

i = 1, … , n

∑ x ij = 1

j = 1, … , n

C1

C2

C3

P1

60

170

330 360

ui + v j + e ij = cij

P2

130

200

200

400

0 + 0 + eij = 300

Max ∑ ui + ∑ v j

P3

50

300

170

180

ui + vj ≤ c ij i = 1, … , n et
j = 1, … , n

P4

120

90

250 200

xij ≥ 0

C4

498

Algorithme hongrois : explication théorique

Algorithme hongrois : explication théorique

Étape 1 : Réduction des lignes

P1
P2

C1

C2

C3

60

170

330 360

130 200
50

300 170

P4

120

90

Étape 1 : Réduction des lignes

C4

200 400

P3

499

180

250 200

∆=60 ⇒
∆=130 ⇒
∆=50

C1

C2

C3

C4

u1 = 60

P1

0

110

270

300

ui + v j + e ij = cij

u2 = 130

P2

0

70

70

270

u2 + v3 + e23 = c23

u3 = 50

P3

0

250

120 130

u4 = 90

P4

30

0

u1 = minj c1j = 60
u2 = minj c 2j = 130



u3 = minj c 3j = 50

∆=90 ⇒

u4 = minj c4j = 90

500

160

130 + 0 + 70 = 200

110

501

Algorithme hongrois : explication théorique

Algorithme hongrois : explication théorique

Étape 2 : Réduction des colonnes

Étape 2 : Réduction des colonnes
v1 =0 v2 =0 v3 =70 v4 =110

C1

C2

C3

C1

C2

C3

C4

u1 = 60

P1

0

110

270 300

C4
∆ =0 ⇒ v1 = mini ( ci1 - ui )= 0

u 1 = 60

P1

0

110

220

190

ui + v j + e ij = cij

u2 = 130

P2

0

70

70

∆ =0 ⇒ v2 = mini ( ci2 - ui )= 0

u 2 = 130

P2

0

70

0

160

u3 + v3 + e33 = c33

u3 = 50

P3

0

250

120 130

∆ =70 ⇒ v 3 = mini ( ci3 - u i )= 70

u 3 = 50

P3

0

250

50

20

50 + 70 + 50 = 170

u4 = 90

P4

30

0

160 110

∆ =110 ⇒ v4 = mini (c i4 - u i ) = 110

u 4 = 90

P4

30

0

90

0

270

∆=0 ∆=0 ∆=70 ∆=110
502

Algorithme hongrois : explication théorique

503

Algorithme hongrois : explication théorique

Étape 3 : Matrice Réduite

Étape 4 : Nouvelle réduction

v1 =0 v2 =0 v3 =70 v4 =110

u 1 = 60

P1

C1

C2

C3

C4

0

110

220

190

u 2 = 130

P2

0

70

0

160

u 3 = 50

P3

0

250

50

20

u 4 = 90

P4

30

0

90

0

v1 =0 v2 =0 v3 =70 v4 =110

3 lignes et il en faut 4



solution du duale n’est pas
optimale car la solution
primale n’est pas réalisable

C1

C2

C3

C4

u 1 = 60

P1

0

110

220

190

u 2 = 130

P2

0

70

0

160

u 3 = 50

P3

0

250

50

20

u 4 = 90

P4

30

0

90

0

Pour maximiser il faut réduire
la valeur des e i j et pour avoir
une solution admissible il faut
prendre le plus petit

504

Algorithme hongrois : explication théorique
Étape 4 : Nouvelle réduction
v1 =0 v2 =0 v3 =70 v4 =110

C1

C2

C3

C4

u 1 = 60

P1

0

110

220

190

u 2 = 130

P2

0

70

0

160

u 3 = 50

P3

0

250

50

20

u 4 = 90

P4

30

0

90

0

505

Algorithme hongrois : explication théorique
Étape 4 : Nouvelle réduction

Réduction de ∆=20 unités des
nombres en rouge



e ij ← ei j - ∆

v1 =0 v2 =0 v3 =70 v4 =110

C1

C2

u 1 = 60

P1

0

90

u 2 = 130

P2

0

P3

0

P4

30

0

90

u 3 = 50
u 4 = 90

506

C3

C4

200

170

70

0

160

230

30

0
0

Réduction de ∆=20 unités des
nombres en rouge



e ij ← ei j - ∆

Pour conserver la relation

ui + v j + e ij = cij
il faut alors



u1 ← u1 + ∆
u3 ← u3 + ∆
507

Algorithme hongrois : explication théorique

Algorithme hongrois : explication théorique
Étape 4 : Nouvelle réduction

Étape 4 : Nouvelle réduction

v1 =0 v2 =0 v3 =70 v4 =110

C1

C2

C3

C4

u 1 = 60+20 P1

0

90

200

170

P2

0

70

0

160

u 2 = 130

u 3 = 50+20 P3

0

230

30

P4

30

0

90

u 4 = 90

v1 =0-20 v2 =0 v3 =70 v4 =110

Ainsi pour tous les ei j alors
on conserve la relation

ui + v j + e ij = cij

C2

C3

C4

0

90

200

170

P2

0

70

0

160

u 3 = 50+20 P3

0

230

30

0

P4

30

0

90

u 2 = 130

mais pas pour

0

C1
u 1 = 60+20 P1

e 11 et e 31

0

u 4 = 90

0

Pour équilibrer les cases
(P1,C1) et (P3,C1), il faut
v 1 ← v1 - ∆



Pour e11 et e31 on conserve
alors la relation

ui + v j + e ij = cij
mais plus pour e 21 et e 41 c’est
pourquoi il faut faire
e 21 ← e 21 + ∆
e 41 ← e 41 + ∆

508

Algorithme hongrois : explication théorique

Algorithme hongrois : explication théorique

Étape 3 : matrice réduite ?

C1

C2

C3

509

Étape 5 : solution optimale

C4

C1

C2

C3

C4

4 lignes
P1

0

90

200

170



P1

0

90

200

170

P2

20

70

0

160

Solution optimale

P2

20

70

0

160

P3

0

230

30

0



P3

0

230

30

0

P4

50

0

90

0

P4

50

0

90

0

Étape 5

510

Travail à faire : heure 22
N.O.P. chapitre 7 Nos 22, 23, 24
(chapitre 7 Nos 20, 21, 22)

512

511


Aperçu du document Methode Hongroise.pdf - page 1/8
 
Methode Hongroise.pdf - page 3/8
Methode Hongroise.pdf - page 4/8
Methode Hongroise.pdf - page 5/8
Methode Hongroise.pdf - page 6/8
 




Télécharger le fichier (PDF)


Methode Hongroise.pdf (PDF, 49 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


methode hongroise
methodes quasi newton
17rewnpls
article ml
sujet maths ii  ccp 2019 1
professeur benzine rachid cours optimisation sans contraintes tome1