COURS DE RECHERCHE OPERATIONNELLE

1

PREMIERE PARTIE : PROGRAMMATION LINEAIRE Chapitre 0 : FORMULATION D4UN PROGRAMME LINEAIRE

I. IntroductionII. Les conditions de formulation d’un programme linéaireIII. Les étapes de formulation d’un programme linéaireIV. Présentation ThéoriqueV. Exemple de formulation

Chapitre 1 : RESOLUTION GRAPHIQUE DE MAXIMISATION MINIMISATION SUR EXEMPLES SIMPLE A DEUX VARIABLES. 3

I. Premier exemple-type : maximisation d’un bénéfice ou d’une marge II. Deuxième exemple-type : minimisation d’un coût

Chapitre 2 : GENERALISATION : DEFINITION D’UN PROGRAMME LINEAIRE.

I. Définition d’un programme linéaire II. Forme canonique et standard d’un programme linéaire

(Introduction de variables d’écart et de variables artificielles)

DEUXIEME PARTIE : PHENOMENE ALEATOIRE.

Chapitre 1 : PHENOMENE D’ATTENTE.

I. Introduction II. Etude de la loi des arrivées et la loi des services

TROIXIEME PARTIE : THEORIE DES GRAPHES

Chapitre 1 : POSITION DU PROBLEME ET ESSEAI DE DEFINITION D’UN GRAPHE

I. Définition d’un graphe comme schéma. II. Définition d’un graphe comme relation binaire. III. Représentation d’un graphe.

Chapitre 2 : RECHERCHE DE NIVREAUX DANS UN GRAPHE SANS CIRCUITS

I. Définition de niveau de génération II. Procédure de détermination des niveaux de génération de chaque sommet à partir

d’un exemple

Chapitre 3 : RECHERCHE DU CHEMIN OPTIMAL

I. Recherche d’un chemin de valeur optimale dans un graphe. (Algorithme de FORD pour le maximum)

II. Application : Recherche de chemin de longueur maximale à l’aide d’un graphe

Chapitre 4 : PROBLEME D’ORDONNANCEMENT : METHODE DE PERT

2

I. Problème d’ordonnancement II. Notion de projet, tache et ordonnancement III. Diagramme de GANTT IV. Méthode de PERT (technique d'évaluation et de contrôle des programmes) V. Le PERT temps

PREMIERE PARTIE : PROGRAMMATION LINEAIRE

3

CHAPITRE 0

Formulation d’un programme linéaire (PL)

I. Introduction

L’importance de l’optimisation et la nécessité d’un outil simple pour modéliser des problèmes de décision que soit économique, militaire ou autres on fait de la programmation linéaire un des champs de recherche les plus actifs au milieu du siècle précédent. Les premiers travaux (1947) sont celle de George B. Dantzig et ses associés du département des forces de l’air des Etats Unis d’Amérique.

Les problèmes de programmations linéaires sont généralement liés à des problèmes d’allocations de ressources limitées, de la meilleure façon possible, afin de maximiser un profit ou de minimiser un coût. Le terme meilleur fait référence à la possibilité d’avoir un ensemble de décisions possibles qui réalisent la même satisfaction ou le même profit. Ces décisions sont en général le résultat d’un problème mathématique.

II. Les conditions de formulation d’un PL

La programmation linéaire comme étant un modèle admet des hypothèses (des conditions) que le décideur doit valider avant de pouvoir les utiliser pour modéliser son problème. Ces hypothèses sont1 :1. Les variables de décision du problème sont positives2. Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces variables,

c’est à dire, que la fonction ne peut pas contenir par exemple un produit croisé de deux de ces variables. La fonction qui représente le critère de sélection est dite fonction objectif (ou fonction économique).

3. Les restrictions relatives aux variables de décision (exemple: limitations des ressources) peuvent être exprimées par un ensemble d’équations linéaires. Ces équations forment l’ensemble des contraintes.

4. Les paramètres du problème en dehors des variables de décisions ont une valeur connue avec certitude

III. Les étapes de formulation d’un PL :

Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d'un programme linéaire :1. Identifier les variables du problème à valeur non connues (variable de décision) et les représenter

sous forme symbolique (exp. x1, y1 ).2. Identifier les restrictions (les contraintes) du problème et les exprimer par un système d’équations

linéaires.3. Identifier l’objectif ou le critère de sélection et le représenter sous une forme linéaire en fonction

des variables de décision. Spécifier si le critère de sélection est à maximiser ou à minimiser.

IV. Présentation Théorique

Un programme linéaire consiste à trouver le maximum ou le minimum d’une forme linéaire dite fonction objectif en satisfaisant certaines équations et inégalités dites contraintes. En langage mathématique, on décrira de tels modèles de la manière suivante :

1

4

Soient N variables de décision x1, x2,…, xn, l’hypothèse que les variables de décision sont positives implique que . 0 , ,0 ,0 21 ≥≥≥ Nxxx

La fonction objectif est une forme linéaire en fonction des variables de décision de typeNN xcxcxcz +++= 2211

où les coefficients c1,…,cN doivent avoir une valeur bien déterminée (avec certitude) et peuvent être positifs, négatifs ou nuls. Par exemple le coefficient ci peut représenter un profit unitaire lié à la production d’une unité supplémentaire du bien xi, ainsi la valeur de z est le profit total lié à la production des différents biens en quantités égales à . , , , 21 Nxxx

Supposons que ces variables de décision doivent vérifier un système d’équations linéaires définis par M inégalités

MNMNMM

NN

NN

bxaxaxa

bxaxaxa

bxaxaxa

≤+++

≤+++≤+++

2211

22222121

11212111

où les coefficients a1M,…, aMN et b1,…, bM doivent avoir une valeur bien déterminée (avec certitude) et peuvent être positifs, négatifs ou nuls. Le paramètre bj représente la quantité de matière première disponible dont le bien xi utilise une quantité égale à aij xi .

En suivant les étapes de formulation ci-dessus, on peut représenter le PL comme suit :

0 , ,0 ,0

.

21

2211

22222121

11212111

2211

≥≥≥≤+++

≤+++≤+++

+++

N

NNMNMM

NN

NN

NN

xxx

bxaxaxa

bxaxaxa

bxaxaxacs

xcxcxcMax

V. Exemple de formulation

Limité au départ aux problèmes industriels et militaires, de nos jours plusieurs problèmes de divers domaines sont représentés ou approximés par des modèles de PL. L’utilisation de ces techniques de modélisation s’est renforcée encore après avoir construit des algorithmes et des logiciels capables de résoudre de plus larges problèmes avec autant de variables de décision que de contraintes.

La tâche de formulation demande généralement une certaine expertise et connaissance du problème pour pouvoir relever facilement les différentes composantes du problème et ainsi donner un programme qui modélise au mieux la situation réelle. Dans ce qui suit, on présentera quelques exemples de formulation en programme linéaire liés à différents problèmes de décision :

Exemple : Problème d’agriculture

Un agriculteur veut allouer 150 hectares de surface irrigable entre culture de tomates et celles de piments. Il dispose de 480 heures de main d’œuvre et de 440 m3 d’eau. Un hectare de tomates demande 1 heure de main d’œuvre, 4 m3 d’eau et donne un bénéfice net de 100 DH. Un hectare de piments demande 4 heures de main d’œuvre, 2 m3 d’eau et donne un bénéfice net de 200 DH.

Le bureau du périmètre irrigué veut protéger le prix des tomates et ne lui permet pas de cultiver plus de 90 hectares de tomates. Quelle est la meilleure allocation de ses ressources ?

5

Formulation du problème en un PL :

Etape 1 : Identification des variables de décision. Les deux activités que l’agriculteur doit déterminer sont les surfaces à allouer pour la culture de tomates et de piments :• x1 : la surface allouée à la culture des tomates• x2 : la surface allouée à la culture des pimentsOn vérifie bien que les variables de décision x1 et x2 sont positives : 0 ,0 21 ≥≥ xx .Etape 2 : Identification des contraintes. Dans ce problème les contraintes représentent la disponibilité des facteurs de production : • Terrain : l’agriculteur dispose de 150 hectares de terrain, ainsi la contrainte liée à la limitation de la

surface de terrain est 150 21 ≤+xx

• Eau : la culture d’un hectare de tomates demande 4 m3 d’eau et celle d’un hectare de piments demande 2m3 mais l’agriculteur ne dispose que de 440m3. La contrainte qui exprime les limitations des ressources en eau est 44024 21 ≤+ xx .

• Main d’œuvre : Les 480 heures de main d’œuvre seront départager (pas nécessairement en totalité) ente la culture des tomates et celles des piments. Sachant qu’un hectare de tomates demande une heure de main d’œuvre et un hectare de piments demande 4 heures de main d’œuvre alors la contrainte représentant les limitations des ressources humaines est 480 4 21 ≤+ xx

• Les limitations du bureau du périmètre irrigué : Ces limitations exigent que l’agriculteur ne cultive pas plus de 90 hectares de tomates. La contrainte qui représente cette restriction est .901 ≤x

Etape 3 : Identification de la fonction objectif. La fonction objectif consiste à maximiser le profit apporté par la culture de tomates et de piments. Les contributions respectives 100 et 200, des deux variables de décision x1 et x2 sont proportionnelles à leur valeur. La fonction objectif est donc

.200100 21 xxz +=Le programme linéaire qui modélise le problème d’agriculture est :

02 ,01

90 1

480 241

4402214

150 21 ..22001100

≥≥

≤

≤+

≤+

≤+

+

xx

x

xx

xx

xxcs

xxMax

Chapitre 1 : Résolution graphique de maximisation et minimisation a deux variables

6

I- Premier exemple type : maximisation d’un bénéfice ou d’une marge

1- Dans une entreprise qui travaille à façon un client désire faire fabriquer des pièces A et des pièces B dans un délai de un mois. Il serait disposé à accepter les prix suivants :

- par séries de 100 pièces A ……….138dh - par séries de 100 pièces B ……….136dh

La réalisation des pièces A et B nécessite un passage dans 3 ateliers pour lesquels on dispose des renseignements suivants :

Nombre d’unités d’œuvre nécessairePour une série de 100 pièces A

Nombre d’unités d’œuvre nécessairePour une série de 100 pièces B

Coût variable d’une unité d’œuvre

Atelier TAtelier FAtelier M

2 1 4

1 4.5 3

10 dh 12 dh 14 dh

Au moment de la commande l’entreprise ne dispose que d’un nombre limités d’heures dans

chaque ateliers correspondant respectivement à :- 200 unités d’œuvre pour l’atelier T- 540 unités d’œuvre pour l’atelier F- 480 unités d’œuvre pour l’atelier M

Ces nombres d’unités d’œuvre sont insuffisants pour satisfaire pleinement le client dans le délai demandé. L’entreprise lui propose une livraison partielle. Quelles quantités de pièces A et de pièces B l’entreprise a-t-elle intérêt à fabriquer au cours du mois si elle veut obtenir une marge maximum, compte tenu des moyens de production disponible ?

I-A. Traduction mathématique du problème

1. Appelons : x1= nombre de séries de 100 pièces A x1≥0 x2= nombre de séries de 100 pièces B x2≥0

2. Le nombre limité d’heures dans chaque atelier permet d’écrire, en tenant compte des contraintes et disponibilités signalées :

2x1 +x2 ≤ 200 pour l’atelier Tx1 +4.5x2 ≤ 540 pour l’atelier F4x1 +3x2 ≤ 480 pour l’atelier M

3. La marge sur coût variable réalisé sur chaque type de série est :

a) pour la série de pièces A :138-[(10*2)+(12*1)+(14*4)]=50b) pour la série de pièces B :136-[(10*1)+(12*4.5)+(14*3)]=30c) la marge total pour x1 séries A s’élève à 50x1 d) la marge total pour x1 séries B s’élève à 30x2

e) la marge définitive pour les séries A et B est : 50x1 +30x2

7

si Z est la marge Z=50x1 +30x2 4. le programme à résoudre graphiquement avec x1 et x2 comme inconnues se présente sous la forme

+≤+≤+

