[PDF] [PDF] Programmation Linéaire - Recherche Opérationnelle

View - Download [PDF] Programmation Linéaire - Recherche Opérationnelle

Previous PDF

Next PDF

Introduction

Introduction

Rechercheop erationnelle

resolutiondeprobl emes d'optimisation, aide a lad ecision

Introduction

Introduction

Rechercheop erationnelle

resolutiondeprobl emes d'optimisation aide alad ecision

Introduction

Origine

En 1940,au coursde laseconde guerremondiale, legouv ernement anglaisc harge PatrickBlackett dedirigerune equipe derecherchepourr esoudrecertains problemestelsque l'implantationoptimale deradars desurv eillance, la gestiondes conv oisd'approvisionnement. Le termeoperationnellevientdu faitque letra vail dugroup eetaitlie a des operationsmilitaires.Apr es laguerre, cestec hniquesse sontconsid erablement developp eesdufaitdela multiplication desdomaines d'application,l'explosion descapacitesdecalcul desordinateurs.

Introduction

Origine

En 1940,au coursde laseconde guerremondiale, legouv ernement anglaisc harge PatrickBlackett dedirigerune equipe derecherchepourr esoudrecertains problemestelsque l'implantationoptimale deradars desurv eillance, la gestiondes conv oisd'approvisionnement. Le termeoperationnellevientdu faitque letra vail dugroup eetaitlie a des operationsmilitaires.

Apreslaguerre, cestec hniquesse sont considerablement d eveloppees dufaitdela multiplicationdesdomaines d'application,

l'explosion descapacit esdecalculdesordinateurs.

Introduction

La ROestg en eralementestlieeaplusieursdomaines:

Mathematiquesappliqu ees,Informatique,

EconomieLes

applicationssontnom breuses:les cha^neslogistiques,la planication,la gestionde production,l'ordonnancement,la gestiondesstoc ks,les problemesd'ing enierie,lesreseaux det elecommuni cation, etc...

Introduction

La ROestg en eralementestlieeaplusieursdomaines:

Mathematiquesappliqu ees,Informatique,

Economie

Les applicationsson tnombreuses: les cha^neslogistiques,laplanication, la gestionde pro duction,l'ordonnancement,lagestiondes stocks, les problemesd'ingenierie, lesreseauxdet el ecommunication, etc...

Programmation lineaire

Sommaire

1

Introduction2

Programmation lineaireFormulationduprobl eme

Methodeetinterpr etation

graphiqueAlgorithme dusimplexe

Detaildel'algorithme

Programmation lineaireFormulationdup robl eme

Formulationduprobl eme

Programmation Lineaire(PL)=optimisation d'unefo nctio nlinaire dev ariables devantsatisfaireun ensemble decon trainteslin eairesde typeinegalit eset/ou egalites. opt z=f(x) g(x)d h x ) =b x i0 avecx= (x1;:::;xn) lesv ariablesded ecision. Les composantesd'une probl emedePLsont:les variables :ce sont lesvaleurs atrouv er,lasolutiondu probleme[ x],les contraintes: donnel'espace dessolutions admissibles[ g(),d,h(),b],qu'est-ce qu'onveutoptimiser ?[f()].

Programmation lineaireFormulationdup robl eme

Formulationduprobl eme

Programmation Lineaire(PL)=optimisation d'unefo nctio nlinaire dev ariables devantsatisfaireun ensemble decon trainteslin eairesde typeinegalit eset/ou egalites. opt z=f(x) g(x)d h x ) =b x i0 avecx= (x1;:::;xn) lesv ariablesded ecision.

Les composantesd'uneprobl eme dePLsont:les variables:ce sont lesv aleursatrouv er,la solutionduprobl eme[x],les contraintes:donnel'espace dessolutions admissibles[ g(),d,h(),b],qu'est-ce qu'onv eutoptimiser?[ f()].

Programmation lineaireFormulationdup robl eme

Problemesd'optimisationlin eaire souscontraintes:

fonction economique opt z=c1x1+c2x2+:::cnxn contraintes 8 >>:t

11x1+t12x2+:::+t1nxnd1

t

21x1+t22x2+:::+t2nxnd2

t m

1x1+tm2x2+:::+tmnxndm

non-negativite x i0i= 1;:::;n (ici, nous ecrivonsseulementdescon traintesin egal ites)

Programmation lineaireFormulationdup robl eme

Exemple 1

