Examen de recherche operationnelle – Corrige

Marc Roelens

Decembre 2006

1 Ordonnancement de taches

1.1On dresse le tableau des contraintes de precedence :

Tache A B C D E F G H I JPrec. J H A, H A, B C, I D D, F

On determine successivement :– les taches de niveau 0 (celles qui n’ont pas d’antecedent) : ce sont C, D et F (que l’on peut numeroter

dans cet ordre) ;– les taches de niveau 1 (celles qui n’ont que des antecedents de niveau 0) : ce sont I et J (que l’on

numerote dans cet ordre) ;– les taches de niveau 2 (celles qui n’ont que des antecedents de niveau 0 ou 1) : ce sont A et H (que

l’on numerote dans cet ordre) ;– les taches de niveau 3 (celles qui n’ont que des antecedents de niveau 0, 1 ou 2) : ce sont B et E (que

l’on numerote dans cet ordre) ;– les taches de niveau 4 (celles qui n’ont que des antecedents de niveau 0, 1, 2 ou 3) : il ne reste plus

que G !Voici donc le tableau des taches avec niveau et numero d’ordre :

Tache A B C D E F G H I JPrec. J H A, H A, B C, I D D, FNiv. 2 3 0 0 3 0 4 2 1 1No 6 8 1 2 9 3 10 7 4 5

Comme on a reussi a numeroter tous les sommets, c’est que le graphe de precedence est sans circuit, et lanumerotation des sommets constitue un tri topologique (si la tache X est avant la tache Y, alors le numerode X est inferieur au numero de Y).

Une representation par niveau possible pour ce graphe est la suivante (on a ajoute des taches fictivescorrespondant au debut et a la fin des travaux) :

niveau 4

C

D

F

I

J A

H

E GDéb Fin

niveau 0 niveau 2 niveau 3niveau 1

B

1

1.2On porte sur chaque arc du graphe de precedence la duree de la tache dont cet arc est issu, et on sait que

l’on calcule la date de debut au plus tot en determinant le chemin le plus long depuis le debut des travaux ;ceci permet de trouver la duree minimale d’execution qui est la date de debut au plus tot de la tache fictiverepresentant la fin des travaux.

Ensuite, on determine la date de debut au plus tard en calculant le chemin le plus long depuis chaquesommet jusqu’a cette tache fictive de fin des travaux.

Comme le graphe est ordonne par niveaux, ces calculs se font par niveaux croissants pour les dates dedebut au plus tot, par niveaux decroissants pour les dates de debut au plus tard. Le resultat est resume surle graphe suivant :

32,32

C

D

F

I

J A

H

E GDéb Fin

1010

8

4

5

51

2

10

5

5

3

7

0,0

0,5

0,3

8,9

5,6

5,5 12,12

13,14

22,31 22,22

B

Les dates de debut au plus tot et au plus tard sont indiquees (separees par des virgules) au dessus des taches.On obtient ainsi les reponses :

– la duree minimale d’execution est de 32 unites ;– le chemin critique est

Deb −→ D −→ J −→ A −→ G −→ Fin

1.3Le graphe PERT est decrit ci-apres : il comprend 8 etapes et deux taches fictives (en pointilles), de

durees nulles, servant a representer les contraintes de precedence.

