01/10/2021

Chapitre 4 : Dualité.

Plan du chapitre 4

I. Illustration de la notion
II. Forme canonique d’un PL
[Link] entre le primal/dual dans le cas
général
IV. Théorèmes généraux de la dualité
V. Obtention de la solution optimale du dual
à partir de la solution optimale du primal
[Link] du tableau optimal du dual à partir du
tableau optimal du primal.
VII. Situations particulières

1
 01/10/2021

I- Illustration de la notion
Une entreprise fabrique des tables et des chaises.
Le profit unitaire généré par la production d’une
table est de 8 DT et celui d’une chaise est de 6 DT.
La fabrication d’une table nécessite 5 m2 de bois, 2h
d’assemblage et 1h de finition. La fa brication d’une
chaise nécessite 3 m 2 de bois, 3h d’assemblage et 3
h de finition. L’entreprise dispose de 30 m2 de bois.
Sa capacité d’assemblage est de 24 h et sa capacité
de finition est de 18h.
La formulation est ainsi :

Formulation du PRIMAL :

X1 Le nombre de tables à fabriquer

X2 Le nombre de chaises à fabriquer

La fonction objectif

Max Z = 8 X1 +6 X2
Les contraintes :

5X1 + 3X2 ≤ 30 (Quantité de bois disponible)

2X1 + 3X2 ≤ 24 (heures d’assemblage)

X1 + 3X2 ≤ 18 (heures de finition)

X1, X2 ≥ 0
01/10/2021

2
 01/10/2021

Construction du problème dual associé au

problème donné appelé primal
Supposons qu’un client voudrait acheter la totalité des
ressources disponibles. Le directeur de l’entreprise acceptera
certainement cette proposition si le prix offert par ce client lui
procure le même profit provenant de la vente des tables et des
chaises.
Les nouvelles variables :
On place alors une valeur monétaire sur les ressources:
y1 le prix d’1 m2 de bois
y2 le prix d'une heure d’assemblage
y3 le prix d’une heure de finition
Les prix de vente des ressources sont bien sûr positifs. yi ≥ 0, avec
i=1,..3.

La nouvelle Fonction objectif est formulée ainsi :

Le problème du client consiste à minim iser les frais

d’achat des ressources, c’est à dire
Min Zy = 30 y1+24 y2 + 18 y3
On doit avoir alors à l’optimalité :
Zx=Z = 8 X1 + 6 X2 =Zy= 30 y1+24 y2 + 18 y3

3
 01/10/2021

Les nouvelles contraintes :

Le directeur de l’entreprise ne cédera ses ressources que si

le revenu rapporté par la vente des ressources nécessaires à la
production d’une unité d’un produit donné est > au revenu
engendré par la production de cette unité et sa vente.

La production de chaque table nécessite

5 m2 de bois ,
2h d’assemblage et
1h de finition,
donc le revenu engendré par la vente de ces ressources est
5y1 +2y2 + y3 et
on sait que le prix engendré par la production et la vente
d’une table est 8 :
d’où la première contrainte imposée par le primal sur le dual
est définie par: 5y1 +2y2 + y3 ≥ 8.

D’une manière similaire, la production de chaque chaise

nécessite
3 m2 de bois,
3h d’assemblage et
3h de finition.

Le revenu engendré par la vente de ces ressources est :

3y1 +3y2 + 3y3 et

on sait que le prix engendré par la production et la

vente d’une chaise est 6

d’où la deuxième contrainte imposée par le primal sur

le dual est définie par:
3y1 +3y2 + 3y3 ≥ 6.

4
 01/10/2021

Formulation du problème dual

D’où la formulation du nouveau problème dual associé au
problème primal :

Min Zy = 30 y1+24 y2 + 18 y3

5y1 +2y2 + y3 ≥ 8.
3y1 +3y2 + 3y3 ≥ 6.

yi ≥ 0, avec i=1,..3.

PRIMAL DUAL

Les variables de décision : Les variables de décision :

