PREMIERE PARTIE : PROGRAMMATION LINEARE

I FORMULATION DU PROGRAMME

II RESOLUTION PAR LA METHODE GRAPHIQUE

III- RESOLUTION PAR LA METHODE DU SIMPLEXE

DEUXIEME PARTIE : ORDONNANCEMENT

I- THEORIE DES GRAPHES

II- ORDONNANCEMENT DES TACHES METHODE DES POTENTIELS

METRA (MPM)

Support de cours
RECHERCHE OPERATIONNELLE

Tout gestionnaire avisé et prudent face aux ressources rares et limitées avec certaines
contraintes doit penser à une formulation d’un raisonnement adéquat conduisant à
l’amélioration de la rentabilité de l’entreprise à produits multiples. Aujourd’hui, il est rare
de trouver des entreprises industrielles qui ne fabriqueraient qu’un seul produit.
« La recherche opérationnelle c’est l’ensemble des recherches qui permettent de
déterminer les résultats les plus favorables qu’il est possible d’atteindre et les méthodes
pour y parvenir : organisation, programmes, plans, répartition des moyens, méthodes
d’exploitation, etc. (Paul ROBERT)
La recherche opérationnelle est donc l’ensemble des méthodes et modèles scientifiques
que l’on peut utiliser pour élaborer une stratégie reposant sur des prises de décision.
En quelques décennies, les techniques de la recherche opérationnelle se sont
considérablement développées sous l’impulsion de plusieurs facteurs :
- la création de modèle mathématique pour analyser les phénomènes économiques.
- le déroulement des opérations militaires pendant la 2ème guerre mondiale
(organisation des raids de forteresses volantes de façon à obtenir le maximum de
destruction tout en essuyant le minimum de perte ; organisation des convois
maritimes entre les Etats-Unis et la Grande Bretagne).
Dès que nous nous trouvons en présence d’un problème d’objectif à atteindre dans les
meilleures conditions compte tenu des contraintes à respecter, nous pouvons faire appel
pour le résoudre au modèle et méthode de la recherche opérationnelle. Les domaines
d’application de la recherche opérationnelle sont nombreux :
 les problèmes d’optimisation en avenir certain : adaptation de la production au meilleur
Chiffres d’Affaire, gestion des stocks; choix des investissements et des financements les
plus rentables, problèmes de transport etc.
les problèmes de décision en avenir incertains : renouvellement des stocks, politique
d’approvisionnement et de vente, problème d’usure et de maintenance des équipements.

Support de cours
PREMIERE PARTIE : PROGRAMMATION LINEARE

Objectif :

Au terme de cette partie, vous serez capable de :

- formaliser un problème concret d’optimisation linéaire en vue de le résoudre ;
- reconnaitre pour un programme linéaire donné, l’ensemble des solutions admissibles ;
- déterminer par différents procédés, la solution optimale d’un programme linéaire en tenant
compte de l’ensemble des contraintes.
Prérequis
Pour mieux appréhender cette 1ere partie, il est nécessaire de savoir résoudre une inéquation
du premier degré à deux inconnues et également maitriser la représentation graphique d’une
fonction linéaire de la forme puis l’utilisation des techniques d’échelonnement en calcul
matriciel que nous allons rappeler aux étudiants

Introduction

Parmi toutes les techniques et modèles mathématiques utilisées en recherche

opérationnelle la programmation linéaire occupe une place prépondérante. Elle
consiste à déterminer l’optimum d’une fonction multivariable linéaire appelée fonction
économique ou objectif sous certaines contraintes elles même linéaires sous forme
d’inégalités ou d’égalités.

Support de cours
 CHAPITRE I
FORMULATION DU PROGRAMME OU MODELISATION

En recherche opérationnelle formuler un programme ou modéliser le programme consiste

à faire l’identification de trois choses
 Les variables intrinsèques ou encore variables inconnues
 Les différentes contraintes
 L’objectif visé (optimisation)
