GME Diapositives .pdf

Matériel reproductible
NOP 1.1
NOP 1.1
NOP 1.1
NOP 1.1
NOP 1.3
NOP 2.1.1
NOP 2.1.1
NOP 2.1.5
NOP 2.1.5
NOP 2.1.5
NOP 2.1.5
NOP 2.1.6
NOP 2.1.6
NOP 2.1.7
NOP 2.1.7
NOP 2.1.7
NOP 2.1.7
NOP 2.1.8
NOP 2.1.8
NOP 2.1.9
NOP 2.1.9
NOP 2.2.1
NOP 2.2.1
NOP 2.2.2
NOP 2.2.2
NOP 2.2.3
NOP 2.2.3
NOP 2.3.3
NOP 2.4.1
NOP 2.4.1
NOP 3.1.1
NOP 3.1.2
NOP 3.1.2
NOP 3.1.4
NOP 4.2
NOP 4.2
NOP 4.3
NOP 4.3
NOP 4.3
NOP 4.4
NOP 4.4
NOP 4.4
NOP 4.4
NOP 4.5
NOP 4.5
NOP 4.5
NOP 4.5
NOP 4.5
NOP 4.5
NOP 5.6
NOP 5.6
NOP 5.7
NOP 5.7
NOP 5.7

Maude : trajet de distance minimale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Maude : trajet de durée minimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Maude : subdivision en secteurs d’un territoire postal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Maude : tournée du facteur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Méthode scientifique et RO : représentation schématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Les chaises de M. Eugène : description du contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Les chaises sans cuisson : le modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un problème de mélange : description du contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un problème de mélange : schéma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un problème de mélange : le modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un problème de mélange : une solution optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Vitrex : description du contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Vitrex : une solution optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Horaire des standardistes, 1re version : données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Horaire des standardistes, 1re version : le modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Horaire des standardistes, 3e version . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Horaire des standardistes, 3e version : le modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Bobines-mères : commandes et plans de coupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Bobines-mères : le modèle linéaire et quelques solutions optimales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Pastissimo : données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Pastissimo : une solution optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Franchises : division de la région en secteurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Franchises : le modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Rotation du personnel : données. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Rotation du personnel : le modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chemin le plus court : le réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chemin le plus court : le modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Les chaises et leur cuisson : le modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Parcours des éboueurs : plan du quartier et circuits optimaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Parcours des éboueurs : durée des passages sur les tronçons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
FRB : description du contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
FRB : les contraintes technologiques et la région admissible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
FRB : le modèle linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
FRB : repérage graphique de la solution optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Intersections des droites associées aux contraintes de (FRB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Coordonnées des intersections des droites associées aux contraintes de (FRB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Organigramme de l’algorithme du simplexe dans le cas (PLS). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tableau du simplexe : gabarit pour (FRB) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Modèle (FRB) : séquence des tableaux du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Région admissible de (PMF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Le modèle (PMF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tableau du simplexe : gabarit pour (PMF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Modèle (PMF) : séquence des tableaux du simplexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(PMult) : le modèle linéaire et la région admissible. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(PMult) : un tableau optimal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un modèle (P) sans solution admissible : dernier tableau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un modèle non borné . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(PDég) : le modèle linéaire et la région admissible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemple (PDég) : séquence des tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Expro : le modèle et les données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Expro : le tableau optimal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Kalinine : description du contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Kalinine : le modèle linéaire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Kalinine : un tableau final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

1

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

NOP 5.8
NOP 5.8
NOP 6.2
NOP 6.2
NOP 6.3.2
NOP 6.3.2
NOP 6.3.2
NOP 6.3.3
NOP 6.3.4
NOP 6.3.5
NOP 6.3.5
NOP 6.3.6
NOP 6.4
NOP 7.1.1
NOP 7.1.2
NOP 7.1.2
NOP 7.1.4
NOP 7.1.5
NOP 7.2.1
NOP 7.2.1
NOP 7.2.1
NOP 7.2.3
NOP 7.2.3
NOP 7.2.3
NOP 7.2.3
NOP 7.2.3
NOP 7.2.3
NOP 7.2.4
NOP 7.2.4
NOP 7.2.4
NOP 7.2.4
NOP 7.2.5
NOP 7.2.5
NOP 7.2.5
NOP 7.2.5
NOP 7.3.1
NOP 7.4
NOP 7.4
NOP 7.4
NOP 7.5.1
NOP 7.5.3
NOP 7.5.3
NOP 8.1
NOP 8.2
NOP 8.2
NOP 8.2
NOP 8.3
NOP 8.3
NOP 8.3
NOP 8.4
NOP 8.4
NOP 8.4
NOP 8.4
NOP 8.5
NOP 8.6
NOP 8.6
NOP 8.6
NOP 8.6

CinéFam : variables et modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
CinéFam : tableau optimal et intervalles de variation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemple 1 : résolution graphique des modèles (P0) et (Px1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemple 1 : résolution graphique des modèles (Px2) et (Px1x2). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemple 1 : arbre d’énumération et graphique après la 1re séparation (selon x1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemple 1 : arbre d’énumération et graphique après la 2e séparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemple 1 : arbre d’énumération et graphique après la 3e séparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemple 1 : arbre d’énumération et graphique après la 1re séparation (selon x2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Plan de production d’appareils électroniques : description du contexte, modèle et solutions optimales . . . . . . . . . . . . . . . .
Exemple 4 : arbres d’énumération après 2 et 4 séparations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemple 4 : arbre d’énumération complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Exemple 4 : arbre selon le critère du meilleur cj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tableau initial de la phase I et tableau final de la phase II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nitrobec : description du contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nitrobec : réseau sommaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nitrobec : le réseau et une solution optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nitrobec : le modèle linéaire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nitrobec : le chiffrier STORM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nitrobec : modifications apportées au contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nitrobec modifié : le réseau et une solution optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nitrobec modifié : le chiffrier STORM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Problème des toques : le réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Problème des toques : description d’une solution optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Pastissimo : le réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Meerrettich : données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Meerrettich : le réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Meerrettich : une solution optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Problème de la société Air Taxi : description du contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Problème de la société Air Taxi : portions du réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Problème de la société Air Taxi : le réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Problème de la société Air Taxi : le chiffrier STORM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nevera Nieve : le secteur confié à Roger T. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nevera Nieve : le réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nevera Nieve : le chiffrier STORM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Nevera Nieve : une solution optimale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Problème du CNRS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Sporcau : description du contexte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Sporcau : le réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Sporcau : le tableau de transport. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Xanada : le réseau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Provi : le réseau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Provi : une solution optimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Projet RESO : description des tâches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un projet abstrait : description des tâches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un projet abstrait : le réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Projet RESO : le réseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Projet RESO : le chiffrier STORM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Projet RESO : sortie graphique de STORM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Projet RESO : sortie numérique de STORM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Émission d’actions : description des tâches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Émission d’actions : réseau et moments au plus tôt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un projet abstrait : coûts d’accélération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un projet abstrait : le modèle linéaire pour l’accélération des tâches à coût minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un projet abstrait, version PERT : durée des tâches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Projet abstrait et réseau potentiels-tâches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Projet abstrait et réseau potentiels-tâches : moments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Contraintes des modèles linéaires avec et sans accélération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Le réseau potentiels-tâches du projet RESO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

2

57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

NOP 1.1 Maude : trajet de distance minimale
FIGURE 1.1

A

Maude
C

U

Mont Royal

B

GeoRoute 5 - redr01 01/06/2001 16:56

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

3

- END -

Page 1/1

NOP 1.1 Maude : trajet de durée minimale
FIGURE 1.2

GIRO Inc.

Network Map Graphic Report

Effective:

01/06/2001

A
Maude

C

U

B

Mont Royal

- END -

GeoRoute 5 - redr01 01/06/2001 16:38

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

4

Page 1/1

NOP 1.1 Maude : subdivision en secteurs d’un territoire postal
FIGURE 1.3

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

5

NOP 1.1

Maude : tournée du facteur

FIGURE 1.4

Laliberté

av. Alfr

ed

1N6

rue Alex

1N7

1Y5

1R7

andre-La

coste

asavan

t

1N2

Étienne-P

2G4

1N1

1M9

av. Jam

es-Mor

rue Suz

or-Côté

rue de Louisbo
urg

ulte

Benjamin S

1R4
rue Dud
emaine
1R5

arent

Laure-Conan

1N3

2G2
2G3

1L5
rue de L
ouisbou
rg
1L6

seph-C

1N4

rue Jo

1N5

1R6

2A3
av. de P
outrinco
urt
2A2

2P3
rue Pasteur

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

6

rice

NOP 1.3

Méthode scientifique et RO : représentation schématique

FIGURE 1.5

1. Détection
d’un
problème

3. Élaboration
d’un modèle

4. Collecte
des données

2. Formulation
du problème

7. Prise de décisions
et implantation
de la solution

6. Validation
du modèle

5. Résolution
du modèle

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

7

NOP 2.1.1

Les chaises de M. Eugène : description du contexte

Produits et demande
Type

Description

Commandes acceptées

Marché potentiel

A
B

en porte-à-faux
Barcelone

42
53

100
100

Résumé des données de fabrication
Durée de fabrication d’une chaise
Opération

A
Porte-à-faux

Brasage
Laquage
Cuisson
Capitonnage

1,5 heure
30 minutes
8 heures
2 heures

Profit par chaise

450 $

B
Barcelone
2
45
6
3

heures
minutes
heures
heures

Nombre
d’heures
disponibles
250
100
140
327

800 $

Note pour les modèles de la section 2.3.3 : Les chaises sont regroupées par lot pour la cuisson. Le four peut
contenir un maximum de 10 chaises en porte-à-faux ou un maximum de 5 chaises Barcelone. La cuisson d’un
lot coûte 100 $.

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

8

NOP 2.1.1

Les chaises sans cuisson : le modèle linéaire
Variables de décision:
xA = nombre de chaises A à fabriquer d’ici 3 semaines
xB = nombre de chaises B à fabriquer d’ici 3 semaines
Objectif :
Max z = 450 xA + 800 xB
Contraintes :
xA ≥ 42

(1)

xB ≥ 53

(2)

xA ≤ 100

(3)

xB ≤ 100

(4)

1,5 xA + 2 xB ≤ 250

(5)

0,5 xA + 0,75 xB ≤ 100

(6)

2 xA + 3 xB ≤ 327

(7)

xA, xB ≥ 0 et entiers

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

9

NOP 2.1.5

Un problème de mélange : description du contexte

Données relatives aux liquides A, B, C et D
A

B

C

D

Disp. (en L)
Achat (en $/L)
Vente (en $/L)

8 000
5,50
6,00

4 250
4,50
5,00

16 000
7,50
8,00

2 000
11,25
11,75

Mélange
E
F
G

≥ 30 %
≥ 25 %
≥ 20 %

≥ 10 %
≤ 20 %
≥ 15 %

40 %
20 %
40 %

≤ 35 %
≥ 10 %

≤ 20 %

Données relatives aux liquides E, F et G

Demande (en L)
Vente (en $/L)
Produit P

E

F

G

≥ 400
11
1/3

≥ 800
15
–

≥ 200
14
2/3

Le produit P se vend 22 $/L.

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

10

NOP 2.1.5

Un problème de mélange : schéma

FIGURE 2.1

A

Ventes

C

B

Ventes

Ventes

E

Ventes

D

Ventes

F

Ventes

G

Ventes

P
Ventes

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

11

NOP 2.1.5

Un problème de mélange : le modèle linéaire

Variables de décision :
xIJ = nombre de litres du liquide I affectés à l’usage J
où I = A, B, ..., G, P et J = E, F, G, P, V. Par exemple,
xAE = nombre de litres du liquide A qui entrent dans la composition du mélange E
xGV = nombre de litres du mélange G qui seront vendus sur le marché.
On introduit également des variables d’étape :
xI = nombre de litres du produit I utilisés,
où I = A, B, C, D, E, G.
Fonction-objectif : Max z = Ventes – Achats, où
Ventes = 6 xAV + 5 xBV + 8 xCV + 11,75 xDV + 11 xEV + 15 xFV + 14 xGV + 22 xPV
Achats = 5,50 xA + 4,50 xB + 7,50 xC + 11,25 xD
Contraintes : Elles se regroupent en 5 catégories.
(a) Disponibilité des liquides :
xAV + xAE + xAF + xAG = xA
xBV + xBE + xBF + xBG = xB
xCV + xCE + xCF + xCG = xC
xDV + xDE + xDF + xDG = xD

et
et
et
et

xA ≤ 18 000
xB ≤ 14 250
xC ≤ 16 000
xD ≤ 12 000

(b) Pour un mélange, quantité vendue ou utilisée = quantité fabriquée :
xAE + xBE + xCE + xDE = xE et xE = xEV + xEP
xAF + xBF + xCF + xDF = xFV
xAG + xBG + xCG + xDG = xG et xG = xGV + xGP
xEP + xGP = xPV
(c) Conditions imposées dans l’élaboration des mélanges :
xAE = 0,30 xE et xBE ≥ 0,10 xE et xCE = 0,40 xE et xDE ≤ 0,05 xE
xAF ≥ 0,25 xFV et xBF ≤ 0,20 xFV et xCF = 0,20 xFV et xDF ≥ 0,10 xFV
xAG = 0,20 xG et xBG ≥ 0,15 xG et xCG = 0,40 xG et xDG ≤ 0,20 xG
xGP = 2 xEP
(d) Quantités minimales imposées par le carnet de commandes :
xEV ≥ 400 et xFV ≥ 800 et xGV ≥ 200
(e) Enfin, il faut ajouter les contraintes usuelles de non-négativité.

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

12

NOP 2.1.5 Un problème de mélange : une solution optimale

TABLEAU 2.4
E
A
B
C
D
E
G
Total

F

1 599
1 332,5
2 132
266,5
–
–

4 389
0
1 254
627
–
–

5 330

6 270

G
2 012
2 917,5
4 024
1 106,5
–
–
10 060

P

Ventes

Total

–
–
–
–
4 930
9 860

0
0
8 590
0
400
200

8 000
4 250
16 000
2 000
5 330
10 060

14 790

–

–

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

13

NOP 2.1.6 Vitrex : description du contexte

TABLEAU 2.5 Vitrex : besoins minimaux en espaces

Mois

Besoins minimaux (en 00 m2)

1
2
3
4
5
6

35
20
30
10
15
20

TABLEAU 2.6 Vitrex : coûts de location selon la durée du bail

Durée (en mois)
Coût (en $/100 m2)

1

2

3

4

5

6

200

360

500

625

745

850

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

14

NOP 2.1.6

Vitrex : une solution optimale
x 11 = 15
x 13 = 5
x 16 = 15
x 33 = 10
x 66 = 5
z = 21 250 (dollars).

Examinons ce programme de baux en regard des besoins minimaux de Vitrex.
TABLEAU 2.7
Mois

Besoins

1
2
3
4
5
6

35
20
30
10
15
20

Espaces loués
15

5
15
15 5
15 5

15
15
15
15
15
115 5 15 15

10
10
10
10
10
10

Excédent
5
5
5
5
5
5

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

15

0
0
0
5
0
0

NOP 2.1.7
TABLEAU 2.9

Horaire des standardistes, 1re version : données
Horaire des standardistes : description des données, 1re version

Heures

0−3

3−6

6−9

9 − 12

12 − 15

15 − 18

18 − 21

21 − 24

Besoins

6

4

12

20

20

24

14

14

Salaire

86 $

86 $

86 $

75 $

75 $

75 $

80 $

80 $

FIGURE 2.2

0h

Horaire des standardistes : représentation schématique

3h

6h

9h

12 h

15 h

x0
x3

★★★★★★★★★★

x6

★★★★★★★★★★

x9

★★★★★★★★★★

x12
•
•
•

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

16

18 h

•••

NOP 2.1.7

Horaire des standardistes, 1re version : le modèle linéaire
Variables de décision :
xj = nombre de standardistes prenant leur service à j heures
Objectif : Minimiser z, où
z = 86 x0 + 86 x3 + 86 x6 + 75 x9 + 75 x12 + 75 x15 + 80 x18 + 80 x21
Contraintes :
x0 + x3 + x6 + x9 + x12 + x15 + x18 + x21

≥ 6

x0 + x3 + x6 + x9 + x12 + x15 + x18 + x21

≥ 4

x0 + x3 + x6

≥ 12

x0 + x3 + x6 + x9

≥ 20

x0 + x3 + x6 + x9 + x12

≥ 20

x0 + x3 + x6 + x9 + x12 + x15

≥ 24

x0 + x3 + x6 + x9 + x12 + x15 + x18

≥ 14

x0 + x3 + x6 + x9 + x12 + x15 + x18 + x21

≥ 14

x0 + x3 + x6 + x9 + x12 + x15 + x18 + x21

= xT

Toutes les variables sont non négatives et entières.

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

17

NOP 2.1.7

Horaire des standardistes, 3e version

FIGURE 2.3

Horaire des standardistes : représentation schématique de la 3e version

Salaire

90

80

80

80

80

80

80

80

80

85

85

Variable

x0

y7

x8

y8

x9

y9

x15

y15

x16

x23

y23

Min

×
×

×
×
×

6
5
2
2
3
3
4
12
20
23
24
24
20
22
24
25
22
20
18
16
15
14
9
7

0h– 1
1h– 2
2h– 3
3h– 4
4h– 5
5h– 6
6h– 7
7h– 8
8h– 9
9 h – 10
10 h – 11
11 h – 12
12 h – 13
13 h – 14
14 h – 15
15 h – 16
16 h – 17
17 h – 18
18 h – 19
19 h – 20
20 h – 21
21 h – 22
22 h – 23
23 h – 24

h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h

×
×
×
×
×
×
×

×
×
×
×
×
×
×

×
×
×
×
×
×
×
×
×
×
×

×
×
×
×
×
×
×

×
×
×
×
×
×
×

×
×
×

×
×
×
×
×
×
×

×
×
×
×
×
×
×

×
×
×
×
×
×
×

×
×
×
×
×
×
×

×

×

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

18

Dom
10 h – 1 h
10 h – 1 h
10 h – 1 h
10 h – 1 h
11 h – 12 h
11 h – 12 h

11 h – 12 h

19 h – 20 h
19 h – 20 h
19 h – 20 h

NOP 2.1.7

Horaire des standardistes, 3e version : le modèle linéaire

Variables de décision :
xj = nombre de standardistes prenant leur service à j heures et leur pause-repas
3 heures après l’arrivée au travail
yj = nombre de standardistes prenant leur service à j heures et leur pause-repas
4 heures après l’arrivée au travail
Objectif :
Min z = 90 x0 + 80 (y7 + x8 + y8 + x9 + y9 + x15 + y15 + x16) + 85 (x23 + y23)
Contraintes :
x0 + x23 + y23 ≥ 6
x0 + y23 ≥ 2
x23 ≥ 2
x0 + y7 ≥ 12
y7 + x8 + y8 ≥ 20
y8 + x9 + y9 ≥ 24
y7 + x8 + y9 ≥ 20
y7 + x8 + y8 + x9 ≥ 22
x8 + y8 + x9 + y9 + x15 + y15 ≥ 25
x9 + y9 + x15 + y15 + x16 ≥ 22
x15 + y15 + x16 ≥ 20
y15 + x16 ≥ 18
x15 ≥ 16
x16 + x23 + y23 ≥ 7
x0 + y7 + x8 + y8 + x9 + y9 + x15 + y15 + x16 + x23 + y23 = t
Toutes les variables sont non négatives et entières.

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

19

NOP 2.1.8 Bobines-mères : commandes et plans de coupe

TABLEAU 2.13

Commandes déjà acceptées

Largeur (en cm)

Longueur (en m)

Nombre de rouleaux

64
60
35

250
250
250

360
180
180

TABLEAU 2.14 Plans de coupe
Largeur
64 cm
60 cm
35 cm
Chutes

Plan de coupe
1

2

3

4

5

6

7

8

9

10

3
0
0

2
1
0

2
0
2

1
2
0

1
1
2

1
0
4

0
3
1

0
2
2

0
1
4

0
0
6

23 27 17 31 21 11

0

25 15

5

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

20

NOP 2.1.8

Bobines-mères : le modèle linéaire et quelques solutions optimales

Variables de décision :
xj = nombre de mises en œuvre du plan de coupe numéro j
Objectif :
Min z = x1 + x2 + ... + x10
Contraintes :
3 x1 + 2 x2 + 2 x3 + … + 0 x10 ≥ 360
0 x1 + 1 x2 + 0 x3 + … + 0 x10 ≥ 180
0 x1 + 0 x2 + 2 x3 + … + 6 x10 ≥ 180
j = 1, 2, …, 10

xj ≥ 0 et entier
Solutions optimales :
Solution A

Solution B

Solution C

x1 = 120
x7 = 60
x10 = 20
z = 200
Chutes = 2 860 cm

x1 = 80
x3 = 60
x7 = 60
z = 200
Chutes = 2 860 cm

x1 = 110
x6 = 30
x7 = 60
z = 200
Chutes = 2 860 cm

Solution D

Solution E

Solution F

x1 = 100
x3 = 30
x7 = 60
x10 = 10
z = 200
Chutes = 2 860 cm

x1 = 95
x3 = 30
x6 = 15
x7 = 60
z = 200
Chutes = 2 860 cm

x1 = 104
x3 = 12
x6 = 24
x7 = 60
z = 200
Chutes = 2 860 cm

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

21

NOP 2.1.9 Pastissimo : données

Pastissimo s’est engagée à livrer 4 tonnes de spaghettis à la fin de chacun des 6 prochains
mois, contre une rémunération de 1,28 $ le kilo. Le tableau 2.15 décrit l’entente de
Pastissimo avec son fournisseur ; le tableau 2.16 donne la capacité de production et les
coûts de production. Pastissimo peut stocker jusqu’à 3 tonnes de matière première, à un
coût mensuel de 20 $ la tonne, et jusqu’à 1 tonne de produits finis, à un coût mensuel de
25 $ la tonne. Pastissimo disposera au début du 1er mois de 2 tonnes de matière première
et désire en retrouver la même quantité à la fin des 6 mois.

TABLEAU 2.15 Pastissimo : l’entente avec Les Grands Moulins
Mois

Prix (en $/t)

Minimum (en t)

Maximum (en t)

1
2
3
4
5
6

1 000
975
1 000
980
1 020
1 025

4
3
5
2
4
5

6
4
7
3
7
6

TABLEAU 2.16 Pastissimo : l’entente avec Hyper-Halli
Mois

Capacité de production (en t)

Coûts (en $/t)

1
2
3
4
5
6

6
5
4
4
4
3

160
150
150
160
175
165

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

22

NOP 2.1.9 Pastissimo : une solution optimale

TABLEAU 2.17

Mois

1

2

3

4

5

6

aj : Achats

4

5

4

4

4

3

3 825

x j : Production

4

3

5

3

4

5

24 070

ej : Entrepôt – Blé

2

–

1

–

–

–

60

sj : Magasin – Spaghettis

–

1

1

1

1

–

100

P = R – z = 30 720 – 28 055 = 2 665

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

23

Coûts

NOP 2.2.1

Franchises : division de la région en secteurs

FIGURE 2.4

1
5
2

3

9

6
4

10

7
8

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

24

NOP 2.2.1

Franchises : le modèle linéaire
Objectif :
Min z = v1 + v2 + … + v10
Contraintes :
v1 + v2 + v3 ≥ 1
v1 + v2 + v3 + v4 + v5 + v7 + v10 ≥ 1
v1 + v2 + v3 + v9 + v10 ≥ 1
v2 + v4 + v7 + v8 + v10 ≥ 1
v2 + v5 + v6 + v7 ≥ 1
v5 + v6 + v7 ≥ 1
v2 + v4 + v5 + v6 + v7 + v8 ≥ 1
v4 + v7 + v8 + v9 + v10 ≥ 1
v3 + v8 + v9 + v10 ≥ 1
v2 + v3 + v4 + v8 + v9 + v10 ≥ 1
vj = 0 ou 1

j = 1, ..., 10

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

25

NOP 2.2.2 Rotation du personnel : données

TABLEAU 2.18

Coûts (en 000 $) des affectations possibles

Poste
Sergent

a

b

c

d

e

f

g

h

m

n

A
B
C
D
E
F
G
H
M
N

*
6
8
7
7
8
6
7
11
8

12
*
17
16
13
8
9
14
16
9

15
14
*
9
8
11
13
16
17
8

11
12
21
*
12
14
9
11
15
13

17
16
17
12
*
12
11
16
17
9

15
11
16
18
22
*
16
22
18
7

11
17
14
18
19
12
*
15
21
8

12
18
12
14
12
17
14
*
22
9

10
18
10
11
13
9
13
14
*
8

10
16
15
14
12
18
16
18
11
*

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

26

NOP 2.2.2

Rotation du personnel : le modèle linéaire

Variables de décision :
vIj = 1 si le sergent I est muté du poste i au poste j
Objectif :
Min z = 500 vAa + 12 vAb + 15 vAc + ... + 9 vNh + 8 vNm + 500 vNn
Contraintes :
vAa + vAb + vAc + vAd + vAe + vAf + vAg + vAh + vAm + vAn = 1
vBa + vBb + vBc + vBd + vBe + vBf + vBg + vBh + vBm + vBn = 1
vCa + vCb + vCc + vCd + vCe + vCf + vCg + vCh + vCm + vCn = 1
vDa + vDb + vDc + vDd + vDe + vDf + vDg + vDh + vDm + vDn = 1
vEa + vEb + vEc + vEd + vEe + vEf + vEg + vEh + vEm + vEn = 1
vFa + vFb + vFc + vFd + vFe + vFf + vFg + vFh + vFm + vFn = 1
vGa + vGb + vGc + vGd + vGe + vGf + vGg + vGh + vGm + vGn = 1
vHa + vHb + vHc + vHd + vHe + vHf + vHg + vHh + vHm + vHn = 1
vMa + vMb + vMc + vMd + vMe + vMf + vMg + vMh + vMm + vMn = 1
vNa + vNb + vNc + vNd + vNe + vNf + vNg + vNh + vNm + vNn = 1
vAa + vBa + vCa + vDa + vEa + vFa + vGa + vHa + vMa + vNa = 1
vAb + vBb + vCb + vDb + vEb + vFb + vGb + vHb + vMb + vNb = 1
vAc + vBc + vCc + vDc + vEc + vFc + vGc + vHc + vMc + vNc = 1
vAd + vBd + vCd + vDd + vEd + vFd + vGd + vHd + vMd + vNd = 1
vAe + vBe + vCe + vDe + vEe + vFe + vGe + vHe + vMe + vNe = 1
vAf + vBf + vCf + vDf + vEf + vFf + vGf + vHf + vMf + vNf = 1
vAg + vBg + vCg + vDg + vEg + vFg + vGg + vHg + vMg + vNg = 1
vAh + vBh + vCh + vDh + vEh + vFh + vGh + vHh + vMh + vNh = 1
vAm + vBm + vCm + vDm + vEm + vFm + vGm + vHm + vMm + vNm = 1
vAn + vBn + vCn + vDn + vEn + vFn + vGn + vHn + vMn + vNn = 1
vIj = 0 ou 1

tout (I ; j)

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

27

NOP 2.2.3

Chemin le plus court : le réseau

FIGURE 2.5

Réseau orienté

2

1
5

6

7

4

O
3

4

4
2

5

3
3

6

5

6

3

7

6
9

6

7

2

8

4

2

9

2

5

7

8

5

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

28

A

NOP 2.2.3

Chemin le plus court : le modèle linéaire
Variables de décision :
vij = 1 si l’objet emprunte le tronçon (i ; j).
Objectif :
Min z = 5 v O1 + 3 vO2 + 4 vO3 + 7 v13 + ... + 2 v9A
Contraintes :
Origine

vO1 + vO2 + vO3 = 1

Sommet 1

vO1 − v13 − v14 = 0

Sommet 2

vO2 − v23 − v25 − v26 − v28 = 0

Sommet 3

vO3 + v13 + v23 − v34 − v38 = 0

Sommet 4

v14 + v34 − v48 − v49 = 0

Sommet 5

v25 − v56 − v57 = 0

Sommet 6

v26 + v56 − v67 − v68 − v6A = 0

Sommet 7

v57 + v67 − v78 − v7A = 0

Sommet 8

v28 + v38 + v48 + v68 + v78 − v89 − v8A = 0

Sommet 9

v49 + v89 − v9A = 0

Arrivée

v6A + v7A + v8A + v9A = 1
vij = 0 ou 1

tout (i ; j)

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

29

NOP 2.3.3

Les chaises et leur cuisson : le modèle linéaire

Variables de décision : xA, xB, LA, LB, rA, rB, vA, vB, où, par exemple,
xA = nombre de chaises A à fabriquer d’ici trois semaines
LA = nombre de lots complets de 10 chaises A
rA = nombre de chaises A dans un éventuel lot résiduel
vA = 1 si 1 ≤ rA ≤ 9
Objectif :
Max z = 450 xA + 800 xB − 100 LA − 100 vA − 100 LB − 100 vB
Contraintes :
xA ≥ 42
xB ≥ 53
xA ≤ 100
xB ≤ 100
1,5 xA + 2 xB ≤ 250
0,5 xA + 0,75 xB ≤ 100
2 xA + 3 xB ≤ 327
xA − 10 LA − rA = 0
v A ≤ rA ≤ 9 v A
x B − 5 LB − rB = 0
v B ≤ rB ≤ 4 v B
8 LA + 6 LB + 8 vA + 6 vB ≤ 140
xA, xB , LA, LB , rA, rB ≥ 0 et entiers
vA, vB = 0 ou 1

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

30

NOP 2.4.1

Parcours des éboueurs : plan du quartier et circuits optimaux

FIGURE 2.6

4

5

2

1
6

3

3

6

7

6

8

4
5

7

4

6
6

9

5

5
3

7

Circuits optimaux : xA, xB, LA, LB, rA, rB, zA, zB, où, par exemple,
1→6→4→7→6→4→2→1→4→5→7→8→5→8→3→2→5→3→2→1
1→4→5→7→8→5→3→8→5→2→3→2→1→2→4→7→6→4→6→1

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

31

8

NOP 2.4.1 Parcours des éboueurs : durée des passages sur les tronçons

TABLEAU 2.27

Tronçon
1
1
1
2
2
2
3
3
4
4
4
5
5
6
7

–
–
–
–
–
–
–
–
–
–
–
–
–
–
–

Total

2
4
6
3
4
5
5
8
5
6
7
7
8
7
8

Passage avec enlèvement
20
30
35
22
12
30
35
50
25
20
35
30
20
24
12

Passage hors service
4
6
8
5
3
6
7
9
6
5
7
4
5
6
3

400 min

84 min

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

32

NOP 3.1.1

FRB : description du contexte

Produits et demande
No

Description

Demande en tonnes

Profit par tonne

1
2

Tuyauterie
Gueuses

34
14

1 000 $
1 200 $

Durée de fabrication
Ébarbage

Peinture

Temps requis
Tuyauterie
Gueuses

10 h/t
15 h/t

2 h/t
3 h/t

Heures disponibles

200 h

60 h

Note : Une tonne de tuyauterie requiert 10 heures au département d’ébarbage et 2 heures à celui de peinture.

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

33

NOP 3.1.2

FRB : les contraintes technologiques et la région admissible
10 x1 + 5 x2 ≤ 200

(ébarbage) (1)

12 x1 + 3 x2 ≤ 160

(peinture) (2)

10 x1 + 5 x2 ≤ 34

(demande de tuyauterie) (3)

10 x1 + 5 x2 ≤ 14

(demande de gueuses) (4)

10 x1 + 5 x2 ≥

0

(5)

10 x1 + 5 x2 ≥

0

(6)

x2

x1 = 34

10
x1 +
5 x2
00

=2
x2 = 14

2x

1

+3

x2

=6

0
x1

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

34

NOP 3.1.2

FRB : le modèle linéaire

Variables de décision :
x1 = nombre de tonnes de tuyauterie traitées
x2 = nombre de tonnes de gueuses traitées
Objectif :
Max z = 1 000 x1 + 1 200 x2
Contraintes :
10 x1 + 5 x2 ≤ 200

(ébarbage) (1)

12 x1 + 3 x2 ≤ 160

(peinture) (2)

10 x1 + 5 x2 ≤ 34

(demande de tuyauterie) (3)

10 x1 + 5 x2 ≤ 14

(demande de gueuses) (4)

10 x1 + 5 x2 ≥

0

(5)

10 x1 + 5 x2 ≥

0

(6)

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

35

NOP 3.1.4

FRB : repérage graphique de la solution optimale

FIGURE 3.8

x2

(x1* ; x2*) = (15 ; 10)

x1

O
z = 6 000 z = 12 000

z = p*

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

36

NOP 4.2

Intersections des droites associées aux contraintes de (FRB)

FIGURE 4.3

x2

L

F
A

B

K

J
C

D
O

G

I
H

x1

E

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

37

NOP 4.2 Coordonnées des intersections des droites associées aux contraintes de (FRB)

TABLEAU 4.1

No

VHB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

x 1, x 2
x 1, e1
x 1, e2
x 1, e3
x 1, e4
x 2, e1
x 2, e2
x 2, e3
x 2, e4
e1, e2
e1, e3
e1, e4
e2 , e3
e2, e4
e3, e4

Solution

Point

(0 ; 0 ; 200 ; 60 ; 34 ; 14)
(0 ; 40 ; 0 ; −60 ; 34 ; −26)
(0 ; 20 ; 100 ; 0 ; 34 ; −6)
--(0 ; 14 ; 130 ; 18 ; 34 ; 0)
(20 ; 0 ; 0 ; 20 ; 14 ; 14)
(30 ; 0 ; −100 ; 0 ; 4 ; 14)
(34 ; 0 ; −140 ; −8 ; 0 ; 14)
--(15 ; 10 ; 0 ; 0 ; 19 ; 4)
(34 ; −28 ; 0 ; 76 ; 0 ; 42)
(13 ; 14 ; 0 ; −8 ; 21 ; 0)
(34 ; −8/3 ; −380/3 ; 0 ; 0 ; 50/3)
(9 ; 14 ; 40 ; 0 ; 25 ; 0)
(34 ; 14 ; −210 ; −50 ; 0 ; 0)

O
L
F
--A
D
G
I
--C
E
K
H
B
J

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

38

Remarque
Inadmissible
Inadmissible
Pas de solution
Inadmissible
Inadmissible
Pas de solution
Inadmissible
Inadmissible
Inadmissible
Inadmissible

NOP 4.3

Organigramme de l’algorithme du simplexe dans le cas (PLS)

FIGURE 4.6

ÉTAPE A

CONSTRUCTION DU
DU
CONSTRUCTION
TABLEAU INITIAL
INITIAL
TABLEAU

SOLUTION
OPTIMALE?

OUI

FIN

NON
ÉTAPE B

CONSTRUCTION
CHOIX DE LA DU
TABLEAUENTRANTE
INITIAL
VARIABLE

ÉTAPE C

CONSTRUCTION
CHOIX DE LA DU
TABLEAUSORTANTE
INITIAL
VARIABLE

IL N’EN
EXISTE
PAS

FIN

ÉTAPE D

CONSTRUCTION DU
PIVOTAGE
TABLEAU
INITIAL

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

39

NOP 4.3

Tableau du simplexe : gabarit pour (FRB)

Tableau no
Base
Coeff.

Var.

Sommet
1000

1200

0

0

0

0

x1

x2

e1

e2

e3

e4

Valeur

0
0
0
0
zj
c j − zj

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

40

Limite

NOP 4.3

Modèle (FRB) : séquence des tableaux du simplexe

TABLEAU 4.11
Base
No

Coeff.

0

0
0
0
0

O

Var.
e1
e2
e3
←e4

zj
c j − zj
1
A

0
0
0
1200

e1
←e2
e3
x2

zj
c j − zj
2
B

0
1000
0
1200

←e1
x1
e3
x2

zj
c j − zj
3
C

0
1000
0
1200
zj
c j − zj

e4
x1
e3
x2

1000

1200

0

0

0

0

x1

x2

e1

e2

e3

e4

Valeur

Limite

10
2
1
0

5
3
0
1

1
0
0
0

0
1
0
0

0
0
1
0

0
0
0
1

200
60
34
14

200/5
60/3
*
14/1

0
1000

0
1200
↑

0
0

0
0

0
0

0
0

0

10
2
1
0

0
0
0
1

1
0
0
0

0
1
0
0

0
0
1
0

−5
−3
0
1

130
18
34
14

0
1000
↑

1200
0

0
0

0
0

0
0

1200
− 1200

16 800

0
1
0
0

0
0
0
1

1
0
0
0

− 5,0
0,5
− 0,5
0,0

0
0
1
0

10,0
− 1,5
1,5
1,0

40
9
25
14

1000
0

1200
0

0
0

500
− 500

0
0

− 300
300
↑

25 800

0
1
0
0

0
0
0
1

0,10
0,15
− 0,15
− 0,10

− 0,50
− 0,25
0,25
0,50

0
0
1
0

1
0
0
0

4
15
19
10

1000
0

1200
0

30
− 30

350
− 350

0
0

0
0

27 000

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

41

130/10
18/2
34/1
*

40/10
*
25/1,5
14/1

NOP 4.4

Région admissible de (PMF)

FIGURE 4.8

x2

Région admissible

F

P

M

C

N

O

D

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

42

x1

NOP 4.4

Le modèle (PMF)
Modèle (PMF) :
Max z = 1 000 x1 + 1 200 x2
sous les contraintes :
10 x1 + 5 x2 ≤ 200

(82)

2 x1 + 3 x2 = 60

(83)

10 x1 + 5 x2 ≤ 12

(84)

10 x1 + 5 x2 ≥

(85)

6

x1 , x2 ≥ 0

(86)

Modèle équivalent (PMF=) :
Max z = 1 000 x1 + 1 200 x2

(87)

sous les contraintes :
10 x1 + 5 x2 + e1
2 x1 + 3 x2
10 x1

+ e3

10 x1 + 5 x2

– e4

= 200

(88)

= 60

(89)

= 12

(90)

=

(91)

6

x1, x2, e1, e3, e4 ≥ 0

(92)

Modèle avec variables de base pour chaque contrainte:
Max z = 1 000 x1 + 1 200 x2

(93)

sous les contraintes :
10 x1 + 5 x2 + e1
2 x1 + 3 x2

+ a2

x1 + 5 x2 + e1 + e3

= 200

(94)

= 60

(95)

= 12

(96)

+ a4 =

2 x1 + 3 x2 + 5 x2 + e– e4
x1, x2, e1, e3, e4, a2, a4 ≥ 0

6

(97)
(98)

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

43

NOP 4.4

Tableau du simplexe : gabarit pour (PMF)

Phase :

Tableau no

Point

Base
Coeff.

Var.

x1

x2

0

0

0

e1

e3

e4

a2

a4

Valeur

0
0
0
0
zj
c j − zj

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

44

Limite

NOP 4.4

Modèle (PMF) : séquence des tableaux du simplexe

TABLEAU 4.14
Base
No
I0
O

Coeff.
0
1
0
1

Var.
e1
a2
e3
←a4

zj
c j − zj
I1
M

0
1
0
0

e1
←a2
e3
x2

zj
c j − zj
I2
F

0
0
0
0

e1
e4
e3
x2

zj
c j − zj

II 0
F

0
0
0
1200

e1
e4
←e3
x2

zj
c j − zj
II 1
P

0
0
1000
1200
zj
c j − zj

e1
e4
x1
x2

0

0

0

0

0

1

1

x1

x2

e1

e3

e4

a2

a4

Valeur

Limite

10
2
1
0

5
3
0
1

1
0
0
0

0
0
1
0

0
0
0
−1

0
1
0
0

0
0
0
1

200
60
12
6

40
20
*
6

2
−2

4
−4
↑

0
0

0
0

−1
1

1
0

1
0

66

10
2
1
0

0
0
0
1

1
0
0
0

0
0
1
0

5
3
0
−1

0
1
0
0

−5
−3
0
1

170
42
12
6

2
−2

0
0

0
0

0
0

3
−3
↑

1
0

−3
4

42

6,67
0,67
1,00
0,67

0
0
0
1

1
0
0
0

0
0
1
0

0
1
0
0

− 1,67
0,33
0,00
0,33

0
−1
0
0

100
14
12
20

0
0

0
0

0
0

0
0

0
0

0
1

0
1

0

1000

1200

0

0

0

6,67
0,67
1,00
0,67

0
0
0
1

1
0
0
0

0
0
1
0

0
1
0
0

100
14
12
20

800
200
↑

1200
0

0
0

0
0

0
0

24 000

0
0
1
0

0
0
0
1

1
0
0
0

− 6,67
− 0,67
1,00
− 0,67

0
1
0
0

20
6
12
12

1000
0

1200
0

0
0

200
− 200

0
0

26 400

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

45

34
14
*
*

15
21
12
30

NOP 4.5

(PMult) : le modèle linéaire et la région admissible
Max z = 1 000 x1 + 1 500 x2
sous les contraintes :
10 x1 + 5 x2 ≤ 200
2 x1 + 3 x2 ≤ 60
10 x1 + 5 x2 ≤ 34
10 x

FIGURE 4.9

+ 5 x2 ≤ 14
x1 , x2 ≥ 0
1

Région admissible de (PMult)

x2

A

B
C

D
O

z = 30 000

x1

z = 15 000
z = 9 000

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

46

NOP 4.5

(PMult) : un tableau optimal

Tableau no 2

Sommet B

Base

1 000

1 500

0

0

0

0

Coeff.

Var.

x1

x2

e1

e2

e3

e4

0
1 000
0
1 500

e1
x1
e3
x2

0
1
0
0

0
0
0
1

1
0
0
0

−5,0
0,5
−0,5
0,0

0
0
1
0

10,0
−1,5
−1,5
−1,0

40
09
25
14

1 000
0

1 500
0

0
0

0
0

0
0

30 000

zj
cj − zj

500
−500

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

47

Valeur

NOP 4.5 Un modèle (P) sans solution admissible : dernier tableau

TABLEAU 4.17

Phase I : Tableau no 2
Base

Point C

0

0

0

0

0

0

1

1

Coeff.

Var.

x1

x2

e1

e2

e3

e4

a3

a4

Valeur

0
0
1
1

x1
x2
a3
a4

1
0
0
0

0
1
0
0

0,15
− 0,10
− 0,15
0,10

− 0,25
0,50
0,25
− 0,50

0
0
−1
0

0
0
0
−1

0
0
1
0

0
0
0
1

15
10
19
14

0
0

0
0

− 0,05
0,05

− 0,25
0,25

−1
1

−1
1

1
0

1
0

23

zj
cj − z j

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

48

NOP 4.5

Un modèle non borné

TABLEAU 4.18

Modèle non borné : dernier tableau du simplexe

Phase II : Tableau no 1

Point (0 ; 2)
1

2

0

0

0

x1

x2

e1

e2

e3

Valeur

Limite

− 1,33
− 0,67
0,67

0
1
0

0,67
0,33
3,00

1
0
0

0
0
1

1
2
36

*
*
*

− 1,33
2,33

2
0

0,67
− 0,67

0
0

0
0

4

Base
Coeff.

Var.

0
2
0

e2
x2
e3
zj
cj − zj

↑

FIGURE 4.10

x2

Région admissible d’un modèle non borné

– 2 x1 + 3 x2 = 6

(0 ; 2)

(0 ; 1)
(4,5 ; 1)

z=4

6 x1 – 9 x2 = 18
x2 = 1

x1
© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

49

NOP 4.5

(PDég) : le modèle linéaire et la région admissible
Max z = 1 000 x1 + 1 200 x2
sous les contraintes :
10 x1 + 5 x2 ≤ 200
2 x1 + 3 x2 ≤ 60
10 x1 + 5 x2 ≤ 34

10 x

1

+ 5 x2 ≤ 20

x1 , x2 ≥ 0
FIGURE 4.11

Région admissible de (PDég)

x2

F

C

D
x1

O

© gaëtan morin éditeur ltée, 2001. Tous droits réservés. La recherche opérationnelle, 3e édition (Nobert, Ouellet, Parent)

50