RECHERCHE OPÉRATIONNELLE -

DUALITÉ

1
INTRODUCTION
Exemple
Pb de gestion de production
Produit Bureau Table Chaise Quantité
Ressource disponible de
ressource
Bois (plaque) 8 6 1 48
Menuiserie (heure) 2 1.5 0.5 8
Finition (heure) 4 2 1.5 20
Prix de revient (D) 60 30 20

Maximisation du revenu total

x1 = nombre de bureaux fabriqués

x2 = nombre de tables fabriquées
x3 = nombre de chaises fabriquées

max z = 60 x1 + 30 x2 + 20 x3
(PL) s.c. 8 x1 + 6 x2 + x3  48 (ressource bois)
2 x1 + 1.5 x2 + 0.5 x3  8 (ressource menuiserie)
4 x1 + 2 x2 + 1.5 x3  20 (ressource finition) 2
x1, x2, x3  0
INTRODUCTION
Exemple

Scénario 2 : Un entrepreneur veut acheter toutes les ressources de l’entreprise.

Objectif : minimiser le prix total d’achat de ces ressources.

On définit alors:
y1 = prix d'une plaque de bois
y2 = prix d'une heure de menuiserie
y3 = prix d'une heure de finition
Produit Bureau Table Chaise Quantité
Ressource disponible de
ressource
Bois (plaque) 8 6 1 48
Menuiserie (heure) 2 1.5 0.5 8
Finition (heure) 4 2 1.5 20
Prix de revient (D) 60 30 20

3
Min w(y) = 48y1 + 8 y2 + 20 y3
INTRODUCTION
Exemple
Min W(y) avec yi compétitifs
Scénario 1
Produit Bureau Table Chaise Quantité
Ressource disponible de
ressource
Bois (plaque) 8 6 1 48 y1
Menuiserie (heure) 2 1.5 0.5 8
Finition (heure) 4 2 1.5 20
y2
Prix de revient (D) 60 30 20 y3
Revenu1 = 60 D

Scénario 2
Revenu2 = 8y1 + 2 y2 + 4 y3

4
yi compétitifs 8y1 + 2 y2 + 4 y3 ≥ 60
INTRODUCTION
Exemple
Min W(y) avec yi compétitifs
De même
Produit Bureau Table Chaise Quantité
Ressource disponible de
ressource
Bois (plaque) 8 6 1 48 y1
Menuiserie (heure) 2 1.5 0.5 8
Finition (heure) 4 2 1.5 20
y2
Prix de revient (D) 60 30 20 y3

6y1 + 1,5 y2 + 2 y3 ≥ 30

y1 + 0,5 y2 + 1,5 y3 ≥ 20

5
INTRODUCTION
Exemple

Scénario 2 : Un entrepreneur veut acheter toutes les ressources de l’entreprise.

Produit Bureau Table Chaise Quantité
Ressource disponible de
ressource
Bois (plaque) 8 6 1 48
Menuiserie (heure) 2 1.5 0.5 8
Finition (heure) 4 2 1.5 20
Prix de revient (D) 60 30 20

min w = 48y1 + 8 y2 + 20 y3
s.c. 8y1 + 2 y2 + 4 y3  60
6y1 + 1.5 y2 + 2 y3  30
y1 + 0.5 y2 + 1.5 y3  20
y1, y2, y3  0
6
INTRODUCTION
Exemple
Scénario 1 Scénario 2
max z = 60 x1 + 30 x2 + 20 x3 min w = 48y1 + 8 y2 + 20 y3
(PL1) s.c. 8 x1 + 6 x2 + x3  48 (PL2) s.c. 8y1 + 2 y2 + 4 y3  60

2 x1 + 1.5 x2 + 0.5 x3  8 6y1 + 1.5 y2 + 2 y3  30

4 x1 + 2 x2 + 1.5 x3  20 y1 + 0.5 y2 + 1.5 y3  20

x1, x2, x3  0 y1, y2, y3  0

60 48 48 60
𝐶1 = 30 𝑏1 = 8 𝐶2 = 8 𝑏2 = 30
20 20 20 20
8 6 1 8 2 4
𝐴1 = 2 1,5 0,5 𝐴2 = 6 1,5 2
4 2 1,5 1 0,5 1,5 7
INTRODUCTION
Exemple

60 48 48 60
𝐶1 = 30 𝑏1 = 8 𝐶2 = 8 𝑏2 = 30
20 20 20 20
8 6 1 8 2 4
𝐴1 = 2 1,5 0,5 𝐴2 = 6 1,5 2
4 2 1,5 1 0,5 1,5

𝐶2 = 𝑏1
𝑏2 = 𝐶1 PL2 est le dual de PL1
𝐴2 = 𝐴1𝑡

8
DUAL D’UN PL SOUS LA FORME NORMALE
Forme Normale

𝑀𝑎𝑥 Cx 𝑀in Cx
Sc Ax ≤ b ou Sc Ax ≥ b
x≥0 x≥0

