[PDF] Recherche opérationnelle La Recherche Opérationnelle constitue

View - Download Recherche opérationnelle

Previous PDF

Next PDF

Recherche opérationnelle

Michel Nakhla, Jean-Claude Moisdon

Collection Les cours

Dans la même collection

Systèmes énergétiques vol 1, vol 2, vol 3

Renaud Gicquel

Thierry Weil

Mécanique des fluides

François Cauneau

Aide-mémoire de géostatistique linéaire

Pierre Chauvet

Introduction aux transferts thermiques

Dominique Marchio, Paul Reboux

Introduction au génie atomique,

Jacques Bouchard, Jean-Paul Deffain, Alain

Gouchet

ngénieur

Anne-Françoise Gourgues-Lorenzon, Jean-

Marc Haudin,

Jacques Besson, Noëlle Billon, Sabine

Cantournet, Yvan Chastel,

Bernard Monasse, Loeiz Nazé

Abrégé de thermodynamique,

Daniel Fargue

Introduction au tra

électrique

Georges Pierron

Introduction à la physique quantique

Bernard Degrange

Brigi-Novel, Michel Cohen de

Lara

Les imperfections des marchés

Daniel Fixari

Introduction à la métallurgie générale

Jacques Lévy

Comment maîtriser sa productivité

industrielle,

Hugues Molet

Géostatistique linéaire applications,

Margaret Armstrong, Jacques Carignan

Recherche opérationnelle

Michel Nakhla, Jean-Claude Moisdon

© Transvalor Presses des Mines, 2010

60 boulevard Saint-Michel, 75272 Paris cedex 06, France

e-mail : presses@mines-paristech.fr http://www.mines-paristech.fr/Presses

ISBN : 978-2-911256-15-8

Dépôt légal : 2010

Crédit photos : M. Nakhla

INTRODUCTION

La Recherche Opérationnelle constitue selon les cas, une simple branche des mathématiques ; à l'autre bout du spectre, elle consiste en l'application des méthodes

scientifiques au contrôle et au pilotage de l'action organisée. Dans le cadre de cet

ouvrage, nous nous limiterons volontairement à la définition suivante : " La Recherche Opérationnelle est une collection de techniques, issues du champ des mathématiques appliquées, destinées à représenter des situations où un ou plusieurs acteurs ont un certain nombre de choix à effectuer, et à guider ces acteurs dans leur décision de façon à ce qu'ils satisfassent au mieux un ou plusieurs critères tout en respectant un ensemble de contraintes prédéfinies ». En quelque sorte, on s'intéresse bien à un secteur particulier des mathématiques, celui de l'optimisation sous contraintes, mais en en restreignant le champ : en effet la définition proposée suggère que l'on ne traitera que de problèmes de décision économique, ou en

tout cas qui y ressemblent : l'ensemble des variables de décision, des critères, des

contraintes auront une signification économique et gestionnaire. Il s'agira donc de formaliser des problèmes d'allocation de ressources, d'organisation de la logistique, d'ordonnancement de production, de plMQLILŃMPLRQ GH SURGXŃPLRQ"

Cette définition explique tout d'abord la nature des problèmes abordés par la R.O

(Recherche Opérationnelle) : ils ne sont pas guidés par le développement autonome

d'une branche des mathématiques, mais par l'ensemble des problèmes de décision économique que peuvent se poser les collectivités organisées, pour l'essentiel les entreprises ou les administrations. Ces problèmes sont ordonnés dans des classes larges (problèmes d'ordonnancement d'atelier par exemple) où non seulement les questions posées sont communes à tous les problèmes de la classe, mais également un certain nombre de variables et de relations entre ces dernières, si bien que l'on peut élaborer des modèles de base, quitte ensuite, au cas par cas, à examiner comment on peut les adapter aux situations concrètes envisagées. Il va de soi que le présent ouvrage, compte tenu de son volume, n'a pour ambition que de présenter les principaux modèles de référence. Une autre conséquence de cette définition est que, comme le lecteur s'en apercevra

facilement, une hétérogénéité certaine caractérise fatalement un exposé des principales

techniques de la R.O : cela provient de la grande variété des problèmes décisionnels que l'on peut rencontrer dans les entreprises, problèmes qui n'ont aucune raison de relever d'un formalisme voisin. Il y a en effet peu de rapport HQPUH O transport de marchandises et la fixation d'un nombre de guichets dans un phénomène

