Dualité et sensibilité 02/06/2014

PLAN :

Introduction

I- La dualité en programmation linéaire :

1. définition générale des problèmes duals

2. Théorème de la dualité

3. Formulation générale des problèmes duals

4. Théorème des relations d’exclusion

II- L’analyse de sensibilité :

2 La variation des coefficients de la fonction économique

)a Evaluation graphique

)b Evaluation algébrique

2 La variation du second membre des contraintes

1
Dualité et sensibilité 02/06/2014

INTRODUCTION :
L’algorithme du simplexe livre une solution optimale. Mais il reste au décideur de faire
le lien entre les résultats abstraits dans les tableaux de calcul et la réalité concrète de
l’entreprise. La solution doit donc être interprétée économiquement pour servir de base
à l’action.
En outre, cette solution optimale découle de nombreuses données initiales imprécises :
coefficients techniques de production, ressources disponibles, coûts, prix de vente, etc.
Or ces données ne sont pas toujours très fiables : elles sont souvent entachées d’erreurs
et d’incertitudes, et peut donc être souhaitable sinon indispensable de déterminer dans
quelle mesure la solution optimale peut néanmoins être retenue.

I. La dualité en programmation linéaire :

1. définition générale des problèmes duals

En se plaçant du coté du vendeur, celui-ci cherchera à maximiser ces recettes tout en

respectant les contraintes liées d’une part aux capacités de production et d’autre part à
celle posées par l’acheteur.
En conclusion, à tout programme de maximisation des recettes correspond un
problème de minimisation des coûts et inversement .le premier problème considéré est
appelé programme primal, et le second appelé programme dual.

Donc à tout programme linéaire dénommé primal il est possible d’associer un

programme linéaire dit dual dont tous les éléments sont dérivés du programme primal.

Notion matricielle :

S’il existe un vecteur solution X tel que

2
Dualité et sensibilité 02/06/2014

[A] [X] ≤ [B]

Max Z =[C] · [X], avec
[X]≥0

Alors il existe un vecteur solution Y associé tel que

[A] T [Y] ≥[C] T

Min Z’ = [B] T [Y] avec
[Y]≥0

2 Théorème de la dualité.
Si les programmes primal et dual possèdent l’un et l’autre des solutions admissibles,
alors le primal admet une solution optimale (X1, X2), le dual une solution optimale
(Y1, Y2) telles que :

∑cjxj = ∑biyi
J=1 i=1

Si l’un des programmes n’admet pas de solution admissible l’autre n’admet pas de
solution optimale.

 Théorème de la dualité faible. éorème de d

Soit x une solution admissible d’un PL canonique et y une solution admissible de son
dual.
Alors Cx ≤Yb

Corollaire

Soit x une solution admissible du (PLP) de valeur z et y une solution admissible du

(PLD) de valeur w. Si z = w, alors les solutions x et y sont optimales pour leur
problème respectif.

 Théorème de la dualité forte.

Si un PL sous forme standard possède une solution optimale x* = (x*D, x*E) de

Valeur z* = cDx* D, alors son dual possède une solution optimale y*= (y*D, y*E). De
plus, la valeur de cette solution est w* = y*Db = z*.

3
Dualité et sensibilité 02/06/2014

2 Formulation générale des problèmes duals :

La construction d’un programme dual s’opère en effectuant les associations suivantes :

- à chaque contrainte primale correspond une variable duale réelle ;

- à chaque variable primale réelle correspond une contrainte duale ;
- la matrice des coefficients des variables dans les contraintes du dual (A) T est la
matrice transposée des coefficients de variables dans le programme primal (A) ;
- les seconds membres des contraintes du dual sont les coefficients économiques
des variables primales ;
- aux contraintes du type ≤ correspond des contraintes de type ≥ et réciproquement ;
- les coefficients économiques des variables duales sont les valeurs figurant au
second membre des contraintes du primal.

