Recherche Opérationnelle

fabrications par des surcharges. II- Méthodes d’ordonnancement Elles sont très nombreuses, certains sont de pure empirisme (règle de priorité, Gantt) ; d’autre, par contre, ont un certain scientifique et relèvent de la recherche opérationnelle (PERT…). 1 Règles de priorités empiriques Ces règles permettent d’établir des plannings pour des fabrications mettant en jeu « M » moyens de production utilisés aléatoirement (Implantation en processus, implantation aléatoire)

définir un algorithme mathématique permettant de modéliser le problème rencontré. Le schéma ci-dessous représente les différents algorithmes envisageables suivant la nature du problème : Ce rapport concerne seulement la résolution par recherche opérationnelle : théorie des graphes et théorie des arbres. La complexité spatiale (taille du problème) et temporelle (nombre d’occurrences) d’un algorithme est un facteur très important. En effet suivant la méthode utilisée (polynomiale ou non), le temps

RECHERCHE OPéRATIONNELLE SOMMAIRE RECHERCHE OPéRATIONNELLE 1 Sommaire 2 Programmation linéaire 3 Exemple classique 3 Mise en équation 3 Formulation générale 3 Propositions 3 Forme canonique & standard 3 Transformation d’écriture 3 Forme standard 3 Forme canonique 4 Exemple 4 Bases, bases réalisables, solutions de base 4 Base & hors-base 4 Solution de base 4 Exemple 4 Caractérisation d’une base réalisable 4 Théorème 4 Solutions optimales

Recherche Opérationnelle 2ème Année Gestion industrielle Responsable du cours : Rim Larbi larbirim@gmail.com Année universitaire : 2009 - 2010 Plan du cours  Introduction  Partie    à la recherche opérationnelle 1 : Programmation Linéaire Chapitre 1 : Introduction à la programmation linéaire Chapitre 2 : Résolution d’un programme linéaire : méthode de simplexe Chapitre 3 : Dualité et analyse de sensibilité dans la programmation linéaire Plan du cours  Partie    2 : Graphes

problèmes, en particulier si l'on doit planifier des fabrications qui viennent en concurrence pour l'utilisation de certaines ressources de l'entreprise. Dans ce cas, il est nécessaire de faire appel à des algorithmes plus complexes issus de la recherche opérationnelle et de la théorie de l'ordonnancement. Toutefois, il est souvent possible de trouver des solutions satisfaisantes en appliquant simplement des règles de priorité heuristiques. La méthode consiste à placer les tâches à effectuer dans le diagramme

RECHERCHE OPéRATIONNELLE Sommaire RECHERCHE OPéRATIONNELLE 1 Sommaire 2 Programmation linéaire 3 Exemple classique 3 Mise en équation 3 Formulation générale 3 Propositions 3 Forme canonique & standard 3 Transformation d’écriture 3 Forme standard  4 Forme canonique 4 Exemple 4 Bases, bases réalisables, solutions de base 4 Base & hors-base 4 Solution de base 4 Exemple 5 Caractérisation d’une base réalisable 5 Théorème 5 Solutions optimales 5 Caractérisation des bases optimales

se fera par : • Des optimisations locales • Des optimisations globales « Supply Chain Management » ou « Efficient Customer Response » • Limiter les déplacements – Éviter les déplacements à vide – Minimiser les trajets (algorithmes de recherche opérationnelle) • Limiter les actions non productives – Ruptures de charge (transfert d’un produit d’un contenant à l’autre) – Aléas (pertes de produits, retards, etc) Optimisations locales Chaque opération doit être efficace : Logistique – Entreposage

allons maintenant décrire brièvement. 2 1.2. Gestion hiérarchique de la production. En gestion de la production, on distingue généralement plusieurs niveaux de décision allant des décisions stratégiques et/ou à long terme aux décisions opérationnelles et/ou à très court terme. Nous nous arrêterons plus particulièrement aux niveaux suivants: Gestion stratégique et planification à long terme: ce niveau de décision couvre • la définition de la mission de l’entreprise (« what business are we in

scientifiques de niveau recherche, publi´es ou non, ´emanant des ´etablissements d’enseignement et de recherche fran¸cais ou ´etrangers, des laboratoires publics ou priv´es. Hugues DUBEDOUT Mémoire présenté en vue de l’obtention du grade de Docteur de l’École Nationale Supérieure des Mines de Nantes sous le label de L’Université Nantes Angers Le Mans École doctorale : STIM Discipline : Informatique et applications Spécialité : Recherche Opérationnelle Unité de recherche : Irccyn Soutenue le 03/06/2013

d’un graphe 4.1 A partir de la matrice d’adjacence . . . . . . . 4.2 A partir d’une matrice d’incidence . . . . . . . 4.2.1 Liste des arˆtes . . . . . . . . . . . . . . e 4.2.2 Liste des cocycles Ω+ (i) ou Ω− (i) . . . 5 Recherche dans un graphe 5.1 Objectifs de cette recherche . . . . . . . . . . . . 5.2 Principe du parcours en profondeur d’un graphe 5.3 L’algorithme de parcours en profondeur . . . . . 5.4 Parcours en largeur d’un graphe . . . . . . . . . 5.5 D´termination des composantes connexes