Cours de Recherche Opérationnelle

 

Année 2002 - 2003

 

EXAMEN BLANC 01

 

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

On pose tout d’abord le problème_ 3

Itération n°1_ 4

Itération n°2_ 4

Itération n°3_ 5

Solution de base_ 5

Vérification de la solution de base_ 5

Trouver une solution optimisée_ 6

III. Cas n°2_ 7

Traduction en graphe (brut) 8

Traduction en graphe épuré_ 8

Réseau PERT_ 8

Réseau GANTT_ 9

 


 

I. Questions de cours

 

 

  1. Qu’est ce que l’algorithme de Ford

 

 

  1. Qu’est-ce que la méthode du simplexe

 

 

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

 

 

  1. Décrire la méthode PERT, ainsi que ses objectifs

 

 

 

 


 

II. Cas n°1

 

Les entreprises de stockage A, B et C ont respectivement les capacités de livraison suivantes 180 palettes, 90 palettes, 270 palettes d’un produit très particulier que leur commande les sociétés clientes C1, C2, C3, C4 ayant des besoins respectifs de 150 palettes, 225 palettes, 90 palettes, 75 palettes.

 

 

Les coûts de transports sont indiqués par la matrice ci-dessous :

 

 

 

Client 1

Client 2

Client 3

Client 4

Entrepôt A

36

30

33

30

Entrepôt B

48

54

51

45

Entrepôt C

63

66

57

60

 

 

1.      Donner une solution de base en utilisant l’algorithme de BALAS-HAMMER.

 

 

2.      Trouver la solution optimale.

 

On pose tout d’abord le problème

 

  1. On  indique la somme des « Besoins » par client.
  2. On indique la somme des « Disponibilités » par entrepôts.
  3. On calcule les « Delta », cela correspond à la différence entre les deux plus petites valeurs.
  4. La somme des disponibilités doit toujours être égale à la somme des besoins.
  5. La condition de non dégénérescence équivaut à  [ n * m – ( n + m – 1) ].

Avec n, le nombre de ligne et m le nombre de colonnes.

Ici cela donne 3 * 4 – ( 3 + 4 – 1 ) = 6.

 

 

 

 

Client 1

Client 2

Client 3

Client 4

 

Dispo.

Delta

Entrepôt A

36

30

33

30

 

180

0

Entrepôt B

48

54

51

45

 

90

3

Entrepôt C

63

66

57

60

 

270

3

 

 

 

 

 

 

 

 

Besoins

150

225

90

75

 

540

 

Delta

12

24

18

15

 

 

 

 


 

Itération n°1

 

 

Client 1

Client 2

Client 3

Client 4

 

Dispo.

Delta

Entrepôt A

36

30 180

33

30

 

0

0

Entrepôt B

48

54

51

45

 

90

3

Entrepôt C

63

66

57

60

 

270

3

 

 

 

 

 

 

 

 

Besoins

150

45

90

75

 

360

 

Delta

12

24

18

15

 

 

 

 

Itération n°2

 

 

Client 1

Client 2

Client 3

Client 4

 

Dispo.

Delta

Entrepôt A

36

30 180

33

30

 

0

 

Entrepôt B

48

54

51

45 75

 

15

3

Entrepôt C

63

66

57

60

 

270

3

 

 

 

 

 

 

 

 

Besoins

150

45

90

0

 

285

 

Delta

15

12

6

15

 

 

 

 


 

Itération n°3

 

 

Client 1

Client 2

Client 3

Client 4

 

Dispo.

Delta

Entrepôt A

36 0

30 180

33 0

30 0

 

0

 

Entrepôt B

48 15

54 0

51 0

45 75

 

0

3

Entrepôt C

63

66

57

60 0

 

270

3

 

 

 

 

 

 

 

 

Besoins

135

45

90

0

 

270

 

Delta

15

12

6

 

 

 

 

 

Solution de base

A la fin de cette itération, on se rend compte qu’il y a 6 zéros. Par conséquent le condition de non dégénérescence est vérifiée, on possède donc une première solution qui peut être la suivante :

 

 

Client 1

Client 2

Client 3

Client 4

 

Dispo.

Entrepôt A

36 0

30 180

33 0

30 0

 

180

Entrepôt B

48 15

54 0

51 0

45 75

 

90

Entrepôt C

63 135

66 45

57 90

60 0

 

270

 

 

 

 

 

 

 

Besoins

150

225

90

75

 

540

Vérification de la solution de base

1.      Somme des Ai = Somme des Bi

En effet : 150+225+90+75 = 180+90+270 = 540

2.      Somme des X1j = a1

En effet : 0+15+135 = 150 …

3.      Somme des Xi1 = b1

En effet : 135+45+90+0 = 270 …

4.      Solution non dégénérée

En effet il y a 6 zéros, ( 3*4–(3+4–1)=6 ).

 


 

Trouver une solution optimisée

 

Rappel de la solution de base :

 

Client 1

Client 2

Client 3

Client 4

 

Dispo.

Entrepôt A

36 0

30 180

33 0

30 0

 

180

Entrepôt B

48 15

54 0

51 0

45 75

 

90

Entrepôt C

63 135

66 45

57 90

60 0

 

270

 

 

 

 

 

 

 

Besoins

150

225

90

75

 

540

Le coût associé à la solution de base correspond à :

15*48 + 135*63 + 180*30 + 45*66 + 90*57 + 75*45  =  26 100

 

1.      Traduction de la solution en graphe :

2.      On repère le coût de transport le plus élevé :

Liaison entre C à C2 : 66

3.      La ligne associée à ce coût possède un potentiel à 0

 

4.      On détermine les potentiels

 

 


 

III. Cas n°2

La société EVENEMENT  SPORTIF S.A. souhaite lancer une nouvelle course cycliste.

Elle choisit de gérer la mise au point et lancement de celle-ci sous la forme d’un projet.

Elle a donc recensé les tâches nécessaires pour mener à bien les diverses actions à réaliser.

Puis elle a évalué les délais nécessaires à la réalisation de chaque tâches.

L’ensemble de ces informations sont synthétisées dans le tableau ci-dessous :

 

N° tâche

Nom tâche

Durée

(en jours)

Prédécesseurs

1

Choix du lieu et de la date de la course

1

 

2

Obtentions des autorisations nécessaires

20

1

3

Engagements des sponsors

12

1

4

Création des différents formulaires

15

3

5

Commandes des maillots

9

3

6

Recrutement des bénévoles nécessaires

3

3 . 5

7

Enregistrement des participants

25

4 . 2 . 6

8

Numérotation des dossards

4

7

9

Réalisation du parcours et de la course

5

8

10

Aménagement des zones de départ et d’arrivée

5

8

11

Remise des prix

1

9 . 10

12

Nettoyage du site

3

11

13

Clôture de la course

1

12

 

Il vous est demandé de :

 

 

 

 

 

 


 

Traduction en graphe (brut)

 

Traduction en graphe épuré

 

Réseau PERT

 

La durée du projet est de 67 jours ouvrés.

Les chemins critiques sont les suivants :

 

Les marges sont les suivantes :

 


 

Réseau GANTT