INDEX 
II. Dualité
La forme d’un programme linéaire de type maximisation est
avec 
, 
des vecteurs de dimensions respectives 
et 
, et A une matrice de dimension 
On appelle programme dual de , le programme linéaire suivant :
avec 
un vecteur de dimension 
et 
la transposée de la matrice 
.
Le programme est appelé programme Primal.
Pour passer du primal au dual, on remarque que :
deviennent des inégalités 
Exemple : Le programme primal (problème de l’agriculteur) est
, 
Donc le programme dual est
, 
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 
le prix d'un hectare de terrain
le prix d’un 
d’eau
le prix d’une heure de main d’œuvre
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 
sous la contrainte que les prix satisfont notre agriculteur.
Pour notre agriculteur un hectare de terrain 
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, 
d’eau et 4 heures de travail lui engendrent un revenu de 200 dinars.
Il n’est prêt à vendre ses ressources que si 
lui rapporte un revenu supérieur ou égale à 100 DT et que si 
lui rapporte un revenu supérieur ou égal à 200 DT.
Ainsi le problème du client est
,
Donc le problème du client peut être modélisé par le programme dual.
Le tableau de simplexe final du programme dual est :
|
|
|
|
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/3y2 = 0
« C2 - z4 = 0y3 = 100/3
« C5 - z5 = - 100/3y4 = 0
« C6 - z6 = 0L1 = 0
« C1 - z1 = 0L2 = 0
« C2 - z2 = 0C1 - z1 = 0
« S1 = 0C2- z2= 60
« S2 = 60C3- z3 = 0
« S3 = 0C4 - z4= 50
« S4 = 50C5 - z5= 40
« x1 = 40C6 - z6= 110
« x2 = 110w = 26000
« z = 260000On peut généraliser ce résultat dans le tableau suivant :
|
Primal (Max) |
Dual (Min) |
|
Variables de décision xj = 0 Þ Cj - zj < 0xj > 0 Þ Cj - zj = 0 |
variables d’écart Li = | Cj - zj | ¹ 0 Þ Cj - zj = 0Li = 0 Þ Cj - zj = xj |
|
variables d’écart Sj = 0 Þ Cj - zj ¹ 0Sj > 0 Þ Cj - zj = 0 |
Variables de décision yi = | Ci - zj | ¹ 0 Þ Cj - zj = 0yi = 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.
c. Tableau de correspondance primal-dual|
Max |
Min |
- Second membre des contraintes - Coefficient de la fonction objectif |
- Transposée de la matrice des contraintes (n, m) - Coefficient de la fonction objectif - Second membre des contraintes |
|
Nombre de contraintes i ème contrainte de type " £ "i ème contrainte de type " ³ "i ème contrainte de type " = " |
Nombre de variables principales i ème variable de type " ³ 0 "i ème variable de type " £ 0 "i ème variable qcq " Î IR " |
|
Nombre de variables j ème variable " ³ "j ème variable " £ "j ème variable qcq " Î IR " |
Nombre de contraintes j ème contrainte de type " ³ "j ème contrainte de type " £ "i ème contrainte de type " = " |
Exemples
|
Primal |
Dual |
|
Max ½ x1 + x2 S.c x1 + x2 £ 3- x1 + x2 £ 1x1 £ 2x1 ³ 0, x2 ³ 0 |
Min 3y1 + y2 + 2y3 S.c y1 - y2 + y3 ³ ½y1 + y2 ³ 1y1 ³ 0, y2 ³ 0, y3 ³ 0 |
|
Min - x1 + x2 S.c 2x1 - x2 ³ 2- x1 + 2x2 ³ -2x1 + x2 £ 5x1 ³ 0, x2 ³ 0 |
Max 2y1 - 2y2 + 5y3 S.c 2y1 - y2 + y3 £ -1- y1 + 2y2 + y3 £ 1y1 ³ 0, y2 ³ 0, y3 £ 0 |
|
Max 2x1 - x2 S.c x1 - x2 = 3 x1 £ 4x1 ³ 0, x2 ³ 0 |
Min 3 y1+ 4 y2 S.c y1+ 2 y2 ³ 2- y1 ³ -1y1 Î IR, y2 ³ 0 |
|
Max 2x1 - x2 S.c x1 - 2x2 £ 2x1 + x2 = 6 x2 £ 5x1 Î IR, x2Î IR |
Min - 2y1 + 6y2 - 5y3 S.c y1 + y2 = 2 - 2y1 + y2+ y3 = -1 y1 ³ 0, y2 Î IR, y3 ³ 0 |
Cliquer ici pour enregistrer le chapitre 5 en format Word sur votre disque dur (371 Ko)
Pour tout commentaire envoyer un mail à hatem_masri@yahoo.com