d'attente : en effet les modélisations s'attaquant à l'un et à l'autre de ces deux problèmes

n'ont clairement pas grand chose de commun. La R.O s'attaque à des problèmes de gestion et de décision des organisations économiques et à la prise en compte du combinatoire et de l'incertitude.

6 Recherche opérationnelle

Prenons deux exemples pour illustrer ce propos.

Dans le problème du voyageur de commerce, ce dernier doit passer dans n villes, sachant qu'il souhaite visiter chacune d'entre elles une fois et une seule. Il connaît les temps de transport entre chaque ville et les autres, temps que l'on suppose fixes. Dans quel ordre doit-il effectuer ses visites de façon à ce que son temps de transport total soit minimal ?

La réponse est a priori facile. La ville de départ importe peu, on s'en rend compte

rapidement. Il se peut de toute façon qu'elle soit fixée. A partir de ce point de départ, notre voyageur de commerce a n-1 possibilités pour la ville suivante, puis pour la deuxième, puis pour troisième etc. Au total, il y a solutions à ce problème, soit On peut alors avoir comme idée d'explorer systématiquement ces solutions, en calculant à chaque fois la somme des temps de parcours, donc le temps de parcours total, et retenir, parmi ces temps totaux le plus petit. Or le nombre devient très vite important lorsque n augmente. Pour

six villes, le calcul reste possible, puisque l'on a 120 permutations à explorer et à

chiffrer. Pour, ce nombre est à peu près égal à 1,2164×1017. Si par exemple on écrit un programme informatique permettant d'évaluer toutes les solutions (et un programme est facile à écrire) et si l'ordinateur dont on dispose nécessite un nanoseconde pour chaque solution on explorera l'ensemble des possibilités en 3,8 ans environ ! C'est dire que les performances des ordinateurs actuels ne libèrent pas de la nécessité de trouver des méthodes permettant de nous orienter dans la prolifération des solutions possibles liées à la présence de nombreux problèmes de gestion combinatoire.

Cet exemple est intéressant car le problème posé est tout à fait réaliste (dans les cas

concrets il se complique souvent considérablement ce qui ajoute encore à la complexité de sa résolution) et renvoie à des questions que se posent de nombreuses entreprises (tournées de postiers, de camions de coopératives laitières etc.). Des méthodes existent

