5/13/2018 Exercice sur la programmation linéaire Plaques à découper - slidepdf.com

http://slidepdf.com/reader/full/exercice-sur-la-programmation-lineaire-plaques-a-decouper 1/3

 

Youssef  1

Exercice sur la programmation linéaireExercice :

Une usine à reçu des plaques de métal d’une largeur de 200cm et

d’une longueur de 500cm.

Il faut en fabriquer au moins 30 plaques de largeur de 110cm, 40

plaques de largeur 75cm et 15 plaques de largeur 60cm.

Donner le modèle mathématique pour que les déchets soient le pluspetits possible.

Solution

 

Plaques

110cm 75cm 60cm

110cm 75cm 60cm 110cm 75cm 60cm 110cm 75cm 60cm

15cm

déchets 

30cmdéchets 

15cmdéchets 

50cmdéchets 

60cm 30cmdéchets 

60cm 60cm

5cmdéchets 

5cmdéchets 

20cmdéchets 

5/13/2018 Exercice sur la programmation linéaire Plaques à découper - slidepdf.com

http://slidepdf.com/reader/full/exercice-sur-la-programmation-lineaire-plaques-a-decouper 2/3

 

Youssef  2

Ainsi il y a 5 façons pour fabriquer les plaques :

1er

: 1 plaque 110cm et 1 plaque 75cm avec 15cm de déchets.

2ème

: 1 plaque 110cm et 1 plaque 60cm avec 30cm de déchets.

3ème

: 2 plaques 75cm avec 50cm de déchets.

4ème

: 1 plaque 75cm et 2 plaques 60cm avec 5cm de déchets.

5ème

: 3 plaques 60cm avec 20cm de déchets.

Définition des variables :

X1 : nombre de plaques à découper avec la 1ère

façon.

X2 : nombre de plaques à découper avec la 2ème

façon.

X3 : nombre de plaques à découper avec la 3ème

façon.

X4 : nombre de plaques à découper avec la 4ème

façon.X5 : nombre de plaques à découper avec la 5

èmefaçon.

Programme primal

Min {D = 15x1 +30x2 +50x3 +5x4 +20x5}

x1+ x2  ≥30

S C x1 + 2x3 +x4  ≥40

x3 + 2x4 +3x5  ≥15

x1 ,x2 ,x3 ,x4 ,x5  ≥0

Programme dual

Max {Z = 30a +40b +15c}

a + b ≤ 15

a ≤ 30

S C 2b + c ≤ 50

b + 2c ≤ 5

3c ≤ 20

a, b, c ≥ 0

5/13/2018 Exercice sur la programmation linéaire Plaques à découper - slidepdf.com

http://slidepdf.com/reader/full/exercice-sur-la-programmation-lineaire-plaques-a-decouper 3/3

 

Youssef  3

Tableau 1

a b c * * * * * B

e1 1 1 0 1 0 0 0 0 15

e2 1 0 0 0 1 0 0 0 30

e3 0 2 1 0 0 1 0 0 50

e4  0 1 2 0 0 0 1 0 5

e5  0 0 3 0 0 0 0 1 20

Z 30 40 15 0 0 0 0 0 0

b entre ; R= B/b ⇒ 5 est le plus petit donc e4 sort 

Tableau 2

a * c * * * e4 * B

L1-L4e1 1 0 -2 1 0 0 -1 0 10

L2e2 1 0 0 0 1 0 0 0 30

L3-

2L4 e3 0 0 -3 0 0 1 -2 0 40

L4b  0 1 2 0 0 0 1 0 5

L5e5  0 0 3 0 0 0 0 1 20

L6-

40L4 Z 30 0 -65 0 0 0 -40 0 -200

a entre ; R= B/a ⇒ 10 est le plus petit donc e1 sort

Tableau 3

* * c e1 * * e4 * B

L1a 1 0 -2 1 0 0 -1 0 10

L2-L1e2 0 20

L3

e3 0 40L4

b  0 5

L5e5  0 20

L6-

30L1 Z 0 0 -5 -30 0 0 -10 0 -500

Ainsi : Z*

= D*

= 500 ; x1*

= 30 ; x2*

= x3*

= 0 ; x4*

= 10 ; x5*

= 0