Qu'est-ce que la recherche opérationnelle ?
La recherche opérationnelle (RO) est au confluent de l'informatique, des mathématiques
appliquées, de la gestion et du génie industriel. L'objet de cette discipline est de fournir des
bases rationnelles à la prise de décisions, habituellement dans un but de contrôle ou
d'optimisation (améliorer l'efficacité, diminuer les coûts, etc.). On utilisera par exemple des
techniques de RO pour :
Gérer les soins de santé dans les hôpitaux
Organiser les services policiers ou ambulanciers
Planifier l'utilisation et gérer la production d'énergie
Planifier des systèmes de livraison ou de transport en commun
Gérer la production, les stocks et la distribution de produits usinés
Concevoir des systèmes de communication et des systèmes informatiques
Établir des horaires de travail, de cours ou des calendriers sportifs
Choisir des politiques économiques et financières
Conférences dans les cégeps
Le Département d'informatique et de recherche opérationnelle de l'Université de Montréal est
composé d'une quarantaine de professeurs dynamiques et passionnés travaillant dans
différents domaines de l'informatique allant de l'informatique théorique et quantique au génie
logiciel en passant par la recherche opérationnelle, la bio-informatique, l'infographie, la
vision 3D, le traitement de l'image, la linguistique informatique et plus encore.
Dans le but de briser les stéréotypes par rapport à l'informatique et d'intensifier nos contacts
avec les étudiants et les professeurs des différents cégeps du Québec, nous vous proposons ici
une liste de conférenciers, tous professeurs au Département, qui seront enchantés de se
déplacer pour venir vous rencontrer et échanger avec vous de leur passion pour les sciences.
Les conférences touchent différents domaines de l'informatique et sont d'une durée d'environ
45 minutes.
Recherche opérationnelle (Operations research)
La recherche opérationnelle peut être définie comme l'ensemble des méthodes et techniques
rationnelles orientées vers la recherche du meilleur choix dans la façon d'opérer en vue
d'aboutir au résultat visé ou au meilleur résultat possible1.
Elle fait partie des « aides à la décision » dans la mesure où elle propose des modèles
conceptuels en vue d'analyser et de maitriser des situations complexes pour permettre aux
décideurs de comprendre, d'évaluer les enjeux et d'arbitrer ou de faire les choix les plus
efficaces2.
Ce domaine fait largement appel au raisonnement mathématique (logique, probabilités,
analyse des données) et à la modélisation des processus. Il est fortement lié à l'ingénierie des
systèmes, ainsi qu'au management du système d'information.
Relations avec d'autres disciplines
La recherche opérationnelle se situe au carrefour de différentes sciences et technologies. Par
exemple, l'analyse économique est souvent nécessaire pour définir l'objectif à atteindre ou
pour identifier les contraintes d'un problème.
Elle est aussi liée à l'ingénierie des systèmes. Par rapport à celle-ci, le champ d'application de
la recherche opérationnelle est historiquement plus axé sur les événements incertains et
l'industrie, et ses méthodes plus particulièrement mathématiques.
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. Les mathématiques,
notamment les statistiques, contribuent aussi à poser efficacement les termes d'un problème.
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 les problèmes de plus court
chemin, le problème du voyageur de commerce, les problèmes d'ordonnancement de tâches,
les problèmes de planning ou encore les problèmes d'optimisation de flux.
Les progrès de l'informatique sont intimement liés à l'accroissement des applications de la
recherche opérationnelle. Une puissance de calcul importante est nécessaire à la résolution de
problèmes de grande taille. Cette puissance est cependant loin de constituer une panacée : la
théorie de la complexité des algorithmes nous apprend que certains problèmes ne peuvent pas
être résolus de manière optimale dans un temps raisonnable, même si l'on considère des
ordinateurs un milliard de fois plus puissants que ceux d'aujourd'hui.
Plusieurs méthodes de résolution de problèmes sont issues de l'intelligence artificielle. Alors
que l'approche de l'intelligence artificielle est de proposer des méthodes de résolution
génériques, la recherche opérationnelle utilise ces méthodes en les spécialisant pour les
rendre plus efficaces à résoudre des classes plus restreintes de problèmes.
On peut aussi citer la théorie des jeux, bien connue des économistes, qui aide à résoudre les
problèmes concurrentiels.
Principales (classes de) méthodes
Algorithmes polynomiaux
Certains problèmes de recherche opérationnelle ne sont pas NP-complets. Dans ce
cas, on utilise un algorithme polynomial pour le résoudre, si le polynôme est de degré
raisonnable.
Programmation dynamique
Certains problèmes ont de bonnes caractéristiques qui permettent de les résoudre à
l'aide d'une formule de récurrence. Les méthodes de programmation dynamique
peuvent alors éventuellement permettre de résoudre le problème avec une complexité
polynomiale ou complexité pseudo-polynomiale.
Processus stochastiques
Les processus stochastiques concernent tous les problèmes aléatoires, en particulier
des problèmes de fiabilité (de systèmes, de composants électroniques…) et
l'optimalité de gestion des files d'attente.
Théorie des graphes
Les problèmes d'ordonnancement sont résolus à l'aide des graphes.
Simulation informatique
La simulation est souvent employée pour résoudre des problèmes de RO, notamment
dans le milieu non académique.
Optimisation linéaire et non linéaire
L'optimisation linéaire est très souvent utilisée pour résoudre des problèmes
combinatoires. Elle permet de résoudre très efficacement les problèmes dans lesquels
les variables sont continues. Lorsqu'il y a des variables discrètes, optimisation linéaire
et méthodes arborescentes (voir ci-après) peuvent être combinées.
L'optimisation non linéaire peut aussi être utilisée. La possibilité d'utiliser des
contraintes ou des fonctions objectifs non linéaires offre une puissance de
modélisation très importante, mais les algorithmes de résolution des problèmes
d'optimisation non linéaire sont significativement moins efficaces que ceux de
l'optimisation linéaire.
Méthodes de complémentarité linéaire et non linéaire
Méthodes arborescentes
Les méthodes de type A* ou branch and bound sont couramment utilisées pour
trouver la solution exacte d'un problème de recherche opérationnelle. Pour une
résolution efficace, un soin particulier est apporté au calcul de bornes supérieures ou
inférieures pour la valeur de la solution.
La programmation par contraintes permet de mettre en œuvre rapidement et
efficacement de telles méthodes de recherche arborescente. Plusieurs bibliothèques
(logiciels) d'optimisation commerciales ou non reposent sur cette approche (ILOG
Solver, Chip, Mozart/Oz, FaCiLe). De nombreux logiciels d'optimisation de
problèmes réels utilisent ainsi cette technologie.
Heuristiques et métaheuristiques
Lorsque la solution optimale ne peut être obtenue en un temps raisonnable, on a
souvent recours à des méthodes approchées de type heuristique ou métaheuristique.
Bibliographie
Robert Faure, Bernard Lemaire et Christophe Picouleau. Précis de recherche
opérationnelle [archive] - Méthodes et exercices d'application - 6e édition. Dunod.
Dominique de Werra, Thomas M. Liebling et Jean-François Hêche. Recherche
opérationnelle pour ingénieurs [archive] - Presses polytechniques et universitaires
romandes. 2003.
Éric Jacquet-Lagrèze. Programmation Linéaire - Modélisation et mise en œuvre
informatique [archive] Collection : P.I.Q. Poche - Editeur : Economica
J. G. Kemeny, A. Schleifer, J.L. Snell, G.L. Thompson, trad. par M. Didier, Les
Mathématiques modernes dans la pratique des affaires, Paris, Dunod, 1964.
Algorithme de Luhn
Les chiffres de toute carte de crédit ou de débit obéissent à une formule complexe dénommée
l'algorithme de Luhn. L'outil proposé ici repose sur l'implémentation de cet algorithme et
permet de vérifier la validité de n'importe quelle carte. Pour toute demande ou n'importe
quelle difficulté rencontrée, n'hésitez pas à contacter le webmaster.
Sécurité
Ce processus de vérification ne présente aucun danger de sécurité. Vous ne devez entrer que
les numéros de la carte et absolument aucune donnée personnelle telle que Nom, Date
d'expiration, et surtout pas le cryptogramme visuel (CVV - Card Verification Value en
anglais) qui est généralement situé au dos de la carte (sauf pour les amex). Cette séquence de
chiffre seule reste inexploitable pour toute tentative d'achat frauduleux.
De plus, aucune donnée n'est stockée sur le serveur et les calculs sont tous faits à la volée.
A quoi correspondent les chiffres d'une carte bancaire?
Chaque position des chiffres a un rôle particulier tel que: définir le type d'émetteur (IIN en
anglais), le numéro de compte, le chiffre de complétude aves l'agorithme de Lunh, etc... Le
lien suivant reprend pour chaque position dans la séquence de chiffre ou pour chaque sous-
groupe de chiffres leur fonction propre: Déchiffrons notre numéro de carte bancaire
Liens utiles
Vous recherchez un taux de change pour vos achats en ligne? Nous recommendons cet outil.
Algorithme de Luhn