en effet pour traiter ce problème de façon efficace (même si elles ne sont pas entièrement

satisfaisantes comme on le verra dans cet ouvrage à propos de l'exposé de l'une d'entre elles). Le deuxième exemple est issu lui aussi d'un problème tout à fait pratique : un marchand de journaux se pose la question de la quantité optimale d'exemplaires d'un quotidien qu'il doit acheter à un distributeur. La demande est variable ; il ne sait pas à l'avance combien de clients lui achèteront le journal chaque jour ; il connaît évidemment le prix d'achat au distributeur et le prix de vente, si bien que pour un niveau de vente donné il peut calculer

sans difficultés le bénéfice (ou la perte s'il achète trop de journaux) obtenu. Le problème

est qu'il ne sait pas intégrer dans un calcul unique les différents bénéfices correspondant

aux événements non prévisibles constitués par les niveaux de vente. Le calcul vient alors

à son secours par deux modalités consécutives : il est tout d'abord invité à analyser sur

un certain nombre de jours la chronique des ventes ; si cette analyse est suffisamment poussée, il peut éventuellement raccorder par un test statistique cette chronique de

ventes à une distribution de probabilités. Ce faisant il a déjà " domestiqué »

considérablement l'incertitude : certes il ne sait pas à l'avance quelle quantité de

journaux il vendra tel ou tel jour, mais il a une information précieuse, à savoir la

probabilité de vendre une quantité donnée (et toutes les probabilités associées aux

diverses quantités possibles). La deuxième étape est alors constituée par une

démonstration, qui aboutit à un résultat qui est loin d'être intuitif : si le phénomène est

Introduction 7

répétitif (prix fixes et demande constante en probabilités), il peut alors agréger les

bénéfices correspondant aux différentes ventes grâce à un opérateur simple que

connaissent bien les spécialistes des probabilités, à savoir l'espérance mathématique

(moyenne des bénéfices pondérés par leurs probabilités). Un théorème célèbre, le

Théorème Central Limite, justifie en effet que l'on prenne ce critère comme critère de

choix, dans un contexte de répétition (stabilité des données et décision répétée un grand

nombre de fois). Il ne reste plus alors à notre marchand de journaux, convaincu par cet

édifice théorique, qu'à calculer les espérances mathématiques de bénéfice, pour chaque

niveau d'achats du quotidien, et à choisir le niveau qui maximise cette espérance. Il est

intéressant de noter d'ailleurs qu'à ce stade le problème reste assez compliqué : en effet,

il est facile de s'apercevoir que cette modélisation aboutit à une formule relativement complexe liant l'espérance du bénéfice au niveau d'achat, pour laquelle les techniques d'optimisation fonctionnelle classiques (dérivation par exemple) sont inopérantes ; le marchand de journaux sera donc obligé de procéder pas à pas, en tâtonnant sur le niveau d'achat, et en calculant à chaque fois la formule, pour trouver le niveau optimal. Et

pourtant, les hypothèses sont frustes ! On sent bien qu'un problème réel ressemblant à ce

problème " épuré » va supposer des hypothèses plus fines (variation de la loi de

probabilités de la demande, possibilités de ventes le lendemain de la parution etc.)

risquant de compliquer quelque peu le modèle. Quoiqu'il en soit, on voit bien quel est l'apport de la R.O dans ce cadre : elle permet ce

que l'esprit ordinaire ne peut pas faire, c'est-à-dire l'intégration dans un calcul des

conséquences des multiples événements qui peuvent peser sur une décision économique.

Quelques éléments historiques

On a l'habitude de situer la naissance de la R.O lors de la seconde guerre mondiale, au sein de l'armée britannique, qui a commencé à formaliser un certain nombre de problèmes stratégiques, tel l'optimisation du parcours ou de la composition des convois maritimes ou encore celle du positionnement des radars etc. Certains auteurs, cela dit, ne sont pas sans souligner que les perspectives d'application

des modèles à l'action organisée se sont manifestées bien avant, qu'il s'agisse de la

construction des pyramides, de la mise en place du siège de Syracuse, ou encore des problèmes de déblai et de remblai formalisés par Monge. Pour ce qui nous intéresse, c'est à dire la diffusion de la discipline dans les entreprises,

on peut néanmoins considérer que cette diffusion s'est opérée, et à un rythme accéléré,

dans les années cinquante. On ne peut s'empêcher de relier ce développement à celui de l'informatique. La plupart

des outils de la R.O nécessitent en effet un support informatique pour résoudre les

problèmes auxquels ils s'attaquent. Mais, bien qu'il existe peu d'études sur ce type de sujet, on peut aussi penser que la R.O est fondée sur une représentation implicite de l'entreprise et de son fonctionnement qui s'est constituée récemment, en tout cas au vingtième siècle. Faire de l'organisation une combinatoire d'activités plus ou moins incertaines signifie en effet un préalable qui est la codification de ces activités, une explicitation de ce qui les relie, une quantification des

8 Recherche opérationnelle

consommations de ressources qu'elles impliquent. C'est dire que la R.O est inséparable de l'approche scientifique du travail de Taylor. Au cours des années cinquante le développement de la R.O dans les organisations s'est

transformé en véritable engouement; une sorte de rêve semble avoir été partagé par

nombre de cadres de l'industrie, à savoir la possibilité de traiter tous les problèmes de gestion, d'organisation et de décision économique par des modèles et de conduire la destinée des entreprises grâce aux mathématiques.

La R.O s'est constituée en discipline à part entière, au début des années soixante, avec la

mise sur pied des principaux attributs d'une profession : experts spécialisés, création de

revues, d'associations savantes, de chaires dans les universités, de congrès etc. Du côté

des entreprises on note le développement de bureaux d'études, de services spécialisés dans les grandes entreprises, souvent rattachés directement à la direction générale. Le

secteur public est " touché » un peu plus tard, au milieu des années soixante. Les progrès

au niveau des méthodes, de leur rapidité de calcul, sont spectaculaires. Les spécialistes

s'attaquent à des problèmes de plus en plus difficiles. Le ton est à l'enthousiasme;

beaucoup pensent que l'on dispose là d'un dispositif essentiel de rationalisation de l'action humaine dans les systèmes organisés. À partir des années soixante-dix, on s'interroge sur la modestie des applications

concrètes dans les entreprises, ou encore du sort réservé aux modèles, parfois

complètement contradictoire avec les attendus des promoteurs. Bon nombre des services de R.O des grandes entreprises sont fusionnés avec les services " d'études

économiques » ou de " stratégie », comme si un discrédit pesait sur la dénomination de

la discipline elle-même. Dans la foulée, le sigle des enseignements se transforme lui " méthodes scientifique de gestion », ou encore de " modélisation des faits économiques ». En 1978 paraît dans la prestigieuse revue américaine " The journal of the O.R Society » une épitaphe joliment intitulée " The future of operational research is past » , d'autant plus perturbante qu'elle est l'°XYUH d'un des pionniers de la discipline, Russel L. Ackoff. Cette contribution en entraîne beaucoup d'autres et ouvre un débat parfois passionné autour de ce que l'on a pu appeler ``la crise'' de la Recherche

Opérationnelle.

Un point de vue raisonné

Il convient tout d'abord de souligner que les applications de la R.O. existent bel et bien : c'est ainsi que la programmation linéaire est devenue une sorte de routine pour des industries du continu, notamment le raffinage pétrolier (Partie 1 de cet ouvrage), qu'il n'est guère envisageable de démarrer un projet de quelque envergure sans avoir recours à une méthode d'ordonnancement des tâches, PERT ou Potentiel (Partie 2), que les analyses du risque se sont multipliées dans de multiples secteurs (Partie 3). On peut même parfois s'inquiéter lorsque l'on constate que certains logiciels de gestion, livrés " clef en main » et tendant à automatiser la conduite des entreprises, appartenant par exemple à la catégorie des GPAO (Gestion de Production Assistée par Ordinateur), intègrent parfois, sans que l'utilisateur en ait conscience, des modèles (gestion de stocks par exemple) sur la généralité desquels il est légitime d'avoir quelques doutes.

Introduction 9

Objectifs et organisation générale de l'ouvrage Les développements qui suivent couvrent un enseignement que les auteurs donnent à l'Ecole des Mines de Paris. Il s'agit essentiellement d'une initiation et que nous ne prétendons nullement être exhaustifs sur les modèles conçus dans le cadre de la R.O. Dans ce cadre, nous n'évoquerons pas les extensions de la programmation linéaire vers

les programmes en nombres entiers ( c'est à dire où l'on contraint les solutions du

problème à prendre des valeurs entières, ce qui correspond à des exigences fréquentes dans la réalité - productions non divisibles par exemple) ; de même, nous serons rapide sur les différents types d'heuristiques qui sont actuellement perfectionnées et qui sont

destinées à s'attaquer à des problèmes hautement combinatoires (algorithmes génétiques,

méthode Tabou, recuit simulé etc.). Au niveau de l'aléatoire, nous ne dirons rien de deux chapitres aujourd'hui très