X1 : nb Tables Y1 :prix d’un m2 de bois
X2 : nb Chaises Y2 : prix d’’ h. d’assemblage

Y3 :prix d’ h. de finition

Max Z = 8 X 1 +6 X 2 min Z = 30 Y1 + 24 Y2 + 18 Y3
Les contraintes : Les contraintes

5X 1 + 3X 2 ≤ 30 (bois) 5 Y1 + 2 Y2 + Y3 ≥ 8 (tables)

2X 1 + 3X 2 ≤ 24 (h. d’assemblage) 3 Y1 + 3 Y2 + 3 Y3 ≥ 6 (chaises)

X 1 + 3X 2 ≤ 18 (h. de finition)

X1 ≥ 0 Y1 ≥ 0

X2 ≥ 0 Y2 ≥ 0

Y3 ≥ 0

5
 01/10/2021

Relation Primal/Dual:
• Problème primal: Maximiser le profit
Etant donné la valeur unitaire (cj) de chaque produit (profit)
et une borne supérieure à la disponibilité de chaque
ressource (bi) :
combien de chaque produit (xj) doit on fabriquer
pour maximiser la valeur totale des produits réalisés.

• Problème dual: Minimiser le coût de production:

Etant donné la disponibilité de chaque ressource (bi) et une
borne inférieure à la valeur unitaire (cj) de chaque produit
vendu :
quelles devront être les valeurs unitaires yi des
ressources pour minimiser la valeur totale des ressources
utilisées. 11

Relation Primal/Dual:

On remarque qu’à chaque variable du Dual correspond une

contrainte du Primal et à chaque contrainte du dual correspond
une variable du primal.
On dit que les variables du dual sont en bijection avec les
contraintes du primal et vice versa.

12

6
 01/10/2021

II- Forme canonique d’un PL

Pour un problème de maximisation :
Max Z = C X
s.c: AX ≤ b
X≥ 0

Pour un problème de minimisation :

Min Z = C X
s.c: AX ≥ b
X≥ 0
Avec
X,C des vecteurs de dimensions n
b : vecteur de dimension m
A une matrice de dimension (m,n).

Remarque :
Quand le primal est sous forme canonique (que ce soit Max ou Min) ,
Le dual obtenu est aussi sous forme canonique.

Relation Primal/Dual:

Forme canonique d’un primal Forme canonique du dual

de type maximisation est :

Max Zx = c x Min Zy =bt y

s.c: Ax ≤ b s.c: At y ≥ ct
x≥0 y ≥0
Avec Avec
x,c des vecteurs de y un vecteur de
dimensions n dimension m
b : vecteur de dimension m At la transposée de la
A une matrice de dimension matrice A, donc de
(m,n). dimension (n,m)

7
 01/10/2021

Exercice d’application:
Construire le problème dual associé à ces deux PL
qui sont sous forme canonique :
1) Max Z = 2x1 + 3x2 + 4x3
x1 -x2 + x3 ≤ 10
2x1 +7x2 + 3x3 ≤ 8
xi ≥ 0 pour i : 1..3

2) Min Z = 5x1 +2x2

x1 + x2 ≥ 8
-x1 + 4x2 ≥ 7
x1 - x2 ≥ 3

xi ≥ 0, avec i=1,..2.

III- Correspondance Primal/Dual dans le cas général

MAX MIN
Nombre VD du primal Nombre contraintes du dual
Nombre contraintes du primal Nombre VD du dual

La jème VD de (P) La jème contrainte de (D)

La ième contrainte de (P) La ième VD de (D)

Contrainte de type ≤ VD ≥ 0
Contrainte de type ≥ VD ≤ 0
Contrainte de type = VD sans signe

VD ≥ 0 Contrainte de type ≥
VD ≤ 0 Contrainte de type ≤
VD sans signe Contrainte de type =

Le second membre de la ième contrainte Le coefficient de la ième VD dans la fonction

objectif
Le coefficient de la jème VD dans la fonction
objectif Le second membre de la jème contrainte

