Recherche Opérationnelle - FSTM
[PDF] Recherche Opérationnelle FSTM fstm ac ma deptmath Cours Rech Operat pdf
Simplexe - Méthodes, Techniques et Outils pour le Raisonnement
[PDF] Simplexe Méthodes, Techniques et Outils pour le Raisonnementdossier univ st etienne pem public simplexeSlides pdf
Recherche opérationnelle - LMPA
[PDF] Recherche opérationnelle LMPA lmpa univ littoral recherche operationnelle chap pdf
maximiser 100 sous les contraintes Remarque : en toute - Cnam
[PDF] maximiser sous les contraintes Remarque en toute Cnam deptmedia cnam new spip php?pdoc
174 EXERCICES SUPPLÉMENTAIRES #8212; PARTIE II
[PDF] EXERCICES SUPPLÉMENTAIRES PARTIE II dmi usherb ca ~dussault RennesOptim OPTChap pdf
Examen de recherche opérationnelle #8211; Corrigé
[PDF] Examen de recherche opérationnelle Corrigékiwi emse POLE SDA corrige exam ro pdf
Recherche Opérationnelle - FSR
[PDF] Recherche Opérationnelle FSR fsr ac ma cours maths RO SMI Etudiants pdf
Graphes et Recherche Opérationnelle - IECL
[PDF] Graphes et Recherche Opérationnelle IECL iecl univ lorraine ~Jean Francois Scheid coursRO pdf
Mathématiques #8211; Recherche Opérationnelle - Ensiie
[PDF] Mathématiques Recherche Opérationnelle Ensiie ensiie ~billionnet Notes de cours
[PDF] exercices corrigés de structure de la matière et des liaisons chimiques
[PDF] exercices corrigés déplacement et antidéplacement pdf
[PDF] exercices corrigés déterminant d'une matrice
[PDF] exercices corrigés en algorithmique pdf prémière année
[PDF] exercices corrigés en théorie de la mesure et de l'intégration pdf
[PDF] exercices corrigés enthalpie réaction
[PDF] exercices corrigés géométrie dans l'espace seconde pdf
[PDF] exercices corrigés géométrie dans l'espace terminale s pdf
[PDF] exercices corrigés graphes
[PDF] exercices corrigés graphes terminale es
[PDF] exercices corrigés grh pdf
[PDF] exercices corrigés hacheur pdf
[PDF] exercices corrigés impot sur les sociétés maroc
[PDF] exercices corrigés logarithme népérien terminale es
Examen de recherche op
´erationnelle - Corrig´e
Marc Roelens
D´ecembre 2006
1 Ordonnancement de t
ˆaches
1.1On dresse le tableau des contraintes de pr
´ec´edence :T
ˆacheABCDEFGHIJ
Pr´ec.JHA, HA, BC, IDD, F
On d´etermine successivement :
- les tˆaches de niveau 0 (celles qui n"ont pas d"ant´ec´edent) : ce sont C, D et F (que l"on peut num´eroter
dans cet ordre); - les tˆaches de niveau 1 (celles qui n"ont que des ant´ec´edents de niveau 0) : ce sont I et J (que l"on
num´erote dans cet ordre);
- les tˆaches de niveau 2 (celles qui n"ont que des ant´ec´edents de niveau 0 ou 1) : ce sont A et H (que
l"on num´erote dans cet ordre);
- les tˆaches de niveau 3 (celles qui n"ont que des ant´ec´edents de niveau 0, 1 ou 2) : ce sont B et E (que
l"on num´erote dans cet ordre);
- les tˆaches de niveau 4 (celles qui n"ont que des ant´ec´edents de niveau 0, 1, 2 ou 3) : il ne reste plus
que G!Voici donc le tableau des t
ˆaches avec niveau et num´ero d"ordre :T
ˆacheABCDEFGHIJ
Pr´ec.JHA, HA, BC, IDD, F
Niv.2300304211
N o68129310745Comme on a r
´eussi`a num´eroter tous les sommets, c"est que le graphe de pr´ec´edence est sans circuit, et la
num´erotation des sommets constitue un tri topologique (si la tˆache X est avant la tˆache Y, alors le num´ero
de X est inf´erieur au num´ero de Y).
Une repr
´esentation par niveau possible pour ce graphe est la suivante (on a ajout´e des tˆaches fictives
correspondant au d´ebut et`a la fin des travaux) :niveau 4
CDF IJ AH E GDéb
Fin niveau 0 niveau 2 niveau 3 niveau 1 B1 1.2On porte sur chaque arc du graphe de pr
´ec´edence la dur´ee de la tˆache dont cet arc est issu, et on sait que l"on calcule la date de d ´ebut au plus tˆot en d´eterminant le chemin le plus long depuis le d´ebut des travaux; ceci permet de trouver la dur ´ee minimale d"ex´ecution qui est la date de d´ebut au plus tˆot de la tˆache fictive repr´esentant la fin des travaux.
Ensuite, on d
´etermine la date de d´ebut au plus tard en calculant le chemin le plus long depuis chaque sommet jusqu" `a cette tˆache fictive de fin des travaux.Comme le graphe est ordonn
´e par niveaux, ces calculs se font par niveaux croissants pour les dates de d´ebut au plus tˆot, par niveaux d´ecroissants pour les dates de d´ebut au plus tard. Le r´esultat est r´esum´e sur
le graphe suivant :32,32C D F I JA HEGDébFin
101084 5 5 1 2105
5 3
70,00,5
0,38,9
5,65,5 12,1213,1422,31 22,22
BLes dates de d
´ebut au plus tˆot et au plus tard sont indiqu´ees (s´epar´ees par des virgules) au dessus des tˆaches.
On obtient ainsi les r
´eponses :
- la dur ´ee minimale d"ex´ecution est de 32 unit´es; - le chemin critique est D 1.3Le graphe PERT est d
´ecrit ci-apr`es : il comprend 8´etapes et deux tˆaches fictives (en pointill´es), de dur ´ees nulles, servant`a repr´esenter les contraintes de pr´ec´edence. [32,32]H (5) B (8)
G (10)
A (10) E (1)J (7)C (4)
D (5)F (2)I (3)
[12,12][8,9] [5,5] [0,0][13,14] [22,22][22,22]Pour chaque´etape, on a indiqu´e la date au plus tˆot et la date au plus tard (entre crochets). Le chemin critique
est (heureusement!) le m ˆeme que celui calcul´e par le graphe de pr´ec´edence. On peut alors calculer les marges libres, totales et certaines, dont on rappelle la d´efinition. Pour toute
etapeei, on notetila date au plus tˆot de cette´etape, ett?ila date au plus tard. Alors, pour une tˆacheXjde
dur ´eedj, comprise entre l"´etapek(avant) et l"´etapel(apr`es), on d´efinit : -MT(Xj) =t?l-tk-dj(marge totale deXj); -ML(Xj) =tl-tk-dj(marge libre deXj); -MC(Xj) =tl-t?k-dj(marge certaine deXj).On obtient les r
´esultats suivants :T
ˆacheABCDEFGHIJ
MT0150930110
ML0140930000
MC0040930000
2 1.4On voit sur le tableau pr
´ec´edent que la marge totale de H est de 1 unit´e : donc, l"augmentation de 1 unit´e de la dur´ee de H va r´esorber cette marge (sans pour autant d´ecaler la fin du projet). Si H augmente`a
nouveau de 1 unit ´e, alors on obtient un nouveau chemin critique D et la dur ´ee minimale d"ex´ecution du projet passe`a 33 unit´es de temps.2 Allocation de ressources
2.1On note doncxjla quantit´e de cageots plac´ee dans le magasinj. Ces variablesxjsont enti`eres, posi-
tives, inf ´erieures`a la valeurn. Le b´en´efice global (que l"on cherche`a maximiser) est donc :F(x1,···,xm) =m?
j=1b(xj,j) en respectant bien s ˆur la contrainte que le nombre total de cageots estn, c"est-`a-dire : m j=1x j=nC"est donc un probl
`eme de programmation dynamique. 2.2On note alors, pour0≤i≤net0≤j≤m,P(i,j)le profit maximum obtenu en vendanticageots
dans lesjpremiers magasins. On a bien´evidemment : (?i? {0..n})(P(i,1) =b(i,1))Ensuite, pourj≥2, pour placer optimalementicageots dans lesjpremiers magasins, on peut dire l"on
placexj≤icageots dans le magasinjeti-xjde fac¸on optimale dans lesj-1premiers magasins. On choisit bien s ˆur la valeur dexjqui maximise la somme des b´en´efices obtenus. En clair :