1 / 19

Chapitre 4: Dualité et duale-simplexe

Hamed Sidi Nounou

Institut Universitaire Professionel, Licence LgTr

23 Avril 2020
 2 / 19
Dualité

Considérons le programme linéaire suivant, sous forme

standard :
min c> x
(P) s.c. Ax = b
x≥0
où x, c ∈ Rn , A ∈ Rn×m et b ∈ Rm .
On associe à ce programme linéaire un autre programme linéaire
(D) appelé le dual. Le problème original est le primal.

Le dual de (D) est déni par :

max b> y
(D)
s.c. A> y ≤ c.

On notera que, pour le problème primal, on a x ∈ Rn tandis que

y ∈ Rm pour le dual.
 3 / 19
Dualité
Dualité sous toutes ses formes : Min vers Max

Données PL Primal PL Dual

Variables x1 , x2 , · · · , xn y1 , y2 , · · · , ym
Matrice A A>
Membre de droite b c
Fonction objectif min c> x max b> y
ième contrainte ≥ ième variable yi ≥ 0
≤ yi ≤ 0
Contraintes et = yi ∈ R
les variables j ème variable xj ≥ 0 j ème contrainte ≤
xj ≤ 0 ≥
xj ∈ R =

Le dual du dual est équivalent au primal.

 4 / 19
Dualité
Dualité sous toutes ses formes : Min vers Max
 5 / 19
Dualité
Interprétation économique de la dualité

Une entreprise fabrique deux types de produis : p1 et p2 qui

rapportent respectivement c1 et c2 par unité. Chaque unité de
produit pi requiert une quantité aij de la matière première Mj .
Sachant que l'entreprise dispose d'un stock b1 de M1 et b2 de
M2 .
max c1 x1 + c2 x2
s.c. a11 x1 + a12 x2 ≤ b1
a21 x1 + a22 x2 ≤ b2
x1 , x 2 ≥ 0
Soit une rme F qui veut racheter les ressources de l'entreprise
E.

A quels prix doit-elle le faire pour tout racheter au coût

minimum ?
 6 / 19
Dualité
Interprétation économique de la dualité

L'ore de la rme F sera accepté si elle ore au moins autant

que le bénéce de chacune des activités de E . En eet, soient y1
le prix d'une unité de la matière première M1 et y2 le prix d'une
unité de la matière première M2 , pour satisfaire l'intérêt de E il
faut que
a11 y1 + a21 y2 ≥ c1
a12 x1 + a22 y2 ≥ c2

De plus F veut racheter les ressources au coût minimum, c'est à

dire min b1 y1 + b2 y2 . Donc la rme F se confronte à un
problème de type :
min b1 y1 + b2 y2
s.c. a11 y1 + a21 y2 ≥ c1
a12 y1 + a22 y2 ≥ c2
y1 , y 2 ≥ 0
 7 / 19
Dualité
Interprétation économique de la dualité

Soit le problème de production pour une entreprise E :

n
X
max cj xj
j=1
n
s.c.
X
aij xj ≤ bi i = 1, · · · , m
j=1
xj ≥ 0 j = 1, · · · , n.

Soit une rme F qui veut racheter les ressources de l'entreprise

E.

A quels prix doit-elle le faire pour tout racheter au coût

minimum ?
 8 / 19
Dualité
Interprétation économique de la dualité

On note yi le prix de la ressource i. F doit xer les yi de

m
manière à ce que aij yi ≥ cj pour tout j = 1, · · · , n. En eet,
X

i=1
pour tout j , cela garantit que E a intérêt à vendre les ressources
nécessaire pour produire une unité de j plutôt que de la
produire. D'où le programme mathématique suivant auquel se
trouve confronté F.
m
X
min bi yi
i=1
m
s.c.
X
aij yi ≥ cj j = 1, · · · , n
i=1
yi ≥ 0 i = 1, · · · , m.
C'est précisément le dual du problème de production.
 9 / 19
Dualité
Interprétation économique de la dualité

Théorème de dualité forte

Considérons la paire de problème primal-dual suivante :
min c> x
(P) s.c. Ax = b
x≥0

max b> y
(D)
s.c. A> y ≤ c.
Si un des deux problèmes admet une solution optimale, alors
l'autre problème aussi admet une solution optimale et leurs
valeurs optimales respectives coïncident.
V(P) = V(D) ⇔ c> x∗ = b> y ∗
 10 / 19
simplexe dual

L'algorithme du simplexe dual consiste à appliquer la méthode

du simplexe au problème dual.
On écrit le problème (P) sous forme canonique dans la base B :
−1
z = z̄ + c̄>

min N xN  b̄ = AB b
s.c. xB + A−1 B AN xN = b̄ avec z̄ = c> b̄
 > B> −1
xB , xN ≥ 0. c̄N = cN − c>
B AB AN .

On peut considérer les variables de base xB comme des variables

d'écart positives ( car xB ≥ 0). On obtient un problème (P 0 ) ne
portant que sur les variables hors bas xN .

min c̄>
N xN
(P 0 ) s.c. −1
AB AN xN ≤ b̄ (m contraintes )
xN ≥ 0 (n − m variables )
On écrit (P 0 ) comme un problème de max.
max −c̄>
N xN
(P 0 ) s.c. AB AN xN ≤ b̄
−1

xN ≥ 0
 11 / 19
simplexe dual

Le dual (D0 ) de (P 0 ) s'écrit

