1 Recherche du plus long chemin dans un réseau. Outil de gestion de projet : algorithme de Ford...

1

Recherche du plus long chemin dans un réseau. Outil de gestion deprojet : algorithme de Ford pour la recherche d’un chemin critiqueet le calcul de la durée minimale d’un projet. Méthodes permettantde comprimer la durée d’un projet au moindre coût. La méthodePERT : durée aléatoire des tâches. Le contrôle des coûts vs lerespect des délais imposés. Exemples.

2

Introduction

L’instinct et le geste impulsif ont fréquemment cédé le pas à l’actionréfléchie et au geste planifié.

La planification ne date pas de la vie moderne :

la construction de l’Arche de Noé : réussite.

l’édification de la tour de Babel : non menée à terme.

Pour les projets complexes exigeant de grands moyens, faisantintervenir un grand nombre de personnes, et dont le caractère estnon répétitif, on doit penser à :

- préciser l'objectif;- déterminer les opérations ou les tâches nécessaires à réaliser;- estimer la durée et les ressources exigées par chaque tâche;- estimer les risques et prévoir les marges nécessaires pour les pallier;- calculer la durée totale et le coût total du projet;- dresser un calendrier d'échelonnement des tâches.

3

1er problème

On s’intéresse à la recherche du plus long chemin dans un réseau.

chemin critiqueVoici un exemple d’application :

Une compagnie désire mettre en exploitation un nouveau gisementminier. Les opérations suivantes doivent être réalisées :

a. Obtention d’un permis d’exploitation 180b. Construction d’une piste entre route et site 120c. Installation de deux sondeuses 7d. Érection de baraques provisoires 21e. Asphaltage de la piste 30f. Adduction d’eau 60

Durée (jours)

Dans la planification d’un projet impliquantplusieurs tâches, exigeant chacune un temps d’exécution et reliéesentre elles selon un ordre de précédence, on cherche le tempsminimum d’achèvement du projet.

4

g. Campagne de sondages 210h. Fonçage et équipement des puits 120i. Installation au fond du matériel d’exploitation 42j. Construction de logements pour le personnel 150k. Traçage et aménagement du fond 330l. Construction d’une laverie 210

Relations d’antériorité :

b doit être précédée de a et suivie des opérations c, d, e, f.

c et d précèdent g.

e, f et g précèdent h et j.

h et j précèdent i, k et l.

Durée (jours)

5

Construction d’un graphe simple appelé diagramme PERT

Les arcs seront les opérations et les sommets seront des événements(l’achèvement de certaines tâches) liés à ces opérations.

D Fa, 180 b, 120

c, 7d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 330

D début des opérations F fin des opérations

Note :

Ce diagramme n’est pas un graphe simple à cause des opérationsparallèles c, d et e,f et i, k, l resp.

Graphe simple : graphe tel qu’il n’y a jamais plus d’un arcallant d’un sommet à un autre.

6

Pourquoi un graphe simple ?Les algorithmes connus pour trouver un chemin critique nécessitentun graphe simple.

Comment convertir ce graphe en un graphe simple ?

Prenons par exemple les opérations parallèles c et d.

Le moyen le plus simple est de créer un événement fictif et uneopération fictive de durée nulle comme ceci :

c

de

f

g0

n opérations parallèles nécessitent n - 1 sommets fictifs etn-1 opérations fictives de durée nulle.

7

1 12a, 180 b, 120

c, 7

d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 330

On obtient donc pour le graphe au complet le diagramme PERTsuivant :

2 3

6

0 0

7

8

9

11

0

10

0

5

4

0

8

Prise en compte de différents types d’opérations :

Opérations composées

Soit une opération a, constituée des 3 opérations élémentairessuccessives a1, a2 et a3 de telle sorte que l’opération c suive a1,d suive a2 et b suive a3.

Sous forme graphique, on obtient :

a1 a2 a3 b

c d

