INFO DEBUT TEST 5 GRAPHE BTS

                             INFO TEST 5 GRAPHES BTS       29/01/14

    EXERCICE 2

          Dès leur arrivée à 8 h dans un garage, les deux employés Bertand et Didier 

          consultent les différentes opérations qui seront à effectuer sur

          différents véhicules.

           Les opérations, qui sont notées  A B C D E F G H J K L, ne se font pas

           dans n'importe quel ordre.

          Certaines opérations nécessitent la réalisation d'une ou plusieurs opérations

          préalables.

           Le gérant, pour la  gestion du travail, a conçu le tableau suivant.

Opérations péalables nécessaires  Opérations  Durée des opérations  en mn
  A         4
  B         5
                   A C         6
                   B C D         10
                   D E         8
                   D F         2
                   F G         3
                   D H         15
                   C J         12
                   G E K         7
                   J K H L         5

     1. Déterminez les niveaux des différentes opérations.

Opérations péalables nécessaires  Opérations  Niveaux
  A         0
  B         0
                   A C         1
                   B C D         2      
                   D E         3
                   D F         3
                   F G         4
                   D H         3
                   C  J         2 
                   G E K         5
                   J  K H L         6

     2.a. Dessinons le graphe.

    Les opérations sont A B C D E F G H J K L.

    Grexbt

    b. Donnons la matrice adjacente M :

                   Mtm1

   3.  Bertand a été désigné pour accomplir sur un véhicule les opérations 

               de A  jusqu'à L.

               A quelle heure, au mieux, aura- t- il terminé son travail ?

          Recherchons d'abord le chemin de durée minimale de A à L

A Départ

B

C

D

E

F

G

H

J

K

L

Fin

Sommet sélect.

0

 ∞

 ∞

 ∞

 ∞

 ∞

 ∞

 ∞

 ∞

 ∞

 ∞

A

Adaj à A : C

         

 ∞

A6

 ∞

 ∞

 ∞

 ∞

 ∞

 ∞

 ∞

 ∞

C

Adaj à C : DJ

 

 ∞

        

C6+10

 

C16

  ∞

  ∞

  ∞

  ∞

C6+12

 

C18

  ∞

  ∞

D

Adaj à D :

EFH

         

 ∞

        

         

D16+8

 

D24

D16+2

 

D18

 

D16+15

 

D31

C18

  ∞

  ∞

F ( ou J )

Adaj à F :G

        

 ∞

       

        

D24

          

F18+3

 

F21

D31

C18

  ∞

  ∞

J

Adaj à J :L

 

        

 ∞

        

       

D24

         

F21

D31

          

 ∞

J18+5

J23

STOP

G

Adaj à G :K

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

         Dès que L est atteint on s'arrête.

          De A à L la durée minimale est 23 mn.

          Bertrand a commencé à 8h.

          Conclusion : Il a terminé à 8h23

  -----------------------------------------------------------------------------------------