Université Mohamed VI

Polytechnique
Master 1 : TIUF

Leçon 5 : Dualité
 Définition du problème dual
Propriétés de la dualité

La dualité associe à tout problème linéaire un autre problème

linéaire qui est appelé problème dual du problème initial ; par op-
position le problème initial est appelé problème primal.
La notion de dualité en P.L. est très intéressante puisqu’elle
permet de montrer qu’un problème d’allocation optimale des
ressources rares est aussi un problème de tarification optimale
de ces ressources.
 Définition du problème dual
Propriétés de la dualité

Exemple 1

Reprenons le modèle de l’entreprise Remox décrit au chapitre 3,

que nous dénoterons (P) :

Max z = 7x1 + 9x2 + 18x3 + 17x4





2x1 + 4x2 + 5x3 + 7x4 6 42



(P) x1 + x2 + 2x3 + 2x4 6 17




 x1 + 2x2 + 3x3 + 3x4 6 24

x1 , x2 , x3 , x4 > 0
 Définition du problème dual
Propriétés de la dualité

Exemple 1

Une entreprise concurrente à Remox se propose d’acheter son

stock. Soit u1 , u2 et u3 les prix respectifs d’une unité de la
ressource A, de B et de C. Quels prix minimaux u1 , u2 et u3 doit-
elle offrir à Remox tout en restant compétitif en ce qui concerne
le marché précédent ?
 Définition du problème dual
Propriétés de la dualité

Exemple 1
Le problème revient à rendre minimum le coût recherché par
l’entreprise concurrente

min w = 24u1 + 17u2 + 24u3

Compte tenu des contraintes suivantes :

2 u1 + 1 u2 + 1 u3 > 7 (Produit 1)
4 u1 + 1 u2 + 2 u3 > 9 (Produit 2)
5 u1 + 2 u2 + 3 u3 > 18 (Produit 3)
7 u1 + 1 u2 + 3 u3 > 17 (Produit 4)

Et il est raisonnable de penser que

u1 , u2 , u3 > 0
 Définition du problème dual
Propriétés de la dualité

Exemple 1

Finalement, pour déterminer les prix unitaires minimaux qu’elle

proposera à Remox, l’entreprise concurrente devrait résoudre le
programme linéaire suivant :

Min w = 42u1 + 17u2 + 24u3





2u1 + u2 + u3 > 7




+ u2 + 2u3 > 9

(D) 4u1


 5u1 + 2u2 + 3u3 > 18



 7u1 + 2u2 + 3u3 > 17

u1 , u2 , u3 > 0
 Définition du problème dual
Propriétés de la dualité

Exemple 1

Primal (Max)
Coeff. des xi S.M
x1 x2 x3 x4 b
u1 2 4 5 7 6 42

Coeff. dans w
Coeff. des uj

u2 1 1 2 2 6 17
Dual (Min)

u3 1 2 3 3 6 24
7 6

9 6

18 6

17 6
S.M.
c

Coeff. dans z
 Définition du problème dual
Propriétés de la dualité

Exemple 2

Un pharmacien doit préparer une poudre vitaminée contenant

au moins 25 mg de vitamine A, 60 mg de vitamine B et 15 mg
de vitamine C. Il s’approvisionne auprès un laboratoire qui vend
deux types de poudre vitaminée en sachet :
— une poudre X de 20 mg de A, 30 mg de B et 5 mg de C, au
prix de 60 dh ;
— une poudre Y de 5 mg de A, 20 mg de B et 10 mg de C, au
prix de 90 dh ;
Combien doit-il se procurer de poudre X et de poudre Y pour
assurer, au coût minimum, son nouveau poudre ?
 Définition du problème dual
Propriétés de la dualité

Exemple 2

Le problème du pharmacien se formule :

Min z = 60x1 + 90x2




20x1 + 5x2 > 25



(P) 30x1 + 20x2 > 60




 5x1 + 10x2 > 15

x1 , x2 > 0

où x1 et x2 les nombres de poudres de types X etY qui’il doit

mélanger.
Le laboratoire décide de vendre séparément les vitamines A, B et
C en sachet de 25, 60 et 15 unités. Combien doit-il vendre l’unité
de chaque vitamine pour être compétitif avec le pharmacien ?
 Définition du problème dual
Propriétés de la dualité

Exemple 2

Soient u1 , u2
et u3 les prix unitaires respectifs de A, B et C. Le
labo cherche donc à maximiser son chiffre d’affaire :

w = 25u1 + 60u2 + 15u3

Le labo doit fixer les prix offerts pour les vitas de façon à ce que :
— un mélange équivalent à X ne coûte pas plus cher que la X ;
— un mélange équivalent à Y ne coûte pas plus cher que Y.
Ce qu’on peut écrire :

