Chapitre 3: Optimisation Avec Contrainte

UCAD /ESP/DGI / IABD/M1

Dr. Mbaye Faye

3 juillet 2026

1/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 1 /

 Plan

1 Méthode Simplexe

2 Les étapes de l’algorithme du Simplexe

3 La méthode des 2 phases

2/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 2 /

 1 Méthode Simplexe

2 Les étapes de l’algorithme du Simplexe

3 La méthode des 2 phases

3/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 3 /

 1 Méthode Simplexe

2 Les étapes de l’algorithme du Simplexe

3 La méthode des 2 phases

4/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 4 /

 Principe
• Pour résoudre un problème d’optimisation avec contrainte par la méthode
simplexe,

• il faudrait d’abord se ramener à un PL sous forme canonique standard

• puis trouver une solution de base réalisable et enfin commencer à dérouler

l’algorithme.

5/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 5 /

 Variable d’écart
• Avant d’exécuter l’algorithme du simplexe, on doit nécessairement convertir le
PL donné en un programme standard où les contraintes sont des équations et les
variables sont positives.

• Pour une contrainte i de type «≤», on rajoute une variable d’écart notée ici
ei positive ou nulle.

• Exemple : l’inéquation x1 + 2x2 ≤ 3 est transformée en x1 + 2x2 + e1 = 3,

avec e1 ≥ 0.

• Quant à une contrainte i de type «≥», on retranche une variable d’écart

notée ici ei positive ou nulle.

• Exemple : l’inéquation 3x1 + x2 ≥ 3 est transformée en 3x1 + x2 − e1 = 3,

avec e1 ≥ 0.

6/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 6 /

 1 Méthode Simplexe

2 Les étapes de l’algorithme du Simplexe

3 La méthode des 2 phases

7/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 7 /

 Les étapes de l’algorithme du Simplexe
Les étapes à suivre pour résoudre un problème de PL par la méthode du Simplexe
sont les suivantes :
X Etape 1 :
Ecrire le système sous forme canonique standard ;

X Etape 2 :
Construire le premier tableau correspondant à la forme canonique standard ;

X Etape 3 :
Choisir la variable à introduire dans la base ;

X Etape 4 :
Choisir la variable à enlever de la base ;

8/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 8 /

 X Etape 5 :
Encadrer le pivot ;

X Etape 6 :
Diviser la ligne du pivot par le pivot ;

X Etape 7 :
Calculer les valeurs des autres lignes ;

X Etape 8 :
Les cœfficients de la fonction objectif sont-ils tous nuls ou négatif ;

Si oui fin de l’algorithme, Si non recommencer encore l’algorithme à

partir de l’étape 3

9/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 9 /

 Même exemple
max f (x1 , x2 ) = 600x1 + 400x2

 3x1 + 9x2 ≤ 81

 4x1 + 5x2 ≤ 55


2x1 + x2 ≤ 20
x1 ≥0




x2 ≥ 0


Mettre sous forme canonique standard en rajoutant les variables d’écart

Etape1 : forme canonique standard

max f (x1 , x2 ) = 6x1 + 4x2


 3x1 + 9x2 + e1 = 81
 1 + 5x2 + e2 = 55
4x


2x1 + x2 + e3 = 20
x1 ≥0




x2 ≥ 0


10/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 10

 Etape 2 : Premier tableau
• Après avoir trouvé une solution de base réalisable, on se ramène à une forme
canonique par rapport à cette base avant de commencer à dérouler l’algorithme
simplexe

• Comme les coûts réduits (CR) des variables hors base sont strictement
positifs, on n’est pas à l’optimum, car faire entrer x1 et x2 permet d’améliorer la
fonction objectif.

11/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 11

 Etape 3 : Variable entrante
• On choisira ici de faire rentrer la variable x1 qui a un effet plus important
(600) que x2

Etape 4 : Variable sortante

• Pour la variable sortante, pour conserver l’admissiblité, on l’a choisie de la
b
manière suivante : min{ ajij } où i0 correspond à la colonne de la variable entrante.
0

• Pour notre cas, on a min{ 81 55 20

3 ; 4 ; 2 } = 10. C’est donc la variable e3 qui
devrait sortir

12/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 12

 Etape 5 : Encadrer le pivot

Il est utile de noter que le pivot correspond à l’intersection de la variable entrante

et de la variable sortante.

13/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 13

 Etape 6 : diviser la ligne du pivot par le pivot

Il est utile de noter que le pivot correspond à l’intersection de la variable entrante

et de la variable sortante.

Cette nouvelle ligne est appelée ligne du pivot notée lp

Au niveau du tableau suivant, on a divisé la ligne du pivot par le pivot

14/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 14

 Etape 7 : Calculer les valeurs des autres lignes

Etape 8 :
• Les cœfficients de la fonction objectif ne sont pas tous nuls ou négatifs. Donc
on reprend l’itération à partir de l’étape 3.

