Td corrigé Chapitre 2 Réseaux et graphes : vocabulaire et exemples pdf

Chapitre 2 Réseaux et graphes : vocabulaire et exemples

2.2 Sommets, arcs et arêtes : les atomes des graphes et des réseaux 55 .... Une modélisation linéaire du problème de transport classique ? La méthode des ...




part of the document



Méthodes de planification en transport




Avant-propos 1


1 Le monde du transport 8
1.1 Des outils qui révolutionnent le monde du transport 9
La palettisation ( La conteneurisation ( Le GPS et ses prédécesseurs ( Le routage des navires
1.2 Quelques anecdotes de l’histoire des transports 16
Le transport automobile ( Le transport militaire ( Le transport périurbain ( Les transports et les luttes syndicales ( Importance stratégique des équipements publics de transport
1.3 Les modes conventionnels de transport 20
Le camion ( Le transport aérien ( Øresund ( Arabie Saoudite ( Guinée ( Chili
1.4 Modes non conventionnels de transport 30
Rôle des pipelines ( Évacuations urgentes ( Acheminement du courriel ( Réseaux de communication ( Modes de transport chez les insectes, les oiseaux, les poissons….
1.5 Le transport au Québec 35
Les voies du passé et du présent ( Le camionnage au Québec ( Des problèmes à résoudre dans l’industrie du camionnage ( La recherche en transport au Québec ( Le Centre de recherche sur les transports ( Le Groupe d’études et de recherche en analyse des décisions ( Giro ( Technologies Ad Opt Inc. ( INRO
1.6 L’approche pédagogique de ce manuel - la famille Simard 41
La méthode pédagogique retenue ( La famille Simard ( Antoine de Saint-Exupéry ( La notion de réseau ( Caractères communs des réseaux ( L’ordinateur et les problèmes de transport ( L’entreprise de transport innovatrice ( Les graphes
1.7 Exercices 49


2 Réseaux et graphes : vocabulaire et exemples 52
2.1 Les précurseurs 52
2.2 Sommets, arcs et arêtes : les atomes des graphes et des réseaux 55
Graphes orientés ( Graphes et réseaux orientés : un exemple ( Graphes et réseaux non orientés : un exemple ( Arcs ou arêtes ? ( Graphes mixtes ( Boucle
2.3 Les graphes orientés 67
La notion de graphe orienté ( Notations mathématiques et définitions de base ( Prédécesseurs, successeurs et degrés ( Chemins ( Accessibilité ( Composantes connexes et forte connexité ( Calcul des composantes connexes d’un graphe ( Algorithme de calcul des composantes connexes ( Exemple : Circulation de l’information dans une firme ( Graphe des composantes connexes d’un graphe
2.4 Les graphes non orientés 83
Incidence et degrés ( Chaînes et composantes connexes ( Accessibilité ( Composantes connexes et connexité
2.5 Compléments 88
Représentation d’un graphe économe de l’espace en mémoire ( Graphe biparti ( Graphe planaire
2.6 Exercices 91

3 Arbres 101
3.1 Une propriété de base des réseaux non orientés : la connexité 101
La famille Simard : design d’un réseau connexe de coût minimal ( Définitions d’un arbre
3.2 Un algorithme efficace pour trouver un arbre générateur de poids minimal 105
3.3 L’arbre générateur de poids maximal 108
3.4 Arbre de poids minimal dans un réseau cartésien 110
3.5 Compléments 112
La logique gourmande ( Validité de l’algorithme de Kruskal ( Validité de l’algorithme pour déterminer un itinéraire permettant une charge maximale ( Modèle linéaire pour l’arbre de poids minimal
3.6 Exercices 121

4 Le calcul du chemin le plus court dans un réseau 139
4.1 Le CLPC, une donnée essentielle dans le monde du transport 139
4.2 Un algorithme efficace pour le calcul des CLPC : la méthode de Dijkstra 150
Historique du calcul des CLPC ( Présentation de la méthode de Dijkstra ( Deux propriétés des CLPC ( Commentaires concernant le calcul des CLPC
4.3 Méthode de Dijkstra pour un réseau non orienté 162
4.4 Compléments 165
Un modèle mathématique pour le calcul d’un CLPC ( Certificat d’optimalité pour les longueurs des CLPC ( Méthode de correction d’étiquettes pour le calcul des CLPC
4.5 Exercices 175

5 Le flot maximal 190
5.1 Le rééquilibrage des palettes 191
5.2 Terminologie et définition du problème de flot maximal 193
Classification des sommets ( Le problème de flot maximal
5.3 Chemin d’augmentation du flot 195
5.4 Chaîne d’augmentation 201
5.5 La notion de coupe dans un réseau 208
5.6 La pose d’étiquettes pour le calcul du flot maximal 215
5.7 Compléments 219
Le réseau résiduel et la pose d’étiquettes pour le calcul du flot maximal ( Modèle mathématique pour le problème de flot maximal ( Preuve de l’équation (5.3) ( Preuves des théorèmes 5.2 et 5.3 ( Commentaires sur les théorèmes 5.1 et 5.4
5.8 Exercices 225

6 Le problème de flot à coût minimal 238
6.1 Définition du problème 238
6.2 Le calcul d’une solution admissible initiale 241
6.3 Classification des arcs dans une solution admissible 243
6.4 Solution admissible de base 250
6.5 Calcul du coût marginal d’un arc hors base et construction de la solution de base no 1 251
6.6 Description de l’algorithme du simplexe réseau 258
6.7 Algorithme du simplexe réseau : résolution de l’exemple de base 262
Initialisation (Itération 0) ( Itération 1 ( Itération 2 ( Itération 3
6.8 Exemples d’applications de PFCM 268
Le transport à charges partielles ( La localisation des entrepôts ( Les PFCM et le transport aérien
6.9 Compléments 274
Un modèle linéaire d’un PFCM ( Présentation d’un problème multisource et multipuits comme un PFCM ( Présentation d’un problème avec bornes inférieures comme un PFCM ( Solutions de base dégénérées ( Itérations dégénérées
6.10 Exercices 287

7 Le problème de transport classique 303
7.1 Définition du problème 303
7.2 Rééquilibrage des palettes entre divers terminus 305
7.3 Calcul d’une 1re solution admissible : la méthode du coin nord-ouest 306
Une 2e heuristique de calcul d’une solution initiale : la méthode des coûts minimaux 310
Vérification de l’optimalité d’une solution 312
L’algorithme du transport 321
Compléments 324
Une modélisation linéaire du problème de transport classique ( La méthode des pénalités ( Le phénomène de la dégénérescence ( PTC non équilibré : cas où la somme des disponibilités est plus élevée ( PTC non équilibré : cas où la somme des demandes est plus élevée
7.8 Exercices 339


8 Le problème d’affectation 353
8.1 Quelques exemples d’application dans le monde du transport 353
Appariements d’allers et de retours ( L’affectation de conducteurs à des cueillettes ( Affectation de conducteurs à des voyages ( Affectation d’équipes à des réparations d’urgence ( Interdire ou forcer des affectations
8.2 La nécessité d’un algorithme efficient 366
8.3 Le principe de base de l’algorithme 368
8.4 La notion de zéros indépendants 369
8.5 Un algorithme pour résoudre les problèmes d’affectation : la méthode hongroise 371
8.6 Un exemple de problème non équilibré avec un objectif de maximisation 377
8.7 Compléments 380
Le modèle linéaire pour le problème d’affectation ( Le principe des réductions-rangées ( Déterminer le nombre maximal de zéros indépendants
8.8 Exercices 386

9 Le problème du postier chinois 397
9.1 La tournée d’un camelot 398
La leçon de Jacques : préliminaires
9.2 La suite de la leçon de Jacques : un appariement optimal des sommets impairs 405
9.3 La séquence de visite des arêtes d’un multigraphe eulérien 411
9.4 Le problème du postier chinois orienté 414
9.5 Compléments 419
Pourquoi un multigraphe non orienté contient-il toujours un nombre pair de sommets impairs? ( Les chaînes de GA d’une tournée optimale ne possèdent aucune arête en commun ( Un modèle linéaire du PCNO ( Le problème du postier chinois mixte
9.6 Exercices 430


10 Le problème du voyageur de commerce 442
10.1 Typologie, historique et applications 442
Définition et exemple euclidien ( Un exemple de PVC non euclidien ( Un exemple de PVC dans un réseau orienté ( Réseau hamiltonien ( Bref historique du PVC  ( Complexité du PVC ( Applications et typologie
10.2 Heuristiques pour un PVC symétrique : principes généraux 455
Mesures de performance d’une heuristique ( Une typologie des heuristiques pour le PVC ( La méthode du sommet le plus proche (SLPP)
10.3 Heuristiques pour un PVC symétrique : construction d’une tournée hamiltonienne initiale 459
Pénalités d’insertion et notion de proximité d’un sommet à une tournée partielle ( La notion de distance d’un sommet non visité à une tournée partielle ( Les méthodes d’insertion
10.4 Heuristiques pour un PVC symétrique : amélioration d’une tournée hamiltonienne 466
La méthode 2-OPT
10.5 Résoudre un PVC asymétrique 472
10.6 Compléments 477
Absence de croisements dans une tournée optimale d’un réseau cartésien ( Le modèle linéaire d’un PVC symétrique : un exemple
10.7 Exercices 481



Bibliographie 495



Table des matières 497