NB : avant de passer d’un programme primal à un programme dual, il faut vérifier que
toutes les inégalités ont un sens identique (≤ s’il s’agit de maximiser ou ≥ pour un
problème de minimisation.

Exemple :

Reprenons l’exemple de l’exposé précédant ; cas de la société Bonvin S.A

 Programme primal (forme canonique).

Max Z avec Z = 400X1 + 500X2

Y1 ← 0,5X1 + 0,2X2 ≤ 13600
Y2 ← 0,3X1 + 0,6X2 ≤ 12000
Y3 ← 0,2X1 +0,2X2 ≤ 10400
Y4 ← 1X1 + 0X2 ≤ 20000
Y5 ← 0X1+1X2 ≤ 16000
Y6 ← -1X1 + 0X2 ≤ -15000
Y7 ← 0X1 – 1X2 ≤ - 5000
↓ ↓ ↓
1ere 2eme Fonction
Contrainte Contrainte Objectif
Duale duale

4
Dualité et sensibilité 02/06/2014

 Programme dual associé.

Min Z’ avec

Z’ = 13600Y1 + 12000Y2 + 10400Y3 + 20000Y4 + 16000Y5 - 15000Y6 – 5000Y7

0,5Y1 + 0,3Y2 + 0,2Y3 + 1Y4 + 0Y5 - 1Y6 – 0Y7≥ 400.

0,2Y1 + 0,6Y2+ 0,2Y3 + 0Y4 + 1Y5 + 0Y6 – 1Y7 ≥ 500.

2 Théorème des relations d’exclusion :

Les variables duales doivent être interprétées comme les couts marginaux ou valeurs
marginales unitaires. Donc :

 Si une contrainte primale n’est pas saturée à l’optimum, le coût marginal de cette
contrainte est nul et la variable duale correspondante prend une valeur nulle à
l’optimum ;
 Si une contrainte primale est saturée à l’optimum, le cout marginal de cette
contrainte est positif ou nulle. la variable duale correspondante prend, à
l’optimum, exactement la même valeur.

Finalement le tableau dual optimal peut être intégralement déduit du tableau primal
optimal. En outre les propriétés de la dualité sont réciproques : le programme dual
associé au dual n’est autre que le programme primal. La connaissance des
caractéristiques d’un programme est donc indissociable de la connaissance de l’autre
programme.

Relation primal-dual

5
Dualité et sensibilité 02/06/2014

Primal : Tableau Final.

 L’intérêt de la dualité est double :

 D’une part la recherche explicite d’une information sur les quantités

(maximales) conduit inévitablement à déterminer implicitement des couts
(minimaux) associés ;
 D’autre part, il est indifférent de recherche explicitement soit les quantités
optimales soit les couts optimaux. Donc il est possible de traiter (par méthode
du simplexe) soit le primal soit le dual selon que l’un semble plus rapide à
résoudre que l’autre.

II. l’analyse de la sensibilité

6
Dualité et sensibilité 02/06/2014

La solution optimale d’un programme linéaire conditionnée par les données initiales
(coefficients techniques, ressources disponibles, coefficients économiques, etc….). Or,
ces données, très souvent, sont imprécises, aléatoires, variables dans le temps. C’est
pourquoi il est souhaitable de mesurer la sensibilité de la solution optimale proposée
par rapport aux variations d’un ou plusieurs coefficients originels.
L’étude de sensibilité aborde deux cas :

-le cas de variation de coefficients de la fonction économiques ;

-le cas de variation des seconds membres des contraintes.

1.la variation des coefficients de la fonction

économique.
Les coefficients de la fonction économique dépendent très souvent d’éléments
difficiles à appréhender. Mais il ne faut pas en déduire pour autant que la solution
optimale qui en découle soit irrémédiablement faussée.
En effet, il existe, dans l’évaluation de ces coefficients, une possibilité d’erreur ou
d’incertitude telle que la solution optimale n’est pas remise en cause. Plus cette
possibilité est importante, et plus la solution optimale est sûre, fiable, stable. Elle peut
être appliquée sans risque. Dans le cas inverse, la solution optimale est instable et de
ce fait, il sera peut être nécessaire avant d’agir, de réaliser une étude plus approfondie
des coefficients douteux de la fonction économique. En tout cas, la solution optimale
ne devra être appliquée qu’avec de grandes précautions.
Le problème à résoudre est donc le suivant :
Dans quel intervalle les coefficients
De la fonction économique peuvent-ils varier sans que soit remise en cause en cause la
structure de la solution optimale ?
Prenons le cas de la Société Bonvin S.A : si la marge sur coût variable di vin
« extra »(400) est appelée à varier, quelle variation peut elle supporter sans que la
solution optimale ne change ?

a) Evaluation graphique :

Si C1 représente la marge sur coût variable de la qualité « extra », le graphique 2

illustre que toute modification de cette marge provoque une variation de la pente de la
droite représentative de la fonction économique Z.

