Professeur responsable

Martin Noël

* ATTENTION *

Ce cours n'est pas offert actuellement.

Objectifs

Maîtriser les techniques de la recherche opérationnelle appliquées à la gestion. Être capable de percevoir un problème, d'identifier ses variables, de le modéliser, de l'optimiser et de l'analyser.

Contenu

Rôle et domaines d'applications de la recherche opérationnelle. Modélisation de problèmes quotidiens de gestion. Résolution graphique de problèmes simples et programmation linéaire. Algorithmes de résolution et interprétation économique. Modélisation de problèmes plus complexes et programmation en nombres entiers. Principaux problèmes pratiques de réseaux : flot maximal, chemin le plus court, affectation, transport. Familiarisation avec un logiciel de programmation linéaire.

Description

La recherche opérationnelle est une science qui, après avoir pris son nom et son essor au cours de la Seconde Guerre mondiale, joue maintenant un rôle prépondérant dans les sociétés postindustrielles. À l'origine, la recherche opérationnelle était réservée aux spécialistes qui devaient posséder des habiletés poussées en modélisation, en programmation et en mathématiques en plus d'avoir accès à des ordinateurs très puissants. Pendant longtemps, ces exigences et les calculs souvent considérables exigés par la recherche opérationnelle en ont freiné le développement dans le monde de la gestion. Heureusement, la recherche fondamentale effectuée dans le domaine a donné lieu à des avancements techniques très importants. La recherche opérationnelle est maintenant accessible aux gestionnaires qui disposent de plusieurs logiciels conviviaux et de micro-ordinateurs de plus en plus rapides.

