Cours sur la dualité

Description

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

Informations

• Publié par: Udde
• Nombre de lectures: 53
• Langue: Français

Extrait

Chapitre 2

Dualite´

2.1 Introduction Avantdedonnerladefinitionformelled’unprobl`emedual,nousallonsexpliquercom mentils’expliqueentermedeproble`medeproduction. Une entrepriseIfabriquendepuin´tapurfieecitroduebtln´´eodprteuiiestc i . Pour fabriquer les produits l’entreprise utilisemrpse`imeserelte,atmeri`edaquantit´etotale matie`rejestb j tiuitunar.Podprde´ei, il fauta i,j e`erqit´euantmatidelaj. PourI, maximisersonbe´ne´ficerevient`ar´esoudre: M axz=cx Ax≤b x≥0    x 1 b 1 . . avecA(m, n), c(1, n) = (c 1 , . . . , c n ), x(n,1) =  , b(m,1) =   qu’on appelle le  .   .  x n b m proble`meprimal. Une entrepriseIIpropose de racheter les ressources deIpour sa propre production. Quandestcequelatransactionpeutsefaire?QuandIneperdpas`avendresesmatie`res premie`resplutotquedefabriquersesproduits.DeplusIIveut payer le prix le plus bas possible. On posey j pe´soporraxprieplIIa`Itpit´earunoduideprj. LecoˆutpourIIest J=M ω= Σy j b j j=1 Lescontraintesrepr´esententquepourIlpeirdxveneet`at)uidorpede´tinurap(IIest pluseleve´oue´galaube´n´eficepourchaqueproduit. pouruneunit´edeproduiti: j=m Σ j=1 y j a j,i ≥c i et´evidemmenty j ≥0 pour toutj.

1

2

´ CHAPITRE 2.DUALITE

Celas’e´crit: M inω=yb yA≥c y≥0 qu’on appelle lealdumee`lborpere´nassuoptr.Lodlmuaede´ilesiasnlifeiatqu’ilestplusint Indve`areedIIque de fabriquer et aussi queIIorpa`ehcrehcbssaeplurixlrleppose possible.

2.2 Definition Definition 1`lbodemePrpnul´eePL(appeprimal) sous la forme canonique : M axz=cx Ax≤b x≥0 avecA(m, n), c(1, n), x(n,1), b(m,1)alorroblslepeme`laud:tse M inω=yb yA≥c y≥0 avecy(m,1) Proposition 1Le dual du dual est le primal. Rappel:latranspos´eed’unematriceA(m, n) = (a i,j ) est la matricet A (n, m) = (a j,i ). On at=Aett=t t,t=−t, siA≤Balorst≤t. t A AAB B−A BA A On met le dual sous forme canonique : −ωM ax=−yb −yA≤ −c y≥0 puis −M axω=t −b u t −A u≤t −c u≥0 (avecu=t y ) dont on calcule le dual −ωM in=vt −c vt −A ≥t −b v≥0

2.3. LIENPRIMALDUAL

3

