Recherche opérationnelle

en sciences de la gestion

Méthodes et techniques d’aide à la décision

(2

e

impression)

PATRICK LYONNAIS

MARIE-CLAUDE BOLDUC

2016

Recherche opérationnelle en sciences de la gestion : Méthodes et techniques d’aide à la décision

c� 2016 Patrick Lyonnais et Marie-Claude BolducTous droits réservés.

Toute reproduction du présent ouvrage, en totalité ou en partie, par tous les moyens présentement connus ou à être découverts,est interdite sans l’autorisation préalable des deux auteurs.Toute utilisation non expressément autorisée constitue une contrefaçon pouvant donner lieu à une poursuite en justice contrel’individu ou l’établissement qui effectue la reproduction non autorisée.Des marques de commerce sont mentionnées ou illustrées dans cet ouvrage. Les auteurs tiennent à préciser qu’ils n’ont reçuaucun revenu ni avantage conséquemment à la présence de ces marques. Celles-ci sont reproduites à la demande des auteursen vue d’appuyer le propos pédagogique ou scientifique de l’ouvrage.

1 2 3 4 5 6 7 8 9 2016 9 8 7 6 5 4 3 2 1Première édition : Août 2016Dépôt légal – Bibliothèque et Archives nationales du Québec, 3e trimestre 2016

2e impression : Décembre 2016

Lyonnais, Patrick.Recherche opérationnelle en sciences de la gestion : Méthodes et techniques d’aide à la décisionComprend des illustrations, références bibliographiques et index.ISBN 978-2-9815471-1-8Courriel : patly@mac.com

Bolduc, Marie-Claude.Recherche opérationnelle en sciences de la gestion : Méthodes et techniques d’aide à la décisionComprend des illustrations, références bibliographiques et index.ISBN 978-2-9816111-0-9Courriel : mc@mcbolduc.com

ISBN 978-2-9815471-1-8

9 782981 547118

Produit, édité et publié à compte d’auteur à Lévis (Québec)Imprimé au Canada

Table des matières

Liste des figures ix

Liste des tables xi

1 Introduction 11.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Optimisation et recherche opérationnelle . . . . . . . . . . . . . . . . . . . . . . 21.3 Classification des modèles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.4 Prise de décision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4.1 Processus de prise de décision . . . . . . . . . . . . . . . . . . . . . . . . 61.4.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4.3 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Modélisation mathématique générale 92.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Formulation générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1 Composantes de la formulation générale . . . . . . . . . . . . . . . . . . . 102.2.1.1 Bien définir les variables principales . . . . . . . . . . . . . . . 112.2.1.2 Définir la mesure d’efficacité . . . . . . . . . . . . . . . . . . . 112.2.1.3 Modéliser les contraintes . . . . . . . . . . . . . . . . . . . . . 122.2.1.4 Contribution du coefficient technologique à la contrainte . . . . . 14

2.3 L’importance des unités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Formulation de modèles 193.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Un exemple de marketing : le choix de véhicules publicitaires . . . . . . . . . . . 193.3 Un exemple de régime alimentaire . . . . . . . . . . . . . . . . . . . . . . . . . . 213.4 Un exemple en transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.5 Affectation du personnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.6 Un problème de mélange dans l’industrie pétrolière . . . . . . . . . . . . . . . . . 283.7 La composition d’un portefeuille d’investissements . . . . . . . . . . . . . . . . . 303.8 Un exemple de planification de la production . . . . . . . . . . . . . . . . . . . . 313.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4 Programmes linéaires à variables entières et binaires 414.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2 Forme générale d’un programme en nombres entiers . . . . . . . . . . . . . . . . 424.3 Quelques concepts en programmation en nombres entiers et binaires . . . . . . . . 42

4.3.1 Représentation de conditions . . . . . . . . . . . . . . . . . . . . . . . . . 434.3.1.1 Cas 1 : Sélectionner une valeur parmi plusieurs . . . . . . . . . . 44

iii

iv Table des matières

4.3.1.2 Cas 2 : Satisfaire l’une ou l’autre de deux contraintes . . . . . . 454.4 Quelques formulations en nombres entiers . . . . . . . . . . . . . . . . . . . . . . 46

4.4.1 Coût de mise en route : choix d’un emplacement d’usine . . . . . . . . . . 464.4.2 Sélection de projets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.4.3 Le sac alpin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.4.4 Production et distribution pour un produit . . . . . . . . . . . . . . . . . . 50

4.5 Approximation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5 Introduction à la résolution de programmes linéaires 575.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.2 Forme générale d’un programme linéaire . . . . . . . . . . . . . . . . . . . . . . 57