Aujourd'hui, la recherche opérationnelle constitue un outil d'aide à la décision qui utilise un certain nombre de méthodes quantitatives afin de résoudre des problèmes de gestion. Le but visé est évidemment l'accroissement de l'efficacité par l'agencement optimal des ressources. Parmi les principaux problèmes traités en recherche opérationnelle, il y a, entre autres :

  • la construction d'horaires (salles d'opération, avions, autobus, gestion des salles de cours, d'examens);
  • l'établissement de routes optimales (distribution du courrier, déneigement, collecte des ordures, distribution de produits);
  • la planification intégrée de la production (gestion de la main-d'oeuvre, gestion des stocks, planification détaillée);
  • la gestion de projets;
  • les problèmes d'affectation de personnel (hôpitaux, téléphonistes, forces policières);
  • les problèmes de localisation (ambulances, hôpitaux, postes de police, casernes de pompiers, usines, entrepôts);
  • les problèmes de composition (pétrole, moulées, café, diététique, liqueurs, croustilles);
  • les problèmes de découpe (billes de bois, bobines mères, papier peint, aluminium);
  • les problèmes de transbordement (flot maximal, chemin de longueur minimale, gestion des entrepôts, systèmes de distribution, logistique).

L'apport de la recherche opérationnelle dans ces domaines s'est traduit par des économies très importantes, et ce, à un point tel qu'il serait maintenant impensable de se passer de cet outil. Aussi, pour garantir leur survie à moyen et à long terme dans le contexte de compétitivité qui est le nôtre, les entreprises doivent devenir des « entreprises de classe mondiale ». Pour ce faire, la parfaite maîtrise de leurs opérations est nécessaire et la recherche opérationnelle est devenue un outil pratique indispensable pour les gestionnaires.

La recherche opérationnelle se trouve actuellement à un tournant de son histoire. D'un côté, les théoriciens et les spécialistes continuent à en faire avancer les fondements. D'un autre côté, les gestionnaires et les non-initiés ont accès à des outils de modélisation qui leur permettent d'utiliser la puissance des modèles de résolution sans en connaître les bases fondamentales.

Ce cours se situe à la croisée de ces chemins et pose un regard insistant sur la pratique. Dans un premier temps, une attention importante est accordée à la modélisation de problèmes réels auxquels le gestionnaire peut devoir faire face quotidiennement. Il faut se familiariser avec la façon de décrire et de modéliser des problèmes pratiques. Nous indiquons également un certain nombre d'astuces de modélisation qui permettent de traiter une multitude de situations. Notre attention est concentrée sur les modèles dits « linéaires » puisqu'ils sont les plus utilisés mais aussi parce que les méthodes de résolution sont simples et plus efficaces.

En second lieu, les principes fondamentaux des approches de résolution sont exposés. Sans trop entrer dans le détail de ces approches, on sera amené à en comprendre le fonctionnement. Pour ce faire, l'interprétation géométrique des principes algébriques est largement utilisée. Quelques techniques plus poussées d'optimisation sont également présentées afin de connaître un large éventail des méthodes disponibles.

Pour appliquer les concepts qui sont présentés, on utilise le logiciel de programmation linéaire LINDO. Ce logiciel permet de valider la compréhension des concepts de modélisation et de résolution.

À la fin de ce cours, on sera en mesure de modéliser un grand nombre de situations réelles pouvant se présenter dans un contexte de prise de décision. À l'aide des principes de modélisation, on sera en mesure d'aborder certains problèmes de décision sous un angle nouveau : l'optimisation. Grâce aux fondements des principaux algorithmes de résolution, on comprendra également l'impact de la modélisation sur le processus de résolution et sera en mesure de proposer des modèles adaptés qui augmenteront la qualité de vos décisions.

Le cours vise également l'atteinte des objectifs suivants :

  • Comprendre le rôle et les diverses applications de la recherche opérationnelle comme outil d'aide à la décision.
  • Traduire un problème de gestion sous forme de modèle mathématique et le résoudre.
  • Comprendre l'importance de la modélisation par rapport aux techniques de résolution.
  • Connaître le processus d'optimisation des modèles mathématiques.
  • Présenter et comprendre les principaux algorithmes de résolution et interpréter les solutions obtenues en termes économiques.
  • Résoudre des programmes linéaires à l'aide d'un logiciel de programmation mathématique.

Le présent cours est divisé en quatre parties qui traitent, chacune, d'un aspect particulier de la recherche opérationnelle. Voici une brève description de ces parties ainsi que des sujets qui y seront abordés.

Partie I Introduction à la recherche opérationnelle

Cette première partie du cours vous sensibilise au rôle et aux applications de la recherche opérationnelle dans la société moderne. On y voit que la recherche opérationnelle touche presque tous les aspects de la vie quotidienne.

Si vous avez besoin de rafraîchir vos connaissances en mathématiques et en algèbre, cette partie du cours propose un supplément qui donne les outils nécessaires pour bien comprendre les autres parties du cours.

Partie II La modélisation

L'aspect pratique de cette deuxième partie est en fait la partie la plus importante du cours. C'est en effet à l'intérieur de cette partie qu'est présentée la modélisation mathématique de problèmes simples, puis plus complexes. On est amené à développer ses habiletés en modélisation au moyen de plusieurs exemples.

Cette partie du cours contient trois leçons portant respectivement sur l'introduction à la modélisation, la modélisation de base puis sur la modélisation avancée.

Partie III L'optimisation

Après avoir écrit plusieurs modèles mathématiques, la question de leur optimisation peut maintenant être abordée. L'optimisation de modèles linéaires fait donc l'objet de la troisième partie du cours.

Dans un premier temps, à la leçon 5, la notion d'optimisation est présentée à l'aide d'exemples graphiques qui permettent de comprendre intuitivement comment s'effectue l'optimisation d'un modèle linéaire. La terminologie nécessaire à la poursuite du cours est également introduite dans cette leçon. Par la suite, les techniques reconnues sont abordées. Afin d'en faciliter la compréhension, les techniques sont illustrées graphiquement avant d'être présentées algébriquement. Les leçons 6, 7 et 8 présentent l'algorithme du simplexe qui est, en fait, l'algorithme le mieux connu et le plus utilisé en recherche opérationnelle. Les leçons 9 et 10 abordent successivement l'analyse postoptimale et la programmation linéaire en nombres entiers. Bien que ces quatre dernières leçons puissent paraître très théoriques, c'est la compréhension et l'intuition qui y sont privilégiées. L'étude des cas particuliers ou posant problème n'est que brièvement abordée.

Partie IV Les problèmes de réseaux

Une gamme importante de problèmes de gestion peut être représentée à l'aide de réseaux. L'objectif de cette partie est de présenter cette classe de problèmes et de montrer comment en faire la modélisation graphique puis mathématique. Finalement, nous abordons un domaine particulier de la recherche opérationnelle, la gestion de projets, qui utilise la représentation sous forme de réseaux.

Matériel didactique

Le matériel didactique comprend un guide d'étude, un guide de mise à niveau en mathématiques et en algèbre, un ensemble de logiciels de programmation linéaire sur cédérom, un guide d'utilisation du logiciel LINDO, un recueil de travaux notés et un volume, La recherche opérationnelle, de Y. Nobert, R. Ouellet et R. Parent, 2001. De plus, des outils complémentaires sont disponibles sur Internet.

Liste des documents expédiés

Renseignements technologiques

Des didacticiels et des logiciels sont fournis sur cédérom.

Encadrement

L'encadrement est individualisé et assuré par une personne tutrice. Les communications se font par téléphone ou par courriel.

Évaluation

L'évaluation porte sur trois travaux (24 %, 20 % et 16 %) et un examen sous surveillance (40 %).

Description détaillée de l'évaluation

Le premier travail noté porte sur la modélisation et la résolution de modèles linéaires. Dans ce travail, il faudra utiliser ses habiletés en modélisation mathématique afin de résoudre des problèmes de décision pratiques. On sera aussi appelé à démontrer sa maîtrise de l'algorithme du simplexe et du logiciel LINDO.

Le deuxième travail porte sur la résolution de modèles linéaires et sur l'analyse postoptimale. Il faudra utiliser ses habiletés à la fois en modélisation mathématique et en résolution de modèles linéaires. La compréhension de l'algorithme du simplexe constitue le point central de cette activité.

Le troisième travail porte à la fois sur l'interprétation et la programmation en nombres entiers et sur les problèmes de réseaux. Il faudra faire appel à ses connaissances des différents problèmes qui se prêtent bien à une résolution sous forme de réseaux.

L'examen final porte sur l'ensemble de la matière. La documentation pertinente et la calculatrice, sans restriction sur le modèle, seront permises.

Particularités d'inscription

La personne doit posséder une maîtrise raisonnable du langage mathématique : manipulation d'équations algébriques, représentations graphiques et interprétation de données.