Théorie des graphes : Chapitre 7 solutions des problèmes
Télécharger PDFChapitre 7 – Solutions des problèmes
1. Modifications à apporter à un réseau
Dans le réseau proposé, la tâche H ne précède pas la tâche F, contrairement à ce qui est spécifié dans le tableau des prédécesseurs immédiats donné dans l'énoncé du problème.
Un réseau corrigé, conforme aux données du tableau, est présenté ci-dessous.
2. Énumération des chemins d'un réseau
Les chemins possibles, ainsi que leurs durées, sont énumérés dans le tableau ci-dessous.
Chemin Durée
1 → 2 → 3 → 4 → 5 → 6 26
1 → 2 → 3 → 5 → 6 22
1 → 2 → 4 → 5 → 6 25
1 → 3 → 4 → 5 → 6 28
1 → 3 → 5 → 6 24
L'unique chemin critique, de longueur 28, est : 1 → 3 → 4 → 5 → 6.
3. Chemin critique
(a) Un réseau qui représente ce projet est donné ci-dessous.
Afin de faciliter le calcul des réponses aux questions (b) et (c), ont été ajoutés les moments au plus tôt des différents sommets et, lorsqu'ils diffèrent, les moments au plus tard.
(b) La date d'achèvement au plus tôt du projet est 13.
(c) L'unique chemin critique est : L → M → G → F1 → S.
4. Moments au plus tôt et au plus tard
(a) Un réseau qui représente ce projet est donné ci-dessous.
Les moments au plus tôt des différents sommets et, lorsqu'ils diffèrent, les moments au plus tard ont été ajoutés.
(b) et (c) Les moments au plus tôt et au plus tard des différentes tâches sont donnés dans le tableau suivant :
Tâche ES EF LS LF
L 0 8 0 8
M 8 13 8 13
N 8 12 9 13
H 13 19 13 19
S 19 26 19 26
T 12 21 17 26
P 26 38 26 38
F1 12 12 13 13
(d) L'unique chemin critique, de longueur 38, est : L → M → H → S → P.
5. Marge des tâches
(a) Un réseau qui représente ce projet est donné ci-dessous.
Les moments au plus tôt des différents sommets et, lorsqu'ils diffèrent, les moments au plus tard ont été ajoutés.
(b) L'unique chemin critique, de longueur 28, est : A → C → F → H.
(c) La marge de la tâche F est nulle, car elle fait partie du chemin critique : marge de F = L(5) – E(4) – dF = 21 – 9 – 12 = 0.
Par contre, la tâche G ne fait pas partie du chemin critique et sa marge est positive : marge de G = L(6) – E(3) – dG = 28 – 7 – 8 = 13.
6. Suppression d'une tâche
(a) Un réseau qui représente ce projet est donné ci-dessous.
(b) L'unique chemin critique, de longueur 36, est : A → C → F → H → J → K → L.
(c) La suppression de la tâche J entraînerait les modifications suivantes : la tâche G se terminerait au sommet terminal commun de H et de I ; ce sommet deviendrait le sommet initial de K ; les sommets 10 et 11 seraient renumérotés 9 et 10 respectivement ; le chemin critique deviendrait A → B → D → E → G → K → L et la durée minimale du projet diminuerait à 35 périodes.
7. Modification de la durée des tâches et chemin critique
Les moments au plus tôt et au plus tard du réseau sont donnés dans le tableau ci-dessous.
Sommet s 1 2 3 4 5
E(s) 0 6 9 17 22
L(s) 0 6 14 17 22
La durée minimale du projet est de 22 jours et l'unique chemin critique est : B → G → H.
(a) La marge de la tâche A est de 11 jours : marge de A = L(3) – E(1) – dA = 14 – 0 – 3 = 11.
Pour que A appartienne à un chemin critique, il faudrait que sa durée augmente de 11 jours ou plus.
(b) La durée de la tâche G devrait être diminuée de plus de 5 jours. Dans un tel cas, le projet pourrait être parachevé en 17 jours et le chemin critique serait B → E → D.
(c) On peut poursuivre cette opération jusqu'à ce que la durée de la tâche H soit nulle ou qu'un autre chemin devienne critique. Ici, ces deux cas surviennent simultanément : lorsque la durée de H est diminuée de 5 jours, les chemins B → E → D et B → G → H sont tous deux critiques.
8. Tâche critique
Pour que la tâche K appartienne à un chemin critique, sa durée doit être égale ou supérieure à la durée minimale du projet, qui est de 35 jours.
9. Chemin critique et modèle linéaire
(a) Les tâches de marge nulle sont celles représentées par les arcs 1 → 2, 2 → 3, 3 → 6, 6 → 7 et 7 → 8.
(b) L'unique chemin critique, d'une longueur de 34 jours, est composé des arcs donnés en (a).
(c) Considérons les durées sur les arcs comme des coûts et cherchons à maximiser le coût total lorsque le sommet 1 émet une unité de flot, que les sommets 2 à 7 sont des sommets de transbordement et que le sommet 8 absorbe l'unique unité de flot qui transite dans le réseau.
Le modèle linéaire associé à ce réseau donnera, à l'optimum, un chemin le plus long.
Noter que, à l'optimum, la quantité de flot sur chacun des arcs sera nulle ou égale à 1.
Il est donc possible d'utiliser comme variables de décision les variables binaires vij définies ainsi :
vij = 1 si l'arc i → j fait partie du chemin critique où i → j est l'un des arcs du réseau.
L'objectif consiste à maximiser z, où z = 4v12 + 3v23 + 5v36 + 2v67 + 3v78.
À l'optimum, z = 34 (jours).
Note : Les contraintes «Sommet 1» et «Sommet 8» sont redondantes dans ce modèle. En leur absence, les variables v12 et v78 prendraient quand même leur valeur maximale 1 à l'optimum, car leurs coefficients dans la fonction-objectif sont positifs.
10. Hydro-Québec
Un réseau représentant ce projet est reproduit ci-dessous.
Les moments au plus tôt et au plus tard des sommets du réseau (sauf le sommet 1, dont les moments sont nuls) sont donnés dans le tableau suivant :
Sommet s 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
E(s) 21 26 50 36 50 62 40 59 72 83 62 83 98 114 137 137 137 158 168 178 198 258
L(s) 21 26 57 41 57 67 40 59 72 83 67 83 116 114 137 137 148 158 168 178 198 258
Les marges des différentes tâches sont présentées dans le tableau suivant :
Tâche A B C D E F G H I J K L M N O P Q R S T U V W X Y Z F1 F2 F3 F4 F5 F6 F7
Marge 0 0 7 5 7 7 0 5 0 13 7 7 0 5 0 0 18 18 29 0 11 0 0 0 0 5 8 10 0 33 0 11
Le projet exige 258 jours. Les tâches critiques sont celles qui forment l'unique chemin critique : A → B → G → I → M → O → F4 → P → T → F6 → V → W → X → Y → Z.
11. Planification familiale en Tataouine
Un réseau représentant ce projet est reproduit ci-dessous.
Les moments au plus tôt et au plus tard des sommets du réseau sont donnés dans les tableaux suivants :
Sommet s 1 2 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
E(s) 0 15 17 19 29 39 42 62 20 100 43 48 58 63 102 45 65 110 113 133 173 73 93 44 64 713 16 96 17 111 112 67 667 75 75 718
L(s) 0 15 17 19 29 39 42 80 31 111 43 48 58 63 120 88 108 121 652 672 712 73 93 73 93 713 32 112 118 122 123 118 718 118 118 718
Les marges des différentes tâches sont présentées dans le tableau suivant :
Tâche A B1 B2 B3 B4 C1 C2 C3 C4 C5 C6 C7 C8 D1 D2 D3 E1 E2 E3 F1 F2 G1 G2 G3 H1 H2 I1 I2 I3 I4 J1 J2 J3 J4 K1 K2 K3 K4 L1 L2 L3 M1 M2 M3 X1 X2 X3 X4
Marge 0 0 0 0 0 0 18 18 18 539 539 539 539 11 11 11 16 16 16 21 21 11 11 11 43 43 0 0 0 0 0 0 0 29 29 29 0 51 51 51 48 43 43 57 56 51 43
Le projet exige 718 jours. Il existe deux chemins critiques, qui ne diffèrent que par la dernière tâche :
A → B1 → B2 → B3 → B4 → C1 → I1 → I2 → I3 → I4 → J1 → J2 → J3 → J4
A → B1 → B2 → B3 → B4 → C1 → I1 → I2 → I3 → I4 → J1 → J2 → J3 → K4.
12. Belladone
(a) La durée minimale du projet, si toutes les tâches sont exécutées à la vitesse normale, est de 74 jours. L'unique chemin critique est formé des arcs 1-2, 2-3, 3-5, 5-7 et 7-8.
(b) Parmi les tâches critiques, 5-7 est celle dont le coût d'accélération est le plus faible.
On accélère donc la tâche 5-7 d'un jour, ce qui réduit la durée du projet d'un jour et coûte 100 $.
(c) Après l'accélération retenue à la question (b), l'unique chemin critique reste formé des arcs 1-2, 2-3, 3-5, 5-7 et 7-8.
On choisit à nouveau d'accélérer la tâche 5-7. Ainsi, en accélérant la tâche 5-7 de 2 jours, ce qui coûte 200 $, on réduit d'autant la durée du projet.
(d) Si on ne tient pas compte des coûts à assumer, on utilisera les durées accélérées. La durée minimale du projet est alors de 53 jours.
13. Implantation d'un progiciel de gestion de paie et des ressources humaines
(a) Un réseau représentant ce projet est reproduit ci-dessous.
Le tableau suivant donne les moments au plus tôt et au plus tard des 13 sommets du réseau :
Sommet s 1 2 3 4 5 6 7 8 9 10 11 12 13
E(s) 0 7 10 18 24 31 39 59 20 59 47 71 76
L(s) 0 7 10 18 24 31 39 59 59 59 71 71 76
L'étude préliminaire exigera 76 jours.
(b) Le réseau admet un seul chemin critique : A → B → D → F → H → J → L → F1 → Q → T.
(c) Le tableau suivant donne les marges demandées :
Tâche C D E M
Marge 24 0 38 8
(d) Le modèle linéaire utilisé comporte des variables de décision réelles indiquant le moment où seront atteints chacun des sommets du réseau et des variables donnant le nombre de périodes d'accélération des tâches.
xs = moment où se produit l'événement s
Acct = réduction (en jours) de la durée de la tâche t grâce à l'accélération, où s = 1, 2, ..., 13 et où t = D, F, H, I, J.
On ajoute des variables binaires pour tenir compte de la possibilité d'ajouter des consultants spécialisés en implantation de progiciels :
vt = 1 si on recourt à des consultants pour accélérer la tâche t, où t = A, L, M, O, P, Q, T, U.
L'objectif consiste à minimiser le coût total z d'accélération.
L'entreprise devrait recourir à des consultants pour accélérer les tâches A et L. Voici les durées de la collaboration des utilisateurs :
Tâche D F H I J
Durée (en jours) 2 1 3 0 2
Le coût total z d'accélération s'élèvera à 30 000 $.