Outils et Logiciels d'Optimisation - Cours 1

P. Pesneau [e-mail]

Description

IntroductionTableurs et solveursOutils et Logiciels d’Optimisation - Cours 1P. [e-mail]´e Bordeaux 1Bˆat A33 - Bur 256P. Pesneau [e-mail] Outils et Logiciels d’Optimisation - Cours 1IntroductionTableurs et solveursMotivationsSyst`emes trop complexes pour qu’un humain puisse lesr´esoudre en prenant tout en compte (nombre de variables,nombre de contraintes, ...).La taille des probl`emes r´eels est tr`es grande.Capacit´e d’acc´eder `a des volumes de donn´ees ´enormes (basesde donn´ees, r´eseau informatique, ...)Acc`es `a de grosses capacit´es de calcul (Calcul parall`ele, calculdistribu´e, ...).Question : Comment acc´eder efficacement `a ces ressources?Utiliser des outils d’aide `a la d´ecision.Beaucoup de ces outils sont des logiciels d’optimisation.P. Pesneau [e-mail] Outils et Logiciels d’Optimisation - Cours 1IntroductionTableurs et solveursTrois ingr´edientsChaque outil de calcul est peut ˆetre compos´e de 3 ´el´ements :Un solveur : moteur d’optimisationUn langage de mod´elisation : communiquer avec le solveurUn environnement de d´eveloppement : ´editeurs et logiciels quipermettent de cr´eer le mod`eleCertains logciels comprennent ces trois ingr´edients, mais on peut´egalement les trouver s´epar´ement.P. Pesneau [e-mail] Outils et Logiciels d’Optimisation - Cours 1IntroductionTableurs et solveursLes solveursC’est le ...

Sujets

• informatique

Informations

• Publié par: Ossi
• Nombre de lectures: 94
• Langue: Français

Extrait

Introduction Tableurs et solveurs

Outils et Logiciels d’Optimisation  Cours 1

P. Pesneau pierre.pesneau@math.ubordeaux1.fr

Universite´Bordeaux1 BˆatA33Bur256

P. Pesneaupierre.pesneau@math.ubordeaux1.fr

Outils et Logiciels d’Optimisation  Cours 1

Motivations

Introduction Tableurs et solveurs

Syste`mestropcomplexespourqu’unhumainpuisseles r´esoudreenprenanttoutencompte(nombredevariables, nombre de contraintes, ...). Latailledesproble`mesr´eelsesttre`sgrande. Capacite´d’acce´der`adesvolumesdedonne´ese´normes(bases dedonn´ees,re´seauinformatique,...) Acc`esa`degrossescapacit´esdecalcul(Calculparalle`le,calcul distribue´,...).

Question :?secmeomCreffieacectnca´cdesressourment`ace Utiliserdesoutilsd’aide`alad´ecision. Beaucoup de ces outils sont des logiciels d’optimisation.

P. Pesneaupierre.pesneau@math.ubordeaux1.fr

Outils et Logiciels d’Optimisation  Cours 1

Introduction Tableurs et solveurs Troisingre´dients

Chaqueoutildecalculestpeuteˆtrecompose´de3e´le´ments: Un solveur : moteur d’optimisation Unlangagedemode´lisation:communiqueraveclesolveur Unenvironnementdede´veloppement:´editeursetlogicielsqui permettentdecre´erlemode`le Certainslogcielscomprennentcestroisingr´edients,maisonpeut e´galementlestrouverse´par´ement.

P. Pesneaupierre.pesneau@math.ubordeaux1.fr

Outils et Logiciels d’Optimisation  Cours 1

Les solveurs

Introduction Tableurs et solveurs

C’est le coeur des logiciels d’optimisation. C’est le module qui fait lecalculmath´ematique.

Plusieurs types de solveurs. Voici quelques exemples : Solveurslin´eaires(programmationline´aire):simplex,points int´erieurs,... Solveurnonlin´eaires(programmationnonlin´eaire):Newton, algorithmes de gradients, ...) Algorithmesdeflots:maximumflot,flotdecouˆtminimum,... Solveurspourlaprogrammationenti`ere:BranchandBound, heuristiques, ...

P. Pesneaupierre.pesneau@math.ubordeaux1.fr

Outils et Logiciels d’Optimisation  Cours 1

Introduction Tableurs et solveurs Leslangagesdemod´elisation

Ilspermettentded´efinirlesmod`elesmathe´matiquesdansun langagecompre´hensibleparlesolveurensuivantunesyntaxeetun vocabulaire.

Ilexisteplusieurslangagesdemod´elisation,Voiciquelques exemples : GNU Mathematical Programming AMPL (A mathematical Programming Language) IBMILOG OPL (Optimization Programming Language) Fico Mosel

P. Pesneaupierre.pesneau@math.ubordeaux1.fr

Outils et Logiciels d’Optimisation  Cours 1

Introduction Tableurs et solveurs Lesenvironnementsded´eveloppement

Unenvironnementdede´veloppementaidel’utilisateurauxactivite´s suivantes : e´crireunmode`le utiliser la bonne syntaxe trouver et corriger les erreurs lancer le solveur sortiretanalyserlesre´sultats L’existenced’environnementsdede´veloppementd´ependsouventde la plateforme sur laquelle on travaille (Windows, Mac, Linux).

P. Pesneaupierre.pesneau@math.ubordeaux1.fr

Outils et Logiciels d’Optimisation  Cours 1

Plan du cours

Introduction Tableurs et solveurs

Dans ce cours, on va essayer de voir : Solveursint´egre´sdanslestableurs Logicielsinte´ractifs Fichiers de transferts Unlangagedemode´lisation(OPL) C++ / Cplex

P. Pesneaupierre.pesneau@math.ubordeaux1.fr

Outils et Logiciels d’Optimisation  Cours 1

Introduction Tableurs et solveurs Tableurs et solveurs

Denosjours,plusieurslogicielspermettantdege´rerdestableaux int`egrentousontinterface´savecdessolveurs.

Laplupartdessolveurssontdessolveurslin´eairesouennombres entiers.Certainspeuventge´rerdesfonctionsquadratiques.

Exmeples : Excel(solveurint´egr´e,Cplex) OpenOffice.orgCalc(solveurint´egre´) IBMLotusSymphony(solveurint´egre´) Gnumeric

P. Pesneaupierre.pesneau@math.ubordeaux1.fr

Outils et Logiciels d’Optimisation  Cours 1

Introduction Tableurs et solveurs Tableurs et solveurs

Lesolveurestge´ne´ralementunemacrosupple´mentaire. Lecalculsefaitsurdesdonn´eesstock´eesdanslescellulesdu tableur. Lescontraintesetl’objectifsont´egalementassoci´es`ades celluleetcorrespondenta`desproduitsscalairedevecteurs.

P. Pesneaupierre.pesneau@math.ubordeaux1.fr

Outils et Logiciels d’Optimisation  Cours 1

Exemples

Introduction Tableurs et solveurs

Traitons quelques exemples avec OpenOffice.org Calc

P. Pesneaupierre.pesneau@math.ubordeaux1.fr

Outils et Logiciels d’Optimisation  Cours 1

Introduction Tableurs et solveurs AvantagesetInconve´nients

Avantages : Lestableurssonttre`sr´ependusdanslesentreprises(pas besoin d’acheter de nouveaux logiciels). Facilite´demiseenplaced’unpetitmod`elemathe´matique. Lesdonn´eessontsouventsauvegard´eesauformattableur.

Inconv´enients: Pasdepossibilit´esd’automatiserlaspe´cificationdes contraintes. Latailledesmode`lesestlimite´e(nombredevariables,nombre de contraintes Lagestiondeplusieursjeuxdedonn´eesestcomplexe (ne´cessitel’e´crituredeplusieursmod`eles). Lessolveursint´egr´essontmoinsperformantsquedessolveurs d´edi´es`alare´solutiondeprogrammesline´airesetprogrammes lin´eairesennombresentiers. P. Pesneaupierre.pesneau@math.ubordeaux1.frOutils et Logiciels d’Optimisation  Cours 1