20u1 + 30u2 + 5u3 6 60

5u1 + 20u2 + 10u3 6 90

Et il est raisonnable de penser que : u1 , u2 , u3 > 0.

 Définition du problème dual
Propriétés de la dualité

Exemple 2

Finalement, pour déterminer les prix unitaires maximaux qu’il ne

doit pas dépasser pour rester compétitif, le labo devrait résoudre
le programme linéaire suivant :

Max w = 20u1 + 60u2 + 15u3





20u1 + 30u2 + 5u3 6 60

(D)

 5u1 + 20u2 + 10u3 6 90

u1 , u2 , u3 > 0

 Définition du problème dual
Propriétés de la dualité

Définition du problème dual

Soit le problème primal


 max c x

(P) Ax 6 b (1)

x>0


Le problème dual correspondant est


 min u b

(D) At u > c (2)

u>0

 Définition du problème dual
Propriétés de la dualité

Définition du problème dual

Si le problème primal est un PL à minimiser, sa forme canonique

est du type (2), et celle de son dual est du type (1) ; on en déduit
immédiatement que le dual du dual est le primal lui-même.
 Définition du problème dual
Propriétés de la dualité

Définition du problème dual

Les règles de passage du primal au dual sont simples : elles

résultent pour la plupart de la transposition de A.
— A étant de p × n, le primal possède n variables et le dual p
variables
— Le second membre du primal devient le vecteur des coeffi-
cients de la fonction objectif du dual et réciproquement.
— Si le primal est un problème de maximisation, le dual est un
problème de minimisation et réciproquement.
— Le sens des contraintes réelles est inversé.
— Les variables duales doivent être positives ou nulles.
 Définition du problème dual
Propriétés de la dualité

Exemple 1
Soit le problème linéaire

x1 +

 max 3x2




 x1 + x2 6 14
(P) −2x1 + 3x2 6 12




 2x1 − x2 6 12

x1 , x2 ≧ 0

Son dual est

 Définition du problème dual
Propriétés de la dualité

Exemple 1
Soit le problème linéaire

x1 +

 max 3x2




 x1 + x2 6 14
(P) −2x1 + 3x2 6 12




 2x1 − x2 6 12

x1 , x2 ≧ 0

Son dual est



 min 14u1 + 12u2 + 12u3
u1 − 2u2 + 2u3 > 1


(D)

 u1 + 3u2 − u3 > 3

u1 , u2 , u3 ≧ 0

 Définition du problème dual
Propriétés de la dualité

Exemple 2
Soit le problème linéaire


 min −x1 + x2

> −2



 2x1 − x2
(P) x1 − x2 6 2

x1 + x2 6



 5

x1 , x2 >

0

Son dual est

 Définition du problème dual
Propriétés de la dualité

Exemple 2
Soit le problème linéaire
 

 min −x1 + x2 
 min −x1 + x2
 
> −2 2x1 − x2 > −2
 


 2x1 − x2 


(P) x1 − x2 6 2 =⇒ −x1 + x2 > −2
 
x1 + x2 6 −x1 − x2 > −5
 


 5 


 
x1 , x2 > x1 , x2 >
 
0 0

Son dual est

 Définition du problème dual
Propriétés de la dualité

Exemple 2
Soit le problème linéaire
 

 min −x1 + x2 
 min −x1 + x2
 
> −2 2x1 − x2 > −2
 


 2x1 − x2 


(P) x1 − x2 6 2 =⇒ −x1 + x2 > −2
 
x1 + x2 6 −x1 − x2 > −5
 


 5 


 
x1 , x2 > x1 , x2 >
 
0 0

Son dual est



 max −2u1 − 2u2 − 5u3


2u1 − u2 − u3 6 −1

(D)


 −u1 + u2 − u3 6 1

u1 , u2 , u3 > 0

 Définition du problème dual
Propriétés de la dualité

Exemple 3
Soit le problème linéaire


 max 5x1 + 7x2

x1 + x2 >6




(P) x1 >4

63



 x2

x1 , x2 >0


Son dual est

 Définition du problème dual
Propriétés de la dualité

Exemple 3
Soit le problème linéaire
 

 max 5x1 + 7x2 
 max 5x1 + 7x2
 
x1 + x2 >6 −x1 − x2 6 −6

 


 

(P) x1 > 4 =⇒ −x1 6 −4
 
63 x2 6 3
 


 x2 


 
x1 , x2 >0 x1 , x2 >
 
0

Son dual est

 Définition du problème dual
Propriétés de la dualité

Exemple 3
Soit le problème linéaire
 

 max 5x1 + 7x2 
 max 5x1 + 7x2
 
x1 + x2 >6 −x1 − x2 6 −6

 


 

