I- HISTORIQUE

Qu'est-ce que la recherche opérationnelle?

La recherche opérationnelle (RO) vise à l'amélioration du fonctionnement des entreprises et des organismes publics par l'application de l'approche scientifique. Reposant sur l'utilisation de méthodes scientifiques, de techniques spécialisées et des ordinateurs, la RO permet d'obtenir une évaluation quantitative des politiques, stratégies et actions possibles dans le cours des opérations d'une organisation ou d'un système.

La RO est apparue en Grande-Bretagne durant la Seconde Guerre mondiale, lorsqu'on décida d'employer des méthodes scientifiques pour étudier divers aspects des opérations militaires. Depuis lors, la RO est devenue un élément important du processus de prise de décision dans de nombreux contextes commerciaux, industriels et gouvernementaux, car elle permet d'appréhender de façon systématique la complexité toujours grandissante des problèmes de gestion auxquels sont confrontés tant le secteur privé que public.

À la suite des succès obtenus dans le domaine militaire durant la Seconde Guerre mondiale, la RO a été appliquée durant de nombreuses années à des problèmes de nature opérationnelle dans l'industrie et le secteur public. Depuis une dizaine d'années, le champ d'application de la RO s'est élargi à des domaines comme l'économie, la finance, le marketing et la planification d'entreprise. Plus récemment, la RO a été utilisée pour la gestion des systèmes de santé et d'éducation, pour la résolution de problèmes environnementaux et dans d'autres domaines d'intérêt public. Les principaux utilisateurs de la RO au Canada sont les entreprises de fabrication, de distribution et de commerce au détail dans les secteurs miniers, de l'énergie, du transport et de la construction, les entreprises de service comme les banques, ainsi que de nombreux organismes gouvernementaux. Parmi les sujets d'application récents de la RO, on peut mentionner :

• les études logistiques (Forces armées canadiennes),
• la sécurité ferroviaire (Commission canadienne des transports),
• la conception d'emballages (Emballages Domtar Ltée),
• la gestion prévisionnelle du personnel (Secrétariat du Conseil du Trésor),
• le transport aérien (Air Canada),
• les opérations forestières (Nova Scotia Research Council),
• l'optimisation du carburant nucléaire (Ontario Hydro),
• la détermination du prix des copeaux de bois (B.C. Research),
• l'affectation des ressources dans un hôpital psychiatrique (Hôpital Douglas),
• l'étude des réseaux de commutation (Recherches Bell-Northern Ltée),
• la planification de la production (Aigle d'or Ltée).

Les premiers chercheurs opérationnels avaient une formation en sciences physiques, biologiques ou sociales; ils appliquaient aux problèmes qui leur étaient soumis les méthodes propres à leur discipline. De nos jours, les chercheurs opérationnels ont, pour la plupart, reçu une formation spécialisée en RO dans une université canadienne ou étrangère. Il s'agit souvent d'un diplôme de deuxième ou troisième cycle en RO obtenu après des études de premier cycle en sciences, en génie, en mathématiques ou en gestion.

Pour réussir, le chercheur opérationnel doit faire preuve de grandes habilités analytiques, d'un esprit ouvert et d'un intérêt marqué pour la résolution de problèmes pratiques.

Une carrière en recherche opérationnelle

À l'heure actuelle, au Canada, on retrouve des personnes possédant une formation en RO à l'intérieur d'équipes spécialisées en RO oeuvrant dans divers secteurs d'organismes privés ou publics. Les méthodes de la RO sont aussi appliquées par des économistes, des ingénieurs, des scientifiques, des administrateurs et des cadres supérieurs dans la résolution de problèmes de gestion et de politique d'entreprise.

La RO est actuellement utilisée dans une trentaine de ministères et organismes fédéraux, une cinquantaine de ministères et organismes provinciaux et une vingtaine d'administrations municipales et locales. On fait aussi un grand usage de la RO dans de nombreuses firmes canadiennes de gestion et de conseil, dans plusieurs centaines d'entreprises commerciales et industrielles réparties à travers le Canada, dans les banques et les sociétés financières et d'assurance ainsi que dans les conseils, fondations et instituts de recherche.

Depuis l'apparition de la RO au Canada il y a une cinquantaine d'années, les décideurs et les gestionnaires y ont recours très fréquemment. Ses applications sont en pleine expansion alors que l'envergure et la complexité des problèmes soumis aux praticiens de la RO n'ont pas cessé de s'accroître. En conséquence, le développement de techniques et méthodes nouvelles pour faire face à ces nouveaux problèmes a provoqué chez les gestionnaires de tous les secteurs des affaires, de l'industrie et du gouvernement une prise de conscience sans cesse grandissante de la nécessité de telles techniques et méthodes ainsi qu'une plus grande confiance en ce que la RO peut faire pour la gestion et la prise de décisions. Il y a dans les secteurs public et privé une demande croissante et un besoin certain des services de la RO.

Études en recherche opérationnelle

Le premier cours en recherche opérationnelle a été donné à l'Université de Toronto, en 1956, sous forme de cours du soir. Depuis, beaucoup d'autres universités, collèges et instituts techniques offrent des cours en RO et, aujourd'hui, il existe au Canada plus de quarante établissements d'enseignement supérieur offrant des cours en recherche opérationnelle et dans les disciplines qui s'y rattachent. Ces cours sont offerts dans toutes les provinces par des facultés (ou départements) de sciences de la gestion, d'administration des affaires, de commerce, d'économie, d'ingénierie, de mathématiques, de méthodes quantitatives ou d'informatique. Les diplômes en RO sont accordés dans diverses universités au niveau du baccalauréat, de la maîtrise et du doctorat. La formation universitaire d'un chercheur opérationnel peut aboutir à un diplôme en RO comprenant des cours de sciences, d'ingénierie, de mathématiques, de statistiques ou d'administration, ou bien à un diplôme de base dans une ou plusieurs de ces disciplines accompagné d'une formation en RO au niveau du deuxième ou du troisième cycle.

La Société canadienne de recherche opérationnelle

Depuis 1958, il existe au Canada une société de RO, appelée Société canadienne de recherche opérationnelle (SCRO). Elle a pour but de promouvoir la théorie et la pratique de la recherche opérationnelle et de stimuler et promouvoir les contacts entre les personnes qui s'intéressent à la RO. Ses principales activités sont les suivantes :

Publications : La SCRO publie une revue scientifique trimestrielle, « INFOR », conjointement avec la Société canadienne de traitement de l'information, ainsi qu'un bulletin qui paraît plusieurs fois par année.

NOTIONS ELEMENTAIRES SUR LES GRAPHES

1) GRAPHE ORIENTÉ

