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

View - Download Examen de recherche opérationnelle – Corrigé

Previous PDF

Next PDF

Examen de recherche op

´erationnelle - Corrig´e

Marc Roelens

D

´ecembre 2006

1 Ordonnancement de t

ˆaches

1.1

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

M

T0150930110

M

L0140930000

M

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 r

´esolution graphique.

Surcegraphique,onatrac

(solutions v

´erifiant les contraintes, en hachur´e), et une droite d"isob´en´efice (en pointill´es). La solution

optimale est le point du polytope par lequel passe une parall `ele`a la droite d"isob´en´efice qui est la plus eloign´ee possible de l"origine : ce point est le point X de la figure.

Pour d

´eterminer pr´ecis´ement ce point, on remarque qu"il est l"intersection des droites de contraintes

relatives `a B et C : c"est donc la solution du syst`eme lin´eaire : ?x1+ 2x2= 24

3x1+ 2x2= 36

qui donne comme solution optimale : x 1= 6 x 2= 9

F= 6×40 + 9×50 = 690

5 x1x2 10 20 1020
D(B) droite d'isobénéfice OX X2 X1

X'D(A)

D(C)FIG. 1 - R´esolution graphique

3.3

On va maintenant r

´esoudre le probl`eme par la m´ethode du simplexe. On sait que par cette m´ethode, on se d

´eplace sur les sommets du polytope des solutions admissibles : ainsi,`a partir du sommet O, on veut

aboutir au sommet X. Que l"on passe par X1 ou par X2, il suffit dans les deux cas de deux

´etapes, ce qui

explique pourquoi on aura trois tableaux. Voici les tableaux successifs en prenant comme crit `ere de choix de colonne celui du coefficient maximal pour la fonction

´economique.

On introduit donc 3 variables d"

´ecartyA,yBetyC(qui repr´esentent les quantit´es non utilis´ees des ingr ´edients A, B et C), et le tableau initial du simplexe s"´ecrit alors :x

1x2yAyByCy

A5 4 1 0 080

y

B120 1 024

y

C3 2 0 0 136

40 50 0 0 0F

Ce tableau correspond

`a la solution initiale (x1= 0,x2= 0,yA= 80,yB= 24,yC= 36), qui est g ´eom´etriquement repr´esent´ee par le sommet O.

Le choix du pivot se fait alors :

- en d

´eterminant la colonne o`u le coefficient est maximal dans la fonction´economique : c"est la co-

lonne dex2; - pour cette colonne, et pour chaque ligne, on calcule le quotient entre la valeur du second membre (s"il est positif) et le coefficient de la ligne (s"il est non nul) : - pour la ligneyA, on obtient le quotient804 = 20; - pour la ligneyB, on obtient le quotient242 = 12; - pour la ligneyA, on obtient le quotient362 = 18; - on retient comme pivot la valeur r

´ealisant le minimum, soit ici la ligneyB

On dit queyBsort de la baseet quex2entre dans la base. Cela signifie que l"on passe de la solution initiale

`a une nouvelle solution en se d´eplac¸ant sur l"arˆete [O;X2] : on cherche le point le plus´eloign´e sur

6 cette ar ˆete qui est donc X2. On obtient le nouveau tableau :x

1x2yAyByCy

A3 0 1-2 032

x 21
2 1 012 012 y

C20 0-1 112

15 0 0-25 0F-600

correspondant `a la nouvelle solution (x1= 0,x2= 12,yA= 32,yB= 0,yC= 12) de b´en´efice 600. Comme il reste un coefficient positif dans la fonction

´economique, ce n"est pas encore l"optimum. On

choisit

`a nouveau le pivot selon les mˆemes r`egles : c"est la colonne dex1(qui va donc entrer dans la base),

et la ligne deyC(qui va donc sortir de la base). On obtient le tableau final :x

1x2yAyByCy

A0 0 1-12

-3214 x

20 1 0

34
-149 x

11 0 0-12

126

0 0 0-352

-152F-690 correspondant `a la nouvelle solution (x1= 6,x2= 9,yA= 14,yB= 0,yC= 0) de b´en´efice 690. Comme les coefficients de la fonction ´economique sont maintenant n´egatifs, on est bien`a l"optimum (on retrouve le point X du graphique). 3.4

On peut r

´e´ecrire les´equations du probl`eme au voisinage de l"optimum trouv´e (c"est le tableau final du

simplexe!) :???? ??y

A= 14 +12

yB+32 yC x

2= 9-34

yB+14 yC x

1= 6 +12

yB-12 yC

F= 690-352

yB-152 yC

Comme on utilise toute la quantit

´e de l"ingr´edient C disponible, on peut se demander comment l"optimum va

(ε), les pivots vont rester les mˆemes, et on peut donc d´eduire la solution optimale du nouveau probl`eme`a

partir de la solution optimale de l"ancien probl `eme en affectant la valeur-ε`a la variableyC. Onlitsur le tableau final du simplexe comment vont varier les diff´erentes variables : -yAdiminue de-32 -x2diminue de-14 -x1augmente de12 -Faugmente de152

Ceci permet de calculer la valeur maximale duε: c"est celle qui provoquera l"annulation de la premi`ere

variable. Dans notre cas : -x1augmente donc ne peut s"annuler; -yAs"annule pour une valeur deεde143 2 =283 -x2s"annule pour une valeur deεde91 4 = 36.

On en d

´eduit que la valeur maximale est283

, valeur limite pour laquelle il y a alors annulation deyA. Ceci explique pourquoi l"

´enonc´e indiquait :

quotesdbs_dbs19.pdfusesText_25

[PDF] exercices corrigés recherche opérationnelle s5

[PDF] exercices corrigés repère dans le plan

[PDF] exercices corrigés repère dans le plan 3ème

[PDF] exercices corrigés repère dans le plan pdf

[PDF] exercices corrigés représentation de newman

[PDF] exercices corrigés sciences physiques premiere s

[PDF] exercices corrigés semi conducteurs pdf

[PDF] exercices corrigés statique des fluides pdf

[PDF] exercices corrigés statique pfs

[PDF] exercices corrigés statistique

[PDF] exercices corrigés statistique descriptive

[PDF] exercices corrigés statistique terminale pdf

[PDF] exercices corrigés sur acide faible/ base faible pdf

[PDF] exercices corrigés sur amplificateur d'instrumentation

[PDF] exercices corrigés sur architecture des ordinateurs