Cela peut arriver lorsqu’on demande que c ne commence qu’unefois le premier tiers de a effectué et que d ne commence qu’unefois les deux premiers tiers de a effectués. De plus, a précède b.

L’opération a est divisée en 3 sous-opérations de durée égale autiers de celle de a.

9

Opérations dépendantes et indépendantes

Soit,a

b

c

d

c et d sont des opérations dépendantes de a et de b.

Effectuons le changement suivant : c doit succéder à a,d est dépendante de a et b.

Il faut créer un état fictif et une opération fictive de durée nulle :a

b

c

d

10

Limites de démarrage : 1er cas

Soit le graphe partiel suivant,

D

a b

c

Suite à des imprévus, l’opération c ne pourra commencer avant t0

unités de temps écoulées depuis le début des travaux.

Il faudra donc créer une opération fictive de durée t0 allant dudébut des travaux au début de c.

Puisque b n’est pas astreinte à cette contrainte de démarrage, ondoit introduire un sommet fictif libérant b de cette limite dedémarrage tout en tenant compte du fait que b et c suivent a.

Finalement, on doit prévoir une opération fictive de durée nulleindiquant la dépendance de c envers a.

11

D

ab

c0

t0

Limites de démarrage : 2ième cas

Pour qu’une tâche i puisse débuter, il est nécessaire que la duréeécoulée depuis le début d’une autre tâche k soit au moins égale àune durée donnée tki.

On doit ajouter l’arc (k, i) représentant une opération fictivede durée tki.

12

Problème de la recherche du chemin critique(les tâches qui s’y trouvent sont critiques pour la durée du projet)

Il s’agit de trouver la date de réalisation de la fin des travaux i.e.la date la plus proche qui permette que toutes les opérations soientréalisées et la séquence de tâches qui réalise cette durée.

Cela consiste à déterminer le chemin le plus défavorable du débutà la fin des travaux i.e. le chemin de longueur maximale.

2

3

13

67

Exemple :

La fin des travaux aura lieu à la date 9.L’opération (1, 3) aura 2 unités de temps supplémentaires pourêtre réalisée.

Convention : Le temps de début des travaux sera toujours le temps 0.

13

Résolution du problème de la recherche du chemin critique

Un diagramme PERT est connexe et sans circuit.

Autrement, nous serionsen présence de plusieurs projets.

Une opération ne peut sesuccéder à elle-même.

Considérons une légère adaptation de l’algorithme de Bellman-Kalabasur le diagramme précédent.

Soit ti,j la durée de l’opération qui va du sommet i à j, ti le temps de réalisation au plus tôt ou temps attendu,

(par convention, t1 = 0)

14

1 12a, 180 b, 120

c, 7

d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 3302 3

6

0 0

7

8

9

11

0

10

0

5

4

0

t2 = t1 + t1,2 = 180

t3 = t2 + t2,3 = 300

t4 = t3 + t3,4 = 300

Pour le sommet 5, il y a 2 possibilités : t3 + t3,5 = 321 ou t4 + t4,5 = 307.Vu qu’on cherche le chemin le plus long, on prendra : t5 = 321.

15

t6 = t3 + t3,6 = 300

t7 = max {t3 + t3,7 , t6 + t6,7 , t5 + t5,7} = 531.

Et ainsi de suite, jusqu’à t12 = 1011.

1 12a, 180 b, 120

c, 7

d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 3302 3

6

0 0

7

8

9

11

0

10

0

5

4

0

0 180 300

300 531 681

681

1011

681531

321

300

temps de réalisation au plus tôt

16

Notion de chemin critique

Un ensemble d’opérations dites critiques en ce sens qu’on ne peuttolérer aucun retard dans leur mise en exécution et dans leurexécution sans retarder le temps tn de la fin des travaux(ici t12 = 1011).

1 12a, 180 b, 120

c, 7

d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 3302 3

6

0 0

7

8

9

11

0

10

0

