Ensait - A3 - Recherche Opérationnelle

Date: Évaluation du 2008-03-12

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 de réponses argumentées à la liste des questions de l'énoncé.
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. Par ailleurs,l'attention des étudiants est attirée sur le fait que le trafic réseau de leur ordinateur est susceptible d'être enregistré pendant la durée de 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\ge18$$

1 Optimisation et rachat de contraintes

Cette partie est largement inspirée de http://www.sebastien-verbois.be/latex/examens-recherche-operationnelle/ro-lihd-examen-2004-janvier.pdf.

1.1 Description simplifiée du problème

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

Table: Données de fabrication

	Temps requis (h/palette)				Heures
Atelier	P1	P2	P3	P4	disponibles
A1	0,12	0,15	0,10	0,09	2760
A2	0,10	0,09	0,15	0,10	2500
A3	0,05	0,04	0,04	0,05	2760

Le Table 2 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 2: Profit par palette

	P1	P2	P3	P4
Profit (€/palette)	2,20	1,90	2,25	1,71

1.2 Problème avec stockage

En fait, ce qui est fabriqué au cours du mois n'est livré qu'à la fin du mois suivant. En effet, une période minimale d'un mois de stabilisation est requise pour que les produits atteignent leur pleine qualité. L'espace d'entreposage requis pour une palette de chaque produit est donné dans le Table 3.

Table 3: Espace d'entreposage par palette

	P1	P2	P3	P4
Espace ($m^{2}$/palette)	0,27	0,28	0,29	0,24

Le manufacturier dispose de 4000 $m^{2}$ d'espace d'entreposage, qui lui coûtent 1200 €par mois. Il peut louer de l'espace supplémentaire (maximum 8000 $m^{2}$), par tranche de 2000 $m^{2}$, aux tarifs mensuels dégressifs donnés dans le Table 4.

Table: Coût de location

Espace ($m^{2}$)	2000	4000	6000	8000
Coût (€)	3000	4800	6400	7800

Déterminer, pour chacune des cinq valeurs possibles de la surface de stockage, quelles sont les valeurs optimales à produire et quel est le profit correspondant. En déduire la meilleure décision possible.

1.3 Modification de l'atelier A1

On continue à se placer dans les conditions AVEC stockage et on examine ce que pourrait apporter une augmentation de la quantité d'heures disponibles dans l'atelier A1.

1. En supposant cette augmentation obtenue à côut nul, quelles seraient les valeurs optimales à produire et quels seraient le profit correspondant et le nombre d'heures supplémentaires nécessaires.
2. En supposant que ces heures supplémentaires coûtent smic+charges, quel serait le bénéfice de l'opération ?
3. Que peut-on faire d'autre ?

.../...

2 Files d'attente

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 1ddmmyy où dd, mm, yy sont tels que dd/mm/19yy soit votre date de naissance.

2.1 Petit essai

1. Modifier la fonction petitessai de la façon suivante: (lignes 6 à 8)
   grand('setsd',1ddmmyy)
   deff('s=arv',sprintf('s=grand(1, ''uin'', %f, %f)',10, 19))
   deff('s=srv',sprintf('s=grand(1, ''uin'', %f, %f)',16, 26))
2. Lancer le programmer et en commenter le résultat.

2.2 Simulation M/Ga/1

Utiliser le programme 'système M/Ga/1' avec les réglages $marv=63, msrv=58, a=2.3, N=40000$ et $seed=1ddmmyy$. 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 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. Déterminer le débit d'arrivée $\lambda$ à partir de $marv$ et donner la distribution (pdf) de probabilité associée. Quelle est la variance du processus d'inter-arrivée ?
3. Rappeler quelle est la distribution de probabilité associée à la loi Gamma de paramètres $a$ et $b$. Déterminer la valeur de $b$ en fonction de $a$ et de $msrv$. Quelle est la variance (théorique) des services ?
4. Pour les temps de service (graphe 4). Récupérer les données par (cf fonction drawq, ligne 487 sqq) :
   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$.
5. Rappeler ce qu'est le paramètre $\rho$ et donner sa valeur.
6. Rappeler ce que signifient les graphes "1-Durée des états" et "2-États lors de l'arrivée". Pourquoi sont-ils si ressemblants dans l'exemple étudié ?
7. 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.
8. 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 en la reliant à $\lambda$ et $\mu$.