Une entreprisefabrique2 produits, AetB, apartirde 3mati eres di erentes,M1, M

2etM3:pourfabri querA, ilf aut1tonnede M1et 2tonnes deM2,pourfabri querB, ilfaut 1tonne deM1, 1tonne deM2et 1tonne deM3.

La ventede1tonne deArapporte150 ¿tandis quela ven tede1tonnedeB rapporte100 ¿.

L'entreprisep ossedeunstockde :300 tonnesde M1,400 tonnesde M2,250 tonnesde M3.FQuestion:combienfaut-il fabriquerde produits AetBpourav oirlemaximum

de benece?

Programmation lineaireFormulationdup robl eme

Exemple 1

Une entreprisefabrique2 produits, AetB, apartirde 3mati eres di erentes,M1, M

2etM3:pourfabri querA, ilf aut1tonnede M1et 2tonnes deM2,pourfabri querB, ilfaut 1tonne deM1, 1tonne deM2et 1tonne deM3.

La ventede1tonne deArapporte150 ¿tandis quela ven tede1tonnedeB rapporte100 ¿. L'entreprisep ossedeunstockde :300 tonnesde M1,400 tonnesde M2,250 tonnesde M3. FQuestion :com bienfaut-ilfabriquerde produits AetBpourav oirlemaximum de benece?

Programmation lineaireFormulationdup robl eme

Analysons leprobl eme:

variables: x

1!nombrede produits A

x

2!nombrede produits B

le protest donn eparlesven tes: z= 150x1+ 100x2 les contraintessontli eesausto ckdesmatieres form ulationdu problemedePL: maxz= 150x1+ 100x2 x

1+x2300

2 x

1+x2400

x 2250
x i0i= 1;2

Programmation lineaireFormulationdup robl eme

Analysons leprobl eme:

variables: x

1!nombrede produits A

x

2!nombrede produits B

le protest donn eparlesven tes: z= 150x1+ 100x2 les contraintessontli eesausto ckdesmatieres formulationdu probl emedePL: maxz= 150x1+ 100x2 x

1+x2300

2 x

1+x2400

x 2250
x i0i= 1;2

Programmation lineaireFormulationdup robl eme

Exemple 2

Considerons3magasins, A,BetC, ayantcommande200 containerschacun.250 containerssontdisponibles audep^ otD1,450 containerssontdisponibles audep^ otD2.

Les co^utsdetransport parcon tainerssont: magasinA BC

dep^otD13:4 2:2 2:9dep^otD23:4 2:4 2:5Fobjectif: minimiserleco ^ut totaldetransportdescon tainersdes d ep^otsvers les

magasins.

Programmation lineaireFormulationdup robl eme

Exemple 2

Considerons3magasins, A,BetC, ayantcommande200 containerschacun.250 containerssontdisponibles audep^ otD1,450 containerssontdisponibles audep^ otD2.

Les co^utsdetransport parcon tainerssont: magasinA BC

dep^otD13:4 2:2 2:9dep^otD23:4 2:4 2:5Fobjectif: minimiser leco^ut totalde transportdescontainersdes d ep^ots versles

magasins.

Programmation lineaireFormulationdup robl eme

Analysons leprobl eme:

variables: x 1 A!nombrede containers depuisled ep^ot D1versle magasinA x 2 A!nombrede containers depuisled ep^ot D2versle magasinA (idem pourBetC:x1B,x2B,x1C,x2C) le co^uttotaldetransport estdonn e par: z= 3:4x1A+ 3:4x2A+ 2:2x1B+ 2:4x2B+ 2:9x1C+ 2:5x2C les contraintessontli eesala disponibilitedesd ep^otset a lademandedesmagasinsformulation duproblemedePL : minz= 3:4x1A+ 3:4x2A+ 2:2x1B+ 2:4x2B+ 2:9x1C+ 2:5x2C x 1

A+x1B+x1C250

x 2

A+x2B+x2C450

x 1

A+x2A= 200

x 1

B+x2B= 200

x 1

C+x2C= 200

x i0i= 1A;2A;1B;2B;1C;2C:

Programmation lineaireFormulationdup robl eme

Analysons leprobl eme:

variables: x 1 A!nombrede containers depuisled ep^ot D1versle magasinA x 2 A!nombrede containers depuisled ep^ot D2versle magasinA (idem pourBetC:x1B,x2B,x1C,x2C) le co^uttotaldetransport estdonn e par: z= 3:4x1A+ 3:4x2A+ 2:2x1B+ 2:4x2B+ 2:9x1C+ 2:5x2C

