Dualité et analyse de sensibilité

CHAPITRE 5 : Dualité et analyse de sensibilité

I. Introduction

Nous abordons maintenant la propriété théorique fondamentale de la programmation linéaire,

dont les applications sont innombrables. Il s'agit de la propriété de dualité.
En suivant la méthode présentée en Section précédente, à tout programme linéaire, on peut
associer un autre programme linéaire, son dual. Le premier programme est le programme
primal. Lors de la transformation, les variables du primal deviennent les contraintes du dual et
les contraintes du primal deviennent les variables du dual.

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, l’excédent de chacune des
ressources. Elles sont aussi dites variables de surplus.

Soit le problème de production pour une entreprise E :

MaxZ = ∑C i Xi
SC ∑a ij X i ≤ bi

Xi ≥ o

Soit une firme F qui veut racheter les ressources de l'entreprise E.

A quels prix doit-elle le faire pour tout racheter au coût minimum?

On note yi le prix de la ressource i. F doit fixer les yi de manière à ce que ∑a Y

ij i ≥ C i ; pour

tout i = 1; : : : ; n. En effet, pour tout i, cela garantit que E a intérêt à vendre les ressources
nécessaires pour produire une unité de i plutôt que de la produire.
Quand une variable d’écart est nulle, on dit que la contrainte correspondante est
saturée .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.

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é.
 Dualité et analyse de sensibilité

II. Dualité

a. Définition
La forme d’un programme linéaire de type maximisation est
Max z = c x
t

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
t
A.Y ≥ c
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.

Exemple : Un agriculteur veut allouer 150 hectares de surface irrigable entre culture de
tomates et celles de piments. Il dispose de 480 heures de main d’œuvre et de 440 m3 d’eau.
Un hectare de tomates demande 1 heure de main d’œuvre, 4 m3 d’eau et donne un bénéfice
net de 100 dinars. Un hectare de piments demande 4 heures de main d’œuvre, 2 m3 d’eau et
donne un bénéfice net de 200 dinars.
Le bureau du périmètre irrigué veut protéger le prix des tomates et ne lui permet pas de
cultiver plus de 90 hectares de tomates. Quelle est la meilleure allocation de ses ressources ?

Le programme primal du 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 y3 ≥ 200
y1 ≥ 0 , y 2 ≥ 0
 Dualité et analyse de sensibilité

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 y3 ≥ 200
y1 ≥ 0 , y 2 ≥ 0
Exemples

Primal Dual
Max ½ x1 + x2 Min 3y1 + y2 + 2y3
S.c x1 + x2 ≤ 3 S.c y1 - y2 + y3 ≥ ½
- x1 + 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 + x2 ≤ 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 y1 + y2 = 2
 Dualité et analyse de sensibilité

S.c x1 - 2x2 ≤ 2 - 2y1 + y2+ y3 = -1

x1 + x2 = 6 y1 ≥ 0, y2 ∈IR, y3 ≥ 0
x2 ≤ 5
x1∈IR, x2∈IR

III. Analyse de sensibilité

Définition: Une solution de base optimale est dite stable si l’ensemble des variables de base à
l’optimum ne changent pas, même si les valeurs de ces variables de base sont modifiées.
Dans cette section on examinera la stabilité de la solution optimale d’un programme linéaire
suite à la variation de l’un des paramètres de ce programme.
On utilisera pour présenter l’analyse de sensibilité sur ces différents paramètres du
programme linéaire l’exemple de l’agriculteur.

Maxz= 100x1 + 200x2

S.c x1 + x2 ≤ 150
4x1 + 2x2 ≤ 440
- x1 + 4x2 ≤ 480
x1 ≤ 90
x1 ≥ 0 , x2 ≥ 0

a. Analyse de sensibilité sur les Cj

On cherche à déterminer un intervalle dans lequel peut varier Cj sans que la solution optimale
ne change.Considérons une variation du coefficient Cj de 100 à 100 + ∆
En remplaçant dans le tableau optimal 100 par 100 + ∆ , on obtient le tableau suivant :