on´elimineles1 M axω=vt c vt A ≤t b v≥0 on transpose et on obtient en posantx=t v M axω=cx Ax≤b x≥0 Definition 2ppleLPa(emedlbe`nproPu´eprimal) sous la forme standard : M axz=cx Ax=b x≥0 avecA(m, n), c(1, n), x(n,1), b(m,1)roep`ebldumeesal:tlalsro M inω=yb yA≥c y quelconque avecy(m,1) Proposition 2alivteenntsoqu´e.s´exdeusdnsioitfineL Celasignifiequepartantd’unproble`meenformecanonique,sionletransformeen proble`mestandardauquelonappliqueledual,onaunre´sultate´quivalent`aceluiobtenu encalculantdirectementledualduproble`meinitial(etidemsionpartdupbstandard).

2.3 LienPrimalDual 2.3.1 Comparaisondes solutions OnprendPenformecanoniqueetDsondualetonconsid`erexetydeuxsolutions quelconques du primal et du dual. Commex≥0 ety≥0 on peut multiplier les contraintes du primal paryet du dual parxpour obtenir : cx≤yAx≤yb Cela est valable pour toutes solutionsxdu primal,ydu dual. Donc l’optimum du primal estforcementinf´erieuroue´gala`celuidudual.Autrecons´equence,siontrouvexsolution du primal etysolution du dual telles quecx=ybalors ont sait qu’elles sont optimales et que l’optimum estz=ω=cx=yb.

´ 4DUALITECHAPITRE 2. 2.3.2Th´eor`emededualite´ Onadmetler´esultatsuivant:´etantdonn´esunematriceA, deux vecteursbetc, alors {cxM ax|Ax≤b}={min yb|yA=c, y≥0}si les ensembles existent. Doncquandlesoptimadesproble`mescorrespondantssontfinisilssonte´gaux.Avoir prisunprobl`emeprimalsouslaformezM ax=cxn’est pas restrictif car on Ax≤b x quelconque peutramenerunprobl`emestandardoucanonique`acetteformeenpr´eservantl’optimum.

Letableausuivantre´capitulelasituation(th.dedualite´).

optimumfini pasd’optimumfini pas de solution

Exemples

optimumfini cas 1 impossible impossible

pasd’optimumfini impossible impossible cas 2

pas de solution impossible cas 2 cas 3

Cas 1.M axz=x 1 +x 2 et le dualM inz=y 1 −x 1 +x 2 = 1−y 1 +y 2 ≥1 x 1 −1/2x 2 = 0y 1 −1/2y 2 ≥1 x 1 , x 2 ≥0y 1 , y 2 quelconques x∗= (1,2), y∗= (3,4) admissibles etz∗=ω∗= 3 donc optimales.

Cas 2.M axz=x 1 −x 2 et le dualM inz=y 1 −x 1 +x 2 = 1−y 1 +y 2 ≥1 x 1 −x 2 = 0y 1 −y 2 ≥ −1 x 1 , x 2 ≥0y 1 , y 2 quelconques Pasdesolutionauprimalmaispossibilit´edesolutionadmissibley 1 =α, y 2 =α+ 1 pour le dual avecαaussi petit que voulu, donc pas d’optimum fini.

Cas 3.zM ax=x 1 +x 2 et le dualzM in=y 1 −x 1 +x 2 = 1−y 1 +y 2 ≥1 x 1 −x 2 = 0y 1 −y 2 ≥1 x 1 , x 2 ≥0y 1 , y 2 quelconques Pas de solution ni au primal ni au dual.

´ 2.4. CONDITIOND’OPTIMALITE PRIMALESDUALES5 2.4Conditiond’optimalite´primalesduales Onconside`reunproble`meprimalenformecanonique: M axz=cxet le dualM inω=ybalors Ax≤b yAx≥c x≥0y≥0 Proposition 3Soitx∗ety∗deux solutions admissibles du primal et du dual. Alorsx∗ety∗:sotnoimptesalilsscoesdntioisnusvinaetssontr´ealis´ees ∗i=n∗ –y(b j −Σa j,i x) = 0pourj= 1, . . . , m j i=1i j=m ∗ –(Σy j a j,i −c i )x= 0pouri= 1, . . . , n j=1 i Attentionopyhe`htse’L:x∗ety∗solutionelrb!s!esentea´semcdsssiiias Preuve : Six∗, y∗solutions alors elles satisfont les contraintes : y∗A≥cetAx∗ ≤b Onmultiplielapremie`reine´galit´eparx∗ ≥0 et la seconde pary∗ ≥0 ce qui donne y∗Ax∗ ≥cx∗ety∗Ax∗ ≤y∗b c.a.d. y∗b≤y∗Ax∗ ≤cx∗ Conditionn´ecessaire:Six∗ety∗ltsemumit(emeˆmealesalimpt’oslorot.thpsno dedualite´): cx∗=y∗b D’o`u: y∗b=y∗Ax∗=cx∗ d’o`uontirelesdeux´egalite´s y∗(b−Ax∗) = 0et(y∗A−c)x∗= 0 Tous lesy∗ j etx∗ i sont≥>0 etb−Ax∗ ≥0 tout commey∗A−c≥0 donc tous les termesdesdeuxproduitssontne´cessairementnulscequidonnelesdeuxse´ried’e´galit´es. Condition suffisante :Si les conditions sont vraies on a : y∗b=y∗Ax∗et y∗Ax∗=cx∗ donclesdeuxfonctionsobjectifsont´egalesetdoncx∗ety∗sont optimales. Remarque:sileprimalestenformestandard,alorslapremie`re´egalit´eest´evidentecar Ax∗=bet donc tous les coefficients dey∗ i sont nuls.