Un graphe orienté G est un couple (X,R)
      où X est un ensemble de sommets {x1,..., xn}
      et R un ensemble de couples orientés (xi,xj) appelés arcs.

Pour un arc (xi,xj) d'origine xi et d'extrémité xj, xi est un précédent de xj, et xj est un suivant de xi .

Un chemin est une suite ordonnée (x1,...,xn) de sommets reliés par des arcs. La longueur du chemin est le nombre d'arcs qu'il contient.

Un circuit est un chemin (x1,...,xn) tel que x1 = xn .

2) DICTIONNAIRE

Outre une représentation graphique sagittale, un graphe peut être représenté par un tableau, appelé dictionnaire, qui à chaque sommet énumère les suivants et les précédents:

 

Sommets x	Précédents P(x)	Suivants S(x)
x1	-	x2 , x3
x2	x1 , x3	x4
x3	x1	x2 , x4
x4	x2 , x3	x5 , x6
x5	x4	x6
x6	x4 , x5	-

3) NIVEAUX

Dans un graphe sans circuit, le niveau d'un sommet x est la longueur du plus long chemin d'extrémité x.
La détermination des niveaux se fait à partir du dictionnaire des précédents:

Sommets x  Précédents P(x)  x1   -  x2  x1 , x3  x3  x1   x4  x2 , x3  x5  x4   x6  x4 , x5		C0 = {sommets de niveau 0}      = {sommets n'ayant pas de précédent}= { x1} Tous les sommets x1 sont barrés (en rouge ici), d'où le tableau ci-dessous

Sommets x  Précédents P(x)  x1   -  x2  x1 , x3  x3  x1   x4  x2 , x3  x5  x4   x6  x4 , x5		Les sommets barrés (en rouge) sont considérés comme n'existant plus. C1 = {sommets de niveau 1}      = {sommets n'ayant pas de précédent}= { x3} Tous les sommets x3 sont barrés (en rouge ici), d'où le tableau ci-dessous

Sommets x  Précédents P(x)  x1   -  x2  x1 , x3  x3  x1   x4  x2 , x3  x5  x4   x6  x4 , x5		Les sommets barrés (en rouge) sont considérés comme n'existant plus. C2 = {sommets de niveau 2}      = {sommets n'ayant pas de précédent}= { x2} Tous les sommets x2 sont barrés (en rouge ici), d'où le tableau ci-dessous

Sommets x  Précédents P(x)  x1   -  x2  x1 , x3  x3  x1   x4  x2 , x3  x5  x4   x6  x4 , x5		Les sommets barrés (en rouge) sont considérés comme n'existant plus. C3 = {sommets de niveau 3}      = {sommets n'ayant pas de précédent}= { x4} Tous les sommets x4 sont barrés (en rouge ici), d'où le tableau ci-dessous