[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 indique la date au plus tot et la date au plus tard (entre crochets). Le chemin critiqueest (heureusement !) le meme que celui calcule par le graphe de precedence.

On peut alors calculer les marges libres, totales et certaines, dont on rappelle la definition. Pour touteetape ei, on note ti la date au plus tot de cette etape, et t∗i la date au plus tard. Alors, pour une tache Xj deduree dj , comprise entre l’etape k (avant) et l’etape l (apres), on definit :

– MT (Xj) = t∗l − tk − dj (marge totale de Xj) ;– ML(Xj) = tl − tk − dj (marge libre de Xj) ;– MC(Xj) = tl − t∗k − dj (marge certaine de Xj).

On obtient les resultats suivants :

Tache A B C D E F G H I JMT 0 1 5 0 9 3 0 1 1 0ML 0 1 4 0 9 3 0 0 0 0MC 0 0 4 0 9 3 0 0 0 0

2

1.4On voit sur le tableau precedent que la marge totale de H est de 1 unite : donc, l’augmentation de 1

unite de la duree de H va resorber cette marge (sans pour autant decaler la fin du projet). Si H augmente anouveau de 1 unite, alors on obtient un nouveau chemin critique

Deb −→ D −→ I −→ H −→ B −→ G −→ Fin

et la duree minimale d’execution du projet passe a 33 unites de temps.

2 Allocation de ressources

2.1On note donc xj la quantite de cageots placee dans le magasin j. Ces variables xj sont entieres, posi-

tives, inferieures a la valeur n. Le benefice global (que l’on cherche a maximiser) est donc :

F (x1, · · · , xm) =m∑

j=1

b(xj , j)

en respectant bien sur la contrainte que le nombre total de cageots est n, c’est-a-dire :

m∑j=1

xj = n

C’est donc un probleme de programmation dynamique.

2.2On note alors, pour 0 ≤ i ≤ n et 0 ≤ j ≤ m, P (i, j) le profit maximum obtenu en vendant i cageots

dans les j premiers magasins. On a bien evidemment :

(∀i ∈ {0..n})(P (i, 1) = b(i, 1))

Ensuite, pour j ≥ 2, pour placer optimalement i cageots dans les j premiers magasins, on peut dire l’onplace xj ≤ i cageots dans le magasin j et i− xj de facon optimale dans les j − 1 premiers magasins. Onchoisit bien sur la valeur de xj qui maximise la somme des benefices obtenus. En clair :

P (i, j) = max0≤xj≤i

b(xj , j) + P (i− xj , j − 1)

2.3D’apres ce que l’on vient de demontrer, on connaıt les valeurs de P (i, 1) pour 0 ≤ i ≤ n (identiques

aux b(i, 1)). Puis, on peut calculer grace a la propriete P (i, 2) pour 0 ≤ i ≤ n, . . .puis P (i, j − 1) pour0 ≤ i ≤ n, et enfin ce que l’on cherche : P (n, m). On a affaire a un algorithme classique de programmationdynamique.

En regardant plus attentivement la formule de recurrence, on constate que pour calculer P (i, j), on abesoin de connaıtre uniquement les valeurs de P (k, j− 1) pour 0 ≤ k ≤ i. Ceci permet de n’utiliser qu’unseul tableau pour calculer les valeurs de P :

pour i allant de 0 a nP(i) = b(i,1)

pour j allant de 2 a mpour 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 superieur a vkmin

kmin = k ; vk = vkminfinsi

finpour(k)P(i,j) = vkmin

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

Cet algorithme permet de determiner P (n, m) (d’ailleurs, dans la derniere boucle, il n’est pas necessairede calculer P (i, m) pour i < n !) : on souhaite egalement conserver la repartition correspondante ! Il suffitpour cela de memoriser les valeurs de vkmin en cours d’algorithme. En termes de complexite, on a ainsi :

– une complexite en espace proportionnelle a n×m (on conserve pour tout i le benefice et la repartitionoptimale, de taille m) ;

– une complexite proportionnelle a n2 ×m (voir les trois boucles imbriquees de l’algorithme).

2.4Voici l’algorithme detaille sur l’exemple :– calcul de P(6,2) : on determine les repartitions 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 = 8P(6,2) = 12, repartition optimale 2+4

– calcul de P(5,2) : on determine les repartitions 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 = 8P(5,2) = 11, repartition optimale 2+3

– calcul de P(4,2) : on determine les repartitions 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 = 8P(4,2) = 10, repartition optimale 2+2

– calcul de P(3,2) : on determine les repartitions 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 = 7P(3,2) = 9, repartition optimale 1+2

– calcul de P(2,2) : on determine les repartitions 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, repartition optimale 1+1– calcul de P(1,2) : on determine les repartitions 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 = 4P(1,2) = 4, repartition optimale 0+1

– calcul de P(0,2) : on determine les repartitions possibles– 0 cageots sur le magasin 2, 0 sur le premier magasin : 0 + 0 = 0P(0,2) = 0, repartition optimale 0+0

– calcul de P(6,3) : on determine les repartitions 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 = 9P(6,3) = 15, repartition optimale 1+2+3

Ainsi, le grossiste doit placer 1 cageot dans le premier magasin, 2 dans le second magasin, 3 dans letroisieme magasin : son benefice (maximal) est de 15.

3 Production a optimiser

3.1On note x1 et x2 les quantites de produits P1 et P2. Ainsi, on cherche a maximiser le produit de la

vente, c’est-a-dire la quantite :F (x1, x2) = 40x1 + 50x2

sachant que l’on doit bien sur respecter les contraintes de stock des ingredients A, B et C : 5 x1 + 4 x2 ≤ 80x1 + 2 x2 ≤ 24

3 x1 + 2 x2 ≤ 36

On a affaire a un (classique) probleme de programmation lineaire.

3.2Comme on n’a que deux variables, une resolution graphique (planaire) est donc possible. La figure 1

reprend cette resolution graphique.Sur ce graphique, on a trace les droites de contrainte, le polytope [O,X1,X,X2] des solutions admissibles

(solutions verifiant les contraintes, en hachure), et une droite d’isobenefice (en pointilles). La solutionoptimale est le point du polytope par lequel passe une parallele a la droite d’isobenefice qui est la pluseloignee possible de l’origine : ce point est le point X de la figure.

Pour determiner precisement ce point, on remarque qu’il est l’intersection des droites de contraintesrelatives a B et C : c’est donc la solution du systeme lineaire :{

x1 + 2 x2 = 243 x1 + 2 x2 = 36

qui donne comme solution optimale :

x1 = 6x2 = 9F = 6× 40 + 9× 50 = 690

5

�����������������������������������

�����������������������������������

x1

x2

10 20

10

20

D(B)

droite d’isobénéficeO

X

X2

X1

X’

D(A)

D(C)

FIG. 1 – Resolution graphique

3.3On va maintenant resoudre le probleme par la methode du simplexe. On sait que par cette methode, on

se deplace sur les sommets du polytope des solutions admissibles : ainsi, a partir du sommet O, on veutaboutir au sommet X. Que l’on passe par X1 ou par X2, il suffit dans les deux cas de deux etapes, ce quiexplique pourquoi on aura trois tableaux. Voici les tableaux successifs en prenant comme critere de choixde colonne celui du coefficient maximal pour la fonction economique.

On introduit donc 3 variables d’ecart yA, yB et yC (qui representent les quantites non utilisees desingredients A, B et C), et le tableau initial du simplexe s’ecrit alors :

x1 x2 yA yB yC

yA 5 4 1 0 0 80yB 1 2 0 1 0 24yC 3 2 0 0 1 36

40 50 0 0 0 F

Ce tableau correspond a la solution initiale (x1 = 0, x2 = 0, yA = 80, yB = 24, yC = 36), qui estgeometriquement representee par le sommet O.

Le choix du pivot se fait alors :– en determinant la colonne ou le coefficient est maximal dans la fonction economique : c’est la co-

lonne de x2 ;– 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 ligne yA, on obtient le quotient 80

4 = 20 ;– pour la ligne yB , on obtient le quotient 24

2 = 12 ;– pour la ligne yA, on obtient le quotient 36

2 = 18 ;– on retient comme pivot la valeur realisant le minimum, soit ici la ligne yB

On dit que yB sort de la base et que x2 entre dans la base. Cela signifie que l’on passe de la solutioninitiale a une nouvelle solution en se deplacant sur l’arete [O ;X2] : on cherche le point le plus eloigne sur

6

cette arete qui est donc X2. On obtient le nouveau tableau :

x1 x2 yA yB yC

yA 3 0 1 −2 0 32x2

12 1 0 1

2 0 12yC 2 0 0 −1 1 12

15 0 0 −25 0 F − 600

correspondant a la nouvelle solution (x1 = 0, x2 = 12, yA = 32, yB = 0, yC = 12) de benefice 600.Comme il reste un coefficient positif dans la fonction economique, ce n’est pas encore l’optimum. Onchoisit a nouveau le pivot selon les memes regles : c’est la colonne de x1 (qui va donc entrer dans la base),et la ligne de yC (qui va donc sortir de la base). On obtient le tableau final :

x1 x2 yA yB yC

yA 0 0 1 − 12 − 3

2 14x2 0 1 0 3

4 − 14 9

x1 1 0 0 − 12

12 6

0 0 0 − 352 − 15

2 F − 690

correspondant a la nouvelle solution (x1 = 6, x2 = 9, yA = 14, yB = 0, yC = 0) de benefice 690. Commeles coefficients de la fonction economique sont maintenant negatifs, on est bien a l’optimum (on retrouvele point X du graphique).

3.4On peut reecrire les equations du probleme au voisinage de l’optimum trouve (c’est le tableau final du

simplexe !) : yA = 14 + 1

2yB + 32yC

x2 = 9− 34yB + 1

4yC

x1 = 6 + 12yB − 1

2yC

F = 690− 352 yB − 15

2 yC

Comme on utilise toute la quantite de l’ingredient C disponible, on peut se demander comment l’optimumva evoluer si on augmente cette quantite. L’hypothese essentielle est la suivante : si l’augmentation est petite(ε), les pivots vont rester les memes, et on peut donc deduire la solution optimale du nouveau probleme apartir de la solution optimale de l’ancien probleme en affectant la valeur −ε a la variable yC .

On lit sur le tableau final du simplexe comment vont varier les differentes variables :– yA diminue de − 3

2ε ;– x2 diminue de − 1

4ε ;– x1 augmente de 1

2ε ;– F augmente de 15

2 ε.Ceci permet de calculer la valeur maximale du ε : c’est celle qui provoquera l’annulation de la premierevariable. Dans notre cas :

– x1 augmente donc ne peut s’annuler ;– yA s’annule pour une valeur de ε de 14

32

= 283 ;

– x2 s’annule pour une valeur de ε de 914

= 36.

On en deduit que la valeur maximale est 283 , valeur limite pour laquelle il y a alors annulation de yA. Ceci

explique pourquoi l’enonce indiquait :quelle quantite supplementaire de C faut-il acheter pour epuiser completement les 80 kg deA ?

On obtient alors comme nouvelle solution optimale :yA = 14− 3

2283 = 0

x2 = 9− 14

283 = 20

3x1 = 6 + 1

2283 = 32

3F = 690 + 15

2283 = 760

7

Graphiquement parlant, augmenter la quantite de l’ingredient C revient a « decaler » la droite D(C) pa-rallelement a elle-meme en l’eloignant de l’origine : on voit alors que le point correspondant a la solutionoptimale se deplace sur la droite D(B) en se rapprochant du point X’. La limite est atteinte lorsque lestrois droites D(A), D(B) et D(C) deviennent concourantes : c’est le point X’ correspondant a la nouvellesolution !

Cette operation est-elle rentable ? On voit que la fonction economique augmente proportionnellementa l’augmentation de la quantite de l’ingredient C, le rapport etant de 15

2 : ainsi, si le prix au kg de C estinferieur a cette valeur, l’operation est rentable ; si le prix est superieur, elle ne l’est pas.

8