GME Diapositives .pdf
Nom original: GME-Diapositives.pdf
Ce document au format PDF 1.5 a été généré par / Mac OS X 10.4.4 Quartz PDFContext, et a été envoyé sur fichier-pdf.fr le 03/05/2012 à 22:18, depuis l'adresse IP 41.141.x.x.
La présente page de téléchargement du fichier a été vue 1775 fois.
Taille du document: 2.1 Mo (114 pages).
Confidentialité: fichier public
Aperçu du document
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
Télécharger le fichier (PDF)
GME-Diapositives.pdf (PDF, 2.1 Mo)