Avec A une matrice m × n , b ∈ Rm ; 𝐶 ∈ Rn , 𝑥 ∈ Rn

Dual
𝑀𝑎𝑥 Cx 𝑀in bty
(P) Sc Ax ≤ b (D) Sc Aty ≥ c
x≥0 y≥0

𝑀in Cx 𝑀ax bty

(P) Sc Ax ≥ b (D) Sc Aty ≤ c
x≥0 y≥0 9
DUAL D’UN PL À CONTRAINTES MIXTES

1. Si P est un problème de maximisation alors D est un problème

de minimisation et vice-versa.
2. Chaque colonne (ou variable) de P résulte en une contrainte
dans D et vice-versa.
3. Chaque contrainte de P correspond à une variable dans D et
vice-versa.
4. La matrice des coefficients des contraintes de D est la
transposée de P et vice-versa.
5. Les composants du second membre de D sont les coefficients de
la fonction objectif de P et vice-versa.
6. Les coefficients de la fonction objectif de D sont les coefficients
de second membre de P et vice-versa.

10
DUAL D’UN PL À CONTRAINTES MIXTES
Primal Dual
- n variables et m - m variables et n
contraintes contraintes
- Fonction à maximiser - Fonction à minimiser
- ième contrainte ≤ 0 - ième variable ≥ 0
- ième contrainte ≥ 0 - ième variable ≤ 0
- ième contrainte = 0 - ième variable <> 0
- jème variable ≥ 0 - jème contrainte ≥ 0
- jème variable ≤ 0 - jème contrainte ≤ 0
- jème variable <> 0 - ième contrainte = 0

Dual du dual = Primal

11
DUAL D’UN PL À CONTRAINTES MIXTES
Exemples

Déterminer le dual de chacun des deux PL suivants :

Max 𝑍 = 2𝑥1 + 𝑥2
(P1) Sc 𝑥1 + 𝑥2 = 2
2 𝑥1 − 𝑥2 ≥ 3
𝑥1 − 𝑥2 ≤ 1
𝑥1 ≥ 0 ; 𝑥2 <> 0

Min 𝑍 = 5𝑥1 − 6𝑥2 + 7𝑥3 + 𝑥4

(P2) Sc 𝑥1 + 2𝑥2 − 𝑥3 − 𝑥4 = −7
6𝑥1 − 3𝑥2 + 𝑥3 + 7𝑥4 ≥ 14
−2𝑥1 − 17𝑥2 + 4𝑥3 + 2𝑥4 ≤ −3
𝑥1 ≤ 0 ; 𝑥2 ≥ 0 ; 𝑥3 <> 0 ; 𝑥4 <> 0
12
DUALITÉ ET CONDITIONS D’OPTIMALITÉ
On considère le problème standard (P) et son dual (D) :

𝑀in 𝐶 𝑡 x 𝑀𝑎𝑥 w = 𝑏𝑡 y
(P) Sc Ax = b (D) Sc 𝐴𝑡 𝑦 ≤ C
x≥0 y <> 0

Lemme 1 (faible dualité)

Si x une solution réalisable de (P) et y une solution réalisable de (D),
alors : 𝐶 𝑡 . 𝑥 ≥ 𝑏𝑡 . 𝑦

Implications:
En particulier, on aura : z* ≥ w*

13
DUALITÉ ET CONDITIONS D’OPTIMALITÉ
On considère le problème standard (P) et son dual (D) :

𝑀in 𝐶 𝑡 x 𝑀𝑎𝑥 w = 𝑏𝑡 y
(P) Sc Ax = b (D) Sc 𝐴𝑡 𝑦 ≤ C
x≥0 y <> 0

Lemme 1 (faible dualité)

Si x une solution réalisable de (P) et y une solution réalisable de (D),
alors : 𝐶 𝑡 . 𝑥 ≥ 𝑏𝑡 . 𝑦

Démonstration:
y solution réalisable de (D)  𝐴𝑡 𝑦 ≤ C => 𝑦 𝑡 . 𝐴. 𝑥 ≤ 𝐶 𝑡 . 𝑥;
x solution réalisable de (P)  x  0

puisque Ax = b, alors 𝑦 𝑡 . 𝑏 ≤ 𝐶 𝑡 . 𝑥
14
DUALITÉ ET CONDITIONS D’OPTIMALITÉ
On considère le problème standard (P) et son dual (D) :

𝑀in 𝐶 𝑡 x 𝑀𝑎𝑥 w = 𝑏𝑡 y
(P) Sc Ax = b (D) Sc 𝐴𝑡 𝑦 ≤ C
x≥0 y <> 0
Lemme 2
Soient x0 et y0 des solutions réalisables respectives de (P) et (D).
Si , 𝐶 𝑡 . 𝑥0 = 𝑏𝑡 . 𝑦0 , alors : x0 est solution optimale de (P) et y0 est
solution optimale de (D).
Démonstration:
Pour tout x solution réalisable de (P) et y
Lemme 1
solution réalisable de (D), on a : 𝐶 𝑡 . 𝑥 ≥ 𝑏𝑡 . 𝑦
En particulier pour y0, 𝐶 𝑡 . 𝑥 ≥ 𝑏𝑡 . 𝑦0
Si , 𝐶 𝑡 . 𝑥0 = 𝑏𝑡 . 𝑦0 , alors pour tout x sol. Real. on a : 𝐶 𝑡 . 𝑥 ≥ 𝑏𝑡 . 𝑥 0
15
x0 est solution optimale de (P)
De même pour y0.
DUALITÉ ET CONDITIONS D’OPTIMALITÉ
On considère le problème standard (P) et son dual (D) :

