Examen de recherche operationnelle

[PDF] cours de recherche operationnelle gratuit pdf

[PDF] programmation linéaire exercices corrigés simplex

[PDF] examen recherche opérationnelle corrigé

[PDF] exercice corrigé methode simplexe pdf

[PDF] multiples et sous multiples physique

[PDF] multiples et sous multiples physique exercices

[PDF] multiples et sous multiples du gramme

[PDF] multiple et sous multiple exercice

[PDF] multiples et sous multiples du litre

[PDF] multiplicateur fiscal formule

[PDF] multiplicateur fiscal macroéconomie

[PDF] cobb douglas explication

[PDF] revenu d'équilibre formule

[PDF] multiplicateur des dépenses publiques macroéconomi

[PDF] fonction de cobb douglas pdf

Examen de recherche op

´erationnelle - Corrig´e

Marc Roelens

´ecembre 2006

1 Ordonnancement de t

ˆaches

1.1

On dresse le tableau des contraintes de pr

´ec´edence :T

ˆacheABCDEFGHIJ

´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

´ec.JHA, HA, BC, IDD, F

Niv.2300304211

N o68129310745

Comme 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 G

Déb

Fin niveau 0 niveau 2 niveau 3 niveau 1 B1 1.2

On 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 H

EGDébFin

10108
4 5 5 1 2105
5 3

70,00,5

0,38,9

5,6

5,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.3

Le 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

T0150930110

L0140930000

C0040930000

2 1.4

On 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.1

On 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=n

C"est donc un probl

`eme de programmation dynamique. 2.2 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

choisit bien s ˆur la valeur dexjqui maximise la somme des b´en´efices obtenus. En clair : 2.3 D"apr dynamique.

En regardant plus attentivement la formule de r

´ecurrence, on constate que pour calculerP(i,j), on a besoin de conna seul tableau pour calculer les valeurs deP: pour i allant de 0 `a n

P(i) = b(i,1)

pour j allant de 2 `a m pour i allant de n `a 0 kmin = 0; vkmin = P(i)+b(0,j) pour k allant de 0 `a i 3 vk = P(i-k)+b(k,j) si vk est sup

´erieur`a vkmin

kmin = k; vk = vkmin finsi finpour(k)

P(i,j) = vkmin

finpour(i) finpour(j) afficher P(n,m)

Cet algorithme permet de d

´eterminerP(n,m)(d"ailleurs, dans la derni`ere boucle, il n"est pas n´ecessaire

de calculerP(i,m)pouri < n!) : on souhaite´egalement conserver la r´epartition correspondante! Il suffit

pour cela de m ´emoriser les valeurs de vkmin en cours d"algorithme. En termes de complexit´e, on a ainsi : - une complexit