≤+≥

)3050(

48034

5405.42002

0,

21

21

21

21

21

xxMax

xx

xxxx

xx

5. On peut construire (Fig 1) les droites d’équations respectives :2x1 +x2 = 200 x1 +4.5x2 = 540

4x1+3x2=480

et éliminer, pour chacune de ces droites, le demi-plan dont les points ne satisfont pas l’inéquation correspondante. On rappelle que pour toute droite D, d’équation ax+by+c=0, l’expression ax+by+c est strictement positive dans l’un, et négative dans l’autre, des deux demi plans ouverts de frontière D ; que la droite (D) partage le plan en trois parties :

• les points appartenant à la droite et ayant les coordonnées vérifiant ax+by+c=0 ;• les 2 demi-plans limités par (D) et dans lesquels, l’expression ax+by+c garde un signe constant

(supérieure ou inférieure à 0)

Pratiquement, On trace les droites et on utilise les coordonnées de l’origine (0,0) pour chacune des inéquations afin de vérifier le sens de l’inéquation. On hachure ensuite la partie qui ne convient pas, comme si dessous indiqué :

D1 : 2x1 +x2 = 200 passe par A(0,200) et B(100,0)D2 : x1 +4.5x2 = 540 passe par C(0,120) et D(540,0)D3 : 4x1 +3x2 = 480 passe par E(0,160) et F(120,0)

6. les coordonnées des points intérieurs et sur les cotés vérifient les contraintes. Il faut donc chercher celui qui donne le bénéfice le plus élevé.Pour le savoir, on remplacera dans l’équation de la marge Z=50x1 +30x2 les coordonnées de chacun des points de la zone d’acceptabilité. On obtient alors :

ZO=50*0+30*0=0dh ZC=50*0+30*120=3600dh

ZH=50*60+30*80=5400dh (Optimum)

ZP=50*36+30*112=5160dh ZB=50*100+30*0=5000dh

L’optimum est réalisé au point H avec :H(60, 80)

8

x1=60 séries de 100 pièces Ax2=80 séries de 100 pièces BZH=5400dh

II- Deuxième exemple-type : Minimisation d’un coût :

Résoudre le programme suivant :x1≥0 x2≥0

-2x1 +x2 ≤2 x1 -2x2 ≤ 2x1+x2≤5

Min (-x1+x2)A. Réponse

1. Déterminons le domaine d’acceptabilité en traçant les droites suivantes (Fig.2) :D1 : -2x1 +x2 = 2 → A1(0,2) ; B1(-1,0)D2 : x1 -2x2 = 2 → A2(0,-1) ; B2(2,0)D3 : x1+x2=5 → A3(0,5) ; B3(5,0) Fig 2

9

D2

0

50

100

150

200

250

0 50 100 150

D1

D3

H

2. Calculons le coût optimal :

L’équation du coût étant C= -x1+x2 remplaçons x1 et x2 par les coordonnées respectives des points délimitant le domaine d’acceptabilité :

Avec A1(0,2) on obtient CA1=0+2=2Avec P(1,4) on obtient CP=-1+4=3

Optimum :

Avec H(4,1) on obtient CH=-4+1=-3

Avec B2(2,0) on obtient CB2=-2+0= -2Avec O(0,0) on obtient CO=0+0=0

La solution optimal se trouve en H : soit:

x1=4x2=1C=-3

10

-2

0

2

4

6

8

10

12

14

0 2 4 6

D3

D1

D2

PH

Chapitre 2 :GENERALISATION : DEFINITION.

FORME CANONIQUE ET STANDARD DU PROGRAMME LINEAIRE

I-DEFINITION D’UN PROGRAMME LINEAIRE :

Les problèmes de programmation linéaire se posent lorsqu’on cherche à rendre optimum (minimum ou maximum) une fonction linéaire de plusieurs variables, ces variables étant soumises à des contraintes linéaires,(supérieures ou inférieurs ou égales à une constante).Les deux programmes suivants sont de ce type :

1. Trouver 0.....,,0,.......,0,0 21 ≥≥≥≥ ni yyyy

tel que :

mnmnimimm

nnii

nnii

qyayayaya

qyayayaya

qyayayaya

≤+++++

≤+++++≤+++++

.......

...............................................................

.......

.......

2211

222222121

111212111

et rendant

nnii ypypypyp +++++ .......2211

Maximum

1. Trouver 0.....,,0,.......,0,0 21 ≥≥≥≥ mi xxxx

Tel que :

nmmnimimm

mmii

mmii

pxaxaxaxa

pxaxaxaxa

pxaxaxaxa

≥+++++

≥+++++≥+++++

.......

...............................................................

.......

.......

2211

222222121

111212111

et rendant

mmii xqxqxqxq +++++ .......2211

MinimumEn utilisant les notations matricielles, ces deux programmes s’écrivent :

11

Programme n°1 : Trouver

≤≥

)(

0

PYMax

QAY

Y

Programme n°2 : Trouver

≥≥

)(

0

QXMin

PAY

Xt

),....,,.........,(

),......,,.........,(

a ............aa a

......................................

a ..............aa a

a .......a ......a a

21

21

mnmim2m1

2n2i2221

1n1i1211

mi

ni

xxxxX

ppppP

A

==

=

=

=

mn q

q

q

Qet

y

y

y

Y

.

.

.

.

.

.2

1

2

1

Ex : 2x1+4x2-7x3≥ 2 x1+7x2 ≤ 0 x1+2x2 =-7Max(x1-x2)

Tout programme linéaire est formé de trois grandes parties notamment :

a) d’inconnues appelées variables d’activitésb) d’équations ou inéquations au nombre de m qui représentent les contraintes linéaires en

fonction des variables d’activités c) d’une fonction économique à maximiser ou à minimiser.

D’une façon générale, la programmation linéaire a pour but la recherche de l’optimum d’une fonction linéaire(fonction économique) comportant plusieurs inconnues positives ou nulles liées entre elles, par des relations linéaires formant un système d’équations ou inéquations appelées contraintes.

A. Domaine d’application de la programmation linéaire

1. Problèmes combinatoires

-choix des investissements les plus rentables, -problèmes d’optimisation des niveaux d’activités,

-problèmes d’affectation ou de répartition optimale de la main-d’œuvre entre différents services ou ateliers,

12

-problèmes d’ordonnancement en vue de réalisation d’un objectif particulier.

2. Problèmes stochastiques

-détermination d’une politique optimale de gestion des stocks, -problèmes de files d’attente, -de répartition et de renouvellement des équipements.

3. Problèmes concurrentiels

-problèmes de distribution ou d’approvisionnement optimum, -problèmes de vente.

II- Forme canonique et standard d’un programme linéaire

Un programme linéaire peut être résolu soit par la méthode graphique soit par la méthode algébrique

A. Méthode graphique :

1. Représenter graphiquement les droites limites (équations provenant des inéquations de départ) ;2. Délimiter la frontière de l’enveloppe polygonale c’est à dire construire le domaine

d’acceptabilité ;3. Remplacer successivement les coordonnées de chaque sommet du polygone dans la fonction

économique afin d’obtenir la combinaison optimale cherchée (minimum ou maximum).

B. Méthode algébrique

1) Notion de formes canoniques

Lorsque l’ensemble de contraintes se présente sous forme d’inégalités (≥ ou≤ ) on parle de forme canonique.

Exemples x1≥ 0 x2≥ 0 ,x3≥ 0 x1≥ 0 x2≥ 0 x3≥ 0 2x1+4x2-7x3≤ 2 x1+2x2-7x3≥ 1 x1+7x2 ≤ 0 x1+0x2+5x3≥ 0 x1+2x2 ≤ -7 x1+2x2 ≥ 3 Max(x1-x2+x3) Min(x1+x2-x3)Forme canonique de Forme canonique de Type I type II

2) Notion de forme mixte

Parfois les contraintes sont les unes dans un sens, les autres dans le sens opposé, l’objectif peut être un maximum ou un minimum.

Exemples x1≥ 0 x2≥ 0 ,x3≥ 0 x1≥ 0 x2≥ 0 x3≥ 0 2x1+4x2-7x3≥ 2 x1+2x2-7x3≤ 1 x1+7x2 ≤ 0 x1+0x2+5x3=0 x1+2x2 =-7 x1+2x2 ≥ 3

13

Max(x1-x2+x3) Min(x1+x2-x3)

3) Forme standard

Toutes les contraintes représentent des égalités. L’objectif pouvant être un maximum ou un minimum.

Exemples x1≥ 0 x2≥ 0 ,x3≥ 0 x1≥ 0 x2≥ 0 x3≥ 0 2x1+4x2+x3=1 x1+x2+x3 =1 x1-x2 =5 x1+0x2+x3=8 x1+2x2 =3 3x1+2x2 =3 Max(x1+x2+2x3) Min(x1+2x2+3x3)

Remarque :

Tout programme présenté sous forme canonique, doit être ramené sous la forme standard avec introduction de variables d’écart ou artificielles selon le et selon les règles bien précises, ainsi nous le verrons par la suite.

4) Introduction de variables d’écart et de variables artificielles (Méthode du simplexe) :

Le problème d’introduction de variables d’écart et variables artificielles se pose lors du passage de la forme canonique à la forme standard et dans le cadre de la méthode algébrique.

Nous appellerons VR=variables réelles ; VE=variables d’écart ; VA=variables artificielles.

Forme canonique Forme standard x1≥ 0 x2≥ 0 x1≥ 0 x2≥ 0 x3≥ 0 x4≥ 0 x5≥ 0 20x1+30x2 ≤ 240 20x1+30x2 +x3 =240 10x1+25x2 ≤ 500 10x1+25x2 +x4 =500 15x1+40x2 ≤ 550 15x1+40x2 + +x5=550 Max(15x1+20x2) Max (15x1+20x2+0x3+0x4+0x5)VR={x1,x2} VE={x3,x4,x5} x1≥ 0 x2≥ 0 x1≥ 0 x2≥ 0 x3≥ 0 x4≥ 0 x5≥ 0 x6≥ 0 2x1+3x2 ≥ 24 2x1+3x2 –x3+ x5 =24 x1+5x2 ≥ 50 x1+5x2 -x4 +x6 =50 Min (5x1+2x2) Min (5x1+2x2+0x3+0x4+Mx5+ Mx5) VR={x1,x2} VE={x3,x4}, VA={x5,x6}

5) Méthode de résolution de maximisation : méthode algébrique de substitution.Principe :

1. Dresser la forme canonique du problème posé ;2. Passer de la forme canonique à la forme standard en transformant les inéquations en équations

et en introduisant les variables d’écart ou artificielles selon le cas ;3. Poser la solution extrême de base en utilisant les variables réelles comme variables non

principales (=variables hors base=variables nulles). Les autres variables non nulles obtenues,

14

constituant les variables principales ou variables de base. A ce stade la fonction économique est nulle.

4. Passer à la première itération afin de trouver une solution meilleure, c’est-à-dire améliorer la fonction économique.Pour y parvenir on sélectionnera une variable entrante et une variable sortante selon le critère suivant :

a) Critère d’entrée : La variable entrante correspondant au coefficient positif le plus élevé dans la fonction économique.

b) Critère de sortie : La variable sortante est celle qui correspond au plus petit rapport positif des rapports des seconds membres des contraintes aux coefficient de la variable entrante (l’infini et les nombres négatifs étant exclus).

5. On arrête les différentes itérations dès que la fonction économique ne contient plus que des coefficients négatifs ou nuls.

Exemple:

Résoudre le programme linéaire ci dessous à l'aide de la méthode algébrique de substitution. x1≥ 0 x2≥ 0 5x1+2x2 ≤ 3 6x1+7x2 ≤ 10 Max (10x1+14x2)

Forme canonique (S1)

x1≥ 0 x2≥ 0 5x1+2x2 ≤ 3 6x1+7x2 ≤ 10 Max (10x1+14x2)

Forme standard (S2)

x1≥ 0 x2≥ 0 x3≥ 0 x4≥ 0 5x1+2x2 +x3 =3 6x1+7x2 +x4 =10 Max (10x1+14x2+0x3+0x4)VR={x1,x2} VE={x3,x4}

Recherche de la solution extrême de base :

VHB :x1=0,x2=0VB :x3=3 x4=10 Z=0VHB : variable hors baseVB : variable de base

15

1èr itération :

La variable entrante est celle qui aura le coefficient le plus élevé dans la fonction économique, on a max (coef(x1),coef(x2))=max (10,14)=14=coef(x2) donc x2 est la variable entrante

A partir de (S2) on obtient le système (S3)

x1≥0 x2≥0 x3≥0 x4≥0 x3 =3-5x1-2x2 (1) x4 =10-6x1-7x2 (2) 3 et 10 : représentent respectivement : seconds membres des équations (1), (2)

A partir du système (S3) on calcule :