𝑀in 𝐶 𝑡 x 𝑀𝑎𝑥 w = 𝑏𝑡 y
(P) Sc Ax = b (D) Sc 𝐴𝑡 𝑦 ≤ C
x≥0 y <> 0

Théorème de forte dualité

Soit x* une solution réalisable de P.
x* est solution optimale de P  il existe au moins y* une solution
réalisable de D tq cx* = y*b
y* est une solution optimale de D

16
 DUALITÉ ET CONDITIONS D’OPTIMALITÉ
𝑀in 𝐶 𝑡 x 𝑀𝑎𝑥 w = 𝑏 𝑡 y
(P) Sc Ax = b (D) Sc 𝐴𝑡 𝑦 ≤ C
x≥0 y <> 0
Démonstration:
( condition nécessaire de l'optimalité de x*)

x* optimum de P   = c -cB B-1A ≥ 0  cB B-1A ≤ c

La valeur de z* = cB B-1 b = cx*
posons y* = cB B-1, on a bien y*A ≤ c (réalisable pour D) et y*b = cB B-1 b = cx*.
Démontrons que y* est optimal pour D :

y* réalisable pour D ⇒ 𝑤* ≥ 𝑦*𝑏

⇒ 𝑤* = 𝑦*𝑏
De plus, d'après la faible dualité 𝑤* ≤ 𝑧* = 𝑦*𝑏
⇒ 𝑦* est un optimum de D

17
 DUALITÉ ET CONDITIONS D’OPTIMALITÉ
𝑀in 𝐶 𝑡 x 𝑀𝑎𝑥 w = 𝑏 𝑡 y
(P) Sc Ax = b (D) Sc 𝐴𝑡 𝑦 ≤ C
x≥0 y <> 0
Démonstration:
( condition suffisante de l'optimalité de x*)

Il existe x* et y* des solutions réalisables respectives de P et de D t.q cx* = y*b.

Soit x une solution réalisable de P; alors d'après la faible dualité: cx ≥ y*b.
Puisque y*b = cx*, on a alors: cx ≥ cx*  x solution réalisable de P
 x* est l'optimum de P

18
DUALITÉ ET CONDITIONS D’OPTIMALITÉ
On considère le problème standard (P) et son dual (D) :

𝑀in 𝐶 𝑡 x 𝑀𝑎𝑥 w = 𝑏 𝑡 y
(P) Sc Ax = b (D) Sc 𝐴𝑡 𝑦 ≤ C
x≥0 y <> 0
Théorème de forte dualité
Soit x* une solution réalisable de P.
x* est solution optimale de P  il existe au moins y* une solution
réalisable de D tq cx* = y*b
y* est une solution optimale de D
Corollaires du théorème de forte dualité:
P infini  D non réalisable
D infini  P non réalisable
P non réalisable et D réalisable  D infini
D non réalisable et P réalisable  P infini
19
 DUALITÉ ET CONDITIONS D’OPTIMALITÉ
Théorème des écarts complémentaires

Soient x et y deux solutions réalisables respectives de P et de D.

x et y sont solutions optimales  𝑦 𝑡 . 𝑎𝑖 − 𝐶𝑖 . 𝑥𝑖 = 0 ∀ 𝑖 = 1, … , 𝑛

ou Soient x et y deux solutions réalisables respectives de P et de D.

𝑥𝑖 > 0 ⇒ 𝑦 𝑡 . 𝑎𝑖 = 𝐶𝑖
x et y sont solutions optimales ൝ 𝑡
𝑦 . 𝑎𝑖 < 𝐶𝑖 ⇒ 𝑥𝑖 = 0

- Si la ième variable de l’un des deux pb est non nulle,

alors la ième contrainte de l’autre pb est saturée,
- Si la ième contrainte de l’un des deux pb est non saturée,
alors la ième variable de l’autre pb est nulle.

20
DUALITÉ ET CONDITIONS D’OPTIMALITÉ
Théorème des écarts complémentaires
Exemple
max 𝑍 𝑥 = 3𝑥1 + 5𝑥2
𝑠. 𝑐 𝑥1 ≤ 4
𝑃 2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
𝑥1 ≥ 0, 𝑥2 ≥ 0

1. Donner le dual de (P)

2
2. Sachant que la solution optimale de (P) est 𝑥 ∗ = ,
6
déterminer la solution optimale de (D)
3. Vérifier qu’à l’optimum on a égalité des fonctions objectifs
de (P) et (D).
21