CHAPITRE

IV : DUALITE

I. Introduction :
Dans ce chapitre, on va étudier des notions relatives aux programmes linéaires tels que
le programme dual, les coûts marginaux ainsi que des techniques de validation de la solution
d’un programme linéaire, c’est à dire l’analyse de sensibilité.
Nous allons commencer ce chapitre par donner quelques termes clés du jargon utilisé pour
interpréter économiquement les différents résultats du programme linéaire.

II. Interprétation économique :

Les éléments clés d’un programme linéaire standard sont :
- La fonction objectif dite fonction économique. Cette fonction peut représenter un coût, un
profit, etc...
- Les contraintes sont composées, des coefficients aij de la matrice A, dite matrice
technologique, et des constantes bi, qui forment le vecteur du second membre. Le second
membre peut représenter la disponibilité des ressources, les niveaux de demande etc...
- Les variables d’écart peuvent représenter, par exemple dans le problème de l’agriculteur,
l’excédent de chacune des ressources : terrain, eau, heures de travail, bureau d’irrigation. Elles
sont aussi dites variables de surplus.
Quand une variable d’écart est nulle, on dit que la contrainte correspondante est
saturée. Dans le problème de l’agriculteur les contraintes terrain et main d’œuvre sont
saturées. Elles sont dites aussi restrictives car une variation du second membre (par exemple)
engendre un changement dans la valeur de la solution optimale.
Toute contrainte non saturée à l’optimum n’est pas restrictive pour le problème, c’est à dire
qu’elle n’a aucune influence sur la solution considérée.
Définition:
Par définition, on appelle coût marginal d’un bien l’augmentation minimale de
dépenses, par rapport à la solution optimale, qui résulterait de l’utilisation d’une unité
supplémentaire de ce bien, lorsque le problème posé consiste à produire des biens au moindre
coût.
Si le problème posé consiste à transformer des biens pour vendre une production avec un
meilleur profit et l’augmentation maximale de revenu qui résulte de la possibilité de disposer
d’une unité supplémentaire de l’un des biens, est la valeur marginale de ce bien. Très souvent,
on emploie également dans ce cas le qualificatif coût marginal.
Remarque : Les coûts marginaux sont donc les effets nets associés aux variables d’écart,
puisque ce sont ces variables qui déterminent les excédents (ou les insuffisances) de biens.
Si une variable d’écart n’est pas nulle, dans la solution optimale, c’est que le bien
correspondant est déjà excédentaire. Par conséquent, le fait de disposer d’une unité
supplémentaire de ce bien n’aura aucune influence sur le revenu. On dit alors que ce bien à

Cours de Recherche opérationnelle 3éme année GEM 36

CHAPITRE IV : Dualité.

une valeur marginale nulle, ou par extension, que la variable d’écart associée à ce bien a une
valeur marginale nulle.
Par contre, si une variable d’écart est nulle dans la solution optimale, c’est que le bien
correspondant est totalement utilisé. Par la suite une variation de la disponibilité aura
généralement une influence sur le revenu. C’est pourquoi cette variable d’écart nulle dans la
solution optimale à une valeur marginale non nulle, et cette valeur marginale précise la
variation de la fonction économique résultant de l’utilisation d’une unité supplémentaire du
bien associé.
Exemple 1 :
Dans le problème de l’entreprise on a :
Supposons que la capacité en heure machine de l'atelier passe de 270 à 279 heures.
Le programme devient :
MaxZ   1500 x1  1800 x2
Sous les contraintes :
MaxZ   1500 x1  1800 x2
Sous les contraintes :
x1  3x2  x3  279
7 x1  8 x2  x4  800
4 x1  6 x2  x5  360
xi  0, i  1,5

x1 x2 x3 x4 x5 R
0 0 -100 0 -250 -117900 Z
1 0 1/3 0 1/6 33 x1
0 0 -5/9 1 -19/18 265 x4
0 1 -2/9 0 5/18 38 x3

Par conséquent, à l'optimum Z = 117900; On a eu une augmentation de la fonction

économique de 100 unités, On dit que la valeur marginale de la variable d'écart correspondent
au facteur de production "heures machine" est de 100 unités.

La valeur marginale d'une variable d'écart est égale à la valeur absolue de

son coefficient dans la fonction économique exprime en fonction des
variables nulles de la solution optimale.

Exemple :