5

4

0

0 180 300

300 531 681

681

1011

681531

321

300

Ex. : (1, 2, 3, 5, 7, 8, 9, 12)

Le chemin critiqueest indiqué en traits doubles.

17

Temps de réalisation au plus tard ou temps limite

Les opérations non critiques peuvent sans doute être retardées dansleur mise à exécution sans retarder le temps final des travaux.

Soit ti le temps limite de réalisation à laquelle peut se fairel’événement i sans retarder le temps tn de la fin des travaux.

Note : tn = tn ti = ti i dans le chemin critique.et

Comment obtenir les temps de réalisation au plus tard :

ti = tn - le temps minimal nécessaire pour réaliser lesopérations entre i et n

ti = tn - somme des temps opératoires sur le cheminle plus long de i à n.

Cependant, il est possible de les obtenir très rapidement.

18

1 12a, 180 b, 120

c, 7

d, 21

e, 30

f, 60

g, 210

h, 120

j, 150

i, 42

l, 210

k, 3302 3

6

0 0

7

8

9

11

0

10

0

5

4

0

0 180 300

501 531 801

969

1011

681531

321

314

temps de réalisation au plus tard

t10 = t12 – t10,12 = 969 t11 = t12 – t11,12 = 801

t9 = temps minimal nécessaire= min{ t12 – t9,12, t11 – t9,11, t10 – t9,10} = min{681,801,969} = 681

etc.

19

Traçons maintenant le chemin critique à partir des ti et des ti:

Le sommet i fait partie du chemin critique si ti = ti.

Si les sommets i et j font partie du chemin critique,l’opération de i à j sera critique si tj - ti,j = ti.

20

Intervalle de flottement d’un événement i

[ti, ti] est l’intervalle de temps où peut se réaliser l’événement isans retarder le temps de fin des travaux.

Note : Les événements du chemin critique auront unintervalle de flottement réduit à un seul point.

Si l’intervalle de flottement de l’événement k estréduit à un seul point, l’événement k appartiendraà un des chemins critiques (s’il y en a plusieurs).

Exemple : 1 0 2 180 3 300 4 [300, 314]

5 321 6 [300, 501] 7 531 8 531

9 681 10 [681, 962] 11 [681, 801] 12 1011

21

Marge libre d’une opération de i à j

Le délai qui peut être apporté à la mise à exécution de l’opération(i, j) sans pour autant retarder le temps de réalisation au plus tôt del’événement j.

Il s’agit de : tj - ti,j - ti.

Exemple :

(1,2) (2,3) (3,4) (3,5) (3,6) (3,7) (4,5) (5,7) (6,7) (7,8)

0 0 0 0 0 171 14 0 201 0

(7,9) (9,10) (9,11) (9,12) (10,12) (11,12)

30 0 0 0 281 120

Note : Une opération critique entraîne une marge libre nulle.L’inverse n’est pas vrai.

Ex. : l’arc (3,4) n’est pas une opération critique.

22

La marge libre est un concept local qui ne tient pas compted’une suite d’opérations non critiques.

Marge totale d’une opération de i à j

Or, ce qui nous importe le plus en général est de ne pas retarderla fin des travaux même si on doit faire des réaménagements surquelques opérations non critiques.

Exemple : On peut retarder le début de l’opération (3, 4)de 14 unités sans retarder la fin des travaux.

La marge totale indique le délai maximal qui peut s’écouler avantle début de l’opération (i, j) sans retarder la fin des travaux maisen retardant peut-être celui de j sans dépasser son temps deréalisation au plus tard :

tj - ti,j - ti.

23

Exemple :

(1,2) (2,3) (3,4) (3,5) (3,6) (3,7) (4,5) (5,7) (6,7) (7,8)

0 0 14 0 201 171 14 0 201 0

(7,9) (9,10) (9,11) (9,12) (10,12) (11,12)

30 288 120 0 288 120

24