min b̄> yB
(D0 ) s.c. (A−1 >
B AN ) yB ≥ −c̄N (n − m contraintes )
yB ≥ 0 (m variables )

On met (D0 ) sous forme standard avec des variables d'écart yN

positives. On obtient un problème (D) à n variables.
min b̄> yB
(D) s.c. yN − (A−1 >
B AN ) yB = c̄N (n − m contraintes )
yB , y N ≥ 0 (n variables )

Le problème (D) est sous forme canonique dans la base B :

variables de base : yN
variables hors base : yB
(notations inversées par rapport au problème primal)
 12 / 19
simplexe dual

min b̄> yB
(D) s.c. yN − (A−1 >
B AN ) yB = c̄N (n − m contraintes )
yB , y N ≥ 0 (n variables )

Tableau TD du simplexe de (D) dans la base B :

yN yB SB
TD = I −1
−(AB AN )> c̄N
0 b̄ −z̄

variables de base : yN , la solution associée c̄N

variables hors base : yB , le vecteur des coûts réduits associé
est b̄ 
yN = c̄N
La solution de base associée à la base B est :
yB = 0
La base B est admissible (réalisable) si yN = c̄N ≥ 0 : base
dual-admissible (dual-réalisable).
 13 / 19
simplexe dual

Pivotage sur le tableau dual TD :

yN yB SB
−1
I −(AB AN )> c̄N
0 b̄ −z̄

Choix du pivot :
Variable hors base entrante ye de coût réduit négatif
(b̄e < 0)
Variable de base sortante ys , ligne s de la variable sortante :
   
c̄N i c̄N s c̄N i
min | āie < 0 ⇔ = max | āie < 0
i∈N −āie āse i∈N āie

Pivot : āse < 0

 14 / 19
simplexe dual

Pivotage sur le tableau primal : On observe que le pivotage

dual peut être réalisé à partir du tableau primal sans écrire
explicitement le tableau dual.
yN yB SB
TD = I −(A−1
B AN )
> c̄N
0 b̄ −z̄
xB xN SB
TP = I −1
AB AN b̄
0 c̄N −z̄

Choisir la variable de base négative xe : b̄e < 0, e ∈ B ;

ligne e : variable sortante.
Déterminer la variable hors base xs :
 
c̄N s c̄N j
= max | āej < 0
āse j∈N āej
colonne s : variable entrante
 15 / 19
simplexe dual

Comparaison simplexe primal et dual :

1 L'algorithme du simplexe primal
maintient une base primal-admissible : si b̄ ≥ 0.
L'optimum est atteint lorsque les coûts réduits sont positifs

ou nuls : c̄N ≥ 0.
2 L'algorithme du simplexe dual
maintient une base dual-admissible : si c̄N ≥ 0.
L'optimum est atteint lorsque les variables de base sont

positives ou nulles : b̄ ≥ 0.
 16 / 19
simplexe dual

Exemple : Algorithme du simplexe dual

On considère le problème linéaire à 5 variables

x1 , x 2 , x 3 , x 4 , x 5 :
min x1 + 2x2 + 2x3 + 3x4 + x5
s.c. x1 + x2 = 1
−x2 − x3 + x5 = 0
−x1 + x3 + x4 = 0
x1 , x2 , x3 , x4 , x5 ≥ 0.
La matrice des contraintes de ce problème est donnée par :
   
1 1 0 0 0 1
A =  0 −1 −1 0 1 , b = 0

−1 0 1 1 0 0
 
1 0 0
On pose B = {2, 3, 4}, AB = −1 −1 0 est inversible : B base

0 1 1
 17 / 19
simplexe dual

On choisit comme base initiale (x2 , x3 , x4 ), et la solution de base

associée à B est : xB = A−1
B b et xN = 0.
     
1 0 0 1 1
xB = A−1
B b = −1 −1 0 . 0 = −1
1 1 1 0 1

La base B non admissible (non réalisable) car xB  0.

Tableau du simplexe dans la base B .

x
xB A−1
B A b̄
-1 c̄> −z̄
 18 / 19
simplexe dual

B AB AN = (1, 0) et z̄ = cB AB b = 3.
−1 > −1
c̄N = cN − c>
xB \ x x1 x2 x3 x4 x5
x2 1 1 0 0 0 1
x3 −1 0 1 0 −1 −1
x4 0 0 0 1 1 1
−1 1 0 0 0 0 −3

La base est non admissible pour le primal (x3 < 0) et admissible

pour le dual ( c̄N ≥ 0 ).
On peut appliquer l'algorithme dual du simplexe pour résoudre
le problème.
Simplexe dual :
1 0
−1 −1
xB \ x x1 x2 x3 x4 x5
x2 1 1 0 0 0 1
x3 −1 0 1 0 −1 −1
x4 0 0 0 1 1 1
−1 1 0 0 0 0 −3

Variable sortante : x3 ; Variable entrante : x5 ; Pivot : ā35 = −1

 19 / 19
simplexe dual

Pivotage : entrée x5 , sortie x3 .

xB \ x x1 x2 x3 x4 x5
x2 1 1 0 0 0 1
x5 1 0 −1 0 1 1
x4 −1 0 1 1 0 0
−1 1 0 0 0 0 −3

Nouvelle base (x2 , x4 , x5 ) : cette base est

primal-admissible b̄ ≥ 0
dual-admissible c̄N ≥ 0
Donc elle est optimale.
Solution :
x∗ = (0, 1, 0, 0, 1) et z ∗ = 3.