Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

Recherche opérationnelle & optimisation

Chapitre 4: Dualité - Analyse de sensibilité

Mohamed Essaied Hamrita

Janvier 2022

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 1 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

1 Introduction

2 Les règles de passage primal-dual

3 Théorèmes de la dualité

4 La méthode du dual simplexe

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 2 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

1 Introduction

2 Les règles de passage primal-dual

3 Théorèmes de la dualité

4 La méthode du dual simplexe

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 3 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

Chaque programme linéaire peut être considéré comme un problème

primal.
Il y a un autre programme linéaire associé avec le primal, uniquement
défini par celui-là. Ce programme linéaire est le problème dual.
Ces deux programmes sont toujours symétriques, dans les sens suivants:
• Il y a une contrainte duale pour chaque variable primale, et une
variable duale pour chaque contrainte primale.

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 4 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

Chaque programme linéaire peut être considéré comme un problème

primal.
Il y a un autre programme linéaire associé avec le primal, uniquement
défini par celui-là. Ce programme linéaire est le problème dual.
Ces deux programmes sont toujours symétriques, dans les sens suivants:
• Il y a une contrainte duale pour chaque variable primale, et une
variable duale pour chaque contrainte primale.
• Les coefficients objectives des variables primales deviennent les cotés
droits des contraintes duales, et les cotés droits des contraintes
primales deviennent les coefficients objectives des variables duales.

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 4 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

Chaque programme linéaire peut être considéré comme un problème

primal.
Il y a un autre programme linéaire associé avec le primal, uniquement
défini par celui-là. Ce programme linéaire est le problème dual.
Ces deux programmes sont toujours symétriques, dans les sens suivants:
• Il y a une contrainte duale pour chaque variable primale, et une
variable duale pour chaque contrainte primale.
• Les coefficients objectives des variables primales deviennent les cotés
droits des contraintes duales, et les cotés droits des contraintes
primales deviennent les coefficients objectives des variables duales.
• Le dual du dual est le primal.

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 4 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

On considère le PL suivant:



max z = 3x1 + 5x2

x + 2x ≤ 12
1 2

 x + 3x 2 ≤ 10


1
x , x ≥ 0
1 2

Le dual correspondant au primal est:



 min W = 12y1 + 10y2


y + y ≥ 3
1 2

 2y + 3y2 ≥ 5


1
y , y ≥ 0
1 2

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 5 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

1 Introduction

2 Les règles de passage primal-dual

3 Théorèmes de la dualité

4 La méthode du dual simplexe

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 6 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

Primal Dual
max min
ci bi
n variables (x1 , . . . , xn ) n contraintes
m contraintes m variables (y1 , . . . , ym )
contrainte j de type ≤ variable yj ≥ 0
contrainte j de type = variable yj ∈ R
variable xi ≥ 0 contrainte i de type ≥
variable xi ∈ R contrainte i de type =
 
  ′
max z = cX min W = b Y
AX ≤ b A′ Y ≥ c ′

 

X ≥0 Y ≥0

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 7 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

Exercice 1
Déterminer le dual correspondant au primal suivant:


 min W = 2x1 + 8x2



2x1 + x2 ≤ 2

x1 + 3x2 ≥ 1



 5x1 + 2x2 = 3



x1 ≥ 0, x2 ∈ R

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 8 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

1 Introduction

2 Les règles de passage primal-dual

3 Théorèmes de la dualité

4 La méthode du dual simplexe

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 9 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

Théorème 1 (Dualité faible)