Il est à noter que dans un problème de programmation linéaire les objectifs e t les
contraintes sont des fonctions linéaires
En programmation linéaire retenons que les expressions :
au moins, au minimum font appel à supérieur ou égal    et les expressions au plus, au
maximum, capacité, disponibilité, en stock etc. font appel à inférieur ou égal    .

Activités préparatoires
Activité 1

Un pépiniériste propose à un grand magasin des sapins sous deux conditionnements

différents:
- les uns avec motte de terre, pesant 10 kg, au prix de 50 francs l'un.
- les autres sans motte, pesant 5kg, au prix de 40 francs l'un.
Le pépiniériste n'accepte que les commandes d'au moins 300 sapins de chaque type.
Le transporteur dispose d'un camion dont la charge ne peut dépasser 10 500 kg. Il n'assure
la livraison que si elle est d'au moins 1 000 arbres.
Le magasin dispose de 66 000 francs pour approvisionner son rayon sapins.
Sachant que les sapins commandés par le magasin seront vendus au prix de 90 francs
pièce pour ceux avec motte et au prix de 50 francs pièce pour les autres.
Ecrire un programme linéaire permettant de maximiser le chiffre d'affaires
En résumé le problème se modélise sous la forme d’un programme linéaire

1- Définissons les variables

Support de cours
On désigne par : x1 et x2 les nombres respectifs de sapins avec motte et sapins sans
motte.
2- Ecriture de la fonction économique
Désignons par Z le chiffre d’affaires des sapins vendus, on a : Z : 90x1  50x2

3- Ecriture des contraintes

- Contraintes liées à la charge : 10x1  5 x2  10500

- Contraintes liées au nombre total d’arbre : x1  x2  1000

- Contraintes liées au nombre de sapins avec motte : x1  300

- Contraintes liées au nombre de sapins sans motte : x2  300

- Contraintes liées au coût : 50x1  40x2  66000

4- Ecriture du programme linéaire

Max Z : 90x1  50x2
10x1  5 x 2  10500
 x  x  1000
 1 2


 x1  300
S / C
 x 2  300
50x1  40x 2  66000


 xi  0

Activité 2
Le conseil municipal de la ville de BONOUA décide de rénover un jardin public. Pour cela, il
aura besoin d’au moins 1 600 plants de lauriers, 600 pieds de rosiers et 1 500 pieds de ficus.
Sur le marché, deux fleuristes proposent ces plants mais par lots.
Le premier fleuriste propose son lot (A) comprenant 15 rosiers, 20 lauriers et 15 ficus à 4 000
F ; le second propose sont lot (B) comprenant 5 rosiers, 20 lauriers et 25 ficus à 3 000 F
Ecrire un programme linéaire pour que la rénovation soit la plus économique possible puis

1- Définissons les variables

On désigne par : x1 et x2 les nombres respectifs de lots A et de lots B.

2- Ecriture de la fonction économique

Désignons par Z le coût total réalisé, on a :
Min Z : 4000x1  3000x2
3- Ecriture des contraintes
- Contraintes liées au nombre de plants de lauriers : 20x1  20x2  1600

Support de cours
 - Contraintes liées au nombre de plants de rosiers : 15x1  5x2  600
- Contraintes liées au nombre de plants de ficus : 15x1  25x2  1500
4- Ecriture du programme linéaire

MinZ : 4000x1  3000x2

20 x1  20 x 2  1600
15x  5 x  600
 1 2
S / C
15 x1  25 x 2  1500

 xi  0

Support de cours
 CHAPITRE II
RESOLUTION PAR LA METHODE GRAPHIQUE

