RECHERCHE

OPÉRATIONNELLE

OBJECTIF

A la fin de cette matière, le stagiaire doit être capable d’appliquer les notions
de la théorie des graphes.

LEÇON N°01 : INTRODUCTION A LA RECHERCHE

OPÉRATIONNELLE ET À LA PROGRAMMATION LINÉAIRE
LEÇON N°02 : ÉLÉMENTS DE LA THÉORIE DES GRAPHES

LEÇON N°03 : PROGRAMMATION LINEAIRE : LA METHODE

DU SIMPLEXE LEÇON N°04 : RECHERCHE D’UN CHEMIN DE
LONGUEUR MINIMALE ET DE LONGUEUR MAXIMALE DANS
UN GRAPHE VALUE METHODE DE FORD

LEÇON N°05 : PROBLEME D’ORDONNANCEMENT :

METHODE PERT LEÇON N° 06 : LE CHOIX

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 1
LEÇON N°01 : INTRODUCTION A LA RECHERCHE
OPÉRATIONNELLE ET À LA PROGRAMMATION
LINÉAIRE

OBJECTIF PÉDAGOGIQUE : À la fin de cette leçon, le stagiaire doit être capable

de :

1- Définir la recherche opérationnelle

2- Définir un programme linéaire
3- Résoudre graphiquement un programme linéaire à 2 inconnues

PLAN DE LA LEÇON:

I- LA RECHERCHE OPÉRATIONNELLE
1- Préceptes de la recherche opérationnelle
2- Démarche

II- LA PROGRAMMATION LINÉAIRE

1- Introduction générale
2- Qu’est ce qu’un programme linéaire
3- Résolution par la méthode graphique d’un programme linéaire

CONCLUSION

EXERCICES

CORRIGÉS

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 2
I-LA RECHERCHE OPÉRATIONNELLE :
1- Préceptes de la recherche opérationnelle :
- Réfléchir avant d’agir ;
- Ne pas se fier au bon sens. Appuyez ses décisions sur des bases rationnelles ;
- Tirer le meilleur parti des moyens dont on dispose dans des circonstances données.

Ces préceptes qui pouvaient être ceux du parfait manager, sont ceux de la
recherche opérationnelle.

La RO consiste en l’application de méthodes scientifiques pour élaborer des

décisions et chercher à résoudre ainsi des problèmes complexes se rencontrant
dans la direction et la gestion de grands systèmes d’hommes, de machines, de
matériaux et d’argent dans l’industrie, le commerce, l’administration et la défense.
La R.O propose une véritable démarche scientifique pour les aborder.

- Chercher à comprendre et à structurer un système complexe en construisant un «

modèle » ;
- Utiliser cette compréhension et ce modèle pour prédire est améliorer les
performances du système discipline carrefour, la recherche opérationnelle utilise
pour arriver à ses fins des techniques propres à d’autres disciplines scientifiques:
Mathématiques, Statistiques, Economique, Informatique.

2- Démarche:
Un premier exemple issu d’un grand domaine d’application de la RO, la logistique,
va nous servir à illustrer cette démarche.

Une entreprise doit livrer chaque matin quatre clients à partir d’un dépôt central.
Un livreur à bord d’un camion se rend donc dans les magasins des clients pour
décharger ses marchandises avant de retourner à son point de dépôt.

L’entreprise dans un 1er temps, cherche à organiser la tournée du livreur. Plus celle-
ci est courte, non seulement plus vite elle permet au livreur de participer à d’autres
tâches, mais surtout plus elle sera économique pour l’entreprise.

Dans ce cas, tout le système, représenté, par le livreur, les clients, l’entreprise et
son environnement, doit être pris en compte.

Après appréciation du coût de voyage entre deux (02) clients, exprimé en temps ou
en unités monétaires, le critère choisi à été unique: tournée dont la somme des
coûts des liaisons empruntées est la plus petite possible.

L’incertitude de certaines données pourraient être prise en compte, le temps de

liaison entre 2 clients peut fluctuer suivant les heures de la journée, seule une
valeur probable peut être connue. D’autres contraintes peuvent exister. Que se

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 3
passe-t-il si le volume de marchandises à livrer aux clients excède la capacité du
camion? Si certains clients ne sont présents que

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 4
pendant une certaine période de la matinée? Tout ceci montre que la construction
d’un modèle est délicate. Le problème posé est: Dans quel ordre le camion doit-il
visiter les clients pour accomplir une tournée de coût total minimal (le plus petit
possible)? Les tournées possibles sont au nombre de 24 :(1 2 3 4, 1 2 4 3, 1 3 2 4,
1 3 4 2, 2 1 3 4, 2 1 4 3,...................................................................................................................),
quelle est donc celle qui fournit le circuit le moins coûteux. En énumérant ces 24
solutions et en calculant le coût total des liaisons à assurer, la tournée cherchée
sera nécessairement trouvée. En calculant à la main, plus on moins
maladroitement, cela prendra 5 minutes.

Passons maintenant à un ordre de grandeur supérieure, plus proche que la réalité:

Vingt cinq clients, par exemple, chiffre encore assez faible par rapport à une
clientèle donnée réelle. Les tournées possibles sont au nombre de 25! = 25 x 24x
23 x….x 2x 1, plus question de calcul manuel, alors peut être un ordinateur? Mais
pas d’illusions, même un ordinateur calculant assez rapidement prendrait un temps
équivalent à plusieurs siècles pour trouver la meilleure tournée entre les 25 clients.
Ceci est surprenant et montre qu’il faut parcourir à un modèle mathématique
(exprimant le problème) et ensuite le résoudre.

L’élaboration d’un modèle consiste en la définition de variables de décision,

associées ici par exemple au choix ou nom d’une liaison à emprunter entre 2
clients, la définition des contraintes (passer par chaque client une et une seule fois)
et de l’objectif représenté par un but à optimiser (coût minimal) et ceci en fonction
de ces variables.

Une fois le problème ainsi posé ; commence l’étude de la conception et de la mise

en œuvre informatique d’une méthode de résolution. Ce problème de tournée est
appelé problème du voyageur de commerce, il a acquis sa renommée pour
plusieurs raisons qui ont éclairé d’autres aspects de la R.O.

II- LA PROGRAMMATION LINÉAIRE :

1- Introduction générale à la programmation linéaire :
Établir un schéma de fabrication qui utilise de manière optimale un stock de
matière première limité, transporter des denrées de différents entrepôts vers
différents magasins au meilleur coût possible, tout en satisfaisant la demande des
magasins et respectant la disponibilité de chaque entrepôt : Voilà quelques
exemples classiques de problèmes économiques pour lesquels il importe de
disposer de modèles mathématiques à la fois simples, puissants et informatisables
(en égard au nombre considérable de données à traiter). On parle
traditionnellement à leur sujet de programmation mathématique sans que le mot
« programmation » ne fasse en quelque manière que ce soit, référence à l’aspect
informatique : il s’agit dans chaque cas d’établir un schéma ou « programme » de
fabrication, de transport, optimisant une fonction économique (fonction bénéfice,
fonction coût) dans laquelle les variables sont soumises à des contraintes
(limitation de stock de matière premières) respect de l’offre et de la demande …).

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 5
Nous ferons lors de la modélisation, une hypothèse simplificatrice supplémentaire: «
tout est linéaire », la fonction économique et les contraintes. Cette réduction sévère
couvre toutefois une gamme importante d’applications pratiques et constitue le prix
à payer pour obtenir le modèle simple et puissant recherché: La programmation
linéaire.

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 6
2- Qu’est ce qu’un programme linéaire ?
Pour illustrer cette définition commençons par un exemple.

2.1- Un premier exemple-type: Maximisation d’un bénéfice: Une

usine fabrique 2 produits P1 et P2 à l’aide de 3 matières premières M 1, M2 et M3 dont
on dispose en quantités limitées. Sous tous les cieux, et tous les régimes se pose le
problème de l’utilisation optimale de ce stock de matières premières, c’est à dire la
détermination d’un schéma (programme) de fabrication tel que:

- Les contraintes de ressources en matières premières sont respectées ;

- Le bénéfice réalisé par la vente de la production est maximum.

Modèle mathématique:

a- Données numériques des contraintes :

- La disponibilité en matières premières :

- Les caractéristiques techniques de la fabrication sont données dans le tableau ci-

18 unités de
après ; y figurent les quantités de matières premières nécessaires à la
fabrication d’une unité de chaque produit Pi.
M1 8 unités

M1 M2 M3
P 1 1 2
1 3 1 1
P
2

b-Hypothèses de linéarité du modèle :

(L1) Linéarité des contraintes:On suppose que la fabrication est à rendement

constant ; c’est à dire, d’après le tableau ci-dessus pour fabriquer x 1 unités de (P1) il
faut ×1 unités de M1, ×1 unités de M2 et 2 ×1 unités de M3 , de même, la fabrication
de ×2 unités du produit P2, nécessite 3 ×2 de M1, ×2 unités de M2 et ×2 unités de
M3 .

(L2) Linéarité de la fonction économique: On suppose que le bénéfice peut être

exprimé à l’aide des bénéfices unitaires c1 et c2 sous la forme Z = c1 x1 + c2 x2.

c1 est le bénéfice unitaire.

C’est à dire : bénéfice réalisé par la fabrication d’une unité du produit P 1, le bénéfice
réalisé par la fabrication de x 1 unités du produit P1 est alors c1 x 1. De même que
pour le produit P2, le bénéfice réalisé par la fabrication de × 1 unités de P1 et ×2
unités de P2 est Z = c1 × 1 + c2 × 2 ce qu’on a appelé fonction économique.

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 7
c- Réalisabilité d’un schéma de production :
x1
Un schéma de production est un cou
p désignant les

quantités de P1 et P2 fabriquées, il doit évidemment vérifier les contraintes x 1 ≥ 0, x 2 ≥

0.

Un tel schéma est-il réalisable? A-t-on suffisamment de matières premières pour

assurer une telle production? Le niveau de fabrication nécessite x 1 + 3 x 2 unités de
M1, x 1 + x 2 unités de M2, 2 x 1 + x 2 unités de M3 .

Les disponibilités en matières premières montrent que le

schéma n’est réalisable que lorsque x1
et x2 vérifient
x1

Les inéquations : x1 +3x2 ≤

18

d-Le problème à résoudre est :

Trouver deux nombres x 1, x 2 tels que:

1- x 1 ≥ 0, x 2 ≥ 0 x 1 + 3 x 2 ≤ 18

x 1 + x 2≤ 8

x1 1 3 18

Soit le s matrices: X= , A= 1 1 , B =8

C = (c1, c2) le problème s’écrit matriciellement sous la forme:

Trouver X ≥ o tel que A x ≤ B et C x maximum ; ce que nous

noterons

x0

A   b
 c   z (max)

2.2 - Un deuxième exemple-type: Minimisation d’un coût: Dans
une raffinerie, la distillation de deux types de pétroles bruts B 1 et B2 fournit 3
qualités d’essences E1, E2 et E3.
INT1801/ RECHERCHE PROPRIETE CNFEPD
SEMESTRE II OPERATIONNELLE 8
La raffinerie doit approvisionner un distributeur d’essences ; le problème consiste à
déterminer le meilleur schéma de distillation, c'est-à-dire les quantités de bruts à
distiller telles que :

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 9
 1-Les quantités d’essences obtenues satisfont la demande ;
2-Le coût des quantités de bruts est minimum.

Modèle mathématique:

a-Données numériques de contraintes :

-
La demande du distributeur est : 500 litres de E1, 400 litres de E2 et 600 litres de E3 ;
-
La distillation de B1 et B2 fournit respectivement :

B1 : 10% de E1, 10% de E2, et 30%

de E3. B2 : 50% de E1, 20% de E2,
et 20% de E3.

b-Hypothèses de linéarité du modèle :

(L1) linéarité des contraintes :On suppose que la qualité des bruts est toujours
la même, et que la distillation s’opère à rendement constant.

Exemple 1 :

La distillation d’un m3 de B1 produit 0,1 m3 de E1, 0,1 m3 de E2, et 0,3 m3 de E3.

La distillation de x1 m3 de B1 produit alors 0,1 ×1 m3 de E1 et alors 0,1x1 m3 de E2

et 0,3 x1 m3 de E3.

(L2) Linéarité de la fonction économique : Les coûts des bruts sont de 20 $ /

m3 pour B1 et de 25 $ / m3 pour B2 ;

On suppose une fois de plus qu’il n’y a pas de tarif dégressif.

c- Réalisabilité d’un schéma de distillation :

x1
Un schéma de distillation est un couple désignant les quantités
x2

(en m3) de B1 et B2 distillés; il doit évidemment vérifier les contraintes x 1 ≥ o et x

2 ≥ o ; un tel schéma est réalisable lorsqu’il permet de satisfaire la demande du

distributeur. Pour cela x 1 et x 2 doivent vérifier :

0,1 x 1 + 0,5 x 2 ≥ 0,5

0,1 x 1 + 0,2 x 2 ≥ 0,4

Remarques:

1-Attention aux unités ! La demande du distributeur indiquée plus haut est

exprimée en litres, les quantités de bruts sont en m 3 ;

2-Pour trouver les inéquations précédentes ; complétons, l’exemple précèdent : La

INT1801/ RECHERCHE PROPRIETE CNFEPD
SEMESTRE II OPERATIONNELLE 10
distillation de x 2 m3 de B2 produit 0,5 x 2 m3 de E1, 0,2 x 2 m3 de E2, 0,2 x 2 m3 de
E3. Donc la distillation de x 1 m3 de B1 et de x 2 m3 de B3 produit (0,1 x 1 + 0,5
x 2) m3 de E1 et (0,1 x 1

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 11
+ 0,2 x 2) m3 de E2,et (0,3 x 1 + 0,2 x 2) de E3. Ces quantités doivent être
supérieures ou égales à la demande.

d-Le problème à résoudre est :

Trouver deux nombres x 1 et x 2 tels que:

(P) x 1≥ 0 , x 2 ≥ 0

0,1 x 1 + 0,5 x 2 ≥ 0,5

0,1 x 1 + 0,2 x 2 ≥ 0,4

0,3 x 1 + 0,2 x 2 ≥ 0,6

Z = 20 x 1 + 25 x 2 est le plus petit possible

(Z représente le coût total des bruts distillés)

Matriciellement ce problème s’écrit :

Trouver X ≥ 0 tel que A X ≥ B et C X minimum avec :

x 
X=
  1 ;= A 0,10,5
0,1  ;= B
0,5
0,4 ;= C 20,25
0,2

x  
0,3 0,2 0,6
 2    

Ce que nous noterons :

X  0

A X  B
 C X  Z (min)

e-Changement d’unités: Formellement, d’un point de vue strictement
mathématique, le problème (P) peut s’écrire de manière équivalente sous la forme :

Trouver 2 nombres x1 et x2 tels que

(P′)
x 1≥ 0 ; x 2 ≥ 0

x1 +5x2 ≥5

x +2 x ≥4

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 12
3- Résolution par la méthode graphique:
Soit le modèle du 1er exemple :

x1 3 x  18

2

x1  x  8 x1  , x 0
 2 , 0
2

2 x1  x  14

C1 2  Z (max)
 1 2
 C x
2

Soit : C1 = 3 et C2 = 2 ;

Résoudre graphiquement ce modèle revient à trouver les valeurs de x 1 et x2 qui

vérifient le système d’inéquations et donne la plus grande valeur à la fonction
économique Z.

On construit d’abord les droites d’équations

respectives. x1 + 3 x 2 = 18
x1+x2=8
2 x 1 + x 2 = 14

Et éliminer, pour chacune de ces droites, le demi-plan dont les points ont des
coordonnées qui ne satisfont pas à l’inéquation correspondante.

Rappel: Toute droite D d’équation a x + by + c = o

L’expression a x + by + c est strictement positive dans l’un et négative dans l’autre, des d
parties :

a x + by +
Les points appartenant à la droite et ayant des coordonnées vérifiant
c = o.
Les 2 demi-plans délimités par (D) et dans lesquels, l’expressiona x + by + c
garde un signe constant (nous l’admettrons sans démonstration).

Pratiquement, on trace les droites et on utilise les coordonnées de l’origine (o, o)

pour chacune des inéquations afin de vérifier que le signe de la région contenant
ladite origine convient ou non au sens de l’inéquation. On hachure ensuite la partie
qui ne convient pas comme ci-dessous indiqué:

x1 2  0 x1
D1 : x 1 + 3 x 2 = 18 passe   B 
par A x  6 x 2
INT1801/ RECHERCHE PROPRIETE CNFEPD
SEMESTRE II OPERATIONNELLE 13


1
8



0



INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 14
 x1 8 x1  0
D2 : x 1 + x 2 =8 passe par   D  
C x  0 x  8
2 2

D3 : 2 x + x = 14 passe
x1  7 x1 0 
par E
1 2   F  
x 2  x  14 
0
2

x2

P;

H;

A
P
H
x1
O B
E C
Figure 1
(D1)
(D2)
(D3)

(OAPHE) contient

Toutes les solutions possibles (réalisables)

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 15
Les coordonnées des points intérieurs et sur les côté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 la fonction économique.

Z = 3 x1 + 2 x2 les coordonnées de chacun des points du domaine des solutions

réalisables, on obtient alors :

ZO = 3 (0) + 2 (0) = 0
ZA = 3 (0) + 2 (6) = 12
ZP = 3 (3) + 2 (5) = 19

ZH = 3 (6) + 2 (2) = 22 *
ZE = 3 (7) + 2 (0) = 21

L’optimum est atteint au point H avec :

x1 = 6
Un autres exemple: Soit le modèle (P/), comme il est à 2 inconnues, on peut
facilement
x2 = le
2 résoudre par la méthode graphique.

On construit d’abord les droites d’équations respectives :

x 1 + 5 x2 = 5
x 1 + 2 x2 = 4
3 x 1 + 2 x2 = 6

Et éliminer pour chacune de ces droites, le demi-plan dont les points ont des
coordonnées qui ne satisfont pas à l’inéquation correspondante.

D1 = x1 + 5 x2 = 5 passe par les points 0 5

A  , B  
1 0
   

D2 = x1 + 2 x2 = 4 0 4 
passe par les points   ,  
C 2 0
D
   

D3 = 3 x1 + 2 x2 = passe
6 par les points
E 0 2 
  , F  
3  0

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 16
 (D3)
1 10/3

G= ,H =

(D2)

(D1)

Figure 2

Remarque: Comme dans l’exemple précèdent, après avoir tracé les droites, on
utilise les coordonnées de l’origine (0,0) pour chacune des inéquations afin de
vérifier le signe de la région contenant ladite origine convient ou non au sens de
l’inéquation, on hachure ensuite la
 0
partie qui ne convient pas soit la première inéquation : x1 + 5 x2 ≥ 5, le point d’origine  
ne 0
 
vérifie pas cette inéquation car 0 + 5 (0) ≥ 5 n’est pas vérifiée, on hachure alors la
région qui contient ce point, dans la figure précédente la partie non hachurée
représente le domaine des solutions possibles (réalisables).

Quel est le point qui minimise le coût total des bruts distillés ? pour répondre à
cette question, on remplace dans la fonction économique : 20 x 1 + 25 x2 les
coordonnées de chacun des points : E, G, H, B

ZE = 20 (0) + 25 (3) = 75 $

ZG = 20 (1) + 25 (3/2) = 115/2 = 57,5$ *

ZH = 20 (10/3) + 25 (1/3) = 225/3 =

75 $ ZB = 20 (5) + 25

(0) = 100 $
1 
Le minimum est atteint au point  G =
3/ 2
INT1801/ RECHERCHE PROPRIETE CNFEPD
SEMESTRE II OPERATIONNELLE 17
  

x1 = 1

x2 = 3/2

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 18
Remarque: Comment calculer un point d’intersection entre deux droites ? Il
suffit de résoudre le système d’équations constitué des équations des 2 droites.
Prenons l’exemple de la figure 2.

Le point d’intersection H entre les deux droites (D 2) et (D1) : le calcul des

coordonnées du point H consiste à résoudre le système d’équations :

x1  5 x2  x  10/3
   1
5
x1  2 x 2  x  1/3
4 2

CONCLUSION:
Nous avons appris à modéliser un problème de maximisation ou de minimisation et
de le résoudre par la méthode graphique, modéliser un problème consiste à
l’exprimer par un modèle mathématique qu’on appellera, dans la leçon suivante, un
programme linéaire. La résolution par la méthode graphique n’est facile que si le
modèle contient au plus deux inconnues.

Dans la leçon suivante on introduira une méthode de résolution quand le modèle

est à plus que deux inconnues.

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 19
EXERCICES CORRIGÉS :
EXERCICE N°1:
Résoudre graphiquement les programmes linéaires suivants
Max Z x1  2 x
Max Z2 3x

Min Zx  x
x
 2

 1 2
  3 x1  2 x 2   1 2
 x1  2 x  4
2   2x  x2  2
2 1
(P1) (P2)  x1  2x  4 (P3)
2 x1  x 2  x1  2 x 2 2
 4  2 
  
 x1  0 , x  x1  x 2  
  x1  x 2 5
2
x 5
0
 1  0 , x 
0
2

EXERCICE N°2 :
Un laboratoire pharmaceutique doit élaborer un fortifiant à l’aide de 3 produits P1,
P2, P3, des normes en vigueur imposent au fortifiant une teneur minimal en
vitamines V1 et V2, plus précisément 8 unités de V1 et 12 unités de V2. Les teneurs
en vitamines de chacun des produits sont :
P1 P2 P3
V1 3 1 8
V2 4 2 9

Les coûts unitaires de chacun des produits sont : C 1 = 24, C2 = 10, C3 = 72.
Evidemment, le laboratoire cherche à fabriquer son fortifiant au coût minimal, tout
en respectant les normes.

Exprimer ce problème sous forme d’un programme linéaire.

NB: Il n’est pas demandé de résoudre le programme linéaire.

EXERCICE N°3:
Soit deux produits P1, P2 fabriqués sur deux machines M1, M2 la production d’une
unité de P1 exige 4 heures machines sur M1 et 2 heures machines sur M2, La
production d’une unité de P 2 exige 8 heures machines sur M 1 et 2 heures machines
sur M2.

M1 M2 Profit unitaire
P1 4 2 4
P2 8 2 6
INT1801/ RECHERCHE PROPRIETE CNFEPD
SEMESTRE II OPERATIONNELLE 20
 Disponibilité 84 24
s
des Mi

1- Modéliser mathématiquement ce problème sous forme d’un programme linéaire

noté (P) sachant que l’objectif est de maximiser le profit.

2- Résoudre (P) par la méthode gra

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 21
SOLUTION DES EXERCICES:
EXERCICE N°1:
Résolution de (P1):

On commence par tracer les droites d’équations respectives :

D1 : x1 + 2 x 2 = 4
passe par les points  20 4 
, B = 0
A=
   

D2 : 2 x1 + x2 = 4  
passe par les points 02
, D=
C=
 

x2

(D2)

(D1)

A E

O C B x1

Figure 3

Pour chacune des droites tracées, on hachure la partie du plan dont les points ne
vérifient pas l’inéquation correspondante (OAEC) décrit le domaine des solutions
réalisables, on l’appelle aussi le domaine d’acceptabilité.

On compare les points O, A, C et E, on remplace leurs coordonnées dans la fonction

économique.

ZO 2 + (0) =
= (0) 3 0
ZA 2 + (2) =
= (0) 3 6

ZC = 2 (2) + 3 (0) = 4

ZE = 2 ( 43 ) + 3 ( 43 ) = 20 / 3

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 22
 *

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 23
La meilleure solution est atteinte au 4 /
point E =
3 4


/3 
x1 =
4/3 x2
= 4/3 Z
= 20/3

Résolution de (P2) :

 0
 2 
La droite D1 : - 3 x1 + 2 x2 = 2 passe par les points A :   , B:  3

1   
 0
 0
  4
La droite D2 : - x1 + 2 x2 = 4 passe par les  , D:  
points C 2 0
:
   

La droite D3 : x1 + x2 = 5    
passe par les points E  50 , F:  05
x2
: X2
 2    
G
 ,
3 

(D3) (D3)

2 1

G ; H

(D2) Domaine
d’acceptabilité x1

