Graphes et RO – TELECOM Nancy 2A

Chapitre 4 : Dualité en programmation linéaire

J.-F. Scheid

v2.1

1
Plan du chapitre

1 Introduction et définitions
2 Propriétés et Théorèmes de dualité
3 Conditions d’optimalité primal-dual (COPD)

2
I. Introduction et définitions

Problème du production.
Deux produits P1 et P2 fabriqués en quantité x1 et x2 , nécessitant trois
ressources disponibles en quantités données. L’entreprise cherche à
maximiser le bénéfice total provenant de la vente des 2 produits.

max [F (x1 , x2 ) = 6x1 + 4x2 ] .

(x1 ,x
2 )
 3x1 + 9x2 ≤ 81
4x1 + 5x2 ≤ 55
2x1 + x2 ≤ 20

x1 , x2 ≥ 0

3
Supposons à présent qu’un acheteur se présente pour acheter toutes les
ressources de l’entreprise. Il propose à l’entreprise les prix unitaires y1 , y2 ,
y3 pour chacune des ressources.

4
Supposons à présent qu’un acheteur se présente pour acheter toutes les
ressources de l’entreprise. Il propose à l’entreprise les prix unitaires y1 , y2 ,
y3 pour chacune des ressources.
L’entreprise acceptera de lui vendre toutes ses ressources uniquement
si elle obtient pour chaque produit un prix de vente au moins égal au
profit qu’elle ferait en vendant ses produits.

4
Supposons à présent qu’un acheteur se présente pour acheter toutes les
ressources de l’entreprise. Il propose à l’entreprise les prix unitaires y1 , y2 ,
y3 pour chacune des ressources.
L’entreprise acceptera de lui vendre toutes ses ressources uniquement
si elle obtient pour chaque produit un prix de vente au moins égal au
profit qu’elle ferait en vendant ses produits.
De son côté, l’acheteur cherche à minimiser ses dépenses.

4
Supposons à présent qu’un acheteur se présente pour acheter toutes les
ressources de l’entreprise. Il propose à l’entreprise les prix unitaires y1 , y2 ,
y3 pour chacune des ressources.
L’entreprise acceptera de lui vendre toutes ses ressources uniquement
si elle obtient pour chaque produit un prix de vente au moins égal au
profit qu’elle ferait en vendant ses produits.
De son côté, l’acheteur cherche à minimiser ses dépenses.

Quels prix unitaires y1 , y2 , y3 l’acheteur doit-il proposer à l’entreprise en

question pour qu’elle accepte de vendre toutes ses ressources ?

4
Supposons à présent qu’un acheteur se présente pour acheter toutes les
ressources de l’entreprise. Il propose à l’entreprise les prix unitaires y1 , y2 ,
y3 pour chacune des ressources.
L’entreprise acceptera de lui vendre toutes ses ressources uniquement
si elle obtient pour chaque produit un prix de vente au moins égal au
profit qu’elle ferait en vendant ses produits.
De son côté, l’acheteur cherche à minimiser ses dépenses.

Quels prix unitaires y1 , y2 , y3 l’acheteur doit-il proposer à l’entreprise en

question pour qu’elle accepte de vendre toutes ses ressources ?

à Programme linéaire.

min [G (y1 , y2 , y3 ) = 81y1 + 55y2 + 20y3 ]

(y1 ,y2 ,y3 )

3y1 + 4y2 + 2y3 ≥ 6
9y1 + 5y2 + 1y3 ≥ 4
y1 , y2 , y3 ≥ 0
4
Matrice A de taille m × n
Vecteurs c ∈ Rn et b ∈ Rm .
Définition (problème dual)
Au programme linéaire primal
h i
maxn F (x) = c> x
x∈R
(PL) 
Ax ≤ b
x≥0

on associe le programme linéaire dual

h i
minm G (y) = b> y
y∈R
(PLD)  >
A y≥c
y≥0

5
 Programme linéaire primal Programme linéaire dual
h i h i
maxn F (x) = c> x minm G (y) = b> y
x∈R y∈R
(PL)  (PLD)  >
Ax ≤ b A y≥c
x≥0 y≥0

Comparaison primal/dual.