" vivants », qui étendent les calculs probabilistes à deux situations d'incertitude qui à

priori ne relèvent pas de l'aléatoire (au sens de la prise en compte de données non

connues à l'avance mais " domestiquées » parce que probabilisables, cf. l'exemple ci- dessus du marchand de journaux) : il s'agit en premier lieu des situations concurrentielles (le décideur ne sait pas ce qui va arriver dans la mesure où cela dépend du comportement d'autres, les autres en question étant dans la même expectative vis à vis du décideur) ;

ces situations relèvent de la théorie des jeux, discipline d'ailleurs à part entière qui a vécu

ces dernières années un renouveau considérable, notamment dans le cadre des travaux

des économistes, s'intéressant aux déséquilibres de marché, aux asymétries d'information

entre acteurs et aux externalités. En second lieu nous pensons aux situations à proprement parler incertaines, où aucune règle ni aucune expérience ne permet d'affecter

des distributions de probabilité aux données. On a affaire alors à l'édifice considérable

qui porte le nom de Théorie de la décision, que l'on peut considérer comme l'aboutissement de la rationalisation des choix individuels. On pourrait penser en effet

que la modélisation est impuissante dans ce cas à aider le décideur ; il n'en est rien et il

est tout à fait stimulant d'examiner comment l'ingéniosité des mathématiciens appliqués