Min ))(

10,

)(

3(

22 xcoefxcoef−− =

7

10)

7

10,

2

3( =Min

C’est dans l’équation (2) qu’on réalise le minimum donc la variable sortante x4. A partir de l’équation (2) on exprime la variable entrante x2 en fonction des autres variables. On a d’après (2)

x4 = 10-6x1-7x2 donc x2 = 41 7

1

7

6

7

10xx −−

On remplace ensuite cette nouvelle expression de x2 dans les différentes équations de (S3), ce qui donne :

x3 =3-5x1-2( 41 7

1

7

6

7

10xx −− )

x2 = 41 7

1

7

6

7

10xx −−

Z =10x1+14x2=10x1+14( 41 7

1

7

6

7

10xx −− )

Finalement on obtient le système (S4) suivant :

x3 = 21 7

2

7

23

7

1xx +− (1)

x2 = 41 7

1

7

6

7

10xx −− (2)

Z = 41 2220 xx −− (3)Coef(Z) : -2 0 0 -2 x1 x2 x3 x4

Les coefficients de des variables de Z sont tous négatifs dont x1=0 et x4=0 et donc Z=20A partir du système (1) et (2) on

16

déduit les valeurs de x2 et x3, soient :

7

1

7

10et

Résoudre le programme linéaire ci dessous à l'aide de la méthode algébrique de substitution.

x1≥ 0 x2≥ 02x1+x2

≤ 140 x1+x2

≤ 1045x1+3x2

≤ 360Max (7x1+4x2)

Forme canonique (S1)

x1>≥ 0 x2≥ 02x1+x2 ≤ 140 x1+x2 ≤ 1045x1+3x2 ≤ 360Max (7x1+4x2)

Forme standard (S2)

x1≥ 0 x2≥ 0 x3≥ 0 x4≥ 0 x5≥ 0 2x1+x2 +x3 =140 x1+x2 +x4 =104 5x1+3x2 +x5 =360 Max (7x1+4x2+0x3+0x4+0x5)VR={x1,x2} VE={x3,x4,x5}

Recherche de la solution extrême de base :

VHB :x1=0,x2=0VB :x3=140

17

x4=104 x5=360 Z=0

VHB : variable hors baseVB : variable de base

1èr itération :

La variable entrante est celle qui aura le coefficient le plus élevé dans la fonction économique, on a Max (coef(x1), coef(x2))=Max (7,4)=7=coef(x1) donc x1 est la variable entrante

A partir de (S2) on obtient le système (S3)

x1≥ 0 x2≥ 0 x3≥ 0 x4≥ 0 x5≥ 0 x3 =140-2x1-x2 (1) x4 =104-x1-x2 (2) x5 =360-5x1-3x2 (3) 140,104 et 360 : représentent respectivement les seconds membres des équations (1), (2) et (3)

A partir du système (S3) on calcule :

Min= ))(

360,

)(

104,

)(

140(

111 xcoefxcoefxcoef−−− = 70)72,,104,70()

5

360,

1

104,

2

140( == MinMin

C’est dans l’équation (1) qu’on réalise le minimum donc la variable sortante est x3

A partir de l’équation (1) on exprime la variable entrante x1 en fonction des autres variables

On a d’après (1) x3 =140-2x1-x2 donc x1 = 32 2

1

2

170 xx −−

On remplace ensuite cette nouvelle expression de x1 dans les différentes équations de (S3), ce qui donne :

x1 = 32 2

1

2

170 xx −−

x4 =104-( 32 2

1

2

170 xx −− )-x2

x5 =360-5( 32 2

1

2

170 xx −− )-3x2

Z =7x1+4x2=7( 32 2

1

2

170 xx −− )+ 4x2

Finalement on obtient le système (S4) suivant :

18

x1 = 32 2

1

2

170 xx −− (1)

x4 = 32 2

1

2

134 xx +− (2)

x5 = 32 2

5

2

110 xx +− (3)

Z = 32 2

7

2

1490 xx −+ (4)

2èm itération :

La variable entrante est celle qui aura le coefficient le plus élevé dans la fonction économique, on a max (coef(x2), coef(x3))=max (1/2,-7/2)=1/2=coef(x2) donc x2 est la variable entrante

A partir du système (S4) on calcule le minimum positif :

Min= ))(

10,

)(

34,

)(

70(

222 xcoefxcoefxcoef−−− =

20)20,68,140()

2

110

,

2

134

,

2

170

( == MinMin

C’est dans l’équation (3) qu’on réalise le minimum donc la variable sortante est x3. A partir de l’équation (3) on exprime la variable entrante x2 en fonction des autres variables

On a d’après (3) x5 =10+5/2x3-1/2x2 donc x2 =20-2x5+5x3, puis, on remplace ensuite cette nouvelle expression de x2 dans les différentes équations de (S4), ce qui donne :

x1 =70-1/2x3-1/2(20-2x5+5x3) x4 =34+1/2x3-1/2(20-2x5+5x3)

x2 =20-2x5+5x3

Z =490+1/2(20-2x5+5x3)-7/2x3

Ce qui donne le système (S5)

x1 =60-3x3+x5 x4 =24-2x3+x5

x2 =20-2x5+5x3

Z =500-x3-x5

Tous les coefficients de la fonction économique sont négatifs. Donc on ne peut plus augmenter la fonction économique et par conséquent l’optimum est atteint. Ce qui donne :

VHB :x3=0,x5=0VB :x1=60 x2=20 x4=24 Z=500

19

VHB : variable hors baseVB : variable de base

La solution optimale est obtenue au point S (60,80) ce qui donne un maximum=500

6) Méthode de résolution de problèmes de minimisation : programme duala- Minimisation par la méthode de substitution

• Résoudre le programme suivant par la méthode de substitution

x1≥ 0 x2≥ 0 5x1+6x2 ≥ 10 2x1+7x2 ≥ 14 Min(3x1+10x2)

Forme canonique (S1)

x1≥ 0 x2≥ 05x1+6x2 ≥ 10 2x1+7x2 ≥ 14Min (3x1+10x2)

Forme standard (S2)

x1≥ 0 x2≥ 0 x3≥ 0 x4≥ 0 x5≥ 0 x6≥ 0 5x1+6x2 -x3 +x5 =10 (1) 2x1+7x2 -x4 +x6 =14 (2) Min (3x1+10x2+0x3+0x4+Mx5+Mx6)VR={x1,x2} VE={x3,x4} VA={x5,x6}

On exprime les variables artificielles (VA) x5, x6 à partir des équations (1) et (2) du système (S2)Ce qui donne :

x5 =10-5x1-6x2 +x3

x6 =14-2x1-7x2 +x4

On remplace ensuite dans la fonction économique x5 et x6 par leur expression respectivesZ=3x1+10x2+0x3+0x4+M(10-5x1-6x2 +x3)+M(14-2x1-7x2 +x4)Z=(3-7M)x1+(10-13M)x2+Mx3+Mx4+24MRecherche de la solution extrême de base

20

VHB :x1=0,x2=0,x3=0,x4=0VB :x5=10 X6=14 Z=24MVHB : variable hors baseVB : variable de baseM : valeur très grande

1èr itération :

La variable entrante est celle qui aura le coefficient le plus négatif dans la fonction économique, on a min (coef(x1), coef(x2))=min (3-7M, 10-13M)=10-13M=coef(x2) donc x2 est la variable entrante

A partir de (S2) on obtient le système (S3)

x1≥ 0 x2≥ 0 x3≥ 0 x4≥ 0 x5≥ 0 x6≥ 0 x5 =10-5x1-6x2 +x3 (1) x6 =14-2x1-7x2 +x4 (2)Z=(3-7M)x1+(10-13M)x2+Mx3+Mx4+24M10,14 : représentent respectivement les seconds membres des équations (1), (2)

A partir du système (S3) on calcule :

Min ))(

14,

)(

10(

22 xcoefxcoef−− =

6

10)

7

14,

6

10( =Min

C’est dans l’équation (1) qu’on réalise le minimum donc la variable sortante est x5. A partir de l’équation (1) on exprime la variable entrante x2 en fonction des autres variables. On a d’après (1) x2

=5/3-5/6x1+1/6x3-1/6x5.On remplace ensuite cette nouvelle expression de x2 dans les différentes équations de (S3), ce qui donne :

x2 = 531 6

1

2

1

6

5

3

5xxx −+−

x6 =14-2x1-7( 531 6

1

2

1

6

5

3

5xxx −+− ) +x4

Z =(3-7M)x1+(10-13M)( 531 6

1

2

1

6

5

3

5xxx −+− )+Mx3+Mx4+24M

Ce qui donne finalement le système (S4) suivant :

x2 = 531 6

1

2

1

6

5

3

5xxx −+− (1)

21

x6 = 5431 6

7

6

7

6

23

3

7xxxx ++−+ (2)

Z = 5431 )6

13

3

5()

6

7

3

5()

6

23

3

16()

3

7

3

50( x

MMxx

Mx

MM +−++−++−++

(3)

2èm itération :

La variable entrante est celle qui aura le coefficient le plus négatif dans la fonction

économique, on a Min ( )6

13

3

5(,),

6

7

3

5(),

6

23

3

16(

MM

MM +−−+− )= )6

7

3

5(

M− = (coef(x3)), donc

x3 est la variable entrante

A partir du système (S4) on calcule le minimum positif

Min((-5/3)/coef(x3), (-7/3)/coef(x3))=Min(((-5/3)/(1/6), (-7/3)/(-7/6))=Min(-10,2)=2.

Min ))(

3

7

,)(

3

5

(33 xcoefxcoef

−− = 2)2,10()

6

73

7

,

6

13

5

( =−=−

−−

MinMin

C’est dans l’équation (2) qu’on réalise le minimum donc la variable sortante est x6

A partir de l’équation (2) on exprime la variable entrante x3 en fonction des autres variables

On a d’après (2) x6 = 5431 6

7

6

7

6

23

3

7xxxx ++−+ donc x3= 541 7

6

6

232 xxx +++ On remplace ensuite

cette nouvelle expression de x2 dans les différentes équations de (S4), ce qui donne :

x2 = 16

5

3

5x− +

6

1( 541 7

6

6

232 xxx +++ ) 56

1x−

x3 = 541 7

6

6

232 xxx +++

Z =

545411 )6

13

3

5()

7

6

6

232)(

6

7

3

5()

6

23

3

16()

3

7

3

50( x

MMxxxx

Mx

MM +−+++++−++−++

Ceci nous amène à écrire le système (S5) suivant :

x2 = 431 7

1

6

1

7

162 xxx +++

x3 = 541 7

6

6

232 xxx +++

Z = 541 7

10

6

120 Mxxx +++

On voit bien que tous les coefficients des variables de la fonction économique sont positifs, donc on ne peut plus diminuer la fonction économique

22

VHB :x1=0,x3=0 ,x4=0 ,x5=0VB :x2=2 x3=2 Z=20VHB : variable hors baseVB : variable de basse

La solution optimale est obtenue au point S (0,2) ce qui donne un mnimum=20On peut faire une petite vérification à partir de :Z=3x1+10x2=3.0+10.2=20

b) Dualité

Les deux programmes suivants sont des programmes canoniques en dualité

≤≥

)(

0

PYMax

QAY

Y

quetelYTrouverI

≥≥

)(

0

QXMin

PAX

X

quetelXTrouverII t

La dualité consiste à passer d’un programme de minimisation vers un programme équivalent de maximisation ou l’inverse

- Le maximum de l’un est le minimum de l’autre- Les relations de correspondance du programme I au programme II sont résumées dans le

tableau suivant :

Programme primalVariables principalesx1 x2 ………..xs

Variables d’écartx’1 x’2 ………..x’r

Programme dual y’1 y’2

………..y’s

Variables d’écart

y1 y2 ………..yr

Variables principales

Coefficients de Z c0 c1 c2 ……….cp

a l’optimumalors c0 : Optimum -c1 =x’1,-c2=x’2,…-cr=x’r et –cs+1 =x1,-cs+2=x2,…-cp=x’s

Exemple d’application :• Résoudre le programme suivant par la méthode de dualité

x1≥ 0 x2≥ 05x1+6x2 ≥ 10 2x1+7x2 ≥ 14Min (3x1+10x2)

Pour passer au programme dual, on écrit le programme précèdent sous la forme suivant :

23

=

0103

1472

1065

A

Après on calcule le transposé de la matrice précédente ce qui donne :

=

01410

10726

325

At

Finalement le programme dual s’écrit :

x1≥ 0 x2≥ 05x1+2x2 ≤ 3 6x1+7x2 ≤ 10Max (10x1+14x2)

Forme standard (S2)

x1≥ 0 x2≥ 0 x3≥ 0 x4≥ 0 5x1+2x2 +x3 =3 6x1+7x2 +x4 =10 Max (10x1+14x2+0x3+0x4)VR={x1, x2} VE={x3, x4}

Recherche de la solution extrême de base :

VHB :x1=0,x2=0VB :x3=3 x4=10 Z=0VHB : variable hors baseVB : variable de base

1èr itération :

La variable entrante est celle qui aura le coefficient le plus élevé dans la fonction économique, on a : Max (coef(x1), coef(x2))=Max (10,14)=14=coef(x2) donc x2 est la variable entrante

A partir de (S2) on obtient le système (S3)

24

x1≥0 x2≥0 x3≥0 x4≥0 x3 =3-5x1-2x2 (1) x4 =10-6x1-7x2 (2) 3 et 10 : représentent respectivement les seconds membres des équations (1), (2)

A partir du système (S3) on calcule :

Min ))(

10,

)(

3(

22 xcoefxcoef−− =

7

10)

7

10,

2

3( =Min

C’est dans l’équation (2) qu’on réalise le minimum donc la variable sortante est x4. A partir de l’équation (2) on exprime la variable entrante x2 en fonction des autres variables

On a d’après (2) x4 = 10-6x1-7x2 donc x2 = 41 7

1

7

6

7

10xx −−

On remplace ensuite cette nouvelle expression de x2 dans les différentes équations de (S3), ce qui donne :

x3 =3-5x1-2( 41 7

1

7

6

7

10xx −− )

x2 = 41 7

1

7

6

7

10xx −−

Z =10x1+14x2=10x1+14( 41 7

1

7

6

7

10xx −− )

Finalement on obtient le système (S4) suivant :

x3 = 41 7

2

7

23

2

1xx +− (1)

x2 = 41 7

1

7

6

7

10xx −− (2)

Z =20-2x1-2x4

Coef(-Z): 2 0 0 2 x1 x2 x3 x4

Les coefficients de –Z à l’optimum représentent dans l’ordre les variables d’écart et les variables réelles solution du problème de minimisation

La fonction économique n’est plus composée que de coefficients négatifs. On ne peut plus augmenter la fonction économique

VHB :x1=0,x4=0VB :x2=10/7 x3=1/2 Z=20

25

VHB : variable hors baseVB : variable de base

La solution optimale est obtenue au point S (0,10/7) ce qui donne un maximum=20En revenant au problème de minimisation :On trouve :

x1=0x2=2x3=2x4=0Z=20

Ce qui conforme au résultat trouvé par la méthode directe.

DEUXIEME PARTIE : PHENOMENE ALEATOIRE

26

Chapitre 1 : Phénomène d’attente

I) Introduction

Aux guichets des gares, des banques, des postes, aux rayons des grands magasins, aux horloges de pointage des usines se constituent, au moins à certaine heures, des files d’attente ou queues, où les gens piétinent de longues minutes et s’impatientent avant d’être servis.

Mais la faculté de constituer des files d’attente n’appartient pas qu’aux êtres animés. Les ordres de fabrications qui s’empilent sur bureau du chef d’atelier, les appels téléphoniques qui parviennent à un standard, les machines tombées en panne dans une usine et qui attendent l’intervention d’un mécanicien, quoique ne forment pas toujours physiquement une queue, sont encore des exemples de phénomènes d’attente.

On distingue en générale dans un phénomène d’attente, d’une part, les entrées ou arrivées des clients, d’autre part, des stations qui exécutent à leur profit un certain service.Les lois des arrivées des clients et les durées de service, que peuvent définir les statisticiens, permettent de caractériser le système et de calculer des résultats intéressants, tel que le temps moyen d’attente des clients et le temps moyen d’inactivité des stations. La solution du problème économique qu’on peut se poser à propos des phénomène d’attente s’exprime par le nombre optimal de stations, correspondant au minimum du coût total de l’attente des clients et de l’inactivité des stations. Elle apparaît donc un compromis entre le prix, qu’on attache à l’attente de la clientèle et les charges qui résultent de l’amélioration du service.

II) Etude de la loi des arrivées et la loi des services