variable x1 x2 x3 x4 x5
valeur marginale 0 0 100 0 250

Pour des raisons pratiques, la définition a été étendue aux variables d'activités.

Cours de Recherche opérationnelle 3éme année GEM 37

CHAPITRE IV : Dualité.

Application:
Si on dispose de 300 heure-machines, 810 heures main d'œuvre spécialisée et 350
heures main-d’œuvre non spécialisée, la marge sur coût de production optimale est de l'ordre :
117 000  300  270  100  810  800  0  350  360  250  117 500
117 000  30  100   10  0    10  250   117 500

Programme dual et primal:

Exemple:
La société mentionnée dans l’exemple 1 sous-traite le facteur de production, à une autre
entreprise qui cherche à minimiser le prix qu’elle paye, mais la société n'a intérêt à cette sous-
traitance que si elle réalise les mêmes marges.
Rappelons la formulation du problème dans l'exemple 1 :
Programme linéaire 1 :
Z
b
xA

 à maximiser
XX
d0

avec 

A

X
5 3  270 
 1500    1 
x
avec   7 8   800 
1800   360   2
x
4 6  

Formulation du problème :
yl : taux horaire d’une heure machine
y2 : taux horaire d'une heure main d'œuvre spécialisée
y3 : taux horaire d’une heure main d'œuvre non spécialisée W : Prix a payé par
l'entreprise.

Programme linéaire 2 :
minZ   270 y1  800 y 2  360 y3
Sous les contraintes :
5 y1  7 y 2  4 y3  1500
3 y1  8 y 2  6 y3  1800
xi  0, i  1,3

Écriture matricielle :
W
d
y

 à minimiser
AY
Y
b0

avec 

Le programme 1 est appelé programme primal du programme 2 et le programme 2 est dit
programme dual du programme 1.
Ces programmes sont liés à l'optimum par:
i) les deux programmes ont le même optimum.
ii) la valeur marginale d'une variable d'un programme est égale à la valeur optimale de
la variable associée.

Cours de Recherche opérationnelle 3éme année GEM 38

CHAPITRE IV : Dualité.

Les variables d'activités du programme primal sont associées aux variables d'écarts du
programme dual et inversement.
Ici La solution optimale du programme dual est :
y1=100, y2= 0, y3 = 250 ; a l'optimum w = 117 000

Exemple 2 : Dans le problème de l’agriculteur on a

 Le coût marginal lié à S1 est 200 3
 Une augmentation de S1 d’une unité entraîne une diminution de 200 3 de la valeur de la
fonction économique.
 Le coût marginal lié à S 2 est 0 et à l'optimum S 2 =0
 on a déjà 60m 3 d’eau de plus donc si on ajoute 1m 3 ca ne va pas changer la solution
optimale ni la valeur de la fonction économique
Le système de contraintes dans le programme linéaire relatif au tableau de simplexe
optimal du problème de l’agriculteur est
 x1  4 3 S1  1 3 S 3  40
S  14 3 S  2 3 S  60
 2 1 3

 x 2  1 3 S1  1 3 S 3  110
 S 4  4 3 S1  1 3 S 3  50
La fonction économique s’écrit :
z  100 x1  200 x 2
Si on exprime z en fonction de S1 et S 3 (variables hors base) en utilisant le système
d’équation ci dessus on a
z  100 4 3 S1  1 3 S 3  40  2001 3 S1  1 3 S 3  110
z  26000  200 3 S1  100 3 S 3
La valeur 26000 correspond à la valeur optimale de la fonction économique.
Si S1  1 alors un hectare de terrain de moins à utiliser, donc une réduction de 200 3 dinars
de la valeur de la fonction objectif.
Si on ajoute 3 hectares de terrains S1  3 , avec l’hypothèse que les autres quantités
restent inchangées alors le revenu augmente de 200 3  3  200dinars
On vérifie ceci, si on résout le programme linéaire
Max 100 x1  200 x 2
S.C x1  x 2  153
4 x1  2 x 2  440
x1  4 x 2  480
x1  90
x1  0 , x 2  0
On trouve que la valeur optimale va augmenter de 200 dinars est devient 26 200 dinars.
Exercice : Expliquer graphiquement que si on ajoute des m 3 d’eau, on aura aucune
amplification dans la fonction objectif.

Cours de Recherche opérationnelle 3éme année GEM 39

CHAPITRE IV : Dualité.

