Cours sur la dualité

Chapitre 2Dualit´e2.1 IntroductionAvant de donner la definition formelle d’un probl`eme dual, nous allons expliquer com-ment il s’explique en terme de probl`eme de production.Une entreprise I fabrique n produit et le b´en´efice par unit´e du produit i est c . Pourifabriquer les produits l’entreprise utilise m mati`eres premi`eres, et la quantit´e totale demati`ere j est b . Par unit´e de produit i, il faut a quantit´e de la mati`ere j. Pour I,j i,jmaximiser son b´en´efice revient `a r´esoudre :Max z = cxAx≤ bx≥ 0   x b1 1   . .   avec A(m,n),c(1,n) = (c ,...,c ),x(n,1) = ,b(m,1) =  qu’on appelle le1 n    . .x bn mprobl`eme primal.Une entreprise II propose de racheter les ressources de I pour sa propre production.Quand est-ce que la transaction peut se faire? Quand I ne perd pas `a vendre ses mati`erespremi`eres plutot que de fabriquer ses produits. De plus II veut payer le prix le plus baspossible. On pose y le prix propos´e par II `a I par unit´e de produit j.jLe couˆt pour II estJ=Mω = Σ y bj jj=1Les contraintes repr´esentent que pour I le prix de vente (par unit´e de produit) `a II estplus elev´e ou ´egal au b´en´efice pour chaque produit.pour une unit´e de produit i :j=mΣ y a ≥ cj j,i ij=1et ´evidemment y ≥ 0 pour tout j.j1´2 CHAPITRE 2. DUALITECela s’´ecrit :Min ω = ybyA≥ cy ≥ 0qu’on appelle le probl`eme dual. Le dual mod´elise ainsi le fait qu’il est plus int´eressant pourI de vendre `a II que de fabriquer et ...