OPÉRATIONNELLE RECHERCHE

Carte mentale

Élargissez votre recherche dans Universalis

Les études combinatoires

Dans ce contexte déterminé, les éléments nécessaires au calcul des décisions sont connus avec exactitude, à la précision des mesures près éventuellement. La principale difficulté réside dans le très grand nombre de solutions possibles entre lesquelles le choix doit s'exercer pour ne retenir que la plus favorable. Les algorithmes de la théorie des graphes et les techniques de programmation linéaire permettent heureusement une convergence vers la meilleure solution sans avoir à énumérer toutes les possibilités.

La théorie des graphes

La théorie des graphes s'introduit avec facilité dans la description de solutions concrètes où existent des combinaisons d'événements ou des successions temporelles (cf. théorie des graphes). Ses algorithmes sont de puissants auxiliaires pour l'analyste. D'abord parce que l'algorithme, prescription détaillée des opérations à réaliser pour obtenir avec certitude la solution d'un type de problème, peut être confié à l'ordinateur ; ensuite parce que la manifestation fondamentale de l'organisation chez l'homme étant l'ordre et l'équivalence, il est bien naturel que la théorie des graphes, dont la principale préoccupation est l'étude des relations pouvant exister entre les éléments d'un ensemble, se soit intéressée à ces problèmes.

Les algorithmes de la théorie des graphes sont très utiles dans l'ordonnancement d'un travail. Celui dit du chemin critique est à la base d'une technique très en vogue dans les centres de recherche et les entreprises. Il s'agit d'instituer une méthode permettant de définir les « étapes critiques », c'est-à-dire celles dont la réalisation ne doit être retardée sous aucun prétexte faute de quoi l'achèvement de l'ouvrage le serait d'autant. C'est la méthode américaine P.E.R.T. (Program Evaluation and Review Technique) ou sa variante française des « potentiels » ; on peut désirer connaître la date au plus près de l'achèvement d'un ouvrage nécessitant trois opérations A, B et C demandant respectivement 3, 5 et 2 unités de temps. Ce travail comportant les étapes a : début des opérations, b : fin de l'opération A, et c : fin des travaux.

L'ordonnancement des opérations est le suivant : l'opération A doit précéder l'opération B, laquelle ne peut être terminée qu'après achèvement complet de l'opération C. Un graphe met en évidence les opérations à effectuer et les étapes à parcourir de l'origine à la fin des travaux : les arcs indiquent le sens de l'ordonnancement, la valeur portée par chaque arc donne la durée de l'opération correspondante, le chemin critique est le chemin de valeur maximale entre les sommets a et c ; c'est ici le chemin abc, de valeur 3 + 5 = 8. Si l'époque t indique le début des opérations, la date au plus près de l'achèvement des travaux est t + 8, l'étape b est une étape critique. Pour entreprendre l'opération C, on dispose de quelque liberté : on peut attendre 6 unités de temps (intervalle de flottement) les moyens nécessaires à son accomplissement, mais la date t + 6 est une date limite ; après cette date, c'est le chemin ac qui deviendrait le chemin critique.

Un algorithme permet la détermination du chemin et donc des étapes critiques, ce qui est particulièrement précieux pour les grands travaux, constructions de barrages, d'avions, de bateaux, d'immeubles, de grands ensembles, etc., pour lesquels les graphes comportent souvent plusieurs milliers de sommets. Les graphes offrent bien d'autres possibilités au chercheur et à l'ingénieur, et il faudrait y consacrer de nombreuses pages pour en donner un pâle reflet.

La programmation linéaire

Dans l'étude des problèmes de l'entreprise, les programmes linéaires ont un vaste domaine d'application. Ils sont rapidement devenus des outils efficaces dans les études de gestion, de conditions de travail, de fabrication, de spécifications particulières. Les applications militaires sont nombreuses, les mathématiques pures ou appliquées en font un large usage. Dans de nombreux secteurs de l'économie, leur emploi est maintenant courant : alimentation, chimie, énergie, papeterie, transports, mines, agriculture, etc. Les types de problèmes abordés concernent les plans de production, les affectations de personnel, les distributions et les transports, les communications, les relations, etc. Un chef d'entreprise peut, par exemple, s'efforcer d'atteindre un chiffre d'affaires donné en rendant minimal le coût des fabrications sans dépasser le niveau des investissements autorisés, de la main-d'œuvre et de l'énergie dont il dispose. La programmation linéaire peut aussi s'appliquer en macro-économie, par exemple au niveau de la planification.

