Chapitre 5 : Programmation linéaire, bases - ENSIIE ... · Examples Graphical method Graphical simplex algorithm Miseenéquation Maximiser y s.c. 20x 50y 150 (1) 2x + 3y 18 (2) 2x

ExamplesGraphical method

Graphical simplex algorithm

Chapitre 5 : Programmation linéaire, basesENSIIE - Module de Recherche Opérationnelle

Dimitri Watel ([email protected])

2016-2017

Dimitri Watel MRO Chap 05 PL Bases



Un exemple à l’école des sorciers

Hermione doit rater des cours pour sauver le monde. Plus elle enrate, plus ses chances d’aider Harry sont élevées. Mais :

Elle dort au moins 6h par jour.Un cours ou une séance de révision dure 2h. Rater un cours luiprend 3h de sa journée.Elle gagne 20 points pour Gryffondor quand elle révise ouassiste à un cours, mais en perd 50 si elle rate un cours. Ellene souhaite pas faire perdre plus de 150 points par jour à samaison.Pour éviter se faire renvoyer, elle ne peut rater plus de 5 courspar jour, et doit passer au moins 8h à réviser.

Combien de cours peut-elle rater ?




Mise en équation

Maximiser ys.c. 20x − 50y ≥ −150 (1)

2x + 3y ≤ 18 (2)2x ≥ 8 (3)y ≤ 5 (4)

x , y ∈ N




Mise en équation

Maximiser ys.c. 20x − 50y ≥ −150 (1)

2x + 3y ≤ 18 (2)2x ≥ 8 (3)y ≤ 5 (4)

x , y ∈ NComment le résoudre ?




Comment le résoudre ?

x ≥ 4 (3)

2x + 3y ≤ 18 (2)⇒ 2 · 4 + 3y ≤ 18⇒ y ≤ 3.333⇒ y ≤ 3

Testons y = 3. Alors

2x + 3y ≤ 18 (2)⇒ x ≤ 9/2⇒ x ≤ 4

Or

x ≥ 4⇒ x = 4

x = 4 et y = 3 respectent toutes les contraintes. Inutile de chercherpour y plus petit car on veut maximiser y , on a une solution

optimale.Dimitri Watel MRO Chap 05 PL Bases



Et si Hermione pouvait...

... couper un cours en morceaux, ou faire des fautes peu graves ?Maximiser y

s.c. 20x − 50y ≥ −150 (1)2x + 3y ≤ 18 (2)

2x ≥ 8 (3)y ≤ 5 (4)

x , y ∈ R+




Comment le résoudre ?

x ≥ 4 (3)

2x + 3y ≤ 18 (2)⇒ 2 · 4 + 3y ≤ 18⇒ y ≤ 10/3

Testons y = 10/3. Alors

2x + 3y ≤ 18 (2)⇒ x ≤ 4

Or

x ≥ 4⇒ x = 4

x = 4 et y = 10/3 respectent toutes les contraintes. Inutile dechercher pour y plus petit car on veut maximiser y , on a une

solution optimale.Dimitri Watel MRO Chap 05 PL Bases



Ce n’est pas toujours aussi simple !

Maximiser −x + 2ys.c. −x + y ≤ 1 (1)

x + y ≤ 3 (2)x , y ∈ N




Ce n’est pas toujours aussi simple !

x ≥ 0, y ≥ 0

x + y ≤ 3 (2)⇒ x ≤ 3, y ≤ 3

Testons y = 3. Alors

x + y ≤ 3 (2)⇒ x ≤ 0

Or

x ≥ 0⇒ x = 0

Donc

−x + y = 3

Contradiction car −x + y ≤ 1(1)Puisqu’on veut maximiser −x + 2y , il n’est pas évident de savoir où

chercher : grand y ? petit x ? intérmédiaires ?Dimitri Watel MRO Chap 05 PL Bases



Exemples de programmes linéaires

Maximiser ys.c. 20x − 50y ≥ −150 (1)

2x + 3y ≤ 18 (2)2x ≥ 8 (3)y ≤ 5 (4)