les a amenés à proposer malgré tout des formalisations dans ce contexte difficile. En dehors du fait que dans une perspective gestionnaire ces deux types de modélisation constituent davantage des références de raisonnement que des outils opérationnels, ils

nécessitent un ouvrage à eux seuls, et nous avons préféré les laisser de côté ici (bien que

nous les enseignions). Si la liste des outils que ce livre décrit est donc volontairement limitée, nous avons en revanche mis un certain soin à justifier chacun d'entre eux, et à démontrer par exemple la convergence des algorithmes ou la validité des formules. Une autre optique, en effet,

choisie parfois par les ouvrages de R.O., consiste à parcourir une liste étendue de

modèles, sans fournir de démonstration. Ce choix n'est pas sans entraîner une certaine frustration chez les lecteurs rigoureux ; il ne fournit pas non plus de vue sur la fréquente originalité du raisonnement des chercheurs opérationnels (qui, comme on l'a dit, ont

résolu à leur façon un certain nombre de problèmes sur lesquels avaient échoué de

grands mathématiciens). Enfin, aucun modèle existant dans la littérature ne s'applique tel

quel à des situations décisionnelles concrètes ; ils doivent être adaptés. Mais pour savoir

comment les modifier, il faut savoir comment et pourquoi ils " marchent ».

10 Recherche opérationnelle

outils que nous exposons ici, sont ceux qui font le plus appel aux mathématiques, alors que les graphes, par exemple, sont très économes en concepts et connaissances

mathématiques, et sont donc plus à même de séduire des lecteurs intéressés par la

discipline mais moins par les équations. D'un autre côté, beaucoup de problèmes,

notamment résolus par des méthodes appuyées sur les graphes, pourraient l'être aussi par

Après avoir relié la programmation linéaire à une problématique générale de

planification de production industrielle, on développera de façon complète la méthode de résolution " phare », à savoir l'algorithme du simplexe. On soulignera qu'il ne s'agit pas de la méthode de résolution a priori la plus rapide et on donnera quelques indications sur d'autres méthodes logiquement plus performantes (sans que cela se vérifie empiriquement). On introduira dans cette partie la notion de dualité dans les programmes linéaires, notion fondamentale d'abord d'un point de vue économique (fixation des prix d'acquisition de ressources supplémentaires), ensuite d'un point de vue pratique (analyse de sensibilité). Dans une seconde partie, nous passerons à la théorie des graphes, et nous montrerons

que cet objet, très simple dans son principe (des points et des flèches) permet de

résoudre un grand nombre de problèmes combinatoires concrets et ayant des implications évidentes au niveau de l'organisation de la production et de la logistique. C'est ainsi que l'on traitera de quelques algorithmes destinés à résoudre le problème du chemin de valeur minimale dans un graphe. Nous montrerons que ces méthodes peuvent

s'appliquer sans difficultés à la question très importante de l'ordonnancement des tâches

