DUALITÉ

Outils de Recherche
Opérationnelle en Génie - MTH 8414

Louis-Martin Rousseau
Office: A520.21 Tel.: #4569
Louis-
[Link]@[Link]
Soit un modèle linéaire

Max x1 + x2

x1 + 3x2 £ 3
3x1 + x2 £ 5
x1 ³ 0
x2 ³ 0
 max x1 + x2
x1
x1 + 3x2 £ 3
3x1 + x2 £ 5
x1 ³ 0
x2 ³ 0

x2
 max x1 + x2
x1
x1 + 3x2 £ 3
3x1 + x2 £ 5
x1 ³ 0
x2 ³ 0

x2
 max x1 + x2
x1
x1 + 3x2 £ 3
Solutions
3x1 + x2 £ 5
réalisables
x1 ³ 0
x2 ³ 0

x2
 max x1 + x2
x1

Solution
x1 + 3x2 £ 3
optimale 3x1 + x2 £ 5
x1=1/2, x2=3/2 x1 ³ 0
x2 ³ 0

x2
Pouvez-vous prouver l’optimalité ?
max x1 + x2
x1

Solution
x1 + 3x2 £ 3
optimale 3x1 + x2 £ 5
x1=1/2, x2=3/2 x1 ³ 0
x2 ³ 0

x2
Pouvez-vous prouver l’optimalité ?

x1 max x1 + x2
x1 + 3x2 £ 3
Solution 3x1 + x2 £ 5
optimale
x1=1/2, x2=3/2
4x1 + 4x2 £ 8

x2
Pouvez-vous prouver l’optimalité ?

x1 max x1 + x2
x1 + 3x2 £ 3
Solution 3x1 + x2 £ 5
optimale
x1=1/2, x2=3/2
x1 + x2 £ 2

x2
Un autre programme linéaire

max x1 + x2

x1 + 2x2 £ 3
4x1 + x2 £ 5
x1 ³ 0
x2 ³ 0
x1=1, x2=1, Optimale ?
Un autre programme linéaire
max x1 + x2

(x1 + 2x2 £ 3 ) *3
(4x1 + x2 £ 5 ) *1
x1 ³ 0 7x1 + 7x2 £ 14
x2 ³ 0 x1 + x2 £ 2
x1=1, x2=1, Optimale !
Un autre programme linéaire

max x1 + x2 £7x1 + 7x2 £14

La “preuve” est une borne supérieure
x1 + 2x2 £ 3 sur l’objectif.

4x1 + x2 £ 5 On veut donc construire une équation

qui, tout en étant minimale, est
x1 ³ 0 toujours plus grande que n’importe
quelle solution réalisable.
x2 ³ 0
Si la borne = la solution obtenue alors
celle si est optimale.
Recherche de la preuve d’optimalité

max x1 + x2 On cherche la plus petite borne

supérieure pour ce problème

x1 + 2x2 £ 3 * y1 On introduit des

multiplicateurs pour
4x1 + x2 £ 5 * y2 chaque contrainte
du problème
x1 ³ 0
x2 ³ 0
Recherche de la preuve d’optimalité

max x1 + x2 On cherche la plus petite borne

supérieure pour ce problème

x1 + 2x2 £ 3 * y1
4x1 + x2 £ 5 * y2 On définit leur signe:
elles doivent être
x1 ³ 0 y1 ³ 0 positives pour ne pas
changer le sens des
x2 ³ 0 y ³0 inégalités.
2
Recherche de la preuve d’optimalité

max x1 + x2 On cherche la plus petite borne

supérieure pour ce problème

Les coefficients de
x1 + 2x2 £ 3 * y1 l’expression doivent être

4x1 + x2 £ 5 * y2 plus grands que ceux de

l’objectif pour garantir une
x1 ³ 0 y1 ³ 0 valeur toujours supérieure à
celle de la fonction objectif
x2 ³ 0 y2 ³ 0
y1 + 4y2 ³ 1
2y1+y2 ³ 1
Recherche de la preuve d’optimalité

max x1 + x2 On cherche la plus petite borne

supérieure pour ce problème

On minimise la
x1 + 2x2 £ 3 * y1 valeur de la borne.

4x1 + x2 £ 5 * y2
x1 ³ 0 y1 ³ 0 min 3y1+5y2
x2 ³ 0 y2 ³ 0 y1 + 4y2 ³ 1
2y1+y2 ³ 1
L’un est le dual de l’autre

max x1+x2 min 3y1+5y2

x1 + 2x2 £ 3 y1 + 4y2 ³ 1
4x1 + x2 £ 5 Dualité 2y1+y2 ³ 1
x1 ³ 0 y1 ³ 0
x2 ³ 0 y2 ³ 0
Primal Dual
La dualité faible (solutions réalisables)

max x1+x2 £ min 3y1+5y2

x1 + 2x2 £ 3 y1 + 4y2 ³ 1
4x1 + x2 £ 5 2y1+y2 ³ 1
x1 ³ 0 y1 ³ 0
x2 ³ 0 y2 ³ 0
Primal Dual
La dualité forte (solution optimale)

max x1+x2 = min 3y1+5y2

x1 + 2x2 £ 3 y1 + 4y2 ³ 1
4x1 + x2 £ 5 2y1+y2 ³ 1
x1 ³ 0 y1 ³ 0
x2 ³ 0 y2 ³ 0
Primal Dual
Dualité
Soit le problème PRIMAL
Max z = c t x
s.c. Ax ≤ b
x≥0
Alors son DUAL est
, t
Min z = b y
s.c. A t y ≥ c
y≥0
Théorème 1 (dualité faible)