(D1)
(D x1 Figure 4
2

-4-‫الشكل‬
(D1 Domaine
d’acceptabilité

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 24
ZO = 0 + 2 (0) = 0
ZA = 0 + 2 (1) = 2
ZF = 5 + 2 (0) = 5

ZG = 2 + 2 (3) = *
8

ZH = 1 + 2. 5/2 = 6
 
L’optimum est atteint au point 32
G=
 

x1 = 2
Résolution de
(P3): x2 = 3  0   1
D1 = - 2 x1 + x2 = 2 , B 0 
passe par les points
A  
2    

 0  2
D2 = x1 - 2 x 2 = 2 , D  
passe par les points   0

C 


D3 = x1 + x2 = 5    
passe par les points  50  05
, F
E
   

4 1

H; P

Domaine
d’acceptabilité

x1

D3 Figure 5

D1
INT1801/ RECHERCHE PROPRIETE CNFEPD
SEMESTRE II OPERATIONNELLE 25
(OAPHD) est le domaine des solutions réalisables.

- La valeur minimale de la fonction économique est atteinte au

point : ZO = 0 + 0 = 0
ZA = 0 + 2 = 0
ZG = -1 + 4 = 3

ZH = - 4 + 1 = - *
3
ZD = -2 + 0 = - 2

La solution optimale se trouve en H :

x1 = 4
EXERCICE N°2 :
x2 = 1
Soient x1, x2, x3 les nombres d’unités utilisées des produits P 1, P2 et P3
respectivement : x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

-
Chaque unité de P1 contient 3 unités de la vitamine V1, x1 unités de V1
contiennent 3x1 unités de la vitamine V1 ;

-
Chaque unité de P2 contient 1 unité de la vitamine V1 , x2 unités de P2 contiennent
x2 unités de la vitamine V1 ;

-
Chaque unité de P3 contient 8 unités de V1, x3 unités de P3 contiennent 8 x3 unités de V1.

Les normes en vigueur imposent au fortifiant une teneur minimale de 8 unités de

V1, c'est-à- dire : le fortifiant doit contenir 8 unités de V 1 ou plus ; soit :

3 x1 + x 2 + 8 x3 ≥ 8

De même, le fortifiant doit contenir au moins 12 unités de la vitamine V 2, D’après

les teneurs des 3 produits en V2, on a :

4 x1 + 2x2 + 9 x3 ≥ 12

La fonction économique à minimiser est 24 x1 + 10 x2 + 72 x3 , le programme

linéaire associé à ce problème est :

x1 0 x2  0 x3  0
 ; ;
3 x1  x  8 x3 8


2

2x  9x  12
 4 x1
2
3

2 x1 10 x 2  72 x 3
 4


INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 26
 Z(min)

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 27
EXERCICE N°3:
1-Modéliser le problème consiste à exprimer les contraintes (sur les heures de
disponibilité des machines) et la fonction économique (qui est le profit à maximiser)
en fonction des inconnues x1, x2 nombres d’unités de P1, P2 à produire
respectivement.

-
Si on décide de produire x1 unités de P1 , et x2 unités de P2, on a besoin de 4 x1 + 8
x2 heures machines sur M1, et 2x1 + 2x2 heures machine sur M2.

-
Comme le temps de disponibilité des machines est limité : 84 heures sur M 1 et 24
heures sur M2, on a les contraintes suivantes :

4 x1 + 8 x2 ≤ 84
2 x1 + 2x2 ≤ 24

- Le profit réalisé est : 4 x1 + 6 x2 qui est la fonction économique à maximiser :

x1 0 x2  0
 ;
4 x1 8x  84
Alors  2
 24
:  2x
 2 x1 2

 4 x1  6 x  Z (max)
2

Est le programme linéaire associé à ce problème.

2- Résolution par la méthode graphique :

x2

x2
D2

(D2) D1

(D1)

Domaine
d’acceptabilité

B x1

INT1801/ RECHERCHE Figure 6 PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 28
Tracés des droites :
0   21
D1 : 4 x1 + 8 x2 = 84 passe par les  , B  
points A

10,5 0 
0  12 
D2 : 2 x1 + 2 x2 = 24 , D  
passe par les points
C  
12  0 

Calcul de la meilleure solution

: ZO = 4 (0) + 6 (0) = 0
ZA = 4 (0) + 6 (10,5) = 63

ZE = 4 (3) + 6 (9) = 66
*

ZD = 4 (12) + 6 (0) = 48
x1 = 3 ; x2 = 9

L’optimum est donc atteint au point E : Z = 66

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 29
LEÇON N°02 : ÉLÉMENTS DE LA THÉORIE DES
GRAPHES

OBJECTIF PÉDAGOGIQUE : À LA fin de cette leçon, le stagiaire doit être

capable de définir un graphe, un chemin, et un circuit, et de déterminer les niveaux
de génération dans un graphe sans circuit.

PLAN DE LA LEÇON :

INTRODUCTION

I- QU’EST-CE QU’UN GRAPHE ?

1- Définition
2- Exemple

II - VOCABULAIRE DE LA THÉORIE DES GRAPHES

III- CONCEPTS NON- ORIENTÉS

IV- RECHERCHE DE NIVEAU DANS UN GRAPHE SANS CIRCUIT

1-Définition de niveau de génération
2-Méthode de détermination des niveaux de chaque sommet à partir d’un exemple

V- CONCLUSION

EXERCICES

CORRIGÉS

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 30
INTRODUCTION :
On regroupe généralement sous le titre de théorie des graphes des problèmes
assez variés qui ont tous comme caractéristiques communes de pouvoir être
visualisés : des points représentant des individus, des objets, des situations…..; sont
joints par des flèches ou des lignes symbolisant les relations existants entre eux.
Jusqu’au milieu du 20ème siècle, la théorie des graphes s’est développée en liaison
avec des problèmes de physique et chimie, mais aussi dans le cadre de recréations
mathématiques (jeux). Ce n’est qu’après 1945 qu’on vit apparaître des applications
dans le domaine de la gestion, classées avec beaucoup d’autres, sous le titre
général de problème de recherche opérationnelle.

À la fin de ce cours le stagiaire doit être capable de définir un graphe, un chemin, et

un circuit, et de déterminer les niveaux de génération dans un graphe sans circuit.

I - QU’EST-CE QU’UN GRAPHE ?

Il convient de distinguer les graphes orientés de ceux qui ne le sont pas. Nous nous
intéressons ici aux premiers et nous donnerons par la suite quelques exemples des
seconds.

1- Définition :
Les graphes orientés que nous traiterons dans cette leçon peuvent être considérés
comme des schémas représentant simplement la structure d’un problème. Ils sont
généralement déterminés par la donnée de :

a-Un ensemble X  x1, x2 ,...xn  d’éléments appelés sommets du graphe ; Si X

fini possède n

éléments distincts, le graphe sera dit d’ordre n.

b-Un ensemble fini U  u , u ,...., u , dont les éléments sont des couples
1 2
ordonnés de sommets appelés arcs.

U est donc une famille d’éléments du produit

cartésien X  X  x, y/x X, YX.

Exemple :Le graphe G(x, u) suivant, présente les résultats d’un tournoi d’échecs =
les sommets x1, x2, x3, x4 représentent les 4 concurrents, et l’existence d’un arc (x i,
x j) ou plus exactement la présence dans 4 de l’arc (x i, xj) indique que le joueur x i a
remporté la partie unique l’opposant au joueur x j.

x1
X3

INT1801/ X2 RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE X4 31
 X  x1 , x 2 , x 3 , x 4 
U  x1 , x 2 , x1 , x 4 , x 2 , x 3 , x 2 , x 4 , x 3 , x1 , x 3 , x 4  

II-VOCABULAIRE DE LA THÉORIE DES GRAPHES :

Voici, quelques définitions de base relatives aux arcs et aux sommets d’un graphe G (X,U).

1- Extrémités d’un arc :

Un arc u = (x, y) possède une extrémité initiale x et une extrémité terminale y.

2- Boucle :
Une boucle est un arc dont les deux extrémités coïncident, elle est de la forme (x, x).

3- Arcs adjacents (voisins) :

Deux ou plusieurs arcs sont dits adjacents, s’ils ont au moins une extrémité en commun.

Exemple : Dans le graphe précédent les arcs (x 1, x2) et (x3, x2) sont voisins, les
arcs (x1, x4), (x2, x4) et (x3, x4) sont eux aussi voisins ou adjacents.

4- Successeur :
On dit qu’un sommet y est un successeur d’un sommet x, s’il existe un arc ayant x
comme extrémité initiale et y comme extrémité terminale. L’ensemble des
successeurs d’un sommet x est noté T +(x).

Exemple : Dans le graphe précédent ; x4 est successeur du sommet x1 ; x1 n’est

pas successeur de x2 car il n’existe pas un arc (x2, x1).

5- Prédécesseur :
On dit qu’un sommet y est un prédécesseur du sommet x , s’il existe un arc ayant y
comme extrémité initiale et x comme extrémité terminale. L'ensemble des
prédécesseurs d’un sommet x est noté T– (x).

Exemple : Dans le graphe précèdent ; x1 est un prédécesseur du sommet x2 ; x1

n’a pas de prédécesseur.

Remarque :
- Si x est prédécesseur de y alors y est successeur de x ;
- Dans quelques ouvrages, vous pouvez trouver que le mot prédécesseur est
remplacé par précèdent.

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 32
6- Sommets adjacents (voisins) :
Un sommet x est adjacent au sommet y, s’il est prédécesseur ou successeur de y.
Ces sommets peuvent aussi être qualifiés de voisins, on peut aussi dire que deux
sommets sont voisins s’il existe un arc qui les relie. On note par T(x) l’ensemble des
sommets voisins de x, T(x) = T +(x) U T – (x).

Exemple :Dans l’exemple précédent :

x1 x2 x3 x4
T x 2 , x 3 , x 4  x3 , x 4  x 4  
 φ x1 x1 , x 2  x1 , x 2 , x 3 
T x 2 , x 3 , x 4  x1 , x 3 , x 4  x1 , x 2 , x 4  x1 , x 2 , x 3 

T

7- Sommet isolé :
Un Sommet isolé est un sommet qui n’a pas de voisins.

8- Chemin :
Un chemin est une suite d’arcs dont l’extrémité terminale de chacun est l’extrémité
initiale du suivant, sauf pour le dernier.

Exemple :Dans le graphe suivant :

x1
X3

X5

X2

X4

x1 , x 3 , x 5 , x est un x1 , x 3 , x 4 , x 2 est un autre chemin.

4 chemin ;

Le Le chemin
x1 , x 3 , x 5 , x 4  est formé des arcsx1 , x 3 
chemin
x1 , x 3 , x 4 , x 2  est formé des arcs x1 , x 3 

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 33
x 3 , x 5  , x 5 ,
x 4 .

x ,x  , x ,
x .
3 4 4 2

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 34
Un chemin peut donc être défini soit par la suite des sommets qu’il contient, soit
par la suite d’arcs qui le composent.

Remarque : Si dans un chemin, l’extrémité initiale du premier arc coïncide avec

l’extrémité terminale du dernier arc, on parlera alors de circuit.

Exemple :Dans le graphe x1 , x 3 , x 4 , x 2 , est un x1 , x 4 , x 2 , x1 est un

précédent circuit. x1  circuit, 
III - CONCEPTS NON ORIENTÉS :
Si entre deux sommets x,y d’un graphe, il existe un arc (x,y) et un arc (y,x) , il peut
intuitivement paraître plus simple de remplacer ces deux arcs par un lien sans
orientation. Si cette situation se produit pour tous les couples de sommets, il n’y a
plus aucune orientation à en considération. On considère alors au lieu de l’arc (x,y),
l’ensemble formé par les points x,y qu’on note e = (x y) et qu’on appelle arête.

Le graphe non orienté est noté G(X, E) où X est l’ensemble des sommets et E
l’ensemble des arêtes.

IV-RECHERCHE DE NIVEAU DANS UN GRAPHE SANS

CIRCUIT :
1- Définition de niveau de génération :
Dans un graphe sans circuit, il est possible de numéroter les sommets du graphe de
telle sorte que le numéro affecté à chaque sommet soit inférieur à celui des
suivants (successeurs) et supérieur à celui des précédents (prédécesseurs) ; ce
numéro attribué à chaque sommet est précisément le niveau de génération ou
rang du sommet en question.

Les sommets de niveau 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 sommets de niveau 2 ont
des précédents de niveau 0 ou 1 et ainsi de suite.

2- Méthode de détermination des niveaux de chaque

sommet à partir d’un exemple :
Soit le graphe suivant :

f
a
b
g

d
c
e
INT1801/ RECHERCHE PROPRIETE CNFEPD
SEMESTRE II OPERATIONNELLE 35
La détermination du niveau de chaque sommet se fait en plusieurs étapes :

Étape N° 1 :On écrit le dictionnaire des précédents dans le tableau suivant :

X T– (x)
a b
b néant
c b,e,f
d a
e g
f g,e
g a

Étape N°2 : On recherche ensuite dans ce dictionnaire des lignes vides, il se

trouve qu’il n’y en a qu’une, en l’occurrence la ligne « b ».

Par conséquent, « b » n’ayant aucun précédent est donc un sommet de niveau 0, ce

que l’on note : N0 = b

On barre ensuite tous les « b » dans les colonnes X et T– (x) d’où le tableau N°1 suivant :

X T– (x)
a néant
c e,f
d a
e g
f g,e
g a

On constate que la ligne « a » devient vide donc « a » est de niveau 1 soit : N1 = a

Étape N°3 : On barre ensuite tous les « a » dans le tableau N°1, on obtient le
tableau N°2 suivant :

X T– (x)
c e,f
d néant
e g
F g,e
g néant

Les lignes « d » et « g » deviennent vides, d et g sont des sommets de

niveau 2, soit : N2 = d, g

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 36
Étape N°4 : On barre ensuite tous les « d » et « g » d’où le tableau N°3, suivant :

X T– (x)
c e,f
e néant
f e

La ligne « e » devient vide, à son tour, ce qui signifie que le sommet e est de niveau

3, soit : N3 = e

Étape N°5 : On barre tous les « e », d’où le tableau N°4 suivant :

X T– (x)
c f
f néant
La nouvelle ligne vide est la ligne « f », donc le sommet f est de rang 4, soit : N4 = f 

Étape N°6 :On barre ensuite tous les « f », et on obtient le tableau N°5 ci-dessous :

X T– (x)
c néant

La ligne du sommet c étant vide, le sommet c sera de niveau 5,

soit enfin : N5 = c

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

N0 = b
N3 =
N 1 = a 
e  N4
N2 = d,
= f 
g N5 =
c 
Cette détermination des niveaux du graphe, va nous permettre de représenter le
graphe précédant par un graphe plus lisible et plus facile à exploiter, car
ordonnancé par niveau de génération.

b
d
a f c

e
g

N0 N5
N1 N2 N4
N3
INT1801/ RECHERCHE PROPRIETE CNFEPD
SEMESTRE II OPERATIONNELLE 37
Ce graphe est identique au premier, sauf que la connaissance des niveaux de
chaque sommet a fait que sa représentation soit plus lisible que celle du 1 er graphe.

V- CONCLUSION : UTILITÉ DU CONCEPT DE

GRAPHE EN RECHERCHE OPÉRATIONNELLE :
Un graphe peut représenter toutes sortes de situations dans les phénomènes
d’organisation. Par exemple, un réseau (c'est-à-dire un graphe comportant une
entrée et une sortie) peut correspondre à des canalisations où circule un fluide
(liquide ou gaz).

Dans ce cas là, les quantités entrantes (par exemple par unité de temps) en un
sommet doivent être égales aux quantités sortantes (par unité de temps) en ce
même sommet. Il est facile, en effet, de comprendre que si trois canalisations
apportent en un sommet A des débits respectifs de 2,3 et 1 litres/mn.

Soit en tout 6L/mn(1), les canalisations qui partent de A doivent avoir un débit total de
6L
/mn. Mais un graphe n’est pas toujours un réseau représentant des circulations
quelconques.

2
4
3 A 2
1

Souvent, une flèche entre deux points, implique seulement une relation de
succession par exemple, le graphe suivant peut valoir dire seulement que A
précède B qui lui-même précède C.

B C
A

On dit qu’un graphe est value si, à tout arc qui le constitue, correspond une valeur
numérique qu’on écrit seulement sur la figure, à proximité de cet arc. Ces valeurs
peuvent être des quantités, transportées, des débits, des coûts,
des durées, etc….

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 38
EXERCICES CORRIGÉS :
EXERCICE N°1 :
Soit le graphe G = (X,U) donné par sa représentation dictionnaire restreinte aux
prédécesseurs des sommets (voir tableau 1).

X 1 2 3 4 5 6 7 8 9 10
précéde – 1, – 1 3 8, 2,5 2,4, 4 7,8,
nts 3 9 5 9

- Dresser le graphe puis déterminer les niveaux de génération du graphe.

EXERCICE N°2 :
Soit un ensemble E =

0,2,6,18,9,11. On définit dans E la

relation par:

xRy x  E, y  E, (x est multiple de y ) et y).

 (x 

1-En utilisant les concepts de la théorie des graphes, proposer une représentation
de cette relation : définir l’ensemble des sommets X, celui des arcs U et dresser G
= (X, U).

2-En utilisant le vocabulaire de la théorie des graphes que représente :

a-Un nombre premier.

b-Le sous-ensemble des éléments de E multiples d’un élément x de E.

c- Le sous-ensemble des éléments de E qui divise un élément x de E.

d-Le cardinal de E.

3-Donner le dictionnaire des prédécesseurs (précédents) du graphe obtenu.

Notes :

- Un nombre premier est un nombre qui n’est divisible que par 1 et lui-même :
ex : 3, 7, 17,47….

- Le cardinal d’un ensemble est le nombre d’éléments qu’il contient. Le

cardinal de l’ensemble L = 0,3,5 est 3 ; le cardinal de l’ensemble vide est égal à
zéro.

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 39
EXERCICE N°3 :
- Donner un ordonnancement par niveau des graphes suivants :

2 7

1
5
6

G
B

Présenter les graphes sous forme plus lisible, les sommets étant disposés selon
leurs niveaux respectifs.

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 40
SOLUTION DES EXERCICES :
EXERCICE N°1 :

9
4

8 6
1

7
10

Détermination des niveaux de génération :

Étape n°1 :D’après le dictionnaire des précédents, les sommets 1 et 3 sont de
niveau 0, car ils n’ont pas de prédécesseurs, soit N0 =

Étape n°2 :On supprime les sommets 1 et 3 du tableau, ce qui permet d’obtenir
le tableau suivant :

X précédents
2 /
4 /
5 /
6 8,9
7 2,5
8 2,4,5
9 4
10 7,8,9

Les sommets de niveau 1 sont : N1 = 2,4,5.

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 41
Étape n°3 : En supprimant les sommets de niveau 1 du tableau, on a :

X P(x)
6 8,9
7 /
8 /
9 /
10 7,8,9

Les sommets de niveau 2, sont N2 = 7,8,9.

Étape n° 4 :Ceci permet d’obtenir le tableau suivant :

X P(x)
6 /
10 /

Les sommets du dernier niveau (3) sont N3 =

6,10 . On a les niveaux de générations

suivants :

N0 =1,3.
N1 =
2,4,5. N2
= 7,8,9.
N3 =6,10
.

EXERCICE N°2 :

1- La représentation de l’ensemble E ainsi que celle de la relation par un

graphe G = (X,U) peut être faite de la manière suivante :
X=
E
U= x, y/ xX, yX, x est multiple de y et x  y

18
2
0

INT1801/ RECHERCHE
9
PROPRIETE CNFEPD
SEMESTRE II 11 OPERATIONNELLE 42
 X  0,2,6,18,9 ,11
Ainsi
U  0,2, 0,6, 0,18, 0,9, 0,11, 6,2, 18,2, 18,6, 18,9
:

2-
a- Un nombre premier n’a pas de successeurs ;
b- Le sous ensemble des éléments de E multiples d’un élément x de E
représente l’ensemble des prédécesseurs de x dans le graphe.

Exemples : Les multiples de 2 ; 6 et 18 sont les précédents du sommet dans le graphe.

c- Le sous ensemble des éléments de E qui divisent un élément x de E

représente l’ensemble des successeurs de x.

Exemple : Les diviseurs de 18 sont 2, 6,9 et ce sont ces successeurs

dans le graphe d- Le cardinal de E (qui est égale à 6) est l’ordre du

graphe.
3-
X précédents
0 /
2 0, 6,18
6 0,18
9 0,18
18 0
11 0

EXERCICE N°3 :
Pour le graphe1, présentons le dictionnaire des précédents :

X P(x)
1 /
2 1
3 1,2,5
4 3,5
5 1
6 3,4
7 2,3

Les sommets de niveau 0 sont : N0 = 1, on supprime ce sommet du tableau ce qui donne
:

X P(x)
2 /
3 2,5
4 3,5
5 /

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 43
 6 3,4
7 2,3

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 44
Les sommets de niveau 1 sont : N1 = 2,5, la suppression des ces sommets, permet
d’obtenir le tableau suivant :

X P(x)
3 /
4 3
6 3,4
7 3

L’ensemble N2 =3, sa suppression du tableau donne :

X P(x)
4 /
6 4
7 /

On peut facilement déduire du tableau que N3 = 4,7et

N0 = :1 N1 = 2,5
N4 = 6. Soit
N2 = 3

2 7

1 6

Pour le deuxième graphe, représentons aussi le dictionnaire des précédents :

X P(x)
A E
B A,E,D
C D,B,H
D E
E /
F E,D
G A,B ,C
H F,D

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 45
N0 = E et le nouveau tableau est le suivant :

X P(x)
A /
B A,,D
C D,B,H
D /
F D
G A,B ,C
H F,D

N1= A, D sa suppression du tableau permet d’obtenir le tableau suivant :

X P(x)
B /
C B,H
F /
G B ,C
H F

N2
B, F , On supprime ces 2 sommets du tableau ce qui permet d’obtenir le
=
tableau
suivant :

X P(x)
C H
G C
H /

N3 =H , N4 = Cet N5 = G peuvent être déduits de la même

façon. L’ordonnancement par niveau de ce graphe est :

N0 = E

N1 = A,

D N2 =
A
B, F E
B
G
C

H
D

F
N0 N5
N1 N3 N4
N2
INT1801/ RECHERCHE PROPRIETE CNFEPD
SEMESTRE II OPERATIONNELLE 46
LEÇON N°03 : PROGRAMMATION LINEAIRE : LA
METHODE DU SIMPLEXE

OBJECTIF PÉDAGOGIQUE : À la fin de cette leçon, le stagiaire doit être

capable d’écrire un programme linéaire sous forme canonique, sous forme standard
et de résoudre un programme de maximisation par la méthode algébrique et la
méthode du simplexe.

PLAN DE LA LEÇON :

INTRODUCTION

I - NOTATION GENERALE D’UN PROGRAMME LINÉAIRE

II - FORMES CANONIQUE ET STANDARD D’UN PROGRAMME LINEAIRE

1-Notion de forme canonique.

2-Forme standard
3-Introduction de variables d’écart et de variables artificielles.

III- METHODES DE RESOLUTION DE MAXIMISATION

1-Méthode algébrique de substitution
2-Présentation pratique (Méthode du simplexe)

CONCLUSION

EXERCICES

RESOLUS

BIBLIOGRAPHIE

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 47
INTRODUCTION :
Les problèmes de la programmation linéaire se posent lorsque l’on cherche à rendre
optimum (minimum ou maximum) une fonction linéaire 1 de plusieurs variables, ces
variables étant assujetties à des contraintes linéaires, c'est-à-dire, du premier
degré. Soulignons, à ce propos qu’une contrainte est linéaire, lorsqu’elle s’exprime
par une égalité ou inégalité dont le premier membre est une combinaison linéaire
ou forme linéaire des variables et le second un nombre réel.

Afin d’étudier le programme linéaire, vous devez avoir des notions sur la résultions
du système d’équation linéaire par la méthode de substitution.

I - NOTATION GENERALE D’UN PROGRAMME LINEAIRE

:
Soient les deux programmes linéaires suivants :

1- Trouve x  0 , x  0,...,x  0,...,x  0 tels que :

1 2 i n
r

…………………………………………

Et rendant :

c1x1  c2 x2 ..... ci xi ...... cn xn Maximum.

Remarque : On appellera b1, b2, bm, le second membre

2- Trouve x  0 ; x  0 ;......x  0 ;........x  0 tels que :

1 2 i n
r

………………………………………………

Et rendant :

c1x1  c2 x2 ..... ai xi ...... cn xn Minimum

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 48
En utilisant les notations matricielles, on peut abréger l’écriture de ces
programmes linéaires :

1
On a appelé cette fonction, la fonction économique.

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 49
 Trouver
Programme N° 1

Trouver
Programme N° 2

Où

B= X=
A=

.. . . B
.. . .
.. . .

C=

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

a- D’inconnues appelées «variables non-négatives » :

x1  0 , x 2  0.........xn Dans le 1er et le 2ème programme.

0

b - D’équations ou inéquations au nombre de m : tenant lieu de contraintes et que

doient vérifier les n variables, chacune des équations ou inéquations étant une
combinaison linéaire du 1er degré par rapport aux variables non négatives.

Exemple :

c -D’une « fonction économique » à maximiser ou à minimiser ;

Ex : c1x1  c2x2 .....ci xi ......cn xn  Z dans laquelle les coefficients Ci peuvent
être positifs, négatifs ou nuls.

De 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 indépendantes et
formant un système d’équations et inéquations appelées contraintes.

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 50
II - FORMES CANONIQUE ET STANDARD D’UN
PROGRAMME LINEAIRE :
L’objectif de ce paragraphe est de définir les formes d’un programme linéaire, ces
dernières seront utiles pour introduire une autre méthode (dite du simplexe) pour la
résolution d’un programme linéaire.

1-Notion de forme canonique :

Lorsque l’ensemble de contraintes se présente sous forme d’inégalités
ou parle de
 , ou 
forme canonique.
Toutefois, il convient de distinguer un programme canonique de type I d’un
programme canonique de type II.

a - Un programme canonique de type I :Est un programme dans

lequel les contraintes inégalités sont tournées dans le sens « inférieur ou égal »,
l’objectif recherché étant la maximisation de la fonction économique.

b - Un programme canonique de type II : A des contraintes inégalités

tournées dans le sens « supérieur ou égal » l’objectif est un minimum.

Exemples :

* Forme canonique de type I * Forme canonique de type II

c- Notion de forme mixte :Parfois, les contraintes sont tournées les unes
dans un sens, les autres dans le sens opposé, l’objectif pouvant être soit un
maximum soit un minimum.
Mais on peut également avoir un mélange d’égalité (=) ou d’inégalités  ou . Un
tel
programme est un programme mixte. On dit aussi qu’il se présente sous forme

mixte. Exemples de formes mixtes ou de programmes mixtes :

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 51
2- Forme standard :
Dans un programme écrit sous forme standard, toutes les contraintes représentent
des égalités. L’objectif pouvant être le maximum ou le minimum.

Exemples :

La forme canonique s’avère plus pratique dans le cadre de la résolution par la

méthode graphique. Quant à la forme standard, elle n’apparaît intéressante que
dans les méthodes matricielles et plus particulièrement dans la méthode du
simplexe que G.B Dantzig développa à partir de 1948, et qui demeure encore la
méthode la plus efficace.

Soulignons enfin que dans la méthode du simplexe, tous programme se présentant

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

3- Introduction de variables d’écart et de variables

artificielles (dans la méthode du simplexe) :
Le problème de l’introduction de variables d’écart et de variables artificielles ne
peut se poser que lors du passage de la forme canonique à la forme standard et
dans le cadre de la méthode du simplexe. Les exemples suivants permettront
certainement de cerner tous les aspects du problème. Nous appellerons VR =
variables réelles ; VE = variables d’écart ; VA = variables

artificielles.

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 52
Forme Canonique Forme Standard Correspondante
x1  0 x2  0
20x 1  30x 2  240 x1  0 x2  0 x3  0 x4  0 x5  0
 V.R V.E
10x 1  25x 2  500
N°1 15x  40x  550 N°1 20x 1  30x 2  x 3  240
 1 2
10x 1  25x 2 x4  500
Max150x 1  200x 2 
15x 1  40x 2 x5 
550 Max150x 1  200x 2  0x 3  0x 4  0x
5 
x1  0 x 2  0 x1  0 x 2  0 x3  0 x 4  0x5  0 x 6  0
V.R V.E
5x1  3x 2  15 V.A

2x  4x 8
N°2  1 2
N°2
 5x 1  3x 2  x 3  15
x x 4
 1 2
2x 1  4x 2 x4 8
Max10x1  20x2 
x1  x 2 x5 x6
4 Max10x 1  20x 2  0x 3  0x 4  0x 5 
Mx 6 

x 1 0 x 2 0 x1  0 x 2  0 x3  0 x4  0
3x 1 5x 2  15

2x  3x  12 V.R V.E V.A
N°3
 1 2
N°3

Max 5x 10 x 
1 2 3x1  5x 2  x3  15

2x  3x x  12
 1 2 4

Max5x1 10x 2  0x 3  Mx 4 

x1  0 x2  0 x3  0 x 4  0 x5  0
x1  0 x 2  0
V.R V.E V.A
N°4 4x1  8x 2  24
 N°4
8x  2x  16 4x1  8x 2 - x3  x 4  24
 1 2 
8x1  2x 2  x 5  16
Max10x1  8x2  Max10x 1  8x 2  0x 3  Mx 4 - Mx 5 

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 53
 x1  0 x 2  0 x1  0 x2  0 x3  0 x4  0 x5  0 x6  0

V.R V.E
7x V.A
N°5  1  2x 2  14 N°5
8x  16x  16
 1 2

2x  5x  10
 1 2

Max 20x 1  15x 2 

INT1801/ RECHERCHE PROPRIETE CNFEPD

SEMESTRE II OPERATIONNELLE 54
 7x 1  2x 2  x 3 x5  14

8x 1  16x 2 x4  16
2x  5x  x  10
 1 2 6

Max20x 1  15x 2  0x 3  0x 4  Mx 5  Mx 6 

x1  0 x 2  0 x3  0 x1  0 x2  0 x3  0x4  0 x5  0 x6  0

8x 1  5x 2  10x 3  50 V.R V.A


N°6 7x 1  8x 2  5x 3  40 N°6 8x 1  5x 2  10x 3  x 4  50
3x  15x  5  50 
 1 2 X3 7x 1  8x 2  5x 3 x5  40
Max 10x 1  20x 2  30x 3  3x  15x  5x  x  50
 1 2 3 6

Max10x 1  20x 2  30x 3  Mx 4  Mx 5  Mx 6 

x1  0 x 2  0 x1  0 x2  0 x3  0 x4  0 x5  0 x6  0

V.R V.E V.A

N°7 5x 1  6x 2  10 N°7

2x  7x  14 5x1  6x 2  x 3  x 5  10
 1 2 
Min 3x 1  10x 2  2x1  7x 2 x4 x6  14
Min 3x1  10x 2  0x 3  0x 4  Mx 5  Mx 6 

x1  0 x2  0 x3  0 x4  0 x5  0
x1  0 x 2  0
V.R V.E V.A
10x1  9 x2  21
N°8  N°8
5x  12x  13 10x1  9 x 2 - x 3 x5  21
 1 2

Min x1  3x 2  5x1  12x 2 x4  13
Min x1  3x 2  0x 3  0x 4  Mx5 

x1  0 x2  0 x3  0 x1  0 x2  0 x3  0 x4  0 x5  0 x 6  0 x7 
0
3x1  5x 2  10x 3  100 V.R V.E


4x  x  x  50 V.A
N°9  1 2 3
N°9
x  x  7x  - 20
 1 2 3 3x1  5x 2  10x 3 - x 4  x 6  100
Max 9x 1  2x 2  4x 3  4x  x  x x  50
 1 2 3 5
x  x  7x  x  - 20
 1 2 3 7

Max 9x 1  2x 2  4x 3  0x 4  0x 5  Mx 6  Mx 7 

INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 42

 x1  0x2  0 x3  0 x 4  0x5  0 x 6  0 x 7  0 x8
x1  0
2x V.R V.E
 1  x2 5
x  2x  10 V.A
 1 2
 N°
3x  7x 3
N°10  1 2
10 2x  x  x x 5
Min 10x 1  x2  1 2 3 6

x1  2x 2 x4 x7  10

3x  7x x x 3
 1 2 5 8

Min 10 x1  x 2  0x 3  0x 4  0x 5  Mx 6  Mx 7  Mx
8 
 On voit à travers ces exemples que les variables artificielles interviennent
exclusivement dans les contraintes égalités (=) ou inégalités tournées dans le sens
« supérieur ou égal à », le second membre étant positif et l’objectif pouvant être le
maximum ou le minimum.

 Si l’objectif est un minimum, les variables artificielles sont accompagnées d’un

coefficient positif M, dans la fonction économique. Si par contre il s’agit d’une
maximisation, les variables artificielles devront être accompagnées dans la fonction
économique, d’un coefficient négatif que l’on convient de noter –M avec M 0 .

 D’autre part, toutes les contraintes de la forme :

a11x1  a12x2 ........ a1nxn  q1

Deviennent des équations dans la forme standard et exigent l’introduction de

variables d’écart affectées d’un (+1), que l’objectif soit un minimum ou un
maximum. Dans la fonction économique ces variables d’écart seront accompagnées
d’un coefficient nul quelque soit l’objectif. Car elles représentent des écarts ou
marges ou encore des bénéfices unitaires de productions fictives (dans le cadre de
la fabrication par exemple). Soulignons enfin que les contraintes du type (≤)
n’exigent que la présence de variables d’écart et jamais de variables artificielles et
ceci indépendamment de l’objectif envisagé.

Par contre, les contraintes de la a11x1  a12x2 .........a1nxn  q1

forme :

Requièrent la présence de variables d’écart et de variables artificielles. Les

variables d’écart sont affectées d’un (-1) et les variables artificielles d’un (+1)
quelque soit l’objectif.

Mais dans la fonction économique on aura un coefficient nul pour la variables

d’écart et (-M) pour la variable artificielle si l’objectif est un maximum ; et dans le
cas contraire, la variable d’écart sera toujours affectée d’un coefficient nul dans la
fonction économique tandis que la variable artificielle est affectée d’un (+M).

Terminons en soulignant que les contraintes de type (=) n’admettent point de

variables d’écart mais seulement de variables artificielles affectées du signe
INT1801/ RECHERCHE PROPRIETE
correspondant à celui du second membre. Dans la fonction économique, on agit
exactement comme dans le cadre des inéquations sus-énoncées.

INT1801/ RECHERCHE PROPRIETE

III - METHODES DE RESOLUTION DE MAXIMISATION :
1- Méthode algébrique de substitution :

1.1- Principe de la méthode :

Étape 1 : Dresser la forme canonique du problème posé.

Étape 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.

Étape 3 : Poser la solution extrême de base en utilisant d’abord les variables

réelles comme variables non principales (qu’on appellera variables hors base ou
variables nulles).

Les autres variables non nulles obtenues, constituant les variables principales ou
variables dans la base. A ce stade la fonction économique est nulle.

Étape 4 : Passer à la 1ère itération (répétition) afin de trouver une solution de base
meilleure, c'est-à-dire améliorer la valeur de la fonction économique.

Pour y parvenir on sélectionnera une variable entrante et une variable sortante

selon les critères de Dantzig suivants :

a - Critère d’entrée :La variable entrante est une variable hors base qui dans la
fonction économique présente le coefficient positif le plus élevé.

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

Étape 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 suivant à l’aide de la méthode de substitution :

S1

Le programme linéaire (S1) est déjà sous forme canonique, pour avoir la forme
standard, il
s’agit seulement d’ajouter des variables x3  0 , x 4  0 , x5  0
d’écart

INT1801/ RECHERCHE PROPRIETE

 S2

- Recherche de la solution de base : En utilisant l’énoncé de l’étape 3 ; la

première solution de base (qu’on a appelé solution extrême), les variables réelles
(sont appelées hors
base ou non principales ou nulles). Ici x1  0 ; x 2  0
on a :

Les autres variables non nulles, sont les variables dans la base ; on déduit leurs valeurs
en remplaçant dans (S2).

De 1ère x  140
la
3
équation : De la x  104
4
2ème équation : De x 5  360
la 3ème équation :

A ce stade, la fonction économique est

nulle La solution extrême de base est :

HB : x1  0 , x 2 
0
B x 3  140
x 4  104
x 5  360

1ère Itération : C’est l’étape 4, le but est de trouver une solution de base meilleure
c'est-à- dire améliorer la fonction économique.

Pour choisir la variable entrante ; c’est l’une des variables hors base qui a le
coefficient positif le plus grand dans la fonction économique ; dans notre exemple :
c’est x1 .

Si entre dans la base ; elle ne sera plus nulle, quelle est la valeur à x1 :
x1 affecter à

À partir des équations (S2) ; on peut obtenir le système (S3)

 Équation d’échange
S3  x

 104  x
4
x1 2
INT1801/ RECHERCHE PROPRIETE
   360  5x
 3x 2
x 1

Or x2  car elle est hors de base , d'où :

0 la

INT1801/ RECHERCHE PROPRIETE

 x 3  140  2x 1
S4 x  104  x1
 4 360  5x
x 1

Or

Le niveau maximum à affecter à x1 est : x1  Min70,104,72   70. On affecte donc la

valeur 70 à x1; et on cherche la variable sortante. Ce sera celle qui s’annulera après
substitution de x1 par 70 .

La variable sortante est donc x 3

La nouvelle solution obtenue à partir de cette 1ère itération est :

HB x  0 ; x 3 
2ème Itération :Dans (S3) l’équation 2d’échange est celle qui fournit la variable sortante,
0
soit :
B x1  70
x 3  140  2x1  x 2 x 5  10
x 4  34
Dans cette équation, on exprime la variable entrante à l’aide de variables x 2 et x3
  7.70  4.0 
hors base soit : 490
1 1
x  70  x  x
1 3 2
2 2

On remplace ensuite cette nouvelle x1 dans les différentes équations de (S3) ce

expression de qui donne :
  1 1
x  104  70  
x  x x
 4  3 2 2
 2 1 21
 
x  360  5 70   x 3x
x
 5  3 2 2
 1  1 2 2 
x  70  x  x
 1 3 2

 2 2

INT1801/ RECHERCHE PROPRIETE

  1
 34  x  1x
x
 52 3 12 2

 x  10  x
 5 3  x2
21 2
1
  70  x  x
x
 2
3
2
2
1

 1 1 
Z 7  70  x 3  x 2   4x 2
 2 2 

7 1
Z  490   x
2
x 2
3
2

On obtient donc le système :

 1 1
 34   x
2
x 2
x
 2 3


S5  Equation d’échange

 1
 x  70 1
x3  x2
 1
2 2

 7 1
 Z  490  x3  x2
 2 2

La variable entrante sera x 2 car elle possède le coefficient positif le plus élevé dans la
donc fonction économique.

Niveau à affecter
à x 2 (tout en maintenant x 3  0, car elle reste hors base).
 1
 34  x
x
 12 2
 x  10 x
  5 2
2

S6 
 x1  70 1
  x2
 1
Z  490 2 x

 2

x x1 1
 0   0  10  x
4
1 2
34  x 2
Or 1
2  0  70  x
2
x5
2
2
INT1801/ RECHERCHE PROPRIETE
0x2  20
0x2  68
0x2  140

x2  Min 68,20,140 20 ; La plus grande valeur qu’on peut

x 2 est la petite des
affecter à
valeurs 68, 20,140 donc x2  20.

INT1801/ RECHERCHE PROPRIETE

Détermination de la variable sortante :

 1
 34  20  24
x
 12

S7  x5  10 
2
20  0

 1
 x1  70  20 
 60
2
 Z  490 10  500

La variable sortante est donc x 5

Solution de la 2ème itération :

HB x3 0,x5 
L’équation d’échange0 est celle qui fournit la variable sortante, c’est
5 1
x  10   x B x1  60
x 2
2
x2 
5 3
2 20
4 
On utilise cette équationx pour
exprimer x 2 24 en fonction des nouvelles variables hors base :

x 2  20  2x 5  5x 3

On substitue cette expression dans

(S7) :
 x2  2x 5  20  5x 3
 1
 x4  34 1 2x 5  20  5x 3 
x3 - 2
 2

 1 1
 1x  70  x -  2x  20  5x 3 
 2
3
2 1
5
 Z  490
7 x   2x  20  5x 3 
 2 3 5
 2

 x2  2x 5  20  5x 3
S :  x4  24  2x  x5
3
8 
 x1  60  3x  x5
3
   500  x  x
 3 5

La fonction économique n’est plus composée que de coefficients négatifs. Il n’est

donc plus possible d’améliorer ni d’augmenter cette fonction économique. La
solution précédente est donc optimale.

INT1801/ RECHERCHE PROPRIETE

 HB : x 3  0 , x 5  0
B x1  60
x 2  20
x 4  24
  500

2- Présentation pratique (Méthode du simplexe) :

Elle a le principe de la méthode précédente, mais a l’avantage d’organiser tous les
systèmes d’équations sous forme de tableaux.

2.1- Principe de la méthode :

1-Obtenir la forme canonique.

2-Obtenir la forme standard.

3-Tableau n° 0 : Recherche de la solution extrême de base :

Les variables d’écart sont considérées au départ comme variables principales ou

variable dans la base.

Les variables réelles sont non principales et se trouvent hors de la base. La fonction
économique est alors nulle. Avec le tableau N° 0, on prépare le tableau N° 1 en
choisissant respectivement la variable entrante, la variable sortante et le pivot :

- La variable entrante correspond au coefficient le plus élevé dans la fonction

économique. La colonne de la variable entrante prend alors le nom de colonne
pivot.

- La variable sortante correspondra au plus petit rapport positif issu de la division de

la colonne second membre (les bi) par la colonne variable entrante. Cette variable
sortante de la base et sur la même ligne que le plus petit rapport positif. La ligne de
la variable sortante prend le nom de ligne pivot.

- Le pivot se trouvera à l’intersection de la ligne pivot et de la colonne pivot.

Il s’agira ensuite de rendre la colonne pivot unitaire : c’est à dire, arriver à un pivot
égal à 1 et tous les autres éléments de la même colonne pivot égaux à zéro jusqu'à
la fonction économique (dernière ligne du tableau). Chaque itération s’arrête dés
que la colonne pivot est devenue totalement unitaire.

4-On construit les différents tableaux jusqu'à ce que la fonction économique ne

contienne plus que des nombres négatifs ou nulles ; cas où il n’est plus possible
d’améliorer la fonction économique.

Remarque :Le pivot ne peut jamais être égal à 0

INT1801/ RECHERCHE PROPRIETE

Exemple : Résoudre par, la méthode du simplexe, le programme linéaire suivant :

Forme standard : x1  0 x 2  0
x1  5x 2 
x1  0 11
x2 0 x3 0 x4 0
1 2 3x
x1 2x5x x 32  11
2x  3x x 5
 51 Max2 3x1  2x 2 4
Max3x 1  2x 2  0x 3  0x 4 

Tableau n°
0:
Variable x4
sortante

To x1 x2 x3 x4 b Rapport
x3 1
A 1 5 1 0 11/1 Variable sortante = x 4
1
B x4 3 0 1 5
2 5/2
C -Z 3 2 0 0 0

Variable entrante dans la x1 : elle a le plus grand coefficient.

base

La solution extrême de base est :

Hors base :x1  x2  0

Base : x3  11,x 4  5

Remarques :
1- L’ordre dans lequel on écrit la liste des variables de la base (x3, x4) est important.
2-
À l’intersection de la colonne pivot (=1) et de la ligne

pivot (=2) Se trouve la valeur 2 entourée, il s’agit du

pivot.

Tableau n°1 : 1ère itérationIl s’agit de transformer le tableau N° 0, en un tableau

équivalent (ce sera le tableau N° 1) de telle sorte que la colonne pivot devient
unitaire :

1-Arriver à 1 pivot = 1, pour cela il suffit de diviser toute la ligne du pivot par 2
(valeur du pivot).

INT1801/ RECHERCHE PROPRIETE

2-Tous les autres éléments de la même colonne pivot égaux à zéro, pour cela il
suffit de trouver pour chaque cas la transformation nécessaire, en utilisant la ligne
du pivot.

Pour notre exemple, trouvons les transformations nécessaires d’abord.

La ligne B B  B / c' est : 3/ 0 1/ 5/2

devient 2 1 2 2

La ligne A :

1 B  1  32 0 1/2  52
A 1 5 1 11
A 0 7 0 17 2
1
2  1
2

La ligne C :

 3 B  3 92 0  3/2 0 15 2

C 3 2 0  32 0
C 0 5
2 0 15
2

On obtient alors le tableau N° 1 :

T1 x1 x2 x3 x4 b
A x3 0 7 1
2 1  17
2 2
B x1 1 3 0 1 5
2 2 2
-Z 0 5 0 3 15
C 2 2 2

Solution optimale :

HB : x 2  x 4  0
B : x1  5 , x3  17
2 2
Z = 15
2

2.3- Un autre exemple :Résoudre par la méthode du simplexe le programme

suivant :

x1  0x 2  0
x1  2x 2  2
x
 1  4x 2  3
INT1801/ RECHERCHE PROPRIETE
Max2x 1  3x 2   Z
Forme standard :

Variables réellesvariables d’écart

Tableau N° 0 :
T0 x1 x2 x3 x4 b rappor
t

x3 1 1 0 2 2
A 2
2
Ligne pivot : x 4
1 Variable sortante.
B x4 0 1 3 3
4 Piv ot 4

-Z 2 3 0 0 0
C Colonne pivot : x 2 variable entrante

La solution extrême de base est :

HB : x1  0 , 0 x 2  0
B : x3  2 , x 4  0
Z=0

Tableau N° 1 : 1ère Itération

T1 x1 x2 x3 x4 b rapport

1 Ligne pivot : x variable sortante

A
x3
2 0 1 1
2
1
2
12/12 1 3

Piv ot

B
x2
1 1 0 1
4
3
4
34/14 3
4
5 3
C -Z 0 0 4 9 Colonne pivot : x1 variable entrante
4 4

INT1801/ RECHERCHE PROPRIETE

Explication : (Comment a-t-on obtenu T1)

B 1 4 0 1 3

B1  B  1 1 0 1 3
4 4 4 4

B  1 1 0 1 3
4 4 4
A 1 2 1 0 2
A  A  2B  1 0 1 1 1
2 2 2

C’est l’opération nécessaire pour obtenir la valeur 0 sur la colonne pivot

B  1 1 0 1 3
4 4 4
C 2 3 0 0 0
C  C  3B  5 0 0 3 9
4 4 4

C’est l’opération nécessaire pour obtenir la valeur 0 sur la colonne pivot.

La solution est :

HB : x1  x 4  0
B : x3  1 , x2 3
2 4
Z= 9
4

Tableau N° 2 : 2ème Itération

T2 X1 X2 X3 X4 b rapport
A Rapport
X1 1 0 2 -1 1
négatif

B X2 0 1 1
2
1
2
1
2
12/12 1 Ligne pivot : x2 : variable sortante

C -Z 0 0 5 1 14
2 2 4 Colonne
pivot : x 4 variable entrante

INT1801/ RECHERCHE PROPRIETE

Explication : (comment a-t-on obtenu T2) :

A  1 0 1 1 1
2 2 2
A  A.2  1 0 2 -1 1

C’est l’opération nécessaire pour obtenir un 1

A  1 0 2 -1 1

B  1 1 0 1 3
4 4 4

1 1 1
B  B  1 A  0 1 2 2 2
4

A  1 0 2 -1 1

5 3
C  0 0 4 9
4 4

1 14
0 0 5 4
C  C  5 A  2 2
4

La solution est :
HB : x3  x 4  0
B : x1  1 , x 2  1
2
Z = 14  7
4 2

Tableau N° 3 : 3ème Itération

A T3 x1 x 2 x 3 x4 b

x1
1 2 1 0 2

B x 4
0 2 -1 1 1

C -Z 0 -1 -2 0 4

C’est le tableau optimal ; mais comment l’a-t-on obtenu ?

INT1801/ RECHERCHE PROPRIETE

Explication :

1 1 1
B  0 1  2
2 2
B  2.B  0 2 -1 1 1

B  0 2 -1 1 1
A  1 0 2 -1 1
A  A  B  1 2 1 0 2

B  0 2 -1 1 1
5 1 14
0 0  4  4
C  2
1
C  C  B  0 -1 -2 0 -4
2
La solution optimale est :

HB : x 2  x3  0
B : x1  2 , x 4  1
Z= 4

Remarque :Notons que les opérations nécessaires pour obtenir une colonne
pivot unitaire sont toujours uniques ; dans le tableau précèdent :

- Pour obtenir 1 à la position du pivot, la seule opération (et nécessaire) et de

multiplier toute la ligne du pivot par 2. Pour le reste des lignes ie A et C ;
l’opération aussi unique,
pour chaque ligne, s’obtient par rapport à la ligne ; par exemple A  A  est
pivot B : B
la seule opération qui : permet d’obtenir un 0 sur la colonne pivot et utilise la
nouvelle ligne pivot B .

CONCLUSION :
La modélisation d’un problème par un programme linéaire, permet de rechercher
l’optimum d’une fonction économique comportant plusieurs inconnues positives ou
nulles liées entre elles, par des relations linéaires indépendantes appelées
contraintes, quand le nombre de ses inconnues est égal à 2, la méthode simple et
appropriée est évidemment la méthode graphique, dans le cas d’un problème à
plus que 2 variables, on utilise la méthode du simplexe qui nécessite l’introduction
de : la notation matricielle , la forme canonique, la forme standard, …etc.
Les deux cours ont été consacrés à un aperçu sur une des techniques de la

INT1801/ RECHERCHE PROPRIETE

recherche opérationnelle ; passons à une autre technique aussi importante et aussi
utile que la première. Il s’agit de la théorie des graphes.

INT1801/ RECHERCHE PROPRIETE

EXERCICES :
EXERCICE N° 01 :
Écrire sous forme canonique (type I ou type II) les programmes linéaires suivants :
Max x1  2x 2 

x   3x 1  x 2  8x 3  8
3x 18

P  x  x  8
1 2
P  4x 1  2x  9x  12

2  2 3
1  1 x 0 x 0 x 0
2x  2   1 2 3
x 14
 1 2 24x  10x  Min
72x
x1  0 , x 2  1 2 3

0

x1  x 2  1 x1  2x 2  x 3  9
 
2x  3x 2 3
x  4x 2   1

2
P3 6x 1  x 2  2 P4 x1  x 2  x 3  1
2x  3x Max x  2x  x Min
x1  0 , x 2  0 x11 0 , 2x 2  0 , x 3  0
1

EXERCICE N°
02 :
Écrire sous forme standard les programmes linéaires de l’exercice N°1

EXERCICE N° 03 :
Résoudre par la méthode du simplexe les programmes suivants :

 x1  0 x2
x3  0 x4  0
0

2x  x  3x  x4 8
  1
2
3
P1  2x1  3x 2  4x4  12

 3x  x  2x
2 3
 18
 1
Max (x1  2x2  x3  x4 )

 x1  0 x2  0

4x1  8x  84
P 2  24
  2x  2x
2
1 2
 Max4x1  6x 2   Z

INT1801/ RECHERCHE PROPRIETE

  x1  0 , x2  0 , x3  0 , x4  0 , x5  0

2x  x  x 8
   1
2 3
P3  x12x 2  x4 7
 
  x5  3
x2
Max 4x1  5x 2 

INT1801/ RECHERCHE PROPRIETE

 Max x1  2x 2 
 - 3x 1  2x 2  x 3 2
P4   -  2x x4 4
 x 1
2
x5 5
 x2
x1

 x1  x 2  x 3  x 4  x  0
 5

0 0 0 0

INT1801/ RECHERCHE PROPRIETE

SOLUTION :
EXERCICE N° 01 : (P1) et (P2) sont déjà écrits sous forme

canonique : Pour (P3), il suffit de multiplier la 1ère inéquation par (-1)

on obtient :

 x1  x
2  1

   x  4x 2 2
P3 q  6x 1  x 2 2
2x  3x  Max
2
 1
x1  0 x 2  0

(P3) q est sous forme canonique

type 2 De même, pour (P4), on

obtient :

 x1  2x 2  x 3  9

2x  3x 3
P   1 2
4 q x  x
1 2  x 3 1
x  2x  x  Min
2
 1 3
x1  x 2  x 3  0
0 0

EXERCICE N° 02 :

 x1  x  x3  x4  x5 0
0 0
2
0 0

 variables .d' écart
P  x 1  3x 2  x  18
3
1 S 
 x1  x x4 8
2
 2x 1  x  x 5  14

2
Max x1  2x 2 

 x1  0 x 2 x  x 4  0 x5  x6 0 x7 0
0 0
3
0

var.réelles var.d' var.artificielles
 écart
P  3x  x  8x  x x 8
2 S  
 1 2 3 4 6

INT1801/ RECHERCHE PROPRIETE

4x 1  2x x5 x7
2  9x 3  12
Min 24x 1  10x 2  72x 3  Mx 6  Mx 7 
 x1  x  x 3  x 4  x5  x6 0
2
0 0 0 0 0

 var.réelles var.d' écart var.artificielles
P  x1  x 2  x 3 x6 
1
3 S
 x1  4x x4 2
2
 6x 1  x x5 2

2

Max 2x 1  3x 2  Mx 6 

INT1801/ RECHERCHE PROPRIETE

  x1  x  x  x4  x5  x6  x7  x8  0
0 0
2
0
3
0 0 0 0

 var.réelles var.d' écart var.artificielles
P  x1  2x 2  x 3  x 9
4
4 S 
 2x  3x  x x7 3
1 2 5
 x1  x 2  x 3  x6  x8  1
Min x1  2x 2  x 3
  Mx 7  Mx 8 

EXERCICE N° 03 :
La forme standard pour (P1)
est :

2x1  x  x  x 8
2 4 5
3x
3
2x  3x  4x x  12
 4
1 2 6
3x  x  2x x  18
1 2 3 7
Maxx1  2x 2  x 3  x4


Tableau N° 0 :
T0 x1 x2 x3 x4 x5 x6 x7 b Rapport

A x5 2 1 3 1 1 0 0 8
8/1
B x6 2 3 0 4 0 1 0 12
C x7 3 1 2 0 0 0 1 18 12/3 ligne pivot :

D -Z 1 2 1 1 0 0 0 0
18/1 x6 :var.sortante

Colonne x 2 variable
pivot : entrante

la solution extrême de base

est :
HB : x1  x 2  x3  x 4  0
B : x 5  8 x 6  12 x 7  18
Z=0

- Comment obtenir
INT1801/ RECHERCHE PROPRIETE
T1 : 1ère Itération

B 2 3 0 4 0 1 0 12

B  B  2 1 0 4 0 1 0 4
3 3 3 3

INT1801/ RECHERCHE PROPRIETE

 B  2 1 0 4 0 1 0 4
3 3 3
A 2 1 3 1 1 0 0 8

A  A  B  4 0 3 1 1 1 0 4
3 3 3

B  2 1 0 4 0 1 0 4
3 3 3
C 3 1 2 0 0 0 1 18

C  C  B  7 0 2 4
 3 0 1 1 14
3 3

B  2 1 0 4 0 1 0 4
3 3 3
D 1 2 1 1 0 0 0 0

D  D  2B   1 0 1 5 0 2
 3 0 -8
3 3

Ainsi le T1 sera comme suit :

tableau

T1 x1 x2 x3 x4 x5 x6 x7 b Rapport

4/3 ligne
A x 5 4 1 1
3
0 3 1 3 0 4 pivot x5 :
3
variable sortante
B x2 2 4 1
1 0 0 0 4
3 3 3 Indéfini
C x7 7 4 1
0 2 3 0 3 1 14
3
14/2
1 5
3 0 3 0 2
D -Z 1 3 0 -8

Colonne pivot x3 variable

entrante :
La solution de base
est :

HB : x1  x3  x 4  x 6 
0
B : x 2  4 , x5  4 , x7 
14
Z=8
INT1801/ RECHERCHE PROPRIETE
- Comment obtenir le 2ème tableau : 2ème itération

3
A  4 0 1 1  1 0 4
3 3 3

A  A  4 0 1 1 1  1 0 4
3 9 9 3 9 3

4 0 1 1 1 1 0 4
A‫اا‬  9 9 3 9 3
B  2 1 0 4 0 1 0 4
3 3 3
B  B  2 1 0 4 0 1 0 4
3 3 3

C’est la même ligne : il n’y a aucune opération à faire puisqu’on a déjà le zéro sur la
colonne du pivot.
1
A  4 1 1 1  0 4
9 0  9 3 3
9
C  7 0 2 4 0 1 1 14
3  3 3
1
C  C  2A  13 0 0 10 2  1 34
9 9 3 9 3

A  4 1 1 1 1 0 4
9 0  9  9 3
3
D  1 0 1 5 0 2 0 -8
 3 3  3
1
D  D  A   7 0 0 14  5 0  28
9 9 3 9 3

La ligne D a tous ces 0 , sera le tableau optimal, écrivons le pour déduire

coefficients la solution T2
optimale :

T2 x1 x2 x3 x4 x5 x6 x7 b

A
x3 1 1 4
4 0 1  9 1  9 0
9 3 3
B
x2 2 1 0 4 0 1 0 4
La solution optimale 3 3 3
C
13 34 est :
HB x7  10 2 1
9 0 0 9 3 9 1 3
:
x1  x 4  x5  x 6 
0 7 14 1 5  28
D -Z 9 0 0 9 3 9 0 3
INT1801/ RECHERCHE PROPRIETE
 B:
x 2  4 , x3  4 , x 7 
3
34
3

Z = 28
3

Dans la suite ; on n’écrira plus comment obtenir les tableaux ; la forme standard de (P2)
est :

x1  0x2  0 x3  0x 4  0

v. réelles v. d’écart

4x1  8x 2  x 3  84

2x1  2x 2 x4  24
LE 
TAMBaLxEA4xU1
N6°x 20 :

T0 x1 x2 x3 x4 b rapport

x3 4 1 0 84 84/8 x 3 : Variable sortante

8
x4 2 2 0 1 24 24/1

-Z 4 6 0 0 0

x 2 : Variable entrante

La solution extrême de base est :

HB : x1  x 2  0
B : x3  84 ; x 4 
24
Z= 0

INT1801/ RECHERCHE PROPRIETE

Le tableau N° 1 : 1ère itération

T1 x1 x2 x3 x4 b Rapport

x2 1
2
1 1
8
0 21
2 212 1 x 4 : Variable sortante
2

x4 1 0 1 1 3 3
4 1

-Z 1 0 3 0 -63 x1 : Variable entrante

4

La solution de base est :

HB : x1  x3  0

B : x 2  21 , x 4 
2
3
Z = 63

Le tableau T2 : 2ème
itération

T2 x1 x2 x3 x4 b

1 1
x2 0 1 2 9
4
x1 1 0 1
4 1 3
-Z 0 0 1
2
-1 -66

La solution optimale est :

HB : x3  x 4  0
B : x1  3 ; x 2 
9
Z = 66

INT1801/ RECHERCHE PROPRIETE

(P3) est déjà écrit sous forme standard :

T0 x1 x2 x3 x4 x5 b
Rapport

x3 2 1 1 0 0 8 8/1
x4 1 2 0 1 0 7
7/2
x5 0 1 0 0 1 3
-Z 4 5 0 0 0 0 3/1 x5 : v. sortante

x 2 : v.entrante

La solution extrême de base est :

HB : x1  x 2  0
B: x3  8 , x 4  7 , x5  3
Z= 0

Le tableau N° 1 : 1ère itération

T1 x1 x2 x3 x4 x5 b rapport
x3 2 0 1 0 -1 5 5/2
x4 1
0 0 1 -2 1 1/1 x 4 : v. sortante
x2 0 1 0 0 1 3 indéfini
-Z 4 0 0 0 -5 -15

x 1 : v. entrante

La solution de base est :

HB : x1  x5  0
B: x3  5 , x 4  1 , x 2  3
Z = 15

INT1801/ RECHERCHE PROPRIETE

Le tableau N° 2 : 2ème itération

x1 x5 rappo
T2 x2 x3 x4 b
rt x3 : v.sortante
x3 0 0 1 -2 3 3 3/3

1 0 0 1 -2 1 >0
x1
x2 0 1 0 0 1 3 3/1
-
-Z 0 0 0 -4 x 5 : v.entrante
3 19
La solution de base est :

HB : x 4  x5  0
B : x3  3 , x1  1 , x 2
3
Z = 19

Le tableau N° 3 : 3ème itération

T3 x1 x2 x3 x4 x5 b
x5 0 0 1 - 2 1 1
3 3
x1 1 0 2 1 0 3
3 3
x2 0 1 1 2 0 2
3 3
-Z 0 0 -1 -2 0 -22

La solution optimale, est atteinte ; c’est :

HB : x3  x 4  0

B: x5  1 , x1  3 , x 2 
2

(P4) est sous forme standard :

Le tableau N° 0 :

x3 x5
T0 x1 x2 x4 b
rapportX2 : X3 :
x4 -3 2 1 0 0 2 2/20 var.
entra
x4 -1 2 0 1 0 4 4/2
nte
x5 1 1 0 0 1 5 5/1
-Z 1 2 0 0 0 0

INT1801/ RECHERCHE PROPRIETE

v. sortante

INT1801/ RECHERCHE PROPRIETE

La solution extrême de base est :

HB : x1  x 2  0
x 3  2, x 4  4 , x 5
5
Z= 0

Le tableau N° 1 : 1ère itération

T1 x1 x2 x3 x4 x5 b rapport

x2 3 1 1 0 0 1 <0
2 2
x4 2 0 -1 1 0 2 2/2
5 X4 : v.sortante
x5 0 1 0 0 4 8/5
2 2
-Z 4 0 -1 0 0 -2

X1 : v. entrante

La solution de base

est :

HB : x1  x 3  0
x 2  1 , x 4  2 , x5
4
Z= 2

Le tableau N° 2 : 2ème itération

T2 x1 x2 x3 x4 x5 b rapport

x2 0 1 3 0 5/2 < 0
1 4
4
x1 1 0 1 0 1 <0
1 2
3 2
x5 0 0 4 5 1 3/2 (3/2) (3/4)
4 X5
-Z 0 0 1 -2 0 -6

X3
La solution de base est :

HB : x3  x 4  0

x 2  5 , x1  1 , x5 
2
3
2
Z= 6
INT1801/ RECHERCHE PROPRIETE
Le tableau N° 3 : 3ème itération

T3 x1 x2 x3 x4 x5 b
x2 0 1 0 1 1 3
3 3
x1 1 0 0 1 2 2
3 3
x3 0 0 1 5 4 2
3 3
-Z 0 0 0  1 4 -8
3 3

T3 est la tableau optimale , la solution optimale de base est :

HB : x 4  x5  0
B : x 2  3 , x1  2 , x3 
2
Z= 8

INT1801/ RECHERCHE PROPRIETE

BIBLIOGRAPHIE :
[1] P. Caron –A Juhel – F. Vendeveld : Programmation linéaire méthodes et
applications (DUNOD)

[2] F. Droesbeke, M.Hallin C. Lefèvre : La Programmation linéaire par

l’exemple (Ellipses).

[3]F.ECOTO : Initiation à la recherche opérationnelle (Ellipses).

INT1801/ RECHERCHE PROPRIETE

LEÇON N°04 : RECHERCHE D’UN CHEMIN DE
LONGUEUR MINIMALE ET DE LONGUEUR
MAXIMALE DANS UN GRAPHE VALUE METHODE DE
FORD.

OBJECTIF PEDAGOGIE : À la fin cette leçon, le stagiaire doit être capable

de trouver un chemin de longueur minimale et un chemin de longueur maximale
dans un graphe valué.

PLAN DE LA LEÇON :

I - NTRODUCTION

II-FORMULATION DU PROBLEME

III- RESOLUTION DU PROBLEME

1-Principe de la méthode de FORD (pour le minimum).
2-Application : recherche de chemin de longueur minimale à l’aide d’un graphe valué.
3-Principe de la méthode de FORD (pour le maximum).
4-Application : recherche de chemin de longueur maximale à l’aide d’un graphe valué.

CONCLUSION

EXERCICES

CORRIGES

INT1801/ RECHERCHE PROPRIETE

INTRODUCTION :
Supposons que dans un graphe orienté, on décide d’attribuer à chaque arc une
longueur positive ou nulle, il est alors naturel de définir la longueur d’un chemin
quelconque comme la somme des longueurs des arcs qui les composent. Un
problème fondamental et qui se pose fréquemment dans les applications de la
théorie des graphes, est celui de la recherche d’un chemin de longueur minimale ou
maximale.

I- FORMULATION DU PROBLEME :
- Soit G (X, U) un graphe orienté sans boucle comportant n sommets.

- A tout arc (xi , xj)  U est associé à un nombre réel l ij appelé longueur de l’arc (x i,
xj).La longueur d’un chemin Mquelconque notée l (M) est alors définie comme la
somme des longueurs des arcs qui le composent.

l (M) = 
(xi ,x j )M
li j

- Un chemin joignant un sommet x i à un sommet xj est dit de longueur minimale s’il

minimise cette longueur l(M) dans l’ensemble de tous les chemins joignant x i à xj.
La longueur d’un tel chemin est appelée distance minimale.

Remarque :
1-Par abus de langage et bien que l’unicité ne soit pas nécessairement réalisée. On
parle parfois de plus court chemin de xi à xj ;

2- Si à tout arc (xi, xj) d’un graphe G(X, U) est associée une longueur, G est dite un
graphe valué.

II-RÉSOLUTION DU PROBLEME :
1- Principe de la méthode de FORD (pour le minimum) :
1ère Etape : Numérotation des sommets du graphe valué dans n’importe quel
ordre, mais en commençant par x0 et en finissant par xn-1 (le nombre de sommets
est n).

2ème Etape : Affectation d’une valeur ti = + ∞ avec 1 ≤ i ≤ n-1 à tous les

sommets sauf pour le sommet initial auquel on attribue la valeur t 0 = 0.

Remarque : La valeur ti = ∞ peut être considérée comme la solution initiale.

Exemple : Mettre t2 = + ∞ signifie l’existence d’un chemin de x0 vers x2 et qui est de

longueur
+ ∞, évidement ce n’est pas le chemin de longueur minimale. t 0 = 0 signifie que le
plus court chemin de x0 vers lui-même est de longueur nulle. La troisième étape à

INT1801/ RECHERCHE PROPRIETE

pour objectif d’améliorer cette solution.

INT1801/ RECHERCHE PROPRIETE

3ème étape :Pour chaque arc (xi, xj), si la valeur tj est supérieure à la quantité ti
+ lij, on remplace alors t′j par tj = ti +lij. Par contre, si tj est inférieure à t i + lij alors
on ne change rien.

Remarque :À cette étape, la comparaison est faite entre deux solutions ; la

solution actuelle : tj est pour l’instant la meilleure solution pour le problème de
chemin de longueur minimale de x0 vers xj.
La deuxième solution (éventuelle) :

Cette deuxième solution suppose l’existence d’un plus court chemin de x 0 vers xi ;
de longueur ti.

La comparaison tj > ti + lij répond à la question : peut-on trouver, à partir de x i, un

plus court chemin de x0 vers xj ;

4ème étape : On répète la 3ème étape jusqu’à ce qu’aucun arc ne permette plus
de diminuer les ti.

2- Application : Recherche de chemin de longueur

minimale à l’aide d’un graphe valué :
Trouver le chemin de longueur minimale du sommet x 0 vers le sommet x7 dans le
graphe valué suivant :
24

x6
x1 21
12 13 3
5
x7
x0 x2 x5
7
2

10 4
14 x3 1 26
x4

16
Remarque :
1- la longueur de l’arc (x0, x1) = 12, c'est-à-dire l01 =12 .

2-M = {(x0, x1), (x1,x6), (x6, x7)} est un chemin de x0 vers x7 la longueur de ce chemin l(M)
= l01
+ l16 + l67 = 12 + 24 + 21 = 57.

INT1801/ RECHERCHE PROPRIETE

Application de la méthode de FORD :
1-Les sommets sont déjà numérotés

2- t0 = 0 et ti = + ∞, 1 ≤ i ≤ 7

A partir du sommet x0 : (x0, x1) et (x0, x3)

Pour l’arc (x0, x1) : t1 = ∞ et to + l01 = 0 + 12

= 12. t1 > 12, on remplace alors t1 par t'1=

t0 + l01 = 12. Pour l’arc (x0, x3) : de même t3

= ∞, t3 > t0 + lo3. On remplace alors t3 par

t'3 = t0 + l03 = 0 + 14 = 14. (x1, x6) et (x1,

x2).

Pour l’arc (x1, x6) : t1 = 12 et t6 = ∞, l16 = 24.

t6 > t1 + l16 on remplace t6 par t1 + l16 = 12 +

24 = 36. Pour l’arc (x1, x2) : t1 = 12, t2 = ∞, l12

= 13.

t2  t1 + l12, on remplace t2 par t'2 = 12 + 13 = 25.

Remarque :A chaque fois qu’on remplace ti par une autre valeur ; ceci indique
qu’on a trouvé un autre chemin de plus petite longueur.

Exemple : t2 = ∞ remplacé par t'2 = 25, indique qu’on a trouvé (à partir du

sommet x1) un chemin de x0 vers x2 de longueur 25 , rappelons que t 2 = ∞ indique
qu’on n’a pas encore trouvé un chemin de x 0 vers x2.