Remarque : Dans le cas où on diminuerait 60m 3 d’eau, la solution optimal devient

dégénérée.
Les valeurs marginales apportent donc des renseignements économiques particulièrement
intéressantes, mais il faut les utiliser avec prudence car leur domaine de validité est limité.
Par exemple, si on ajoute 30 hectares de terrains aux 150 déjà disponibles dans le problème de
l’agriculteur, le revenu augmentera de 200 3  3  200dinars . Ceci n’est pas vrai, parce que
si on résout le programme linéaire suivant :
Max 100 x1  200 x 2
S.C x1  x 2  180
4 x1  2 x 2  440
x1  4 x 2  480
x1  90
x1  0 , x 2  0
La valeur optimale du programme linéaire ci-dessus est de 26 875,14 donc le revenu
n’a pas augmenté de 2000 dinars comme prévu.
II. Dualité :
a. Définition
La forme d’un programme linéaire de type maximisation est
Max z  ct x
S.C Ax  b (PL1)
x0
avec x, b , c des vecteurs de dimensions respectives n, m et n , et A une matrice de
dimension m, n 
On appelle programme dual de PL1 , le programme linéaire suivant :
Min w  bt y
S .C A.Y  c
t

y0
avec y un vecteur de dimension m et t A la transposée de la matrice A .
Le programme (PL1) est appelé programme Primal.
Pour passer du primal au dual, on remarque que :
a ) Les termes du second membre deviennent les coefficients de la fonction objectif et
réciproquement.
b ) Le problème de maximisation devient un problème de minimisation.
c ) Les inégalités "  " deviennent des inégalités "  "
d ) La matrice A se transforme en sa transposée.

Cours de Recherche opérationnelle 3éme année GEM 40

CHAPITRE IV : Dualité.

Exemple : Le programme primal (problème de l’agriculteur) est

Max z  100 x1  200 x 2
S .C x1  x 2  150
4 x1  2 x 2  440
x1  4 x 2  480
x1  90
x1  0 , x 2  0
Donc le programme dual est
Min w  150 y1  440 y 2  480 y 3  90 y 4
S .C y1  4 y 2  y 3  y 4  100
y1  2 y 2  4 y 3  200
y1  0 , y 2  0

b. Propriétés et signification économique du programme dual

Pour expliquer la signification du problème dual on va se baser sur l’exemple de l’agriculteur.
Supposons qu’un agriculteur (client) voudrait acheter la totalité de nos ressources disponibles.
Notre agriculteur acceptera certainement cette proposition si le prix offert par ce client lui
procure le même profit.
Soit : y1 le prix d'un hectare de terrain
y 2 le prix d’un m 3 d’eau
y 3 le prix d’une heure de main d’œuvre
y 4 le prix de la permission de la culture d’un hectare de tomates.
Le problème du client consiste à minimiser les frais d’achat des ressources : c’est à dire
150 y1  440 y 2  480 y 3  90 y 4 , sous la contrainte que les prix satisfont notre agriculteur.
Pour notre agriculteur un hectare de terrain 4m 3 d’eau, une heure de travail et un hectare de
permission du bureau est équivalent a un revenu de 100 dinars.
Tandis que, un hectare de terrain, 2m 3 d’eau et 4 heures de travail lui engendrent un revenu
de 200 dinars.
Il n’est prêt à vendre ses ressources que si y1  4 y 2  y 3  y 4 lui rapporte un revenu supérieur
ou égal à 100 DT et que si y1  2 y 2  4 y 3 lui rapporte un revenu supérieur ou égal à 200 DT.
Ainsi le problème du client est
Min 150 y1  440 y 2  480 y 3  90 y 4
S .C y1  4 y 2  y 3  y 4  100
y1  2 y 2  4 y 3  200
y1  0 , y 2  0
Donc le problème du client peut être modélisé par le programme dual.
Le tableau de simplexe final du programme dual est :

Cours de Recherche opérationnelle 3éme année GEM 41

CHAPITRE IV : Dualité.

150 440 480 90 0 0

y1 y2 y3 y4 L1 L2
480 y3 100/3 0 -2/3 1 -1/3 1/3 1/3
150 y1 200/3 1 14/3 0 4/3 -4/3 1/3
150 380 480 40 -40 -110
0 60 0 50 40 110