Diagramme à barres de de Gantt

Construit à l’aide de la marge totale et du diagramme PERT, il nousindique les opérations critiques en 1ière rangée avec l’échéancier àrespecter.

Sous les opérations critiques se placent les opérations non critiquesdans les cases où elles peuvent varier librement.

Exemple :

L’opération c précède l’opération d, toutes 2 non critiques;c peut varier de 10 à 20 étant d’une durée de 3; d peut varier de 17 à 24 étant d’une durée de 4.

10 24

c 3

d 4

2017

25

Diagramme de Gantt tiré de notre exemple :

0 180

a b

300

d g j k

321 531 681 1011

c 7

f 60

e 30

h 120 i 42

l 210

Cela indique bien visuellement ce qu’on peut faire sans toucher autemps de fin des travaux.

Note : Le diagramme devrait être tracé à l’échelle.

26

Algorithme de Ford pour calculer les temps au plus tôt ti.

Étape 0. Poser ti = 0 i = 1, 2, …, n.Poser i = 1, j = 2.

Étape 1. Si l’arc (i, j) n’existe pas dans le diagrammealors aller à l’étape 4.

Étape 2. Si tij > tj - ti, faire tj = tij + ti et aller à l’étape 3.

sinon aller à l’étape 4.

Étape 3. Si i > j, faire i = j, j = 2 et aller à l’étape 5

sinon aller à l’étape 4.

Étape 4. Faire j = j + 1.

Étape 5. Si j n aller à l’étape 1

sinon faire j = 2, i = i +1 et aller à l’étape 6.

Étape 6. Si i n aller à l’étape 1

sinon Fin.

27

Algorithme de Ford pour calculer les temps au plus tard ti.

Il s’agit d’utiliser l’algorithme de Ford précédentoù chaque sommet i a été remplacé par n – i + 1,

chaque arc (i, j) du diagramme est remplacé par (j, i).

Les résultats obtenus sont placés sur le diagramme originalaprès avoir effectué le calcul suivant :

ti = tn - somme des temps opératoires sur le cheminle plus long de i à n.

28

BREF

Les notions précédentes ont une grande importance :

L’établissement du diagramme PERT permet de préciser ledéroulement des opérations avec les interactions des différentestâches.

La mise en évidence d’un chemin critique détermine lesopérations conditionnant la réalisation du projet.

Elles devront être surveillées attentivement par le gestionnairedu projet.

Les opérations non critiques sont moins rigides et peuventtolérer certains retards quant à leur temps de mise en œuvre(intervalles de flottement, marges libre et totale).

29

En pratique, les durées tij des opérations sont mal connues et incertaines.

Deux cas se présentent :

A On connaît les distributions des temps d’opérations à partir dedonnées statistiques obtenues dans la réalisation de projetssemblables.

Déterminer le temps moyen et la variance de chaqueopération : tij et 2

ij.

Ce temps moyen de chaque opération servira comme durée del’opération.

La variance interviendra plus tard dans l’estimation du temps defin des travaux.

30

B On suppose que les temps d’opération sont distribués selon une loiBêta pour des raisons de commodité de calculs.

T ~ Bêta(a, b)

T est une v.a. comprise dans l’intervalle [a, b]où a et b sont des constantes positives.

L’aspect de la distribution Bêta en fonction des paramètresa, b et M est le suivant :

a bM

M désigne la valeur de T où sa fonction de densité est maximale.

31

Les paramètres de cette fonction de densité sont choisis de telle façon

tij = (aij + 4Mij + bij) / 62

ij = (bij - aij)2 / 36.

Pour déterminer les valeurs de tij et 2ij, il suffit de poser les questions

suivantes aux spécialistes responsables de chaque opération :

À combien estimez-vous la durée minimale de l’opération (i, j) ?

À combien estimez-vous la durée maximale de l’opération (i, j) ?

Quelle est la durée la plus probable de l’opération (i, j) ?