les contraintessontli eesala disponibilitedesd ep^otset a lademandedesmagasinsformulationdu probl emedePL:

minz= 3:4x1A+ 3:4x2A+ 2:2x1B+ 2:4x2B+ 2:9x1C+ 2:5x2C x 1

A+x1B+x1C250

x 2

A+x2B+x2C450

x 1

A+x2A= 200

x 1

B+x2B= 200

x 1

C+x2C= 200

x i0i= 1A;2A;1B;2B;1C;2C: Programmation lineaireMethodeetinterpr etation graphique

Methodeetinterpr etation graphique

La methodegraphiquepour resoudreun problemede PLestfaisableseulement pourdes probl emesa2,voire3, variables. Dans lecas d'unprobl eme a2variabl es,lescontrain tesp euvent^etretrac ees dans le plan a2dimensio ns( x1;x2). On peutalorsvisualiser l'espaced es solutionsadmissibles. Ilfautalors ensuite determinerlep oint duplan,decoordonn ees( x

1;x2), optimisantlafonction

economique.Reprenons le problemede l'exemple1 : maxz= 150x1+ 100x2 x

1+x2300(1)

2 x

1+x2400(2)

x

2250(3)

x i0i= 1;2(4) Programmation lineaireMethodeetinterpr etation graphique

Methodeetinterpr etation graphique

La methodegraphiquepour resoudreun problemede PLestfaisableseulement pourdes probl emesa2,voire3, variables. Dans lecas d'unprobl eme a2variabl es,lescontrain tesp euvent^etretrac ees dans le plan a2dimensio ns( x1;x2). On peutalorsvisualiser l'espaced es solutionsadmissibles. Ilfautalors ensuite determinerlep oint duplan,decoordonn ees( x

1;x2), optimisantlafonction

economique.

Reprenons leprobl emedel'exemple1:

maxz= 150x1+ 100x2 x

1+x2300(1)

2 x

1+x2400(2)

x

2250(3)

x i0i= 1;2(4) Programmation lineaireMethodeetinterpr etation graphique Representonsdansleplan (x1;x2), les5 contrain tes.x 1 x 2 (1) (4) (2) (3))Nous pouvons visualiserl'espace dessolutions admissibles. )Quel pointchoisir? Programmation lineaireMethodeetinterpr etation graphique Representonsdansleplan (x1;x2), les5 contrain tes.x 1 x 2 (1) (4) (2) (3))Nous pouvonsvisualiserl'espacedes solutionsadmissibles. )Quel pointchoisir? Programmation lineaireMethodeetinterpr etation graphique fonction objectif:z= 150x1+ 100x2 soit :x2=32 x1+z100x 1 x 2 Programmation lineaireMethodeetinterpr etation graphique fonction objectif:z= 150x1+ 100x2 soit :x2=32 x1+z100x 1 x 2 Programmation lineaireMethodeetinterpr etation graphique fonction objectif:z= 150x1+ 100x2 soit :x2=32 x1+z100x 1 x 2 -3/2 Programmation lineaireMethodeetinterpr etation graphique fonction objectif:z= 150x1+ 100x2 soit :x2=32 x1+z100x 1 x 2 x* Programmation lineaireMethodeetinterpr etation graphique x est lep oint(x1;x2) quimaximise leb en ecez.

La solutionxest appeleelasolution optimale.La solutionest a l'intersectiondescon traintes(1)et (2): (x1;x2) =(100 ;200)La valeurdub en eceestdonc:z= 35000¿.B

enecedansd'autres cas: equilibre entreles produits AetB!x1=x2= 130 )z= 32500¿pertede 7%maximum deproduitsA!x1= 200et x2= 0 )z= 30000¿pertede 14%maximum deproduitsB!x1= 0et x2= 250 )z= 25000¿pertede 29% Programmation lineaireMethodeetinterpr etation graphique x est lep oint(x1;x2) quimaximise leb en ecez.

La solutionxest appeleelasolution optimale.La solutionest a l'intersectiondescon traintes(1)et (2): (x1;x2) =(100 ;200)La valeurdub en eceestdonc:z= 35000¿.

Benecedansd'autrescas:equilibree ntrelesproduitsAetB!x1=x2= 130 )z= 32500¿pertede 7%maximum deproduitsA!x1= 200et x2= 0 )z= 30000¿pertede 14%maximum deproduitsB!x1= 0et x2= 250 )z= 25000¿pertede 29% Programmation lineaireMethodeetinterpr etation graphique x est lep oint(x1;x2) quimaximise leb en ecez.

