Introduction a la recherche opérationnelle

INTRODUCTION A LA RECHERCHE OPERATIONNELLE

Dualité & Sensibilité

DS1) Suite de l’exercice S6a).
Quel est le coût réduit de chacune des variables du problème?
DS2) Suite de l’exercice S3).
a) Si le coefficient de la variable x2 dans la fonction objectif augmentait de 2 unités, quel serait l’effet produit sur la solution optimale et la valeur optimale du problème? Et si cette augmentation était de 4 unités?
b) Quel est le coût réduit de chacune des variables du problème?
c) Quel est le prix dual de chacune des contraintes d’inégalité du problème?

Files d’attente

F1) Le responsable d’un parking du centre-ville a compté le nombre de voitures garées dans son parking à différents instants de la journée. En moyenne, il en a trouvé 150. Il sait par ailleurs que, toujours en moyenne, 40 voitures par heure pénètrent dans le parking et y trouvent une place.
Estimez le temps moyen passé par chaque voiture dans le parking. Expliquez votre approche.
F2) Des clients arrivent dans un restaurant selon un processus de Poisson au taux de 20 clients par heure. Le restaurant ouvre ses portes à 11 heures.
Trouvez:
a) la probabilité d’avoir 20 clients dans le restaurant à 11 h 12 sachant qu’il y en avait 18 à 11 h 07.
b) la probabilité qu’un nouveau client arrive entre 11 h 28 et 11 h 30 sachant que le dernier client est arrivé à 11 h 25.
F3) Des patients arrivent à une clinique selon un processus de Poisson. On dispose de l’information suivante: si X représente l’intervalle de temps écoulé entre deux arrivées successives, alors
Pr [x > 30x > 15] = 0,6
Soit N(t) le nombre de clients qui se présentent durant un intervalle de t minutes.
Calculez Pr [ N(15) = 0 ]. Justifiez votre réponse.
F4) Les articles d’un stock sont vendus selon un processus de Poisson au taux de 5 articles par jour. Le stock initial est de 80 articles.
a) Trouvez la probabilité que 10 articles soient vendus durant les 2 premiers jours.
b) Déterminez la probabilité qu’il n’y ait plus d’articles en stock après 4 jours.
c) Déterminez le nombre moyen d’articles vendus sur une période de 4 jours.
F5) Des clients se présentent à une agence de banque au rythme moyen de 10 clients par heure. Ils y sont servis par l’unique employé de l’agence, auprès duquel chaque client passe 5 minutes en moyenne. Selon les données recueillies par le directeur de l’agence, les arrivées de clients et les temps de service semblent caractéristiques de processus de Poisson.
a) Quel modèle décrit adéquatement ce système? Expliquez.
b) Estimez le temps moyen passé par chaque client dans le système.
Le directeur de l’agence décide de licencier son employé et de le remplacer par un employé plus qualité, x fois plus rapide que l’employé actuel, où x est un paramètre au moins égal à 1
c) Estimez le temps moyen passé par chaque client dans ce nouveau système.
d) Que doit valoir x pour que le temps ainsi calculé en c) soit réduit à 5 minutes?
F6) Un aéroport possède une seule piste réservée aux décollages (et une autre réservée aux atterissages). En moyenne, la tour de contrôle reçoit 15 demandes d’autorisation de décoller par heure; ces demandes surviennent selon un processus de Poisson. Par ailleurs, la durée moyenne de chaque décollage est de 3 minutes, mais varie de façon aléatoire selon une loi exponentielle (par « durée de décollage », on entend le temps écoulé entre le moment où la tour donne à un avion l’autorisation de décoller et le moment où elle peut accorder cette autorisation à un (éventuel) avion suivant).
a) Quel modèle décrit adéquatement ce système? Expliquez.
b) Estimez le nombre moyen d’avions en file d’attente, c’est-à-dire ayant demandé, mais pas encore reçu, l’autorisation de décoller.
c) Estimez le temps moyen passé par chaque avion en file d’attente (défini comme en b)).
d) Quelle est la probabilité qu’un avion qui demande l’autorisation de décoller ne reçoive pas immédiatement cette autorisation, et doive donc attendre?
e) Par mesure de sécurité, on voudrait réduire à 2 le nombre moyen d’avions gérés par la tour de contrôle (c’est-à-dire, en file d’attente ou en cours de décollage) à tout instant. A combien faut-il réduire la durée moyenne de chaque décollage pour atteindre ce but?
F7) Des voitures arrivent à un poste de péage selon un processus de Poisson avec une moyenne de 90 voitures par heure. Le temps moyen de passage à ce poste est de 38 secondes. Les automobilistes se plaignent de longues attentes à ce poste. Les autorités locales désirent alors réduire le temps de passage à 30 secondes en installant un nouveau dispositif automatique. Mais cette modification sera justifiée seulement si, sous l’ancien système, le nombre moyen de voitures dans la file dépasse 5. De plus, le pourcentage de temps creux (c’est-à-dire sans voitures) sous le nouveau système ne devrait pas excéder 10%.
Le nouveau dispositif peut-il être jusitifié?