5.2.1 L’hypothèse de linéarité . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.2.2 Quelques définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5.3 Une méthode : Résolution graphique . . . . . . . . . . . . . . . . . . . . . . . . 595.3.1 Quelques remarques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

5.4 Résolution graphique d’un problème de maximisation . . . . . . . . . . . . . . . 605.4.1 Contraintes et région des solutions réalisables . . . . . . . . . . . . . . . . 605.4.2 Détermination des coordonnées des points extrêmes . . . . . . . . . . . . 625.4.3 Calcul de la fonction économique pour chaque point extrême . . . . . . . . 62

5.5 Tracé de la fonction économique . . . . . . . . . . . . . . . . . . . . . . . . . . . 635.5.1 Tracé de la fonction économique de l’exemple . . . . . . . . . . . . . . . 64

5.6 Solutions multiples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645.7 Incompatibilité des contraintes : aucune solution réalisable . . . . . . . . . . . . . 665.8 Pas de solution optimale finie : Z augmente jusqu’à l’infini . . . . . . . . . . . . . 665.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

6 Algorithme du simplexe 736.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736.2 Pour appliquer le simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.2.1 Transformation sous forme standard . . . . . . . . . . . . . . . . . . . . . 746.2.2 Étapes de l’algorithme du simplexe . . . . . . . . . . . . . . . . . . . . . 74

6.3 Tableau du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756.4 Critère d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.4.1 Comment détecter qu’il n’existe aucune solution . . . . . . . . . . . . . . 776.4.2 Quoi faire lorsque le critère d’optimalité n’est pas rencontré . . . . . . . . 77

6.5 Critère d’entrée d’une variable dans le programme . . . . . . . . . . . . . . . . . 776.6 Critère de sortie d’une variable dans le programme . . . . . . . . . . . . . . . . . 786.7 Pivoter le simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786.8 Exemple de résolution avec le simplexe . . . . . . . . . . . . . . . . . . . . . . . 796.9 Autres situations traitées avec le simplexe . . . . . . . . . . . . . . . . . . . . . . 84

6.9.1 Solutions multiples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 846.9.2 Pas de solution au modèle . . . . . . . . . . . . . . . . . . . . . . . . . . 866.9.3 Solution non bornée : pas de solution optimale finie . . . . . . . . . . . . . 896.9.4 Solution dégénérée (programme de base dégénéré) . . . . . . . . . . . . . 92

6.10 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

7 Analyse de sensibilité 1017.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1017.2 Modèle utilisé pour la démonstration . . . . . . . . . . . . . . . . . . . . . . . . 1017.3 Modification des ressources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

Table des matières v

7.3.1 Détermination des nouvelles quantités . . . . . . . . . . . . . . . . . . . . 1037.3.2 Limites de variation des bi . . . . . . . . . . . . . . . . . . . . . . . . . . 104

7.3.2.1 Limites de variation à l’optimum pour le département de coupe . 1047.3.2.2 Limites de variation à l’optimum pour le département d’assem-

blage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1067.3.2.3 Limites de variation à l’optimum pour l’empaquetage . . . . . . 107

7.3.3 Limites de variation d’une ressource sous contrainte de type � . . . . . . . 1097.3.4 Valeur marginale d’une ressource bi . . . . . . . . . . . . . . . . . . . . . 109

7.3.4.1 Résumé pour l’exemple . . . . . . . . . . . . . . . . . . . . . . 1097.3.5 Et si la variation sur la ressource ne se situe pas dans l’intervalle ? . . . . . 110

7.4 Modification des coefficients économiques . . . . . . . . . . . . . . . . . . . . . 1117.4.1 Modification des coefficients économiques des variables de décision hors

base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1117.4.2 Modification des coefficients économiques des variables de décision dans la

base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1127.4.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1127.4.4 Quelques remarques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1137.4.5 Que signifie la notion de coût réduit ? . . . . . . . . . . . . . . . . . . . . 114

7.4.5.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1147.5 Ajout d’une nouvelle variable principale . . . . . . . . . . . . . . . . . . . . . . . 1157.6 Ajout d’une nouvelle contrainte . . . . . . . . . . . . . . . . . . . . . . . . . . . 1167.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

8 Algorithmes de réseaux 1238.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1238.2 Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

8.2.1 Composition d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . 1238.2.2 Arc orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1248.2.3 Réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1248.2.4 Chaîne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1248.2.5 Chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1258.2.6 Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1258.2.7 Graphe connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1258.2.8 Graphe orienté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1258.2.9 Source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1258.2.10 Destination ou réservoir . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