Continuons l’application de l’algorithme de

FORD. A partir du sommet x2 : (x2, x6),

(x2, x5), (x2, x4). Pour l’arc (x2, x6) : t2 = 25,

t6 = 36 et l26 = 3.

t6 > t2 + l26, on remplace t6 par t'6 = t2 + l26

= 28. Pour l’arc (x2, x5) : t2 = 25, t5 = ∞, l25

= 7.

t5 > t2 + l25, on remplace t5 par t'5 = t2 + l25 =

INT1801/ RECHERCHE PROPRIETE

32. Pour l’arc (x2, x4) : t2 = 25, t4 = ∞, l24 = 1.

t4 > t2 + l24, on remplace t4 par t'4= t2 +

l24 = 26. A partir du sommet x3 : (x3,

x2), (x3, x4) : Pour l’arc (x3, x2) : t3 =14, t2

= 25, l32 = 10.

t2 > t3 + l32, on remplace t2 par t'2 = t3 +l32 = 24.

INT1801/ RECHERCHE PROPRIETE

Pour l’arc (x3, x4) : t3 = 14, t4 = 26 et l34 = 16.

tu < t3 + l34 , alors on ne change pas la valeur de t4.

Remarque : À partir du sommet x3, on a pu trouver un plus court chemin de x 0 vers