dans un projet. Comme on l'a signalé plus haut, peu de projets industriels se privent à l'heure actuelle d'une planification à base d'un PERT ou d'une méthode potentiels, qui constituent les deux outils concurrents en la matière. Là aussi, l'exposé restera succinct, dans la mesure où l'on ne fera qu'évoquer les complications introduites dans ces techniques par la prise en compte de contraintes autres que celles portant sur la succession des tâches (les contraintes disjonctives notamment, qui ouvrent l'immense et difficile chapitre de l'ordonnancement d'atelier).

On traitera ensuite des problèmes liés à des graphes particuliers, nommés " arbres » ; on

montrera que cette notion permet de traiter simplement des questions de tracé de réseaux (comment relier n points de la façon la plus économique ?). Le concept voisin d'arborescence conduit moins, de son côté, à des outiOV G une classe particulière de méthodes visant à approcher des questions hautement combinatoires et particulièrement difficiles. C'est dans ce cadre que nous aborderons le fameux problème du voyageur de commerce (cf. supra). Le dernier chapitre de cette partie abordera les problèmes de flots : il s'agit cette fois-ci

de faire circuler des flux dans des réseaux (flux divers : pièces, matières premières, mais

aussi individus ou voitures sur un réseau autoroutier) de façon soit à maximiser les

entrées totales sur le réseau (problème du flot maximal), soit à minimiser un coût global

de transport, à entrée totale donnée (programme de transport). On montrera également

Introduction 11

que certains problèmes a priori éloignés de ces préoccupations (problème de l'affectation de tâches à des effecteurs potentiels notamment) peuvent être traités avec élégance par les formalisations issues de la notion de flot.

Enfin, dans une dernière partie, nous traiterons des phénomènes aléatoires. Pour ce faire,

on fera appel au calcul des probabilités, en restreignant au minimum l'arsenal mathématique correspondant (on sait qu'il peut être considérable). Il suffira donc au lecteur d'avoir des connaissances limitées aux lois probabilistes les plus courantes, aux concepts les plus répandus (espérance et variance) et aux opérations classiques sur les variables aléatoires pour consulter les trois chapitres de cette partie, consacrés d'une part

à la gestion des files d'attente, d'autre part à la fiabilité des équipements, enfin à la

gestion des stocks.

Chapitre 1

Généralités sur la Programmation Linéaire Nous commencerons le cours de Recherche Opérationnelle par l'examen d'un outil

auquel il est très souvent fait référence dans nombre de problèmes économiques, qu'ils

concernent l'entreprise ou l'Etat : la programmation linéaire. Nous n'analyserons pas celle-ci sous l'angle de la signification économique des différents concepts qu'elle met en °XYUH ŃH TXL SHXP rPUH IMit par exemple dans un cours de calcul économique; nous nous préoccuperons plutôt des techniques de résolution usuelles des programmes linéaires. Parfois, nous serons amenés à introduire des notions économiques comme le " profit », le " coût », les " ressources », mais ce sera davantage par simple souci d'illustration que pour indiquer le champ d'application des techniques exposées. Soulignons enfin que dans les chapitres suivants nous ferons fréquemment allusion à la programmation linéaire, en particulier pour les problèmes de graphes, ce qui justifie que ce premier fascicule soit consacré à cet outil.

1.1. UN EXEMPLE SIMPLE

Avant d'aborder l'exposé le plus général sur la programmation linéaire, il convient de

donner un petit exemple n'ayant aucune prétention à représenter un problème réel, mais

permettant d'illustrer la plupart des résultats que nous dégagerons par la suite. Soit une entreprise qui fabrique deux types de camions (types A et B). Cette entreprise est divisée en trois ateliers, l'atelier I fabriquant les moteurs, l'atelier II fabriquant les

ŃMUURVVHULHV O

Les temps unitaires pour chacune des trois opérations et pour chaque type de camions sont consignés dans le tableau suivant :

Ateliers Camions de type

A

Camions de type

B I

Moteurs

1h 3h II

Carrosseries

2h 1h III

Assemblage

1h 1h

14 Recherche opérationnelle

Par ailleurs, l'étude des capacités de production des 3 ateliers a dégagé qu'en un mois,

450 heures de travail pouvaient être utilisées dans l'atelier I, 350 heures dans l'atelier II,

200 dans l'atelier III.

Enfin, on sait que le bénéfice unitaire réalisé par l'entreprise sur les camions de type A

s'élève à 4000 et que celui réalisé sur les camions de type B est de 8000. La question que l'on se pose est la suivante : quelle doit être la production mensuelle en camions de chaque type pour rendre le bénéfice de l'entreprise le plus grand possible ? Nous pouvons formaliser ce problème de la façon suivante : Soit la production mensuelle en camions de type A et celle en camions de type B. Les contraintes de disponibilité d'heures de travail dans chacun des ateliers peuvent s'écrire:

Atelier I :

450321

quotesdbs_dbs33.pdfusesText_39

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

[PDF] inpes

[PDF] methode boscher pdf download

[PDF] méthode boscher cahier de lecture pdf

[PDF] methode boscher en ligne

[PDF] méthode boscher gratuit

[PDF] méthode boscher cahier des sons pdf

[PDF] adjectif pour acrostiche

[PDF] recherche qualitative définition

[PDF] méthode qualitative et quantitative

[PDF] méthode qualitative mémoire

[PDF] méthode quantitative

[PDF] méthodologie de recherche qualitative pdf

[PDF] méthode qualitative entretien

[PDF] méthode qualitative sociologie