´e en espace proportionnelle`an×m(on conserve pour toutile b´en´efice et la r´epartition

optimale, de taillem); - une complexit ´e proportionnelle`an2×m(voir les trois boucles imbriqu´ees de l"algorithme). 2.4

Voici l"algorithme d

´etaill´e sur l"exemple :

- calcul de P(6,2) : on d

´etermine les r´epartitions possibles

- 0 cageots sur le magasin 2, 6 sur le premier magasin : 0 + 4 = 4 - 1 cageots sur le magasin 2, 5 sur le premier magasin : 4 + 4 = 8 - 2 cageots sur le magasin 2, 4 sur le premier magasin : 6 + 4 = 10 - 3 cageots sur le magasin 2, 3 sur le premier magasin : 7 + 4 = 11 - 4 cageots sur le magasin 2, 2 sur le premier magasin : 8 + 4 = 12 - 5 cageots sur le magasin 2, 1 sur le premier magasin : 8 + 3 = 11 - 6 cageots sur le magasin 2, 0 sur le premier magasin : 8 + 0 = 8

P(6,2) = 12, r

´epartition optimale 2+4

- calcul de P(5,2) : on d

´etermine les r´epartitions possibles

- 0 cageots sur le magasin 2, 5 sur le premier magasin : 0 + 4 = 4 - 1 cageots sur le magasin 2, 4 sur le premier magasin : 4 + 4 = 8 - 2 cageots sur le magasin 2, 3 sur le premier magasin : 6 + 4 = 10 - 3 cageots sur le magasin 2, 2 sur le premier magasin : 7 + 4 = 11 - 4 cageots sur le magasin 2, 1 sur le premier magasin : 8 + 3 = 11 - 5 cageots sur le magasin 2, 0 sur le premier magasin : 8 + 0 = 8

P(5,2) = 11, r

´epartition optimale 2+3

- calcul de P(4,2) : on d

´etermine les r´epartitions possibles

- 0 cageots sur le magasin 2, 4 sur le premier magasin : 0 + 4 = 4 - 1 cageots sur le magasin 2, 3 sur le premier magasin : 4 + 4 = 8 - 2 cageots sur le magasin 2, 2 sur le premier magasin : 6 + 4 = 10 - 3 cageots sur le magasin 2, 1 sur le premier magasin : 7 + 3 = 10 - 4 cageots sur le magasin 2, 0 sur le premier magasin : 8 + 0 = 8

P(4,2) = 10, r

´epartition optimale 2+2

- calcul de P(3,2) : on d

´etermine les r´epartitions possibles

- 0 cageots sur le magasin 2, 3 sur le premier magasin : 0 + 4 = 4 - 1 cageots sur le magasin 2, 2 sur le premier magasin : 4 + 4 = 8 - 2 cageots sur le magasin 2, 1 sur le premier magasin : 6 + 3 = 9 - 3 cageots sur le magasin 2, 0 sur le premier magasin : 7 + 0 = 7

P(3,2) = 9, r

´epartition optimale 1+2

- calcul de P(2,2) : on d

´etermine les r´epartitions possibles

- 0 cageots sur le magasin 2, 2 sur le premier magasin : 0 + 4 = 4 - 1 cageots sur le magasin 2, 1 sur le premier magasin : 4 + 3 = 7 - 2 cageots sur le magasin 2, 2 sur le premier magasin : 6 + 0 = 6 4

P(2,2) = 7, r

´epartition optimale 1+1

- calcul de P(1,2) : on d

´etermine les r´epartitions possibles

- 0 cageots sur le magasin 2, 1 sur le premier magasin : 0 + 3 = 3 - 1 cageots sur le magasin 2, 0 sur le premier magasin : 4 + 0 = 4

P(1,2) = 4, r

´epartition optimale 0+1

- calcul de P(0,2) : on d

´etermine les r´epartitions possibles

- 0 cageots sur le magasin 2, 0 sur le premier magasin : 0 + 0 = 0

P(0,2) = 0, r

´epartition optimale 0+0

- calcul de P(6,3) : on d

´etermine les r´epartitions possibles

- 0 cageots sur le magasin 3, 6 sur les deux premiers magasins : 0 + 12 = 12 - 1 cageots sur le magasin 3, 5 sur les deux premiers magasins : 2 + 11 = 13 - 2 cageots sur le magasin 3, 4 sur les deux premiers magasins : 4 + 10 = 14 - 3 cageots sur le magasin 3, 3 sur les deux premiers magasins : 6 + 9 = 15 - 4 cageots sur le magasin 3, 2 sur les deux premiers magasins : 7 + 7 = 14 - 5 cageots sur le magasin 3, 1 sur les deux premiers magasins : 8 + 4 = 12 - 6 cageots sur le magasin 3, 0 sur les deux premiers magasins : 9 + 0 = 9

P(6,3) = 15, r

´epartition optimale 1+2+3

Ainsi, le grossiste doit placer 1 cageot dans le premier magasin, 2 dans le second magasin, 3 dans le

troisi `eme magasin : son b´en´efice (maximal) est de 15.

3 Production

`a optimiser 3.1 On notex1etx2les quantit´es de produitsP1etP2. Ainsi, on cherche`a maximiser le produit de la vente, c"est- `a-dire la quantit´e :

F(x1,x2) = 40x1+ 50x2

sachant que l"on doit bien s ˆur respecter les contraintes de stock des ingr´edients A, B et C : x

On a affaire

`a un (classique) probl`eme de programmation lin´eaire. 3.2

Comme on n"a que deux variables, une r

´esolution graphique (planaire) est donc possible. La figure 1 reprend cette rquotesdbs_dbs5.pdfusesText_9

[PDF] Examen de recherche operationnelle – Corrig´ e´