La solutionxest appeleelasolution optimale.La solutionest a l'intersectiondescon traintes(1)et (2): (x1;x2) =(100 ;200)La valeurdub en eceestdonc:z= 35000¿.

Benecedansd'autrescas:equilibree ntrelesproduitsAetB!x1=x2= 130 )z= 32500¿pertede 7%maximumde produits A!x1= 200et x2= 0 )z= 30000¿pertede 14%maximum deproduitsB!x1= 0et x2= 250 )z= 25000¿pertede 29% Programmation lineaireMethodeetinterpr etation graphique x est lep oint(x1;x2) quimaximise leb en ecez.

La solutionxest appeleelasolution optimale.La solutionest a l'intersectiondescon traintes(1)et (2): (x1;x2) =(100 ;200)La valeurdub en eceestdonc:z= 35000¿.

Benecedansd'autrescas:equilibree ntrelesproduitsAetB!x1=x2= 130 )z= 32500¿pertede 7%maximumde produits A!x1= 200et x2= 0 )z= 30000¿pertede 14%maximumde produits B!x1= 0et x2= 250 )z= 25000¿pertede 29% Programmation lineaireMethodeetinterpr etation graphique

Exemple 3:

maxz= 6x1+ 5x2 x

1+x28 (1)

2 x

1+ 3x26 (2)

x

1x22 (3)

x i0i= 1;2 (4) Programmation lineaireMethodeetinterpr etation graphique Representonsdansleplan (x1;x2), les5 contrain tes.x 1 x 2 (1) (4) (2) (3) Programmation lineaireMethodeetinterpr etation graphique fonction objectif:z= 6x1+ 5x2 soit :x2=65 x1+z5x 1 x 2 x*La solutionest al'intersection descontraintes (1)et (3):(x1;x2) =(5 ;3)La valeur optimaleest donc: z= 9.21 /56 Programmation lineaireMethodeetinterpr etation graphique fonction objectif:z= 6x1+ 5x2 soit :x2=65 x1+z5x 1 x 2

x*La solutionest a l'intersectiondescon traintes(1)et (3): (x1;x2) =(5 ;3)La valeuroptimaleest donc: z= 9.

Programmation lineaireAlgorithmedu simplexe

Algorithme dusimplexe

Problemedeprogrammation lin eaire:

fonction economique opt z=c1x1+c2x2+:::cnxn contraintes 8 :t

11x1+t12x2+:::+t1nxnd1t

21x1+t22x2+:::+t2nxnd2

t m

1x1+tm2x2+:::+tmnxndm

non-negativite x i0i= 1;:::;nPo urresoudreceprobl eme quelquesoitladimension etdefaconsyst ematique, il existe l' algorithme dusimplexe . Unsi mplexeestunp oly edrec onvexedeRn possedant( n+ 1)sommets.

Programmation lineaireAlgorithmedu simplexe

Algorithme dusimplexe

Problemedeprogrammation lin eaire:

fonction economique opt z=c1x1+c2x2+:::cnxn contraintes 8 :t

11x1+t12x2+:::+t1nxnd1t

21x1+t22x2+:::+t2nxnd2

t m

1x1+tm2x2+:::+tmnxndm

non-negativite x i0i= 1;:::;n Pourr esoudreceproblemequ elque soitladimensionetde faconsystematique,i l existe l' algorithme dusimplexe . Unsi mplexeestunp oly edrec onvexedeRn possedant( n+ 1)sommets.quotesdbs_dbs28.pdfusesText_34

[PDF] interprétation droite de henry

[PDF] principe droite de henry

[PDF] exercice corrigé droite de henry

[PDF] courbe de henry excel

[PDF] droite de henry pdf

[PDF] programmation linéaire exercices corrigés pdf

[PDF] programmation linéaire exercices corrigés

[PDF] programmation linéaire simplexe

[PDF] recherche opérationnelle programmation linéaire exercices corrigés pdf

[PDF] exercices recherche operationnelle

[PDF] theme astral chinois complet gratuit interpretation

[PDF] cours recherche opérationnelle methode de simplexe

[PDF] recherche opérationnelle simplexe exercices corrigés

[PDF] livre recherche opérationnelle pdf

[PDF] cours et exercices corrigés de recherche opérationnelle+pdf