x , y ∈ R





Maximiser ys.c. 20x − 50y ≥ −150 (1)

2x + 3y ≤ 18 (2)2x ≥ 8 (3)y ≤ 5 (4)

x , y ∈ N





Maximiser ys.c. 20x − 50y ≥ −150 (1)

2x + 3y ≤ 18 (2)2x ≥ 8 (3)y ≤ 5 (4)x ∈ Qy ∈ R





Minimiser 2x − 3ys.c. 20x − 50y ≥ −150 (1)

2x + 3y ≤ 18 (2)2x ≥ 8 (3)y ≤ 5 (4)x ∈ Qy ∈ R





Minimiser 2x − 3yx ∈ Qy ∈ R





Minimiser 2x − 3y + zs.c. x − z ≥ 1 (1)

2x + 3y + z ≤ 10 (2)x , z ∈ Qy ∈ R





Minimiser −2x + 38zs.c. x = 1 + z (1)

2x + z = 10− 3y (2)x ∈ N

y , z ∈ D





Minimiser −2.3x + 0.3y + 38.7zs.c. πx − φz ≤ 1 (1)√

2x + exp(3)y + ln(12)z ≥ 1 (2)x ∈ N

y , z ∈ D





Minimiser xs.c. x ≤ 1 (1)

x ≥ 2 (2)x ∈ R




Exemples de non programmes linéaires

Minimiser exp(x)s.c. x + y ≤ 1 (1)

x − y ≥ 2 (2)x , y ∈ R





Minimiser xs.c. x + sin(y) ≤ 1 (1)

cos(x)− y ≥ 2 (2)x , y ∈ R





s.c. x + y ≤ 1 (1)x − y ≥ 2 (2)x , y ∈ R





Minimiser xs.c. x + y ≤ 1 (1)

x − y ≥ 2 (2)x + y ∈ N




Généralisation

DéfinitionUn programme linéaire se définit par :

ses variables numériques et leurs ensembles de définitionsa fonction objective à optimiserses contraintes

Minimiser c1 · x1 + c2 · x2 + · · ·+ cn · xns.c. a11 · x1 + a12 · x2 + · · ·+ a1n · xn ≤ b1

a21 · x1 + a22 · x2 + · · ·+ a2n · xn ≥ b2...

am1 · x1 + am2 · x2 + · · ·+ amn · xn = bmx1, x2, . . . , xn ∈ R,N, [1, 34], . . .




Généralisation




a21 · x1 + a22 · x2 + · · ·+ a2n · xn ≥ b2...





Généralisation




a21 · x1 + a22 · x2 + · · ·+ a2n · xn ≥ b2...





Généralisation




a21 · x1 + a22 · x2 + · · ·+ a2n · xn ≥ b2...





Écriture matricielle

Soient

c =(c1, c2, . . . , cn

)x =

(x1, x2, . . . , xn

)b =

(b1, b2, . . . , bm

) A =

a11, a12, . . . , a1na21, a22, . . . , a2n

...am1, am2, . . . , amn




Écriture matricielle


a21 · x1 + a22 · x2 + · · ·+ a2n · xn ≤ b2...

am1 · x1 + am2 · x2 + · · ·+ amn · xn ≤ bmx1, x2, . . . , xn ∈ R

est équivalent à

Minimiser c · txs.c. A · tx ≤ b

x ∈ Rn




Méthode de résolution graphique

Résolution graphiqueDans le cas d’un programme linéaire avec 2 variables, il estpossible de résoudre le problème graphiquement.

Remarque : on peut avec 3 variables, mais il faut être doué pourdessiner en 3D.Remarque : il n’est pas envisageable qu’un ordinateur utilise cetteméthode pour résoudre un tel problème ! ! ! C’est une méthode pourles humains, pour dessiner des exemples et bien comprendre laprogrammation linéaire.




Exemple

Maximiser ys.c. 20x − 50y ≥ −150 (1)

2x + 3y ≤ 18 (2)2x ≥ 8 (3)y ≤ 5 (4)