L’expérience montre que, dans beaucoup de phénomène d’attente, les lois des arrivées et les lois des services sont, respectivement, poissonniennes et exponentielles. Ce sont évidement pas les seules formes que peuvent affecter ces lois, mais ce sont les plus fréquentes et aussi les plus simple à utiliser.

On peut noter que la probabilité d’avoir n personnes arrivant le long d’une période de temps T est :

Tn

n en

TTP λλ −=

!

)()(

λ : est le nombre moyen d’arrivées par unité de temps, par conséquent λT est le nombre moyen d’arrivées durant la période de temps T

Ceci nous permet de calculer le nombre moyen de personnes arrivant durant la période T

Ten

Tn T

n

λλ λ∑∞

− =0

)!

)((

27

De même les distributions des durées de service sont définies par l’expression suivante :

ts etT µ−−=< 1)Pr(

C’est aussi la probabilité d’avoir un temps de service inférieur à t µ : est nombre de clients servis par unité de temps

µ1

: est la durée d’un service

II-1) Cas d’une file d’attente à une station (un seul guichet)

Plaçons nous dans le cas très simple où la loi des arrivées est poissonnienne et la loi des services est exponentielles (Fig.1)

Fig.1

De façon général, jn +=ν or dans notre cas de figure, on a une seule station (un seul guichet, j=1) ce qui donne 1+=νn

Avec n : le nombre d’unités se trouvant dans le système comprenant les unités en cours de service.

On supposant qu’on a un système stationnaire et on notant pn la probabilité d’avoir n unités dans le système on peut écrire :

µλ=

−1n

n

q

q

En utilisant la relation précédente on déduit 0)( qq nn µ

λ= , ,or 10

=∑∞

nq ce qui donne

−=µλ

10q (q0 : est la probabilité d’une attente nulle) et par conséquent )1()(µλ

µλ −= n

nq , ceci n’est

valable que si la série qn est convergente c’est à dire λ/μ<1 (taux d’arrivée inférieur au taux de service), si la relation précédente n’est pas vérifiée il y aurait engorgement et par conséquent au fil du temps on aura une file d’attente infinie.

Le rapport )(µλ

est appelé : taux de trafic ou intensité de trafic, il est noté ψ, dans ces

conditions nous pouvons écrire : )1( Ψ−Ψ= n

nq

28

ν

En attente

En service

n

j

Entrée Sortie

En service

Calculons maintenant le nombre moyen ñ d’unités dans le système :

Ψ−Ψ=Ψ−Ψ== ∑ ∑

∞ ∞

1)1(

0 0

_n

n nnqn

Appelons _

ν ¨ le nombre moyen d’unités dans la file d’attente (non compris l’unité en cours de

service). A chaque instant : 1−= nν , (n>0). Puisque le régime est permanent, et que le système est en équilibre (nombre d’entrées est égal au nombre de sorties) , on peut écrire :

Ψ==− µλν

n

_

Où Ψ==λν

µ

__

n

Cette constatation nous permet de calculer _

ν

Ψ−Ψ=Ψ==

1)(

2___

nnµλν

Ainsi que le temps moyen d’attente dans la file :

)1()1(

2_

Ψ−Ψ=

Ψ−Ψ==

−

µλλν

ft

De même on peut exprimer le temps d’un service en utilisant la relation d’équilibre

µµν

λ1

__

=−n

µν

λ

__

−n : représente la différence entre le temps moyen d’attente dans le système et le

temps moyen d’attente dans la file, c’est aussi le temps moyen d’un service.

La relation µµ

νλ

1__

+=n : représente le temps moyen d’attente globale d’un client dans le

système, c’est aussi le temps moyen d’attente dans la file (λν−

=_

ft ) plus le temps moyen d’un service

(1/ μ)On peut noter aussi que le taux moyen d’inactivité d’une station ρ, est aussi la probabilité

d’avoir zéro unités dans le système soit :

Ψ−=−

1ρExemple1

La durée d’une consultation chez un médecin est en moyenne 15mn, le médecin convoque ses clients toutes les 20mn

1) Calculer le nombre moyen de clients arrivant par heure2) Calculer le nombre moyen de personnes servis par heure

29

3) Calculer ftetn__

Solution

1) λ étant le nombre d’arrivées par mn =nombre d’arrivées/le temps correspondant à ces

arrivées en mn. λ1

: étant le temps moyen séparant deux arrivées successifs. Or λ1

=20mn=3

1h donc λ =

3

11

=3 clients arrivant par heure

2) La durée d’une consultation chez un médecin est en moyenne 15mn=1/4 h, c’est aussi la

durée d’un service= µ1

=4

1h, donc

4

11=µ

=4 personnes servis par heure, on en déduit le

taux de trafic= 175.04

3===Ψ

µλ

,

3) Le nombre moyen de clients Ψ−

Ψ=1

_

n = 375.01

075 =−

, de même la durée d’attente dans la

file)1()1(

2_

Ψ−Ψ=

Ψ−Ψ==

−

µλλν

ft =4

3_

=µn

Exemple2

Un organisme publique est ouvert, chaque jours, de 9h à 17h sans interruption. Il accueille, en moyenne, 64 usagers ; un guichet unique sert à traiter le dossier de chaque usager, ceci en un temps moyen de deux minutes et demi. Les usagers, si nécessaire, font la queue dans l’ordre de leur arrivée ; même si la queue est importante, on ne refuse aucun usager.

Une étude statistique a permis de conclure que la durée aléatoire des services suit une loi exponentielle et que les arrivées des usagers forment un processus de Poisson. On suppose que le régime permanent est rapidement atteint.

1) Donner le temps passé à attendre_

ft ; le temps moyen passé dans l’organisme par chaque

usager, _

τ

2) Quelles sont les probabilités qu’il n’arrive aucun client entre 15h et 16h ? que six clients arrivent entre 16h et 17h. ?

3) Quelle est, en moyenne et par heure, la durée pendant laquelle l’employé du guichet ne s’occupe pas des usagers ?

4) Quelle est la probabilité d’observer une file d’attente de quatre usagers, derrière celui en cours de service ?

5) quelle est la probabilité q’un usager attend plus d’un quart d’heure dans l’organisme ?

Solution

1) Le taux des arrivées est 8917

64 =−

=λ arrivées par heure

30

Le taux des services est μ=5.2

6060/2.5=24 services par heure, L’organisme n’est pas saturé

puisque 13

1==Ψ

µλ

Le temps d’attente dans la file

smnmnht f 15125.148

60

48

1

))3

1(1(8

)3

1(

)1(

22_

====−

=Ψ−

Ψ==−

λλν

, ceci nous permet de calculer _

τ

smnmnt f 45375.316

60

16

1

24

1

48

11_

====+=+=µ . Cette question concerne la loi des arrivées, la loi

de poisson : Tn

n en

TTP λλ −=

!

)()( .

Le processus étant homogène, l’heure à la quelle est pratiquée l’observation n’a aucune importance, seule compte sa durée T. 48

0 10.359.3)( −−− === eeTP Tλ , de même ;

122.0!6

)1*8()( 1.8

6

6 == −eTP

2) soit qn : la probabilité de trouver n usagers présents, en régime permanent ( )1( Ψ−Ψ= nnq ).

Le guichetier n’est occupé avec la probabilité3

2)

3

11.(1)1(0

0 =−=Ψ−Ψ=q . Donc, par heure,

il dispose mn4060*3

2 = pour vaquer à d ‘autres occupations.

3) La probabilité d’observer une file d’attente de quatre usagers, derrière celui en cours de service

est 00274.0)3

11()

3

1()1( 55

5 =−=Ψ−Ψ=q .

4) La probabilité qu’un usager attend plus d’un temps t dans l’organisme est :310.105.6)25.0*)824(exp(

3

1)25.0Pr())(exp()Pr( −=−−==−−Ψ=> ss TttT λµ

II-2) Cas d’une file d’attente à S stations

On généralise les résultats précédents (S=1) pour un phénomène d’attente à S station, et on obtient les formules suivantes :

La probabilité d’une attente nul est :

∑−

=

+−

=1

0

0

!)1(!

1S

i

iS

iS

S

pψ

ψψ

La probabilité d’avoir n personne dans le système est :

0)!

( pn

pn

n

ψ= Si 1≤n<S

0)!

( pSS

pSn

n

n −= ψ Si S≤n

31

Le nombre moyen d’unités dans la file d’attente est :

02

1

1 )1(!.)( p

SSS

psnS

Snn ψ

ψν−

=−=+∞

+=

−

∑

Avec µλψ =

La durée moyenne d’attente dans la file est :

==−

−

λν

ft 02)1(!.

p

SSS

S

ψµ

ψ

−

Le nombre moyen d’unités dans le système est :

)1