8.3 Problème de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1268.3.1 Modélisation mathématique . . . . . . . . . . . . . . . . . . . . . . . . . 1268.3.2 Caractéristiques du problèmes de transport . . . . . . . . . . . . . . . . . 1288.3.3 Algorithme du transport . . . . . . . . . . . . . . . . . . . . . . . . . . . 1288.3.4 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

8.3.4.1 Méthode du coin nord-ouest . . . . . . . . . . . . . . . . . . . . 1318.3.4.2 Suite de l’exemple . . . . . . . . . . . . . . . . . . . . . . . . . 1328.3.4.3 Méthode des coûts duaux pour améliorer une solution . . . . . . 136

8.3.5 Cas particuliers du problème de transport . . . . . . . . . . . . . . . . . . 1418.4 Le problème d’affectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

8.4.1 Modélisation mathématique . . . . . . . . . . . . . . . . . . . . . . . . . 1428.4.2 Algorithme pour résoudre le problème d’affectation : la méthode hongroise 142

8.4.2.1 Les étapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1438.4.2.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1448.4.2.3 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

vi Table des matières

8.4.3 Modifications possibles au problème d’affectation . . . . . . . . . . . . . 1478.5 Le problème de flot maximum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

8.5.1 Algorithme de flot maximum . . . . . . . . . . . . . . . . . . . . . . . . . 1498.5.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

8.6 Le chemin le plus court . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1518.6.1 Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1518.6.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1538.6.3 Même exemple, mais origine différente . . . . . . . . . . . . . . . . . . . 159

8.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

9 Arbres de décision 1679.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1679.2 Composition d’un arbre de décision . . . . . . . . . . . . . . . . . . . . . . . . . 167

9.2.1 Insertion des options dans l’arbre de décision . . . . . . . . . . . . . . . . 1679.2.2 Lecture d’un arbre de décision . . . . . . . . . . . . . . . . . . . . . . . . 1699.2.3 Écriture d’un arbre de décision . . . . . . . . . . . . . . . . . . . . . . . . 1699.2.4 Forme de l’arbre de décision . . . . . . . . . . . . . . . . . . . . . . . . . 169

9.3 Prise de décision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1719.3.1 Prise de décision avec coût intermédiaire . . . . . . . . . . . . . . . . . . 171

9.4 Équivalent-certain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1739.4.1 Critère de profit maximax (critère optimiste) . . . . . . . . . . . . . . . . 1749.4.2 Critère de profit maximin (critère pessimiste) . . . . . . . . . . . . . . . . 1749.4.3 Critère de regret minimax . . . . . . . . . . . . . . . . . . . . . . . . . . 1759.4.4 Une méthode versus une autre . . . . . . . . . . . . . . . . . . . . . . . . 176

9.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

10 Techniques de l’optimisation 18110.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18110.2 Recherche d’un optimum sans contrainte . . . . . . . . . . . . . . . . . . . . . . 182

10.2.1 Et si f0(x⇤) = 0 et f00(x⇤) = 0 ? . . . . . . . . . . . . . . . . . . . . . . . . 18210.2.2 Minimum ou maximum absolu ou local . . . . . . . . . . . . . . . . . . . 183

10.2.2.1 Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18410.2.2.2 Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

10.3 Plusieurs variables dans la fonction à optimiser . . . . . . . . . . . . . . . . . . . 18510.3.1 Conditions d’atteinte d’un optimum . . . . . . . . . . . . . . . . . . . . . 186

10.3.1.1 Maximum local . . . . . . . . . . . . . . . . . . . . . . . . . . 18610.3.1.2 Minimum local . . . . . . . . . . . . . . . . . . . . . . . . . . 18710.3.1.3 Col . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18710.3.1.4 Incapacité à conclure . . . . . . . . . . . . . . . . . . . . . . . 187

10.3.2 Le déterminant de la matrice des dérivées partielles secondes . . . . . . . . 18710.3.3 Exemple 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

10.4 Recherche d’un optimum avec contrainte d’égalité . . . . . . . . . . . . . . . . . 18910.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19010.6 Rappel sur la dérivée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

10.6.1 Formules de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19210.6.2 Dérivée seconde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19310.6.3 Dérivée partielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19310.6.4 Dérivée partielle seconde croisée . . . . . . . . . . . . . . . . . . . . . . . 194

11 Méthodes multicritères élémentaires 19511.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

Table des matières vii

11.2 Méthode par pondération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19611.2.1 Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

11.3 ELECTRE-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19711.3.1 Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

11.4 Analyse du point mort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20211.4.1 Exemple 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

11.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

