Modèles de réseau

Modèles de réseau (en recherche opérationnelle ; en anglais Network models) — une classe de modèles mathématiques qui représentent un problème sous la forme d'un graphe (ou réseau), où les sommets (nœuds) désignent des objets ou des états, et les arêtes (arcs) représentent les liens ou les processus entre eux. Dans le contexte de l'optimisation, un réseau est souvent compris comme un graphe orienté, que l'analyse opérationnelle appelle directement « réseau » ; les sommets de ce réseau sont appelés nœuds et les arêtes sont appelées arcs.

Les modèles de réseau sont un outil puissant pour l'analyse et l'optimisation de systèmes complexes dans des domaines tels que la logistique, les télécommunications, la gestion de projet et la finance. Leur force réside dans leur haut niveau d'abstraction : un nœud peut représenter une ville, un routeur informatique ou une étape de projet, tandis qu'un arc peut représenter une route, un canal de communication ou une opération technologique.

Définition et terminologie

La théorie des graphes constitue la base des modèles de réseau. Les concepts clés sont les suivants :

• Réseau de flot (en anglais flow network) : un graphe orienté où chaque arête possède une capacité (capacity) et un flot (flow). Le graphe distingue deux sommets particuliers : la source (source), d'où le flot émane, et le puits (sink), où il aboutit.
• Loi de conservation du flot : Pour tout sommet qui n'est ni la source ni le puits, le flot total entrant doit être égal au flot total sortant. Cette condition est l'analogue discret des lois physiques de conservation.
• Planification de réseau : Un modèle représentant un projet comme un ensemble d'opérations interdépendantes (arcs) et d'événements (nœuds). De tels réseaux sont des graphes orientés acycliques, ce qui reflète l'ordre d'exécution des tâches.

Propriétés clés et théorèmes

Les modèles de réseau possèdent un certain nombre de propriétés particulières qui permettent d'utiliser des algorithmes très efficaces pour les résoudre.

• Intégrité des solutions : De nombreux problèmes d'optimisation de réseau (par exemple, le flot maximum ou le plus court chemin) possèdent la propriété d'unimodularité totale de la matrice des contraintes. Grâce à cela, si les paramètres du problème (capacités, longueurs) sont des entiers, la solution optimale trouvée par des méthodes de programmation linéaire sera également entière sans qu'il soit nécessaire d'introduire des contraintes supplémentaires.
• Théorème flot-max/coupe-min : Le résultat central de la théorie des flots. Il affirme que la valeur maximale du flot de la source au puits est égale à la capacité minimale de toutes les coupes séparant la source et le puits. Ce théorème établit un critère d'optimalité pour le flot et constitue la base de nombreux algorithmes.
• Principe d'optimalité pour les plus courts chemins : Si un chemin du point A au point C est un plus court chemin, alors toute sous-partie de ce chemin (par exemple, du point intermédiaire B à C) est également un plus court chemin entre les sommets correspondants. Cette propriété, qui est à la base de la programmation dynamique, assure la validité d'algorithmes tels que l'algorithme de Dijkstra.
• Propriétés de l'arbre couvrant de poids minimal (ACPM) :
• Propriété de la coupe : Pour toute coupe d'un graphe, l'arête de poids minimal traversant la coupe appartient à au moins un ACPM.
• Propriété du cycle : Dans tout cycle d'un graphe, l'arête de poids maximal n'appartient à aucun ACPM.

La validité des algorithmes « gloutons » de Prim et de Kruskal repose sur ces propriétés.

Problèmes fondamentaux de l'optimisation de réseau

• Problème du plus court chemin : Trouver un chemin de longueur (poids) totale minimale entre deux nœuds donnés. Résolu par l'algorithme de Dijkstra (pour des poids non négatifs) ou l'algorithme de Bellman-Ford (pour des poids arbitraires).
• Problème du flot maximum : Déterminer le plus grand flot possible de la source au puits, compte tenu des capacités des arcs. La méthode classique de résolution est l'algorithme de Ford-Fulkerson.
• Problème de l'arbre couvrant de poids minimal : Trouver un sous-graphe qui relie tous les sommets du réseau et a un coût total d'arêtes minimal.
• Méthode du chemin critique (CPM) : Dans les modèles de planification de réseau, déterminer la plus longue séquence de tâches, qui établit la durée minimale possible pour l'achèvement du projet entier. Les tâches sur ce chemin ont une marge de temps nulle.

Exemples

• Plus court chemin : Recherche de l'itinéraire optimal par un système de navigation entre deux points sur une carte de ville, où les villes sont des nœuds et les routes des arcs avec des poids égaux à la longueur ou au temps de parcours.
• Flot maximum : Détermination de la capacité maximale d'un réseau de pipelines, où les stations de pompage sont des nœuds et les tuyaux des arcs avec une capacité limitée.
• Arbre couvrant de poids minimal : Conception d'un réseau de communication (par exemple, la pose de câbles à fibres optiques) pour relier plusieurs villes avec une longueur totale de câble minimale.
• Chemin critique : Dans un projet de construction de maison, où les tâches (fondations, construction des murs, installation du toit) ont une durée et des dépendances technologiques données, le chemin critique détermine le délai minimal d'achèvement de la construction. Tout retard d'une tâche sur ce chemin entraînera un retard de l'ensemble du projet.

Voir aussi

• Recherche opérationnelle
• Théorie des graphes
• Problème de transport
• Méthode du chemin critique
• PERT