()(0 µ

λµλν

−−∞

=

−+=+== ∑ f

nn tnpn

Le taux moyen d’inactivité des guichets est :

µλρ −=−= ∑

=

−SpnS

S

nn

0

)(

La probabilité d’attendre un temps supérieur à t (dans le cas où on a S guichets) est :

)1()0Pr())(exp().0Pr()Pr(_

StToùtSTtT fs

Ψ−=−−=> µλµ

II-3) Optimisation du nombre de guichets

La solution du problème économique qu’on peut se poser à propos des phénomène d’attente s’exprime par le nombre optimal de stations, correspondant au minimum du coût total de l’attente des clients et de l’inactivité des stations. Elle apparaît donc un compromis entre le prix, qu’on attache à l’attente de la clientèle et les charges qui résultent de l’amélioration du service.

Le problème précédent peut être mis en évidence à l’aide de l’exemple suivant :

Exemple3

Dans une usine, existe un magasin de pièces détachées où les ouvriers viennent se ravitailler. Le chef d’entreprise a remarqué une affluence au guichet du magasinier, il est conscient de la perte de productivité qu’entraîne pour lui l’attente des ouvriers dans la file d’attente, il sait aussi que s’il augmente trop le nombre de guichets, il risque d’avoir une inoccupation des magasiniers et donc de payer un service qui ne sera pas rendu.

En bon gestionnaire, que va faire le chef d’entreprise ?

Solution

D’abord le chef d’entreprise va s’efforcer de minimiser les frais et donc de trouver un compromis entre le temps d’attente des ouvriers et le nombre de magasiniers qu’il faut embaucher.

32

Pendant la période T de travail ; il y a en moyenne λT arrivées pour un temps moyen de service égal à 1/μ. Du fait de l’attente dans la file, les ouvriers perdent en moyenne λTtf unités de temps de travail.

Pour un effectif de S magasiniers, le temps d’inactivité est égal, en moyenne, à ST-λT/μ

Donc le coût global est :

TccT

STcTtcS f )()()(_

2

_

12

_

1 ρνµ

λλ +=−+=Γ

Avec c1 : tarif horaire des ouvriers, c2 : tarif horaire des magasiniersLa solution du problème passe par la minimisation du coût global, ceci nous amène à trouver le

nombre de magasiniers optimal (Sopt) en rendant minimum la fonction Γ(S).

Il suffit de faire S =1,2,...,h,... , pour trouver le minimum de la fonction Γ(S), dans le cas de la figure précédente, l’optimum est réalisé au point Sopt

Exemple 4

L’usine Levablanc fabrique des machines à laver. Située dans la région parisienne, elle occupe un millier d’ouvriers et produit six types différents de machines. La production s’effectue en séries de taille moyenne et nécessite un outillage très diversifié ne permettant donc pas de laisser en permanence aux ouvriers tous les outils qui leur seraient nécessaire : ces nombreux outils son rangés dans un magasin d’outillage situé dans le hall de montage de l’usine. De ce fait on constate malheureusement la formation de queues d’ouvriers devant les guichets comptoirs du magasin. Le nombre de magasiniers assurant la distribution des outils influence, naturellement le temps d’attente ; s’ils sont trop nombreux, les attentes seront réduite, voire nulles : il semble bien inutile alors de payer des magasiniers la plus part du temps inactifs ; si, au contraire, ils sont en nombre insuffisant, les attentes deviendront fréquentes, longues et coûteuses (manque à gagner sur la production non effectuée)...

Ainsi apparaît un problème économique : combien dit-on prévoir de magasiniers, pour distribuer les outils de manière que le coût du temps perdu à attendre par les ouvriers, dune part, augmenté du coût d’inactivité des magasiniers soit minimal ? Le prix de revient horaire d’un

33

Sopt

S

c1.ν¨

c2.ρ

Γ(S)/T Fig.2

magasinier à été évaluer 4Є/h, celui du manque à gagner sur production non effectuée par un ouvrier en attente : 8Є/h

Précisons l’organisation du magasin : la file d’attente est unique : dés qu’un magasinier a servi un ouvrier, celui qui est en tête de la file d’attente le remplace immédiatement (ou, si la file est vide, le magasinier devient inactif). Les ouvriers se rangent dans la file d’attente dans l’ordre d’arrivée. La direction de Laveblanc a fait procéder à des mesures, exploitées ensuite par un statisticien ;: en moyenne 96 ouvriers se rendent au magasin chaque heure ; en autre il a observé que :

a) l’arrivée d’un ouvrier est indépendante de celle d’un autre ; b) il n’arrive jamais deux ouvriers (ou plus) simultanément ;c) le taux moyen des arrivées ne fluctue pas dans le temps.

Ces trois propriétés permettent de conclure que les arrivées aléatoires des ouvriers suivent une loi de poisson (de taux : λ=96 arrivées/h).

Par ailleurs, l’étude des temps passés par les magasiniers à servir les ouvriers a permis de conclure que la durée des services est une loi exponentielle de taux : μ =54 services/h (pour un magasinier donné).

1) Quelle est la plus petite valeur de S telle que la file d’attente ne s’allonge pas indéfiniment.

2) La durée de la journée de travail est de 8 heures : combien d’ouvriers se présentent-ils, en moyenne, au magasin d’outillage par jours ?Quel est le temps total passé par les magasiniers à les servir (le convertir en secondes) ?On supposant qu’il y a deux, puis trois, puis quatre, puis cinq magasiniers,Evaluer dans chacun de ces quatre cas, la durée journalière globale d’inactivité des magasiniers en secondes, puis son coût.

3) En utilisant l’abaque ci-joint, trouver l’attente moyenne par ouvrier selon que S=2, 3, 4 ou 5. Déterminer la durée totale d’attente journalière puis son coût pour chacun de ces cas.

4) Déterminer le nombre de magasiniers qui minimise la somme du coût d’attente totale journalière et du coût de l’inactivité totale journalière.

Prouver qu’alors, en moyenne, l’un au moins des magasiniers est inactif ...5) On suppose désormais que l’absentéisme des magasiniers fait que, sur un

effectif de S, dans 90% des cas il y a S présents et dans 10% des cas, S-1 ; l’absentéisme est négligeable au plan de la demande d’outils par les ouvriers.Montrer alors qu’il vaut mieux embaucher quatre magasiniers, les absents percevant leur salaire.

Solution

Remarque : Utilisation de l’abaque :

Connaissant le nombre de guichets S, le taux des arrivées λ, le taux des services de chaque

client μ, Calculer d’abord )1( Sµλ

. Se placer alors sur la courbe de paramètre )(Sµλ

si elle est tracée,

ou sinon la tracer par interpolation. Connaissant l’abscisse S, lire alors sur cette courbe l’ordonnée _

ftµ , puis en déduire _

ft par division par μ.

34

1) la plus petite valeur de S telle que la file d’attente ne s’allonge pas indéfiniment est déduit à

partir de la condition : )1( Sµλ

(taux des arrivées λ inférieur au taux de service μ.S) .

Numériquement )(µλ

S =54

9678.1≈ , d’où S≥2.

2) Les arrivées étant poissonniennes, le nombre moyen d’arrivées sur l’intervalle T est λT ; pour T=8 heures on obtient λT =96*8=768 arrivées d’ouvriers chaque jour au magasin.

La durée moyenne d’un service, pour la loi exponentielle, est µ1

soit 54

1heure. Le temps total

passé par les magasiniers à servir les ouvriers vaut :

ondesT

sec512003600*)54

768( ==

µλ

Le tableau ci-dessous résume les calculs demandés.

S Durée totale de présence P desMagasiniers en secondes

Durée de l’inactivité I Coût de l’inactivité C en Є

2345

5760086400115200144000

6400352006400092800

7.0739.0771.07103.07

Avec P=T.S.3600; I=P-51200; C= 4).3600

(I

3) On résume les lectures et calculs dans le tableau suivant :

S _

ftµ_

ftAttente total A par jour en secondes

Coût K de L’attente A en Є

2345

3.60.280.0540.012

24018.673.60.8

184320143362764.8614.4

409.6031.876.131.33

Où μ.tf est lu sur l’abaque ; A=760._

ft ; K=(8

8).3600

(AA = .

4) Le coût total Γ(S) est C+K d’où :

S 2 3 4 5Γ(S) 416.67 70.93 72.20 104.40

Le plus faible valeur du coût est obtenue pour S=3 magasiniers.Remarquons que pour S=3 l’inactivité est de 35200s /jours, soit 9h 46mn 40s, c’est à dire plus que la durée journalière de travail d’un magasinier.

5) Un magasinier absent perçoit son salaire. Pour l’absentéisme décrit, l’espérance du coût total est :Avec S=3 39.07+31.87*0.9+409.60*0.1=108.67 Є

35

Avec S=4 71.07 + 6.13*0.9+31.87*0.1=79.73 ЄAvec S=5 ce coût dépasse 97.78 Є (prix de revient de 5 magasiniers).

On a donc intérêt à engager un quatrième magasinier, même si l’inactivité journalière passe à 64000s, soit 17h 46mn 40s, c’est à dire plus de deux fois la durée journalière du travail.

Reste à convaincre le chef du personnel...

36

TROIXIEME PARTIE : THEORIE DES GRAPHES

THEORIE DES GRAPHES : POSITION DU PROBLEMEET ESSEAI DE DEFINITION D’UN GRAPHE

37

La théorie des graphes est une tentative de visualisation concrète des faits, C’est par conséquent, un essai de formalisation des situations de notre vie quotidienne (vie sociale, économique, politique,etc), au moyen de dessin permettant d’exprimer commodément le problème posé et parfois même d’en suivre aisément la solution par un algorithme approprié,Exemples de situations pouvant être traduites en graphe :

Différentes tâches exécutées par une ménagère lors de la préparation d’un déjeuner ; Expédition du pétrole brut depuis les régions productrices jusqu’aux raffineries de régions consommatrices ; Réseau de voies ferrées ; Fils électriques ; Rues d’une ville ; Files de téléphone ; Echanges commerciaux ; Distribution des marchandises, etc.….

I- DEFINITION D’UN GRAPHE CO MME SCHEMA

Un graphe G est constitué de deux ensembles : Un ensemble X d’éléments appelés sommets matérialisés par des points, Un ensemble U de lignes reliant chacune deux sommets ; un graphe est donc noté :

G = ( X,U )Si les lignes de U sont orientées, on les appelle alors des arcs et G prend le nom de ( graphe orienté ) ( Fig, A ).Par contre, si elles ne sont pas orientées, on obtient alors des arrêtes et G devient alors un (graphe non orienté ) ( Fig, B )

Fig. A : graphe orienté Fig. B : graphe non orienté

A tout graphe orienté, on peut associer un graphe non orienté en supprimant l’orientation des arcs, De même, à tout graphe non orienté, on peut associer un graphe orienté en remplaçant chaque arrête par deux arcs en sens inverses.

a

b

e

c

c

d

a c

e

db

38

II- DEFINITION D’UN GRAPHE CO MME RELATION BINAIRE

Un graphe peut être définit de manière plus abstraite comme la donnée d’une relation binaire sur l’ensemble des sommets :

( xi est en relation avec xj ) est équivalent à ( xi, xj ) est un arc.

Pour un graphe non orienté, la relation binaire ainsi définie est symétrique puisque si ( xi, xj ) est un arc, ( xj, xj ) l’est aussi.Dans un graphe orienté G = ( X,U ), on notera pour un sommet x :

U_(x) = { y Є X|/ ( y,x ) Є U } = ensemble des antécédents du sommet xU+(x) = { z Є X|/ ( x,z ) Є U } = ensemble des sommets successeurs du sommet x

U (x) = U_(x) U U+(x) = ensemble des sommets adjacents à x

On peut définir entièrement un graphe en se donnant pour chaque sommet, l’ensemble de ses successeurs ou de ses antécédents.

Exemple : soit G = ( X,U ) avec X = { x1, x2, x3, x4, x5 } et

U+( x1 ) = { x3, x4 }U+( x2 ) = { x1, x3, x5 }U+( x3 ) = øU+( x4 ) = { x4, x5 }U+( x5 ) = { x3, x4, x5 }

En définitive :On appelle le graphe, le couple G = ( X ,U ) formé - par un ensemble X d’éléments appelés points ou sommets.- et par une faille U de couples de sommets que l’on convient d’appeler arcs.

X1

X2

X51

X41

39

On en déduit le graphe Fig.C

X3

Le cardinal card X est l’ordre du graphe G ou nombre de sommets de G. On rappelle que, l’ensemble des sommets X est fini et que la faille U est une séquence finie. Un exemple de graphe d’ordre 6 est donné par la figure 1.

Fig. 1 : Graphe orienté et non valué

L’arc u 7 ( e, e ) est une boucle.Les points a, b, c, d,e, f sont des sommets.Les flèches reliant certains sommets sont des arcs, par exemple :u1, u2, u3, u4,, u6,u7,u8,u9.Pour u9 , par exemple, d est son extrémité initiale ( la source ) et f son extrémité terminale ( la cible ). Une flèche de c à d indique que c est en relation avec d.Si de plus, on indique le nombre sur chaque arc, comme dans la figure 2, alors le graphe est dit, et l’on parle de graphe valué.

Fig. 2 : Graphe valué

u2

u6

u10

u4

u9

u5

u3

u1

u8

b e

df

c

a

u7

3

10

6

3

54

8

2 3

b e

df

c

a

2

40

En principe, la ligne qui relie deux sommets est orientée : il s’agit d’un arc. Dans le cas ou elle ne le serait pas, cela signifierait alors qu’il conviendrait de considérer les deux sens : il s’agirait alors d’une arête, c'est-à-dire une ligne non orientée que l’on peut toujours dédoubler en deux : arcs orientés en sens inverses et réciproquement (voir fig. 3). A ce propos, dans la fig. 2 les arcs (c,e ) et (e,c) peuvent être replacés par une simple ligne non orientée. On aura alors, par exemple, l’arête [c,e] ou [e,c].

Fig. 3: Graphe non orienté

III- REPRESENTATIONS D’UN GRAPHE

On peut représenter un graphe de diverses façons, entre autres, par :- une représentation sagittale ;- une énumération de tous les sommets et arcs qui le composent ;- des dictionnaires ou tableaux à simple entrée ;- des matrices appropriées ; - une grille.

A. Représentation sagittale d’un graphe

Un représentation sagittale d’un graphe se caractérise par un schéma pourvu de sommets reliés entre eux par des lignes orientées ou non ( cf. Fig. 1,2,C ).

