OM43 : RECHERCHE OPERATIONNELLE

UTBM - IMAP Semestre dAutomne 2006 (17/01/07)

Examen Final (dure 2 heures) e Exercice 1 On prvoit une augmentation du trac entre les deux villes 1 et 9 relies par le rseau routier e e e illustrs sur la gure ci-dessous. Sur ce rseau, on a reprsent le trac actuel ainsi que la e e e e capacit maximale de chacune des routes en nombre de vhicules par minute. e e250 2 300 | 300 | 1 100 | 400 | 3 | 400 | 50 | 50 | 50 | 100 | 5 4 100 | 100 | 0 | 50 | 200 | 200 | 6

0 20 0 | 0 |3

50 | 50 |

50 | 150 | 50 0 | 50 | | 150 | 100 7 | 300 | 300 | 400 | 8

1. Dterminer le ot maximum que peut supporter ce rseau, en utilisant lalgorithme de e e Ford-Fulkerson. 2. Donner la coupe minimale de ce rseau et calculer sa capacit en prcisant les arcs utiliss e e e e dans le calcul. Exercice 2 Une entreprise doit planier la production dun produit P sur un cycle de 4 mois. Le cot xe u de lancement dans latelier de production du produit P est estim ` 300 Euros. Le cot direct ea u dpend de la main doeuvres disponible. Il est de 150 Euros lunit en heures normales et de 200 e e Euros lunit en heures supplmentaires. La demande prvisionnelle de n de mois de ce produit e e e P ainsi que la capacit maximale de production en heures normales et en heures supplmentaires e e sont donnes dans le tableau suivant: e Mois 1 2 3 4 Capacit en heures normales 4 2 4 3 e Capacit en heures supp. e 3 3 2 2 Demande prvisionnelle e 4 5 3 4 On dispose dune capacit de stockage limite ` 3 units et le cot de stockage est de 15 Euros e e a e u par unit stocke par mois. On sinterdit toute rupture de stock et le stock au dbut et ` la n e e e a du sycle est nul. 1. Donner, pour chaque mois, lexpression du cot de production Cpk (x) ; k = 1, 2, 3 et 4. u 2. Formuler le probl`me de planication de la production du produit P comme un probl`me e e de programmation dynamique. 3. Dterminer le plan optimal de production et de stockage pour les mois 1 ` 4. e a 4. Calculer le gain de la solution optimale par rapport ` la solution qui consiste ` produire a a chaque mois juste pour satisfaire la demande. 1

0 15 0 | 5 |2

9

Exercice 3 En des points A, B, C et D existent des quantits respectives de 500, 600, 200 et 900 tonnes de e minerai ` transporter vers 6 points de ventes o` on doit faire parvenir les quantits respectives a u e de 400, 300, 700, 200, 400 et 200 tonnes. Les distances mutuelles, en Km, des points de vente aux points A, B, C et D sont donnes dans le tableau ci-dessous, et le transport a t ngoci e ee e e au tarif kilomtrique de 5 Euros la tonne. e A B C D Soit la solution initiale suivante : 1 A B C D Demandes 2 300 400 400 3 500 100 100 700 4 5 6 200 200 200 200 200 400 Ores 500 600 200 900 1 9 7 6 6 2 12 3 6 8 3 9 7 9 11 4 6 7 11 2 5 9 5 3 2 6 10 5 11 10

300

200

1. Calculer le cot de transport total correspondant ` cette solution initiale. u a 2. Partant de cette solution initiale, dterminer le plan de transport ` cot minimal en e a u utilisant la mthode du stepping stone. e 3. Quel est le gain par rapport ` la solution initiale. a

2