Primal Dual
max(F ) Ö min(G )
coefficient c de F Ö second membre c
second membre b Ö coefficient b de G
m contraintes inégalités (Ax ≤ b) Ö m contraintes de positivité (y ≥ 0)
n contraintes de positivité (x ≥ 0) Ö n contraintes inégalités (A> y ≥ c)

6
Définition générale de la dualité quand le problème primal est sous
forme canonique mixte

Primal Dual
h i h i
maxn F (x) = c> x minm G (y) = b> y
x∈R y∈R
n
X
∀i ∈ I1 , aij xj ≤ bi ↔ ∀i ∈ I1 , yi ≥ 0
j=1
Xn
∀i ∈ I2 , aij xj = bi ↔ ∀i ∈ I2 , yi de signe
j=1 quelconque
X m
∀j ∈ J1 , xj ≥ 0 ↔ ∀j ∈ J1 , aij yi ≥ cj
i=1
m
X
∀j ∈ J2 , xj de signe ↔ ∀j ∈ J2 , aij yi = cj
quelconque i=1

7
II. Propriétés - Théorèmes de dualité

Proposition
Le dual du dual est le primal.

8
II. Propriétés - Théorèmes de dualité

Proposition
Le dual du dual est le primal.

Preuve. Dual d’un (PL) sous forme canonique pure :

h i h i
min G (y) = b> y max −G (y) = (−b)> y
y y
(PLD)  > ⇐⇒
−A> y ≤ −c

A y≥c
y≥0 y≥0

8
II. Propriétés - Théorèmes de dualité

Proposition
Le dual du dual est le primal.

Preuve. Dual d’un (PL) sous forme canonique pure :

h i h i
min G (y) = b> y max −G (y) = (−b)> y
y y
(PLD)  > ⇐⇒
−A> y ≤ −c

