Scribd Logo
Importer

Bienvenue sur Scribd !

  • 265 vues

    01 Introduction

    Transféré par

    Abdellah Amine
    Le document présente le plan d'un cours de recherche opérationnelle. Il contient plusieurs sections sur l'optimisation linéaire et non linéaire, les problèmes de réseaux et en nombres entiers, ainsi que des exemples et l'historique de la recherche opérationnelle.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PPT, PDF, TXT ou lisez en ligne sur Scribd

    01 Introduction

    Transféré par

    Abdellah Amine
    265 vues41 pages
    Le document présente le plan d'un cours de recherche opérationnelle. Il contient plusieurs sections sur l'optimisation linéaire et non linéaire, les problèmes de réseaux et en nombres entiers, ainsi que des exemples et l'historique de la recherche opérationnelle.

    Description originale:

    Introduction

    Titre original

    01 Introduction (1)

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PPT, PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Le document présente le plan d'un cours de recherche opérationnelle. Il contient plusieurs sections sur l'optimisation linéaire et non linéaire, les problèmes de réseaux et en nombres entiers, ainsi que des exemples et l'historique de la recherche opérationnelle.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PPT, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format ppt, pdf ou txt
    265 vues41 pages

    01 Introduction

    Transféré par

    Abdellah Amine
    Le document présente le plan d'un cours de recherche opérationnelle. Il contient plusieurs sections sur l'optimisation linéaire et non linéaire, les problèmes de réseaux et en nombres entiers, ainsi que des exemples et l'historique de la recherche opérationnelle.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PPT, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format ppt, pdf ou txt
    Vous êtes sur la page 1sur 41

    Recherche opérationnelle

    GC-SIE
    Plan du cours
     Optimisation linéaire
    – Introduction et exemples
    – Géométrie
    – Algo. du simplexe (phase II)
    – Algo. du simplexe (phase I)
    – Dualité

    Introduction Michel Bierlaire 2


    Plan du cours (suite)
     Optimisation non-linéaire
    – Introduction et exemples
    – Conditions d’optimalité
    – Plus forte pente et Newton
    – Variations sur Newton
    – Moindres carrés

    Introduction Michel Bierlaire 3


    Plan du cours (suite)
     Problèmes de réseaux
    – Introduction et exemples
    – Problème du plus court chemin
    – Problème de flot maximal
    – Problème de transbordement

    Introduction Michel Bierlaire 4


    Plan du cours (suite)
     Problèmes en nombres entiers
    – Introduction et exemples
    – Algorithmes exacts
    – Algorithmes d’approximation
    – Heuristiques
     Recuit simulé
     Algorithmes génétiques
     Introduction à la simulation

    Introduction Michel Bierlaire 5


    Introduction

    Recherche opérationnelle
    Génie Civil
    Chapitre 1
     Introduction à l’optimisation
    – Démarche générale
    – Exemples
    – Formulation
    – Approche intuitive
    – Types de problèmes
    – Algorithmes

    Introduction Michel Bierlaire 7


    Historique
    Théorie des Programmation Combinatorique,
    décisions mathématique Théorie des graphes

    Pascal (1654) Fourier (1824) Sainte-Laguë (1926)


    Fermat (1654) D. König (1936)
    Bernouilli (1713)
    RO 2e guerre mondiale:
    1ère application: militaire

    Simplexe Premier “grand” algorithme (1947)

    1er ordinateur 1ère application commerciale (1956)


    Mots clés
     Modélisation
    – Simplification de la réalité pour pouvoir en
    appréhender certains aspects
     Optimisation
    – Identification d’une configuration qui soit
    meilleure que toute autre suivant un critère
    spécifique
     Simulation
    – Représentation artificielle d’un
    fonctionnement réel

    Introduction Michel Bierlaire 9


    Recherche
    Statistiques opérationnelle
    Réalité Modèle

    Observateur Description Prédiction


    Optimisation

    Données
    Décision

    Estimation

    Modèle
    Exemple : Geppetto
    Geppetto, Inc., jouets en bois.
    Soldats : vendus 27F et coûtant 10F de matériel brut.
    Coûts généraux : 14F par soldat.
    Qté. de travail : 1 h de menuiserie 2 h de finissage
    Trains : vendus 21F et coûtant 9F de matériel brut.
    Coûts généraux : 10F par train.
    Qté. de travail : 1 h de menuiserie et 1 h de finissage
    Au maximum, on dispose de
    80 h de menuiserie et
    100 h de finissage par semaine.
    Demande : illimitée pour les trains,
    maximum 40 soldats par semaine.

    Introduction Michel Bierlaire 11


    Exemple : Geppetto
    Comment maximiser les bénéfices de Geppetto ?
    Modélisation :
    1. Variables de décision :
    x1 = nombre de soldats produits par semaine
    x2 = nombre de trains produits par semaine
    2. Fonction objectif :
    Bénéfice = revenu – coût du matériel – coûts généraux
    Revenu = revenu pour les soldats +
    revenu pour les trains
    = (francs/soldat)(soldats/semaine) +
    (francs/train)(trains/semaine)
    = 27 x1 + 21 x2
    Coût du matériel = 10 x1 + 9 x2
    Coûts généraux = 14 x1 + 10 x2

    Introduction Michel Bierlaire 12


    Exemple : Geppetto
    Bénéfice = (27 x1 + 21 x2)-(10 x1 + 9 x2)-(14 x1 + 10 x2)
    = 3 x1 + 2 x2
    On notera Maximiser z = 3 x1 + 2 x2
    3. Contraintes :
    a) Pas plus de 100 h de finissage par semaine
    b) Pas plus de 80 heures de menuiserie par semaine
    c) Pas plus de 40 soldats par semaine
    Finissage/semaine =
    (finissage/soldat)(soldats/semaine) +
    (finissage/train)(trains/semaine) =
    2 x1 + x2
    Contrainte a : 2 x1 + x2  100
    Contrainte b : x1 + x2  80
    Contrainte c : x1  40
    x1  0, x2  0
    Introduction Michel Bierlaire 13
    Formulation
     Sous quelles formes présenter le
    problème d’optimisation ?
     Formes standard ou canonique
     Exigences des algorithmes
     Nécessité de transformer le
    problème

    Introduction Michel Bierlaire 14


    Formulation
     Fonction objectif
    min f(x) max f(x)
     Contraintes
    g(x)  cte g(x)  cte g(x) = cte
     Contraintes de bornes
    lxu
     Contraintes de signe
    x0

    Introduction Michel Bierlaire 15


    Formulation : transformations

    Introduction Michel Bierlaire 16


    Formulation : transformations

    g(x)  0 -g(x)  0

    Introduction Michel Bierlaire 17


    Formulation : règles

    Introduction Michel Bierlaire 18


    Formulation : exemple

    sous contraintes

    Introduction Michel Bierlaire 19


    Formulation : exemple

    sous contraintes sous contraintes

    Introduction Michel Bierlaire 20


    Approche intuitive
     Considérons des exemples triviaux
    1. Une entreprise gagne 5F chaque fois
    qu’elle vend 1 litre de produit chimique.
    Elle désire maximiser son profit.
    Profit (F)

    1 Litres
    Introduction Michel Bierlaire 21
    Approche intuitive
     Observations :
    – Fonction objectif linéaire
    – Pas de contraintes
    – Solution infinie
     Commentaire :
    – La solution est toujours infinie lorsque
    la fonction objectif est linéaire et qu’il
    n’y a pas de contraintes

    Introduction Michel Bierlaire 22


    Approche intuitive
    2. Un laboratoire achète 30F le litre de
    produit chimique. Il dispose d’un budget
    de 1000F. Quelle quantité maximale
    peut-il acheter ?
    Coût (F)

    300

    10 Litres
    Introduction Michel Bierlaire 23
    Approche intuitive
     Observations :
    – Réponse évidente : 1000 / 30 litres
    – Bien que l’on puisse dépenser 1000F ou
    moins, on dépense exactement 1000F
     Commentaires :
    – Si la fonction objectif et les contraintes sont
    linéaires, il y a au moins une contrainte active
    à la solution
    – La contrainte g(x)  0 est dite active en x* ssi
    g(x*)=0

    Introduction Michel Bierlaire 24


    Approche intuitive
    3. Un laboratoire achète 30F le litre de
    produit chimique. Il dispose d’un budget
    de 1000F et doit en acheter au minimum
    40 litres. Quelle quantité maximale peut-
    il acheter ?
    Coût (F)

    300

    10 40 Litres
    Introduction Michel Bierlaire 25
    Approche intuitive
     Observations :
    – Problème impossible
    – Contraintes incompatibles
     Commentaire :
    – La solution peut ne pas exister. On dit
    que le problème ne possède pas de
    solution admissible.

    Introduction Michel Bierlaire 26


    Approche intuitive
    4. Un laboratoire achète 3F un
    microprocesseur. Il dispose d’un budget
    de 10F. Quelle quantité maximale peut-il
    acheter ?
    Coût (F)

    1 10/3 Microprocesseurs
    Introduction Michel Bierlaire 27
    Approche intuitive
     Observations :
    – Impossible d’acheter des parties de
    microprocesseurs
    – Malgré que la fonction objectif et les
    contraintes soient linéaires, le budget ne sera
    pas totalement dépensé
     Commentaire :
    – Lorsque les variables sont entières, les
    résultats théoriques peuvent être différents

    Introduction Michel Bierlaire 28


    Approche intuitive
    5. Un objet est lancé à la verticale à la
    vitesse de 50 m/s. Quand atteindra-t-il
    son point culminant ?
    Tangente
    Hauteur (m)

    horizontale

    Temps (sec)
    Introduction Michel Bierlaire 29
    Approche intuitive
     Observations
    – Fonction objectif non linéaire
    – Pas de contraintes
    – Solution finie
     Commentaires
    – Si la fonction objectif est non linéaire, une
    solution finie peut exister, même en l’absence
    de contraintes
    – A la solution, la tangente à la courbe est
    horizontale (i.e. la dérivée est nulle)

    Introduction Michel Bierlaire 30


    Approche intuitive

    Tangente
    horizontale

    mais pas un maximum, ni un minimum…

    Introduction Michel Bierlaire 31


    Approche intuitive
     Observations
    – Pas de solution finie
    – Présence d’une tangente horizontale
     Commentaires
    – Une solution finie n’est pas garantie par
    la non linéarité de la fonction objectif
    – Une tangente horizontale n’identifie
    pas nécessairement une solution.

    Introduction Michel Bierlaire 32


    Approche intuitive

    Pas de tangente

    Introduction Michel Bierlaire 33


    Approche intuitive
     Observation :
    – La fonction n’est pas dérivable à la solution

     Commentaire:
    – Attention aux fonctions non différentiables
    Introduction Michel Bierlaire 34
    Approche intuitive
     Le plus haut sommet du monde est l’Everest
     Le plus haut sommet d’Asie est l’Everest
     Le plus haut sommet d’Europe est l’Elbrouz

    Introduction Michel Bierlaire 35


    Types de problèmes
     Linéaire vs. non-linéaire
     Définition:
    Une fonction f(x1,x2,…,xn) de x1,x2,…,xn est
    une fonction linéaire si et seulement s’il
    existe un ensemble de constantes
    c1,c2,…,cn telles que
    f(x1,x2,…,xn) = c1 x1+c2 x2+…+cnxn
     Fonction objectif
     Contraintes

    Introduction Michel Bierlaire 36


    Types de problèmes
     Avec ou sans contraintes
     Dans ce cours :
    – Programmation linéaire
     Objectif linéaire
     Contraintes linéaires
    – Programmation non linéaire
     Objectif non linéaire
     Sans contraintes

    Introduction Michel Bierlaire 37


    Types de problèmes

    x y
    f(x) est concave sur X si pour tout x,yX, on a

    Introduction Michel Bierlaire 38


    Types de problèmes
     Résumé des critères
    – linéaire / non-linéaire
    – contraintes / pas de contraintes
    – convexe / non convexe
    – concave / non concave
    – différentiable / non différentiable
    – variables continues / entières

    Introduction Michel Bierlaire 39


    Algorithmes
     Al Khwarizmi, surnom du mathématicien arabe
    Muhammad Ibn Musa (IXième siècle), né à Khwarizem, en
    Ouzbekistan.
    – Il a écrit Al-jabr wa'l muqabala dont vient le mot
    « algèbre » [et les équations]
     Algorithme:
    suite finie de règles
    à appliquer dans un ordre déterminé
    à un nombre fini de données
    pour arriver avec certitude,
    en un nombre fini d’étapes,
    à un certain résultat
    et cela indépendamment des données.
     Résolution d’une classe de problèmes
    Introduction Michel Bierlaire 40
    Algorithmes
    La plupart des algorithmes considérés
    dans ce cours auront la forme
     Soit x0 une estimation de la solution
     Pour k=0,…. faire
    – Trouver xk+1 à partir de xk
     Tant que xk n’est pas acceptable
     De telle manière que
    limk xk = x*

    Introduction Michel Bierlaire 41

    Vous aimerez peut-être aussi