Sommets x  Précédents P(x)  x1   -  x2  x1 , x3  x3  x1   x4  x2 , x3  x5  x4   x6  x4 , x5		Les sommets barrés (en rouge) sont considérés comme n'existant plus. C4 = {sommets de niveau 4}      = {sommets n'ayant pas de précédent}= { x5} Tous les sommets x5 sont barrés (en rouge ici), d'où le tableau ci-dessous

Sommets x  Précédents P(x)  x1   -  x2  x1 , x3  x3  x1   x4  x2 , x3  x5  x4   x6  x4 , x5		Les sommets barrés (en rouge) sont considérés comme n'existant plus. C5 = {sommets de niveau 5}      = {sommets n'ayant pas de précédent}= { x6} Tous les sommets x6 sont barrés (en rouge ici), d'où le tableau ci-dessous

Sommets x  Précédents P(x)  x1   -  x2  x1 , x3  x3  x1   x4  x2 , x3  x5  x4   x6  x4 , x5		Tous les sommets ayant été barrés, l'algorithme est terminé. Les niveaux sont donc C0 = { x1} C1 = { x3} C2 = { x2} C3 = { x4} C4 = { x5} C5 = { x6} D'où la représentation du graphe par niveaux ci-dessous

4) CHEMINS EXTREMAUX

A chaque arc (x,y) est associé un nombre positif V(x,y) appelé la valeur de l'arc. La valeur d'un chemin est la somme des valeurs des arcs dont il est composé.
L'algorithme de Ford va nous permettre de déterminer le chemin de valeur maximale entre un sommet D et un sommet F.

a) On ordonne le graphe par niveaux
b) On fait la représentation du graphe par niveaux.
A partir de cette représentation, on supprime les sommets et les arcs par lesquels on ne peut pas passer pour aller de D à F.
c) En partant du sommet D de niveau le plus faible (le plus à gauche) jusqu'au sommet F de niveau le plus fort (le plus à droite), on associe à chaque sommet x une marque m(x) correspondant à la valeur du chemin de valeur maximale aboutissant à x.
m(D) = 0
m(x) = max [m(y) + V (y,x)]  , le max étant pris sur tous les précédents y de x
La marque de F donnera donc la valeur du chemin le valeur maximale entre D et F. Le chemin de valeur maximale est le chemin qui a permis d'aboutir à la marque de F. Il est obtenu en partant de F et en regardant quel est le sommet précédent qui a permis d'obtenir m(F), et ainsi de suite jusqu'à revenir en D.

Pour un chemin de longueur minimale, il suffit de remplacer "max" par "min" dans l'algorithme.

 ORDONNANCEMENT   MPM   PERT  

Un problème d'ordonnancement consiste à ordonner dans le temps un ensemble de tâches contribuant à la réalisation d'un même projet. L'objectif est de minimiser la durée de réalisation du projet compte tenu des contraintes d'antériorité reliant les différentes tâches. De plus, on détermine les calendriers de réalisation de chacune de ces tâches aini que les marges de manoeuvre associées.

Deux méthodes sont classiquement utilisées: la Méthode des Potentiels Metra (MPM), et la méthode PERT (Programm Evaluation and Research Task). Toutes les deux utilisent une représentation graphique pour résoudre le problème.

1) MPM

a) Construction du graphe

- un sommet correspond à une tâche
- un arc définit une relation d'antériorité
- la valeur de l'arc définit le temps minimum séparant deux tâches successives.

- Chaque sommet de la représentation graphique est figuré par un rectangle         

Tx	T*x
x

où      x = nom de la tâche
        Tx  = date de début au plus tôt de la tâche
        T*x  = date de début au plus tard de la tâche

- Un sommet terminal permettant de dater la fin des travaux est rajouté au graphe.

- La représentation graphique est ordonnée par niveaux des sommets, c.à.d. des tâches.

b) Calendrier au plus tôt

Une tâche x ne pouvant débuter que lorsque toutes les tâches qui y aboutissent sont terminées, Tx correspond à la valeur du chemin de valeur maximale aboutissant à x. Ceci sera obtenu en utilisant l'algoritme de Ford, après avoir ordonné le graphe par niveaux des tâches.

Tx = max [Ty + V(y,x)]  , le max étant pris sur les précédents y de x.

Pour le sommet terminal z, Tz correspond à la durée minimale du projet (qui correspond au chemin de valeur maximale aboutissant à z). Le chemin de valeur maximale associé est appelé chemin critique, constitué de tâches critiques: un retard sur l'une de tâches critiques entraînerait un allongement de la durée du projet.