Elle consiste tout d’abord à transformer les inégalités en égalités ce qui constitue es droites à
tracer
Ensuite à procéder au régionnement du plan ce qui permet d’avoir le domaine solution
Enfin deux méthodes s’offrent au candidat. Il peut :
- tracer la droite de la fonction objectif, la déplacer parallèlement à elle-même
jusqu’à ce qu’elle ne touche le dernier point dans le domaine dans le solution dans
le cas d’une maximisation et le premier point du domaine solution dans le cas
d’une minimisation ;
- recenser les points tout autour du domaine solution remplacer les coordonnées de
ces points dans la fonction objectif et retenir comme solution optimale le point qui
donne la valeur la plus élevée dans le cas d’une maximisation et la valeur la plus
petite dans le cas d’une

Support de cours
 CHAPITRE III
RESOLUTION PAR LA METHODE DU SIMPLEXE

INTRODUCTION
La méthode graphique est limité car
ALGORITHME DU SIMPLEXE
La première forme du programme que nous écrivons est appelée communément forme
canonique du programme ou du modèle.
Forme canonique du programme
MaxZ  c1 x1  c 2 x 2  . . .  c m x m

a11 x1  a12 x 2  . . .  a1m x m  b1

a x  a x  . . .  a x  b


21 1 22 2 2m m 2

S /C : 
a x  a x  . . .  a x  b
 n1 1 n2 2 nm m n


 xi  0

Après la forme canonique du programme on doit écrire la forme standard du programme.

La forme standard du programme est obtenue en transformant les inégalités en égalités par
ajout des variables d’écarts.
Au nombre de contraintes structurelles on fait correspondre le même nombre de variables
d’écarts

Forme Standard du programme

MaxZ  c1 x1  c 2 x 2  . . .  c m x m  0e1  0e2  . . .  0en

a11 x1  a12 x 2  . . .  a1m x m  e1  b1

a x  a x  . . .  a x  e2  b2


21 1 22 2 2m m

S /C : 
a x  a x  . . .  a x  en  bn
 n1 1 n2 2 nm m


 xi  0 ; ei  0

Support de cours
 Notons que pour des raisons de commodité nous allons nous pencher sur la méthode
tabulaire du simplexe

Tableau 1

Cj 0 0 0 Contraintes Ratios
Hors base
Base
x1 x2 e1 e2 e3 bi 

0 e1

0 e2

0 e3

Zj
Cj  Z j

0 e1

0 e2

0 e3

Zj
Cj  Z j

0 e1

0 e2

0 e3

Zj
Cj  Z j

Support de cours
 Tableau 2

Cj Contraintes Ratios
Hors base
Base
x1 x2 e1 e2 e3 bi 

0 e1

0 e2

0 e3

Zj
Cj  Z j

Zj
Cj  Z j

Zj
Cj  Z j

Support de cours
 TRAVAUX DIRIGES PROGRAMMATION LINEAIRE

Exercice 1

Un fleuriste compose deux sortes de bouquets, le premier bouquet nommé bouquet

Royal comporte une branche de muflier, un gerberas et trois roses et le second nommé
bouquet de la Duchesse comporte une branche de muflier, deux gerberas et une rose.
Pour sa journée, le fleuriste dispose de douze branches de muflier, dix-huit gerberas et
trente roses.
La dépense effectuée pour un bouquet Royal est de 120 francs et 100 francs pour le
bouquet de la Duchesse. Il espère vendre chaque bouquet Royal à 170 F et le bouquet
de la Duchesse à 125 F.
Ecrire un programme linéaire permettant au fleuriste de maximiser son bénéfice.

Exercice 2

Un club de loisirs organise une sortie à laquelle participeront cent personnes. Pour la
pause du matin le responsable de la journée prévoit d’emporter au moins deux
croissants par personne, au moins deux confiseries par personne et au moins cent
cinquante boissons.
Un premier fournisseur lui propose des lots A comprenant trois croissants, une
confiserie et une boisson pour un, prix de trente francs.
Un second fournisseur lui propose des lots B comprenant un croissant, deux
confiseries et une boisson pour un prix de vingt-cinq francs.
Ecrire un programme linéaire permettant au club de minimiser les coûts.

Exercice 3