Note : Ces informations fort subjectives doivent être utiliséesavec prudence.

32

Exemple :

Les opérations fictives demeurent avec des durées nulles.

33

1 12a, 180 b, 135

c, 6

d, 20

e, 28

f, 61

g, 205

h, 160

j, 140

i, 50

l, 215

k, 3152 3

6

0 0

7

8

9

11

0

10

0

5

4

0

00

180180

315315

315512

540560

700800

700965

10151015

700700

540540

335335

315329

Le chemin critiqueest indiqué en traits doubles.

Le chemin critique est 1, 2, 3, 5, 7, 9, 12 et son espérance mathématiqueest égale à la somme des espérances des opérations qui le composent i.e.E(t12) = 1015.

34

Si les opérations sont en nombre suffisant et les temps opératoires sontindépendants, le théorème central-limite s’applique.

35

Sous ces hypothèses, on obtient que :

2t12

= 21,2 + 2

2,3 + 23,5 + 2

5,7 + 27,9 + 2

9,12 = 1300.1111

Calcul de la variance des dates au plus tôt des autres événements :

Il s’agit de considérer le chemin le plus long de 1 à 8 et,

Ex. : E(t8) = 540 = somme des temps moyens sur le chemin le plus long de 1 à 8.

2t8 = 2

1,2 + 22,3 + 2

3,5 + 25,7 + 2

7,8 = 797.3333

Calcul de la variance des dates au plus tard des autres événements :

Il s’agit de considérer le chemin le plus long de 4 à 12 et,

Ex. : E(t4) = 329 = somme des temps moyens sur le chemin le plus long de 4 à 12.

2t4 = 2

4,5 + 25,7 + 2

7,9 + 29,12 = 973.8055

36

Importance du calcul des variances pour la réalisation d’un projet

Supposons que le contracteur qui réalise les travaux s’est engagé à lesterminer avant 1100 jours et qu’après, il ait à payer des pénalités parjour de retard.

Le contracteur est intéressé à connaître la probabilitéqu’il respecte son engagement.

t12 – 1015 N(0, 1) 36.057

Par conséquent, P(t12 ≤ 1100) = P( t12 – 1015 ≤ 2.36) ≥ 99% 36.057

ce qui laisse une marge de manœuvre suffisante au contracteur.

Note : Si le contracteur s’était engagé à terminer les travaux avant 1040jours, on aurait trouvé P(t12 ≤ 1040) ≥ 75,8% Risque élevé.

Le contracteur augmenterait alors le prix de sa soumission.

37

Analyse des coûts de réalisation des tâches d’un projet

L’accélération du temps de réalisation d’une tâche se traduit par uneaugmentation de son coût.

Dorénavant, chaque temps opératoire tij peut varier entre deux bornesdij et Dij.

Limite supérieure ou durée normale(temps opérationnel normal)

Limite inférieure ou durée accélérée(temps minimal nécessaire pour réaliser l’opération Pij)

Terminologie :

En optant pour la durée normale (accélérée) de chaqueopération, le problème à résoudre est dit le programme normal(accéléré).

Note : Habituellement, le programme accéléré est trop coûteux etle programme normal trop long.

38

Coût de réalisation cij de l’opération Pij

La fonction de coût a généralement la forme suivante :

tij

cij

dij Dij

Le coût de l’opération est minimal si sa durée est normale etcroît lorsqu’on s’en éloigne.

Si tij > Dij on ne peut effectuer le travail qu’à des coûts beaucoupplus élevés ce qui correspond habituellement à desmoyens insuffisants en main d’œuvre et matériel.

****

39

Comment trouver des durées qui représentent un juste milieu entre nospossibilités temporelles et financières ?

1ière approche : Diminution du coût total d’un programme enaugmentant la durée des opérations non critiques.

On suppose ici qu’il nous est impossible de modifier la durée desopérations critiques et donc la date de fin des travaux.