B. Représentation d’un graphe à l’aide de dictionnaire

1- Dictionnaire des suivants

On appelle dictionnaire des suivants d’un graphe G = (X, U) un tableau à simple entrée dont chaque ligne concerne un sommet précis et contient tous les suivants du dit sommet. Par conséquent, en face de chaque sommet X, on inscrit la liste des différents sommets qui représentent l’extrémité terminale d’un arc U dont X est l’extrémité initiale ( cf. Fig. 4 ).

2- Dictionnaire des précédents

b

d

c

a

41

On appelle dictionnaire des précédents d’un graphe G = (X, U), un tableau à simple entrée dont chaque ligne relève d’un sommet précis et contient tous les précédents du sommet en question, En face de chaque sommet X, on inscrit donc la liste des sommets qui sont l’extrémité initiale d’un arc dont X est l’extrémité terminale (voir Fig. 4)

Fig. 4: Graphe orienté

Dictionnaire (des suivants) Dictionnaire (des précédents) Relatif à la Figure 4 relatifs à la Figure 4

X S(X) X P(X)abcde

f

b e, f

bcd

e, b

abcde

f

-a, c, fdeb, fb

S(X) = ensemble des suivants de XP(X)=ensemble des précédents de XOn peut également confectionner le dictionnaire en se servant directement du dictionnaire des suivants. Dans ce cas, on note sur la ligne des sommets X, le no des lignes dans lesquelles X apparaît comme suivant.

Exemple

Soit le dictionnaire des suivants d’un graphe orienté. En déduire le dictionnaire des précédents et le graphe correspondant :

X S(X)abcd

bdc--c

a

b

c

e

d

f

42

Réponse

1) Dictionnaire des précédents

• on commence par chercher la lettre (a) dans la colonne marquée S(X). Comme (a) n’y apparaît point, cela signifie qu’il n’a pas de précédents.

• On passe ensuite à (b). la lettre (b) apparaît sur la 1ère ligne, la ligne ( a). Donc le précédent de (b) est (a).

• On passe à (c). cette lettre se trouve sur deux lignes, d’abord sur ligne (b), et ensuite sur la ligne (d). Par conséquent (c) aura pour précédents (b) et (d).

• Enfin, (d) apparaît uniquement sur la ligne (a), donc (a) est son précédent.

Au total, nous avons donc :

Précédent de (a) = néant Précédent de (b) = (a) Précédent de (c) = (b et d ) Précédent de (d) = (a)

D’où le dictionnaire des précédents que voici :

X PX)abcd

néanta

b,da

2) Graphe orienté correspondant

C. Représentation matricielle d’un graphe

1) Matrice associée à un graphe ( matrice booléenne )

b

a

d

c

Fig.5

43

M = mij avec mi

j = 1 si ( xi ;xj) Є U 0 sinon

Exemple de matrice associée au graphe Fig. 6

Sommets (extrémités)

X1 X2 X3 X4

X1 0 1 0 0Sommets X2 0 1 1 1(origines) X3 1 1 0 1

M = X4 0 0 1 1

N.B. Les termes non nuls de la diagonale principale représentent les boucles.2) Matrice aux arcs

On rappelle que tout graphe peut être défini par sa matrice associée ( ou matrice d’adjacence ) qui peut être alors littérale (matrice aux arcs ) ou booléenne comme ci-dessous (matrice correspondant au graphe de la Fig. 6 ). Dans une telle matrice une colonne de zéro correspond à une entrée, une ligne de zéro à une sortie du graphe. x1 x2 x3 x4

1100

1011

1110

0010

4

3

2

1

x

x

x

x

Matrice booléene

x4

x3

x1

x2

44

x1 x2 x3 x4

4434

432313

423222

21

4

3

2

1

00 xxxx

xxxxxx

xxxxxx

xx

x

x

x

x

Matrice aux arcs

La matrice booléenne permet l’introduction et le traitement des graphes dans un ordinateur. Si on élève M à la puissance p (p>0), la multiplication des matrices devient équivalente à « la concaténation des chemins adjacents »et la loi additive équivalente à la réunion des chemins obtenus.

Chapitre 2 :

RECHERCHE DE NIVREAUX DANS UN GRAPHE SANS CIRCUITS

45

I – DEFINITION DE NIVEAU DE GENERATION

Dans un graphe sans circuits, il est possible de numéroter les sommets du graphe de telle que le numéro affecté à chaque sommet soit inférieur à celui des suivants et supérieur à celui des précédents. Ce numéro attribué à chaque sommet est précisément le niveau de génération ou rang du sommet en question.

Par conséquent, le niveau d’un sommet Xi est la longueur du plus long chemin ayant pour extrémité Xi. Les sommets de rang 0 sont ceux qui n’ont aucun précédent. Ceux de rang 1 sont ceux dont les précédents appartiennent au rang 0. Les sommet de rang 2 ont des précédent de rang 0 ou 1 et ainsi de suite.

II – PROCEDURE DE DETERMINATION DES NIVEAUX DE GENERATION DE CHAQUR SOMMET A PARTIR D’UN EXEMPLE

Fig.1

b f g a d e c

1ère étape :

On confectionne le dictionnaire des précédents à partir du graphe Fig.1, et l’on obtient le tableau suivant :

Tableau 0 : N° de ligne

X P(X)

1 a b2 b néant3 c b, e, f4 d a5 e g6 f e, g7 g a

46

2èm étape :

On recherche ensuite dans ce dictionnaire les lignes vides. Il se trouve qu’il n’y en a aucune, en l’occurrence la ligne « b ». Par conséquent, « b » n’ayant pas de précédent est donc un sommet de niveau ou rang zéro. Ce que l’on note :

N0={b}

On barre ensuite tous les « b » dans les colonnes x de P(X), d’où le tableau n°1 ci-dessous : Tableau 1 : N° de ligne

X P(X)

1 a néant3 c e, f4 d a5 e g6 f e, g7 g a

On constate que la ligne « a » devient vide. Donc « a » est de rang 1 soit :

N1={a}

3èm étape :

On barre ensuite tous les « a » dans le tableau n°1 et on obtient le tableau n°2 suivant :

Tableau 2 : N° de ligne

X P(X)

3 c e, f4 d néant5 e g6 f e, g7 g néant

Les lignes « d » et « g » devient vides, d et g sont les sommets de niveau 2 soit :

47

N2={d, g}

On barre ensuite tous les « d » et « g », d’où le tableau n°3 ci-après :

Tableau 3 : N° de ligne

X P(X)

3 c e, f5 e néant6 f e

La ligne e de vient à son tour vide . Ce qui signifie que le sommet « e » est de rang 3 soit :

N3={e}

4èm étape :

On barre tous les « e », d’où le tableau n°4 suivant :

Tableau 4 : N° de ligne

X P(X)

3 c f6 f néant

La nouvelle ligne vide est la ligne « f ». Donc le sommet f est de rang 4 soit :

N4={f}

On barre ensuite la lettre « f », et on obtient le tableau n°5 ci-dessous :

Tableau 5 :

48

N° de ligne

X P(X)

3 c néant

La ligne « c » est vide, le sommet « c » sera de rang 5 soit enfin :

N5={c}

En résumé les différents niveaux sont :

N0={b}N1={a}N2={d, g}N3={e}N4={f}N5={c}

Le graphe Fig.1 devient le graphe Fig.2 plus lisible et plus facile à exploiter, car ordonnancé par niveau de génération.

Fig.2

d

b a e c f

g

| | | | | | N0 N1 N2 N3 N4 N5

49

Chapitre 3 :

THEORIE DU GRAPHE : RECHERCHE DU CHEMIN OPTIMAL

I- Recherche d’un chemin de valeur optimale dans un graphe. (Algorithme de FORD pour le maximum)

Soit G=(X,U) un graphe orienté donné, les arcs de graphe sont de plus valués (longueur, coût, temps, revenus,…), il s’agit donc de chercher le(s) ou les chemin(s) de longueur extrémale(minimum ou maximum) partant du sommet n°1 et aboutissant à un sommet donné.

1èr étape :

Numérotation des sommets du graphe valué dans n’importe quel ordre, mais en commençant par x0 en finissant par xn-1 (avec n nombre total de sommets).

2ème étape :

Affectation d’une valeur ∞=iλ avec 1≤i≤n-1 à tous les sommets du graphe valué (voir Fig.4)

3ème étape :

Pour tout arc (xi, xj), si la différence ijij λλ −=∆ est supérieure au nombre inscrit sur l’arc (appelé valuation), on substitue à « λj » la quantité λi+V(xi, xj) où V(xi, xj) représente la valuation comprise entre les sommets xi et xj ;

Par contre, si la différence ij∆ est inférieure au nombre inscrit sur l’arc, alors on ne change rien. (Pour chaque sommet xi : si ),( jiijij xxVλλ −=∆ alors : ),( jiij xxV+=λλ , par contre si

),( jiij xxV≤−λλ on ne change rien )

4ème étape :

On continue les itérations jusqu’à ce qu’aucun λj ne soit plus diminué.

II- Application : Recherche de chemin de longueur maximale à l’aide d’un graphe valué

50

AC F

B

2

1

7

1

Fig.4

Fig.5

1) On remplace les lettres A, B, C … F par x0, x1, x2 … x5 (voir Fig.3 et Fig.4).2) On affecte à chaque sommet xi la valeur λi=∞, 3) On note V(xi, xj) la longueur de l'arc (xi, xj) indiqué sur le graphe

Arcs partant du sommet x0 : (x0,x1), (x0,x3), dont les valeurs sont : V(x0,x1)=2, V(x0,x3)=6

-pour l'arc (x0, x1) i=0 et j=12),(0 1001 =−∞=− xxVλλ (oui) ⇒ 220),( 1001 =+=+= xxVλλ

-pour l'arc (x0, x3) i=0 et j=36),(0 3003 =−∞=− xxVλλ (oui) ⇒ 660),( 3003 =+=+= xxVλλ

Arcs partant du sommet x1 : (x1,x2), (x1,x5) dont les valeurs sont : V(x1,x2)=1, V(x1,x5)=7

-pour l'arc (x1,x2) i=1 et j=21),(2 2112 =−∞=− xxVλλ (oui) ⇒ 312),( 2112 =+=+= xxVλλ

-pour l'arc (x1,x5) i=1 et j=57),(2 2115 =−∞=− xxVλλ (oui) ⇒ 972),( 5115 =+=+= xxVλλ

Arcs partant du sommet x2 : (x2,x4) dont la valeur est : V(x2,x4)=1

-pour l'arc (x2, x4) i=2 et j=4λ 4- λ2=∞-3> V(x2, x4)=1 (oui) donc λ4= λ2+V(x2,x4)=3+1=4

51

x0x2 x5

x1

x4

x3

E

D

2 71

16

1

6

1

66

1),(3 4224 =−∞=− xxVλλ (oui) ⇒ 413),( 4224 =+=+= xxVλλ

Arcs partant du sommet x3 : (x3, x5) dont la valeur est : V(x3, x5)=6

-pour l'arc (x3, x5) i=3 et j=56),(69 5335 =−=− xxVλλ (Inéquation non vérifiée) on ne fait rien

Arcs partant du sommet x4 : (x4, x5) dont la valeur est : V(x4, x5)=1

-pour l'arc (x4,x5) i=4 et j=5λ 5- λ4=7-4> V(x4,x5)=1 (oui) donc λ 4= λ2+V(x4,x5)=4+1=5

1),(49 4245 =−=− xxVλλ (oui) ⇒ 514),( 5445 =+=+= xxVλλ

Conclusion

La valeur du chemin le plus court est égale 5, il correspond à la valeur finale de λ5. En définitive le chemin le plus court est : (x0, x1, x2, x4, x5) soit (A, B, C, E, F). (Voir Fig.5 : flèches pleines)

52

Chapitre 4 :

PROBLEME D’ORDONNANCEMENT : METHODE DE PERT

I – PROBLEMES D’ORDONNANCEMENT

• Les retards apportés aux réalisations de projet industriels et commerciaux ainsi qu’à leur livraison ponctuelle aux clients ;

• La mauvaise conception du produit à fabriquer ;• L’inexistence d’objectif à caractère unique et clairement défini, compréhensible par tous et

facilement exploitable par l’ensemble des exécutants.• Le manque de contrôle rapproché des différents opérations ou tâches élémentaires composant le

projet.• Et enfin, et surtout le manque de coordination entre les responsables des opérations concernant

l’ordre de passage des différents tâches et leur fin :Sont autant de problèmes que bon nombre d’entreprises doivent encore affronter aujourd’hui et qui nécessitent, de facto, l’apprentissage des techniques d’ordonnancement.

II – NOTION DE PROJET, TACHE ET ORDONNANCEMENT

A. Notion de projet

Un projet est un ensemble de tâches ou opérations a, b, c ,d… permettant d’atteindre un objectif fixé, lesquelles tâches sont elles-mêmes soumises à un certain nombre de contraintes telle que :

- les contraintes potentielles- les contraintes disjonctives- les contraintes cumulatives

1) Contraintes potentielles

