3 Optimisation avec contraintes Max CERF

3.1 Simplexe
3.1.2 Déplacement
Techniques d’optimisation 2018

3.1.2 Exemple
Méthode des tableaux
• Problème linéaire à 3 variables x1, x2, x3

 x 1  2x 2  2x 3  20
2x  x 2  2x 3  20
min  10x 1  12x 2  12x 3 sous  1
2x  2x 2  x 3  20
 1
x1 , x 2 , x 3

x 1 , x 2 , x 3  0

• Forme standard

 Variables d’écart x4, x5, x6 positives

 x 1  2x 2  2x 3  x 4  20
2x  x 2  2x 3  x 5  20
min  10x 1  12x 2  12x 3 sous  1
2x  2x 2  x 3  x 6  20
 1
x1 , x 2 , x 3 , x 4 , x 5 , x 6

x 1 , x 2 , x 3 , x 4 , x 5 , x 6  0

479
3 Optimisation avec contraintes Max CERF
3.1 Simplexe
3.1.2 Déplacement
Techniques d’optimisation 2018

3.1.2 Exemple
Méthode des tableaux
• Tableau du simplexe

x1 x2 x3 x4 x5 x6
1 2 2 1 0 0 20 x4 Base initiale admissible
(x4 , x5 , x6)
2 1 2 0 1 0 20 x5
2 2 1 0 0 1 20 x6
-10 -12 -12 0 0 0 0 -z

• Solution de base non optimale : coûts réduits négatifs (= directions de descente)

• Variable entrante : 1er coût réduit négatif  x1

• Variable sortante : 1ère variable de base à s’annuler  x5

• Pivot : a 51  2

480
3 Optimisation avec contraintes Max CERF
3.1 Simplexe
3.1.2 Déplacement
Techniques d’optimisation 2018

3.1.2 Exemple
Méthode des tableaux
• 1er pivotage : entrée x1, sortie x5

x1 x2 x3 x4 x5 x6 Pas
1 2 2 1 0 0 20 x4  s14=20
2 1 2 0 1 0 20 x5  s15=10
2 2 1 0 0 1 20 x6  s16=10
-10 -12 -12 0 0 0 0 z

x1 x2 x3 x4 x5 x6
0 1.5 1 1 -0.5 0 10 x4 Nouvelle base
1 0.5 1 0 0.5 0 10 x1 (x1 , x4 , x6)

0 1 -1 0 -1 1 0 x6
0 -7 -2 0 5 0 100 z

481
3 Optimisation avec contraintes Max CERF
3.1 Simplexe
3.1.2 Déplacement
Techniques d’optimisation 2018

3.1.2 Exemple
Méthode des tableaux
• 2ème pivotage : entrée x2, sortie x6

x1 x2 x3 x4 x5 x6 Pas
0 1.5 1 1 -0.5 0 10 x4  s24=20/3
1 0.5 1 0 0.5 0 10 x1  s21=20
0 1 -1 0 -1 1 0 x6  s26=0
0 -7 -2 0 5 0 100 z

x1 x2 x3 x4 x5 x6
0 0 2.5 1 1 -1.5 10 x4 Nouvelle base
1 0 1.5 0 1 -0.5 10 x1 (x1 , x2 , x4)
0 1 -1 0 -1 1 0 x2
0 0 -9 0 -2 7 100 z

482
3 Optimisation avec contraintes Max CERF
3.1 Simplexe
3.1.2 Déplacement
Techniques d’optimisation 2018

3.1.2 Exemple
Méthode des tableaux
• 3ème pivotage : entrée x3, sortie x4
x1 x2 x3 x4 x5 x6 Pas
0 0 2.5 1 1 -1.5 10 x4  s34=4
1 0 1.5 0 1 -0.5 10 x1  s31=20/3
0 1 -1 0 -1 1 0 x2  s32=+
0 0 -9 0 -2 7 100 z

x1 x2 x3 x4 x5 x6
0 0 1 0.4 0.4 -0.6 4 x3 Nouvelle base
1 0 0 -0.6 0.4 0.4 4 x1 (x1 , x2 , x3)
0 1 0 0.4 -0.6 0.4 4 x2
0 0 0 3.6 1.6 1.6 136 z

x*  4 4 4 0 0 0T
• Solution optimale : c0 
z*  136
483