Le coefficient aij : de la la jème VD dans la ième Le coefficient aji : de la la ième VD dans la jème
contrainte contrainte

8
 01/10/2021

Exercice d’application:
Construire le problème dual associé à ces deux
exemples :
1) Max Z = 4x1 + 5x2 + 9x3
x1 +x2 + 2x3 = 16
7x1 +5x2 + 2x3 ≤ 25
x1 sans signe ; x2 ≥ 0 ; x3 ≤ 0

2) Min Z = 6x1 +5x2 + 10x3

x1 + x3 ≥ 7
3x2 – x3 ≤ -1
x1 + 2x2 + 4x3 = 1

x1 ≥ 0 ; x2 ≤ 0 ; x3 sans signe

IV- Théorèmes généraux de dualité

Théorème 1 :
Le dual du dual est le primal

Théorème 2 : Propriété faible de dualité :

Pour toute paire de solutions réalisables de deux PL
primal et Dual on a toujours :
Z max ≤ Z min

Théorème 3 : Propriété forte de dualité

Si les PL primal et dual admettent des solutions
optimales finies alors on a:
Z max =Z min

9
 01/10/2021

Exercices d’application
(propriété faible de la dualité)
1) Soit le programme linéaire suivant :
Min Z = x1 +2x2 -3x3
5x1 -x2 +6x3 ≥ 4
x1+x2 +x3 ≤ 10
xi ≥ 0 ; i:1..3
Les tableau ci-dessous présente 3 solutions du primal et 3 solutions du dual :

Primal Dual
x1 x2 x3 y1 y2
7 2 0 -1 0
3 0 1 3 -5
0 -2 3 0 -4

1) Quelles sont les solutions réalisables ?

2) Donner un encadrement pour la valeur optimale de Z.

Correction
Le dual :
Min Z = x1 +2x2 -3x3
5x1 -x2 +6x3 ≥ 4 Max Z = 4y1 + 10y2
x1+x2 +x3 ≤ 10 5y1 +y2 ≤ 1
xi ≥ 0 ; i:1..3
-y1 + y2 ≤ 2

6y1 +y3 ≤ 3
y1 ≥ 0 ; y2 ≤ 0
Solution 1 :
X1 =7 , X2 =2, X3 =0 à Zmin = 11
Solution 2 :
X1 =3 , X2 =0, X3 =1 à Zmin = 0
Solution 3 :
X1 =0 , X2 =-2, X3 =3 à XXX
Solution 4 :
Y1 =-1 , Y2 =0à XXX
Solution 5 :
Y1 =3 , Y2 =-5à Zmax = -38
Solution 6 :
Y1 =0 , Y2 =-4à Zmax = -40

DONC -38 ≤ Zopt ≤ 0

10
 01/10/2021

Théorème 4 : Théorème des écarts complémentaires

Notons :
si et ej respectivement les variables d’écart des PL du Primal et du Dual. Et
(xj, j=1,..n) et (y i i=1, ..m) respectivement des solutions réalisables du primal et
du dual

Alors, a l’optimalité, la propriété de complémentarité des écarts s’écrit :

y *i s*i=0
e*j x*j=0
C’est-à-dire :
Le produit d’une variable du dual par la variable d’écart correspondante
dans le primal est nul
Et le produit d’une variable du primal par la variable d’écart
correspondante dans le dual est nul

En d’autres termes :
Si une variable d’écart primale si* est dans la base (donc non nulle) alors la
variable duale correspondante est nulle y i*. Et vice versa.
Si la variable de décision primal xj* est dans la base (donc non nulle) alors la
variable d’écart duale correspondante ej* est nulle. Et vice versa.

Exercice d’application:
Sans utiliser l’algorithme de simplexe, résoudre le
programme linéaire suivant :
Max Z = 2x 1 -3x2 + 4x3
x 1 + 5x 2 + x 3 =4
-x 1 -3x 2 + x 4 =2
x1 ; x2 ≥ 0 ;

