4.
Dualité en Programmation Linéaire
4.1. Introduction :
La notion de dualité est un aspect très important de la programmation linéaire. Elle
fut développé par John Newmann en 1947 où il a démontré qu’à tout modèle linéaire
qu’on appelle programme primal (P) correspond un autre appelé programme dual (D)
et leurs fonctions objectifs sont égales. Depuis, cette notion a suscité une intention
très particulière dans plusieurs domaines tels que optimisation non convexe,
programmation non linéaire, théorie des jeux ...
D’un point de vue théorique, la notion de dualité permet : En résolvant le dual
d’obtenir également la solution optimale du primal.
4.2. Propriétés et règles de construction du dual
Théorème 1
Le problème dual du problème dual est le problème primal.
4.2.1. Règles de construction
Les différentes transformations sont résumées dans le tableau suivant :
34
Exemple :
Primal Dual
Max 5𝑥 + 12𝑥 + 4𝑥 min 10𝑦 + 8𝑦
⎧ 𝑥 + 2𝑥 + 𝑥 ≤ 10 ⎧
⎪ ⎪𝑦 + 2𝑦 ≥ 5
𝑆𝐶 2𝑥 −𝑥 + 3𝑥 = 8 𝑆𝐶 2𝑦 − 𝑦 ≥ 12
⎨ ⎨ 𝑦 + 3𝑦 ≥ 4
⎪ ⎪
⎩ 𝑥 ,𝑥 ,𝑥 ,≥ 0 ⎩ 𝑦 ≥0
Max 3𝑥 + 𝑥 − 2𝑥 min 10𝑦 + 7𝑦 + 8𝑦
⎧ 𝑥 + 2𝑥 ≥ 10 ⎧
⎪ ⎪𝑦 + 3𝑦 + 𝑦 = 10
𝑆𝐶 3𝑥 − 𝑥 + 𝑥 =7 𝑆𝐶 2𝑦 − 𝑦 ≥7
⎨𝑥 + 3𝑥 ≤ 8 ⎨ 𝑦 + 3𝑦 ≥8
⎪ ⎪
⎩ 𝑥 ,𝑥 ,≥ 0 ⎩ 𝑦 ≤ 0, 𝑦 𝜖𝑅, 𝑦 ≥0
Max 2𝑥 + 𝑥 min 10𝑦 + 7𝑦 + 8𝑦
⎧ 𝑥 − 2𝑥 ≤ 2 ⎧ 𝑦 + 3𝑦 + 𝑦 = 10
⎪ ⎪
𝑆𝐶 5𝑥 + 𝑥 ≥ 9 𝑆𝐶 2𝑦 − 𝑦 ≥7
⎨−3𝑥 + 6𝑥 = 7 ⎨ 𝑦 + 3𝑦 ≥8
⎪ ⎪
⎩ 𝑥 ,𝑥 ≥ 0 ⎩ 𝑦 ≤ 0, 𝑦 𝜖𝑅, 𝑦 ≥0
4.3. Relations primal/dual
Théorème (Dualité faible).
Considérons la paire primale-duale :
- Si x est une solution admissible du primal et y une solution admissible du
dual, alors.
𝑐 𝑥≤𝑏 𝑦
- S’il y a égalité, alors x est une solution optimale du primal et y une
solution optimale du dual.
35
Théorème (Dualité forte).
Considérons la paire primale-duale :
- Si le primal et le dual admettent tous les deux une solution admissible, ils
ont tous deux une solution optimale finie et la même valeur objectif
optimale.
- Si le primal (dual) est non borné, le dual (primal) n’admet pas de solution
admissible.
Théorème (complémentarité).
Considérons la paire primale-duale :
Si x est une solution optimale du primal et y une solution optimale du dual,
alors
𝑥 𝑎 𝑦−𝑐 =0
où ai est la i-ème colonne de A.
En d’autres termes :
𝑥 ≥ 0⇒𝑎 𝑦 = 𝑐
𝑎 𝑦 > 𝑐 ⇒𝑥 = 0
36
Exemple (Résolution du dual par les règles de complémentarité).
4.4. Interprétation économique de la dualité
– La forme canonique d’un programme linéaire peut être interprétée comme un
problème d’allocation de ressources.
– Paire primale-duale :
37
Interprétation de la dualité faible
Interprétation de la dualité forte :
Le profit maximal est atteint si les ressources ont été exploitées complètement, i.e.
jusqu’à épuisement de leur valeur.
4.5. Algorithme dual du simplexe :
4.5.1. Tableau initial
Toutes les variables
A = (aij)i,j bi
Matrice des coefficients vecteur des
valeurs du
des contraintes du programme seconds
standard membre
cj coefficient de la fonction objectif
correspond aux variables
4.5.2. Algorithme
1. Mettre le PL sous forme standard.
2. Vérifier le critère d’optimalité: si tous les bi sont positifs ou nuls, stop.
Sinon
3. Choisir la variable xj sortante, min{𝑏 }.
4. Déterminer la variable de entrante: max ,𝑎 < 0
5. Effectuer un pivot et déterminer une nouvelle solution de base réalisable.
Retour à l’étape 2.
38
Exemple
1
Résoudre le PL suivant à l’aide de la méthode dual du simplexe :
Min 120𝑥 + 60𝑥
3𝑥 +𝑥 ≥ 150
⎧ 4𝑥 + 5𝑥 ≥ 440
⎪
𝑆𝐶 3𝑥 + 2𝑥 ≥ 24
⎨
⎪
⎩ 𝑥 ,𝑥 ≥ 0
Sous forme standard :
Min (120𝑥 + 60𝑥 )
−3𝑥 −𝑥 ≤ −150
⎧ −4𝑥 − 5𝑥 ≤ − 440
⎪
𝑆𝐶 −3𝑥 − 2𝑥 ≤ − 24
⎨
⎪
⎩ 𝑥 ,𝑥 ≥ 0
Min (120𝑥 + 60𝑥 )
−3𝑥 − 𝑥 + 𝑥 = − 150
⎧ −4𝑥 − 5𝑥 + 𝑥 = − 440
⎪
𝑆𝐶 −3𝑥 − 2𝑥 + 𝑥 = − 24
⎨
⎪
⎩ 𝑥 ,𝑥 ,𝑥 ,𝑥 ,𝑥 ≥ 0
Premier tableau :
𝑥 𝑥 𝑥 𝑥 𝑥 𝑏
-3 -1 1 0 0 -15
-1 -5 0 1 0 -20
-3 -2 0 0 1 -24
Z 120 60 0 0 0 0
39
Itération 1:
∗ 𝑀𝑖𝑛 𝑏 = 𝑀𝑖𝑛{−15, −20, −24} = −24
Donc la variable sortant de la base est la variable 𝑥 (ligne pivot)
𝑥 𝑥 𝑥 𝑥 𝑥 𝑏
L1 -3 -1 1 0 0 -15
L2 -1 -5 0 1 0 -20
L3 -3 -2 0 0 1 -24
L4 120 60 0 0 0 0
*Max = , = {−40, −30} = −30
Alors la variable entrante est la variable 𝑥
𝑥 𝑥 𝑥 𝑥 𝑥 𝑏
L1- -3 -1 1 0 0 -15
(1/2)L3
L2- -1 -5 0 1 0 -20
(5/2)L3
-1/2L3 -3 -2 0 0 1 -24
L4+30L3 120 60 0 0 0 0
𝑥 𝑥 𝑥 𝑥 𝑥 𝑏
-3/2 0 1 0 -1/2 -3
13/2 0 0 1 -5/2 40
3/2 1 0 0 -1/2 12
30 0 0 0 30 720
Itération 2:
∗ 𝑀𝑖𝑛 𝑏 = 𝑀𝑖𝑛{−3} = −3
Donc la variable sortant de la base est la variable 𝑥 (ligne pivot)
𝑥 𝑥 𝑥 𝑥 𝑥 𝑏
L1 -3/2 0 1 0 -1/2 -3
L2 13/2 0 0 1 -5/2 40
L3 3/2 1 0 0 -1/2 12
L4 30 0 0 0 30 720
*Max = , = {−20, −60} = −20
/ /
40
Alors la variable entrante est la variable 𝑥
𝑥 𝑥 𝑥 𝑥 𝑥 𝑏
-2/3L1 -3/2 0 1 0 -1/2 -3
L2+13/3L1 13/2 0 0 1 -5/2 40
L3+L1 3/2 1 0 0 -1/2 12
L4+20L1 30 0 0 0 30 720
𝑥 𝑥 𝑥 𝑥 𝑥 𝑏
1 0 -2/3 0 1/3 2
0 0 13/3 1 -28/6 27
0 1 1 0 -1 9
0 0 20 0 20 780
Stop
La solution optimale est :
𝑥 ∗ = 2 , et 𝑥 ∗ = 9 et 𝑍 ∗ = 780
41