Cette pente a pour valeur -c1 , car :

500

7
Dualité et sensibilité 02/06/2014

-
Z= c1X1+500X2 → X1= X2
Cependant, tant que la valeur de la pente de Z reste comprise entre :
-la valeur de la pente de la droite(2) associée à la contrainte (pente= -0.5)
-et la valeur de la pente de la droite (4) associée à la contrainte (pente= -∞) alors
la solution optimale ne change pas. Donc si la marge «c 1 » est telle que :

-∞≤- ≤ -0.5, soit 250≤ c1

Alors la solution optimale reste la base B de coordonnées X1=20000 et X2 = 10000. En

revanche, si c1<250 cesse d’être solution optimale et la base L devient la nouvelle

solution optimale.

8
Dualité et sensibilité 02/06/2014

Une étude semblable peut être appliquée à la marge sur coût variable c 1 du vin
« supérieur » :
-si 0 ≤ c1 ≤800 la solution de base B reste optimale ;
-si c1 >800 la solution L devient nouvelle base optimale.
Enfin dans le cas où les deux marges «c1 » et « c1» se modifient conjointement.

-si ≥ 0.5, B reste solution optimale ;

-si le rapport < 0.5 alors L devient solution optimale.

b) Evaluation algébrique :

Lorsque toute solution graphique est exclue, la méthode employée pour mesurer la
sensibilité consiste à paramétrer les coefficients douteux.

Si la marge sur coût variable du vin « extra » est jugée incertaine, la valeur de cette
marge s’exprime par l’expression 400(1+λ), où λ est un paramètre pouvant prendre
n’importe quelle valeur sur IR. Si λ=0 la valeur de la marge est celle d’origine, soit
400.

Puisqu’une donnée économique initiale est modifiée, il convient de calculer à nouveau

les coefficients de la fonction économique. Et cela, non pas à partir de la base
originelle, mais tout simplement dans la base optimale déterminée précédemment. En
outre, il convient de noter que le changement ne peut affecter que les coefficients de Z
et ne modifie en rien les coefficients des contraintes ou leur second membre.

Tableau
Le fait de paramétrer le coefficient économique c1 de X1 provoque une modification du
critère du simplexe pour e4. Le nouveau coefficient de e4 s’écrit :

-150 - 400 λ.

9
Dualité et sensibilité 02/06/2014

Dans un problème de maximisation, l’optimum est atteint lorsque tous les coefficients
sont négatifs ou nuls dans la fonction économique. Ici, cette condition est respectée si :
-150 - 400 λ ≤ 0 ==> λ ≥ -0,375.
Ainsi, la solution proposée précédemment reste solution optimale si, et seulement si,
λ ≥ -0, 375, c’est-à-dire si le coefficient économique c1 de X1 est tel que :
c1 ≥ 400(1- 0.375)
c1 ≥250
Dans le cas présent, il n’existe pas de borne supérieure pour c1. Donc X1 = 20000 et X1
=10000 reste optimale pour que la marge sur coût variable du vin « extra » reste
supérieure à 250.
Si, en revanche, cette marge prend une valeur inférieure à 250, alors la solution
correspondant à la base B cesse d’être optimale puisque le coefficient de e1 est positif.
Il faut réaliser une itération :
-La variable entrant dans la nouvelle base est e4.
-la variable sortant de la base est e4.
-la nouvelle base optimale correspondant à L (de coordonnées X1=15000 et
X1=12500)
Si la marge sur coût variable du vin « supérieur » est susceptible de varier dans la
Proportion β, il convient de paramétrer le coefficient c1 de X1 dans la fonction
économique. La fonction B reste solution optimale si :
1. coefficient de e4 :

- (1= β) ≤0 → β ≥ -1
2. coefficient de e4 :
-150+250 β≤0 → β≤0.6
Donc si, -1 ≤β≤ 0.6.

Lorsque plusieurs coefficients sont simultanément imprécis ou incertains, l’étude

devient plus complexe. Dans le cas présent, si les deux marges ( du vin « extra » et du
vin « supérieur ») varient conjointement, la solution proposée reste optimale si les
conditions suivantes sont respectées :

10
Dualité et sensibilité 02/06/2014

1. β ≥ -1 → c1 ≥ 0

2. λ≥ β- → c1 ≥ 250(1+ β)

L’analyse de la sensibilité exposée ci-dessus a été appliquée au cas de variables « en