Avec L1 et L2, les variables d’écart à la 1ère et la 2ème contrainte du programme dual.
On remarque que la solution optimale du dual peut être déduite du primal de la manière
suivante :
y1 = 200/3  C3 - z3 = - 200/3
y2 = 0  C2 - z4 = 0
y3 = 100/3  C5 - z5 = - 100/3
y4 = 0  C6 - z6 = 0
L1 = 0  C1 - z1 = 0
L2 = 0  C2 - z2 = 0
C1 - z1 = 0  S1 = 0
C2- z2 = 60  S2 = 60
C3- z3 = 0  S3 = 0
C4 - z4= 50  S4 = 50
C5 - z5= 40  x1 = 40
C6 - z6= 110  x2 = 110
w = 26000  z = 260000
On peut généraliser ce résultat dans le tableau suivant :

Primal (Max) Dual (Min)

Variables de décision : variables d’écart :
xj = 0  Cj - zj < 0 Li = | Cj - zj |  0  Cj - zj = 0
xj > 0  Cj - zj = 0 Li = 0  Cj - zj = xj
Variables d’écart : Variables de décision :
Sj = 0  Cj - zj  0 yi = | Ci - zj |  0  Cj - zj = 0
Sj > 0  Cj - zj = 0 yi = 0 et Cj – zj = Sj
On remarque aussi qu’à l’optimum la valeur de la fonction objectif du dual est égale à la
valeur de la fonction objectif du primal.

Proposition : Le dual du programme dual est le programme primal.

Cours de Recherche opérationnelle 3éme année GEM 42

CHAPITRE IV : Dualité.

c. Tableau de correspondance primal-dual

Max Min
- Matrice des contraintes (m, n) - Transposée de la matrice des contraintes (n,
m)
- Second membre des contraintes - Coefficient de la fonction objectif
- Coefficient de la fonction objectif - Second membre des contraintes
Nombre de contraintes Nombre de variables principales
i ème contrainte de type «  » i ème variable de type «  0 »
i ème contrainte de type «  » i ème variable de type «  0 »
i ème contrainte de type « = » i ème variable qcq « IR »

Nombre de variables Nombre de contraintes

j ème variable «  » j ème contrainte de type «  »
j ème variable «  » j ème contrainte de type «  »
j ème variable qcq « IR » i ème contrainte de type « = »

Exemples
Primal Dual
Max ½ x1 + x2 Min 3y1 + y2 + 2y3
S.c x1 + x2  3 S.c y1 - y2 + y3  ½
- x 1 + x2  1 y1 + y2  1
x1  2 y1  0, y2  0, y3  0
x1  0, x2  0
Min - x1 + x2 Max 2y1 - 2y2 + 5y3
S.c 2x1 - x2  2 S.c 2y1 - y2 + y3  -1
- x1 + 2x2  -2 - y1 + 2y2 + y3  1
x1 + x 2  5 y1  0, y2  0, y3  0
x1  0, x2  0
Max 2x1 - x2 Min 3 y1+ 4 y2
S.c x1 - x2 = 3 S.c y1+ 2 y2  2
x1  4 - y1  -1
x1  0, x2  0 y1IR, y2  0
Max 2x1 - x2 Min - 2y1 + 6y2 - 5y3
S.c x1 - 2x2  2 S.c y1 + y2 = 2
x 1 + x2 = 6 - 2y1 + y2+ y3 = -1
x2  5 y1  0, y2 IR, y3  0
x1IR, x2IR

III. Exercice :
Une entreprise à la faculté de fabriquer sur une même machine donnée travaillant 45
heures/ semaine, 3 produits différent : P1 , P2 , P3

Cours de Recherche opérationnelle 3éme année GEM 43

CHAPITRE IV : Dualité.

Les revenus nets sont respectivement pour chaque article des 3 produits 4 TND, 12 TND et 3
TND, les rendements horaires de chaque machine sont respectivement 50, 25, et 75
Les ventes possibles sont limitées comme suit : 100 articles P1, 500 articles P2 et 1500
articles P3.
a) Résoudre le problème par une méthode économique en maximisant le revenu de
l’entreprise.
b) Quel est le programme de production qui maximise le revenu de l’entreprise.
c) Poser et résoudre le programme dual.
d) Si on disposait de 55 heures machines par semaines, quel serait le revenu optimal de
l’entreprise.

Cours de Recherche opérationnelle 3éme année GEM 44