12 Décision de groupe 20712.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20712.2 Le processus d’analyse hiérarchique . . . . . . . . . . . . . . . . . . . . . . . . . 207

12.2.1 Hiérarchie de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20812.2.2 Fonctionnement de l’AHP . . . . . . . . . . . . . . . . . . . . . . . . . . 209

12.2.2.1 Comparaison par paire . . . . . . . . . . . . . . . . . . . . . . . 20912.2.2.2 Matrice de comparaisons par paire . . . . . . . . . . . . . . . . 21012.2.2.3 Obtention d’un ordre de priorité pour les comparaisons par paire 21112.2.2.4 Cohérence des résultats . . . . . . . . . . . . . . . . . . . . . . 21212.2.2.5 Autres comparaisons par paire pour les alternatives de chacun des

critères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21412.2.2.6 Décision finale . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

12.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

13 Simulation 21913.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21913.2 Qu’est-ce qu’une simulation ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21913.3 Pourquoi simuler ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22013.4 Aborder la simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22013.5 Différents types de simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

13.5.1 Simulation par événements discrets . . . . . . . . . . . . . . . . . . . . . 22113.5.2 Simulation dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22313.5.3 Simulation déterministe ou stochastique ? . . . . . . . . . . . . . . . . . . 227

13.6 Les nombres aléatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22713.7 Les grandes étapes d’une intervention avec la simulation . . . . . . . . . . . . . . 22813.8 Quelques outils informatiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22913.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

Bibliographie 231

Index 233

Liste des figures

1.1 Classification générale des modèles . . . . . . . . . . . . . . . . . . . . . . . . . 3

3.1 Représentation du réseau de distribution de l’exemple en transport . . . . . . . . . 25

4.1 Modèle de production-distribution à un produit . . . . . . . . . . . . . . . . . . . 50

5.1 Contraintes et ensemble des solutions réalisables de l’exemple : (a) Tracé de lacontrainte (1) ; (b) Tracé de la contrainte (2) ; (c) Tracé de la contrainte (3) ; (d)Ensemble des solutions réalisables ; et (e) Les points extrêmes . . . . . . . . . . . 61

5.2 Tracé de la fonction économique de l’exemple : (a) Première droite ; (b) Troisièmedroite ; (c) Plusieurs autres droites et Z augmente ; et (d) Droite touchant le point 4 65

5.3 Représentation graphique du programme linéaire avec solutions multiples . . . . . 655.4 Aucune solution réalisable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665.5 Pas de solution optimale finie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

6.1 Représentation graphique du programme linéaire avec solutions multiples . . . . . 856.2 Aucune solution réalisable au problème . . . . . . . . . . . . . . . . . . . . . . . 876.3 Pas de solution optimale finie au problème . . . . . . . . . . . . . . . . . . . . . . 906.4 Solution graphique du problème dégénéré . . . . . . . . . . . . . . . . . . . . . . 93

8.1 Représentation générale du problème de transport . . . . . . . . . . . . . . . . . . 1278.2 Matrice de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1298.3 Exemple de flot maximum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1488.4 Exemple de flot maximum : État initial du réseau . . . . . . . . . . . . . . . . . . 1498.5 Exemple de flot maximum : État du réseau après une entrée de valeur 4 sur le chemin

1 ! 2 ! 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1508.6 Exemple de flot maximum : État du réseau après une entrée de valeur 5 sur le chemin

1 ! 3 ! 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1508.7 Exemple de flot maximum : État optimal . . . . . . . . . . . . . . . . . . . . . . . 1518.8 Réseau de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1538.9 Réseau de base, modifié pour fins de représentation . . . . . . . . . . . . . . . . . 1538.10 Initialisation : départ depuis A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1548.11 Les arcs depuis A : {G,U,T} deviennent temporaires. . . . . . . . . . . . . . . . . 1548.12 G devient permanent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1548.13 Les arcs depuis G : S devient temporaire. . . . . . . . . . . . . . . . . . . . . . . 1548.14 U devient permanent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1558.15 Les arcs depuis U : L devient temporaire. . . . . . . . . . . . . . . . . . . . . . . 1558.16 T devient permanent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1568.17 Les arcs depuis T : L est modifié. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1568.18 L devient permanent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1568.19 S devient permanent. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1568.20 À rebours A ! G ! S = 35km . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

ix

x Liste des figures

8.21 À rebours A ! T ! L = 26km . . . . . . . . . . . . . . . . . . . . . . . . . . . 1588.22 À rebours A ! T = 13km . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1588.23 À rebours A ! U = 12km . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1588.24 À rebours A ! G = 11km . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