base » à l’optimum. Lorsqu’il s’agit de variables « hors base », l’étude est très
simple. Dans le cas d’un problème de maximisation :

-Le coefficient de la variable hors base dans la fonction économique initiale peut
diminuer indéfiniment sans que la solution optimale ne soit modifiée ;

-lorsque le coefficient de la variable hors base augmente (dans la fonction économique

initiale), la limite supérieure de cet accroissement est équivalente, en valeur absolue,
au coût marginal associé à la variable dans la fonction économique optimale. Si
l’accroissement dépasse ce coût marginal, alors il convient de changer de solution
optimale.

2. la variation du second membre des contraintes

Dans un problème de production, les seconds membres des contraintes concernant des
ressources disponibles, des capacités de production ou des capacités d’absorption du
marché. Des erreurs ou des incertitudes peuvent perturber l’évaluation de ces
données. Mais outre ces problèmes d’erreurs et d’incertitude, il peut être intéressant
pour l’entreprise de s’interroger sur les conséquences d’une variation de ses ressources
ou de ses capacités de vente.

Certes l’analyse des coefficients de la fonction économique à l’optimum permet de

répondre à ces préoccupations. Ainsi dans le cas de Bonvin un hectolitre

supplémentaire de cru du Bordelais permettrait d’accroitre sa marge de F

(valeur du coût marginal d’opportunité de cette ressource). D’où l’intérêt d’acquérir
une quantité supplémentaire de cru du Bordelais. Mais quelle quantité ? Car si dans
l’immédiat, ce cru du Bordelais est la ressource rare qui limite la production, le fait

11
Dualité et sensibilité 02/06/2014

d’en acquérir une quantité supplémentaire risque de modifier la situation. Cette

ressource peut devenir pléthorique auquel cas son intérêt économique (son coût
marginal) devient nul alors que dans le même temps une autre ressource devient rare.

Par conséquent, la problématique de l’étude des variations des seconds membres

s’énonce comme suit : dans quelle mesure est-il possible de modifier la valeur du
second membre d’une contrainte sans changer la valeur du coût marginal de cette
contrainte à l’optimum ?

Lorsque le second membre d’une contrainte varie, les coefficients de la fonction

économique optimale ne sont affectés que si cette variation est d’une ampleur telle
qu’elle suscite un changement de structure de la solution optimale. Comme les
variables constituant la base optimale ont changé, les coûts marginaux sont modifiés.

Le changement de base provient du fait que la variation du second membre suscite une
déformation du domaine des solutions admissibles. Une déformation importante rejette
l’ancienne base optimale hors du domaine des solutions admissibles. Si dans le cas de
Bonvin les ressources en cru du Bordelais sont accrus de 50%, la solution de base
B(ancien optimum) est en dehors du domaine des solutions admissibles, et le nouvel
optimum correspond à la base I ( intersection des droites(4) et (5) sur le graphique).

12
Dualité et sensibilité 02/06/2014

Soit un problème de maximisation comportant des contraintes ≤. Dans quel intervalle

les seconds membres des contraintes peuvent-ils varier sans remettre en cause la
structure de la solution optimale et donc la valeur des coûts marginaux des contraintes
à l’optimum ?

Dans le cas d’une contrainte non saturée :

-le second membre peut augmenter indéfiniment sans modification des coûts
marginaux ;

-il peut diminuer d’une valeur égale au plus à la valeur prise par la variable d’écart
associée à la contrainte.

Dans le cas Bonvin, le second membre de la contrainte concernant la ressource en cru

de l’Hérault doit ainsi rester supérieure à 12000.

13
Dualité et sensibilité 02/06/2014

Quand il s’agit d’une contrainte saturée à l’optimum telle que la contrainte n°2 il est
possible de recourir à la technique du paramétrage.

Une méthode consiste à paramétrer le second membre en question dans la solution de

base initiale. Dans le cas de la contrainte n°2, il devient :

12000(1+λ)

A l’optimum, seules les variables « en base » ont une valeur affectée par l’introduction
du paramètre λ. Les variables « hors base »conservent une valeur nulle (e2 et e4 en
l’occurrence), le système à m équations (les contraintes) et à m variables (X1, X2, e1, e3,
e5, e6 et e7) peut être résolu : il fournit directement la valeur des variables à l’optimum.
Cette valeur est exprimée en fonction du paramètre λ.

TABLEAU