c) Calendrier au plus tard

Il s'agit de la date au plus tard à laquelle peut commencer une tâche sans remettre en cause la date de fin des travaux. Ceci sera obtenu en commençant par les sommets de niveau les plus élevés jusqu'aux sommets de niveau les plus faibles.

T*z = Tz    pour le sommet terminal
T*x = min [T*y - V(x,y)]  , le min étant pris sur les suivants y de x.

Remarque: sur les tâches critiques, T*x = Tx 

d) Marges totales

C'est le retard maximum que l'on peut prendre dans la mise en route d'une tâche sans remettre en cause les dates au plus tard des tâches suivantes (donc sans retarder la fin des travaux).

mT(x) = T*x - Tx

e) Marges libres

C'est le retard maximum que l'on peut prendre dans la mise en route d'une tâche sans remettre en cause les dates au plus tôt des tâches suivantes (donc sans retarder la fin des travaux).

mL(x) = min [Ty - Tx - V(x,y)] , le min étant pris sur les suivants y de x.

2) PERT

a) Construction du graphe

- un arc correspond à une tâche
- la valeur de l'arc représente la durée de la tâche.
- un sommet est une étape signifiant
               toutes les tâches qui y arrivent sont terminées
               toutes les tâches qui en partent peuvent commencer

a et b doivent être terminées pour que c et d puissent commencer

Remarque 1: il est quelque fois nécessaire d'introduire des tâches fictives de durée nulle

a et b doivent être terminées pour que c puisse commencer et uniquement b doit être terminée pour que d commence

Remarque 2: deux arcs ne peuvent avoir à la fois la même origine et la même extrémité. Il est nécessaire de rajouter une tâche fictive dans ces conditions:

sera transformé en

- Chaque sommet de la représentation graphique est figuré par un cercle 

 
      où      n = nom ou numéro de l'étape
                tn  = date de début au plus tôt de l'étape
                t*n  = date de début au plus tard de l'étape

 

- Un sommet terminal et un sommet initial sont rajoutés au graphe.

- La représentation graphique est ordonnée par niveaux des sommets, c.à.d. des étapes.

b) Calendrier au plus tôt des étapes

Une étape n ne pouvant débuter que lorsque toutes les étapes qui y aboutissent sont terminées, tn correspond à la valeur du chemin de valeur maximale aboutissant à n. Ceci sera obtenu en utilisant l'algoritme de Ford, après avoir ordonné le graphe par niveaux des étapes.

tn = max [tm + V(m,n)]  , le max étant pris sur les précédents m de n.

Pour le sommet terminal z, tz correspond à la durée minimale du projet (qui correspond au chemin de valeur maximale aboutissant à z). Le chemin de valeur maximlale associé est appelé chemin critique, constitué de tâches critiques: un retard sur l'une de tâches critiques entraînerait un allongement de la durée du projet.

c) Calendrier au plus tôt des tâches

La date de début au plus tôt d'une tâche x est égale à la date de début au plu tôt de l'étape dont elle est issue.

Tx = tn    si la tâche x est issue de l'étape n

d) Calendrier au plus tard des étapes

Il s'agit de la date au plus tard à laquelle peut commencer une étape sans remettre en cause la date de fin des travaux. Ceci sera obtenu en commençant par les sommets de niveau les plus élevés jusqu'aux sommets de niveau les plus faibles.

t*z = tz    pour le sommet terminal
t*n = min [t*m - V(n,m)]  , le min étant pris sur les suivants m de n.

e) Calendrier au plus tard des tâches

La date de début au plus tard d'une tâche x est égale à la date de début au plus tard de l'étape à laquelle elle aboutit, diminuée de la durée de la tâche

T*x = t*m - V(n,m) ,  si la tâche x va du sommet n au sommet m

Remarque: sur les tâches critiques, T*x = Tx 

f) Marges totales

C'est le retard maximum que l'on peut prendre dans la mise en route d'une tâche sans remettre en cause les dates au plus tard des tâches suivantes (donc sans retarder la fin des travaux).

mT(x) = T*x - Tx

g) Marges libres

C'est le retard maximum que l'on peut prendre dans la mise en route d'une tâche sans remettre en cause les dates au plus tôt des tâches suivantes (donc sans retarder la fin des travaux).

mL(x) = tm - tn - V(n,m) ,  si la tâche x va du sommet n au sommet m

Remarque: si du sommet d'arrivée m ne partent que des tâches fictives, on retiendra le minimum sur tous les premiers sommets suivants d'où partent au moins une tâche réelle.

  VOIR LA SUITE EN RECHERCHE OPERATIONNELLE AVANCEE (SUITE 1) important svp