• On n’est pas à l’optimum car x2 permet d’améliorer la fonction d’objectif

(variable entrante).

15/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 15

 En procédant de la même manière que précedemment, on voit que e2 est la
variable sortante car le minimum est ici égal à 5.

• On est à l’optimum car les coûts réduits des variables hors base sont négatifs.
La solution est donnée par e1 = 27 15
2 , x1 = 2 , x2 = 5, e2 = e3 = 0

16/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 16

 1 Méthode Simplexe

2 Les étapes de l’algorithme du Simplexe

3 La méthode des 2 phases

17/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 17

 La méthode des 2 phases

• Cette méthode est une variante de l’algorithme du simplexe qui se déroule en

deux phases, comme son nom l’indique.

• Il est donc nécessaire de comprendre la méthode simplexe.

• Concrètement, la méthode des deux phases comporte deux phases ;

18/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 18

 X Phase 1
La Phase 1 qui consiste à déterminer une solution de base réalisable ; en pratique,
il s’agit de minimiser la fonction objectif artificielle, notée fA

X Phase 2
La Phase 2 qui reprend l’objectif initial de maximiser la fonction f . En d’autres
termes, cette étape consiste à se déplacer, de façon itérative, de la solution de
base réalisable trouvée à la première étape à la solution optimale

19/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 19

 Principe
• Face à un problème d’optimisation, il est d’abord important de pouvoir
détecter le besoin de se servir de la méthode des deux phases.

• Après la reconnaissance de l’utilité de cette méthode, on peut donc passer à la

construction du tableau de la phase 1 ; ensuite on passe de la phase 1 à la phase 2.

• Essentiellement, cet algorithme en deux phases consiste à ajouter des

variables de base artificielles, notées ai , dans les équations où il n’y a aucune
variable candidate naturelle.

• Partant d’un programme linéaire dont le second membre b est positif, la

méthode des deux phases consiste à faire les transformations suivantes pour se
ramener à la forme standard

20/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 20

 X Pour les contraintes de type «≥», on retranche des variables d’écart et on
rajoute des variables artificielles.

X Pour les contraintes de type «=», on rajoute des variables artificielles

seulement.

X Pour les contraintes de type «≤», on rajoute des variables d’écart seulement.

21/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 21

 Exemple d’application
Soit le problème de maximisation suivante

max f (x1 , x2 , x3 ) = 2x1 + x2 + 3x3

sous les contraintes 


 −x1 + 2x2 + x3 ≤ 6
x3 ≥ 3


 x 1 − x 2 + 2x3 ≤ 12
x1 , x2 , x3 ≥ 0


22/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 22

 Résolution
En appliquant le principe de l’algorithme, on obtient le système suivant :



 −x1 + 2x2 + x3 + e1 = 6
x3 − e2 + a1 = 3


 x 1 − x 2 + 2x 3 + e3 = 12
x1 , x2 , x3 , e1 , e2 , e3 , a1 ≥ 0


23/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 23

 • Pour la phase 1, la fonction objectif à minimiser
Pk est la somme des variables
artificielles et qui est : est donnée par Min Z 0 = i=1 ai

• La solution de base réalisable est donnée par xB = (e1 , a1 , e3 ) correspondant

au tableau ci-dessous.

24/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 24

 • La variable entrante est la variable x3 car on résout un problème Min et que
son coût réduit est négatif (ici -1).

• Pour la variable sortante, on trouve que c’est la variable a1 (revoir la méthode

simplexe) car elle minimise les rapports abii3 i.e min{ 61 ; 31 ; 12
2 } = 3. Ce qui donne le
tableau suivant :

25/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 25

 • Etant donné que la fonction objectif est nulle et que la variable artificielle a1
est devenue une variable hors base ; on peut passer donc à la phase 2.

• Celle-ci donne les tableaux suivants, successivement.

26/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 26

 • Etant donné que l’on résout un programme Max dans la deuxième phase, la
variable entrante est e2 (son coût réduit est positif permettant donc d’accroitre la
valeur de la fonction objectif). La variable sortante peut être soit e1 , soit e3 car
donnant la même valeur minimale pour abii5 = 3.

• Ici, on choisit sans perte de généralité de faire sortir e1 . Ce qui donne le

tableau suivant

27/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 27

 • Ce tableau montre que c’est la variable x1 qui doit rentrer et e3 la variable à
sortir donnant le tableau suivant

28/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 28

 • Ce tableau montre que c’est la variable x2 qui doit rentrer à la place de e2 qui
doit sortir donnant le tableau suivant

• On est à l’optimum pour un problème Max car tous les coûts réduits sont
strictement négatifs montrant qu’il n’y a plus de possibilités de pouvoir accroître
la valeur de la fonction objectif.

• La solution est également unique. La valeur de la fonction objectif à

l’optimum est 48.

29/29 Dr. Mbaye Faye () Optimisation Continue 3 juillet 2026 29