Pour que la structure de la solution optimale ne change pas, il faut que tous les seconds
membres soient positifs ou nuls. Donc

1600-4000 λ≥0 → λ ≤ 0.4

4400-4000 λ≥0 → λ ≤ 1.1

10000+20000 λ≥0 → λ ≤ -0.5

6000-20000 λ ≥0 → λ ≤0.3

5000+20000 λ≥0→ λ≥-0.25

Finalement, si le paramètre λ vérifie les conditions :

14
Dualité et sensibilité 02/06/2014

-0.25≤ λ≤0.3

C’est-à-dire si le second membre de la deuxième contrainte prend une valeur sur

l’intervalle : 9000≤ second membre≤ 15600,

Alors la structure de la solution optimale ne change pas(les variables e 1, X1, e3, X2, e5,
e6 et e7 restent « en base »), non plus que les coûts marginaux.

Par conséquent, Bonvin pourrait acquérir jusqu’à 3600 hectolitres supplémentaires de

vin du Bordelais tout en dégageant une marge de par hectolitre

(supplémentaire).la marge totale liée à cette opération serait alors :

3600* =3000000 F.

Au-delà de 3600 hectolitres supplémentaires, la structure de la solution optimale

change :

e2 entre en base, e5 sort de la base

et de ce fait les coûts marginaux changent également, et en particulier le coût marginal

associé à la deuxième contrainte devient nul, donc toute acquisition supplémentaire de
vin du Bordelais, au-delà de 3600 hectolitres n’aurait aucun intérêt économique pour
Bonvin.

Une seconde méthode utilisant les propriétés de la dualité est envisageable pour
l’étude de la sensibilité de la solution optimale par rapport à une modification du
second membre d’une contrainte. En effet, il suffit de constater que paramétrer le
second membre d’une contrainte du programme primal est équivalent à paramétrer le
coefficient correspondant dans la fonction économique du programme dual.

15
Dualité et sensibilité 02/06/2014

ANNEXE :

Exercice1 :
On considère le programme linéaire :

Min Z =4000X1+6000X2+6000X3
S.C : X1, X2, X3 ≥ 0
X1+X3 ≥ 4
X2+⅔X3 ≥ 3
1-Ecrire puis résoudre le programme dual associé.
2-En déduire la solution du programme primal.
3-Retrouver la solution du primal à l’aide des relations d’exclusion.

Exercice 2 :
Un restaurateur dispose de 880 oursins et de 720 huitres. Il propose à
Sa clientèle deux types d’assiette : assiette à 30 euros (4 oursins, 1 huitre), assiette à 20
euros (2 oursins, 3 huitres).
1 - Combien d’assiettes de chaque catégorie doit-il vendre pour maximiser sa recette?
2 - Le restaurateur dispose en fait de 900 oursins et de 750 huitres. Quelle est sa
Recette maximale ?
3 - On revient aux conditions de la première question. Poser, résoudre et interpréter le
programme dual.

Exercice 3 :
Une entreprise fabrique deux produits A et B à partir de deux matières premières M1 et
M2. Une tonne de M1 permet d’obtenir 600 kg de A et 400 kg de B. Une tonne de M2
permet d’obtenir 200 kg de A et 700 kg de B. Il faut fabriquer au moins 25 tonnes de A
et 28 tonnes de B par mois. Le traitement d’une tonne de M1 coute 2 000
Euros et celui d’une tonne de M2 coute 4 000 euros. Quel est le programme de
production qui minimise le coût de production en satisfaisant la demande ?

16
Dualité et sensibilité 02/06/2014

Bibliographie :

Michel Simonnard « Programmation linéaire »,1

Fondement, Edition Dunod, paris 1972 ;

Jean Pierre Védrine « Techniques quantitatives de

gestion », Edition Vuibert, mars 1985 ;

Yves, Nobert, Roch Ouellet, Régis Parent « La recherche

opérationnelle »,2ème édition, Gaëtan Morin . .

Cours :
Professeur BENMLIH « Théorie de la décision 1 »,
« programmation linéaire », cours 5ème semestre.

Webographie :

http://roso.epfl.ch/cours/ro/2005-2006/cours/Dualite.pdf
http://www.lri.fr/~mdr/pl.htm
http://www.esiee.fr/~talboth/ESIEE/IF4-
ALG2/pdf/04_dualite.pdf
http://www.lama.univ-savoie.fr/~saber/proglin3.pdf

17