Un propriétaire de chenil nourrit ses chiens en leur apportant un minimum journalier

de 240kg de protides, 180kg de lipides et 120kg de glucide. Il existe sur le marché
deux préparations « Oua-oua » et « Beautoutou » dont les caractéristiques sont :

Oua-oua Beautoutou
Protides 3kg 2kg
Lipides 3kg 1kg
Glucides 1kg 2kg
Prix 50F 25F

1- Ecrire un programme permettant au propriétaire du chenil de minimiser les

coûts
2- Résoudre par la méthode graphique.

Support de cours
Exercice 4

Un artisan fabrique deux types de jouets A et B en bois

-Un jouet A nécessite une demi-heure de travail et 3 kg de bois .
-Un jouet B nécessite une heure de travail et 2 kg de bois .
L’artisan dispose quotidiennement de 24 kg de bois , il travaille au plus 8 heures par
jour et limite sa production quotidienne de jouet A à 7 unités.
La vente d’un jouet A rapporte un bénéfice de 80 francs, celle d’un jouet B un
bénéfice de 120 francs.
Déterminer par la méthode du simplexe le nombre de jouets de chaque type à fabriquer
pour obtenir un bénéfice maximal.

Exercice 5

Pour fleurir un parc, il faut au minimum 1200 jacinthes, 3200 tulipes et 3000 narcisses.
Deux pépiniéristes proposent leurs lots :
- Lot A : comprenant 30 jacinthes, 40 tulipes et 30 narcisses pour 75 Francs
- Lot B : comprenant 10 jacinthes, 40 tulipes et 50 narcisses pour 60 Francs
1- Ecrire un programme linéaire permettant de minimiser les dépenses
2- Résoudre graphiquement
3- Reste-t-il des fleurs pour le jardinier ?

Exercice 6

Pour pouvoir partir en voyage scolaire, une classe organise une vente de gâteaux
pendant les récréations. En une semaine, les élèves ne peuvent en fabriquer au
maximum que 60 (des gros et des petits). Chaque gros gâteau nécessite 2 œufs: chaque
petit gâteau 1oeuf. On dispose en tout de 100 œufs. Les gros gâteaux sont plus
rapidement fabriqués que les petits. Hors cuisson, il faut une heure de préparation pour
un gros gâteau et trois heures pour un petit gâteau.
Les élèves ne peuvent consacrer que 120 heures au maximum à la préparation de ces
gâteaux.
Chaque gros gâteau rapporte un bénéfice de 3$ et chaque petit gâteau un bénéfice de
2$.
1) Ecrire un programme linéaire permettant à la classe de maximiser le bénéfice.
2) Résoudre le programme par la méthode du simplexe.

Exercice 7

Le conseil municipal de la ville de BONOUA décide de rénover un jardin public. P our

cela, il aura besoin d’au moins 1 600 plants de lauriers, 600 pieds de rosiers et 1 500
pieds de ficus. Sur le marché, deux fleuristes proposent ces plants mais par lots.

Support de cours
Le premier fleuriste propose son lot (A) comprenant 15 rosiers, 20 lauriers et 15 ficus
à 4 000 F ; le second propose son lot (B) comprenant 5 rosiers, 20 lauriers et 25 ficus à
3 000 F
Ecrire un programme linéaire pour que la rénovation soit la plus économique possible
puis résoudre.

Exercice 8

La fabrication d’une pièce P1 coûte 150 euros celle d’une pièce P2 coûte 100 euros.
Chaque d’une pièce est traitée successivement dans trois ateliers.
Le nombre d’heures - machines par pièce est indiquée dans le tableau suivant
Ateliers P1 P2
A 3 1
B 4 3
C 2 3
Pour éviter le chômage technique, l’atelier A doit fournir au moins 1200 heures
machines, l’atelier B au moins 3000 heures et l’atelier C au moins 1800 heures -
machines.
1- Ecrire un programme linéaire permettant de minimiser les coûts.
2- Résoudre graphiquement le programme.