On distingue :• Les contraintes de succession encore appelées contraintes d'antériorité qui se traduisent par le

fait qu'une tâche A ne peut commencer que si la tâche B est achevée;• Les contraintes de localisation temporelle qui impliquent qu'une tâche A ne peut débuter avant

une date imposée (par exemple, appareil non disponible avant cette date) ou ne peut se terminer après une date imposée (exemple : appareil à libérer impérativement avant cette date).

2) Contraintes disjonctives

Ces contraintes imposent la non réalisation simultanée de deux tâches A et B (pour des raisons d'utilisation d'un même appareil, par exemple, ou cause de besoin de main d'œuvre).

3) Contraintes cumulatives53

Elles limitent les possibilités d'ordonnancement, car elles tiennent compte de tous les facteurs productifs : hommes, machines, moyens financiers. C'est ainsi qu'il ne saurait être question de programmer, par exemple, pour un mois donné, des opérations qui, en temps normal, requièrent toutes ensemble, l'équivalent de six mois de travail d'un corps de métier qui ne comporterait, sur le terrain, que deux représentants.

B. Notion de tâche

Une "tâche" ou "activité" est une opération. L'ensemble des tâches forme le projet. On peut donc la définir comme étant l'unité ou l'élément du projet. On associe à chaque tâche sa durée et une contrainte d'antériorité par rapport aux autres tâches. C'est ainsi, qu'on dira que A est immédiatement antérieure à B si B ne peut débuter que lorsque A est achevée.

C. Méthode d'ordonnancement

C'est un ensemble de méthodes qui permettent au responsable du projet de prendre des décisions nécessaires dans de meilleures conditions possibles. Une telle méthode doit donc permettre :

- d'analyser le projet en profondeur, c'est-à-dire le décomposer en tâches;- de mettre sur pied un plan d'action contribuant à réaliser le dit projet tout en respectant les

contraintes;- et enfin, de contrôler le bon déroulement du projet.

Par conséquent, une méthode d'ordonnancement n'est ni plus ni moins qu'un problème d'organisation du projet.Les méthodes d'ordonnancement existantes peuvent se regrouper en deux catégories selon leur principe de base.A ce sujet, on distingue :

- les méthodes de type diagramme de Gantt (ou diagramme à barres);- ou d'autres comme :

1) La Critical Path Method (CPM), mise au point par MorGan R.2) Le Program Evaluation and Review Technique (PERT) datant de 1958 à l'époque où la marine

américaine devait réaliser dans les meilleurs délais, le système d'armes polaris, c'est-à-dire des missiles à longue portée, embarqués dans des sous-marins et doté d'une ogive nucléaire sous la responsabilité de l'amiral Rayburn.

III- DIAGRAMME DE GANTT

A. but du diagramme de Gantt

C'est un graphe de planning et de prévision ayant pour but, de mettre en évidence, les durées, et de permettre, ainsi, le contrôle, à tout moment, de l'évolution du projet, par comparaison des réalisations aux prévisions.

B. Avantages du diagramme de Gantt

- facilement compréhensible par les exécutants, de par sa clarté et sa simplicité;- peut servir de base à des plans d'action intermédiaires plus détaillés;- permet de suivre le déroulement des opérations dans le temps;- résume assez bien l'analyse du projet établie par les responsables respectifs.

54

C. Inconvénients du diagramme de Gantt

- cache les erreurs de forme et de fond commises au niveau de l'analyse du projet;- ne met pas en évidence les tâches critiques au niveau desquelles tout retard apporté au

niveau de l'exécution, entraîne un retard équivalent quant à la réalisation de l'ensemble du projet.

- Impossibilité de rectifier ponctuellement la durée d'une tâche précise, sans avoir à décaler d'autant les suivantes et à redresser sinon complètement, du moins partiellement l'édifice. Si un des maillons de la chaîne change, c'est donc tout l'édifice qui s'écroule;

- Insuffisance également dans la mise en évidence des liaisons existant entre les différentes tâches.

D. Construction du diagramme de Gantt

1) Principe de construction

Le diagramme de Gantt se présente sous la forme d'un tableau quadrillé dans lequel une colonne correspond à une unité de temps et une ligne à une tâche ou opération. La tâche se matérialise par une barre horizontale dont la longueur représente la durée ( de la tâche). Le travail effectif ou le déroulement réel du projet se présente parfois, par des barres horizontales en pointillés, juste au-dessus de celle figurant les prévisions, comme l'indique la Fig.1.

2) Exemple d'application

Un projet se décompose en 6 tâches dont les caractéristiques sont les suivantes :

Tâches Durée prévue

Tâches précédentes

Durée réalisée

ABCDEF

4 mois2 mois 3 mois5 mois6 mois1 mois

sans précédentssuccède à Asuccède à B}succèdent à Csuccède à A

323541

En déduire, Le diagramme de Gantt correspondant à l'état d'avancement du projet au 15ème mois.

Fig.1: diagramme de Gantt

Temps

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

TâchesA

B

C

D

E

55

F

On constate, au 15ème mois, que toutes les tâches ont respecté les délais impartis, sauf A et E. La tâche A est en retard d'un mois, et la tâche E de 2 mois. Les tâches B et F succèdent à A sont réalisé complètement alors que B et E succèdent à C ne le sont pas simultanément; commencées à la même date, seule la tâche D s'est terminée dans le délai imparti.

IV - METHODE PERT (technique d'évaluation et de contrôle des programmes)

A. But de la méthode PERT

L'objet essentiel de la "Program Evaluation and Research Task" (PERT) ou méthode des potentiel-étapes, est de mettre en évidence les différentes liaisons qui existent entre les tâches. L'outil de base demeure le graphe du projet, c'est-à-dire, l'organisation ou articulation des opérations les une par rapport aux autres.

B. Structure fondamentale de la méthode PERT

On peut décomposer sommairement la méthode PERT en trois phases principales, notamment celles :

1) De la confection d'un graphe traduisant l'organisation de l'ensemble des tâches, les unes par rapport aux autres, par conséquent , la mise en évidence du projet ou du programme envisagé.

2) De la recherche du chemin critique et on peut en avoir plusieurs dans le même graphe ou réseau-PERT.

3) De l'introduction du temps, de la détermination de la durée de réalisation de l'ensemble des opération et du calcul des marges.

4) Et de l'explication des résultats, leur interprétation et la mise sur pied d'actions correctrices.

C. Construction d'un réseau PERT

La construction de tout réseau-PERT doit obéir aux conventions fondamentales ci-dessous :

1) deux tâches successives doivent être représentées par deux flèches placées l'une à la suite de l'autre (Fig.2);

2) chaque arc représente une tâche élémentaire. Si la tâche "i" doit être antérieure à la tâche "j", l'extrémité finale de l'arc "i" coïncide avec l'extrémité initiale de l'arc "j";

3) les sommets des graphes représentent alors des "étapes" dans le déroulement des opérations;

Fig.2: Notion d'étapes initiales et terminales d'une tâche "i" ou "j" i j1 2 3

étape initiale étape terminale étape initiale étape terminale de "i" de "i" de "j" de "j"

56

1 2 3

4) le graphe doit posséder une "entrée", sommet sans antécédent qui est l'extrémité initiale des arcs associés aux tâches sans antécédent, c'est-à-dire, celles pouvant commencer sans préalable. Ce sommet correspond à "l'étape début des opérations".De même le graphe doit posséder une "sortie", sommet sans successeur l'extrémité finale des arcs associés aux tâches sans successeur : ce sommet correspond à l'étape "fin des opérations".

5) Chaque tâche doit correspondre à une tâche et une seule.6) Le graphe ne doit contenir ni boucles ni circuits.7) Le graphe doit comporter le moins possible de croisements d'arcs.8) Chaque sommet correspondant à une étape doit être représenté par un cercle à l'intérieur duquel est

prévu un système de repérage (numéro ou lettre) permettant de l'identifier et de suivre aisément l'ordre de succession des tâches.

9) Afin de faciliter la consultation du graphe, il est conseillé d'orienter les flèches de la gauche vers la droite.

3) Cas particulier d'utilisation des tâches fictives

Une tâche fictive est une tâche de durée nulle ne mettant pas en jeu aucun moyen matériel et financier. Elle est généralement représentée par des arcs ou flèches en pointillés. L'introduction des taches fictives permet de solutionner certaines situations complexes et de lever des ambiguïtés, par exemple lorsque deux ou plusieurs opérations sont menées parallèlement ou lorsque deux ou plusieurs tâches ont même sommet initiale et même sommet finale.

• 1er exemple-typeReprésenter le cas suivant :

"l" succède à "j""k" succède à "i" et "j"

La représentation graphique correcte est :

Fig.3 i k1 2 3

j l1 2 3

Nota : tâche fictive (5-2)Par contre la représentation suivante est incorrecte :La Fig.36 signifie que "l" succède à "i" ce qui n'est pas indiqué dans l'énoncé.

Fig.4

i k

j l

57

1 32

4 5 6

• 2èm exemple-type

La Fig.5 est correcte. Le graphe de la fig.6 est inexact.

Fig.5 : Graphe correcte Fig.6 : Graphe incorrecte

i j j i

Tâche fictive Étape fictive

V - LE PERT-TEMPS

En attribuant à chaque opération une durée prévisionnelle quant à son exécution, il nous sera possible de mettre en évidence "un chemin critique" formé d'une succession de tâches critiques au niveau desquelles tout retard sera prohibé, sous peine de retarder d'autant la réalisation de l'ensemble du projet. Ce chemin critique représente le temps minimum nécessaire quant à la réalisation du projet. Alors les tâches critiques rendent le programme rigide, les tâches non critiques quant à elles, laissent une certaine marge de manœuvre dans les déroulements des travaux.Dés que le chemin critique sera établi (et implicitement les "dates au plus tôt" et "au plus tard") il sera donc possible de convertir le graphe PERT en diagramme de Gantt, et de contrôler aisément le déroulement des travaux. La détermination des marges à partir des calculs des dates au plus tôt et au plus tard, permettra, en outre, de connaître encore le temps disponible par tâche, la marge de manœuvre dont nous disposons, de déceler certains retards, d'imputer les responsabilités, et d'apporter des actions correctrices qui s'imposent.

A. recherche du chemin critique - date au pus tôt - date au plus tard d'un événement

1) Chemin critique

On rappelle que le chemin critique est le temps minimum nécessaire quant à la réalisation du projet. Il est composé exclusivement de tâches critiques, c'est-à-dire celles dont l'exécution ne doivent être ni retardée ni ralentie, sous peine d'augmenter d'autant, la réalisation de l'ensemble du projet. Ce chemin passe par les sommets dont au plus tôt et au plus tard coïncident. Son "intervalle de flottement" est nul par comparaison à celui des autres. Aussi les responsables du projet ne jouira-t-il d'aucune liberté au niveau de ces tâches, la marge de manœuvre permise étant nulle.

2) Dates au plus tôt d'un événement

Il s'agit de la date avant laquelle une tâche ne peut démarrer. C'est donc la date attendue de réalisation d'un événement ou date avant laquelle un événement ne peut se réaliser.

58

1

2

3

1 2

3

3) Date au plus tard d'un événement

C'est la date limite de réalisation d'un événement. Si l'événement venait, en effet, à se réaliser après ladite date, le projet tout entier ne pourrait jamais se réaliser dans le délai correspondant à la longueur du chemin critique.

4) Notion d'intervalle de flottement

a - Position du problème

Pour affiner le suivi des opérations et le contrôle de la ponctualité quant au respect des dates au plus tôt et au plus tard, il devient alors indispensable, pour le responsable du projet, de se pencher sur le degré de liberté dont il dispose, pour éventuellement augmenter la durée d'une tâche, sans pour cela compromettre la fin du projet dans les délais impartis. Chercher à modifier les dates au plus tôt ou au plus tard sans que le délai total de réalisation du projet n'en soit modifié, suppose que le responsable ait à sa disposition les "intervalles de flottement" pour chaque étape ou événement. S'intéresser davantage aux tâches qu'au événement pour connaître la marge de manœuvre dont dispose face au événements de début et de fin qui encadrent la tâche, sous entend que l'on s'intéresse aux "marges". On en distingue trois : la marge libre, la marge totale, et la marge certaine.

B - Intervalle de flottement

Pour chaque sommet, on obtient un intervalle de flottement en faisant la différence entre la date au plus tard et la date au plus tôt du même événement. Rappelons que l'intervalle de flottement est un intervalle dans lequel peut intervenir la réalisation d'un événement sans compromettre l'exécution de l'ensemble du projet ni sa durée totale minimale.

C - Les marges

Calcul des marges

On distingue trois sortes de marges : marge totale, marge libre et marge certaine pour chaque tâche.

Evénement ou étape Evénement ou étape

Ei Ej

