Recherche Opérationnelle

Cours de

Recherche Opérationnelle

Semestre 7- E.N.C.G Kenitra

Plan du cours :

Chapitre I : Programmation linéaire

- Méthode graphique

- Méthode Simplexe

- Méthode Dualité

Chapitre II- Ordonnancements de projets

- Diagramme de Gant

- Méthode des potentiels METRA

- Méthode PERT

Chapitre III : Introduction à la théorie des Jeux

Chapitre IV : Problème de transport

Introduction

La recherche opérationnelle apparaît en 1940 en Angleterre puis aux États-Unis à des fins de recherche militaire : il s'agissait pour le Royaume Uni d'utiliser au mieux ses moyens militaires, à l'époque insuffisants. L'idée fondamentale était de mettre autant de soin dans l'emploi des moyens qu'on en avait mis pour les concevoir et les construire.

La recherche opérationnelle, appelée aussi «Outil d’aide à la décision », peut être définie comme l'ensemble des méthodes et des techniques rationnelles d'analyse et de synthèse des phénomènes de management du système d'information utilisables pour élaborer de meilleures décisions. La recherche opérationnelle (RO) propose donc des modèles conceptuels pour analyser des situations complexes et permet aux décideurs de faire les choix les plus efficaces.

Dans cette optique, la recherche opérationnelle est une discipline dont le but est de fournir des méthodes pour répondre à un type précis de problème, c’est-à-dire à élaborer une démarche universelle pour un type de problème qui aboutit à la ou les solutions les plus efficaces. La particularité de la recherche opérationnelle est que les méthodes proposées sont des démarches rationnelles basées sur des concepts et outils mathématiques et/ou statistiques.

Généralement, ces méthodes sont employées dans des problèmes tels que leur utilisation "manuelle" devient impossible. C’est pourquoi, du fait qu’elles sont rationnelles, les démarches proposées par la recherche opérationnelle peuvent être traduites en programmes informatiques.

Cette traduction d’une démarche en un programme informatique n’est pas sans difficulté :

Tout d’abord, le temps d’exécution du programme résultant et/ou la place occupée dans la mémoire de l’ordinateur peuvent ne pas être acceptables. Ainsi, une méthode en recherche opérationnelle sera jugée sur ces critères de temps et de place. Plus une méthode sera rapide et peu gourmande en mémoire, plus elle sera considérée comme bonne.

La recherche opérationnelle traite différents types de problème, on cite en particulier ceux d’ordre combinatoire et concurrentiel.

Un problème est dit combinatoire lorsqu'il comprend un grand nombre de solutions admissibles parmi lesquelles on cherche une solution optimale ou proche de l'optimum. Exemple typique : Déterminer où installer 5 centres de distribution parmi 30 sites d'implantation possibles, de sorte que les coûts de transport entre ces centres et les clients soient minimums.

Un problème est dit aléatoire s'il consiste à trouver une solution optimale face à un problème qui se pose en termes incertains.

Un problème est dit concurrentiel s'il consiste à trouver une solution optimale face à un problème dont les termes dépendent de l'interrelation entre ses propres agissements et ceux d'autres décideurs. Exemple typique : fixer une politique de prix de vente, sachant que les résultats d'une telle politique dépendent de la politique des concurrents.

Dans ce cours, nous verrons différents outils de recherche opérationnelle sans apporter de justifications mathématiques très détaillées et rigoureuses. Après quelques exemples qui permettront de mieux cerner le domaine de la recherche opérationnelle, nous introduirons un outil à la fois graphique et théorique: les graphes. Afin de mieux appréhender la complexité d’un problème ou la rapidité d’un algorithme, nous nous intéresserons à la théorie de la complexité. Enfin, nous verrons un autre outil important de la recherche opérationnelle qui est la programmation linéaire. L’avantage de cet outil est d’apporter une solution générique à la résolution de nombreux problèmes.

.

Chapitre 1 : Programmation linéaire

I- Introduction

La programmation linéaire est sans aucun doute la technique la plus connue de la recherche opérationnelle. C’est aussi un des outils les plus puissants et les plus utilisés en application industrielles parmi les technologies d’aide à la décision pour ne citer que :

- Planification de production

- Allocation des ressources

- Choix des produits à fabriquer

- Planification d’investissement ; affectation du personnel

- Gestion de projet

- Etc.

Les problèmes de programmations linéaires sont généralement liés à des problèmes d’allocations de ressources limitées, de la meilleure façon possible, afin de maximiser un profit ou de minimiser un coût. Le terme meilleur fait référence à la possibilité d’avoir un ensemble de décisions possibles qui réalisent la même satisfaction ou le même profit. Ces décisions sont en général le résultat d’un problème mathématique.

II- Les conditions de formulation d’un programme linéaire (PL)

La programmation linéaire comme étant un modèle admet des hypothèses (des conditions) que le décideur doit valider avant de pouvoir les utiliser pour modéliser son problème. Ces hypothèses sont :

1. Les variables de décision du problème sont positives

2. Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces variables, c’est

...