Exercice 9

La Direction d’une usine de meubles a constaté qu’il y a des temps morts dans chacun
des départements de l’usine, elle décide d’utiliser ces temps morts pour fabriquer deux
nouveaux modèles de bureaux M1 et M2 qui rapporte respectivement 300 francs et
200 francs
Les temps libres disponibles dans les départements sciage, assemblage et sablage sont
respectivement 20h, 22h et 12h.
La fabrication d’un bureau M1 nécessite : une heure de travail dans le département
sciage, deux heures en assemblage et une heure en sablage.
La fabrication d’un bureau M2 a besoin de 2 heures en sciage, une heure assemblage
et également une heure en sablage.
Ecrire le programme qui permet de maximiser le bénéfice puis résoudre par la
méthode du simplexe.

Exercice 10

Pour fleurir un parc, il faut au minimum 1200 jacinthes, 3200 tulipes et 3000 narcisses.
Deux pépiniéristes proposent leurs lots :
- Lot A : comprenant 30 jacinthes, 40 tulipes et 30 narcisses pour 75 Francs
- Lot B : comprenant 10 jacinthes, 40 tulipes et 50 narcisses pour 60 Francs
1- Ecrire un programme linéaire permettant de minimiser les dépenses
2- Résoudre graphiquement
3- Reste-t-il des fleurs pour le jardinier ?

Support de cours
DEUXIEME PARTIE : ORDONNANCEMENT

Lors de l’analyse de tout projet de grands envergure (construction d’une usine, d’un
bateau, d’avion, d’un bâtiment, lancement d’un produit,..), un des problèmes cruciaux
qui se posent est celui de la confection du calendrier d’exécution des différentes tâches
qui constituent ce projet.
Ils s‘agit de déterminer dans quel ordre doivent s’accomplir les différentes tâches de
manière à minimiser le temps total d’exécution du projet.

THEORIE DES GRAPHES

1. NOTION ESSENTIELLES EN THEORIE DES GRAPHES

1.1.Définitions et représentations
1.1.1 Définitions
Un graphe est un ensemble fini de points, les sommets, reliés par des flèches appelées arcs.
Exemples :

L’arc (A, B) a pour origine le point A et pour extrémité le point B. On dit aussi que B est un
suivant de A, et que A est un précédent de B.

Un chemin est une succession d’arcs telles que l’extrémité de chacun coïncide avec l’origine
du suivant.
Exemples :
-
-

Support de cours
Un circuit est un chemin tel que l’origine du premier arc coïncide avec l’extrémité du
dernier.

Exemples :

-
-

Une boucle est un arc, dont l’origine et l’extrémité sont confondues.

Exemple :

1.1.2 Représentations

Un graphe peut être représenté de différentes façons :

Représentation sagittale (par un schéma) exemple précédent.
Donner l’ensemble de tous les arcs

G= {(A ,B),(B,C),(B,D),(C,E),(D,E),(E,F),(F,D),(F,A)}

Le dictionnaire des précédents

SOMMETS PRECEDENTS
A
B
C
D
E
F

Le dictionnaire des suivants

SOMMETS SUIVANTS
A
B
C
D
E
F

Support de cours
La matrice Booléenne
A B C D E F
A
B
C
D
E
F
NB :
1 signifie que l’arc existe
0 signifie que l’arc n’existe pas.
Si, à tout arc qui constitue le graphe, il correspond une valeur numérique, le graphe est dit
valué. Cette valeur numérique peut présenter différentes significations telle que la distance ou
le débit qui circule entre deux sommets, ou encore le coût de transport, etc.

2- NIVEAU OU RANG DES SOMMETS DANS UN GRAPHE SANS CIRCUIT

Considérons un graphe G sans circuit.
Méthode de pratique :

1) Considérez le dictionnaire des précédents du graphe initial G0 .