x2 qui est de longueur 24, alors que le sommet x 2 a déjà été exploré (quand t 2 =
25) et a permis de modifier t6, t5 et t4 . Il convient alors de reprendre le sommet x 2.

A partir du sommet x2 : (x2, x6), (x2, x5),

(x2, x4) Pour l’arc (x2, x6) : t2 = 24, t6 =

28, l26 = 3.

t6 > t2 + l26, on remplace t6 par t'6 =

27. Pour l’arc (x2, x5) : t2 = 24, t5 =

32, l25 = 7. t5 > t2 + l25 , on remplace

t5 par t'5 = 31.

Pour l’arc (x2, x4): t2 = 24, t4 = 26, l24

= 1. t4 > t2 + l24 on remplace t4 par

t'4 = 25.

A partir du sommet x4 : (x4, x7)

Pour l’arc (x4, x7) : t4 = 25, t7 = ∞, l47 = 26.

t7 > t4 + l47, on remplace t7 par t'7 = t4 + l47 = 51.

A partir du sommet x5 : (x5, x6), (x5,

x7) Pour l’arc (x5, x6) : t5 = 31, t6 = 27,

l56 = 5. t6 < t5 + l56, on ne change pas

la valeur de t6. Pour l’arc (x5, x7): t5 =

31, t7 = 51, l57 = 2.

t7 > t5 + l57, on remplace t7 par t'7 = t5 + l57 = 33.

A partir du sommet x6 : (x6, x7)

Pour l’arc (x6, x7) : t7 = 33, t6 = 27, l67

= 21. t7 < t6 + l67, on ne change pas la
valeur de t7.

INT1801/ RECHERCHE PROPRIETE

Ainsi, on a exploré tous les sommets, c’est la fin de l’application de la méthode de FORD.

En définitive, on obtient comme plus court chemin (xo, x3, x2 , x5, x7), représenté en
traits discontinus sur le graphe.

3- Principe de la méthode de FORD (pour le

maximum) : 1ère étape :

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

INT1801/ RECHERCHE PROPRIETE

2ème étape :
Affectation d’une valeur ti = 0 avec 0, ≤ i ≤ n à tous les sommets du graphe valué.

3ème étape :
Pour tout arc (xi, xj), si la valeur tj est inférieure à la quantité ti + lij, on remplace
alors tj par t'j = ti + lij. Par contre, si tj est supérieur à tj + lij alors on ne change rien.

4ème étape :
On répète la 3ème étape jusqu’à ce qu’aucun arc ne permette plus d’augmenter les ti.

Remarques :

1-L’étape de numérotation est importante mais peut être faite d’une autre
manière : 1, 2,….,n ou A,B,C…..

2- A l’étape N°2 ; ti = 0 peut être comme une solution initiale.

Exemple : Mettre t2 = 0, signifie l’existence d’un chemin de x o vers x2 et qui est de

longueur zéro évidement, ce n’est pas le chemin de longueur maximale.

3- La 3ème étape a pour objectif d’améliorer la solution initiale de l’étape N°2.

À cette étape, la comparaison est faite entre 2 solutions, la solution actuelle : tj est
pour l’instant la meilleure solution pour le problème de chemin de longueur
maximale de xo vers xj. La 2ème solution (éventuelle), suppose l’existence d’un
plus long chemin de xo vers xi, de longueur ti.

La comparaison tj < ti + lij répond à la question : peut- on trouver, à partir de x i, un

plus long chemin de xo vers xj.

4- Application : recherche d’un chemin de longueur

maximale à l’aide d’un graphe valué :
Trouver le chemin de longueur maximale du sommet x o vers le sommet x7 dans le
graphe valué suivant :

24
x6
21
x1
12 13 3 5

xo x2 x5 x7
2
10 7
1 4
14
26
x3
x4
INT1801/ RECHE1R6CHE PROPRIETE
1- On affecte à chaque sommet xi , la valeur ti = 0.

(A partir du sommet xo ) : (xo, x1) et

(xo, x3) Pour l’arc (xo, x1) : t1 = 0 et to +

l01 = 12.

t1 < 12, on remplace t1 par t'1 = to + l01

= 12. Pour l’arc (xo, x3), t3 = 0 et to +

l03 = 0 + 14.

t3 < 14, on remplace alors t3 par t'3 = to + l03 = 14.

A partir du sommet x1 : (x1, x6) et (x1, x2)

Pour l’arc (x1, x6) : t6 = 0, t1 = 12, t1 + l16 = 12 + 24 = 36.

t6 < 36, on remplace t6 par t'6 = 36.

Pour l’arc (x1, x2) : t2 = 0, t1 = 12, l12 = 13 ; t1 +

l12 = 25. t2 < 25, on remplace alors t2 par t'2 =

25.

A partir du sommet x2 : (x2, x4), (x2, x5) ,

(x2,x6). Pour l’arc (x2, x4) : t4 = 0, t2 = 25, t2 +

l24 = 26.

t4 < 26, on remplace alors t4 par t'4 = t2 + l24 =

26. Pour l’arc (x2, x5) : t5 = 0, t2 = 25, t2 + l25 =

25 + 7 = 32. t5 < 32, on remplace alors t5 par t'5

= t2 + l25 = 32.

Pour l’arc (x2, x6) : t6 = 36, t2 = 25, t2 + l26 = 25 + 3 = 28.

t6 > 28, on ne change pas la valeur de t6.

A partir du sommet x3 : (x3, x2), (x3, x4) :

Pour l’arc (x3, x2) : t2 = 25, t3 = 14, t3 + l32 = 14 + 10 = 24.

t2 > 24, on ne change pas la valeur de t2.

Pour l’arc (x3, x4) : t4 = 26, t3 = 14, t3 + l34 = 14 + 16 = 30.

INT1801/ RECHERCHE PROPRIETE CNFEPD

t4 < 30, on remplace alors t4, par t'4 = t3 + l34 = 30.

A partir du sommet x4 : (x4, x7)

Pour l’arc (x4, x7) : t7 = 0, t4 = 30, l47 = 26, t4+

l47 = 56. t7 < 56, on remplace alors t7 par t'7 = t4

+ l47 = 56.

A partir du sommet x5 : (x5, x4), (x5, x6), (x5, x7) :

Pour l’arc (x5, x4) : t4 = 30, t5 = 32, l54 = 4

, t5+ l54 = 36. t4 < 36, on

remplace t4 par t'4 = t5 + l54 = 36.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Pour l’arc (x5, x6) : t6 = 36, t5 = 32, t5 + l56 = 32 + 5 = 37.

t6 < 37, on remplace alors t6 par t'6 = t5 + l56 =

37. Pour l’arc (x5, x7) : t7 = 56, t5 = 32, t5 + l57 =

32 + 2 = 34.

t7 > 34, on ne change pas la valeur de t7.

Puisque la valeur de t4 a changé (t4 = 36), on reprend alors les arcs qui partent du
sommet x4, il s’agit de (x4, x7) seulement :

t7 = 56, t4 = 36, l47 = 26, t4 + l47 = 62.

t7 < 62, on remplace t7 par t'7 = 62.

A partir du sommet x6 : (x6, x7) :

t7 = 62, t6 = 37, t6 + l67 = 37 + 21 = 58.

t7 > 58, on ne change pas la valeur de t7.

A la fin de l’application de la méthode de FORD, le chemin le plus long mesure 62.

En définitive, on obtient comme chemin le plus long (xo, x1, x2, x5, x4, x7)
représenté en traits discontinus sur le graphe.

