[PDF] Optimisation et Recherche opérationelle Exercice 1

Corrigé de l'examen de la session normale Recherche opérationnelle Semestre 6 Filière Economie et Gestion Ensembles : 2 et 3 M ATMANI Exercice 1

[PDF] Examen de recherche opérationnelle – Corrigé

Examen de recherche opérationnelle – Corrigé Marc Roelens Décembre 2006 1 Ordonnancement de tâches 1 1 On dresse le tableau des contraintes de

[PDF] Correction de lExamen de Recherche Opérationnelle Session

Les matières premières sont en quantité limitée : 90 Kg (Kilogrammes) de fraises 60 Kg de lait et 30 Kg de sucre La vente du yaourt A rapporte 40 Dh

[PDF] Examen de Recherche Opérationnelle Filière : SMI-5 Durée : 2h

Examen de Recherche Opérationnelle – Filière SMI 5 Session normale Page 1 / 4 Lire tout l'énoncé de l'examen avant de commencer à répondre

[PDF] EXAMEN DE RECHERCHE OPÉRATIONNELLE

EXAMEN DE RECHERCHE OPÉRATIONNELLE CET EXAMEN CONTIENT UNE PAGE Exercice I 1) Citer trois exemples d'application de la recherche opérationnelle

[PDF] Corrigé de lExamen de Rattrapage de Programmation Linéaire

Département de Recherche Opérationnelle Année Universitaire 2015-2016 Corrigé de l'Examen de Rattrapage de Programmation Linéaire

[PDF] Université A MIRA de Béjaia Licence Faculté des Sciences Exactes

Département de Recherche Opérationnelle Année Universitaire 2014-2015 Corrigé de l'Examen de Programmation Linéaire Exercice 1 (6 points ) Considérons le

[PDF] Exercice corrigé recherche opérationnelle pdf

d'examen de la recherche Queuing opérationnelle? Foire Le tableau de PERT est décrit ci-dessous: 8 comprend des étapes et deux tâches factices (en

[PDF] Recherche Opérationnelle: - Loria

Recherche Opérationnelle: Notes de cours et exercices corrigés Frédéric SUR 2 6 1 L'anatomie d'un moteur de recherche (examen 2010-2011) 35

[PDF] Optimisation et Recherche opérationelle Exercice 1 - CNRS

Examen Final Nom: Prenom: Numéro étudiant: — Durée de l'examen : 1h30 — Document autorisé : une feuille de notes A4 recto-verso — Cet examen comporte

Optimisation et Recherche opérationelleJanvier 2018

Examen Final

Nom: Prenom: Numéro étudiant:-Durée de l"examen : 1h30 Do cumentautorisé : une feuille de notes A4 rec to-verso Cet examen comp ortetrois exercices indép endantsp ouvantêtre traités dans n"imp ortequel ordre. Les deux premiers sont assez courts tandis que le dernier est un problème comportant trois parties indépendantes elles-aussi.

L"énoncé est à rendre a vecla copie, n"oublier pas d"indiquer v osnoms et prénoms sur toutes

les feuilles. T outesles rép onsesdoiv entêtre justifiées.

Le barème donné est indicatif.

Exercice1:Question de cours(2 pts)

Donner le nom de trois algorithmes métaheuristiques vus en cours. Parmi ceux-ci, lesquels sont proba-

bilistes? déterministes? Justifier.

Exercice2:Flots(4.5 pts)

Question 1.(2 pts)Le flot suivant est-il complet? Est-il maximal?

Justifiez vos réponses et si le flot n"est pas maximal, augmentez-le jusqu"à obtenir un flot maximal, et

donnez sa valeur. Vous pouvez décrire le flot maximal sur la feuille directement (qui sera à rendre),

mais votre réponse devra dans tous les cas être justifiée.s1 2 34
5 6p3/5 4/4

2/52/21/10/4

4/4 2/6

2/43/33/4

2/6

4/40/5

Question 2.(1 pt)Donner une coupe minimale.

Question 3.(1,5 pt)On souhaite désormais augmenter le flot total, et pour cela, nous avons la