2) Relevez tous les sommets sans précédent : ils ont pour niveau 0.
3) Considérez le dictionnaire des précédents obtenus à partir de celui de G en supprimant
dans les deux colonnes tous les sommets de niveau 0 ; on obtient le dictionnaire d’un
sous graphe G1 .
4) Relevez tous sommets de G1 sans précédent : ils ont pour niveau 1.
5) Supprimez dans le dictionnaire des précédents de G1 tous les sommets de niveau 1,
etc.

Support de cours
 TRAVAUX DIRIGES SUR L’ORDONNANCEMENT
Exercice 1
La société ZEDMEN, Société immobilière gère un important parc d’immeubles.
Elle propose à ensembles immobiliers le descriptif du projet (succession des tâches à
réaliser avec leurs durées respectives) est donné dans le tableau ci-dessus :
OPERATIONS DESCRIPTIF OPERATION DUREE
PREREQUISES (JOURS)
A Zonage et plan de circulation 8
B Etude de fréquentation 5
C Appels d’offre pour commande A, B 15
D Sélection fournisseur commandes A, B, C 5
E Mise au point des logiciels C, D 35
F Réception logiciels C, D 4
G Implantation logiciels E, F, H 5
H Installations matériels D, E 48
I Marquage Zones H, F 12
J Travaux sécurité I 8
1- Ordonner les opérations par niveau
2- En utilisant la méthode des potentiels METRA (ou méthode MPM).
Représenter par un graphe, le chemin critique marquant le temps minimal
nécessaire à la réalisation du projet. Faire figurer sur ce graphe, les dates de
début et de fin au plus tôt et au plus tard de chaque tâche.
3- Indiquer, pour chaque tâche, le retard maximal qui peut être supporté dans son
exécution sans retarder la fin des travaux.

Exercice 3
La construction d’un entrepôt peut se décomposer en 10 tâches, décrites dans le
tableau ci-dessus :
OPERATIONS DESCRIPTIF OPERATIONS DUREE
PREREQUISES JOURS
A Acceptation des plans par le 4
propriétaire
B Préparation du terrain 2
C Commande des matériaux A 1
D Creusage des fondations A, B 1

Support de cours
 E Commande des portes et des fenêtres A 2
F Livraison des matériaux C, B, A 2
G Coulage des fondations D, F, C, A 2
H Livraison des portes et des fenêtres E, A 10
I Pose des murs, de la charpente, du G 4
toit
J Mise en place des portes et des H, I, A 1
fenêtres
1- rdonnancer les opérations par niveau
2- En utilisant la méthode des potentiels METRA (ou méthode MPM).
Représenter par un graphe, le chemin critique indiquant le temps minimal
nécessaire à la réalisation du projet. Faire figurer sur ce graphe les dates de
début et de fin ou plus tôt et ou plus tard de chaque tâche
3- Indiquer, pour chaque tâche, le retard maximal qui peut être supporté dans son
exécution sans retarder la fin des travaux.
Exercice 4
La mise en exploitation d’un nouveau gisement minier demande la réalisation d’un
certain nombre de tâche. Le tableau suivant représente ces différentes tâches avec leurs
relations d’antériorité
TACHES DESCRIPTION TACHES Durée en
ANTERIEURES jours
A Obtention d’un permis d’exploitation 120
B Etablissement d’une piste de 6 km A 180
C Transport et installation à pied d’œuvre B 3
D Création de bâtiments provisoires B 30
E Goudronnage de la piste B 60
F Adduction d’eau D 90
G Campagne de sondage C, D 240
H Forage et équipement de trois puits E, F, G 180
I Transport et installation du matériel J, H 30
J Construction de bureau et logement E, F, G 240
K Traçage et aménagement du fond J, H 360
L Construction d’une laverie J, H 240

1- Déterminer les dates au plus tôt et les dates au plus tard de chaque tâche
2- Déterminer le temps minimum de réalisation de l’ensemble

