Cours de Recherche Opérationnelle

 

Année 2002 - 2003

 

EXAMEN BLANC 02

 

1ère session normale de Juin 1997

 

Durée : 2 heures

Documents de cours autorisés

 

Barème :

·        Question de cours        4 points

·        Cas n°1                       8 points

·        Cas n°2                       8 points

 

 

 

I. Questions de cours 2

II. Cas n°1_ 3

1ère solution (de base) 4

Algorithme_ 4

Débit de chaque ville_ 5

Réalisation d’une déviation_ 6

III. Cas n°2_ 7

Tableau des tâches, durées, chemin critique, marge…__ 7

Diagramme de GANTT_ 7

 


 

I. Questions de cours

 

 

 

  1. Qu’est-ce qu’un chemin critique

 

 

  1. Qu’est-ce qu’un problème d’affectation

 

 


 

II. Cas n°1

 

 

Pou évaluer la capacité d’un réseau routier reliant la ville A et la ville J, des mesures ont étés effectuées sur chaque axe routier possible entre A et J.

 

Ces axes de circulation peuvent traverser les villes B, C, D, E, F, G, H et I.

 

Le schéma ci-dessous illustre la situation, les mesures indiquent le nombre maximal de véhicules que chaque route peut accepter compte tenu de ses caractéristiques propres.

 

Les mesures sont exprimés en centaines de véhicules par heurs.

 

 

 

  1. Quel est le débit maximal qui peut s’écouler entre les villes A et J ?


  2. Dans la question précédente, il n’a pas été tenu compte jusqu’ici des capacités de transit des villes intermédiaires, ce qui risque de fausser l’estimation du flot de véhicules.
    Aussi, pour tenir compte de ce fait, des mesures complémentaires ont étés réalisées afin de connaître les débits automobiles à l’intérieur de chaque ville :

Ville

B

C

D

E

F

G

H

I

Débit (nombre de voiture par heure)

1 000

5 000

3 500

6 000

4 500

2 500

2 000

500

            Compte tenu de ces paramètres, déterminer le débit maximal du réseau routier.


  1. Les finances régionales ne permettent que la réalisation d’une seule déviation autour d’une de ces villes. Laquelle pouvez-vous préconiser de façon à augmenter de manière maximale le flot de véhicules ?

 

1ère solution (de base)

8 000 voitures / heure.

Vérification : pour chaque point de passage, on a bien S (entrées) = S (sorties)

Un chemin est saturé, lorsque le flux est maximal.

Remarque : tous les circuits sont saturés.

On peut dans ce cas, appliquer l’algorithme, afin de trouver une solution optimisée.

Algorithme

Le but de l’algorithme, est de trouver un chemin non saturé pouvant accepter une charge supplémentaire, et à contrario compenser par un chemin saturé ou non, que l’on peut décharger.

Pour notre exercice, cela donne :

·         A partir de A :

o        On ne peut rien rajouter à A - B et A - D, car ils sont déjà saturés.

o        On peut rajouter une charge supplémentaire entre A et C.

·         A partir de C (+A) :

o        On peut rajouter à E.

o        On peut rajouter à D.

·         A partir de E :

o        On ne peut pas retirer ou ajouter à E – G et E – D, car ils sont saturés.

o        On peut retirer à E – B et B - A, mais on boucle sur C.

o        On peut rajouter à E – F, mais F – H est saturé, et avec F – B on boule sur C.

·         A partir de D (+C) :

o        On ne peut pas retirer à D – A, car on boucle sur C.

o        On peut rajouter une charge entre D et I.

·         A partir de I (+D) :

o        On peut retirer une charge entre I et G.

·         A partir de G (-I) :

o        On peut rajouter une charge entre G et J.

·         A partir de J (+G) :

o         

 


 

Cela donne un circuit que l’on peut optimiser facilement en calculant les deltas sur chaque axe. La valeur retenue sera le deltas minimum de tous les deltas en valeurs absolues (ici 35) :

 

On obtient par conséquent le nouveau graphe suivant :

11 500 voitures / heure. Gain de 80 000 – 11 500 = 3 500 voitures.

A ce stade on recommence l’algorithme, tant que l’on n’est pas bloqué. Ce qui est le cas ici.

 

Débit de chaque ville

On obtient avec cette solution :

4 000 voitures / heure.

Remarque : tous les chemins sont saturés, on peut donc appliquer l’algorithme d’optimisation.

On se rend compte qu’il est impossible d’optimiser cette solution.


 

Réalisation d’une déviation

 

Pour se faire, on reprends la solution optimale trouvée précédemment :

 

 

Et on cherche la meilleure déviation :

 

Il serait très judicieux d’installer la déviation pour la ville I. En effet, pour cette ville le débit est très faible par rapport aux potentiels existants en entrée 8 000, et en sortie 6 000.

 

On se rend d’ailleurs compte que le trajet I à J est passé de 6 000 véhicules/heure à 500 véhicules/heure, soit un ration de 1/12.

 

 

 


 

III. Cas n°2

  1. Créer le tableau des tâches, avec leur code, leur nom, leur durée et leur(s) prédécesseur(s).
  2. Déterminer le chemin critique, les marges, ainsi que la durée totale du projet.
  3. Réaliser le diagramme de GANTT.
  4. Tracer le diagramme d’enchaînement des tâches selon la méthode potentiels-tâches.

 

Tableau des tâches, durées, chemin critique, marge…

 

Etapes

Durée (jours)

Prédécesseurs

+ tôt

+ tard

Marge

DD

DF

DD

DF

 

A

Lancement

10

 

0

10

0

10

 

B

Création groupe prototype

5

A

10

15

10

15

 

C

Diagnostic de l’existant

30

A

10

40

10

40

 

D

Prototype Intranet

25

A . B

15

40

15

40

 

E

Validation architecture

20

D

40

60

130

150

90

F

Bilan

10

C . D

40

50

40

50

 

G

Expression des besoins

40

F

50

90

50

90

 

H

Déploiements navigateurs

10

F

50

60

80

90

30

I

Etude organisationnelle

60

G

90

150

90

150

 

J

Spécifications générales

5

G . H

90

95

90

95

 

K

Spécifications détaillées

10

J

95

105

95

105

 

L

Programmation

30

K

105

135

105

135

 

M

Recette programme

10

L

135

145

140

150

5

N

Mise en œuvre

0

E . I . M

150

150

150

150

 

 

Diagramme de GANTT

A

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

150

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

B

 

 

 

 

 

E

90

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

D

 

 

 

 

 

 

 

 

 

 

I

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

C

 

 

G

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

FIN

 

 

 

 

 

 

 

 

F

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

H

30

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

J

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

K

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

L

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

M

5