Par contre, on peut modifier la durée des opérations non critiques.

La durée tij de chaque opération Pij est contrainte comme suit :

dij ≤ tij ≤ Dij

Considérons un exemple où les durées tij sont indiquées sur les arcsdans le diagramme PERT suivant :

40

Exemple :

41

Exemple (suite) :

L’augmentation des coûts est proportionnelle à la diminution des tempsopératoires, i.e. les fonctions de coût sont linéaires et décroissantes.

Posons cij coût marginal de l’opération Pij ou encore,l’augmentation d’une unité dans la durée del’opération Pij implique une diminution de cij

dans le coût de cette opération.

Dans le tableau suivant, on retrouve :- les durées normales,- les durées accélérées,- les temps opératoires,- les marges libres,- les marges totales,- les couts marginaux,- les coûts opératoires,- le coût total (la somme des coûts de toutes les opérations).

42

Exemple (suite) :

cij

Coût total : 214,000$

43

Exemple (suite) :

La durée du programme étant inchangée, il suffit de diminuer lamarge libre des opérations non critiques pour diminuer le coût total.

Les nouvelles durées des opérations non critiques ne pourront êtresupérieures à :

t'ij = tij + min(mlij, Dij - tij)= min(Dij, tij + mlij).

Dans cet exemple, choisissons comme durées ces bornes supérieures.

44

Exemple (suite) : On obtient le nouveau diagramme PERT suivant :

Cela crée un nouveau chemin critique (1, 2, 5, 3, 6, 8, 9).

4

45

Exemple (suite) :