(P) x1 > 4 =⇒ −x1 6 −4
 
63 x2 6 3
 


 x2 


 
x1 , x2 >0 x1 , x2 >
 
0

Son dual est



 min −6u1 − 4u2 + 3u3


−u1 − u2 >5

(D)


 −u1 + u3 > 7

u1 , u2 , u3 > 0

 Définition du problème dual
Propriétés de la dualité

Contraintes d’égalité

Si le problème primal est sous la forme


 min c x

(P) Ax = b (3)

x≧0


le problème dual correspondant est


 max u b

(D) At u ≦ c (3)

u qcq


Nous pouvons vérifier, en mettant la forme standard (3) sous la

forme (2), que cette définition est cohérente avec la précédente.
 Définition du problème dual
Propriétés de la dualité

Règles de dualisation

Le tableau suivant donne un ensemble de règles formelles per-

mettant de passer d’un problème de P.L. général à sa forme
duale.

max min
xj > 0 ⇐⇒ contrainte j >
xj 6 0 ⇐⇒ contrainte j 6
xj qcq ⇐⇒ contrainte j =
contrainte i 6 ⇐⇒ ui > 0
contrainte i > ⇐⇒ ui 6 0
contrainte i = ⇐⇒ ui qcq
 Définition du problème dual
Propriétés de la dualité

Propriétés de la dualité

Considérons un problème linéaire de maximisation – le primal –

sous sa forme canonique et son dual
 

 z̃ = max z = c x  w̃ = min w = u b

(P) Ax ≦ b (D) uA ≧ c
 
x≧0 u≧0
 
 Définition du problème dual
Propriétés de la dualité

Propriétés de la dualité : Dualité faible

Propriété 1 :
Si x et u sont des solutions réalisables respectivement du
primal (maximum) et du dual (minimum), elles vérifient :
cx 6 ub

En effet,
) (
Ax 6 b et u ≧ 0 uAx 6 ub
=⇒ =⇒ cx 6 ub
uA > c et x ≧ 0 uAx > cx
 Définition du problème dual
Propriétés de la dualité

Propriétés de la dualité

Corollaire :
Une solution réalisable du dual (resp. primal) fournit une
borne supérieure (resp. inférieure) de w (resp. z) :

z̃ 6 ub ∀ u réalisable du dual
w̃ > cx ∀ x réalisable du primal
 Définition du problème dual
Propriétés de la dualité

Propriétés de la dualité

Condition suffisante d’optimalité

Corollaire :
Soient x et u des solutions réalisables respectivement du
primal et du dual. Si cx = ub, alors x et u sont solutions
optimales

En effet, si x n’est pas solution optimale, il existe une solution

réalisable x∗ pour laquelle cx < cx∗ . On aurait donc ub < cx∗ , ce
qui est impossible en vertu de la propriété 1.
 Définition du problème dual
Propriétés de la dualité

Propriétés de la dualité

Corollaire :
Si un problème possède une valeur optimale infinie, son
dual est impossible.

En effet, supposons que z̃ = +∞. D’après le corollaire 1 :

ub > +∞ pour toute solution réalisable u du dual

ce qui est impossible.

Même démonstration si le dual est non borné.

w̃ = −∞ =⇒ ub 6 −∞ =⇒ le primal est impossible

 Définition du problème dual
Propriétés de la dualité

Propriétés de la dualité : Dualité forte

Corollaire :
L’égalité des fonctions économiques du primal et du dual
est donc une C.N.S. d’optimalité pour des solutions réalis-
ables des deux problèmes.
 Définition du problème dual
Propriétés de la dualité

Propriétés de la dualité : Dualité faible

Propriété 2 :
Si le problème primal (resp. dual) possède une solution
optimale finie, alors il en de même pour le problème dual
(resp. primal) et de plus z̃ = w̃.
 Définition du problème dual
Propriétés de la dualité

Propriétés de la dualité

Propriété 2 :
Pour une paire de problèmes liés par la dualité :
1◦ soit les deux problèmes ont des solutions optimales
finies (propriété 2) ;
2◦ soit un problème est non borné et l’autre est impossible
(corollaire 3) ;
3◦ soit les deux problèmes sont impossibles.

Voir Illustrations ci-après

 Définition du problème dual
Propriétés de la dualité

Les deux problèmes ont des solutions finies

 

 min 2x1 + 2x2 
 max −u1 − u2
x1 − x2 > −1 u1 − u2 6 2

 

(P) (D)

 −x 1 + x2 > −1 
 −u 1 + u2 6 2
 
x1 , x2 > 0 u1 , u2 > 0
 

4 4

0 0
0 4 0 4
 Définition du problème dual
Propriétés de la dualité

Un problème est impossible ; l’autre est non borné

 

 max 2x1 + 2x2 
 min u1 + u2
−x1 + x2 6 1 −u1 + u2 > 2

 

(P) (D)

 x1 − x2 6 1 
 u1 − u2 > 2
 
x1 , x2 > 0 u1 , u2 > 0
 

4 4

0 0
0 4 0 4
 Définition du problème dual
Propriétés de la dualité

Les deux problèmes sont impossibles

 

 max 2x1 + 2x2 
 min −u1 − u2
x1 − x2 6 −1 u1 − u2 > 2

 

(P) (D)

 −x 1 + x2 6 −1 
 −u 1 + u2 > 2
 
x1 , x2 > 0 u1 , u2 > 0
 

4 4

0 0
0 4 0 4
 Définition du problème dual
Propriétés de la dualité

Théorème des écarts complémentaires

Considérons un problème linéaire de maximisation – le primal –

sous sa forme canonique et son dual
 

 z̃ = max z = c x  w̃ = min w = u b

(P) Ax ≦ b (D) uA ≧ c
 
x≧0 u≧0
 
 Définition du problème dual
Propriétés de la dualité

Théorème des écarts complémentaires

Propriété 1 :
Soient x et u deux solutions réalisables respectivement du
primal et du dual. Une CNS pour que x et u soient solutions
optimales, est qu’elles vérifient les relations :

u (Ax − b) = 0
(c − uA) x = 0

Etant donné que par hypothèse,

)
u (b − Ax) = α > 0
=⇒ cx − ub = α + β > 0
(uA − c) x = β > 0
 Définition du problème dual