Support de cours
Exercice 5
Un projet de construction de bâtiment confié aux bâtisseurs de l’ENSI se résume dans le
tableau suivant : la durée des taches est en mois.

Tâches Désignation Tâches pré Durée

requises
A Acceptation des plans par le - 12
propriétaire
B Préparation du terrain - 6
C Commande des matériaux A 3
D Creusage des fondations A, B 3
E Commande des portes et fenêtres A 6
F Livraison des matériaux B, C 6
G Coulage des fondations D, F 6
H Livraison des portes et fenêtres E 30
I Pose des murs, de la charpente, du toit G 12
J Mise en place des portes et fenêtres H, I 3

1- Ordonnancer les opérations ou les tâches par niveau

2- Représenter le graphe (méthode des potentiels métra ou PERT).
3- Quel est le temps minimal nécessaire à la réalisation de ce projet de construction.
4- Préciser les tâches sur lesquelles peut-on agir sans retarder la fin des travaux.
5- Donner les marges libres et totales des tâches D, I et G.
Donner la signification des marges trouvées.
Exercice 6
Apres une année de dur labeur, Monsieur ABAYA Alex décide de consacrer ses vacances à la
découverte de la sous – région Ouest – Africaine. Ne voulant pas effectuer seul ce périple, il
décide de trouver deux compagnons qu’il espère recruter par annonce. Il planifie les
différentes tâches à exécuter pour mener à bien ce projet.
DUREE (en TÂCHES
TÂCHES jours) ANTERIEURES
A : Achat de la carte routière de la Côte d’Ivoire 1
B : Commande à l’ING des autres cartes 15
C : Etablissement du trajet à effectuer en Côte d’Ivoire 3 A
D : Etablissement du trajet dans les autres régions 15 B
E : Passage d’une petite annonce pour recruter 2 coéquipiers 21 A, B, C, D
F : choix des coéquipiers 30 E, C, D, L
G : Récupération de la tente prêtée à un copain 30 ----
H : Achat du matériel manquant 7 C, D, F, G
I : Réservation des hôtels d’étape 15 C, D, F
J : Achat des vivres pour les 3 premiers jours 1 F, G, H, I
K : Réservation des guides touristiques 1 I, J

Support de cours
L : Préparation du carnet de route 10 C

I.N.G : Institut National de Géographie.

1. Ordonnancer les taches par niveau
2 .Construire le graphe MPM associé à ce projet
2. Préciser le chemin critique, déterminer la durée total du projet, les marges totales et les
libres ainsi que leurs significations

Exercice 7

Vu le succès commercial de sa nouvelle entreprise installée à COTONOU, M. MADODE

envisage de créer une succursale à PORTO-NOVO. Pour cela il fait appel à vos services et
vous dresse la liste de toutes les tâches X qui devront être effectuées ainsi que les tâches
précédentes P X  et la durée en jours de chacune de ces tâches.
X A B C D E F G H I J K L
P X  - - A A B A, D C A, C, D B E, F, I C, G, H F, J
Durée 15 12 25 5 13 7 31 14 8 2 30 7

1- Ordonnancer les tâches par niveau.

2- Faire la représentation du graphe MPM associée à ce problème d’ordonnancement.
NB : Eviter les ponts dans la mesure du possible
3- Préciser le chemin critique et la durée minimale de réalisation du projet.

Exercice 8

Pour la construction de la route LOME-VOGAN on a fait appel à vos services et vous avez
dressé la liste de toutes les tâches qui devront être effectuées ainsi que les tâches précédentes
et la durée en mois de chacune de ces tâches.
Tâches A B C D E F G H I J K L M
Tâches précédentes - A A A A B C C D, J E E F, G H, I, K, L
Durée 4 1 6 2 7 3 4 7 3 4 8 1 2

1- Déterminer les niveaux des différentes tâches.

2- Tracer le réseau (Méthode M.P.M).
3- Préciser le chemin critique.
4- Quelle est la durée minimale de réalisation du projet ?

Support de cours