Pour chaque opération non critique, la diminution du coût seraégale à : cij (t'ij - tij).

On obtient alors pour les opérations non critiques indiquées,la diminution de coût suivante :

Cela donne une diminution totale de 39, 400$ et le coût totals’établit maintenant à 214, 000 – 39,400 = 174, 600$.

diminution de 18.6% env.

46

Il ne faut pas croire que l’on soit parvenu pour une date de fin destravaux égale à 31 à un programme de coût minimal.

2

124

On pourrait tenir compte de la marge totale de P24.

47

On peut augmenter la durée de P24 de 2 unités (économie de 4600$) etlaisser la durée de P45 à 2 unités au lieu de 4. Nous aurions réalisé uneéconomie supplémentaire de 2,700$.

48

2ième approche : Accélération d’un programme au moindre coût.

Pour réduire le temps total d’exécution d’un programme, il fautréduire la durée d’une ou de plusieurs opérations critiques.

Si nous choisissons l’opération critique qui, pour une mêmediminution de temps, propose la plus faible augmentation des coûts,nous dirons que nous avons accéléré le programme au moindre coût.

49

Exemple :

g

f

h

d

c

e

i

b

a

Les fonctions de coût des opérations sont de la forme ****.

Ce diagramme PERT représente un programme normal admettantun coût total de 350 millions (voir tableau suivant).

Nous avons aussi un programme accéléré dans ce tableau.

50

durées(mois) et coûtsde

chaque opération

durées(mois) et coûtsde

chaque opération

Coût total: 350 x 106$ 523 x 106$

51

Il n’est pas nécessaire d’augmenter la durée des opérations critiques :on dépenserait alors de l’argent inutilement.

Attaquons-nous aux opérations critiques a, b, f et i.

Puisque le coût d’accélération par mois est :

a : 5 millionsb : 19 millionsf : 13 millionsi : 3 millions,

pour accélérer le programme au moindre coût, il s’agit de réduirele temps opératoire de 1 mois sur i ce qui va coûter le moins cher.

52

g

f

h

d

c

e

i

b

a

Le diagramme PERT devient :

2

35 35

En gagnant 1 mois sur i, nous n’avons pas créé de nouveauxchemins critiques car, autrement, il aurait fallu tenir comptedes nouvelles opérations critiques.

53

Essayons de gagner un autre mois.

On ne peut le faire sur i puisqu’elle a déjà atteint sa durée accélérée.

Parmi les autres opérations critiques (a, b et f), a coûte le moins cherà accélérer et puisqu’on peut l’accélérer, gagnons un autre mois surl’opération a.

g

f

h

d

c

e

i

b

a2

34 343

9 9

3 3

19 22

32 32

54

Essayons de gagner un autre mois sur la tâche a, ce qui est possible.

g

f

h

d

c

e

i

b

a2

33 332

8 8

2 2

18 21

31 31

Il n’est maintenant plus possible d’accélérer la tâche i ou la tâche a.

Entre b et f, il faut choisir f.

55

On peut gagner 3 autres mois sans difficulté.

g

f

d

c

i

b

a2

30 302

8 8

2 2

18 18

28 28h

10

20

ce qui fait apparaître un nouveau chemin critique.

e

56

Pour réduire la durée totale d’exécution, 3 possibilités s’offrent à nous :

gagner 1 mois sur b : coût de 19 millions,

gagner 1 mois sur f : coût de 13 millions,et 1 mois sur e : coût de 5 millions, d’où un coût de 18.

gagner 1 mois sur f : coût de 13 millions,et 1 mois sur h : coût de 7 millions, d’où un coût de 20.

On choisit donc la 2ième option.

57

g

f

d

c

i

b

a2

29 292

8 8

2 2

17 17

27 27h

10

19

e 9

On ne peut plus accélérer la tâche e.Il nous reste 2 alternatives :

gagner 1 mois sur b : coût de 19 millions,

gagner 1 mois sur f : coût de 13 millions,et 1 mois sur h : coût de 7 millions, d’où un coût de 20.

58

g

f

d

c

i

b

a2

28 282

7 7

2 2

16 16

26 26h

10

19

e 9

Gagnons un mois sur b.

5

Finalement, il nous reste une possibilité :

gagner 1 mois sur f : coût de 13 millions,et 1 mois sur h : coût de 7 millions, d’où un coût de 20.

59

g

f

d

c

i

b

a2

27 272

7 7

2 2

16 16

25 25h

9

18

e 9

5

Il n’est maintenant plus possible d’accélérer la date des travauxdans cet exemple.

60

En résumé,

Durée du programme

(mois)

Coût

(millions $)

a b c d e f g h i

36 350 4 6 4 12 10 23 7 10 3

35 353 4 6 4 12 10 23 7 10 2

34 358 3 6 4 12 10 23 7 10 2

33 363 2 6 4 12 10 23 7 10 2

32 376 2 6 4 12 10 22 7 10 2

31 389 2 6 4 12 10 21 7 10 2

30 402 2 6 4 12 10 20 7 10 2

29 420 2 6 4 12 9 19 7 10 2

28 439 2 5 4 12 9 19 7 10 2

27 459 2 5 4 12 9 18 7 9 2

Durée des opérations(mois)

C’est au gestionnaire de choisir l’alternative la plus appropriée.

61

Généralisations possibles du problème :

La fonction de coût avait jusqu’à maintenant la forme suivante :

tij

cij

dij Dij

****

tij

cij

dij Dij

Voici des alternativesoù le problème devientplus difficile :

tij

cij

dij Dijt*

62

Généralisation au programme à coût minimal si les coûts sont desfonctions quelconques des durées :

Posons cij(tij) le coût en fonction de la durée de la tâche Pij,dij la durée accélérée de la tâche Pij,Dij la durée normale de la tâche Pij,dn et Dn les durées accélérée et normale d’exécution,tij la durée de la tâche Pij,t la durée totale d’exécution,U l’ensemble des arcs du programme,on cherche à minimiser le coût total de ce programme.

MIN cij(tij)(i,j) U

Sujet à tij ≤ t chemin allant du sommet 1 au sommet n.(i,j)

dn ≤ t ≤ Dn

dij ≤ tij ≤ Dij tâche Pij