Propriétés de la dualité

Théorème des écarts complémentaires

Appelons
(Li x 6 bi , ui > 0) i = 1, . . . , m
ou
(xj > 0, uCj > cj , ) j = 1, . . . , n
des couples de contraintes duales.
Convenons qu’une contrainte d’inégalité (6 ou >) est dite serrée
pour une solution, si elle est vérifiée avec le signe d’égalité (=).
 Définition du problème dual
Propriétés de la dualité

Théorème des écarts complémentaires

Le théorème des écarts complémentaires peut alors s’énoncer :

Propriété 1 :
A l’optimum, dans tout couple de contraintes duales, il y a
au moins une contrainte serrée.

Ainsi, si x et u sont des solutions optimales, respectivement du

primal et du dual, on en déduit :

• xj > 0 −→ uCj = cj
• Li x < bi −→ ui = 0
• ui > 0 −→ Li x = bi
• uCj > cj −→ xj = 0
 Définition du problème dual
Propriétés de la dualité

Théorème des écarts complémentaires

En introduisant les variables d’écart y et v des contraintes réelles

du primal et du dual :

Ax + y = b
uA − v = c

Le théorème des écarts complémentaires s’écrit simplement :

xi vi = 0 i = 1, . . . , n
yj uj = 0 j = 1, . . . , m

ce qui justifie l’appellation « écarts complémentaires ».

 Définition du problème dual
Propriétés de la dualité

Exemple

Appliquons le TEC au problème linéaire suivant :

max 15x1 + 25x2







 x1 + 3x2 6 96
(P) x1 + x2 6 40




 7x1 + 4x2 6 238

x1 , x2 ≧ 0
 Définition du problème dual
Propriétés de la dualité

Exemple

Son dual est le problème linéaire suivant :



 min 96u1 + 40u2 + 238u3
u1 + u2 + 7u3 > 15


(D)

 3u1 + u2 + 4u3 > 25

u1 , u2 , u3 ≧ 0

 Définition du problème dual
Propriétés de la dualité

Exemple

Soit la solution primale

x1 = 0, x2 = 32

Les deux dernières contraintes ne sont pas saturées

=⇒ les deux variables duales associées sont nulles ;
x2 > 0 =⇒ 2ieme contrainte duale saturée ;
Donc 3u1 = 25 =⇒ u1 = 25/3 (et u2 = u3 = 0) ;
Cette solution ne satisfait pas la 1ere contrainte duale
=⇒ non réalisable ! ;
La solution primale précédente n’est donc pas optimale !
 Définition du problème dual
Propriétés de la dualité

Exemple

Considérons maintenant la solution primale :

x1 = 12, x2 = 28
La dernière contrainte n’est pas saturée
=⇒ la variables duale associée est nulle ;
x1 , x2 > 0 =⇒ 2 contraintes duales saturées ;
On obtient donc le système suivant :
u1 + u2 = 15
3u1 + u2 = 25
On fait la différence des 2 égalités
2u1 = 10 =⇒ u1 = 5 =⇒ u2 = 10
Cette solution est admissible pour (D) =⇒ x1 = 12, x2 = 28
est optimale