100+∆ 200 0 0 0 0
x1 x2 S1 S2 S3 S4
100+∆ x1 40 1 0 4/3 0 -1/3 0
0 S2 60 0 0 -14/3 1 2/3 0
200 x2 110 0 1 -1/3 0 1/3 0
0 S4 50 0 0 -4/3 0 1/3 1
100+∆ 200 (200+4∆)/3 0 (100-∆)/3 0
0 0 -(200+4∆)/3 0 ∆-100/3 0

La solution donnée par le tableau reste optimale si

 ( 200 + 4 ∆ )
− ≤ 0
 3  ∆ ≤ − 50
 ⇔  ⇔ − 50 ≤ ∆ ≤ 100
 ∆ − 100 ≤ 0  ∆ ≤ 100
 3
Donc la solution optimale est stable et prend la même valeur (x1,x2)=(40,110) tant que
50 ≤ C1 ≤ 200

Exercice : Supposons que le coefficient Cj d'une variable hors base dans la solution optimale,
est modifié. Dans quel intervalle, Cj peut-il varier sans que la base optimale soit modifiée ?
(Aide : différencier le cas d’un programme de maximisation et le cas d’un programme de
minimisation).
 Dualité et analyse de sensibilité

Solution :
- ∞ < C j ≤ zj cas d’un programme de maximisation
zj ≤ Cj < - ∞ cas d’un programme de minimisation

b. Analyse de sensibilité sur les bj

Déterminer l’intervalle pour lequel, la solution optimale reste stable, pour une variation du
second membre de la ième contrainte bi.
Considérons une variation de b1 de 150 à 150+∆. Sachant que dans le premier tableau de
simplexe b1 n’est présent que dans la première contrainte. On obtient ainsi une
correspondance entre la colonne des quantités Qi et la colonne de S1.

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
0 S1 150+1× ∆ 1 1 1 0 0 0
0 S2 440+0× ∆ 4 2 0 1 0 0
0 S2 480+0× ∆ 1 4 0 0 1 0
0 S4 90+0× ∆ 1 0 0 0 0 1
0+1× ∆ 0 0 0 0 0 0
100 100 0 0 0 0

Dans le tableau optimal, la colonne correspondant à S1 nous donne les coefficients de ∆ dans
la colonne des quantités.

100 200 0 0 0 0
x1 x2 S1 S2 S3 S4
100 x1 40+4/3∆ 1 0 4/3 0 -1/3 0
0 S2 60-14/3∆ 0 0 -14/3 1 2/3 0
200 x2 110-1/3∆ 0 1 -1/3 0 1/3 0
0 S4 50-4/3∆ 0 0 -4/3 0 1/3 1
26000+200∆/3 100 200 200/3 0 100/3 0
0 0 -200/3 0 -100/3 0
La base reste optimale tant que :
40 + 4 / 3∆ ≥ 0 ∆1 ≥ −30
60 − 14 / 3∆ ≥ 0 ∆ ≤ 90 / 7
 
 ⇔ 1 ⇔ - 30 ≤ ∆ ≤ 90/7
 110 − 1 / 3∆ ≥ 0  ∆ 1 ≤ 330
50 − 4 / 3∆ ≥ 0 ∆1 ≤ 75 / 2

Donc tant que 120 ≤ b1 ≤ 160,85 la base demeure la même et la solution optimale est stable
mais elle change en valeur (exemple: pour ∆= 3 le vecteur de solutions optimale est
(x1,x2,S1,S2,S3,S4)=(44,109,0,46,0,46))

Remarque : D’après le résultat ci-dessus on peut conclure que le coût marginal de 200/3 par
hectare de la première ressource n’est valide que si la solution de base demeure stable. Donc
si et seulement si 120 ≤ b1 ≤ 160,85. Ceci est appelé le domaine de validité du coût marginal.
 Dualité et analyse de sensibilité