Soit x une solution réalisable d’un programme linéaire de maximisation,
et y une solution réalisable de son dual. Alors cx ≤ b ′ y .
Preuve:
{
c ′ ≤ A′ Y
⇐⇒ cX ≤ (A′ Y )′ X = Y ′ AX ≤ Y ′ b = b ′ Y
X ≥0

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 10 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

Théorème 1 (Dualité faible)

Soit x une solution réalisable d’un programme linéaire de maximisation,
et y une solution réalisable de son dual. Alors cx ≤ b ′ y .
Preuve:
{
c ′ ≤ A′ Y
⇐⇒ cX ≤ (A′ Y )′ X = Y ′ AX ≤ Y ′ b = b ′ Y
X ≥0

Conséquence: Si le primal est non borné, alors le dual est impossible et

vice-versa.

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 10 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

Théorème 2 (Dualité forte)

Si le primal a une solution optimale X ∗ , alors le dual a aussi une solution
optimale Y ∗ et cX ∗ = b ′ Y ∗ .

Théorème 3 (Écarts complémentaires)

Soient X = (x1 , x2 , . . . , xn ) une solution réalisable du primal et
Y = (y1 , . . . , ym ) une solution réalisable du dual. Soient (e1 , . . . , em ) les
variables d’écarts du primal et (s1 , . . . , sn ) les variables d’écarts du dual.
X et Y représentent les solutions optimales du primal et du dual
respectivement si et seulement si:

xi si = 0 ∀i = 1, . . . , n

yj ej = 0 ∀j = 1, . . . , m

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 11 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

Le tableau du simplexe du programme primal de type maximisation est

comme suit:
cj 3 -1 0 0
bi
Base x1 x2 e1 e2
3 x1 1 3 0 1 2
0 e1 0 5 1 2 2
zj 3 9 0 3 z =6
δ j = cj − zj 0 -10 0 -3

1) Ce tableau est-il optimal? Si oui, déterminer la solution optimale.

2) En déduire la solution optimale du dual correspondant.

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 12 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

1) Tous les coefficients δj ≤ 0 et la fonction objectif de type

maximisation, donc le tableau du simplexe donné est optimale et on a:
X ∗ = (2, 0, 2, 0) et z ∗ = 6.
2) Puisque le programme primal admet une solution optimale, alors le
dual a aussi une solution optimale et on a W ∗ = z ∗ = 6 et d’après le
théorème des écarts complémentaires, on a:
y1 e1 = 0 =⇒ y1 = 0 car e1 = 2 ̸= 0.
y2 e2 = 0 =⇒ y2 ̸= 0 car e2 = 0. y2 = −δ4 = 3
s1 x1 = 0 =⇒ s1 = 0 car x1 = 2 ̸= 0.
s2 x2 = 0 =⇒ s2 ̸= 0 car x2 = 0. s2 = −δ2 = 10.
Ainsi, Y ∗ = (0, 3, 0, 10).

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 13 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

1 Introduction

2 Les règles de passage primal-dual

3 Théorèmes de la dualité

4 La méthode du dual simplexe

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 14 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

La méthode du dual simplexe s’applique lorsqu’on dispose d’une solution

de base initiale duale réalisable mais non nécessairement réalisable au
sens où on n’a pas nécessairement positivité des variables de base.
A chaque itération de la méthode du simplexe dual, on applique le
simplexe sur le problème dual pour déterminer les variables entrante et
sortante dans la base du programme primal.
Variable sortante: c’est la variable la plus négative.
Variable entrante: Soit Li la ligne pivotale. Si aij ≥ 0 pour tout j, alors
le programme est non réalisable (programme { impossible).} Sinon, alors la
δs δ
variable sortante xs est telle que ais = min aijj : aij < 0 .
Critère d’arrêt: Si tous les coefficients du second membre sont positifs
et δj ≤ 0, ∀j, alors le tableau est optimal.

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 15 / 16
Introduction Les règles de passage primal-dual Théorèmes de la dualité La méthode du dual simplexe

Exemple 1
Résoudre le programme suivant par la méthode du dual simplexe.


 min z = 2x1 + 3x2 + 4x3 + 5x4




x1 − x2 + x3 − x4 ≥ 10
x1 − 2x2 + 3x3 − 4x4 ≥ 6



 x1 − 4x2 + 5x3 − 6x4 ≥ 15



x1 , x2 , x3 , x 4 ≥ 0

Mohamed Essaied Hamrita

Recherche opérationnelle & optimisation 16 / 16