Ensait - A3 - Recherche Opérationnelle

Date: Évaluation 2008-2009 : le 03/04/2009 à 16h15

Durée : 2 heures. Le sujet comporte 3 pages. Tous documents autorisés.
L'usage d'un ordinateur (et des programmes indiqués en cours) est recommandé.

Consignes

1. La première qualité que l'on attend d'un ingénieur est de savoir présenter ses conclusions. Les listings, les calculs, les graphiques et autres "sorties d'ordinateur" ne peuvent en aucun cas remplacer un relevé de conclusions, rédigé de façon précise et scientifique.
2. Il est donc nécessaire d'ordonner différents types de matériaux de façon à produire un document organisé, produisant une liste ordonnée de réponses argumentées.
3. La méthode RECOMMANDÉE est de rédiger les réponses à la main et de faire des couper-coller avec des ciseaux et de la colle pour insérer les "sorties d'ordinateur". L'expérience confirme que cette méthode est à la fois la plus rapide et la plus robuste. C'est aussi celle qui permet de se concentrer sur les compétences évaluées et non sur les compétences/incompétences en dactylographie.
4. L'attention des étudiants est attirée sur le fait que le trafic réseau de leur ordinateur est susceptible d'être enregistré durant l'évaluation.
5. La bibliothèquewaitsdoit être à jour, c'est à dire avoir été téléchargée récemment sur le site web. Le numéro de version est :
   $$waits\ge22$$

1 Un problème d'approvisionnement

1.1 Description de la situation

Table 1: Problème d'approvisionnement : distances et tonnages

		60 t	80 t	50 t	70 t
		Châteauroux	Bourges	Clermont	Lyon
50 t	Dunkerque	567	502	696	736
70 t	Le Havre	406	448	594	682
40 t	Bordeaux	345	410	369	548
60 t	Sète	568	574	380	325
80 t	Mulhouse	688	623	519	340

Comme décrit dans la Table 1, une matière première se trouvée stockée dans 5 dépôts situés à Dunkerque (50 tonnes disponibles), au Havre (70 tonnes disponibles), à Bordeaux (40 tonnes disponibles), à Sète (60 tonnes disponibles) et à Mulhouse (80 tonnes disponibles). On souhaite approvisionner 4 points de vente situés à Châteauroux (60 tonnes demandées), Bourges (80 tonnes demandées), Clermont (50 tonnes demandées) et Lyon (70 tonnes demandées). On suppose que les seuls coûts à prendre en compte pour l'optimisation sont les coûts de transports, et que ceux-ci sont proportionnels à la quantité transférée et à la distance parcourue (telle qu'elle est donnée dans la table ci-dessus).

1.2 Questions à traiter

Utiliser seed=ddmmyy, où dd/mm/19yy est votre date de naissance. On commencera par se limiter à Dunkerque, Le Havre, Bordeaux pour les sources et Châteauroux et Bourges pour les destinations.

1. Quelles sont les variables, quel est leur nombre ? Quelles sont les contraintes ?
2. Mettre en équations. Expliciter la taille des matrices utilisées. Donner une description par blocs de ces matrices.
3. Résoudre. Imprimer ce que vous avez écrit avant d'appeler la fonction linpro.
   En cas de besoin, il est conseillé de perturber légèrement les données pour éviter les "systèmes redondants" (cf Section 2.5 in http://www.douillet.info/~douillet/cours/oprea/node5.html). On pourra utiliser par exemple : dist=dist+rand(dist)/1D7.
4. Écrire (ou imprimer) explicitement la solution, et commenter le résultat obtenu.

2 Optimisation et rachat de contraintes

2.1 Problématique de base

Un manufacturier fabrique quatre produits : P1, P2 et P3. Ces produits requièrent l'intervention de 4 ateliers distincts : A1, A2, A3, A4. La Table 2 présente les données relatives aux durées de production et aux disponibilités de ces ateliers au cours du prochain mois.

Table 2: Données de fabrication

	Temps requis (h/palette)			Heures
Atelier	P1	P2	P3	disponibles
A1	0.20	0.15	0.10	2400
A2	0.21	0.08	0.13	2400
A3	0.15	0.04	0.04	2400
A4	0.17	0.12	0.15	2400

La Table 3 indique le profit par palette réalisé lors de la commercialisation des produits. Déterminer quelles sont les quantités optimales à produire et quel est alors le profit attendu.

Table 3: Profit par palette

	P1	P2	P3
Profit (€/palette)	2.75	2.93	3.35

2.2 Rachat de contraintes

Indiquer quelles sont les contraintes actives, et indiquer quelle est leur valeur de rachat (prix maximal à payer pour relaxer la contrainte). .../...

3 Chronogramme

On utilise désormais le programme de simulation de files d'attentes décrit dans waits.sce. Le générateur aléatoire doit être initialisé en utilisant seed=ddmmyy, où dd/mm/19yy est votre date de naissance.

1. Modifier la fonction petitessai de la façon suivante: (lignes 7 à 8)
   grand('setsd', ddmmyy) 
   [aa,bb,cc,dd]=(17,27,11,18);
   de façon à obtenir
   ======= arv in 11..18, srv in 17..27 ==
2. Lancer le programme. Imprimer son résultat.
3. Tracer et commenter le chronogramme correspondant.

Remarque : pour les étudiants qui utiliseraient Scilab 1.5 sur un ordinateur personnel, modifier les lignes 15 et 16 en remplaçant zeros(1,5) par zeros(1,5-nbsej). Pour les versions précédentes, cette modification n'est pas nécessaire.

4 Simulation M/Ga/1

Utiliser le programme 'système M/Ga/1' avec les réglages $marv=70, msrv=60, a=2, N=30000$ et $seed=ddmmyy$. Le processus d'interarrivée $X$ est alors une loi exponentielle de paramètre $\lambda$ et le processus de service $Y$ est une loi Gamma de paramètres $a$ et $b$ tels que $\mathrm{E}\left(X\right)=marv$ et $\mathrm{E}\left(Y\right)=msrv$.

1. Imprimer le tableau de résultats. Imprimer les 5 graphes. Pour chacun d'eux, placer les moyennes et écart-types expérimentaux (on ne saurait exclure que l'utilisation d'une règle soit la méthode la plus rapide).
2. Donner les valeurs théoriques des débits et des variances du processus d'arrivée et du processus de service.
3. Pour les temps de service (graphe 4). Récupérer les données par (cf fonction drawq) :
   hndl,err=mopen('dat_services.txt', 'rb') 
   services=mget(many,'f', hndl); mclose(hndl)
   Puis comparer, par un test du $\chi^{2}$, les temps de service obtenus par simulation avec la distribution théorique. On choisira les classes pour que $\nu=10$.
4. Quelle serait la durée de séjour moyenne dans une file M/M/1 ayant les mêmes valeurs de $\lambda$ et $\mu$? Expliquer pourquoi la valeur obtenue pour la file M/Ga/1 est inférieure.
5. Comparer le nombre de services résiduels constatés et le nombre de clients entrés dans le système. Expliquer la proportion constatée.