• Soient 𝐸 l’ensemble des solutions réalisables du primal et 𝐸 ! l’ensemble des solutions réalisables du dual.
Alors:

∀𝑥 ∈ 𝐸 et ∀𝑦 ∈ 𝐸 !
On a 𝑐 " 𝑥 ≤ 𝑏 " 𝑦
(i.e. 𝑧 ≤ 𝑧 ! )

Corollaire du théorème 1
• Si un P.L. n’admet pas de solution optimale finie (il est non borné), alors son dual n’admet aucune
solution réalisable (la réciproque est fausse).
Théorème 2 (dualité forte)

• S’il existe une solution 𝑥 ∗ du primal et une solution 𝑦 ∗ du dual telles que
𝑐 " 𝑥 ∗ = 𝑏 " 𝑦 ∗ alors ces solutions sont optimales pour leurs problèmes respectifs.

Théorème de dualité forte

• Si le problème primal et son dual admettent chacun au moins une solution réalisable, soit 𝑧 la valeur
de l’objectif du primal et 𝑧 ! la valeur de l’objectif du dual, alors :
a) 𝑧 et 𝑧 ! ont une valeur optimale finie
b) max 𝑧 = min 𝑧 !
Exemple

Primal Dual
𝑀𝑎𝑥 𝑧 = 2𝑥! + 3𝑥" 𝑀𝑖𝑛 𝑧′ = 3𝑦! + 8𝑦" + 4𝑦#
s.c. s.c.
𝑥! + 𝑥" ≤ 3 𝑦! − 𝑦" + 2𝑦# ≥ 2
− 𝑥! + 𝑥" ≤ 8 𝑦! + 𝑦" + 𝑦# ≥ 3
2𝑥! + 𝑥" ≤ 4 𝑦! , 𝑦" , 𝑦# ≥ 0
𝑥! , 𝑥" ≥ 0
Exemple (suite)
Si on regarde la forme matricielle

Primal Dual
1 1 3 1 -1 2 2

-1 1 8
1 1 1 3
2 1 4 3 8 4

2 3
Exemple

Primal Dual
𝑀𝑎𝑥 2400𝑥# + 4000𝑥$ 𝑀𝑖𝑛 4000𝑦# + 2600𝑦$ + 2700𝑦%
s.c. s.c.
10𝑥# + 40𝑥$ ≤ 4000 10𝑦# + 20𝑦$ + 30𝑦% ≥ 2400
20𝑥# + 20𝑥$ ≤ 2600 40𝑦# + 20𝑦$ + 10𝑦% ≥ 4000
30𝑥# + 10𝑥$ ≤ 2700
Résultats

Primal Dual
Valeur Coût réduit Valeur Coût réduit
X1 40 0 Y1 53.3 0
X2 90 0 Y2 93.3 0
Contrainte Écart Coût Marg. Y3 0 600
1 0 53.3 Contrainte Écart Coût Marg.
2 0 93.3 1 0 -40
3 600 0 2 0 -90

Que remarquez-vous ? Le dual du dual = …

La Dualité
• Le concept de la dualité est FONDAMENTAL en PL

• Il permet entre autres:

• de réduire le nombre de contraintes;
• l’obtention d’une structure plus efficace pour la résolution du problème;
• de concevoir des méthodes de décomposition performantes.

• Il fournit essentiellement l’information sur la sensibilité de la solution optimale par rapport aux
changements dans:
• l’objectif,
• les coefficients des contraintes,
• les constantes du terme de droite,
• l’addition de nouvelles variables,
• l’addition de nouvelles contraintes.
Variables duales et coûts réduits

Le prix (ou variable) dual pour chaque contrainte:

• indique l’effet sur l’objectif si on augmente d’une unité le côté droit de la contrainte.
• est aussi appelé coût marginal (shadow price) pour indiquer le montant que l’on serait prêt à payer pour une
unité additionnelle de la ressource correspondante.
• équivaut à la valeur optimale donnée à la variable associé à cette contrainte dans le problème dual.

Le coût réduit pour chaque variable.

• indique de combien on devrait augmenter le coefficient d’une variable pour qu’il devienne profitable de
rendre cette variable positive.
• indique la pénalité (par unité) à payer pour forcer la variable dans la solution.
• équivaux à l’écart de la contrainte dual associé à cette variable.

Les coûts réduits ne sont valables que dans un intervalle spécifié dans l’analyse de sensibilité (range analysis).
Transformation

Primal Dual
Max 𝑏! 𝜆
Min 𝑐!𝑥
s.t.:
s.t.:
𝐴! 𝜆 ≤ 𝑐
𝐴𝑥 ≥ 𝑏
𝜆 ≥ 0
𝑥 ≥ 0

Min 𝑐 ! 𝑥 Max 𝑏! 𝜆
s.t.: s.t.:
𝐴𝑥 = 𝑏 𝐴! 𝜆 ≤ 𝑐
𝑥 ≥ 0 𝜆 (libre)
Transformation
Résumé

max min
𝑖 12 contrainte = 𝑦3 ∈ ℝ
𝑥4 ∈ ℝ 𝑗12 contrainte =
𝑥4 ≥ 0 𝑗12 contrainte ≥
𝑥4 ≤ 0 𝑗12 contrainte ≤
𝑖 12 contrainte ≤ 𝑦3 ≥ 0
𝑖 12 contrainte ≥ 𝑦3 ≤ 0