x , y ∈ R+




Exemple : tracer les axes

0 x

y

10

7




Exemple : tracer les ensembles de définition

0 x

y

10

7




Exemple : tracer les contraintes

0 x

y

10

720x − 50y = −150

2x + 3y = 18

y = 5

2x = 8




Exemple : tracer l’ensemble réalisable

0 x

y

10

720x − 50y ≥ −150

2x + 3y ≤ 18

y ≤ 5

2x ≥ 8




Exemple : tracer la fonction objectif

0 x

y

10

720x − 50y ≥ −150

2x + 3y ≤ 18

y ≤ 5

2x ≥ 8

y = 1





0 x

y

10

720x − 50y ≥ −150

2x + 3y ≤ 18

y ≤ 5

2x ≥ 8

y = 2





0 x

y

10

720x − 50y ≥ −150

2x + 3y ≤ 18

y ≤ 5

2x ≥ 8

y = 3




Exemple : déduire la solution optimale

0 x

y

10

720x − 50y ≥ −150

2x + 3y ≤ 18

y ≤ 5

2x ≥ 8

y = 3.333




Exemple : déduire la solution optimale

0 x

y

10

720x − 50y ≥ −150

2x + 3y ≤ 18

y ≤ 5

2x ≥ 8

y = 3.333

Optimal solution : (4,3.333)




Autre exemple : 2e exemple simple

Minimiser 2x + ys.c. x + y ≤ 1 (1)

x + y ≥ −1 (2)x − y ≤ 1 (3)x − y ≥ −1 (4)x , y ∈ R




Autre exemple : Si la fonction objective est parallèle à unecontrainte.

Minimiser x + ys.c. x + y ≤ 1 (1)

x + y ≥ −1 (2)x − y ≤ 1 (3)x − y ≥ −1 (4)x , y ∈ R




Autre exemple : Si l’ensemble des solutions réalisables estvide.

Maximiser ys.c. x + y ≥ 1 (1)

x + y ≤ −1 (2)x − y ≤ 1 (3)x − y ≥ −1 (4)x , y ∈ R




Autre exemple : Si l’ensemble des solutions réalisables n’estpas borné.

Maximiser yx + y ≥ −1 (2)x − y ≤ 1 (3)x − y ≥ −1 (4)x , y ∈ R




Autre exemple : Si une ou deux variables sont entières.

Maximiser 2x + ys.c. 2x + 2y ≤ 5 (1)

2x + 2y ≥ −5 (2)2x − 2y ≤ 5 (3)2x − 2y ≥ −5 (4)

x , y ∈ N




L’algorithme du simplexe

DéfinitionL’algorithme du simplexe est un algorithme de résolution deprogramme linéaire par descente de gradient.

On va voir comment il fonctionne graphiquement. Le prochainchapitre vous expliquera comment l’implémenter.




Solution de base

0 x

y




Solution de base

0 x

y

Solution de base




Solution de base

0 x

y

Solution de base réalisables




Solution de base

0 x

y

Fonction objective : max 2x + y




Solution de base

0 x

y

Fonction objective : max 2x + y

0

3

8

11.33

9.75




Solution de base

0 x

y

0

3

8

11.33

9.75Solution optimale




Algorithme du simplexe : principe

0 x

y

1. Trouver une solution de base réa-lisable (n’importe laquelle, n’importecomment).

0





0 x

y

~∆(f )

2. Calculer la dérivée de l’objectifvers les voisins.





0 x

y

~∆(f )

2. Calculer la dérivée de l’objectifvers les voisins.

21





0 x

y

2

3. Conserver la meilleure solution.

4





0 x

y

~∆(f )

2-21

4. Recommencer.





0 x

y

1

7.33





0 x

y

-1.1

-1

5. Si les deux directions déteriorentla solution, elle est optimale.


Documents

Chapitre 5 : Programmation linéaire, bases - ENSIIE ... · Examples Graphical method Graphical simplex algorithm Miseenéquation Maximiser y s.c. 20x 50y 150 (1) 2x + 3y 18 (2) 2x