Mathématiquement, il s'agit de déterminer les valeurs, ou encore les niveaux d'activités de variables, ou activités X1, X2, ..., Xj, ..., Xn, représentant les paramètres du programme, ces valeurs devant satisfaire simultanément à un certain nombre de contraintes relatives aux ressources et, de plus, rendre optimale (maximale ou minimale) une fonction de coûts (fonctionnelle ou fonction objectif). Les contraintes peuvent être de nature très diverse : disponibilités en matière première, en personnel ; investissements consentis ; capacité de production, de stockage, de transport ; frais de transport ; longueur de parcours.

Selon que les ressources sont homogènes ou non, la programmation linéaire utilise deux méthodes essentielles (cf. programmation linéaire et optimisation) : la méthode du simplexe permet, à partir de considérations algébriques, de trouver une solution admissible, c'est-à-dire n'excédant pas les ressources, puis d'améliorer pas à pas cette solution initiale jusqu'à la meilleure solution, optimisant la fonction objectif tout en respectant les limitations de ressources ; la méthode des transports donne la façon la moins onéreuse de répartir un produit disponible dans certains centres vers des lieux de destination : on recherche une solution de base satisfaisant l'ensemble des demandes à l'aide de la totalité des disponibilités ; puis, compte tenu du coût de transport de chaque centre vers chaque destination, on s'efforce de retoucher le plan de transport pour atteindre progressivement la solution de coût total minimal.

La méthode du simplexe

On peut rechercher dans une entreprise les valeurs xj d'un certain nombre d'activités Xj pour j allant de 1 à n, les ressources étant limitées à b1 pour l'investissement, b2 pour les frais de stockage, b3 pour les heures de travail, b4 pour la consommation d'énergie, et ainsi de suite jusqu'à bm, ≤ n. En supposant connus, pour chaque activité Xj, l'investissement unitaire a1j, le coût de stockage unitaire a2j, le temps de fabrication unitaire a3j, la consommation unitaire d'énergie a4j, etc. ; après avoir évalué le profit unitaire cj escompté sur chaque activité Xj ; si l'on admet que les effets sont proportionnels aux causes et si l'on cherche à maximiser le profit, le programme linéaire à résoudre s'écrit :

F étant à maximiser.

Les activités [...]

1  2  3  4  5
pour nos abonnés,
l’article se compose de 9 pages

Médias de l’article

Blaise Pascal

Blaise Pascal
Crédits : Hulton Archive/ Getty Images

photographie

Opérations à effectuer et étapes à parcourir de l'origine à la fin des travaux

Opérations à effectuer et étapes à parcourir de l'origine à la fin des travaux
Crédits : Encyclopædia Universalis France

dessin

Afficher les 2 médias de l'article


Écrit par :

  • : ingénieur à l'Ecole supérieure d'électricité, directeur de la division "Enseignement" du Centre interarmées de recherche opérationnelle

Classification

Autres références

«  OPÉRATIONNELLE RECHERCHE  » est également traité dans :

ÉCONOMIE (Définition et nature) - Objets et méthodes

  • Écrit par 
  • Henri GUITTON
  •  • 6 469 mots

Dans le chapitre « La recherche opérationnelle »  : […] Le mot de recherche exprime bien l'esprit de toute science. Rechercher, c'est accepter de se tromper, c'est œuvrer pour s'approcher d'une solution. La recherche est opérationnelle par nature. Cette expression ( operational research ) a pris naissance dans le domaine de la stratégie militaire. La recherche opérationnelle est alors tâche d'état-major, de collaboration entre esprits de formation et […] Lire la suite

Voir aussi

Pour citer l’article

Georges CULLMANN, « OPÉRATIONNELLE RECHERCHE », Encyclopædia Universalis [en ligne], consulté le 02 décembre 2021. URL : https://www.universalis.fr/encyclopedie/recherche-operationnelle/