Outils d'optimisation pour la logistique
théorie et pratique
Jean-Michel Réveillac
iSTE
Préface15
Pascal Mauny
Avant-propos19
Introduction23
Chapitre 1. La recherche opérationnelle29
1.1. Historique29
1.2. Champs d'application, principes et concepts30
1.2.1. L'identification30
1.2.2. La modélisation31
1.2.3. La résolution33
1.2.4. La validation34
1.2.5. La mise en oeuvre34
1.2.6. L'amélioration35
1.3. Les modèles de base35
1.4. Avenir de la RO35
Chapitre 2. Bases de la théorie des graphes37
2.1. Graphe et représentation37
2.2. Graphe non orienté38
2.2.1. Multigraphe38
2.2.2. Graphes planaire et non planaire39
2.2.3. Graphes connexe et non connexe39
2.2.4. Graphe complet39
2.2.5. Graphe biparti40
2.2.6. Graphe partiel, sous-graphe, clique et stable40
2.2.7. Degré d'un sommet et d'un graphe41
2.2.8. Chaîne et cycle dans un graphe42
2.2.9. Indicateur de connectivité43
2.2.10. Graphe eulérien44
2.2.11. Graphe hamiltonien44
2.2.12. Graphe planaire45
2.2.13. Isthme46
2.2.14. Arbre et forêt47
2.2.15. Arborescence48
2.2.16. Arborescence ordonnée49
2.3. Graphe orienté ou digraphe50
2.3.1. Chemin et circuit dans un digraphe50
2.3.2. Absence de circuit dans un digraphe51
2.3.3. Matrice d'adjacence52
2.3.4. Matrice d'un graphe valué53
2.4. Graphes pour la logistique54
Chapitre 3. Les chemins optimaux55
3.1. Concepts de base55
3.2. L'algorithme de Dijkstra56
3.2.1. Calculs des chemins minimaux sur un exemple56
3.2.2. Interprétation du résultat des calculs58
3.3. L'algorithme de Flyod-Warshall58
3.3.1. Création des matrices de départ (initialisation de l'algorithme)58
3.3.2. Remplissage des matrices pour les itérations suivantes59
3.3.3. Exemple de calcul des chemins minimaux59
3.3.4. Interprétation des résultats62
3.4. L'algorithme de Bellman-Ford63
3.4.1. Initialisation63
3.4.2. Itérations suivantes avec relâchement64
3.4.3. Exemple de calcul64
3.4.4. Interprétation des résultats67
3.5. L'algorithme de Bellman-Ford avec un circuit négatif67
3.5.1. Exemple67
3.6. Exercices70
3.6.1. Exercice 1 : optimisation d'un temps de parcours70
3.6.2. Exercice 2 : un graphe orienté avec arc de coût négatif71
3.6.3. Exercice 3 : routage de paquets de données72
3.6.4. Solution de l'exercice 172
3.6.5. Solution de l'exercice 273
3.6.6. Solution de l'exercice 374
Chapitre 4. Programmation dynamique77
4.1. Principes de la programmation dynamique77
4.2. Formulation du problème78
4.2.1. Exemple 1 - La pyramide de nombres78
4.2.2. Exemple 2 - La suite de Fibonacci80
4.2.3. Exemple 3 - Le sac à dos82
4.3. Processus stochastique85
4.4. Les chaînes de Markov85
4.4.1. Propriétés des chaînes de Markov86
4.4.2. Classes et états d'une chaîne87
4.4.3. Matrice et graphe89
4.4.4. Application des chaînes de Markov90
4.5. Exercices92
4.5.1. Exercice 1 : la distance de Levenshtein92
4.5.2. Exercice 292
4.5.3. Exercice 3 : le modèle d'Ehrenfest93
4.5.4. Solutions de l'exercice 193
4.5.5. Solutions de l'exercice 294
4.5.6. Solutions de l'exercice 396
Chapitre 5. Ordonnancement avec PERT et MPM97
5.1. Concepts principaux97
5.2. Méthode du chemin critique98
5.3. Diagramme de précédence98
5.4. Planification d'un projet avec PERT/CPM101
5.4.1. Historique101
5.4.2. Méthodologie102
5.5. Exemple de détermination d'un chemin critique avec PERT111
5.5.1. A partir du scénario, création du tableau d'antécédents112
5.5.2. Création du graphe112
5.5.3. Numérotation des sommets113
5.5.4. Détarmination des dates au plus tôt de chacune des tâches114
5.5.5. Détermination des dates au plus tard de chacune des tâches115
5.5.6. Détermination du ou des chemins critiques117
5.6. Les marges118
5.6.1. Marge totale118
5.6.2. Marge libre118
5.6.3. Marge certaine119
5.6.4. Propriétés119
5.7. Exemple de calcul de marges119
5.8. Détermination du chemin critique à l'aide d'un tableau à double entrée121
5.8.1. Création d'un tableau à partir de notre exemple121
5.8.2. Remplissage du tableau122
5.8.3. Dates de début au plus tôt122
5.8.4. Dates de fin au plus tard124
5.8.5. Chemin critique125
5.9. Méthodologie de planification avec MPM126
5.9.1. Historique126
5.9.2. Formalisme du graphe127
5.9.3. Règles de construction128
5.9.4. Dates au plus tôt et au plus tard129
5.9.5. Détermination du chemin critique130
5.10. Exemple de détermination d'un chemin critique avec MPM130
5.10.1. Création du graphe131
5.10.2. Détermination des dates au plus tôt de chacune des tâches131
5.10.3. Détermination des dates au plus tard de chacune des tâches132
5.10.4. Détermination du ou des chemins critiques133
5.10.5. Marges134
5.11. PERT/CPM/MPM probabilisé135
5.11.1. Probabilité des tâches136
5.11.2. Mise en oeuvre sur un exemple137
5.11.3. Cacul des durées moyennes et de la variance138
5.11.4. Calcul de la durée moyenne du projet138
5.11.5. Calcul de la probabilité de terminer le projet suivant une durée choisie138
5.11.6. Calcul de la durée du projet pour une probabilité donnée139
5.12. Diagramme de Gantt139
5.12.1. Création du diagramme140
5.12.2. Exemple140
5.13. Coût PERT-MPM143
5.13.1. Méthode144
5.13.2. Exemple144
5.14. Exercices149
5.14.1. Exercice 1149
5.14.2. Exercice 2149
5.14.3. Exercice 3150
5.14.4. Exercice 4151
5.14.5. Solution Exercice 1152
5.14.6. Solution Exercice 2153
5.14.7. Solution Exercice 3154
5.14.8. Solution Exercice 4156
Chapitre 6. Flot maximal dans un réseau159
6.1. Flot maximal159
6.2. Algorithme de Ford-Fulkerson161
6.2.1. Présentation de l'algorithme162
6.2.2. Application sur un exemple163
6.3. Théorème de la coupe minimale169
6.3.1. Exemple de coupes170
6.4. Algorithme de Dinic170
6.4.1. Présentation de l'algorithme171
6.4.2. Application sur un exemple172
6.5. Exercices176
6.5.1. Exercice 1 : approvisionnement en eau potable176
6.5.2. Exercice 2 : flot maximal selon Dinic177
6.5.3. Solution de l'exercice 1177
6.5.4. Solution de l'exercice 2180
Chapitre 7. Arbres, tournées et transport185
7.1. Les concepts de base185
7.2. L'algorithme de Kruskal187
7.2.1. Application sur un exemple188
7.3. L'algorithme de Prim190
7.3.1. Application sur un exemple191
7.4. L'algorithme de Sollin195
7.4.1. Application sur un exemple196
7.5. L'algorithme de Little pour la résolution du PVC201
7.5.1. Application sur un exemple202
7.6. Exercices213
7.6.1. Exercice 1 : réseau informatique213
7.6.2. Exercice 2 : livraisons214
7.6.3. Solution de l'exercice 1215
7.6.4. Solution de l'exercice 2217
Chapitre 8. La programmation linéaire223
8.1. Concepts de base223
8.1.1. Formulation d'un programme linéaire224
8.2. Méthode de résolution graphique224
8.2.1. Identification225
8.2.2. Formalisation225
8.2.3. Résolution230
8.3. Méthode du simplexe233
8.3.1. Démarche233
8.3.2. L'exemple à traiter233
8.3.3. Formalisation234
8.3.4. Passage en forme standard235
8.3.5. Création du tableau235
8.3.6. Détermination du pivot236
8.3.7. Itérations237
8.3.8. Interprétation240
8.4. Dualité240
8.4.1. Formulation duale241
8.4.2. Passage du primal au dual, formalisation242
8.4.3. Détermination du pivot243
8.4.4. Itérations244
8.4.5. Interprétation245
8.5. Exercices245
8.5.1. Exercice 1 : vidéo et festival245
8.5.2. Exercice 2 : simplexe246
8.5.3. Exercice 3 : primal et dual246
8.5.4. Solution de l'exercice 1247
8.5.5. Solution de l'exercice 2249
8.5.6. Solution de l'exercice 3250
Chapitre 9. Les logiciels253
9.1. Des logiciels pour la RO et la logistique253
9.2. Les tableurs254
9.2.1. Fonctions avancées avec Microsoft Excel256
9.2.2. Tableaux croisés dynamiques259
9.2.3. Solveur260
9.2.4. Visual Basic Application261
9.3. Les gestionnaires de projets271
9.3.1. La démarche de création d'un projet272
9.4. Les simulateurs de flux274
9.4.1. La création d'un processus de simulation275
Chapitre 10. Recherche opérationnelle avec un tableur277
10.1. Avertissement277
10.2. Programmation dynamique277
10.3. Ordonnancement282
10.3.1. Matrice de calcul d'un chemin critique283
10.3.2. Diagramme de Gantt classique286
10.3.3. Diagramme de Gantt avec Calendrier294
10.4. Flots maximaux301
10.5. Modèle de transport307
10.5.1. Livraison client307
10.5.2. Transport à coût minimum311
10.6. Programmation linéaire314
10.6.1. Création du tableau de calculs314
10.6.2. Saisie des données315
10.6.3. Mise oeuvre en du solveur316
Chapitre 11. Tableaux de bord, tableur et TCD319
11.1. Le tableur, un outil polyvalent319
11.2. La base de données exemple320
11.2.1. Champ calculé et mise en forme321
11.2.2. Tranche calendaire, classement et moyenne325
11.2.3. Champs calculés conditionnels327
11.2.4. Segment, filtrage et champ calculé330
11.2.5. Eléments calculés335
11.3. Bases de données multiples338
11.3.1. Nouvelles tables pour la base339
11.3.2. Création des tableaux de données341
11.3.3. Relation entre tableaux342
11.3.4. Tableau croisé dynamique multitables344
11.4. Limites et contraintes liées aux champs calculés346
11.5 Conclusion348
Chapitre 12. Ordonnancement et planification avec un gestionnaire de projet349
12.1. Rappels et informations349
12.2. L'exemple : conception et fabrication d'une machine-outil350
12.2.1. Mise en situation350
12.2.2. Création et paramétrage du projet352
12.2.3. Saisie des tâches et des durées355
12.2.4. Saisie des antécédents (prédécesseurs)356
12.2.5. Visualisation du réseau MPM357
12.2.6. Calcul des marges358
12.2.7. Saisie des ressources360
12.2.8. Affectation des ressources361
12.2.9. Solutionner les sur-utilisations363
12.2.10. Visualiser le projet sous forme chronologique368
12.2.11. Utiliser une codification WBS369
12.2.12. Générer des tableaux de bord et des rapports370
12.3. Le suivi de projet374
12.4. Conclusion375
Chapitre 13. Simulation de flux informatisés377
13.1. Pour commencer377
13.2. L'exemple à traiter378
13.2.1. Plan de la station378
13.2.2. Enoncé et cahier des charges du problème379
13.3. Saisie du projet dans le logiciel ExtendSim 9381
13.3.1. Définition des paramètres principaux381
13.3.2. Dessin du modèle et saisie des contraintes383
13.3.3. Définition des flux397
13.3.4. Lancement de la simulation398
13.3.5. Création et affectation des ressources399
13.3.6. Relance de la simulation403
13.3.7. Création, génération d'un rapport et analyse403
13.3.8. Mise au point, enrichissement et amélioration406
13.3.9. Hiérarchisation413
13.3.10. Habillage415
13.4. Conclusion420
Conclusion421
Annexe 1. Installation du solveur425
Annexe 2. Table de la loi normale centrée réduite433
Glossaire435
Bibliographie441
Index447