possibilité d"augmenter la capacité de l"arc(2;5). Cet arc est-il actuellement limitant (càd qu"une

augmentation de sa capacité permettrait d"augmenter le flot total)? Si oui, quel est la plus petite

valeur de capacité entière qu"on peut donner à l"arc(2;5)pour qu"il ne soit plus limitant? Dans ce cas,

donnez la nouvelle valeur du flot. Justifiez toutes vos réponses. 1 Exercice3:(15.5 pts)Les différentes parties de ce problème sont indépendantes et peuvent

être traitées dans n"importe quel ordre. Vous pouvez aussi admettre une question pour répondre à

la suivante.

L"entreprise Regeot fabrique des voitures. Pour fabriquer les différents pièces, elle se pose plusieurs

problèmes d"ordonnancement. Partie I : Une machine avec un temps de maintenance(4.5 pts)

Dans un premier temps, on considère une seule machine qui doit fabriquernpièces différentes dont

la durée de fabrication varie. On noteradila durée de fabrication de la piècei. Une opération de

maintenance est prévue à une date fixetMet pendant une duréedM. Pendant la maintenance,

aucune pièce ne peut être fabriquée et l"on ne peut pas interrompre la fabrication d"une pièce

au moment de la maintenance. On cherche à minimiser le temps final où toutes les pièces seront

fabriquées. On considèrera que la fabrication des pièces commence à la datet0= 0. Pour mieux comprendre le problème, voilà un exemple avecn= 5,tM= 35etdM= 4. Les pièces à usiner ont les durées suivantes :Pièces12345

Duréedi27131729

Un ordonnancement possible avec comme temps final81est le suivant (sur le dessin, M désigne la période de maintenance) :P

102MachineP

4193981Temps263552P

2P 3P 5M

Question 1.(1,5 pt)Modéliser ce problème sous forme d"un PLNE. On pourra remarquer qu"il suffit

de décider pour chaque pièce si elle est effectuée avant ou après la maintenance.

On propose de résoudre ce problème avec le principe de programmation dynamique. Plutôt que de

minimiser le temps final d"éxécution on va résoudre le problème équivalent consistant à maximer le

temps de tâches effectuées avant la pause de maintenance. On pose doncf(i;k)le temps maximal

de travail qui peut être fait pendant une durée inférieure àken fabriquant des pièces parmi les

pièces 1 ài.

Le tableau suivant donne quelques valeurs def(i;k)pour les données de l"exemple précédent. Par

exemple,f(4;18) = 17signifie que le temps maximal de travail qui peut être fait avec les tâches 1

à 4 sans dépasser 18 unités de temps est au maximum 17 (en l"occurence, atteint avec la tâche 4

seule).ink0123456:::18:::29303132333435

1 (d1= 2)0022222:::2:::2222222

2 (d2= 7)0022222:::9:::9999999

3 (d3= 13)0022222:::15:::22222222222222

4 (d4= 17)0022222:::17:::26303032323232

5 (d5= 29)0022222:::17:::

Question 2.(0,5 pt)Pour quelles valeurs deietk, le calcul def(i;k)résoud notre problème? Question 3.(1 pt)Donner une relation de récurrence pourf(i;k)utilisantf(i1;k)etf(i1;kdi). Question 4.(1,5 pt)Compléter le tableau (pouri= 5et29k35) et en déduire une solution optimale pour le problème initial. 2 Partie II : Usinage de pièces surmmachines avec des précédences(7 pts)

Dans cette partie, l"entreprise doit toujours fabriquernpièces mais dispose cette fois demmachines

identiques. Les pièces doivent être réalisées en une seule fois sur une seule machine mais peuvent

être réalisées indifférement sur l"une ou l"autre des machines. On cherche encore à minimiser le

temps nécessaire pour que toutes les pièces soient fabriquées. Pour chaque pièceP, on noted(P)

la durée de fabrication de la pièceP. On noteraPl"ensemble des pièces.

Question 5.(1 pt)Rappeler la complexité algorithmique de ce problème. Existe-t-il un algorithme

d"approximation, si oui, avec quel facteur?

En fait, certaines pièces ont besoin que d"autres pièces soient finies pour pouvoir être fabriquées

(mais pas nécessairement sur la même machine). Dans la suite de cette partie, on considèrera

l"exemple suivant sur trois machines :PièceDuréePrécédences A3 B2 C3 D4 E7A F2D G3A,D

H3B,C,D

I2G,H

J4D,G,H

Question 6.(1 pt)Donner l"ordonnancement obtenu sur 3 machines en suivant l"algorithme de liste

avec la listefA;B;C;D;:::g. Pour rappel, cela consiste à éxécuter au tempst(en partant àt= 0, la

plus petite tâche disponible selon l"ordre donné par la liste. Nous allons montrer que n"importe quel algorithme de liste fournit un algorithme d"approximation avec un facteur21=mde l"optimal. SoitIune instance quelconque de notre problème. Soit opt(I)le temps minimal que l"on peut obtenir parmi tous les ordonnancements possibles etsol(I)

la solution donnée par un algorithme de liste quelconque. SoitP`la pièce dont la fabrication se

termine en dernière. On notet(P`)la date à laquelle la pièce a commencée à être fabriquée etd(P`)

sa durée. Question 7.(0,5 pt)Exprimersol(I)en fonction det(P`)etd(P`).

SoitP`1la pièce qui est terminée en dernière parmi toutes les pièces qui doivent être faites avant

`. De la même manière, on définitP`2,...,PsavecPiqui est la pièce terminée en dernière parmi

toutes les pièces qui doivent être faites avantPi+1etPsqui n"a aucune pièce qui doit être finie

avant elle. Il y a ainsi une chaîne de dépendancesPs!Ps+1:::!P`. Question 8.(0,5 pt)Sur l"ordonnancement obtenu à la question 6, donner les noms des pièces correspondant àP`,P`1,...,Ps.

Question 9.(1 pt)Montrer queP`

i=sd(Pi)opt(I)etP

P2Pd(P)mopt(I).

Question 10.(1 pt)Expliquer pourquoi entre les datest(Pi)+d(Pi)ett(Pi+1)(pouri2 fs;:::;`1g),

ainsi qu"avant la datet(Ps)toutes les machines sont occupées, et occupées à d"autres tâches que les

tâches de la chaînePs;:::;P`. En déduire l"inégalité suivante : m t(Ps) +`1X i=s[t(Pi+1)(t(Pi) +d(Pi))]! X

P2Pd(P)`X

i=sd(Pi) Question 11.(1 pt)En utilisant les questions 7,9 et 10, en déduire que l"on a bien une(21=m)- approximation, c"est-à-dire quesol(I)(21=m)opt(I). Question 12.(1 pt)Donner un exemple général surmmachines où le facteur21=mest atteint. 3 Partie III : Ordonnancement sur 2 machines de tâches séquentielles(4 pts)

Dans cette partie, l"entreprise doit usinernpièces qui doivent être fabriquée par deux machines,A

etBséquentiellement : d"abord sur la machineMApuis sur la machineMB. Une fois l"ordre choisi

sur la machineA,les pièces doivent être réalisées suivant le même ordre sur la machine

B. On dispose comme données des durées de fabricationdA(Pi)etdB(Pi)de chaque piècePisur

les deux machines. Encore une fois, le but est de minimiser le temps final où toutes les pièces sont

éxécutées.

Voilà un exemple de données. En usinant les pièces dans l"ordre 2,1,3 on obtient un ordonnancement

qui termine à la date 16.Pièces123

DuréedA324

DuréedB147P

202MachineAMachineBP

1P 2P 1P 3P

35916Temps

Question 13.(1 pt)Cette solution est-elle optimale? Justifiez pourquoi. L"algorithme de Johnson fournit un algorithme polynomial pour ce problème. Il procède ainsi : 1. Soit Sl"ensemble des piècesPitelles quedA(Pi)dB(Pi). 2.

Soit Tles autres pièces.

3. Ordonnancer les piè cesdans l"ordre suiv ant: d"ab ordles p iècesde SpardAcroissante, puis les pièces deTpardBdécroissante. Question 14.(1.5 pt)Appliquer cet algorithme sur l"instance suivante. On donnera les ensemblesS etTet l"ordonnancement final obtenu.Pièces12345

DuréedA41352

DuréedB13233

Pour justifier son algorithme, Johnson a prouvé que pour obtenir l"ordonnancement optimal, il suffit de mettre la piècePiavant la piècePjsi l"inégalité suivante est vérifiée min(dA(Pi);dB(Pj))min(dB(Pi);dA(Pj))(1) Question 15.(1.5 pts)Montrer que, pour une instance quelconque, l"ordonnancement obtenu avec

l"algorithme de Johnson vérifie bien cette propriété. C"est-à-dire que pour toutes piècesPietPjl"in-

égalité (1) est vérifiée. On pourra séparer les cas suivant siPietPjsont tous les deux dansSou bien

tous les deux dansTou bien un dans chaque ensemble. 4quotesdbs_dbs4.pdfusesText_7

[PDF] [PDF] Optimisation et Recherche opérationelle Exercice 1 - CNRS

[PDF] Examens avec Solutions Recherche opérationnelle - fsjes ain chock