A y≥c
y≥0 y≥0
On prend le dual du dual :
h i
min (−c)> x
h i
>
x max c x
x
⇐⇒ (PL)
(
> 
(−A> ) x ≥ −b Ax ≤ b
x≥0 x≥0

8
Théorèmes de dualité
Théorème 1. Théorème faible de dualité
Soit x une solution réalisable d’un (PL) sous forme canonique mixte et y
une solution réalisable du problème dual (PLD). Alors :
1 F (x) ≤ G (y)
2 Si F (x) = G (y) alors x et y sont des solutions optimales de (PL) et
(PLD) respectivement.

9
Théorèmes de dualité
Théorème 1. Théorème faible de dualité
Soit x une solution réalisable d’un (PL) sous forme canonique mixte et y
une solution réalisable du problème dual (PLD). Alors :
1 F (x) ≤ G (y)
2 Si F (x) = G (y) alors x et y sont des solutions optimales de (PL) et
(PLD) respectivement.

Preuve. (PL) sous forme canonique pure

1 On a Ax ≤ b, x ≥ 0 et A> y ≥ c, y ≥ 0.

>
F (x) = c> x ≤ (A> y) x = y> |{z}
Ax ≤ y> b = G (y)
≤b

9
Théorèmes de dualité
Théorème 1. Théorème faible de dualité
Soit x une solution réalisable d’un (PL) sous forme canonique mixte et y
une solution réalisable du problème dual (PLD). Alors :
1 F (x) ≤ G (y)
2 Si F (x) = G (y) alors x et y sont des solutions optimales de (PL) et
(PLD) respectivement.

Preuve. (PL) sous forme canonique pure

1 On a Ax ≤ b, x ≥ 0 et A> y ≥ c, y ≥ 0.

>
F (x) = c> x ≤ (A> y) x = y> |{z}
Ax ≤ y> b = G (y)
≤b

2 Soient x∗ et y∗ des solutions réalisables de (PL) et (PLD) telles que

F (x∗ ) = G (y∗ ). D’après 1., pour x solution réalisable de (PL), on a
F (x) ≤ G (y∗ ) = F (x∗ ) donc x∗ est une solution réalisable optimale.
Idem pour y∗ . 
9
Théorème 2. Théorème fort de dualité
Si le problème primal (PL) admet une solution réalisable optimale x∗ alors
le problème dual (PLD) admet lui aussi une solution réalisable optimale y∗
et on a
F (x∗ ) = G (y∗ ).

10
Théorème 2. Théorème fort de dualité
Si le problème primal (PL) admet une solution réalisable optimale x∗ alors
le problème dual (PLD) admet lui aussi une solution réalisable optimale y∗
et on a
F (x∗ ) = G (y∗ ).

Preuve. On suppose (PL) mis sous forme standard.

S’il existe une solution réalisable optimale, alors il existe une solution de
base réalisable optimale xB ∗ = A−1 B ∗ b.

10
Théorème 2. Théorème fort de dualité
Si le problème primal (PL) admet une solution réalisable optimale x∗ alors
le problème dual (PLD) admet lui aussi une solution réalisable optimale y∗
et on a
F (x∗ ) = G (y∗ ).

Preuve. On suppose (PL) mis sous forme standard.

S’il existe une solution réalisable optimale, alors il existe une solution de
base réalisable optimale xB ∗ = A−1 B ∗ b. On choisit alors

>
y∗ = (A−1
B ∗ ) cB .
∗

On montre que y∗ est une solution réalisable optimale pour le dual (PLD).

10
 >
• Avec y∗ = (A−1
B ∗ ) cB , on a
∗

−1 > −1

>
A> ∗ >
H ∗ y = AH ∗ (AB ∗ ) cB ∗ = AB ∗ AH ∗ cB ∗ = cH ∗ − LH ∗ .

Or, à l’optimum LH ∗ ≤ 0 donc A> ∗ > ∗

H ∗ y ≥ cH ∗ . Puisque AB ∗ y = cB ∗ ,
on a
A> y∗ ≥ c
y∗ de signe quelconque.
i.e. y∗ est une solution réalisable du dual (PLD) (pas de contrainte de
positivité sur les variables y du dual).

11
 >
• Avec y∗ = (A−1
B ∗ ) cB , on a
∗

−1 > −1

>
A> ∗ >
H ∗ y = AH ∗ (AB ∗ ) cB ∗ = AB ∗ AH ∗ cB ∗ = cH ∗ − LH ∗ .

Or, à l’optimum LH ∗ ≤ 0 donc A> ∗ > ∗

H ∗ y ≥ cH ∗ . Puisque AB ∗ y = cB ∗ ,
on a
A> y∗ ≥ c
y∗ de signe quelconque.
i.e. y∗ est une solution réalisable du dual (PLD) (pas de contrainte de
positivité sur les variables y du dual).
•
−1
F (x∗ ) = c> x∗ = c> B ∗ AB ∗ b
> >
(A−1 b = G (y∗ )


= B ∗ ) cB
∗
| {z }
y∗

Théorème faible de dualité ⇒ y∗ est optimal pour (PLD). 

11
Lien primal/dual
Rappel : 3 cas possibles (et seulement 3) pour le problème primal (PL) :
(1) il existe (au moins) une solution optimale.
(2) l’ensemble DR des solutions réalisables n’est pas borné et l’optimum
est infini.
(3) pas de solution réalisable (DR = ∅).

12
Lien primal/dual
Rappel : 3 cas possibles (et seulement 3) pour le problème primal (PL) :
(1) il existe (au moins) une solution optimale.
(2) l’ensemble DR des solutions réalisables n’est pas borné et l’optimum
est infini.
(3) pas de solution réalisable (DR = ∅).

Théorème 3.
Etant donnés un problème primal (PL) et son dual (PLD), une et une
seule des trois situations suivantes a lieu
(a) les deux problèmes possèdent chacun des solutions optimales (à
l’optimum, les coûts sont égaux).
(b) un des problèmes possède une solution réalisable avec un optimum
infini, l’autre n’a pas de solution.
(c) aucun des deux problèmes ne possède de solution réalisable.

12
Il y a donc 3 situations (au lieu de 9) qui peuvent se résumer dans le
tableau suivant:

Dual
Solution Optimum pas de
(1) (2) (3)
optimale infini solution
Solution
(1) (a) impossible impossible
Primal

optimale
Optimum
(2) impossible impossible (b)
infini
pas de
(3) impossible (b) (c)
solution

13
III. Conditions d’optimalité primal-dual (COPD)
Z Cas (a) où les problèmes primal et dual possèdent chacun des
solutions optimales (optimum fini).

Théorème 4.
Soient x et y des solutions réalisables respectivement du problème primal
(PL) et du problème dual (PLD). Alors x et y sont des solutions réalisables
optimales si et seulement si les conditions d’optimalité primal-dual
(COPD) suivantes sont vérifiées:

Si une contrainte est satisfaite en tant qu’inégalité stricte dans (PL)

(resp. (PLD)) alors la variable correspondante de (PLD) (resp. (PL))
est nulle.
Si la valeur d’une variable dans (PL) ou (PLD) est
strictement positive alors la contrainte correspondante de l’autre
programme est une égalité.
14
Problème primal sous forme canonique mixte.

x et y sont optimales pour le problème primal et le problème dual

respectivement si et seulement si on a les COPD :

Xn
• ∀i ∈



 I 1 , aij xj = bi ou yi = 0

j=1



 m
X

• ∀j ∈ J , aij yi = cj ou xj = 0

1



i=1

15
Preuve de la condition nécessaire du Théorème des COPD.
On suppose le problème primal (PL) mis sous forme canonique pure.
Soient x et y des solutions réalisables optimales de (PL) et (PLD)
respectivement : Ax ≤ b, x ≥ 0 et A> y ≥ c, y ≥ 0.
Variables d’écart e et ε respectivement pour (PL) et (PLD):

Ax + e = b A> y − ε = c
et
x ≥ 0, e ≥ 0 y ≥ 0, ε ≥ 0

⇒ F (x) = c> x = (A> y − ε)> x = y> Ax − ε> x

G (y) = b> y = (Ax + e)> y = (Ax)> y + e> y = y> Ax + e> y.

Théorème de la dualité forte ⇒ F (x) = G (y)

⇒ ε> x + e > y = 0 .

16
Puisque x ≥ 0 et y ≥ 0, la relation ε> x + e> y = 0 donne

εi xi = 0, ∀i
ej yj = 0, ∀j
( (
Si εi 6= 0 alors xi = 0 Si ej 6= 0 alors yj = 0
⇒
Si xi 6= 0 alors εi = 0, Si yj 6= 0 alors ej = 0.


Réciproque (condition suffisante) à partir du Théorème faible de dualité.

17
Utilisation pratique des COPD.
Elles permettent de vérifier si une solution réalisable d’un (PL) est
optimale ou non, à partir de la connaissance d’une solution optimale du
problème dual.

x∗ et y∗ solutions réalisables optimales de (PL) et (PLD) respectivement.


Xn
aij xj∗ <bi ⇒ yi∗ =0




 •
j=1
m
X
aij yi∗ >cj ⇒ xj∗ =0

 •



i=1
 n
X
∗ >0 ⇒ aij xj∗ =bi




 • y i
j=1
m
X
∗ aij yi∗ =cj

 • xj >0 ⇒



i=1
18
Exemple. Problème de production
max F (x) = 6x1 + 4x2
x
 3x1 + 9x2 ≤ 81

(PL)  4x1 + 5x2 ≤ 55
2x + x2 ≤ 20
 1


x1 , x2 ≥ 0

Problème dual :
min [G (y) = 81y1 + 55y2 + 20y3 ]
y

(PLD)  3y1 + 4y2 + 2y3 ≥ 6
9y1 + 5y2 + 1y3 ≥ 4
y1 , y2 , y3 ≥ 0


19
Solution optimale de (PL):
COPD
e1∗ = 27/2 > 0 =⇒ y1∗ = 0
COPD
x1∗ = 15/2 > 0 =⇒ 3y1∗ + 4y2∗ + 2y3∗ = 6 (ε∗1 = 0)
COPD
x2∗ = 5 > 0 =⇒ 9y1∗ + 5y2∗ + y3∗ = 4 (ε∗2 = 0)
e2∗ = e3∗ = 0

⇒ Solution optimale du problème dual

y1∗ = 0, y2∗ = 1/3, y3∗ = 7/3.

20