OPÉRATIONNELLE RECHERCHE

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[...]