CONCLUSION :
Dans ce cours, on a utilisé le concept de graphe pour représenter un problème
économique, c’est celui de la recherche de chemin de longueur minimale on
maximale. Ainsi on a présenté une méthode (ou algorithme) appelée méthode de
FORD, pour résoudre ce problème, cette méthode a comme principe de donner une
solution initiale et de procéder par comparaison entre deux solutions, jusqu’à ce
qu’il n’y a plus de comparaisons possibles.

INT1801/ RECHERCHE PROPRIETE CNFEPD

EXERCICES CORRIGES :
EXERCICE N° 1 :
En appliquant la méthode de FORD, trouver le chemin de longueur minimale de x0
vers x5 dans le graphe suivant :
2

x1
x3
3 7

6
x5
xo

2 6 2
8

1
x2 x4

EXERCIE N° 02 :
En appliquant la methode de FORD, trouver le chemin de longueur maximale de
x1 vers x9 dans le graphe suivant :
5
x5
x2

3 1
2 x6
5 x4 4
x1
4 5
2 x9
3 7
x3 x8
x7 3
4
3

INT1801/ RECHERCHE PROPRIETE CNFEPD

SOLUTIONS :
EXERCICE N° 1 :
1-Les sommets sont déjà numérotés.

2-Puisqu’il s’agit de la recherche d’un chemin de longueur minimale, on affecte au

sommet x0 la valeur to = 0 et au reste des sommets les valeurs : t 1 = t2 = t3 = t4 =
t5 = + ∞.

A partir du sommet x0 : (x0, x1), (x0, x2),

(x0, x3) Pour l’arc (x0, x1) : t0 + l01 = 0 + 3

= 3 et t1 = + ∞. t1 > 3, alors on remplace

t1 par t'1 = 3.

Pour l’arc (x0, x2) : de même on remplace t2 = + ∞ par t'2 = t0 + l02 = 8.

Et pour l’arc (x0, x3): de même, on remplace t3 = + ∞ par t'3 = t0 + l03 = 6.

A partir du sommet x1 : (x1, x3),

(x1,x4) Pour l’arc (x1, x3) : t3 = 6, t1= 3,

t1 + l13 = 5.

t3 > 5, on remplace alors t3 par t'3 = t1 + l13

= 5. Pour l’arc (x1, x4) : t4= + ∞, t1 + l14= 3

+ 6 = 9.

t4 > 9, on remplace alors t4 par t'4 = t1+ l14 = 3 + 6 = 9.

A partir du sommet x2 :

Pour l’arc (x2, x4) : t4 = 9, t2 = 8, t2 + l24 = 8 +

1 = 9. t4 = 9, la valeur reste t4 = 9.

Remarque : Cette comparaison, entre deux valeurs égales, indique qu’il existe
2 chemins différents de x0 vers x4 et qui sont de même longueur, ce sont : (x 0, x2,
x4) et (x0, x1, x4)

A partir du sommet x3 : (x3, x2), (x3, x5).

Pour l’arc (x3, x2) : t2 = 8, t3 = 5, t3 + l32 = 5

+ 2 = 7. t2 > 7, on remplace alors t2 par t'2 =

INT1801/ RECHERCHE PROPRIETE CNFEPD

t3 + l32 = 7.

Pour l’arc (x3, x5) : t5 = ∞, t3 = 5, t3 + l35 = 5 +

7 = 12 t5 > 12, on remplace alors t5 par t'5 = t3

+ l35 = 12.

Remarque :A partir du sommet x3, on a changé la valeur de t2, il

convient alors de réexaminer le sommet x2 :

A partir de somme x2 : (x2 , x4) :

Pour l’arc (x2, x4) : t4 = 9, t2 = 7, t2 + l24 = 7 + 1 = 8.

INT1801/ RECHERCHE PROPRIETE CNFEPD

t4 > 8, on remplace t4 par t'4 = t2 + l24 = 8.

Continuons l’application de la méthode de

FORD. A partir du sommet x4 : (x4, x5)

Pour l’arc (x4, x5) : t5 = 12, t4 = 8, t4 + l45 = 8

+ 2 = 10. t5 > 10, on remplace t5 par t'5 = t4 +

l45 = 10.

En définitive, on obtient le plus court chemin de x0 vers x5 de longueur 10, le

chemin est : (x0, x1, x3, x2, x4, x5).

EXERCICE N° 2 :
1-Les sommets sont numérotés.

2- t1 = t2 =……= t9 = 0

A partir de x1 : (x1, x2), (x1, x3), (x1, x4)

Pour l’arc (x1, x2) : t2 = 0, t1 = 0, t1 + l12 = 0

+ 2 = 2. t2 < 2, on remplace t2 par t'2 = t1 +

l12 = 2.

Pour l’arc (x1, x3) : t3 = 0, t1 = 0, t1 + l13 = 0 +

3 = 3. t3 < 3, on remplace t3 par t'3 = t1 + l13

= 3.

Pour l’arc (x1, x4) : t4 = 0, t1 = 0, t1 + l14 = 0

+ 5 = 5. t4 < 5, on remplace t4 par t'4 = t1 +

l14 = 5.

A partir de x2 : (x2, x4), (x2, x5)

Pour l’arc (x2, x4) : t4 = 5, t2 = 2, t2 + l24

= 5. t4 = 5, la valeur de t4 ne change

pas.

Pour l’arc (x2, x5) :t5 = 0, t2 = 2, t2 + l25 = 2

+ 5 = 7. t5 < 7, on remplace t5 par t'5 = t2 +

INT1801/ RECHERCHE PROPRIETE CNFEPD

l25 = 7.

A partir de x3 : (x3, x4), (x3, x7)

Pour l’arc (x3, x4) : t4 = 5, t3 = 3, t3 + l34 = 3 +

4 = 7. t4 < 7, on remplace t4 par t'4 = t3 + l34

= 7.

Pour l’arc (x3, x7) : t7 = 0, t3 = 3, t3 + l37 = 3 +

4 = 7. t7 < 7, on remplace t7 par t'7 = t3 + l37

=7

INT1801/ RECHERCHE PROPRIETE CNFEPD

A partir du sommet x4 : (x4, x6), (x4, x7), (x4,

x8) Pour l’arc (x4, x6) : t6 = 0, t4 = 7, t4 + l46 =

7 + 4 = 11. t6 < 11, on remplace t6 par t'6 = t4

+ l46 = 11.

Pour l’arc (x4, x7) : t7 = 7, t4 = 7, t4 + l47 = 7 + 7 = 14.

t7< 14, on remplace t7 par t'7 = t4 + l47 = 14.

Pour l’arc (x4, x8) : t8 = 0, t4 = 7, t4+ l48 = 7 +

2 = 9. t8 < 9, on remplace t8 par t'8 = t4 + l48

= 9.

A partir du sommet x5 : (x5, x6)

Pour l’arc (x5, x6) : t6 = 11, t5 = 7, t5 + l56 = 7

+ 1 = 8. t6 > 8, on ne change pas la valeur de

t6.

A partir du sommet x6 : (x6, x9)

Pour l’arc (x6, x9) : t9 = 0, t6 = 11, t6 + l69 = 11 +

5 = 16 t9 < 16, on remplace alors t9 par t'9 = t6

+ l69 = 16

A partir du sommet x7 : (x7, x8)

Pour l’arc (x7, x8) : t8 = 9, t7 = 14, t7 + l78 = 14 +

3 = 17 t8 < 17, on remplace t8 par t'8 = t7 + l78

= 17

A partir du sommet x8 : (x8, x9)

Pour l’arc (x8, x9) : t9 = 16, t8 = 17, t8 + l89 = 17 +

3 = 20 t9 < 20, on remplace t9 par t'9 = t8 + l89 =

20

Ainsi, on obtient, un plus long chemin de x 1 vers x9 de longueur 20, c’est : (x1, x3,
x4, x7, x8, x9).

INT1801/ RECHERCHE PROPRIETE CNFEPD

LEÇON N°05:PROBLEME D’ORDONNANCEMENT
:METHODE PERT

OBJECTIF PEDAGOGIQUE : À la fin cette leçon, le stagiaire doit être

capable de déterminer et d’exécuter des diverses tâches.

PLAN DE LA LEÇON :

INTRODUCTI

ON I-

DEFINITION

S
1-Projet
2-Notion de tâche

II- REPRESENTATION D’UN PROBLEME D'ORDONNANCEMENT

1-Par le diagramme de Gantt
2-Représentation d’un problème d’ordonnancement par un graphe

III- RESOLUTION D’UN PROBLEME D’ORDONNANCEMENT

1-Les dates au plus tôt et au plus tard des tâches
2-Les dates au plus tôt et au plus tard des étapes

IV- CONCLUSIO

N EXERCICES

CORRIGES

INT1801/ RECHERCHE PROPRIETE CNFEPD

INTRODUCTION :
Étant donné un objectif qu’on se propose d’atteindre et dont la réalisation suppose
l’exécution préalable de multiples tâches soumises à de nombreuses conditions ou
contraintes, le problème d’ordonnancement est alors le problème de détermination
de l’ordre et le calendrier d’éxécution des diverses tâches.

I- DEFINITIONS :
1- Le projet :
C’est un ensemble de tâches ou d’opérations a, b, c,….permettant d’atteindre un
objectif fixé ; lesquelles tâches sont elles mêmes soumises à un certain nombre de
contraintes telles que :

a. Les contraintes potentielles ;

b.Les contraintes disjonctives ;
c. Les contraintes cumulatives.

a-Les contraintes potentielles : On distingue :

Les contraintes de succession encore appelées contraintes d’antériorité qui se
traduisent par le fait q’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 : l’appareil que nécessite cette tâche
n’est pas disponible avant cette date) ou ne peut se terminer après une date
imposée (par exemple : l’appareil que nécessite cette tâche doit être
impérativement libérée avant cette date).

b- Les 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 pour cause de besoin en main d’œuvre.

c- Les contraintes cumulatives :Celles-cilimitent 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 tâches qui , en temps normal,
requièrent tout ensemble, l’équivalent de six mois de travail d’un corps de métier
qui ne comporterait sur le terrain que deux représentants.

2- Notion de tâche :
Une tâche ou activité est une opération, l’ensemble des tâches forment le projet, on
peut donc la définir comme étant l’unité ou l’élément d’un projet. On associe à
chaque tâche sa durée et une contrainte d’antériorité par rapport aux autres
tâches.

INT1801/ RECHERCHE PROPRIETE CNFEPD

C’est ainsi qu’on peut dire que A est immédiatement antérieure à B si B ne peut
débuter que lorsque A est achevée.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Dans la suite de ce cours, nous allons étudier le cas particulier le plus important «
Problème central d’ordonnancement » où les seules contraintes sont des
contraintes de successions dans le temps : l’exécution de la tâche j ne peut être
commencée que lorsque la tâche i est achevée.

Exemple : La construction d’un pavillon demande la réalisation d’un certain

nombre de tâches qui sont données avec leurs durées et relations d’antériorités,
dans le tableau suivant :

Code de Désignation de la Durée (en Tâches

la tâche tâche semaine) antérieur
es
A Travaux de maçonnerie 7 /
B Charpente de la toiture 3 A
C Toiture 1 B
D Installations sanitaire et 8 A
électrique
E Façade 2 D et C
F Fenêtres 1 D et C
G Aménagement du jardin 1 D et C
H Travaux de plafonnage 3 F
I Mise en peinture 2 H
J Emménagement 1 E, G et I

II- REPRESENTATION D’UN PROBLEME

D’ORDONNANCEMENT :
1- Par le diagramme de Gantt :
a- But du diagramme de Gantt :C’est un planning 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- Construction du diagramme de Gantt :

- Principe de construction : Le diagramme de Gantt se présente sous forme d’un
tableau quadrillé dans lequel une colonne correspond à une unité de temps et une
ligne à une tâche. Une tâche se matérialise par une barre horizontale dont la
longueur représente la durée (de la tâche).

Le travail effectué ou le déroulement réel du projet se présente parfois, par des

barres horizontales en pointillés, juste au dessus de celles figurant les prévisions
(C’est-à-dire les durées des tâches).

INT1801/ RECHERCHE PROPRIETE CNFEPD

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

Tâches Durées Tâches Durées

prévues antérieures réalisées
A 4 mois / 3
B 2 mois A 2
C 3 mois B 3
D 5 mois C 5
E 6 mois C 4
F 1 mois A 1
En déduire le diagramme de Gantt correspondant à l’état d’avancement du projet au
15ième
mois.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A
B
C
D
E
F

On constate, au 15iè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 deux mois. Les

tâches B et F succédant à
A sont réalisées complètement alors que D et E succédant à 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..

c-Avantages du diagramme de Gantt :

- Il est facilement compréhensible par les exécutants du projet, de par sa
clarté et sa simplicité ;
- Il peut servir de base à des plans d’actions intermédiaires plus détaillés ;
- Il permet de suivre le déroulement des opérations dans le temps.

d- Inconvénients du diagramme de Gantt :

- Il est impossible de rectifier ponctuellement la durée d’une tâche précise, sans
avoir à décaler d’autant les suivantes et à redresser partiellement ou
complètement le diagramme ;

- Le diagramme de Gantt présente également une insuffisance dans la mise en

évidence des liaisons existante entre les différentes tâches.

INT1801/ RECHERCHE PROPRIETE CNFEPD

2- Représentation d’un problème d’ordonnancement par
un graphe :
La représentation par un graphe ; d’un problème d’ordonnancement permettra une
bonne vision globale du problème. L’étude de ce graphe permettra alors d’identifier
les tâches prioritaires et de détecter à temps les retards pour prendre les mesures
correctives.

Nous allons citer deux représentations possibles :

1-Le graphe potentiel-tâches ;

2-Le graphe potentiel-étapes (Pert).

a- Graphe potentiel-tâches : À partir d’un projet donné, on peut

construire le graphe suivant :

1-A chaque tâche (notée i) du projet, on associe un sommet (noté i) du graphe.

Exemple : Soit le projet de construction d’un pavillon cité dans le paragraphe de

définitions ; à chaque tâche de ce projet on associe un sommet du graphe potentiel-
tâches. Ainsi le graphe contient les sommets A,B,C,D,E,F,G,H,I,J.

2- On définit un arc du sommet i vers le sommet j de longueur di si la tâche i doit

précéder la tâche j où di est la durée de la tâche i

Exemple :Soit le projet de construction d’un pavillon cité dans le paragraphe de

définitions ; d’après le tableau représentant ce projet : La tâche B nécessite
l’exécution de la tâche A, la durée de A est 7 semaines, le graphe potentiel-tâches
qui représente ce projet contient donc un arc du sommet A vers le sommet B sa
longueur est 7. La tâche E nécessite l’exécution des tâches D et C, la durée de C
est une semaine, celle de D est 8 semaines, le graphe potentiel- tâches qui
représente ce graphe contient donc les deux arcs :

- Du sommet D au sommet E, sa longueur est 8 ;

- Du sommet C au sommet E, sa longueur est 1.

3- On ajoute au graphe ainsi obtenu ; deux sommets DP et FP correspondant à deux

tâches fictives, respectivement, la tâche début du projet de durée 0 qui doit être
antérieure à toutes les autres tâches (pour celà, il suffit de relier DP aux sommets
sans prédécesseurs seulement). Et la tâche Fin du projet qui doit être postérieure à
toutes les autres tâches (il suffira de la relier aux sommets sans successeurs
seulement).

INT1801/ RECHERCHE PROPRIETE CNFEPD

Application : Soit le projet de construction d’un pavillon cité dans le
paragraphe de définitions ; donner sa représentation par un graphe potentiel-
tâches.

Solutions :
1- Le graphe potentiel-tâches contient les sommets suivants :

C E
B
A

F H I J

D
G

INT1801/ RECHERCHE PROPRIETE CNFEPD

D’après le tableau qui décrit les contraintes du projet (paragraphe de définition) on
obtient le graphe potentiel-tâche de la manière suivante :

- La tâche B nécessite A, alors le graphe contient un arc de A vers B de longueur 7

(durée de la tâche A)
- La tâche C nécessite B, alors le graphe contient un arc de B vers C de longueur 3
(durée de la tâche B)

On remarque que la durée de la tâche J ne figure pas sur le graphe. Ce dernier

n’exprime pas complètement notre projet, le rajout des deux sommets DP et FP va
nous permettre de compléter cette représentation.
D’après la définition de la tâche fictive DP : elle est antérieure à toutes les tâches,
pour exprimer ceci, il suffit de relier le sommet DP à tous les sommets sans
précédents, dans notre exemple, il y a un seul (le sommet A).

D’après la définition de la tâche fictive FP : elle est postérieure à toutes les tâches,
pour exprimer ceci, il suffit de relier le sommet FP à tous les sommets sans
successeurs, dans notre cas, il y a un seul ( le sommet J) .

Au graphe ci-dessus, on rajoute alors :

- Deux sommets DP et FP.

- Deux arcs : de DP vers A de longueur O (durée de la tâche DP) ; de J vers FP de
longueur 1 (durée de la tâche J) .

Enfin on obtient le graphe suivant :

3C 1
E
2
0 7
DP A B

8
1
1 F H I J FP
13 2 1
7
8
D
G
1

8
Ainsi, nous avons représenté un problème d’ordonnancement par un graphe
potentiel-tâches ; l’objet du paragraphe suivant est sa représentation par la
méthode Pert ; et chaqu’une de ces deux représentations permet de calculer au
commencement du projet, le temps nécessaire à sa réalisation.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Ces deux représentations nous indiquent pour ceci, les tâches critiques c’est à dire
celles qui ne doivent souffrir d’aucun retard, car au cas où se retard aura lieu, il se
répercutera sur la durée totale du projet, et les tâches disposants d’une durée de
flottement nous permettent de nous réorganiser au mieux et en tirer profit.

2–Représentation d’un problème d’ordonnancement par

la méthode Pert :
Dans cette représentation, les tâches seront les arcs du graphe, la longueur de
chaque arc sera la durée de la tâche correspondante.

Exemple : Le graphe Pert qui représente le projet de construction d’un pavillon

contient 10 arcs :

Le premier associé à la tâche A de longueur 7, le deuxième est associé à la tâche B,

il est de longueur 3, le troisième est associé à la tâche C, il est de longueur 1, …
etc….

La question qui se pose est : Quels sont les sommets de ce graphe ?

Les sommets du graphe de Pert s’interprètent comme des étapes du projet. Chaque
étape sera définie par un ensemble de tâches ayant déjà été effectuées. Si une
tâche J nécessite l’exécution d’une tâche i, alors l’extrémité initiale de l’arc associé
à la tâche J (noté u j) doit coïncider avec l’extrémité terminale de l’arc associé à la
tâche i, (noté ui).

Exemple : Soit le projet de construction d’un pavillon cité dans le paragraphe de

définitions ; le graphe Pert associé à ce projet contient l’arc A de longueur 7 et l’arc
B de longueur 3, comme la tâche B nécessite l’exécution de A, alors l’extrémité
terminale de A est égale à l’extrémité initiale de B, ceci peut être exprimé par le
schéma suivant :

x0 x1 x2

A;7 B;3

Application :Donner la représentation graphique du projet de construction d’un

pavillon par la méthode Pert.

Solution :

- La tâche A ne nécessite l’exécution d’aucune tâche, donc le début de la tâche A

coïncide avec le début du projet noté DP.
A;7

DP x1

INT1801/ RECHERCHE PROPRIETE CNFEPD

- La tâche B est précédée par la tâche A :

INT1801/ RECHERCHE PROPRIETE CNFEPD

Représentation graphique :

A;7 B;3
DP x1 x2

INT1801/ RECHERCHE PROPRIETE CNFEPD

- La tâche J est précédée par les tâches E,
G et I
E; 2

Représentation graphique :
B ;3 C; 1 F;1 H;3 I ;2
A ;7 x2 x3 x4
x5 x6
x1
J;1
D; 8
G; 1
La tâche J ne précède aucune tâche, sa fin coïncide avec la fin du projet FP : d’où le
graphe Pert suivant :

E; 2
A;7 B3 C
;1
DP x2
x1
xF x5 F I ;2 J ;1
;
:1
H

D; 8
G; 1

INT1801/ RECHERCHE PROPRIETE CNFEPD

III RESOLUTION D’UN PROBLEME
D’ORDONNANCEMENT :
Après la représentation du problème d’ordonnancement par un graphe, vient
l’étape de résolution. Rappelons que la résolution d’un problème d’ordonnancement
consiste à déterminer l’ordre d’exécution des diverses tâches en un temps minimal,
en d’autres termes, elle consiste à trouver sur le graphe qui le représente (graphe
potentiel- tâches ou potentiel- étapes Pert) ce qu’on appellera un chemin critique.

Pour calculer le chemin critique, nous devons d’abord connaître les dates au plus tôt
et au plus tard des tâches et les dates au plus tôt et au plus tard des étapes.

1- Les dates au plus tôt et au plus tard des tâches :

a- Les dates au plus tôt : Une date au plus tôt pour l’exécution d’une tâche i
est une date avant laquelle il est impossible d’exécuter la tâche i, elle est notée t i.

Exemple : Dans le projet de construction d’un pavillon ; la tâche A n’est précédée

par aucune tâche, la date au plus tôt pour commencer A est 0, mais B est précédée
par A, donc on ne peut commencer la tâche B que si A est terminée c'est-à-dire
après 7 semaines, la date au plus tôt pour commencer B est 7, et la date au plus tôt
pour la finir est 7 + (durée de B
= 3) = 10, la tâche C, elle est précédée par B, la date au plus tôt pour commencer
C est la date au plus tôt pour finir B c'est-à-dire 10. La tâche D est précédée par A,
alors comme la tâche B, on ne peut commencer à exécuter D que si la tâche A est
achevée c'est-à-dire après 7 semaines la date au plus tôt pour le début de la tâche
D est 7, la date au plus tôt pour son achèvement est 7 + durée de la tâche D = 15
semaines, de même la date au plus tôt pour la fin de la tâche C est 10 + durée de la
tâche C = 10 + 1 = 11 semaines.

Que se passe-t-il si une tâche est précédée par deux ou plusieurs tâches ? Et
comment calculer la date au plus tôt de son début ? Prenons le cas de la tâche E :

L’exécution de la tâche E, nécessite l’achèvement de la tâche C et de la tâche D.

Donc on ne peut commencer l’exécution de E que si les deux tâches C et D sont
achevées. Sachant que l’achèvement de la tâche C aura lieu au plus tôt à la 11 ème
semaine et celui de D aura lieu au plus tôt à la 15 ème semaine, on ne peut
commencer alors l’exécution de E qu’à la 15 ième semaine d’où la date au plus tôt de
la fin de la tâche E est 15 + durée de E = 15 + 2 = 17 semaines.

Résultats :

1- Si une tâche i est précédée par deux ou plusieurs tâches, la date au plus tôt pour
le début de son éxécution est la plus grande date au plus tôt pour la fin des tâches
qui doivent la précéder.
2- La date au plus tôt pour la fin d’une tâche i est la date au plus tôt pour son début
+ durée de la tâche i

INT1801/ RECHERCHE PROPRIETE CNFEPD

3- La date au plus tôt pour commencer une tâche qui n’est précédée par aucune
autre tâche est égale à 0.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Remarque : Les trois résultats précédents nous permettent de calculer les dates
au plus tôt pour le début et la fin de toutes les tâches d’un projet.

b- Les dates au plus tard :La date au plus tard pour le début de l’exécution
d’une tâche i est une date à laquelle on peut commencer l’exécution, mais après
laquelle le début de l’exécution entraînera un retard de la fin du projet, elle est
notée Ti. Le calcul des dates au plus tard se fait par récurrence :

La date au plus tard du début d’une tâche i est égale à la plus petite différence
entre la date au plus tard des tâches qui la succèdent est la durée de la tâche i.

La date au plus tard de la fin d’une tâche i est égale à la plus petite date au plus
tard des tâches qui la succèdent.

c- La marge totale :Elle est égale à la différence entre les dates au plus tôt et
au plus tard, elle représente le temps de retard que peut prendre une tâche sans
influer sur le reste du parcours.

Remarques :

1-La date au plus tard de la tâche FP (Fin du projet) est égale à la date au plus tôt
de cette tâche : TFP = TFP.
2-Une tâche dont la marge totale est nulle est appelée une tâche critique.
3-Un chemin critique est le chemin qui passe par les tâches critiques, c’est aussi un
chemin sur lequel aucun retard n’est Permis.

Notations : On notera par :

- Tdi la date au plus tôt pour le début de la tâche i.

- tfi la date au plus tôt pour la fin de la tâche i.

- Tdi la date au plus tard pour le début de la tâche i.

- Tfi la date au plus tard pour la fin de la tâche i.

- di la durée d’une tâche i.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Application :
Soit le projet de construction d’un pavillon, calculer les dates au plus tôt et au plus
tard pour le début et la fin de chaque tâche.

Solution : Ces calcules se font de façon plus facile en utilisant le graphe

potentiel – tâches associé à ce projet :

3 1

BB E
2
7
0 8 1
DP
A 1 1 3 2 1
F
8 H I FP

7
D
G
8 1

Calculs des dates au plus tôt :

- Dp est une tâche sans précédents, on a alors : tdDP =0, tfDP = tdDP + dDP
=0+0=0
- tdA = = 0 ; tfA = tdA + dA + 7 = 7
tfDP =0
- tdB = =7 ; tfB = tdB + dB = 7 + 3 =
tfA 10
- tdC = = ; tfC = tdC + = 10 + 1 =
tfB 10 dC 11
- tdD = =7 ; tfD = tdD + =7 +8=
tfA dD 15