INDICES :
1) PL a 4 variables et 2 contraintes à Penser a écrire le dual qui sera à 2
variables et 4 contraintes : donc résolution graphique (on aura dans ce cas
directement la solution optimale duale, mais il faut quand même vérifier)
2) Application du TEC pour déterminer la solution optimale du primal

11
 01/10/2021

V - Obtention de la solution optimale du dual

à partir de la solution optimale du primal (et vice versa)
1) Application du TEC :
La résolution par l’algorithme du simplexe a donné comme tableau final :
Max x1 x2 s1 s2 s3 b
Cj 8 6 0 0 0
x1 8 1 0 1/4 0 -1/4 3
x2 6 0 1 -1/12 0 5/12 5
s2 0 0 0 -1/4 1 -3/4 3
zj 8 6 3/2 0 1/2 Z=54
Cj-zj 0 0 -3/2 0 -1/2

La solution optimale du primal est donc

X1=3 ; S1=0
X2=5 ; S2=3
et Z =54 S3=0

Application du TEC à pour retrouver la solution optimale du dual

Primal Dual
X1=3 e1=0
X2=5 e2=0
S1=0 Y1= ?
La Forme standard du dual : S2=3 Y2=0
S3=0 Y3=?
5 y1 +y3 – e1= 8
Z=Z’=54
3 y1 +3 y3 – e2= 6
A l’optimalité, en utilisant le TEC (e1 =e2=y2=0), on obtient :

30 y1 +24 *0 +18 y3 = 54 y1=3/2

5 y1 +y3 = 8 d’où y3=1/2
3 y1 +3 y3 = 6

24

12
 01/10/2021

2) D’après la dernière ligne Δj = cj-zj

On peut retrouver les valeurs des variables duales à partir de la dernière ligne Δj
= cj-zj du tableau optimal primal

Max x1 x2 s1 s2 s3 b
Cj 8 6 0 0 0
x1 8 1 0 1/4 0 -1/4 3
x2 6 0 1 -1/12 0 5/12 5
s2 0 0 0 -1/4 1 -3/4 3
zj 8 6 3/2 0 1/2 Z=54
Cj-zj 0 0 -3/2 0 -1/2

e1 e2 y1 y2 y3 Z’

Interprétation économique de la ligne Δj d’une variable d’écart

(valeur de la variable duale)
C’est la valeur marginale de la ressource correspondante à la
contrainte : la variation de Z suite à l’augmentation d’une unité
supplémentaire de cette ressource.

Si PL de max (profit), on parle de gain marginal.

Si PL de min (coût), on parle de coût marginal.

Comme le Δj de la variable d’écart détermine la valeur de la variable

duale, il est appelé aussi prix fictif (ou Shadow Price).

Cette valeur est

nulle si la contrainte correspondante n’est pas saturée et donc si la
ressource associée est abondante
non nulle si la contrainte est saturée et donc si la ressource
associée est épuisée

26

13
 01/10/2021

Interprétation de la solution
duale de l’exemple
Solution duale :
Y1=3/2 : Je suis prêt à payer au max 3/2 pour 1 m2 de bois en plus de sa valeur
sur le marché //Prix de cession//Prix marginal//gain marginal//shadow price

Y2=0 : Je suis prêt à payer uniquement sa valeur sur le marché pour 1h

d’assemblage

Y3=1/2 : Je suis prêt à payer au max ½ pour 1h de finition , en plus de sa valeur

sur le marché.

e1=0 : Le revenu rapporté par la vente des ressource nécessaire à la production

d’une table = revenu engendré par sa vente.

e2=0 : : Le revenu rapporté par la vente des ressource nécessaire à la production

d’une chaine = revenu engendré par sa vente.

Z’=54