Date au plus Date au plus Data au plus Data au plustôt de Ei tard de Ei tôt de Ej tard de Ej

59

ti t'itj t'j

EiEj

Tij =tâche comprise entre Ei et Ej dij =durée de la tâche Tij

Marge libre de Tij : ML (Tij) = tj- ti- dij

Marge total de Tij : MT (Tij) = t'j- ti- dij

Marge certaine de Tij : MC (Tij) = tj- t'i- dij équivalent à 0 si MC est négativeNota: on a toujours :

0≤MC≤ML≤MT

Signification économique et influence sur la durée du projet

4-1) La marge libre d'une opération correspond pour cette opération, au retard maximum que l'on peut apporter à son démarrage, sans perturber la date de réalisation au plus tôt de l'événement suivant. Concrètement,si une tâche si une tâche commence à sa date au plus tôt, et si sa durée est augmentée de sa marge libre, il n'y a pas de perturbations dans la suite du projet, les dates au plus tôt et au plus tard des autres opérations restent inchangées. Un retard supérieur à la marge libre se répercute sur les tâches suivantes en diminuant leurs marges.

4-2) La marge totale d'une opération est le retard maximum que l'on peut apporter à son démarrage sans perturber la date de fin des travaux. Pratiquement, la marge totale représente la fluctuation maximale pour la tâche considérée, à condition qu'elle est commencée le plus tôt possible. Notons que si une marge totale a été utilisée, certaines tâches subséquentes deviennent critiques et il apparaît alors un deuxième chemin parfois appelé chemin sous-critique. En effet, si, le retard est égale la marge totale, la tâche ne dispose plus d'aucune marge, c'est pour cela qu'elle devient critique, de même qu'un certain nombre de tâches, qui lui succèdent. Par ailleurs, si le retard dépasse la marge totale, l'excédent se répercute sur la date de la fin du projet qui se trouve alors décalée d'autant.4-3) La marge certaine est le retard maximum, que l'on peut apporter à son démarrage sans perturber la date de réalisation au plus tôt de l'événement suivant, bien que l'événement précédent n'ait été réalisé qu'à sa date limite.

5) Mise à jour d'un PERT: contrôle et surveillance du déroulement des opérations

La mise à jour d'un PERT nécessite que :

5.1) l'on recueille des informations aussi à partir des exécutants qui les appliquent qu'à partir de la direction du projet appelée à faire des retouches permanentes au fur et à de l'avancement des travaux.

5.2) Ces informations recueillies se présentent sous des formulaires spéciaux et compréhensibles par tous. Ces formulaire mettront suffisamment en évidence, l'ensemble des points importants du projet auxquels les exécutants devront consigner les dates effectivement atteintes et les écarts positifs ou négatifs observés par rapport aux prévisions. C'est ainsi qu'il sera nécessaire de dresser la liste des tâches du projet en les classant par rubriques ou par date de début ou de fin. Par exemple:- Par ordre croissant de date de début au plus tôt;- Par ordre croissant de date de début au plus tard;- Par ordre croissant de date de fin au plus tôt;- Par ordre croissant de date de fin au plus tard;- Par marge totales croissantes.

En pointant le travail effectivement fait, on pourra donc facilement savoir si les dates de début et de fin ont été ou non respectées. A ce propos, la liste des dates au plus tard permettra

60

immédiatement de déceler les tâches devenues critiques, tout comme la lite des marges croissantes permettra de situer l'état d'avancement de l'ensemble du projet.

5.3) Après la collecte des informations quant à l'état d'avancement du projet et le choix du mode de leur présentation, il faut les dépouiller soigneusement, les trier et enfin les départager, les tâches critiques (qui ne doivent souffrir d'aucun retard) des tâches non critiques ( présentent plus de souplesse au niveau de l'exécution).

5.4) Il faudra ensuite procéder au traitement des différentes informations provenant de l'échange des données entre les exécutants et les décideurs, et procéder aux corrections et " recorrections " diverses.

5.5) Ensuite, arrivent les phases de l'analyse et de l'interprétation.5.6) Et enfin, la phase d'imputation des responsabilités, et la mise sur pied d'actions

correctrices Suivies de contrôles, sinon, permanents du moins intermittents permettant de s'assurer que les nouvelles mesures correctrices sont respectées et portent leur fruit.

6) Exercice d'application sur la méthode PERT

- Thème 1 : Recherche d'un chemin critique

La réalisation d'un ouvrage se décompose en tâches A, B, C, D, E, F, G, H.

Les durées respectives sont les suivantes : A (3 jours), B(4 jours), C(4 jours), D(2 jours), E(6 jours), F(2 jours), G(4 jours), H(1 jours). On se propose de déterminer la durée minimum nécessaire quant à la réalisation dudit ouvrage, ainsi que les dates auxquelles doivent ou peuvent débuter les tâches pour que cette durée minimum soit respectée.

On rappelle, en effet, que les tâches A et B sont sans tâche intérieure. Par contre, la réalisation de la tâche F nécessite l'achèvement des tâches C et D et donc A et de B, et précède la réalisation de la tâche H. Les tâches E et H sont sans successeur, mais H suit G et F tout comme E vient immédiatement après A. Notons que C est précédé par A et que D sui B, ainsi que le résume le tableau suivant :

Tâches A B C D E F G HTâches précédentes

A B A C,D B F,G

- Réponse au thème 1

1) Construction d'un réseau PERT

61

A(3)

B(4)

C(4)

F(2)

E(6)

D(2)

G(4)

H(1)E

4

S

1

2

3

Fig.7

Nota:E:entrée du "réseau-PERT"; S= sortie du "réseau-PERT"

Nom de l'étapeDate au plus tôt

Date au plus tard

2) Détermination des dates au plus tôt

a) On affecte à l'entrée, la date tE=0b) Pour un sommet j, on calcule la date au plus tôt (tj) en posant : Tj= Max{ti+dij}

Avec i= antécédent de j dij= durée de l'arc (i, j) ti= date au plus tôt du sommet i tj= date au plus tôt du sommet j tS= durée minimum de l'ouvrage

Fig.8 : Dates au plus tôt (à gauche du cercle)

tE= 0t1= tE+ 3t2= tE+ 4t3= Max{t1+4, t2+2} = Max{3+4, 4+2} = 7t4= Max{t2+4, t3+2} = Max{4+4, 7+2}

62

A(3)

B(4)

C(4)

F(2)

E(6)

D(2)

G(4)

H(1)E

4

S

1

2

3

0

7

4

310

9

= 9tS= Max{t1+6, t4+1} = Max{3+6, 9+1} = 10La durée minimum de l'ouvrage est de 10 jours.

3) Détermination de la date au plus tard

Pour calculer la date au plus tard, on peut adopter, la méthode suivante :

a) inversion de l'orientation de tous les arcs du graphe (une sorte de compte à rebours);b) avec ce nouveau graphe, on calcule les dates au plus tôt ( les rôles de l'entrée et de la sortie sont

inversés);c) les dates au plus tard sont alors obtenues par différence entre la durée minimum de l'ouvrage et les

dates ainsi calculées comme le montre le graphe inversé ci-dessous (Fig.9)

Fig.9 : Dates au plus tard (à droite du cercle)

Dates au plus tôt dans le graphe orientée Dates au plus tard tS= 0 t'S= 10-0 =10 t4= 1 t'4= 10-1 =9 t3= t4+ 2=3 t'3= 10-3 =7 t2= Max{t4+4, t3+2} t'2= 10-5 =5 = Max{1+4, 3+2} = 5 t1= Max{tS+6, t3+4} t'1= 10-7 =3 = Max{0+6, 3+4} = 7 tE= Max{t1+3, t2+4} t'E= 10-10=0 = Max{7+3, 5+4} = 103) Détermination du chemin critique

On reconnaît les tâches critiques par l'égalité qu'il y a entre leurs dates au plus tôt et au plus tard. Et comme le chemin critique passe par les taches critiques depuis l'entrée (E) jusqu'à la sortie (S), il

63

A(3)

B(4)

C(4)

F(2)

E(6)

D(2)

G(4)

H(1)E

4

S

1

2

3

0

7

55

310

9

suffira donc de repérer les tâches critiques, de passer un trait épais dessus ou alors tracer deux traits pour bien mettre en évidence ledit chemin critique (voir Fig.10).

Fig. : Récapitulation des résultats; dates au plus tôt et dates au plus tard. Chemin critique

Le chemin critique est ici A, C, F, H.

Thème 2 : Construction d’un « réseau PERT » par utilisation de niveau de génération. Chemin critique ; calcul de marges et des intervalles de flottement.

La construction d’un entrepôt peut se décomposer en 10 tâches reliées entre elles par des conditions d’antériorité. L’entreprise chargée de cette construction vous communique le tableau des enchaînements des différentes activités, avec indication des durées respectives de chaque tâche (voir tableau annexe). Pour planifier son travail, elle vous demande de représenter sur un graphe, le chemin critique indiquant le temps minimum nécessaire pour la réalisation de ce projet.

Tableau annexe

Désignation Activités pré requises

Durée (jours)

A Acceptation des plansB Préparation du terrainC Commande des matériauxD Creusage des fondationsE Commande des portes et fenêtresF Livraison des matériauxG Coulage des fondationsH Livraison des portes et fenêtresI Pose des murs et de la charpente du toitJ Mise en place des portes et des fenêtres

AA, B

AC

D, FEG

H, I

42112221041

64

A(3)

B(4)

C(4)

F(2)

E(6)

D(2)

G(4)

H(1)E

4

S

1

2

3

Fig.10

Travail à faire :

1) Construire le « réseau PERT » dans lequel l’événement sera matérialisé par un cercle comme suit :

événement

Date au plus tôt Date au plus tard

1) Déterminer le chemin critique ;2) Calculer la marge libre, la marge totale, et la marge certaine de chaque tâche ;3) Déterminer le flottement de chaque sommet ou événement.

Réponse du thème 2

1) Construction d’un réseau-PERT

On se sert du « tableau annexe » de l’énoncé comme dictionnaire des précédents, les premières lignes vides fournissant le premier niveau de génération A et B). Barrant ensuite A et B où qu’ils se trouvent, on obtient le 2ème niveau de génération et ainsi de suite. On obtient, en définitive, les niveaux ci-dessous ainsi que le graphe associé.

N0={A, B} N1={C, D, E} N2={F, H}N3={G} N4={I} N5={J}

Solution 1 : Fig.11

65

Ei

ti t’i

A(2)

B(2)

C(1)

F(2)

E(2)

D(1) G(2)

J(1)

1

2

3

4

I(1)

H(10)5

9

6

8

7

Solution 2 : Fig.12

2) Chemin critique (voir fig.12)

Pour déterminer le chemin critique, On adopte la même méthode que dans le thème 1, en calculant préalablement les dates au plus tôt et au plus tard et en choisissant le chemin dont les tâches sont critiques (c’est à dire dont les tâches au plus tôt et au plus tard coïncident). Le lecteur est donc vivement invité à s’exercer au calcul de ces dates par lui-même.Le chemin critique est (1, 2, , 8, 9) ou (A, E, H, I), soit 17 jours. On notera, entre autres, la présence d’une tâche fictive entre A et D.

3) Calcul des marges

Tâche Durée

Marge libre Marge totale

Marge certaine

A=( 1- 2)A=(1 - 3)A=(2 - 4)A=(3 - 6)A=(2 - 5)A=(2 - 6)A=(4 - 7)A=(6 - 8)A=(5 - 8)A=(8 - 9)

42112221041

4-0-0=44-0-2=25-4-1=07-4-1=26-4-2=07-5-2=09-7-2=0

16-6-10=016-9-4=317-16-1=0

4-0-4=09-0-2=78-4-1=310-4-1=56-4-2=010-5-2=312-7-2=316-6-10=016-9-4=317-16-1=0

4-0-4=04-0-2=25-4-1=07-6-1=06-4-2=0

7-8-2=-2 (MC=0)9-10-2=-2 (MC=0)

16-6-10=016-12-4=017-16-1=0

3) Calcul des intervalles de flottement

L’intervalle de flottement d’un sommet Ei est :

66

A(2)

B(2)

C(1)

F(2)

E(2)

D(1) G(2)

J(1)

1

2

3

4

I(1)

H(10)5

9

6

8

7

IF= t’i-ti

avec

Date au plus tôt Date au plus tard

Détermination du flottement de chaque événement

Evénement

Date au plus tardt’j

Date au plus tôttj

Intervalle de flottement

IF= t’i-ti

123456789

t’j =0t’j =4t’j=9t’j=8t’j=6t’j=10t’j=12t’j=16t’j=17

tj=0tj=4tj=4tj=5tj=6tj=7tj=9tj=16tj=17

005303300

Les tâches critiques présentent toujours des « intervalles de flottement » nuls. C’est un bon moyen pour reconnaître un chemin critique. Les nombres en gras soulignés retracent les différentes étapes empruntées par le chemin critique.

67

Ei

ti t’i

68