ENM EXAMEN DE RECHERCHE OPERATIONNELLE 20 Janvier 2012

2A/T.C O CC orruynifm ffn^ Dure : 2h 15mnPROBLEME (8points)

Une compagnie fabrique trois modles de tlvisions couleurs, A, B et C, qui lui rapportent des profits de 80, 120 et 50 respectivement. Les niveaux maxima de production requis pour une semaine sont de 60 pour le modle A, 100 pour le modle B, et 30 pour le modle C.

Chaque type de tlvision requiert un certain temps pour la fabrication des pices, pour lassemblage et pour lemballage. Plus prcisment, pour un article du modle A on a besoin de, une (1) heure pour la fabrication, de 1 heure pour lassemblage et de 2 heures pour lemballage. Les donnes correspondantes pour un article de B sont de 2h, lh et lh , et pour un article de C elles sont lh, 2h et lh. Pendant la semaine venir, la compagnie aura 100 heures de disponibles pour la fabrication, 115 h pour lassemblage et 80 pour lemballage.

1- Etablir le programme linaire (P) permettant de dterminer le plan de production, qui maximise les profits de la compagnie.

2- Rsoudre (P).3- Ecrire le programme dual (D) de P.4- Rsoudre (D) en expliquant votre raisonnement.

EXERCICE1 (4points)

: Rsoudre le programme linaire suivant

z = X j+2X 2+ 2 x 3 + 3 x 4 + x s ] "

1= X1+X2

0 X 2 -X 3 + X5-

= X |+ X 3 + x4-.0

EXERCICE 2 (8points)

Un livreur de pizzas doit livrer une commande en moins de 30 minutes. Chaque arc du graphe orient de la figure ci-aprs indique la dure exprime en minutes des trajets entre les diffrents carrefours de son arrondissement. La socit fabriquant les pizzas se situe l entre du rseau et la livraison doit s effectuCT la sortie du g r a p h e { ^ ^

1- Donner une bonne numrotation des sommets du graphe.2- Le livreur arrivera-t- il temps ? Enumrer touts les trajets optim aux

parcourus par le livreur depuis lentre jusqu^ la sortie, en expliquant votre raisonnement et indiquer la^thode ou algorithme utiliss.:

Calculer la dure dun chemin optimal parcouru par le livreur depuis lentre jusqu la sortie.

- Tracer alors une arboreseence des chemins les plus courts issus de l entre du rseau vers les autres sommets du graphe.