Exercice d’application:
Une société cherche à décider les quantités à fabriquer de trois types P1, P2 et
P3 .Ces produits nécessitent respectivement 1, 2 et 3 unités de ressource rare
disponible en 15 unités . On exige la fabrication d’au moins 4 unités de P2 et P3
. Les prix de vente unitaires sont respectivement de 2 dinars pour P1, 1 dinar
pour P2 et de 2 dinars pour P3.

1)Modéliser ce problème sous forme d’un programme linéaire.

2) Ecrire le PL dual correspondant
3) Parmi ces deux dernières lignes du tableau optimal associé au PL primal,
qui correspond au bon résultat ?

X1 X2 X3 S1 S2 bi
Δj 0 0 -1 -2 -3 18

X1 X2 X3 S1 S2 bi
Δj 0 0 -1 0 -4,5 18

4) Donner une interprétation des variables duales.

14
 01/10/2021

1) Max Z = 2x1 +x2 +2x3

Correction
x1 +2x2 +3x3 ≤ 15
x2 +x3 ≥ 4
xi ≥ 0 ; i:1..3
2) Min Z’=15y1+4y2
y1+y2 ≥2
2y1 ≥1
3y1+y3 ≥ 2
y1 ≥ 0 ; y2 ≤ 0
3) Comme y1 ≥ 0 et y2 ≤ 0 , on a :
y1=2 et y2 = -3 pour le premier tableau et donc Z= 18
y1=0 et y2 = - 4,5 pour le deuxième tableau et donc Z= -18 X
Le premier tableau est donc JUSTE
X1 X2 X3 S1 S2 bi
Δj 0 0 -1 -2 -3 18

4) y1=2 : On est prêt à payer 2 DT au maximum, en plus de sa valeur

sur le marché pour une unité de ressource
y2 = -3 :Chaque unité supplémentaire exigée de l’un des deux
produits P2 ou P3, engendre un coût supplémentaire de 3DT de plus que
le coût initial

VI- Obtention du tableau optimal dual à

partir du tableau optimal primal
Tableau Primal Optimal Matrice simpliciale
S1 s3 b
X1 1/4 -1/4 3
Max x1 x2 s1 s2 s3 b X2 -1/12 5/12 5
Cj 8 6 0 0 0 S2 -1/4 -3/4 3
x1 8 1 0 1/4 0 -1/4 3 -3/2 -1/2
x2 6 0 1 -1/12 0 5/12 5
Opposé de la transposée de la matrice
s2 0 0 0 -1/4 1 -3/4 3 e1 e2 y2
zj 8 6 3/2 0 1/2 Z=54 y1 -1/4 1/12 1/4 3/2
Cj-zj 0 0 -3/2 0 -1/2 y3 1/4 -5/12 3/4 1/2

Cj-zj 3 5 3
e1 e2 y1 y2 y3 Z’

Correspondance entre Variables primales et duales

15
 01/10/2021

tableau optimal dual

Min y1 y3 e1 e2 y2 b
cj 30 18 0 0 24
y1 30 1 0 -1/4 1/12 1/4 3/2
y3 18 0 1 1/4 -5/12 3/4 1/2
Δj = Cj-zj 0 0 3 5 3 Z’=54

VII- Situations particulières

Si l’un des deux PL a une solution rejetée vers l’infini, alors
l’autre PL n’a pas de solution

Si l’un des PL n’a pas de solution alors L’autre PL a

soit une solution rejetée vers l’infini
soit il n’a pas de solution

Si l’un des deux PL a une solution dégénérée alors l’autre

PL a une solution multiple

Si l’un des deux PL a une solution optimale finie alors

l’autre PL a aussi une solution optimale finie et en plus on
a Zmax=Zmin

16
 01/10/2021

Exercice d’application:
Résoudre les Pl donnés et leur Dual correspondant. Que
pouvez vous conclure ?

1) Max Z = 10x1 - x2
2x1 +x2 ≤ -4
5x1 ≤ 10
x2 ≤ 6
xi ≥ 0 ; i:1..2

2) Max Z = x1+x2

-x1 + x2 = 1
x1 – x2 = 0

xi ≥ 0 ; i:1..2

17