9.1 Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1689.2 Exemple 1 modifié . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1689.3 Exemple 1 modifié avec des probabilités . . . . . . . . . . . . . . . . . . . . . . . 1709.4 Arbre de décision pour l’achat d’une automobile . . . . . . . . . . . . . . . . . . . 1729.5 Arbre de décision pour l’exemple Équivalent-certain . . . . . . . . . . . . . . . . 1739.6 Arbre de décision de l’Exercice 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 1779.7 Exercice 5 : Revenus générés par des habitations . . . . . . . . . . . . . . . . . . 1799.8 Exercice 6 : Coûts pour des vacances . . . . . . . . . . . . . . . . . . . . . . . . . 179

10.1 Exemple d’un col . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18310.2 Exemple de maximum absolu d’une fonction . . . . . . . . . . . . . . . . . . . . 18310.3 Maximum et minimum locaux d’une fonction . . . . . . . . . . . . . . . . . . . . 18410.4 Maximum de la fonction de l’Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . 18510.5 Maximum et minimum locaux de l’Exemple 2 . . . . . . . . . . . . . . . . . . . . 186

11.1 Les fonctions de coût total de l’Exemple 3 . . . . . . . . . . . . . . . . . . . . . . 20411.2 Les intersections d’intérêt de l’Exemple 3 . . . . . . . . . . . . . . . . . . . . . . 20511.3 Les zones favorisées de l’Exemple 3 . . . . . . . . . . . . . . . . . . . . . . . . . 205

12.1 Hiérarchie du problème de choix d’un vélo de route performance . . . . . . . . . . 208

13.1 Simulation d’un réseau de distribution avec AnyLogic . . . . . . . . . . . . . . . . 22213.2 Simulation des opérations d’un entrepôt avec AnyLogic : (a) Vue 2D ; et (b) Vue 3D 22313.3 Représentation d’un modèle de simulation dynamique avec Stella . . . . . . . . . 22413.4 Simulation dynamique d’un calcul financier avec Stella . . . . . . . . . . . . . . . 22413.5 Simulation déterministe d’un calcul financier avec Stella . . . . . . . . . . . . . . 22513.6 Simulation d’une règle de lotissement avec Stella . . . . . . . . . . . . . . . . . . 22513.7 Simulation d’un réseau de distribution avec Stella . . . . . . . . . . . . . . . . . . 22613.8 Simulation d’une usine et ses résultats financiers avec Stella . . . . . . . . . . . . 226

Liste des tables

1.1 Classification des modèles analytiques et de simulation . . . . . . . . . . . . . . . 41.2 Caractéristiques des différents niveaux de prise de décision . . . . . . . . . . . . . 5

3.1 Données : Choix de véhicules publicitaires . . . . . . . . . . . . . . . . . . . . . . 203.2 Données : Exemple de régime alimentaire . . . . . . . . . . . . . . . . . . . . . . 223.3 Données : Coûts de transport d’un moteur, en $/unité . . . . . . . . . . . . . . . . 243.5 Données : Affectation du personnel . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.1 Les coordonnées des points extrêmes . . . . . . . . . . . . . . . . . . . . . . . . . 625.2 Valeur de Z aux différents points extrêmes . . . . . . . . . . . . . . . . . . . . . . 63

8.1 Les chemins de l’exemple. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1578.2 Les chemins avec Lévis (Desjardins) comme origine. . . . . . . . . . . . . . . . . 159

11.1 Les critères et poids de l’Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . 19611.2 Les évaluations de l’Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19711.3 Les évaluations de l’Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19911.4 Matrice de concordance de l’Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . 20011.5 Matrice de discordance de l’Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . 20111.6 Matrice de surclassement de l’Exemple 2 . . . . . . . . . . . . . . . . . . . . . . 20111.7 Données de l’Exemple 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20311.8 Exemple 3 : Coût total lorsque la demande vaut 10 000 unités . . . . . . . . . . . . 20311.9 Exemple 3 : Coût total lorsque la demande vaut 15 000 unités . . . . . . . . . . . . 203

12.1 Types de vélo de route performance . . . . . . . . . . . . . . . . . . . . . . . . . 20812.2 Échelle d’importance d’une comparaison . . . . . . . . . . . . . . . . . . . . . . 20912.3 Comparaisons par paire des critères d’un choix de vélo de route performance . . . 21012.4 Valeurs de RI en fonction du nombre de critères n . . . . . . . . . . . . . . . . . . 21312.5 Comparaison par paire des alternatives pour chacun des critères . . . . . . . . . . 21412.6 Ordres de priorité de chacune des alternatives pour chacun des critères . . . . . . . 21412.7 Ordre de priorité globale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216

xi