Recherche opérationnelle - Free

Module :
Recherche opérationnelle Par : Melle Najlae Korikache Un peu d'histoire : |1654 |Pascal, Fermat |espérance mathématique |
| |Bernoulli, Waldegrave |problèmes de décision dans |
| | |l'incertain |
|1776 |Monge |un problème économique de nature |
| | |combinatoire - déblais et remblais |
|1838 |Cournot |théorie mathématique des richesses |
|1917 |Erlang |théorie des files d'attente |
|1921-25 |Borel |théorie des jeux |
|1936 |Konig |théorie des graphes |
|1939-45 |Kantorovich |programmation linéaire |
|1940 |Blackett |dirige la première équipe de RO |
Blackett traite rapidement et avec succès difficiles questions, telles que
: Implantation optimale de radars de surveillance, protection des convois
de navires.. Après la 2éme guerre mondiale, les techniques se sont considérablement
développées, grâce, notamment, à l'explosion des capacités de calcul des
ordinateurs. Les domaines d'application se sont également multipliés. Pourquoi une apparition si tardive ?
L'économie parvient à une certaine maturité et fait recours aux
mathématiques Les problèmes sont devenus complexes, en raison de la taille croissante des
entreprises et les liens entre elles. Les acquis théoriques ne seraient rien sans moyens de calcul. Seuls les
ordinateurs sont aptes à résoudre les problèmes pratiques. (Tentative de) définition :
La recherche opérationnelle est l'ensemble de méthodes et techniques
rationnelles d'analyse et de synthèse des phénomènes d'organisation
utilisables pour élaborer de meilleures décisions. La recherche opérationnelle est fortement liée à l'ingénierie des systèmes. La RO ne s'occupe pas des problèmes dans lesquels une solution de bon sens
intervient naturellement. Son domaine est celui des situations dans
lesquelles, le sens commun se révèle faible ou impuissant. L'objectif :
L'objectif de la Recherche Opérationnelle est l'aide à la décision. Les deux termes sont essentiels. En premier lieu, ce que l'on cherche à
garantir, ce n'est pas la valeur du résultat, mais l'optimalité de la
décision. En effet, nous ne sommes pas maîtres des aléas qui constituent le
contexte de notre action. Ce que maîtrisons, ce sont nos choix... et il est
souhaitable de ne pas avoir à les regretter par la suite. En second lieu,
la Recherche Opérationnelle n'a pas pour but de prendre des décisions, mais
de clarifier le contexte dans lequel ces décisions sont prises. Un choix
réel ne peut se faire qu'en connaissance de cause... mais on ne peut
attendre de tout connaître avant d'agir. Types de problèmes traités 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 minimum.
Ce problème ne peut être résolu par une simple énumération des solutions
possibles par l'esprit humain, puisqu'il en existe 30 x 29 x 28 x 27 x 26 /
(5x4x3x2) = 142 506 (!) Un problème est dit aléatoire s'il consiste à trouver une solution optimale
face à un problème qui se pose en termes incertains. Exemple typique : Dans une grande entreprise, la moyenne des entrées des
personnels au bureau du correspondant de la sécurité sociale est d'une
personne par 4 min. Un employé peut servir, en moyenne, une personne toutes
les 3 min 20 sec. Combien d'employés faut-il embaucher dans le bureau ? 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 que les
concurrents adopteront. Domaines d'application o Problèmes combinatoires : définition des investissements les plus
rentables; optimisation des niveaux d'activité, des affectations, des
transports; ordonnancements,. . .
o Problèmes stochastiques (c à d ou intervient le hasard, aléatoire) :
files d'attente; fiabilité et sûreté de fonctionnement des
équipements; gestion de la production,. . .
o Problèmes concurrentiels : définition de politiques
d'approvisionnement, de vente,. . . Les applications dans le domaine de l'informatique sont très nombreuses
elles aussi.
On peut citer, entre autres, le choix de la localisation et du nombre de
serveurs à mettre en place, de la capacité de stockage, de la puissance de
calcul et du débit du réseau, le choix d'une architecture informatique
(application centralisée / distribuée, traitements en temps réel ou en
différé, réseau maillé ou en étoile, etc.), et l'ordonnancement dans les
systèmes d'exploitation.
Recherche Opérationnelle - une discipline-carrefour La recherche opérationnelle utilise de nombreuses méthodes issues de
théories mathématiques diverses. En ce sens, une partie de la recherche
opérationnelle peut être considérée comme une branche des mathématiques
appliquées. Au-delà des méthodes, les mathématiques, notamment les
statistiques, contribuent à poser efficacement les termes d'un problème.
La théorie des jeux, bien connue des économistes, aide à résoudre les
problèmes concurrentiels.
La théorie des graphes sert de support à la résolution d'un vaste
échantillon de problèmes, notamment certains issus de l'algorithmique
classique, tels que la recherche du plus court chemin entre deux endroits,
le problème du voyageur de commerce (dans lesquels on cherche le chemin le
plus court passant par n points), les problèmes d'ordonnancement de tâche,
les problèmes de planning ou encore les problèmes d'optimisation de flux. Contenu du cours : o Programmation linéaire
. Rappels mathématiques.
. Formalisation des problèmes de programmation linéaire et
les méthodes de leur résolution.
. Post-optimisation.
o Théorie des graphes et théorie des jeux
o Exemples réels d'utilisation de réseaux :
. Identifier le cheminement dans un graphe.
. Problème de circulation flots et l'ordonnancement
algorithme du PERT.
. Transformation d'un problème de jeu en un problème de
programmation linéaire.
o Analyse multicritère et les files d'attente
. Modèle de formation.
. Méthode ELECTRE.
. Algorithme de recherche de nom ou d'un graphe.
. La typologie des files d'attente.
. Lois statiques essentielles. o Programmation linéaire
. Rappels mathématiques.
Théorie des ensembles :
Quelques Définitions :
Ensemble, élément :
Un ensemble peut être vu comme une sorte de sac virtuel entourant ses
éléments.
Les éléments peuvent être de n'importe quelle nature : nombres, points
géométriques, droites, fonctions, autres ensembles. On donne donc volontiers des exemples d'ensembles en dehors du monde
mathématique. Par exemple, lundi est un élément de l'ensemble des jours de la semaine, et
4 est un élément de l'ensemble des nombres entiers, ainsi que de l'ensemble
des nombres pairs (forcément entiers). Ces deux derniers ensembles sont
infinis, ils ont une infinité d'éléments. Élément extremum :
Un ensemble ordonné est un ensemble muni d'une relation d'ordre.
Dans un ensemble ordonné, le plus grand élément (resp. plus petit élément)
ou élément maximum (resp. élément minimum) d'une partie de cet ensemble est
l'élément qui, quand il existe, appartient à cette partie et est supérieur
(resp. inférieur) à tous autres éléments de la partie.
Fonction :
On peut voir une fonction comme une « transformation » de certains objets
en d'autres objets. Une application f d'un ensemble E dans un ensemble F est une fonction
applicative,
C'est-à-dire une correspondance dont tout élément de l'ensemble de départ E
a une et une seule image.
Extremum d'une fonction : Soient (F, ?) un ensemble totalement ordonné et f une fonction de
l'ensemble E vers l'ensemble F. Notons D, l'ensemble de définition de f et soit a un élément quelconque de
D.
On rappelle que si A est une partie de D ou D lui-même, alors la notation
f(A) désigne l'image de A par la fonction f.
Extremum global d'une fonction : Un « extremum global de f » est un « maximum global de f » ou un « minimum
global de f ». Maximum global : On dit que f(a) est le « maximum » ou le « maximum global » de f si et
seulement si pour tout élément x de D, on a f(x) ? f(a).
Cela équivaut à dire que f(a) est le plus grand élément de f(D). Minimum global : On dit que f(a) est le « minimum » ou le « minimum global » de f si et
seulement si pour tout élément x de D, on a f(a) ? f(x).
Cela équivaut à dire que f(a) est le plus petit élément de f(D). Extremum local d'une fonction : La notion d'extremum local suppose définie sur D une structure topologique
(donnant un sens précis à l'adjectif local). Dès lors, un « extremum local
de f sur D » est un « maximum