ECOLE NORMALE SUPÉRIEURE DE ﺍﻟﻤﺪﺭﺳﺔ ﺍﻟﻌﻠﻴﺎ ﻸﺳﺎﺗﺬﺓ ﺍﻟﺗﻌﻠﻴﻢ ﺍﻟﺗﻘﻨﻲ
L'ENSEIGNEMENT
TECHNIQUE DE MOHAMMEDIA
ENSET ﺍﻟﻤحﻤﺪﻴﺔ
UNIVERSITÉ HASSAN II DE CASABLANCA ﺟﺎﻤﻌﺔ ﺍﻟحﺳﻦ ﺍﻟﺜﺎﻨﻲ ﺑﺎﻟﺪﺍﺭ ﺍﻟﺑﻴﻀﺎﺀ
Examen de Recherche Opérationnelle 1
Durée : 2 heures
Question Préliminaire : Réseau PERT.
Tracer le réseau PERT relatif au projet ci-dessous et déterminer sa durée minimale :
Désignation des tâches Tâches immédiatement antérieures Durées en semaines
A - 3
B P 9
C B, N 3
D L, Q 1
E D, J 6
F H, P 7
G - 12
H O 9
I P 6
J C 4
K D 5
L F, N 3
M D, J 1
N H, O 1
O - 6
P A, G 8
K I 15
Exercice 1 : Algorithme Machin1.
On suppose que le sommet de départ (qui sera la racine de l’arborescence) est le sommet numéroté 0.
Notons qu’on peut toujours renuméroter les sommets pour que ce soit le cas.
Algorithme :
pour faire
faire
modification faux;
pour faire
si ( ) alors
pour chaque successeurs de faire
si alors {
; // est atteint à partir de
Modification vrai;
;
tant que (modification = vrai)
Adresse : BP 159 Bd Hassan II, ﺷﺎﺭﻉ،159 ﺻﻨﺪﻭﻕ ﺍﻟﺒﺮﻳﺪ: ﺍﻟﻌﻨﻮﺍﻥ
Mohammedia - Maroc ﺍﻟﻤﺤﻤﺪﻳﺔ،ﺍﻟﺤﺴﻦ ﺍﻟﺜﺎﻧﻲ
Tél : 0523322220 0523322220 : ﺍﻟﻬﺎﺗﻒ
Fax : 0523322546 0523322546 : ﺍﻟﻔﺎﻛﺲ
Site web : [Link] [Link]
ECOLE NORMALE SUPÉRIEURE DE ﺍﻟﻤﺪﺭﺳﺔ ﺍﻟﻌﻠﻴﺎ ﻸﺳﺎﺗﺬﺓ ﺍﻟﺗﻌﻠﻴﻢ ﺍﻟﺗﻘﻨﻲ
L'ENSEIGNEMENT
TECHNIQUE DE MOHAMMEDIA
ENSET ﺍﻟﻤحﻤﺪﻴﺔ
UNIVERSITÉ HASSAN II DE CASABLANCA ﺟﺎﻤﻌﺔ ﺍﻟحﺳﻦ ﺍﻟﺜﺎﻨﻲ ﺑﺎﻟﺪﺍﺭ ﺍﻟﺑﻴﻀﺎﺀ
1. Appliquer l’algorithme Machin1 au graphe ci-dessus.
2. En déduire l’arborescence des plus courts chemins.
3. Modifier cet algorithme par ajout d’un test permettant de détecter la présence d’un circuit
absorbant.
Exercice 2 : Algorithme Machin2.
Soit le graphe avec un poids associé à chacune de ses arêtes. On veut trouver, dans G, un
arbre couvrant de poids total minimum.
Algorithme :
Données :
– Graphe
– Pour chaque arête e de E, son poids c(e).
Résultat : Arbre ou forêt couvrant de poids minimum.
Trier et renuméroter les arêtes de G dans l’ordre croissant de leur poids :
c(e 1 ) ≤ c(e 2 ) ≤ . . . ≤ c(e m ).
Poser
Tant que et faire
Début
si e k 1 ne forme pas de cycle avec F alors F := F {e k 1 }
k := k+1
Fin
1. Appliquer l’algorithme Machin2 au graphe ci-dessus.
2. En déduire l’arbre couvrant de poids minimum.
3. Proposer une procédure permettant de détecter les cycles.
Adresse : BP 159 Bd Hassan II, ﺷﺎﺭﻉ،159 ﺻﻨﺪﻭﻕ ﺍﻟﺒﺮﻳﺪ: ﺍﻟﻌﻨﻮﺍﻥ
Mohammedia - Maroc ﺍﻟﻤﺤﻤﺪﻳﺔ،ﺍﻟﺤﺴﻦ ﺍﻟﺜﺎﻧﻲ
Tél : 0523322220 0523322220 : ﺍﻟﻬﺎﺗﻒ
Fax : 0523322546 0523322546 : ﺍﻟﻔﺎﻛﺲ
Site web : [Link] [Link]