Remarque :Jusqu’à présent, nous avons calculé les dates au plus tôt pour le début
et la fin de tâches qui ne sont précédées que par une seule tâche.

Rappelons que dans ce cas ; pour calculer la date au plus tôt pour le début d’une
tâche, il suffit de prendre la date au plus tôt pour la fin de la tâche qui la précède.

Exemple : tdC = tfB , car C doit être précédée par la tâche B et pour calculer la
date au plus tôt pour la fin d’une tâche i on rajoute à la date au plus tôt pour le
début de cette tâche i sa durée di , c'est-à-dire : tfi = tdi + di .

Exemple : tfC = tdC + dC

Mais si une tâche i doit être précédée par deux ou plusieurs tâches ; la date au plus
tôt pour le début de cette tâche correspond à la plus grande date au plus tôt pour la
fin des tâches qui la précédent.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Exemple : La tâche E est précédée par C et D donc tdE = Max (tfC, tfD ).
=Max (11, 15) = 15.

La date au plus tôt pour la fin d’une tâche précédée par deux ou plusieurs tâches
est calculée de la même façon que pour la fin d’une tâche qui n’est précédée que
par une seule tâche ; c'est-à-dire tfi = tdi + di

Exemple : tfE = tdE + dE = 15 + 2 = 17.

Continuons les calculs des dates au plus tôt pour le reste des

tâches : tdF = Max (tfC, tfD ) = Max (11, 15) = 15 ; tfF = 15 +

dF = 15+1 = 16. tdG=Max (tfC, tfD ) = Max (11, 15) = 15 ; tfG

= tdG + dG = 15+1 = 16. tdH = tfF = 16 ; tfH = tdH + dH = 16

+ 3 = 19.

tdI = tfH = 19 ; tfI = tdI + dI = 19 + 2 = 21

tdJ = Max (tfE , tfG , tfI ) = Max (17 , 16, 21) = 21 ; tfJ = tdJ + dJ

= 21 + 1 = 22

tdFP = tfJ = 22 ;tfFP = 22

Calcul des dates au plus tard :

TdFP = 22 ; TfFP = 22

TdJ = TdFP - dj = 22 – 1 = 21 ; TfJ = TdFP

= 22 TdI = TdJ - dI = 21 – 2 = 19 ; TfI =

Tdj = 21 TdH = TdI - dH = 19 – 3 = 16 ;

TfH = TdI = 19 TdG = TdJ – dG = 21 – 1

= 20 ; TfG = TdJ = 21 TdF =

TdH – dF = 16 – 1 = 15 ; TfF = TdH =

16 TdE = TdJ – dE = 21 – 2 = 19 ; TfE

= TdJ = 21

TdD = Min ( TdE , TdF , TdG ) – dD = Min (19,15,20) -8 =

15-8 = 7 TfD = Min ( TdE , TdF , TdG ) = 15

TdC = Min ( TdE , TdF , TdG ) – dC = Min (19,15,20) - 1 = 15 -

INT1801/ RECHERCHE PROPRIETE CNFEPD

1 = 14 TfC = Min ( TdE , TdF , TdG ) = 15

TdB = TdC – dB = 14 – 3 = 11 ; TfB = TdC = 14

TdA = Min ( TdB , TdD ) - dA = Min (7,11) – 7 = 7 –

7 = 0 ; TfA = Min (TdB , TdD ) = 7.

TdDP = TdA - dFP = 0 ; TfDP = TdA = 0

INT1801/ RECHERCHE PROPRIETE CNFEPD

Ce qui permet d’obtenir le tableau suivant :

Date au plus tôt Date au plus tard Mar

Tâc Début Fin Début Fin ge
h total
es e
Dp 0 0 0 0 0
A 0 0+7=7 7-7=0 Min (7,11) = 7 0-0 =
0
B 7 7+3=1 14- 14 11- 7 =
0 3=11 4
C 10 10+1= 15- Min (19, 14 - 10
1 1=14 15,20)=15 =
1 4
D 7 7+8=1 15- Min (19, 7 – 7 =
5 8=7 15,20)=15 0
E Max (11,15) = 15+2= 21- 21 19 – 15
15 1 2=19 =
7 4
F Max (11,15) = 15+1= 16- 16 15 – 15
15 1 1=15 =
6 0
G Max (11,15) = 15+1= 21- 21 20 - 15
15 1 1=20 =
6 5
H 16 16+3= 19- 19 16 – 16
1 3=16 =
9 0
I 19 19+2= 21- 21 19 – 19
2 9=19 =
1 0
J Max (17, 21+1= 21 22 21 – 21
16,21) 2 =
= 21 2 0
FP 22 22 22 22 22-22=0

Remarque :Les tâches DP, A, D, F, H, I, J, FP sont des tâches critiques car leurs
marges sont nulles.

On reporte ces résultats sur le graphe de la manière suivante :

- Sur chaque sommet (qui représente une tâche) ; on inscrit sur la droite la date au
plus tard pour le début de la tâche et sur la gauche la date au plus tôt pour le début
de la tâche.

- On marque le chemin critique par des traits discontinus ; rappelons que le chemin
critique est un chemin qui passe par les tâches critiques.

INT1801/ RECHERCHE PROPRIETE CNFEPD

 711 10 14

00
15 19

15 15 16 16 1919

15 16 22 22

Par le calcul de ces dates au plus tôt et au plus tard on a résolu le problème
d’ordonnancement associé au projet de construction d’un pavillon, la durée
minimale d’exécution de ce projet est 22 semaines, c'est-à-dire qu’on ne peut
exécuter ce projet en moins de 22 semaines.

L’ordre des tâches critiques décrit le calendrier des tâches à exécuter sans
possibilité de les avancer ou de les retarder est : DP, A, D, F, H, I, J, FP, c’est le
chemin critique.

Les tâches B, C, E et G ont des périodes de flottement :

Exemple : Le début d’exécution de la tâche E peut être retardé au maximum

jusqu’à la 14ième semaine et cela sans retarder la fin du projet.

2 – Les dates au plus tôt et au plus tard des étapes :

a- Date au plus tôt d’une étape : La date au plus tôt d’une étape i est
égale à la plus grande durée d’exécution des étapes qui la précèdent, on la notera
ti.

Exemple : Dans la représentation par la méthode Pert du projet de construction

d’un pavillon, il y a les étapes suivantes :

L’étape DP, l’étape 1 notée x1, l’étape 2 notée x2,

….etc. On a tDP = 0 , tx1 = t DP +7=7;

INT1801/ RECHERCHE PROPRIETE CNFEPD

tx2 = tx1 + l (x1, x2) = 7 + 3 = 10.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Remarque : l(x1, x2) = longueur de l’arc (x1, x2)= d(B) = 3

b– Date au plus tard d’une étape : La date au plus tard pour l’exécution
d’une étape i est calculée par récurrence, elle est égale à la plus petite différence
entre les dates au plus tard et les durées des tâches qui lui succèdent, elle est
notée Ti

Application :
Soit le projet de construction d’un pavillon et sa représentation par la méthode Pert
; calculer les dates au plus tôt et au plus tard pour l’exécution de chaque étape
ainsi que leurs marges.

Solution : À partir de la représentation par la méthode Pert du projet, on a

obtenu le graphe suivant :
E;2
A;7 B;3
C;1 F;1 H;3 I;2 J:1
X1
X3 X4 X5 X6

D;
8 G ;1
Remarqu
e:

1- Pour tout problème d’ordonnancement on a : tFP = tFP

2- Pour tout problème d’ordonnancement on a :

tDP = 0 Calcul des dates au plus tôt :

L’étape DP, par définition tDP = 0

L’étape x1 : tx 1
= tDP + d (A) = 0 +
7 = 7 L’étape x2 : tx 2
= tx1+ d (B)
= 7+3 = 10
L’étape x3 : tx = Max (tx 1 + d (D) ; tx2 + d (c) )
3
= Max ( 7+8 ; 10 + 1 ) = Max (15,11) = 15
L’étape x4 : tx 4 = tx 3 + d (F) = 15 +
1 = 16 L’étape x5 : tx 5
= tx 4 + d (H)
= 16 + 3 = 19
L’étape x6 : tx 6 = Max (tx3 + d (E) ; tx3 + d(G) ; tx5 + d(I))
= Max (15+2, 15+1; 19+2) = Max (17,16, 21)
= 21 L’étape FP : tFP = tx6 + d (J) = 21 + 1= 22

Calcul des dates au plus tard :

INT1801/ RECHERCHE PROPRIETE CNFEPD

Pour l’étape FP on a par définition : TFP= tFP
= 22 Pour l’étape x6 : Tx6 = TFP – d (J) = 22 –
1 = 21 Pour l’étape x5 : Tx5 = Tx6 – d (I) =
21 – 2 = 19 Pour l’étape x4 : Tx4 = Tx5 – d
(H) = 19 – 3 = 16

Pour l’étape x3 : Tx3 = Min (Tx4 – d (F) ; Tx6 – d (E) , Tx6- d (G))

INT1801/ RECHERCHE PROPRIETE CNFEPD

 = Min (16-1 , 21-2, 21-1) = Min (15,19,20) = 15
Pour l’étape x2 : Tx2 = Tx3 – d (C) = 15 – 1 = 14
Pour l’étape x1 : Tx1 = Min (Tx3 – d (D) ; Tx2 – d (B))
= Min ( 15 – 8 ; 14 - 3 ) = Min (7 ; 11) = 7

Pour l’étape DP : TDP = Tx1 – d ( A) = 7 – 7

= 0 Ces calculs sont résumés dans le

tableau suivant :

Etapes Date au plus Date au plus Marge

tôt tard
DP 0 0 0–0=0
x1 7 7 7–7=0
x2 10 14 14 – 10 = 4
x3 15 15 15 – 15 = 0
x4 16 16 16 – 16 = 0
x5 19 19 19 – 19 = 0
x6 21 21 21 – 21 = 0
FP 22 22 22 – 22 = 0

Remarque : Les étapes DP, x1, x3, x4, x5, x6 et FP sont des étapes critiques car
leurs marges sont nulles.

On reporte les résultats du calcul sur le graphe de Pert de la manière suivante :

- Sur chaque sommet (qui représente une étape), ou inscrit sur la droite la date au
plus tard et sur la gauche la date au plus tôt.

- On marque le chemin critique par des traits discontinus ; dans ce cas le chemin
critique est un chemin qui passe par les étapes critiques.

10
14

B; 3 E; 2

15
C; 1 19
0 0 7 7 21 22
15 19
A; 7 H; 3
21 22
D;8 16 F;1 I;2 J;1
16
16

G; 1

Comme pour la représentation par le graphe potentiel-tâches, le calcul des dates au

plus tôt et au plus tard des étapes, dans une représentation par la méthode Pert
permet aussi de résoudre le problème d’ordonnancement.

INT1801/ RECHERCHE PROPRIETE CNFEPD

On remarque qu’on obtient les mêmes résultats, c'est-à-dire, la même durée
minimale (22 semaines) et le même chemin critique : DP, x1 , x3 , x4 , x5 , x6 , FP, et
si au lieu de décrire ce chemin par les sommets on utilise les arcs (qui dans cette
méthode représente les tâches) on obtient : A, D, F, H, I, J : les mêmes tâches
critique trouvées dans la première représentation graphique.

Remarque : Relation entre les dates au plus tôt et au plus tard du début d’une
tâche et les dates au plus tôt et au plus tard des étapes :

- La date de début au plus tôt d’une tâche est égale à la date au plus tôt de l’étape
dont elle est issue.

- La date de début au plus tard d’une tâche est égale à la date au plus tard de
l’étape à laquelle elle aboutit, diminuée de la durée de la tâche.

A partir de cette remarque, vous pouvez calculer les dates de début au plus tôt et
au plus tard des tâches en utilisant le graphe de Pert et les dates au plus tôt et au
plus tard des étapes.

IV - CONCLUSION :
Nous avons défini la notion de Projet, de tâches, et de Problème Centrale
d’Ordonnancement, ces notions restent applicables dans plusieurs domaines :
construction, production, organisation des activités et même les opérations
militaires où la méthode Pert a été créée et utilisée pour la première fois.

Nous avons aussi proposé des méthodes pour sa représentation et sa résolution

(Problème Central d’Ordonnancement) essentiellement la méthode Pert qui donne
entière satisfaction et assure une réussite complète du projet.

INT1801/ RECHERCHE PROPRIETE CNFEPD

EXERCICES CORRIGES :
EXERCICE N°1 :
Désirant fabriquer un produit, on dispose des informations suivantes :

Tâche Description Durée Tâches

s (en j) antérieur
es
A Préparer la liste des 1 /
matières
premières nécessaires
B Préparer le diagramme de 3 A
fabrication
C Commander les 4 A
matières
premières
D Organiser la chaîne de 2 B
production
E Tester le fonctionnement 1 C,D
F Définir les procédures 1 B
d’inspection
G Établir les postes d’inspection 2 E,F
H Former les ouvriers 4 C,D
I Fabriquer les produits 7 G,H

1-Représenter ce projet par le graphe potentiel-tâches.

2-Donner la représentation par le graphe Pert.

3-Calculer les dates au plus tôt et au plus tard pour chaque étape, et en déduire le
chemin critique et le délai minimum de réalisation de ce projet.

EXERCICE N°2 :
Soit un projet constitué de 6 tâches, les données relatives à l’antériorité et à la
durée de chacune des tâches sont répertoriées dans le tableau suivant :

Tâches A B C D E F
Tâches
C - - B B,A D
antérieures

Durées (en mois) 2 7 5 3 6 2

1- Déterminer les niveaux des tâches du projet.

2- Tracer le graphe Pert associé à ce projet.
3- Déterminer le chemin critique et les tâches critiques.

INT1801/ RECHERCHE PROPRIETE CNFEPD

EXERCICE N°3 :
L’entreprise « Bontemps » décide de lancer un nouveau produit sur le marché,
les services commerciaux ont déterminé l’ensemble des tâches
nécessaires à cetteaction :
A,B,C,D, E, F,G, H, I,J,K.
Les conditions d’antériorité liant ces tâches et les durées de celles-ci sont
rassemblées dans le tableau ci-dessous.

Tâches A B C D E F G H I G K
T. E J,E - - - D F,D A,C,D H,A,C,E,K,D,F E F,D
Antérieure
s
Durée(en 4 6 12 14 8 2 10 6 8 12 2
semaines)

1- En classant les tâches par niveaux, déterminer les tâches immédiatement

antérieures à chaque tâche.

Exemple : La tâche B est précédée par J et E, mais J elle- même est précédée
par E, donc seule la tâche J est immédiatement antérieure à B.

2- Tracer le graphe du projet par la méthode Pert.

3- Trouver le ou les chemin (s) critique (s) en indiquant sur le graphe les dates
au plus tôt et les dates au plus tard des étapes.

4 – Les services commerciaux aimeraient connaître en quel temps minimum le

lancement sera réalisé.

Déterminer le temps minimum nécessaire pour le lancement.

5 – Dresser le tableau des marges totales.

INT1801/ RECHERCHE PROPRIETE CNFEPD

SOLUTIONS :
EXERCICE N°1 :
1- Représentation du projet par le graphe potentiel-tâches :

Le graphe contient les sommets suivants :

B D F

A
G

C E
I

Les arcs et leurs longueurs sont obtenus en utilisant : les tâches antérieures et les durées :

La tâche B nécessite la tâche A : le graphe contient un arc du sommet A vers B et

sa longueur et la durée de A.

La tâche C aussi nécessite la tâche A alors le graphe contient un arc du sommet A

au sommet C, sa longueur est alors 1. La tâche D nécessite la tâche B, alors le
graphe contient un arc du sommet B au sommet D, sa longueur est 3 (durée de la
tâche B).

La tâche E nécessite les tâches C et D alors le graphe contient deux arcs :

- Du sommet C au sommet E, sa longueur est 4 (durée de la tâche C) .

- Du sommet D au sommet E, sa longueur est 2 (durée de la tâche D).
- La tâche F nécessite la tâche B, alors le graphe contient un arc du sommet B au
sommet F sa longueur est 3 (durée de la tâche B).
- La tâche G nécessite les tâches E et F, le graphe contient deux arcs :
- Du sommet E au sommet G, sa longueur est 1 (durée de la tâche E).
- Du sommet F au sommet G, sa longueur est 1 (durée de la tâche F).

INT1801/ RECHERCHE PROPRIETE CNFEPD

- La tâche H nécessite les tâches C et D alors le graphe contient deux arcs :

INT1801/ RECHERCHE PROPRIETE CNFEPD

- Du sommet C au sommet H, sa longueur est 4 (durée de la tâche C).
- Du sommet D au sommet H, sa longueur est 2 (durée de la tâche D).
- La tâche I nécessite les tâches G et H alors le graphe contient deux arcs :
- Du sommet G au sommet I , sa longueur est 2 (durée de la tâche G).
- Du sommet H au sommet I, sa longueur est 4 (durée de la

tâche H). Ainsi, on obtient le graphe suivant :

1 B F
31
2
A D I
G

1 2
2 1
C E
4

4 H 4

On remarque que la durée de la tâche I ne figure pas sur le graphe. Ce dernier

n’exprime pas complètement le projet. Le rajout des deux sommets DP et FP va
nous permettre de compléter cette représentation.

D’après la définition de la tâche fictive FP : elle est antérieure à toutes les tâches,
pour exprimer ceci, il suffit de relier le sommet DP à tous les sommets sans
précédents. Dans notre cas, il y a un seul c’est le sommet A).

D’après la définition de la tâche fictive FP : elle est postérieure à toutes les tâches,
pour exprimer ceci, il suffit de relier le sommet FP à tous les sommets sans
successeurs. Dans notre cas, il y a un seul et c’est le sommet I.

Au graphe ci-dessus, on rajoute alors :

- Deux sommets : DP et FP.

- Deux arcs : de DP vers A de longueur 0 (durée
de DP). de I vers FP de longueur 7 (durée de la
tâche I)

INT1801/ RECHERCHE PROPRIETE CNFEPD

Enfin, on obtient le graphe suivant

INT1801/ RECHERCHE PROPRIETE CNFEPD

INT1801/ RECHERCHE PROPRIETE CNFEPD
INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 106
INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 107
INT1801/SEMESTRE II RECHERCHE OPERATIONNELLE PROPRIETE CNFEPD 108
Enfin, la tâche I, nécessite G et H :

Représentation graphique :

F; 1 G; 2
B; 3 x4 x5
x2

DP A; 1
x1
D;2 E,1 U2,0

C; 4
x7
x3 H; 4 x6 I; 7

La tâche U2 est une tâche fictive qui peut être supprimée, la représentation
graphique simplifiée est la suivante :

F ;1
B ;3 x4 1
x2
A ;1
DP x1

E ;1 G ;2
D ;2
C ;4
x3
x5 I FP
H ;

3-
Calcul des dates au plus tôt et au plus tard
pour chaque étape :
Les dates au plus tôt :
L’étape DP : par définition tDP = 0

L’étape x1 : tx1 = tDP + d (A) = 0 + 1

= 1 L’étape x2 : tx2 = tx1 + d (B) = 1

+3=4

L’étape x3 : tx3 = Max (tx1 + d (C), tx2 + d (D))

= Max (1 + 4, 4 + 2) = Max (5,6) = 6

INT1801/ RECHERCHE PROPRIETE CNFEPD

L’étape x4 : tx4 = Max (tx2 + d (F), tx3 + d (E))
= Max (4 + 1, 6 + 1) = Max (5,7) = 7

INT1801/ RECHERCHE PROPRIETE CNFEPD

