Make your own free website on Tripod.com

INDEX

II. Dualité

a. Définition

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 :

  1. Les termes du second membre deviennent les coefficients de la fonction objectif et réciproquement.
  2. Le problème de maximisation devient un problème de minimisation.
  3. Les inégalités deviennent des inégalités
  4. La matrice A se transforme en sa transposée.

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/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

xj = 0 Þ Cj - zj < 0

xj > 0 Þ Cj - zj = 0

variables d’écart

Li = | Cj - zj | ¹ 0 Þ Cj - zj = 0

Li = 0 Þ Cj - zj = xj

variables d’écart

Sj = 0 Þ Cj - zj ¹ 0

Sj > 0 Þ Cj - zj = 0

Variables de décision

yi = | Ci - zj | ¹ 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.

 c. Tableau de correspondance primal-dual

Max

Min

  • Matrice des contraintes (m, n)

- 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 £ 1

x1 £ 2

x1 ³ 0, x2 ³ 0

Min 3y1 + y2 + 2y3

S.c y1 - y2 + y3 ³ ½

y1 + y2 ³ 1

y1 ³ 0, y2 ³ 0, y3 ³ 0

Min - x1 + x2

S.c 2x1 - x2 ³ 2

- x1 + 2x2 ³ -2

x1 + x2 £ 5

x1 ³ 0, x2 ³ 0

Max 2y1 - 2y2 + 5y3

S.c 2y1 - y2 + y3 £ -1

- y1 + 2y2 + y3 £ 1

y1 ³ 0, y2 ³ 0, y3 £ 0

Max 2x1 - x2

S.c x1 - x2 = 3

x1 £ 4

x1 ³ 0, x2 ³ 0

Min 3 y1+ 4 y2

S.c y1+ 2 y2 ³ 2

- y1 ³ -1

y1Î IR, y2 ³ 0

Max 2x1 - x2

S.c x1 - 2x2 £ 2

x1 + x2 = 6

x2 £ 5

x1Î 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