Chapitre 3 : La dualité
1) Définition
À tout programme linéaire appeler PRIMAL on peut lui faire correspondre un autre
programme linéaire appeler DUAL. En effet, soit le PL suivant :
𝑀𝑎𝑥 𝑍𝑥 = 𝐶 𝑡 𝑋
(3.1) { 𝑠/𝑐
𝐴𝑋 ≤ 𝐵
𝑋≥0
Appelons ce PL un primal, alors son dual est aussi un PL qui s'écrit comme suit :
𝑀𝑖𝑛 𝑍𝑦 = 𝐵 𝑡 𝑌
(3.2) { 𝑠/𝑐
𝑡
𝐴𝑌≥C
𝑌≥0
Avec une écriture plus claire, le primal et le dual peuvent s'écrire comme suit :
PRIMAL DUAL
𝑛 𝑚
𝑀𝑎𝑥 𝑍𝑥 = ∑ 𝑐𝑗 𝑥𝑗 𝑀𝑖𝑛 𝑍𝑦 = ∑ 𝑏𝑖 𝑦𝑖
𝑗=1 𝑖=1
𝑠/𝑐 𝑠/𝑐
𝑛 𝑚
∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 , 𝑝𝑜𝑢𝑟 𝑖 = 1, … , 𝑚 ∑ 𝑎𝑖𝑗 𝑦𝑖 ≥ 𝑐𝑗 𝑝𝑜𝑢𝑟 𝑗 = 1, … , 𝑛
𝑗=1 𝑖=1
𝑥𝑗 ≥ 0 𝑝𝑜𝑢𝑟 𝑗 = 1, … , 𝑛 𝑦𝑖 ≥ 0 𝑝𝑜𝑢𝑟 𝑖 = 1, … , 𝑚
Étant donné le primal et le dual ci-dessus les formes standards en fonction des variables
principales et écarts s'écrivent comme suit :
PRIMAL DUAL
𝑀𝑎𝑥 𝑍𝑥 = Cpt 𝑋𝑝 + Cet 𝑋𝑒 𝑀𝑖𝑛 𝑍𝑦 = Bpt 𝑌𝑝 + Bet 𝑌𝑒
(3.3) s/c ⇒ (3.4) 𝑠/𝑐
𝐴𝑝 𝑋𝑝 + 𝐴𝑒 𝑋𝑒 = 𝐵 𝐴𝑝 𝑌𝑝 − 𝐴𝑡𝑒 𝑌𝑒 = C
𝑡
{ 𝑋𝑝 , 𝑋𝑒 ≥ 0 { 𝑌𝑝 , 𝑌𝑒 ≥ 0
Avec une écriture plus détaillée le deux PL s’écrit :
1
PRIMAL DUAL
𝑛 𝑚 𝑚 𝑛
𝑀𝑎𝑥 𝑍𝑥 = ∑ 𝑐𝑗 𝑥𝑗 + ∑ 0. 𝑒𝑖 𝑀𝑖𝑛 𝑍𝑦 = ∑ 𝑏𝑖 𝑦𝑖 + ∑ 0. 𝑒𝑗′
𝑗=1 𝑖=1 𝑖=1 𝑗=1
𝑠/𝑐 𝑠/𝑐
𝑛 𝑚
∑ 𝑎𝑖𝑗 𝑥𝑗 + 𝑒𝑖 = 𝑏𝑖 , 𝑝𝑜𝑢𝑟 𝑖 = 1, … , 𝑚 ∑ 𝑎𝑖𝑗 𝑦𝑖 − 𝑒𝑗′ = 𝑐𝑗 , 𝑝𝑜𝑢𝑟 𝑗 = 1, … , 𝑛
𝑗=1 𝑖=1
𝑥𝑗 ≥ 0 𝑝𝑜𝑢𝑟 𝑗 = 1, … , 𝑛 𝑦𝑖 ≥ 0 𝑝𝑜𝑢𝑟 𝑖 = 1, … , 𝑚
𝑒𝑖 ≥ 0 𝑝𝑜𝑢𝑟 𝑖 = 1, … , 𝑚 𝑒𝑗′ ≥ 0 𝑝𝑜𝑢𝑟 𝑗 = 1, … , 𝑛
D'après les deux PL Primal et Dual ci-dessus nous pouvons remarquer que :
- Puisque tous les PL peuvent être ramenés à des programmes canoniques après les
changements éventuels, nous pouvons donc faire ces transformations au départ,
ensuite nous construisons le dual en appliquant les définitions données ci-dessus.
- Résumons le passage du primal au dual et réciproquement dans le tableau suivant :
Primal (Dual) Dual (Primal)
1) Le PL est une Maximisation 1) Le PL est une Minimisation
2) Le vecteur des coefficients (𝐶) 2) Le vecteur du second membre des
de la fonction objectif 𝑍𝑥 contraintes
3) Le vecteur du second membre 3) Le vecteur des coefficients de la
des contraintes (𝐵) fonction objectif 𝑍𝑦
4) La matrice 𝐴 4) La transposée de 𝐴: (𝐴𝑡 )
5) Inégalité de type (≤) 5) Inégalité de type (≥)
6) Une contrainte de type 6) La variable duale correspondante est
inégalité (≤ 𝑜𝑢 ≥) non négative (≥ 0)
7) Une contrainte de type égalité 7) La variable duale correspondante est
de signe quelconque
8) Une variable de signe 8) La contrainte duale correspondante est
quelconque de type égalité.
9) Une variable positive ou nulle 9) La contrainte duale correspondante est
type inégalité (≥)en cas de Min.
l'inverse (≤)en cas de Max.
10) On a 𝑛 variables principales 10) On a 𝑛 contraintes duales
11) On a 𝑚 contraintes 11) On a 𝑚 variables principales
2
Exemple :
𝑀𝑎𝑥 𝑍𝑥 = 5 𝑥1 + 2𝑥2 + 3𝑥3 𝑀𝑎𝑥 𝑍𝑥 = 5 𝑥1 + 2𝑥2 + 3𝑥3
𝑠/𝑐 𝑠/𝑐
2𝑥1 + 2𝑥2 + 𝑥3 ≤ 2 2𝑥1 + 2𝑥2 + 𝑥3 ≤ 2
3𝑥1 + 4𝑥2 ≥3 ⇔ −3𝑥1 − 4𝑥2 ≤ −3
𝑥1 + 3𝑥2 + 𝑥3 = 5 𝑥1 + 3𝑥2 + 𝑥3 = 5
𝑥1 𝑞𝑙𝑞 , 𝑥2 , 𝑥3 ≥ 0 𝑥1 𝑞𝑙𝑞 , 𝑥2 , 𝑥3 ≥ 0
{ 𝐹𝑜𝑟𝑚𝑒 𝐶𝑎𝑛𝑜𝑛𝑖𝑞𝑢𝑒 {𝐹𝑜𝑟𝑚𝑒 𝑐𝑎𝑛𝑜𝑛𝑖𝑞𝑢𝑒 𝑡𝑟𝑎𝑛𝑠𝑓𝑜𝑟𝑚é𝑒
Remarquons que la troisième contrainte est de type égalité, alors avant de passer au dual
nous pouvons l'écrire sous forme de deux contraintes. L'une de type ≤ et l'autre de type ≥ et
cette dernière va être transformée par la suit en une de type ≤ de la manière suivante :
𝑥 + 3𝑥2 + 𝑥3 ≤ 5 𝑥 + 3𝑥2 + 𝑥3 ≤ 5
𝑥1 + 3𝑥2 + 𝑥3 = 5 ⇔ { 1 ⇔{ 1
𝑥1 + 3𝑥2 + 𝑥3 ≥ 5 −𝑥1 − 3𝑥2 − 𝑥3 ≤ −5
Mais d'après le point (6) du résumé, nous pouvons garder cette contrainte telle quelle et la
variable duale correspondante sera de signe quelconque.
Le PL dual se construit comme suit :
𝑀𝑎𝑥 𝑍𝑥 = 5 𝑥1 + 2𝑥2 + 3𝑥3
𝑠/𝑐
2𝑥1 + 2𝑥2 + 𝑥3 ≤ 2 ⟵ 𝑦1 ≥ 0
−3𝑥1 − 4𝑥2 ≤ −3 ⟵ 𝑦2 ≥ 0
𝑥1 + 3𝑥2 + 𝑥3 =5 ⟵ 𝑦3 𝑞𝑙𝑞
𝑥1 𝑞𝑙𝑞 , 𝑥2 , 𝑥3 ≥ 0
↑ ↑ ↑
1𝑒𝑟𝑒 2é𝑚𝑒 3é𝑚𝑒
𝑐𝑜𝑛𝑡. 𝑐𝑜𝑛𝑡. 𝑐𝑜𝑛𝑡.
𝑡𝑦𝑝𝑒 𝑡𝑦𝑝𝑒 𝑡𝑦𝑝𝑒
(=) (≥) (≥)
Le dual correspondant est :
𝑀𝑖𝑛 𝑍𝑦 = 2𝑦1 − 3𝑦2 + 5𝑦3
𝑠/𝑐
2𝑦1 − 3𝑦2 + 𝑦3 =5
2𝑦1 − 4𝑦2 + 3 𝑦3 ≥2
𝑦1 + 𝑦3 ≥3
{ 𝑦1 , 𝑦2 ≥ 0 , 𝑦3 𝑞𝑙𝑞
3
2) Théorèmes généraux de la dualité
Théorème 1 :
Le dual de dual est le primal.
Démonstration :
Primal Dual Dual de Dual = Primal
𝑡 𝑡
𝑀𝑎𝑥 𝑍𝑥 = 𝐶 𝑋 𝑀𝑖𝑛 𝑍 𝑦 = 𝐵 𝑌 𝑀𝑎𝑥 𝑍𝑥 = 𝐶 𝑡 𝑋
𝑠/𝑐 ⇒ 𝑠/𝑐 ⇒ 𝑠/𝑐
𝐴𝑋 ≤ 𝐵 𝑡 𝐴𝑋 ≤ 𝐵
𝐴 𝑌≥C
𝑋≥0 𝑌≥0 𝑋≥0
Théorème 2 :
Considérons le primal et le dual donné ci-dessus. Supposons qu'il existe une solution réalisable
du primal 𝑋 et une solution réalisable du dual 𝑌 alors : 𝑍𝑥 ≤ 𝑍𝑦 .
Démonstration :
Soient le primal et le dual suivant :
Primal Dual
𝑀𝑎𝑥 𝑍𝑥 = 𝐶 𝑡 𝑋 𝑀𝑖𝑛 𝑍𝑦 = 𝐵 𝑡 𝑌
𝑠/𝑐 ⇒ 𝑠/𝑐
𝐴𝑋 ≤ 𝐵 𝑡
𝐴 𝑌≥C
𝑋≥0 𝑌≥0
On a :
D'après le système des contraintes du primal: 𝐴𝑋 ≤ 𝐵 ⇔ 𝑌 𝑡 𝐴𝑋 ≤ 𝑌 𝑡 𝐵 = 𝐵 𝑡 𝑌 = 𝑍𝑦 .
De même, le système des contraintes de dual: 𝐴𝑡 𝑌 ≥ C ⇔ X t 𝐴𝑡 𝑌 ≥ X t C = 𝐶 𝑡 𝑋 = 𝑍𝑥 .
Alors, 𝑍𝑥 ≤ X t 𝐴𝑡 𝑌 = 𝑌 𝑡 𝐴𝑋 ≤ 𝑍𝑦 ⇔ 𝑍𝑥 ≤ 𝑍𝑦 .
Corolaire :
Sous les mêmes hypothèses données plus haut nous avons :
𝑍𝑥 ≤ 𝑍𝑥∗ ≤ 𝑍𝑦 ≤ 𝑍𝑦∗ Avec 𝑍𝑥∗ = 𝑀𝑎𝑥𝑍𝑥 𝑒𝑡 𝑍𝑥∗ = 𝑀𝑖𝑛𝑍𝑦
Démonstration :
4
𝑍𝑥∗ = 𝑀𝑎𝑥𝑍𝑥 ⇒ 𝑍𝑥 ≤ 𝑍𝑥∗ vraie par définition,
𝑍𝑥∗ = 𝑀𝑖𝑛𝑍𝑦 ⇒ 𝑍𝑦 ≤ 𝑍𝑦∗ vraie par définition,
D'après le théorème 2 on a 𝑍𝑥 ≤ 𝑍𝑦 ∀ 𝑋 𝑒𝑡 𝑌 . Alors comme cas particulier 𝑍𝑥∗ ≤ 𝑍𝑦∗ . D’où
𝑍𝑥 ≤ 𝑍𝑥∗ , 𝑍𝑦 ≤ 𝑍𝑦∗ 𝑒𝑡 𝑍𝑥∗ ≤ 𝑍𝑦∗ ⇒ 𝑍𝑥 ≤ 𝑍𝑥∗ ≤ 𝑍𝑦 ≤ 𝑍𝑦∗ .
Théorème 3 :
Sous les mêmes hypothèses du théorème 2, on peut écrire qu'à l'optimalité les deux fonctions
économiques sont égales : 𝑍𝑥∗ = 𝑍𝑦∗ .
Démonstration :
Écrivons le primal et le dual sous leurs formes standards et en fonction des variables
principales et des variables d'écarts.
Primal Dual
t t
𝑀𝑎𝑥 𝑍𝑥 = Cp 𝑋𝑝 + Ce 𝑋𝑒 𝑀𝑖𝑛 𝑍𝑦 = Bpt 𝑌𝑝 + Bet 𝑌𝑒
𝑠/𝑐 𝑠/𝑐
⇒
𝐴𝑝 𝑋𝑝 + 𝐴𝑒 𝑋𝑒 = 𝐵𝑝 Ap Yp − Ate Ye = Cp
t
𝑋𝑝 ≥ 0 Yp ≥ 0
𝑋𝑒 ≥ 0 Ye ≥ 0
Le dernier tableau du simplexe du primal est :
𝐶𝑝𝑡 𝐶𝑒𝑡
Solutions
𝑋𝑝 𝑋𝑒
𝐶𝐼 . 𝑋𝐼 A−1
I 𝐴𝑝 A−1
I 𝐴𝑒 A−1
I 𝐵𝑝
δj (𝐶𝑝𝑡 − CIt A−1
I 𝐴𝑝 ) (𝐶𝑒𝑡 − CIt A−1
I 𝐴𝑒 ) 𝑍𝑥 = 𝐶𝐼𝑡 A−1
I 𝐵𝑝
−δj CIt A−1 𝑡
I 𝐴𝑝 − 𝐶𝑝 CIt A−1
I
Rappelons que : 𝐶𝑒𝑡 = 0, B𝑒𝑡 = 0, 𝐴𝑒 = 𝐼m et Ate = 𝐼n
Le système des contraintes du dual est :
Atp Yp − Ate Ye = Cp ⇔ Ypt Ap − Yet Ae = Cpt .
Prenons
Ypt = CIt A−1
I et Yet = CIt A−1 𝑡
I 𝐴𝑝 − 𝐶𝑝
Vérifions que les deux valeurs vérifient le système des contraintes : Le premier membre de ce
système des contraintes sera égal à
CIt A−1 t −1 𝑡 t −1 t −1
I Ap − (CI AI 𝐴𝑝 − 𝐶𝑝 )Ae = CI AI Ap − CI AI Ap + Cp = Cp
t t
qui est égal au second membre de ce système ⇒ Yp et Ye sont deux solutions réalisables de
dual.
5
𝑍𝑦 = Bpt 𝑌𝑝 + Bet 𝑌𝑒 = Bpt 𝑌𝑝 = Bpt (CIt A−1 𝑡 −1 𝑡 −1
I ) = 𝐶𝐼 AI 𝐵𝑝 = 𝐶𝐼 AI 𝐵
Or 𝑍𝑥∗ = 𝐶𝐼𝑡 A−1 ∗ ∗ ∗ 𝑡 −1 ∗
I 𝐵 et d'après le corolaire 𝑍𝑥 ≤ 𝑍𝑥 ≤ 𝑍𝑦 ≤ 𝑍𝑦 . D’où 𝑍𝑥 = 𝐶𝐼 AI 𝐵 = 𝑍𝑦
À l'optimalité les deux fonctions économiques sont égales.
Théorème 4 : théorème des écarts complémentaires.
Sous les mêmes hypothèses que les autres théorèmes, à l'optimalité nous avons :
𝑌 ∗𝑡 (𝐵 − 𝐴𝑋 ∗ ) = 0 𝑒𝑡 𝑋 ∗𝑡 (𝐴𝑡 𝑌 ∗ − 𝐶) = 0 où 𝑋 ∗ 𝑒𝑡 𝑌 ∗ les solutions optimales du primal et
de dual respectivement. On peut aussi utiliser les indices p et e alors on aura :
𝑌𝑝∗𝑡 (𝐵 − 𝐴𝑝 𝑋𝑝∗ ) = 0𝑌𝑝∗𝑡 𝑋𝑒∗ = 0
{ ∗𝑡 𝑡 ∗ ⇔ { ∗𝑡 ∗
𝑋𝑝 (𝐴𝑝 𝑌𝑝 − 𝐶) = 0 𝑋𝑝 𝑌𝑒 = 0
Démonstration :
Nous avons :
(𝐵 − 𝐴𝑋 ∗ ) ≥ 0 𝑒𝑡 𝑌 ∗ ≥ 0 ⇒ 𝑌 ∗𝑡 (𝐵 − 𝐴𝑋 ∗ ) ≥ 0
De même :
(𝐴𝑡 𝑌 ∗ − 𝐶) ≥ 0 𝑒𝑡 𝑋 ∗ ≥ 0 ⇒ 𝑋 ∗𝑡 (𝐴𝑡 𝑌 ∗ − 𝐶) ≥ 0
La somme de deux termes est :
𝑌 ∗𝑡 (𝐵 − 𝐴𝑋 ∗ ) + 𝑋 ∗𝑡 (𝐴𝑡 𝑌 ∗ − 𝐶) = 𝑌 ∗𝑡 𝐵 − 𝑌 ∗𝑡 𝐴𝑋 ∗ + 𝑋 ∗𝑡 𝐴𝑡 𝑌 ∗ − 𝑋 ∗𝑡 𝐶
= 𝐵 𝑡 𝑌 ∗ − 𝑌 ∗𝑡 𝐴𝑋 ∗ + 𝑌 ∗𝑡 𝐴𝑋 ∗ − 𝐶 𝑡 𝑋 ∗ = 𝐵 𝑡 𝑌 ∗ − 𝐶 𝑡 𝑋 ∗ = 𝑍𝑦∗ − 𝑍𝑥∗ = 0
Si la somme de deux termes positifs ou nuls est nulle, alors chaque terme est nul. Donc :
𝑌 ∗𝑡 (𝐵 − 𝐴𝑋 ∗ ) = 0 𝑒𝑡 𝑋 ∗𝑡 (𝐴𝑡 𝑌 ∗ − 𝐶) = 0 ⇔ 𝑌𝑝∗𝑡 𝑋𝑒∗ = 0 𝑒𝑡 𝑋𝑝∗𝑡 𝑌𝑒∗ = 0.
Détaillons encore ces relations :
Désignons par 𝑥𝑗 , 𝑗 = 1, … , 𝑛 les variables principales du primal et par 𝑒𝑗′ , 𝑗 = 1, … , 𝑛 les
variables d'écarts de dual.
𝑦𝑖 , 𝑖 = 1, … , 𝑚 les variables principales du dual et 𝑒𝑖 , 𝑖 = 1, … , 𝑚 les variables d'écarts du
primal.
𝑌𝑝∗𝑡 𝑋𝑒∗ = 0 ⇔ ∑𝑚 ∗ ∗ ∗ ∗ ∗ ∗
𝑖=1 𝑦𝑖 𝑒𝑖 = 0 et puisque 𝑦𝑖 ≥ 0 𝑒𝑡 𝑒𝑖 ≥ 0 ainsi que 𝑦𝑖 𝑒𝑖 ≥ 0 et la somme
est nulle, alors chaque terme 𝑦𝑖∗ 𝑒𝑖∗ = 0, ∀ 𝑖 = 1, … , 𝑚.
De même on a:
𝑋𝑝∗𝑡 𝑌𝑒∗ = 0 ⇔ ∑𝑛𝑗=1 𝑥𝑗∗ 𝑒𝑗′∗ = 0 et puisque 𝑥𝑗∗ ≥ 0 𝑒𝑡 𝑒𝑗′∗ ≥ 0 ainsi que 𝑥𝑗∗ 𝑒𝑗′∗ ≥ 0 et la somme
est nulle, alors chaque terme 𝑥𝑗∗ 𝑒𝑗′∗ = 0, ∀ 𝑗 = 1, … , 𝑛.
D'après ce qui précède, on peut dire qu'à l'optimalité le produit d'une variable principale
du primal (dual) et la variable d'écart correspondante (primal) est nul, ce qui entraine
qu'au moins l'une des variables est nulle à l'optimalité.
6
Exemple :
Une entreprise veut produire deux produits P1 et P2. Le prix unitaire de P1 est 800 u.m et celui
de P2 est 600 u.m. La fabrication de ces deux produits nécessite l'utilisation de 3 matières
premières M1, M2 et M3. La production unitaire de P1 requiert 5 unités de M1, 2 unités de
M2 et 1 unité de M3. Une unité de P2 demande 3 unités de chacune des 3 matières premières.
Les quantités disponibles de ces matières premières M1, M2 et M2 sont, respectivement 30,
24 et 18.
Travail à faire :
1) Formuler un programme linéaire qui maximise le chiffre d'affaire de cette entreprise.
2) Résoudre par le simplexe le PL trouvé.
3) Écrire le dual du PL formalisé
4) Donner le dernier tableau du simplexe du dual déduit de celui du primal.
5) Donner la signification économique des variables et des contraintes duales ainsi que la
fonction économique.
Réponse :
1) Soient 𝑥1 𝑒𝑡 𝑥2 les quantités produites de P1 et P2 respectivement.
On a trois contraintes associées aux matières premières M1, M2 et M3. La fonction
objectif est la maximisation du chiffre d'affaire de l'entreprise. Donc la PL sera le suivant :
𝑀𝑎𝑥 𝑍𝑥 = 800 𝑥1 + 600𝑥2
𝑠/𝑐
5𝑥1 + 3𝑥2 ≤ 30
2𝑥1 + 3𝑥2 ≤ 24
𝑥1 + 3𝑥2 ≤ 18
{ 𝑥1 , 𝑥2 ≥ 0
2) Résolution par le simplexe.
𝑀𝑎𝑥 𝑍𝑥 = 800 𝑥1 + 600𝑥2 𝑀𝑖𝑛 𝑍𝑥 = 800 𝑥1 + 600𝑥2 + 0(𝑒1 + 𝑒2 + 𝑒3 )
𝑠/𝑐 𝑠/𝑐
5𝑥1 + 3𝑥2 ≤ 30 5𝑥1 + 3𝑥2 + 𝑒1 = 30
2𝑥1 + 3𝑥2 ≤ 24 ⇒ 2𝑥1 + 3𝑥2 + 𝑒2 = 24
𝑥1 + 3𝑥2 ≤ 18 𝑥1 + 3𝑥2 + 𝑒3 = 18
𝑥1 , 𝑥2 ≥ 0 𝑥1 , 𝑥2 , ≥ 0
{ 𝑓𝑜𝑟𝑚𝑒 𝑐𝑎𝑛𝑜𝑛𝑖𝑞𝑢𝑒 { 𝑓𝑜𝑟𝑚𝑒 𝑠𝑡𝑎𝑛𝑑𝑎𝑟𝑑
Le tableau initial est :
7
800 600 0 0 0
𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 RHS
0 𝑒1 5 3 1 0 0 30 ℓ1 = 6 → 𝑉𝑆
0 𝑒2 2 3 0 2 0 24 ℓ2 = 12
0 𝑒3 1 3 0 0 1 18 ℓ3 =18
𝛿𝑗 800 600 0 0 0 Z=0
↑
𝑉𝑒
800 600 0 0 0
𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 RHS
800 𝑥1 1 3/5 1/5 0 0 6 ℓ1 = 10
0 𝑒2 0 9/5 -2/5 1 0 12 ℓ2= 20/3
ℓ3 = 5
0 𝑒3 0 12/5 -1/5 0 1 12
→ 𝑉𝑆
𝛿𝑗 0 120 -160 0 0 Z=4800
↑
𝑉𝑒
800 600 0 0 0
𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 RHS
800 𝑥1 1 0 1/4 0 -1/4 3
0 𝑒2 0 0 -1/4 1 -3/4 3
600 𝑥2 0 1 -1/12 0 5/12 5
𝛿𝑗 0 0 -150 0 -50 Z=5400
La solution optimale est :
𝑥1∗ = 𝑒2∗ = 3 𝑒𝑡 𝑥2∗ = 5
{ 𝑒1∗ = 𝑒3∗ = 0
𝑍𝑥∗ = 5400
3) Le dual du programme linéaire formalisé est :
𝑀𝑖𝑛 𝑍𝑦 = 30𝑦1 + 24𝑦2 + 18𝑦3
𝑠/𝑐
5𝑦1 + 2𝑦2 + 𝑦3 ≥ 800
3𝑦1 + 3𝑦2 + 3 𝑦3 ≥ 600
{ 𝑦1 , 𝑦2 , 𝑦3 ≥ 0
8
4) La déduction du dernier tableau du dual à partir de celui du primal se fait comme
suit :
𝒆′𝟏 𝒆′𝟐 𝒚𝟏 𝒚𝟐 𝒚𝟑 RHS=valeurs marginales
𝑽𝑯𝑩 𝑽𝑩 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 des VHB de dual
VHB 𝒆′𝟏 𝑥1 1 0 1/4 0 -1/4 3
de 𝒚𝟐 𝑒2 0 0 -1/4 1 -3/4 3
dual
𝒆′𝟐 𝑥2 0 1 -1/12 0 5/12 5
𝛿𝑗 0 0 -150 0 -50 𝑍𝑥 = 5400
−𝜹𝒋 0 0 150 0 50 𝒁𝒚 = 𝟓𝟒𝟎𝟎
Les valeurs des variables duales
- Les éléments des colonnes des variables de bases sont nuls sauf l'élément pivot qui
doit avoir la valeur 1.
- Les cases d'intersection entre les variables de bases et hors bases doivent être les
opposées de celles dans le tableau du primal.
Le dernier tableau du dual est alors :
30 24 18 0 0
𝑦1 𝑦2 𝑦3 𝑒1′ 𝑒2′ RHS
30 𝑦1 1 1/4 0 -1/4 1/12 150
18 𝑦3 0 3/4 1 1/4 -5/12 50
𝛿𝑗 0 3 0 3 5 Z=5400
𝑦1∗ = 150 𝑒𝑡 𝑦3∗ = 50
La solution optimale est : { 𝑦2∗ = 𝑒1′∗ = 𝑒2′∗ = 0
𝑍𝑦∗ = 5400
5)
- Interprétation des variables duales :
Δ𝑍
Les 𝑦𝑖 = Δ𝑏 , 𝑖 = 1,2,3 sont les valeurs marginales rapportées par unité supplémentaire des
𝑖
matières premières. Ces variables sont appelées aussi les prix de références ou les prix
d'ombres des matières premières. On constate que la première contrainte correspondante à
la matière première M1 est saturée (on a utilisé les 30 unités disponibles car 𝑒∗1 = 0) ainsi que
la troisième contrainte. Par contre la deuxième n'est pas saturée (on n'a pas utilisé la totalité
de la ressource disponible : 𝑒∗2 = 5 ).
9
Les matières premières M1 et M3 sont rares, alors une unité supplémentaire de ces matières
premières a un prix (une unité de M1 coûte ou rapporte
∗ ∗ ∗
𝑦1 = 150 u. m. c.à.d. que la fonction économique 𝑍𝑥 et 𝑍𝑦 augmente de 150 u.m) et une
unité supplémentaire de M3 rapporte ou coûte 𝑦3∗ = 50 u. m. c.à.d. que la fonction
économique 𝑍𝑥∗ et 𝑍𝑦∗ augmente de 50 um). Cependant, la matière première M2 est supposée
abondante, alors une unité supplémentaire n'aura pas de prix 𝑦2∗ = 0 u. m).
- La signification des contraintes duales :
Puisque nous avons supposé que les variables duales soient les prix de référence des matières
premières (les coûts d'achat des matières premières). Alors la première contrainte duale
signifie que le coût de la production d'une unité du produit P1 (indiqué par le premier membre
de cette contrainte) est supérieur ou égale à son prix de vente (indiqué par le second membre
de cette contrainte).
La deuxième contrainte indique que le coût de la production unitaire du produit P2 est
supérieur ou égale à son prix de vente unitaire.
Noter que le prix de vente sur le marché est fixé selon l'offre et la demande c.à.d. par les
entreprises les plus performantes et les plus compétitives. Si le coût unitaire de la production
égalise le prix de vente unitaire, la condition d'équilibre est atteinte (le profit est nul).
- La fonction économique de duale a pour objectif la minimisation du coût total de la
production des produits P1 et P2.
Remarque :
Le passage d’une solution d'un PL de minimisation (par exemple le dual) à celle d'un PL de
maximisation (son primal) se fait comme suit :
Reprenons l'exemple précédent et supposons que nous avons le dernier tableau de dual (qui
est un PL de minimisation) et que nous voulons déduire celui de son primal (qui est un PL de
maximisation). Ce passage se fait comme suit :
𝒆𝟏 𝒆𝟐 𝒆𝟑 𝒙𝟏 𝒙𝟐 -RHS=
valeurs
RHS marginales
𝑿̅𝑰 𝑌𝐼 𝑦1 𝑦2 𝑦3 𝑒1′ 𝑒2′ des VHB
primales
VHB 𝒆𝟏 𝑦1 1 1/4 0 -1/4 1/12 150 -150
du 𝒆𝟑 𝑦3 -50
primal 0 3/4 1 1/4 -5/12 50
𝛿𝑗 𝑍𝑦 = 5400 𝒁𝒙
0 3 0 3 5
= 𝟓𝟒𝟎𝟎
𝜹𝒋
Les valeurs des variables primales
Le dernier tableau du primal est :
10
800 600 0 0 0
𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 RHS
800 𝑥1 1 0 1/4 0 -1/4 3
600 𝑥2 0 1 -1/12 0 5/12 5
0 𝑒2 0 0 -1/4 1 -3/4 3
𝛿𝑗 0 0 -150 0 -50 𝑍𝑥 = 5400
11