Exercice 1: Sans faire de calcul, de combien peut-on modifier la quantité de m3 d’eau sans
nuire à la solution optimale ? Confirmez votre résultat à l'aide de la méthode d'analyse de
sensibilité exposé ci-dessus ?

Exercice 2 : Déterminer l’intervalle dans lequel peut varier b1 et b3 (les ressources en surface
et en main d’œuvre) sans que la base optimale change.

Réponse 2 :
40 + 4 / 3∆1 − 1 / 3∆ 2 ≥ 0 4∆1 − ∆ 2 ≥ −120
60 + 14 / 3∆ + 2 / 3∆ ≥ 0 7 ∆ + ∆ ≤ 90
 1 2  1 2
 ⇔ 
110 + 1 / 3∆1 + 1 / 3∆ 2 ≥ 0 ∆1 − ∆ 2 ≤ 330
50 + 4 / 3∆1 − 1 / 3∆ 2 ≥ 0 4∆1 − ∆ 2 ≤ 150
Pour ∆1 = 0 (variation nulle de la surface en hectare), la solution optimale est stable pour une
variation ∆2 des ressources en main d’œuvre entre 570 et 730 heures (-150 ≤ ∆2 ≤ 90).
Le coût marginal de 100/3 par heure de main d’œuvre de la 3ème ressource n’est valide que
dans l’intervalle [570, 730].

c. Analyse de sensibilité sur les coefficients aij

Supposons que dans le problème de l’agriculteur, le nombre d’unités de la ième ressources

nécessaire pour produire une unité de produit j, soit (aij + δ) ou lieu de aij. Ainsi, on se pose la
question si la solution optimale demeure stable suite à un tel changement.

i) xj est une variable de base et la ième ressource est totalement utilisée.

Par exemple : x1 + (4+δ)x2 ≤ 480 ⇒ x1 + (4 + δ )x2 + S3 = 480
A l’optimum, la base est inchangée donc
x1* + (4 + ∂ ) x *2 + S*3 = 480
S*3 = 0, x1* ≥ 0, x *2 ≥ 0
• Si δ ≥ 0 , alors l’équation ne peut pas être satisfaite sinon S*3 < 0 puisque x1* + 4 x 2* = 480
et ∂ x *2 + S*3 = 0 , x2* ≥ 0 .
• Si δ ≤ 0 , alors on a un excèdent de la 3ème ressource (S3 ≠ 0), ce qui nous contraint à
changer la base (la solution optimale n’est plus stable).

Conclusion: Dans le cas où xj est une variable de base optimale et la ième ressource est
totalement utilisée, il est impossible de modifier le coefficient aij sans que la base dans la
solution optimale ne change pas (la solution optimale n'est pas stable).

ii) xj est une variable de base et la ième ressource n’est pas totalement utilisée.
Par exemple : (4 +δ) x1 + 2x2 ≤ 440
⇒ (4 + δ )x1 +2x2 + S2 = 440

A l’optimum, la solution est inchangée donc

 Dualité et analyse de sensibilité

(4 + ∂ ) x1* + 2 x2* + S * 2 = 440

S*2 = 60, x1* ≥ 0, x *2 ≥ 0
Pour que la base demeure toujours optimale il faut et il suffit que
∂ x * + S * = 60 60
2 2
 * ⇒ 60 − ∂ x 2* ≥ 0 ⇒ ∂ ≤ ⇒ δ ≤ 3/ 2
S 2 ≥ 0 x 2*

Conclusion: Dans le cas où xj serait une variable de base optimale et où la ième ressource n’est
pas totalement utilisée, il est possible de modifier le coefficient aij d’une valeur δij égale à
S
− ∞ ≤ δ ij ≤ i et la solution optimale demeure stable.
x *j
iii) Si xj est une variable hors base (xj = 0). Ceci implique qu’on ne va pas produire le produit
j
• Si δij ≥ 0, alors il est encore moins économique de fabriquer ce produit si le coefficient
technologique aij augmenterait de δij
• Si δij ≤ 0 , alors la fabrication du produit j peut devenir économique si on utilise moins de
ressources.