L’étape x5 : tx5 = Max (tx4 + d (G, tx3 + d (H))
= Max (7 + 2, 6 + 4) = 10

L’étape FP : tFP = tx5 + d (I) = 10 + 7 = 17

jours. Le délai minimum du projet est 17

jours.

Les dates au plus tard :

L’étape FP : on a par définition TFP = tFP =

17 Pour l’étape x5 : Tx5 = TFP – d (I) = 17 –

7 = 10 Pour l’étape x4 : Tx4 = Tx5 – d (G)

= 10 – 2 = 8

Pour l’étape x3 : Tx3 = Min (Tx5 – d (H), Tx4 – d (E))

= Min (10 – 4, 8 – 1) = Min (6,7) = 6

Pour l’étape x2 : Tx2 = Min (Tx3 – d (D), Tx4 – d (F))

= Min (6 – 2, 8 – 1) = Min (4,7) = 4

INT1801/ RECHERCHE PROPRIETE CNFEPD

EXERCICE N°2 :

1 – Détermination des niveaux :Les tâches B et C n’ont pas de tâches

antérieures, ce sont les tâches de premier niveau :

N1 = B,C

On supprime ces 2 tâches du tableau, on obtient le tableau suivant :

Tâches Tâches antérieures

A /
D /
E A
F D

INT1801/ RECHERCHE PROPRIETE CNFEPD

D’où N2 = A,D , En les supprimant de ce tableau, on obtient le tableau suivant :

Tâches Tâches antérieures

E /
F /

E et F sont les tâches de dernier niveau, N3 = E, F

Les niveaux sont résumés

par : N1 = B,C

N2 = A,D

N3 = E, F
La tâche A nécessite la tâche C :
Représentation graphique :

B; x1

DP
A;5
C;5
x3
x2

La tâche D nécessite la tâche B :

Représentation
graphique :
D; 3

x2
x1
B;

DP
C;5
x3
x2 A;2

INT1801/ RECHERCHE PROPRIETE CNFEPD

 La tache E nécessite B et A :

Représentation graphique :

D;3
x4
B;7 x1

U0;0
DP
C;5 E;6
A;2
x2 x6
x3 x5

U1;0

Les tâches U0 et U1 sont des taches fictives, mais seulement la tâche U1 peut être suprimée.U0 ne peut être supprimée, la repré

F, la dernière tâche nécessite D :

Représentation graphique :

INT1801/ RECHERCHE PROPRIETE CNFEPD

Remarques :

1- La tâche U0 n’a pas été supprimé car : E nécessite B et A mais la tâche D ne

nécessite que la tâche B. Si on fait aboutir les arcs A et B vers un même sommet,
on ne peut pas exprimer le fait que D nécessite B.

La représentation suivante :

B; 7 D; 3
x3
A; 2 E;6

Exprime que D nécessite A et B, et E aussi, ce qui n’est pas le cas.

2 – On a fait aboutir les arcs E et F vers le même sommet, car les

tâches correspondantes (c’est-à-dire E et F) ne sont antérieures à aucune des
autres tâches, elles coïncident alors avec la fin du projet FP.

3 – Détermination du chemin critique et les tâches critiques :

Pour déterminer le chemin critique, on doit d’abord calculer les dates au plus tôt et
au plus tard pour chaque étape :

Les dates au plus tôt :

L’étape DP : par définition tDP = 0

L’étape x1 : tx1 = tDP + d (B) = 0 + 7

= 7 L’étape x2 : tx2 = tDP + d (C) = 0
+5=5
L’étape x3 : tx3 = Max (tx1 + d (U0), tx2 + d (A) = Max (7 + 0, 5+2)
= Max (7,7) = 7
L’étape x4 : tx4 = tx1 + d (D) = 7 + 3 =
10 L’étape FP : tFP = Max (tx4 + d (F), tx3
+ d (E))
= Max (10 + 2, 7 + 6) = 13

Les dates au plus tard :

L’étap FP : tFP = tFP 13
e =
L’étap x4: tx4 = tFP - d (F) = 13 - 2 =
e 11
L’étap x3: tx3 = tFP - d (E) = 13 - 6
e =7
L’étap x2: tx2 = tX3 - d (A) = 7 - 2 =
e 5

L’étape x1: tx1 = Min (tx3 - d (U0), Tx4 – d (D))

INT1801/ RECHERCHE PROPRIETE CNFEPD

 = Min (7 – 0,11 – 3) = Min (7,8) = 7

L’étape DP : tDP = Min (tx1 – d (B), tx2 - d (C))

= Min (7 – 7, 5 – 5) = Min (0,0) = 0

INT1801/ RECHERCHE PROPRIETE CNFEPD

On résume ces calculs dans le tableau suivant :

Etape Date au plus Date au plus Marges

tôt tard
DP 0 0 0–0=0
x1 7 7 7–7=0
x2 5 5 5–5=0
x3 7 7 7–7=0
x4 10 11 11 – 10 = 1
FP 13 13 13 – 13 = 0

EXERCICE N°3 :
1- Détermination des tâches immédiatement antérieures à chaque

tâche : D’après le tableau :

Les tâches C, D et E n’ont pas de tâches antérieures, leur suppression du tableau

permet d’obtenir le tableau suivant :

Tâches Tâches
antérieures
A /
B J
F /
G F
INT1801/ RECHERCHE PROPRIETE CNFEPD
 H A
I H, A, F, K
J /
K F

N1 = C, D, E  , N2 = A, F, J

En supprimant les tâches A, F, et J de ce tableau, on obtient le tableau suivant :

Tâches Tâches
antérieures
B /
G /
H /
I H, K
K /

D’où N3 = B, G, H, K.

La suppression des tâches B, G, H et K du tableau permet d’obtenir le dernier niveau

N4 =
 I
Les niveaux sont les suivants :

N1 = C, D, E 

N2 = A, F, J 

N3 = B, G, H,K


N4 = I

A partir de cette détermination de niveau, on détermine les tâches

immédiatement antérieures à chaque tâche.

Tâches A B C D E F G H I J K
T.antérieure E J / / / D F A,C,D H,K E F
s

- G nécessite F et D mais la tâche F elle-même nécessite D, d’où G nécessite F seulement.

- H nécessite A, C et D, ces 3 tâches ne sont pas liées entre elles, on ne peut pas simplifier

INT1801/ RECHERCHE PROPRIETE CNFEPD

- I nécessite H, A, C, E, K, D, F : Mais la tâche H nécessite A, C et D et A elle-même
nécessite E, on peut déduire que la tâche I nécessite seulement H, K et F, mais K
nécessite F, d’où I nécessite seulement H et K.

- K nécessite F et D ; mais F nécessite D d’où K nécessite seulement la tâche F.

La tâche A nécessite E : Représentation graphique :

INT1801/ RECHERCHE PROPRIETE CNFEPD

INT1801/ RECHERCHE PROPRIETE CNFEPD
INT1801/ RECHERCHE PROPRIETE CNFEPD
La tâche J nécessite E et la tâche K nécessite F et B nécessite J

Représentation graphique :

J; 1 B6
E; 8 x7 x8
x1

DP A; 4
C; 12 x2 x6
H; x9

U2 ;0
D,14 K;2
x3
x4 x5

G; 10
F; 2
Enfin la tâche I nécessite H et
K:

Représentation
graphique : J B x
; x7 ;8
E;8 x1

DP
A;4 I ;8
x10
C;12 C;12 x2 H ;6 x6 U0 ;

x9
U1;0
D;14 U 2 ;0
x3 x4 K;2 x5

F;2 G;10

INT1801/ RECHERCHE PROPRIETE CNFEPD

Les tâches U0 et U1 sont des tâches fictives qui peuvent être supprimées, ce
qui permet d’obtenir la représentation simplifiée suivante :
J; 12 B ;6
x1
E; 8 x7 x8

C; 12 A; 4
DP
H; 6 I; 8
x2 x6 x9

D; 14 U2 ; 0 K; 2

x3 x4 x5

F; 2 G; 10

Les tâches B,G et I ne sont nécessaires à aucune autre tâche, elles doivent toutes les
trois coïncider avec la fin du projet FP ; pour cela on doit renuméroter les sommets :

J; 12
x1 x6
E; 8
B; 6
DP

A; 4
C; 12 x2 H; 6 x5
FP
I; 8

U 2; 0 K;
D; 14 x3 x4

G; 10

F; 2

3 – Calcul des dates au plus tôt :

tDP = 0 par définition

L’étape x1 : tx1 = tDP + d (E) = 0 + 8 =

8 L’étape x2 : tx2= tDP + d (C) = 0 +

12 = 12 L’étape x3 : tx3 = tDP + d (D)

= 0 + 14 = 14 L’étape x4 : tx4 = tx3 +

INT1801/ RECHERCHE PROPRIETE CNFEPD

d (F) = 14 + 2 = 16

INT1801/ RECHERCHE PROPRIETE CNFEPD

 L’étape x5 : tx5 = Max (tx2 + d (H) tx4 + d (K))
= Max (12 + 6, 16 + 2) = Max (18,18) = 18

L’étape x6 : tx6 = tx1 + d (J) = 8 + 12 = 20

L’étape FP : tFP = Max (tx4 + d (G), tx5 + d (I), tx6 + d (B) )

= Max (16+10, 18+8, 20+6) = Max (26,26,26) = 26

Calcul des dates au plus tard :

L’étape FP : TFp = TFP = 26

L’étape x6 : Tx6 = TFP – d (B) = 26 – 6 =
20 L’étape x5 : Tx5 = TFP - d (I) = 26 – 8
= 18 L’étape x4 : Tx4 = TFP - d (G) = 26 –
10 = 16 L’étape x3 : Tx3 = Tx4 - d (F) =
16 – 2 = 14 L’étape x2 : Tx2 = Min Tx5 – d
(H) , Tx3 – d (U2))
= Min (18 – 6 ; 14 – 0 ) = Min (12,14) = 12
L’étape x1 : Tx1 = Min (Tx2 – d (A ) , Tx6 – d (J)
= Min ( 12 – 4 , 20 – 12 ) = Min (8,
8) = 8 L’étape DP : TDP = Min (Tx1 – d (E), Tx2 – d (C)
, Tx3 – d (D))
= Min ( 8 – 8 , 12 – 12, 14 – 14 ) = 0

00

INT1801/ RECHERCHE PROPRIETE CNFEPD

On remarque que, pour chaque étape les dates au plus tôt et au plus tard sont
égales, toutes les étapes sont critiques ; il existe plusieurs chemins critiques :

1. DP, E, J, B, FP

2. DP, C, H, I, FP

3. DP, D, F, G, FP

4. DP, E, A, H, I, FP

5. DP, D, F, K, I, FP

4- Le temps minimum nécessaire par le lancement est : 26 semaines

5- Calcul des marges totales :

Etape Date au plus Date au plus Marges
tôt tard totales
DP 0 0 0
x1 8 8 0
x2 12 12 0
x3 14 14 0
x4 16 16 0
x5 18 18 0
x6 20 20 0
FP 26 26 0

INT1801/ RECHERCHE PROPRIETE CNFEPD

LEÇON N° 06 :LE CHOIX D’INVESTISSEMENTS

OBJECTIF PÉDAGOGIQUE : À la fin de cette leçon, le stagiaire doit

être capable d’établir et choisir le projet le plus bénéfique.

PLAN DE LA LEÇON :

INTRODUCTION

I- DEFINITION DE L’INVESTISSEMENT

II- LES DIFFERENTS TYPES DE CLASSIFICATION DE L’INVESTISSEMENT

1-Classification par nature
2-Classification selon la finalité
3-Classification selon l'objectif

III- LES ETAPES DU PROJET D’INVESTISSEMENT

1-L’Identification
2-La préparation
3-L’évaluation
4-La décision
5-L'exécution ou la réalisation
6- Le contrôle ou le suivi

IV- LES CRITERES DE RENTABILITE DE L’INVESTISSEMENT

1-Le délai de récupération
2-La méthode financière (RATIO)
3-La valeur actuelle nette (V.A.N)
4-Le taux de rentabilité interne (TRI)

EXERCICES CORRIGES

INT1801/ RECHERCHE PROPRIETE CNFEPD

INTRODUCTION :
Pour réaliser ses objectifs, lesquels sont établis sur la base des objectifs de ventes ;
l’entreprise doit disposer d’investissements suffisants l’acquisition et le
renouvellement de ces mobilisations, ce qui entraîne des dépenses importantes et
nécessite un financement.

Investir est nécessairement faire un pas vers l’inconnu, c’est donc une démarche
qui implique des risques. Alors toute initiative d’investissement mérite d’être au
préalable étudiée dans ses moindres détails pour éviter les risques d’erreurs
souvent très coûteux parce que souvent les investissements supposent des
sommes importantes.

I-DEFINITION DE L’INVESTISSEMENT :
On peut définir l’investissement comme étant une dépense actuelle qui va
engendrer des bénéfices futures. S’agissant de se projeter dans l’avenir, on
substitue au terme investissement l’expression projet d’investissement. Pour
l’entreprise, investir c’est consentir à décaisser aujourd’hui une certaine somme
avec l’espoir d’encaisser ultérieurement sur plusieurs exercices des sommes plus
importantes permettant d’augmenter ainsi la valeur de l’entreprise et par la suite le
patrimoine des propriétaires. A partir de cette définition on peut déduire les trois
caractéristiques de l’investissement.

- L’investissement est un décaissement actuel : toute activité de l’entreprise

consiste à avancer des sommes d’argent en vue d’obtenir des revenus futurs. Le
cycle d’investissement s’étale sur plusieurs années ; par exemple une machine ou
un bâtiment vont être utilisés pendant plusieurs cycles de production et donc ils
vont participer aux résultats de plusieurs exercices.

- Les encaissements doivent être supérieurs aux décaissements ; un investissement

doit générer " réaliser" des encaissements supérieurs aux décaissements ce qui
permet d’augmenter la valeur de l’entreprise, dans quel cas ; on dit qu’il est
rentable. Le problème est de savoir comment évaluer les flux des liquidités liés à
l’investissement afin de vérifier cette inégalité fondamentale entre les
encaissements et le décaissement.

0 1 2 3 n-1 n

D0 R 1 R2 R3 Rn-1 Rn

Si on désigne par :

D0 : La dépense initiale faite à l’année 0

R1, R2,R3,……Rn sont les rentrées d’argent dans la 1ère année, 2ème année, 3ème
année,….., la nième année respectivement.

Les encaissements et décaissements se réalisent dans des points différents du temps.

INT1801/ RECHERCHE PROPRIETE CNFEPD
- L’incertitude : avec l’espoir d’encaisser ultérieurement ; au moment de
l’investissement le décideur ne peut que estimer ce que seront les encaissements à
venir. Toute décision d’investissement comporte une évaluation du risque
d’exploitation, le risque est plus

INT1801/ RECHERCHE PROPRIETE CNFEPD

important quand le bien acheté est destiné à être utilisé longtemps et son prix
d’achat est élevé. L’analyse financière d’un projet d’investissement vise à estimer
sa rentabilité. Cette estimation passe nécessairement par une étude préalable des
conditions techniques et une analyse commerciale qui cherche d’abord de la
viabilité de l’investissement. C’est-à-dire la possibilité de son développement et de
son aboutissement.

On peut donc définir l’investissement de plusieurs points de vue :

- Du point de vue comptabilité : c’est un capital constant productif ou non

productif, à emploi durable.

- Du point de vue économique : l’investissement est important dans l’activité de

production, il gère le progrès économique principal puisqu’il consiste en l’échange
d’un capital actuel contre les revenus futurs d’un montant égal ou supérieur, le
caractère de l’investissement est être productif.

- Du point de vue financier : l’investissement est une dépense actuelle qui

produit des revenus sur une longue période, il doit être financé par des capitaux
permanents. Le financier s’intéresse à l’équilibre dans le temps entre les ressources
et les emplois.

II-LES DIFFERENTS TYPES DE CLASSIFICATION

DE L’INVESTISSEMENT :
On classe généralement les investissements selon leur. Nature, leur finalité et leur
objectif.

1- Classification par nature :

On distingue l’investissement corporel et l’investissement incorporel :

a- L’investissement corporel :Il s’agit des biens physiques ou d’objets

matériels tels que les terrains, les bâtiments, les machines, les véhicules, le
mobilier, etc....

b- L’investissement incorporel : Il s’agit des investissement abstrait tels

que le fond de commerce, la licence de fabrication, les dépenses pour la formation
du personnel, pour la publicité ou pour des études de recherche etc....

2- Classification selon la finalité :

On distingue l’investissement directement productif et l’investissement non
directement productif.

a- L’investissement directement productif : C’est un investissement

dont la production est destinée à être commercialisée sur le projet.

b- L’investissement non directement productif :Les investissements

INT1801/ RECHERCHE PROPRIETE CNFEPD
non directement productifs sont des projets tels que :

- Les projets sociaux : enseignement, santé, éducation ;

- Les infrastructures : les routes, les ponts, les barrages ;

INT1801/ RECHERCHE PROPRIETE CNFEPD

- L’appui à la production : formation, assistance ; encadrement technique.

3- Classification selon l’objectif :

On distingue l’investissement de remplacement et l’investissement d’expansion ou
de croissance :

a- L’investissement de remplacement :Appelé aussi de renouvellement

ou investissement forcé, il s’agit d’investissement nécessaire pour continuer les
activités de l’entreprise. Il permet de garder intact le potentiel de production, si ce
type d’investissement n’est pas réalisé, l’entreprise risque de disparaître à court
terme.

b- L’investissement d’expansion ou de croissance :Contrairement

à l’investissement de remplacement qui est une obligation à court terme.
L’investissement de croissance est un choix pour le long terme. Il est destiné à faire
face à la croissance de la demande, soit par le développement de la production de
produit qu’elle fabrique déjà, soit par le développement de la production de produits
nouveaux.

III-LES ETAPES DU PROJET D’INVESTISSEMENT :

Appelées aussi cycle de projet d’un courent dont le processus va du lancement de
l’idée de projet, à sa préparation, son évaluation, la prise de décision, puis son
exécution ; ces étapes sont au nombre de six :

1-L’identification ;
2-La préparation ;
3-L’évaluation ;
4-La décision ;
5-L’exécution ;
6-Le contrôle.

On appelle cela un cycle parce qu’une phase conduit naturellement à une phase
suivante et qu’il est souvent nécessaire de revenir à une phase précédente au cours
du déroulement des opérations dans le temps.

1- L’identification :
La première phase consiste en la recherche des projets qui contribuent au
développement du pays, et qui dégagent en même temps une rentabilité assez
suffisante pour justifier leur financement c’est-à-dire qu’ils dégagent des excédents
suffisants pour rémunérer la contribution de ceux qui ont ramené des fonds.
Parmi les objectifs de l’identification, on cite :

- Voir si l’idée du projet est techniquement, financièrement et économiquement viable.

- S’assurer qu’on peut continuer à consacrer d’autres ressources.
INT1801/ RECHERCHE PROPRIETE CNFEPD
2- La préparation :
Dans cette phase on procède à la collecte des données de base qui serviront à
l’étude et à l’examen du projet et si celui-ci est estimé réalisable du point de vue
commercial, technique et financier. Son évaluation devient alors envisageable voire
même possible.

3- L’évaluation :
Durant cette phase on regroupe les données obtenues dans la phase précédente en
vue de procéder à une série d’études et d’évaluation qui concerne :

- L’évaluation financière ;
- L’évaluation technique ;
- L’évaluation commerciale ;
- L’analyse de la sensibilité.

a- L’évaluation financière :Son but est de déterminer si le projet est capable

de générer des excédents financiers susceptibles de couvrir le revenu des facteurs
de production engagé dans le projet. A partir de cette analyse, il sera possible de
porter un jugement sur le plan financement initial.

b- L’évaluation technique :Elle consiste à présenter le procédé de

fabrication, la durée des travaux et les besoins en matières premières.

c- L’évaluation commerciale :C’est l’étude du marché, le niveau de la

demande, celui de l’offre, le niveau général des prix et la concurrence.

d- L’analyse de la sensibilité :L’analyse de la sensibilité est la

détermination des différents coûts et avantages relatifs au projet. Ces derniers ne
sont en fait que des estimations qui engagent de se rapprocher le plus de la réalité
et qui restent exposées à l’erreur.

Les analyses de la sensibilité permettent de ramener des estimations à des valeurs

plus proches de la réalité. Sur la base des analyses de la sensibilité ; de nouvelles
rentabilités financières sont calculées et c’est selon ces dernières que la décision de
financement est prise ou non.

4- La décision :
Les responsables pourront alors prendre en pleine connaissance de cause une
décision motivée, trois décisions sont possibles :

1-Le refus du projet, pour cause de rentabilité insuffisante ou qu’il est jugé prématuré ;
2-La décision de poursuivre les études, soit pour obtenir des informations plus
précises, soit pour établir des variantes de possibilités nouvelles ;
3-L’acceptation pure et simple du projet.

INT1801/ RECHERCHE PROPRIETE CNFEPD

5- L’exécution ou la réalisation :
Après la prise de la décision d’entreprendre le projet identifié et évalué, on passe à
la construction d’ouvrages, l’acquisition des équipements et la mise à la disposition
des fonds nécessaires à la concrétisation du projet.

6- Le contrôle ou le suivi :
Durant la phase de suivi, il sera procédé à différents contrôles qui porteront sur les
points suivants :

 Contrôle du bon déroulement de réalisation du projet.

 Contrôle du fonctionnement de l’entreprise sur le plan budgétaire, de la gestion de
stocks et de la production.
 Contrôle périodique des documents comptables qui permet d’apprécier la situation
financière de l’entreprise et plus exactement : sa capacité de remboursement des
emprunts contractés, sa situation de trésorerie et sa capacité d’autofinancement.
 Le suivie des risques auxquels est exposé un projet et qui sont :

- Le risque de non opportunité : c’est-à-dire le produit dont est l’origine, le

projet ne correspond pas au besoin des utilisateurs ;
- Le risque de non – conformité : le produit du projet n’est plus conforme à sa
définition initiale ;
- Le risque de mauvaise réalisation ; c’est-à-dire, il dure plus longtemps ou il coûte
plus cher que ce qui était prévu au départ.

IV-LES CRITERES DE RENTABILITE DE

L’INVESTISSEMENT :
Comment peut-on choisir entre plusieurs projets d’investissements ? Pour pouvoir
répondre à cette question ; tout projet d’investissement doit être évalué et chiffré :
recettes et dépenses.

Chaque investissement est connu par :

 La dépense initiale : C’est le prix d’acquisition, elle est suivie de

dépenses futures secondaires telles que l’entretien ou la réparation.

 La durée de vie : la rentabilité d’un investissement doit être évaluée sur toute sa
durée de vie.

 Cash-flow : C’est le surplus financier ; le bénéfice net non distribué et les

dotations aux amortissements.

 La valeur résiduelle : À la fin de l’exploitation de l’entreprise, certains de

ses actifs présentera une valeur résiduelle.

INT1801/ RECHERCHE PROPRIETE CNFEPD

On distingue cinq méthodes pour choisir entre les différents projets
d’investissement qui sont :

1. Le délai de récupération ;
2. La méthode financière (radio) ;
3. La valeur actuelle nette (V.A.N) ;
4. L’indice de profitabilité ;
5. Le taux de rentabilité interne.

1- Le délai de récupération :
Pour chaque investissement, il est possible de calculer en combien d’années
l’investisseur pourra récupérer sa dépense initiale. Alors il choisit l’investissement
dont le délai de récupération est le plus court.

On peut définir le délai de récupération comme la durée au bout de laquelle la

valeur des flux des recettes nettes procurés par un investissement devient égale à
la dépense initialement engagée. Il s’agit donc de la durée pour que l’accumulation
des recettes dues à l’investissement compense au moins la somme investie.

Exemple N°01 :

Soient les deux projets A et B réalisés dans les conditions suivantes :

Projet A Projet B
Le coût Les flux Le coût Les flux
Périodes de des de des
l’investissem recettes l’investisseme recett
ent nt es
0 600.000 DA 700.000 DA
1 200.000 DA 300.000
DA
2 180.000 DA 200.000
DA
3 120.000 DA 200.000
DA
4 100.000 DA 100.000
DA
5 80.000 DA 50 000 DA

6 80.000 DA 50 000 DA

Total 760.000 900 000

DA DA
On remarque que le capital investi dont le projet A est récupéré au bout de quatre

ans ; 200000 + 180000 + 120000 +100000 = 600000 DA.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Par contre le capital investi dans le projet B est récupéré au bout de trois ans ;

300000 + 200000 + 200000 = 700000 DA. Selon cette méthode, on choisit ou

on retient le projet B parce qu’il a le délai de récupération le plus court.

Exemple N°02 :Soient les deux investissements suivants :

Projet A Projet B
Périodes Le coût de Les flux Le coût de Les flux des
l’investisseme des l’investisseme recettes
nt recettes nt
0 200.000 DA 200.000 DA
1 50.000 DA 20.000 DA
2 40.000 DA 30.000 DA
3 60.000 DA 30.000 DA
4 50.000 DA 30.000 DA
5 10.000 DA 90 000 DA
6 12.000 DA 80 000 DA
Total 222.000 DA 280 000 DA

Quel est le projet le plus rentable selon la méthode du délai de récupération ?

Pour le projet A ; on remarque que le capital investi est récupéré au bout de quatre

ans ; 50000 + 40000 + 60000 + 50000 = 200000DA.

Pour le projet B ; on remarque que le capital investi est récupéré au bout de cinq

ans ; 20000 + 30000 + 30.000 + 30000 + 90000 = 200000 DA.

Selon cette méthode ont choisi le projet A parce qu’il a le délai de récupération
le moins court.

Exemple N°3 :

Soient les deux projets A et B réalisés dans les conditions suivantes :

Projet A Projet B
Période Le coût Les flux Le coût Les flux
s de des de des
l’investisseme recettes l’investissem recettes
nt ent
0 200.000 DA 200.000 DA
1 40.000 DA 20.000 DA
2 40.000 DA 30.000 DA
3 40.000 DA 50.000 DA
4 40.000 DA 40.000 DA
5 40.000 DA 90 000 DA
6 40.000 DA 90 000 DA

INT1801/ RECHERCHE PROPRIETE CNFEPD

Total 240.000 320 000 DA
DA

INT1801/ RECHERCHE PROPRIETE CNFEPD

Pour le projet A ; on remarque que le capital investi est récupéré au bout de cinq

ans : 40000 + 40000 + 40000 + 40000 + 40000 = 200000 DA.

Pour le projet B ; on remarque que le capital investi est récupéré au bout de

quatre ans et quelques mois ; alors le projet le plus rentable est le projet B.

a- Les inconvénients de cette méthode :

- Elle ne prend pas le facteur temps dans l’analyse parce que les flux ne sont pas
actualisés ;

- Elle ignore les flux qui interviennent après la récupération du capital investi ; c’est
–à- dire le total général des flux ;

- Il est très important de signaler que la méthode de délai de récupération ne

peut être appliquée que si les projets à comparer ont des durées de vie égales.

b- Les avantages de cette méthode :

- La rapidité est le meilleur avantage que présente les critères (le procédé ou la
méthode) du délai de récupération ;

- S’agissant d’un instrument qui détermine la rapidité de récupération du capital

investi ; c’est donc un critère qui permet d’apprécier la liquidité que peut produire
le projet.

Remarque : Ce critère est généralement utilisé quand :

- L’entreprise manque de liquidité ;

- Les actionnaires souhaitent récupérer rapidement leurs fonds ;
- L’avenir présente des risques ; il serait alors prudent de récupérer le plus vite
le capital investi.

2- La méthode financière (Radio) :

Cette méthode consiste à exprimer en pourcentage le bénéfice obtenu par rapport
au capital investi, il s’agit du taux de rentabilité de l’investissement.

Taux de
Bénéfice annuel
rentabilité  Capital investi  100

Le bénéfice annuel peut être variable pendant la durée d’utilisation de

l’investissement, alors on met au numérateur le bénéfice moyen annuel, et au
dénominateur on met le capital moyen investi ; on notera ce dernier CMI.

C  Capital investi  La valeur résiduelle

2
MI

Taux de rentabilité
INT1801/ RECHERCHE PROPRIETE CNFEPD
 Bénéfice moyen annuel
 Capital moyen investi
Selon cette méthode, il faut prévoir le cash flow.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Exemple N° 4 : Soit à étudier le projet d’investissement dont l’exploitation doit
durer 5 ans dans une société soumise à l’IBS au taux de 30% ; il est prévu un
investissement initial de
200.000 DA et une valeur résiduelle nulle en fin d’exploitation.

Années Produits Charges

1 170.000 DA 120.000 DA
2 194.000 DA 130.000 DA
3 228.000 DA 150.000 DA
4 267.000 DA 175.000 DA
5 316.000 DA 210.000 DA

Calculer les cash-flows réalisés annuellement ainsi que le taux de rentabilité.

Calcul de l’amortissement (noté Amort) :

L’amortisseme
investissement initial
nt  durée de vie du projet

Dans notre exemple : amort = 200.000/5 = 40.000

Calcul du bénéfice brut :

Pour chaque année ; le bénéfice brut est calculé par la formule

suivante : Le bénéfice brut = produit – (charge décaissée +

l’amortissement).

Par exemple pour l’année 1 :

Le bénéfice brut = produit – (charge décaissée + l’amortissement).

= 170.000– (120.000 + 40.000) =170.000–160.000
= 10.000 DA.

Calcul de l’IBS :

IBS= Le bénéfice brut 

30% Par exemple pour

l’année 1 :
IBS= le bénéfice brut  30% = 10.000  30% = 10.000 3/100 = 3.000

Calcul du bénéfice net d’impôt :

Le bénéfice net d’impôt = le bénéfice net –

l’IBS. Par exemple pour l’année 1 :

Le bénéfice net d’impôt = le bénéfice net – l’IBS = 10.000 – 3.000 = 7.000 DA.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Calcul du cash flow :

Annuellement, le cash flow est calculé par la formule suivante :

INT1801/ RECHERCHE PROPRIETE CNFEPD

 Le cash flow = l’amortissement + bénéfice net

d’impôt. Par exemple pour l’année 1 :

Le cash flow = l’amortissement + bénéfice net d’impôt

= 40.000 + 7.000 = 47.000DA

Le tableau suivant résume le calcul du cash-flow :

Années Produits Charges Résult IBS Résult Cas

at brut 30 at net h-
Ch. décaissées Amort Total % d’impôt flow
1 170.000 120.000 40.000 160.000 10.000 3.000 7.000 47.000
2 194.000 130.000 40.000 170.000 24.000 7.200 16.800 56.800
3 228.000 150.000 40.000 190.000 38.000 11.400 26.600 66.600
4 267.000 175.000 40.000 215.000 52.000 15.600 36.400 76.400
5 316.000 210.000 40.000 250.000 66.000 19.800 46.200 86.200

Le calcul du taux de rentabilité, nécessite le calcul du bénéficie moyen annuel

(BMA) et du capital moyen investi (CMI).

Le bénéfice moyen annuel (BMA) est la somme des cash flow divisée par le nombre

d’années ; BMA= (47.000 + 56.800 + 66.600 + 76.400 + 86.200)/5 = 333.000/5

= 66.600DA.
Le capital moyen investi (CMI) est calculé par la formule :

Le capital  La valeur résiduelle

CMI
invetis 2
=

CMI = (200.000 – 0) /2 = 100.000 DA

Alors le taux de rentabilité est : 66.600 /100.000 = 0,666 = 66,6 %

Le taux de rentabilité est 66,6%

a- Les avantages de cette méthode :

- Elle prend en considération tous les flux ;

- Elle est simple.

b- Les inconvénients de cette méthode :

- Elle ne prend pas le facteur temps en considération.

3- La valeur actuelle nette (V.A.N) :

Tout investissement est un échange entre des dépenses présentes et des recettes
futures ; l’actualisation est devenue nécessaire parce qu’il n’est pas possible de

INT1801/ RECHERCHE PROPRIETE CNFEPD

comparer entre des dépenses d’investissement enregistrées dans le présent et des
recettes d’exploitation générées par ce projet.

INT1801/ RECHERCHE PROPRIETE CNFEPD

L’actualisation est un instrument de comparaison entre le présent et l’avenir et
permet à ce titre d’orienter le choix d’investissement.

Avant d’étudier l’actualisation ou de monter l’impact de l’actualisation ; on étudie

d’abord la notion de capitalisation avec l’intérêt composé.

a- La capitalisation :Supposons une somme de 1000 DA placée à

intérêts composés pendant trois ans, au taux annuel de 10% sa valeur acquise sera
:

A la fin de la 1ère année = 1000 + 1000 × 10% = 1000 +

100 = 1100 DA A la fin de la 2ème année = 1100 +
1100+10% = 1100+110= 1210 DA
A la fin de la 3ème année = 1210 +1210 ×10% = 1210+121=1331 DA.

Les tables financières d’intérêts composés donnent directement le montant global

qui sera encaissé à la fin de la période n pour un taux donné, pour l’exemple
précédent, la table financière donne pour un taux d’intérêt de 10% et une durée de
3 ans, un coefficient de 1,331; en appliquant ce coefficient à la somme investi, on
trouve le montant: 1000DA × 1,331
= 13331 DA.

Exemple N°05 :

Calculer C5 la valeur acquise de la somme C 0 = 120.000 DA placée à intérêts

composés au taux de 16% après 5 ans.

C5 = C0 (1+0,16)5 = 252.041 DA

Exemple N°06 :

Calculer C4, C8, C10 les valeurs acquises de la somme d’argent C0 = 45.000 DA
placée à intérêts composés au taux de 5,5% respectivement après la 4 ème, la 8ème et
la 10ème année.

C4 = C0 (1 + 0,055)4 = 55.747,10 DA
C8 = C0 (1+ 0,055)8 = 69.060,89 DA
C10 = C0 (1 + 0,055)10 = 76.866,50 DA

b- L’actualisation :C’est le phénomène inverse de la capitalisation si on reçoit

1 DA aujourd’hui vaut (1 + i) 1 DA. Pendant un an on peut comprendre que 1 DA
disponible dans un an vaut aujourd’hui 1/(1+i)1.

De façon plus générale si 1 DA vaut (1 + i) n DA après n années, il est normal que 1

DA paru dans n années vaut en réalité aujourd’hui n/(1 + i) n.
En résumé :

- Notion de capitalisation : 1 DA aujourd’hui vaudra (1 + i) n dans n années ;

- Notion d’actualisation : 1/ (1 + i) n DA aujourd’hui valait 1 DA il y a n années.

On peut généraliser par les notations

INT1801/ RECHERCHE PROPRIETE CNFEPD
suivantes : Cn = C0 (1+i)n
C0 = Cn (1 +i )-n

INT1801/ RECHERCHE PROPRIETE CNFEPD

Exemple N°07 :

Quelle est la valeur actuelle d’une somme de 500.000 DA qui sera obtenue dans 5
ans sachant que le taux d’actualisation est de 4%.

C0 = 500.000 (1+0,04)-5 = 410.963,55 DA

Exemple N° 08 :

Quelle est la valeur actuelle des sommes suivantes qui seront perçues dans le futur
à une année donnée ?

Somme Nombr Taux

à e d’actualisatio Valeur actuelle
percevoi d’anné n en %
r es
744 DA 8 4 C0 = 744 (1+0,04)-8=
543,63 DA
2.543 DA 4 8 C0 = 2.543(1+0,08)-4
=
1.311 ,65 DA
1.213 DA 20 7 C0 = 1.213 (1+0,07)-
20 =
313,46 DA
22 DA 12 14 C0 = 22(1+0,14)-12
=
4,56 DA
343 DA 8 12 C0 = 343 (1+0,12)-8=
138,53 DA

La méthode VAN consiste à calculer le revenu global actualisé par différence entre
le cash- flow, la capacité d’autofinancement actualisés et les dépenses
d’investissement à une date initiale située un an avant que n’apparaisse le premier
résultat. Si on désigne par n la durée de vie d’un projet d’investissement.
D0 : la dépense d’investissement
initiale R1,R2 ,R3,… ,Rn-1,Rn : les
cash-flow
t : le taux d’actualisation.

0 1 2 3 4 n-1 n

DO R1 R3 Rn-1 Rn
R2 R4

R1(1+t)-1

INT1801/ RECHERCHE PROPRIETE CNFEPD

 R2(1+t)-2

R3(1+t)-3

INT1801/ RECHERCHE PROPRIETE CNFEPD

Le revenu global actualisé = la somme des cash flow actualisés – la
dépense initiale d’investissement.

On exprime le revenu global actualisé par : la valeur actuelle nette (VAN) et le

bénéfice actuel net (BAN).

Il faudra que la différence entre les recettes actualisées et la dépense initiale soit

positive. Cette différence va permettre de :

- Récupérer la dépense initialement investie ;

- Payer les intérêts des emprunts qui ont financé le projet d’investissement ;
- S’enrichir !

Remarques :

1-Selon cette méthode tout projet qui présente une VAN négative est rejeté ;
2-Entre deux projets, on choisit celui qui présente la VAN la plus élevée.

Exemple N°09 : Soit le projet suivant dont les cash flow sont les suivants :

Année Cash-flow
s
0 1650 DA
1 1000 DA
2 900 DA
3 800 DA
4 700 DA

Calculer la VAN de ce projet sachant que le taux d’actualisation est de 12%.

Solution :Calculons d’abord les cash flow actualisés sur le tableau ci-dessus :

Année Cash-flow Cash flow actualisé

s
0 1.650 DA
1 1.000 DA 1.000(1,12)-1 =
892,85
DA
2 900 DA 900(1,12)-2= 717,47DA
3 800 DA 800(1,12)-3= 569,42
DA
4 700 DA 700(1,12)-4 = 444,86
DA

VAN = somme des cash flow actualisés – la dépense initiale

= (892 ,85 + 717,47 + 569,42 + 444,86) – 1.650 = 2.624,6 – 1.650
= 974,6 DA.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Exemple N° 10 : Soit le projet d’investissement dont la dépense initiale est de
80.000 DA, les flux futurs sont les suivants :

Année Flux
s
1 8.000 DA
2 12.000 DA
3 18.000 DA
4 30.000 DA
5 30.000 DA
6 30.000 DA
7 30.000 DA
8 30.000 DA

Calculer la VAN au taux d’actualisation de 9,5%.

Solution : Comme pour l’exemple précédent ; on calcule d’abord les flux actualisés :

Année flux flux actualisé

s
1 8.000 DA 8.000 (1,095)-1 = 7.309,93
DA
2 12.000 DA 12.000 (1,095)-2 =
10.008,13DA
3 18.000DA 18.000 (1,095)-3= 13.709,76
DA
4 30.000DA 30.000 (1,095)-4 = 20.867,22
DA
5 30.000DA 30.000 (1,095)-5 = 19.056,82
DA
6 30.000DA 30.000 (1,095)-6 = 17.403,49
DA
7 30.000DA 30.000 (1,095)-7 =15.893,60
DA
8 30.000DA 30.000 (1,095)-8 = 14.514,70
DA

VAN = somme des cash flow actualisés – la dépense initiale

= (7.309,93 + 10.008,13 + 13.709,76 + 20.867,22 + 19.056,82 + 17.403,49
+
15.893,60+ 14.514,70)-80.000 =
31.759,65 DA La VAN est : 31.759,65 DA

Exemple N°11 :Soit les deux projets suivants :

Année Projet A Projet B

s Les flux Flux
D0 Flux des D0 Flux actualisés
recettes au
taux de
10%
INT1801/ RECHERCHE PROPRIETE CNFEPD
 0 1.000 DA 1.000 DA

1 100 DA 90,90 DA 250DA 227,27 DA

2 300 DA 247,93 DA 350DA 289,25 DA

3 500 DA 375,65 DA 450DA 338,09 DA

4 700 DA 478,10 DA 550DA 375,65 DA

Total 1.192,58 DA 1.230,26 DA

Dites quel est le projet le plus rentable selon la VAN et selon le délai de récupération.

Réponse :

La VAN du projet A est : 1.192,58 – 1.000 =

192,58 DA La VAN du projet B est : 1.230,26 –
1.000 = 230,26 DA

Selon la méthode VAN ; le projet B est plus rentable car il présente la plus grande VAN.

Selon le délai de récupération ; le projet B est le plus rentable car la dépense est
récupérée au bout de la 3ème année ; alors que celle de A n’est récupérée qu’au
bout de la 4ème.

c- Les avantages de la méthode VAN :

- C’est le critère de choix d’investissement le plus complet dans la mesure où on

raisonne à partir des flux actualisés ;
- Tous les flux sont pris en compte sur la durée totale du projet d’investissement.

d- Les inconvénients de la méthode VAN :

- Impossibilité de comparer des VAN des projets dont la durée de vie est différente ;
- L’importance des flux générés est différente selon la durée de vie et des projets
dont les dépenses sont différentes, d’où le problème de choix du taux
d’actualisation.

4- Le taux de rentabilité interne (TRI) :

Définition : le taux de rentabilité est un taux d’actualisation qui donne une VAN nulle
(=0).

Exemple N°12 : Soit le projet d’investissement avec les conditions suivantes :

Année Flux nets

s
0 -10.000 DA
INT1801/ RECHERCHE PROPRIETE CNFEPD
 1 2.000 DA
2 5.000 DA
3 6.000 DA

Note : la valeur -10.000 indique que la dépense est

10.000DA. Calculer la VAN aux taux suivants : 8%, 10%, 12%,

13%.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Solution :

VAN1  2.000 1,08  5.000 1,08  2  6.000 1,8  3   10.000


 1 

 1.851,85   4.762,99  10.000   10.000
4.286,69 10.901,53
 901,53DA
VAN2  2 3 
1  5.0001,1  6.0001,1  10.000
2.0001,1  

 1.818,18  4.132,23  4.507,88 10.000  10.458,29  10.000
 458,29DA
VAN3  2.000 1,12   5.000 1,12  2  6.000 1,12  3   10.000
1  

 10.042,35  10.000  42,35DA


VAN4  2.000 1,13   5.000 1,13   6.000 1,13 
1 2 3
 10.000
 9.843,94  10.000  156,06DA

À partir du taux de 8% ; la VAN diminue au fur et à mesure que le taux

d’actualisation augmente arrivant au point ou cette VAN s’annule, ce point est
justement le niveau du taux de rentabilité interne.

La VAN s’annule quand la somme des flux actualisés est égale à la dépense initiale ;
autrement dit le taux de rentabilité interne détermine le coût maximum des
capitaux que pourrait supporter le projet.

On peut déterminer le taux de rentabilité interne par la méthode d’interpolation

linéaire qui consiste à :

12% → VAN = 42,35 DA

X → VAN = 0
13 % → VAN = 156,06
X = 0,12 + (0,13 – 0,12) (42,35/ (42,35 + 156,06))
= 0,12 + 0,01 (42,35/198,41)= 0,1221

D’où TRI = 12,21%.

INT1801/ RECHERCHE PROPRIETE CNFEPD

 EXERCICES CORRIGES :
EXERCICE N°01 :
Soient les deux projets d’investissement A et B suivants :

Années Projet A Projet B

Produits Charges Amortisseme Produits Charges Amortisseme
nt nt
0 - 30.000 - - 45.000 -
1 100.000 75.000 6.000 100.000 60.000 9.000
2 120.000 90.000 6.000 120.000 72.000 9.000
3 140.000 105.000 6.000 140.000 84.000 9.000
4 160.000 120.000 6.000 160.000 96.000 9.000
5 180.000 135.000 6.000 180.000 108.000 9.000

Travail demandé :
1-Présenter un tableau qui montre le calcul des cash-flows réalisés
annuellement sachant que le taux d’IBS est de 30%.

2-Dire quel est le projet le plus rentable selon :

- La méthode VAN ;
- Le délai de récupération.

Note : Le taux d’actualisation est de 10%.

Exercice N°02 :
Soient les deux projets d’investissement A et B suivants :

Années Projet A Projet B

Produit Charges Produit Charges
s décaissées s décaissées
0 - - - -
400.000 350.000
1 250.000 100.000 245.000 98.000
2 350.000 200.000 195.000 100.000
3 270.000 90.000 200.000 110.000
4 400.000 30.000 250.000 130.000
5 200.000 50.000 390.000 210.000
Valeur 9.000 - - -
résiduelle

Travail demandé :
1-Calculer l’amortissement annuel de chaque projet.

INT1801/ RECHERCHE PROPRIETE CNFEPD

2-Calculer la capacité d’autofinancement pour chaque projet.
3-Quel est le projet le plus rentable selon la

VAN ? Note : le taux d’actualisation est 10%.

Exercice N°3 :
Une entreprise envisage de changer ses procédés de fabrication. Pour cela, elle doit
acquérir un ensemble de matériels pour une somme globale de 200.000 DA, le
financement se fera de la façon suivante :

- 100.000 DA à l’aide de fonds propres à l’entreprise ;

- Le reste soit 100.000 DA à l’aide d’un emprunt.

La durée de vie probable de ce projet d’investissement est de 5 ans, l’emprunt est

remboursable sur 5 ans ; l’annuité de la somme remboursable est de 35.000 DA.

Les prévisions des produits et des charges décaissées à l’exclusion des annuités
sont données dans le tableau suivant :

Année Produi Charge

s ts s
1 170.000 120.000
2 194.000 130.000
3 228.000 150.000
4 267.000 175.000
5 316.000 210.000
Travail à faire :
Calculer la capacité d’autofinancement.

Exercice N° 4 :
Une entreprise souhaite acquérir un certain matériel industriel en vue de
l’ouverture prochaine d’une nouvelle branche d’activité, elle a le choix entre trois
types de matériel dont les caractéristiques sont résumées dans le tableau suivant :

Matériel Matériel B Matériel C

A
Prix d’acquisition 250.000 200.000 230.000
Cap-fin année 70.000 30.000 38.000
(1)
Cap-fin année 72.000 40.000 42.000
(2)
Cap-fin année 76.000 70.000 81.000
(3)
Cap-fin année 71.000 90.000 84.000
(4)
Cap-fin année 68.000 80.000 69.000
(5)
INT1801/ RECHERCHE PROPRIETE CNFEPD
 Valeur résiduelle 5000 0 0

Remarque : Cap-fin est la capacité d’autofinancement.

INT1801/ RECHERCHE PROPRIETE CNFEPD

Travail à faire :
Parmi ces trois projets d’investissement ; dire lequel est le plus rentable ;
sachant que le taux d’actualisation est 10%.

INT1801/ RECHERCHE PROPRIETE CNFEPD

 CORRECTION DES EXERCICES :
Exercice N°1 :
Pour le projet A :
Pour l’année 1 :

Le total des charges = charges décaissées + l’amortissement

= 75.000 + 6.000 = 81.000 DA
Le bénéfice brut ou résultat = produits – total des charges
= 100.000 – 81.000 = 19.000 DA

L’IBS = le résultat brut  30%

= 19.000  30% = 5.700 DA

Le résultat net d’impôt = résultat brut – l’IBS

= 19.000 – 5.700 = 13.300 DA
Le cash flow= résultat net d’impôt +
l’amortissement
= 13.300 + 6.000 = 19.300 DA.

Pour l’année 2 :

Le total des charges = charges décaissées + l’amortissement

= 90.000 + 6.000 = 96.000 DA
Le bénéfice brut ou résultat = produits – total des charges
= 120.000 – 96.000 = 24.000 DA
L’IBS = le résultat brut  30%
= 24.000  30% = 7.200 DA
Le résultat net d’impôt = résultat brut – l’IBS
= 24.000 – 7200 = 16.800 DA
Le cash flow = résultat net d’impôt + l’amortissement
= 16.800 + 6.000 = 22.800 DA

Pour l’année 3 :

Le total des charges = charges décaissées + l’amortissement

= 105.000 + 6.000 = 111.000 DA

Le bénéfice brut ou résultat = produits – total des charges

= 140.000 – 111.000 = 29.000 DA
L’IBS = le résultat brut  30%
= 29.000 30% = 8.700 DA
Le résultat net d’impôt = résultat brut – l’IBS
= 29.000 – 8.700 = 20.300 DA
Le cash flow = résultat net d’impôt +
l’amortissement
= 20.300 + 6.000 = 26.300 DA

INT1801/ RECHERCHE PROPRIETE CNFEPD

De même pour les années 4 et 5 ; ce qui permet d’obtenir le tableau suivant :

INT1801/ RECHERCHE PROPRIETE CNFEPD

 Cash
Charges Résult IBS 30% Résult flow
Année Produit at brut at net
s s Ch.décaissée Amort Total d’impôt
s
0 – 30.000 – 30.000
1 100.000 75.000 6.000 81.000 19.000 5.700 13.300 19.300
2 120.000 90.000 6.000 96.000 24.000 7.200 16.800 22.800
3 140.000 105.000 6.000 111.000 29.000 8.700 20.300 26.300
4 160.000 120.000 6.000 126.000 34.000 10.200 23.800 29.800
5 80.000 135.000 6.000 141.000 39.000 11.700 27.300 33.300

Pour le projet B :

Pour l’année 1 :
Le total des charges = charges décaissées + l’amortissement
= 60.000 + 9.000 = 69.000 DA
Le bénéfice brut ou résultat = produits – total des charges
= 100.000 – 69.000 = 31.000 DA

L’IBS = le résultat brut 30%

= 31.000 30% = 9.300 DA

Le résultat net d’impôt = résultat brut – l’IBS

= 31.000 – 9.300 = 21.700 DA
Le cash flow = résultat net d’impôt +
l’amortissement
= 21.700 + 9.000 = 30.700 DA
Pour l’année 2 :

Le total des charges = charges décaissées + l’amortissement

= 72.000 + 9.000 = 81.000 DA
Le bénéfice brut ou résultat = produits – total des charges
= 120.000 – 81.000 = 39.000 DA
L’IBS = le résultat brut 30%
= 39.000 30% = 11.700 DA

Le résultat net d’impôt = résultat brut – l’IBS

= 39.000 – 11.700 = 21.300 DA
Le cash flow = résultat net d’impôt +
l’amortissement
= 27.300 + 9.000 = 36.300 DA

Pour l’année 3 :

Le total des charges = charges décaissées + l’amortissement

= 84.000 + 9.000 = 93.000 DA
Le bénéfice brut ou résultat = produits – total des charges
INT1801/ RECHERCHE PROPRIETE CNFEPD
 = 140.000 – 93.000 = 47.000 DA

INT1801/ RECHERCHE PROPRIETE CNFEPD

L’IBS = le résultat brut 30%
= 47.000 30% = 14.100 DA

Le résultat net d’impôt = résultat brut – l’IBS

= 47.000 – 14.100 = 32.900 DA
Le cash flow = résultat net d’impôt +
l’amortissement
= 32.900 + 9.000 = 41.900 DA

De même pour les années 4 et 5 ; ce qui permet d’obtenir le tableau suivant :

Charges Résult Cas

Résult IBS at net h
Année Produit Ch.décais Amor Total at brut 30% d’impôt flo
s s s ées t w

0 – 45.000 – 45.000
1 100.000 60.000 9.000 69.000 31.000 9.300 21.700 30.700
2 120.000 72.000 9.000 81.000 39.000 11.700 27.300 36.300
3 140.000 84.000 9.000 93.000 47.000 14.100 32.900 41.900
4 160.000 96.000 9.000 105.000 55.000 16.500 38.500 47.500
5 180.000 108.000 9.000 117.000 63.000 18.900 44.100 53.100

Calcul du cash-flow actualisé :

Pour le projet A :

Année Flux Flux actualisés

s
1 19.300 DA = 19.300 (1,1)-1 = 17.545,45
DA
2 22.800 DA = 22.800 (1,1)-2 = 18.842,97
DA
3 26.300DA =26.300 (1,1)-3 = 19.759,57
DA
4 29.800DA = 29.800 (1,1)-4 = 20.353,80
DA
5 33.300DA = 33.300 (1,1)-5 = 20.676,68
DA

La VAN = somme des flux actualisés – dépense initiale

=(17.545,45+18.842,97+19.759,57+20.353,8+20.676,68)-30.000
= 97.178,47 – 30.000 = 67178.47 DA

Pour le projet B :

Année Flux Flux actualisés

s
1 30.700 DA = 30.700 (1,1)-1 = 27.909,09
DA
2 36.300 DA = 36.300 (1,1)-2 = 30.000 DA
INT1801/ RECHERCHE PROPRIETE CNFEPD
 3 41.900 DA = 41.900 (1,1)-3 = 31.480,09
DA
4 47.500 DA = 47.500 (1,1)-4 = 32.443,13
DA
5 53.100 DA = 53.100 (1,1)-5 = 32.970,92
DA

INT1801/ RECHERCHE PROPRIETE CNFEPD

 De même :

La VAN = somme des flux actualisés – dépense initiale

= (27.909,09 + 30.000 + 31.480,09 + 32.443,13 + 32.970,92)
– 45.000 = 109.803,23 DA

Elle est supérieure à la VAN du projet

A. Selon la VAN ; le projet B est plus

rentable.

Et les deux projets présentent le même délai de récupération (un an et quelques mois).

Exercice N°2 :
1- Calcul des amortissements :
L’amortissement annuel = la dépense initiale/durée de vie du

projet. Pour le projet A ; l’amortissement = 400.000/5 =

80.000 DA

Pour le projet B ; l’amortissement = 350.000/5 = 70.000 DA

2- Calcul des capacités d’autofinancement :

Pour le projet A :

Charges Résult Cas

Années Produit Résult IBS at net h
s Ch.décaissé Amort Total at brut 30% d’impôt flo
es w
0 – 400.000 – 400.000
1 250.000 100.000 80.000 180.000 70.000 21.000 49.000 129.000
2 350.000 200.000 80.000 280.000 70.000 21.000 49.000 129.000
3 270.000 90.000 80.000 170.000 100.000 30.000 70.000 150.000
4 400.000 30.000 80.000 380.000 20.000 6.000 14.000 94.000
5 200.000 50.000 80.000 130.000 70.000 21.000 49.000 129.000

Pour projet B :

Charges
Années Produits Résult IBS Résult Cas
Ch. Amort Total at brut 30 at net h-
décaissées % d’impôt flow

0 – 350.000 – 350.000
1 245.000 98.000 70.000 168.000 77.000 23.100 53.900 123.90
0
2 195.000 100.000 70.000 170.000 25.000 7.500 17.500 87.50
INT1801/ RECHERCHE PROPRIETE CNFEPD
 0
3 200.000 110.000 70.000 180.000 20.000 6.000 14.000 84.00
0
4 250.000 130.000 70.000 200.000 50.000 15.000 35.000 105.00
0
5 390.000 210.000 70.000 280.000 110.000 33.000 77.000 147.00
0

INT1801/ RECHERCHE PROPRIETE CNFEPD

Calcul des cash flow actualisés :

Pour le projet A :

Année Flux Flux actualisés

s
1 129.000 DA = 129.000 (1,1)-1 =
117.272,72
DA
2 129.000 DA = 129.000 (1,1)-2 =
106.611,57
DA
3 150.000DA = 150.000 (1,1)-3 =
112.697,22DA
4 94.000 DA = 94.000 (1,1)-4 =

64.203,26
DA
5 129.000 DA = 129.000 (1,1)-5 =

80.098,85
DA

Pour le projet B :

Année Flux Flux actualisés

s
1 123.900 DA = 123.900 (1,1)-1 =
112.636,36
DA
2 87.500 DA = 87.500 (1,1)-2 = 72.314,05
DA
3 84.000DA = 84.000 (1,1)-3 = 63.110,44
DA
4 105.000 DA = 105.000 (1,1)-4 =
71.716,41 DA
5 147.000 DA = 147.000 (1,1)-5 =
91.275,43 DA

La VAN = somme des flux actualisés – dépense initiale

Pour le projet A : on trouve VAN = 80.883,62 DA

Pour le projet B : on trouve VAN = 60.653,26 DA ; le projet A est donc le plus rentable.

Exercice N°3 :
Le calcul des capacités d’autofinancement est résumé dans le tableau suivant :

Charges

INT1801/ RECHERCHE PROPRIETE CNFEPD

Anné Produit Ch. Amort Total Résult Résult Capacité
es s décaissées at brut at net d’autofinance
d’impôt m ent
1 170.000 155.000 20.000 175.000 –5.000 –2.500 17.500
2 194.000 165.000 20.000 185.000 9.000 4.500 24.500
3 228.000 185.000 20.000 205.000 23.000 11.500 31.500
4 267.000 210.000 20.000 230.000 37.000 18.500 38.500
5 316.000 245.000 20.000 265.000 51.000 25.500 45.500

INT1801/ RECHERCHE PROPRIETE CNFEPD

Exercice N°4 :
Calcul de la VAN pour le projet A :
70.0001,1 1  72.0001,1 2  76.0001,1 3  71.0001,1 4  68.0001,1 5  5.0001,1 5 
250.000 = 24.061,6 DA
 

Calcul de la VAN pour le projet B :

30.0001,1 1  40.0001,1 2  70.0001,1 3  90.0001,1 4  80.0001,1 5  
 
200.000  24.067,53DA

Calcul de la VAN pour le projet C :

38.0001,1 1  42.0001,1 2  81.0001,1 3  84.0001,1 4  69.0001,1 5  
 
230000  329,38 DA
Le projet B et le plus rentable car il a la plus grande VAN.

INT1801/ RECHERCHE PROPRIETE CNFEPD