Institut Africain de Management

IAM/Ouagadougou

Année académique 2022 - 2023

Dr SOURATIE W. Minata/ Enseignante-chercheure/

Université de Dédougou
Contacts: 76 93 42 07/ 62 43 22 70
Table de matières

Introduction ............................................................................................................................................................ 2
Chapitre I. Programmation linéaire ........................................................................................................................ 3
I.1. Formulation d’un programme linéaire à deux variables ................................................................. 3
I.1.1. Identification des variables ........................................................................................................ 3
I.1.2. Objectif ........................................................................................................................................ 4
I.1.3. Les contraintes ............................................................................................................................ 4
I.2. Généralité au cas d’un programme linéaire à n variables et m contraintes................................... 5
I.2.1. Forme canonique ........................................................................................................................ 6
I.2.2. Forme standard .......................................................................................................................... 7
I.3. Résolutions ........................................................................................................................................... 8
I.3.1. La résolution graphique ............................................................................................................. 8
I.3.1.1. Représentation graphique du problème ............................................................................... 8
I.3.1.2. Interprétation et résolution graphique ................................................................................. 9
I.3.1.3. Cas dégénérés ....................................................................................................................... 11
I.4. La dualité ........................................................................................................................................... 17
I.4.1. Définition ................................................................................................................................... 17
I.4.2. Principe de construction du dual ............................................................................................ 17
I.4.3. Interprétation économique de la dualité................................................................................. 18
I.4.4. Résolution du problème dual à partir de la solution du primal ........................................... 19
I.4.4.1. Résolution graphique ........................................................................................................... 19
I.4.4.2. Résolution par le tableau du simplexe ................................................................................ 20
Travaux dirigés ..................................................................................................................................................... 21
Chapitre II : Théorie de l’ordonnancement ........................................................................................................... 23
II.1. Généralités sur les graphes ............................................................................................................... 23
II.1.1. Définitions...................................................................................................................................... 23
II.1.2. Dictionnaire des suivants et des précédents ................................................................................ 24
II.1.3. Niveaux .......................................................................................................................................... 25
II.2. Méthode MPM................................................................................................................................... 27
II.2.1. Principe de construction du graphe ........................................................................................ 27
II.2.2. Calendrier au plus tôt .............................................................................................................. 27
II.2.3. Calendrier au plus tard ............................................................................................................ 28
II.2.4. Calcul des marges ..................................................................................................................... 28
II.3. Méthode PERT .................................................................................................................................. 31
II.3.1. Principes de construction du graphe ...................................................................................... 31
II.3.2. La construction PERT ............................................................................................................. 33
II.3.3. Calendrier au plus tôt des étapes ............................................................................................ 33
II.3.4. Calendrier au plus tard des étapes .......................................................................................... 34
II.3.5. Calcul des marges totales ......................................................................................................... 36
II.4. Le diagramme de GANTT................................................................................................................ 37

1
Introduction

Tous les acteurs de la vie économique et sociale qu’il s’agisse des ménages, des entreprises ou
de l’Etat, dans le cadre de la gestion de leurs activités, sont appelés à prendre des décisions, les
meilleurs. Cela suppose qu’ils doivent opérer des choix sur un ensemble d’options possibles.
Un tel choix, au-delà du bon sens, requiert la mise en œuvre d’une démarche scientifique ou
l’usage d’outils appropriés. C’est pourquoi, pour éviter l’arbitraire dans le processus
décisionnel, la science met à la disposition de l’homme, des méthodes ou des outils d’aide à la
prise de décision. Parmi ces outils il y a la recherche opérationnelle.
La recherche opérationnelle peut se définir comme l’ensemble de méthodes et techniques
rationnelles d’analyse et de synthèse des phénomènes d’organisation utilisables pour prendre
des meilleures décisions. C’est une discipline dont le but est de fournir des méthodes pour
répondre à un type précis de problème, c’est-à-dire à élaborer une démarche universelle pour
un problème donné et aboutit à la ou les solutions les plus efficaces. La particularité de la
recherche opérationnelle est que les méthodes proposées sont des démarches rationnelles
basées sur des concepts et outils mathématiques et/ou statistiques.
La recherche opérationnelle est apparue pendant la seconde guerre mondiale en 1940 en
Angleterre puis aux Etats-Unis et était utilisée à des fins militaires. A la suite de ses succès
obtenus dans ce domaine, la recherche opérationnelle a été appliquée pendant de nombreuses
années dans l’industrie et le secteur public. Depuis plus d’une décennie, le champ d’application
de la recherche opérationnelle s’est élargi à des domaines comme l’économie, la finance, le
marketing et la planification d’entreprise. Plus récemment, elle a été utilisée pour la gestion
des systèmes de santé et d’éducation, pour la résolution des problèmes environnementaux et
dans plusieurs autres domaines d’intérêt publics.
En définitive, les domaines d’application de la recherche opérationnelle sont nombreux et très
variés. On peut retenir entre autres :
▪ La planification de la production ;
▪ Les réseaux de communication ;
▪ Les problèmes de transport ;
▪ La gestion des stocks ;
▪ La gestion prévisionnelle des emplois ;
▪ Le système concurrentiel
▪ Etc.

Les objectifs de ce cours se déclinent en quatre points :

▪ Assimiler la formulation des problèmes de RO.
▪ Maitriser les différentes techniques de résolutions.
▪ Maitriser les principes de la dualité, sa conception, sa résolution et la conversion des
solutions duales en solutions primales.
▪ Maitriser les différentes techniques d’ordonnancement en vue d’une meilleure
planification et suivi de projets.

2
Chapitre I. Programmation linéaire

La programmation linéaire est un outil très puissant de la recherche opérationnelle qui permet
la résolution algébrique d’un certain nombre de problèmes complexes. En effet, une fois qu’un
problème est modélisé sous forme d’équations linéaires, des méthodes simples existent et
assurent la résolution du problème de manière exacte.
On appelle Programmation Linéaire, le problème mathématique qui consiste à optimiser
(maximiser ou minimiser) une fonction linéaire de plusieurs variables qui sont reliées par des
relations linéaires appelées contraintes.
Une des méthodes les plus connues pour résoudre des programmes linéaires en nombre réels
est la méthode du Simplex.
I.1. Formulation d’un programme linéaire à deux variables

Le traitement d’un programme linéaire est subordonné en premier lieu à l’expression formelle
de l’objectif et des contraintes. Il convient avant tout de procéder à :
▪ L’identification des variables ;
▪ La définition de l’objectif et des contraintes.

Exemple d’application : Une entreprise fabrique deux articles A et B. Le processus de

production impose aux deux articles le passage par les ateliers usinage et assemblage.

Usinage Assemblage
Article A (en heures) 1h 2,5
Article B (en heures) 1,5h 1,5h
Capacité mensuelles (en heures) 3000h 4500h

D’autre part le service commercial vous communique les indicateurs suivants :

A B
Capacités mensuelles de vente 1600 1800
Volume de stockage (en 𝑚3 ) 1 1
Marge unitaire nette en FCFA 30 40

Le mode de distribution adopté suppose le stockage des articles produits au cours du mois et
qui ne seront livrés qu’au début du mois suivant. Le volume total disponible est de 3400𝑚3 .
Déterminer le programme mensuel de production qui permet de réaliser le résultat global
maximal.
I.1.1. Identification des variables

Le résultat global évolue en fonction du nombre d’articles A et B produits et vendus. Le

problème consiste à déterminer les nombres d’articles de A et B qui permettent de réaliser le
résultat global le plus important.
Désignons par :
▪ 𝑥1 , le nombre d’articles A à fabriquer ;

3
 ▪ 𝑥2 , le nombre d’articles B à fabriquer ;

𝑥1 et 𝑥2 sont appelés variables d’activités ou variables réelles.

I.1.2. Objectif

Au regard des variables d’activités définies, le résultat global s’obtient à partir de :

𝑹 = 𝟑𝟎𝒙𝟏 + 𝟒𝟎𝒙𝟐

L’objectif poursuivi est exprimé par la fonction économique et consiste à déterminer le couple
de valeur 𝑥1 et 𝑥2 qui maximise le résultat global R :

Max𝑹 = 𝟑𝟎𝒙𝟏 + 𝟒𝟎𝒙𝟐

I.1.3. Les contraintes

Les valeurs attribuées à 𝑥1 et 𝑥2 sont limitées par les disponibilités des facteurs concourant à
la production et la vente des articles A et B. Ces contraintes délimitent le cadre de recherche
de la solution. Il convient ainsi de prendre en considération :
▪ Les conditions de signe

Ces conditions n’apparaissent pas de façon explicite dans l’énoncé. Néanmoins leur caractère
est évident. Les valeurs de 𝑥1 et 𝑥2 ne peuvent être que positives ou nulles.

𝑥1 ≥ 0 𝑥2 ≥ 0.

▪ Les contraintes de production

Elles s’expriment en fonction du temps de travail nécessaire à l’usinage et l’assemblage d’une

unité de A et B, sachant que le total des heures allouées ne peut excéder, respectivement 3000
et 4500. Formellement, ces relations s’expriment ainsi :

- Usinage : 𝑥1 + 1,5𝑥2 ≤ 3000

- Assemblage : 2,5𝑥1 + 1,5𝑥2 ≤ 4500

▪ Les contraintes de marché

Le marché ne saurait absorber plus de 1600 unités pour A et 1800 pour B :

𝑥1 ≤ 1600 𝑥2 ≤ 1800

▪ Les contraintes de stockage

Le volume total de 3400 𝑚3 doit être affecté à raison de 1 𝑚3 pour unité de A et 1 𝑚3 pour la
même proportion de B :

𝑥1 + 𝑥2 ≤ 3400

Les contraintes étant définies, il reste à s’assurer qu’aucune d’elles n’est redondante. Une
contrainte présente cette caractéristique si elle peut être déduite des autres contraintes par
combinaison linéaire.

4
Considérons à titre d’exemple les contraintes de marché et de stockage.
𝑥1 ≤ 1600
𝑥2 ≤ 1800
𝑥1 + 𝑥2 ≤ 3400

La contrainte de stockage est une combinaison linéaire des contraintes de marché. En d’autres
termes, le respect des contraintes de marché implique nécessairement la satisfaction de la
contrainte de stockage. Dans ce cas il convient de supprimer la contrainte redondante.
Le programme linéaire défini s’écrit :

Max𝑅 = 30𝑥1 + 40𝑥2

▪ Sous les conditions : 𝑥1 ≥ 0 𝑥2 ≥ 0

▪ Sous les contraintes :
𝑥1 + 1,5𝑥2 ≤ 3000 (1)
2,5𝑥1 + 1,5𝑥2 ≤ 4500 (2)
𝑥1 ≤ 1600 (3)
𝑥2 ≤ 1800 (4)

Remarque : les contraintes sont représentées par un système d’inéquations. La forme ainsi
donnée au programme est dite canonique.
Exercices :
1. L’entreprise Thom-Gerry fabrique deux produits P1 et P2 à partir de trois matières
premières A, B, et C à raison de 3 tonnes de A, 3 tonnes de B et 7 tonnes de C par unité
de P1 fabriquée, et de 6 tonnes de A, 1 tonne de B et 6 tonnes de C par unité de P2
fabriquée.
Les disponibilités en matières premières sont limitées à 3000 tonnes de A, 1500 tonnes
de B et 4200 tonnes de C. le bénéfice net réalisé est de 30F par unité de P1 et 50 F par
unité de P2. Quel est le programme optimal maximisant le bénéfice ?

2. Une entreprise fabrique deux pièces P1 et P2 à l’aide de trois ateliers. La fabrication

d’une pièce coûte 1060F, celle d’une pièce P2 coûte 650F. chaque P1 et ou P2 est traité
successivement dans trois ateliers.
Le nombre d’heures-machine par pièce est indiqué dans le tableau suivant :
Atelier I Atelier II Atelier III
Pièce P1 3h 5H 2h
Pièce P2 1h 3h 3h

Pour éviter un chômage technique, l’atelier I doit obligatoirement fournir 1260 heures-
machine, l’atelier II 3300 heures-machine et l’atelier III 1680 heures-machine.
Combien faut-il fabriquer de pièces P1 et ou P2, d’une part pour rendre minimum les
coûts de revient de l’ensemble de la production, d’autre part pour assurer le
fonctionnement des trois ateliers excluant tout chômage technique

I.2. Généralité au cas d’un programme linéaire à n variables et m contraintes

5
Considérons un programme linéaire quelconque caractérisé par la fonction économique :

𝑅 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + … … … . +𝑐𝑗 𝑥𝑗 … … . +𝑐𝑛 𝑥𝑛

Où 𝑥𝑗 , (𝑗 = 1 … . 𝑛) représente les variables d’activité ou de décision ;

𝑐𝑗 , (𝑗 = 1 … . 𝑛) sont les coefficients économiques associés à chaque variable 𝑥𝑗 .

La valeur de ces coefficients résulte de l’objectif assigné (profit ou marge unitaire, cout
unitaire, …).
Considérons par ailleurs le système de contraintes suivantes :

𝑎11 𝑥1 + 𝑎12 𝑥2 + … … … . +𝑎1𝑗 𝑥𝑗 … … . +𝑎1𝑛 𝑥𝑛 ≤ 𝑏1

………………………………………………………
𝑎𝑖1 𝑥1 + 𝑎𝑖2 𝑥2 + … … … . +𝑎𝑖𝑗 𝑥𝑗 … … . +𝑎𝑖𝑛 𝑥𝑛 ≤ 𝑏𝑖
………………………………………………………
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + … … … . +𝑎𝑚𝑗 𝑥𝑗 … … . +𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚

Où :
▪ 𝑎𝑖𝑗 , (𝑖 = 1 … . 𝑚 et 𝑗 = 1 … . 𝑛) désignent les coefficients techniques associés à chaque
variable 𝑥𝑗 . Il s’agit de la quantité de ressources 𝑖 requise pour chaque unité de la
variable 𝑥𝑗 .
▪ 𝑏𝑖 (𝑖 = 1, … . 𝑚) est la quantité totale de ressource i disponible.

I.2.1. Forme canonique

Si l’objectif est la maximisation de la fonction économique R, le programme linéaire à 𝑛

variables et 𝑚 contraintes se présente comme suit :
𝑀𝑎𝑥𝑅 = ∑ 𝑐𝑗. 𝑥𝑗
▪ Sous les conditions : 𝑥𝑗 ≥ 0 𝑗 = 1, … … … , 𝑛
▪ Sous les contraintes : ∑ 𝑎𝑖𝑗 . 𝑥𝑗 ≤ 𝑏𝑖 𝑖 = 1, … … … , 𝑚

Remarques : La résolution d’un programme linéaire implique parfois la transformation de la

fonction économique ou celle de certaines contraintes.
▪ Si un programme de maximisation comporte une inéquation du type :
▪ 𝑎11 𝑥1 + 𝑎12 𝑥2 + … + 𝑎1𝑛 𝑥𝑛 ≥ 𝑏1

Le système d’inéquations peut être harmonisé en procédant à la transformation suivante :

−𝑎11 𝑥1 − 𝑎12 𝑥2 − … − 𝑎1𝑛 𝑥𝑛 ≤ −𝑏1

Il convient d’appliquer la transformation inverse dans le cas d’un problème de minimisation.

▪ Si l’une des contraintes s’exprime sous la forme d’une égalité de la forme :
𝑎11 𝑥1 + 𝑎12 𝑥2 + … … … . +𝑎1𝑗 𝑥𝑗 … … . +𝑎1𝑛 𝑥𝑛 = 𝑏1

Cette contrainte peut être décomposée en deux inéquations de sens inverse :

6
𝑎11 𝑥1 + 𝑎12 𝑥2 + … … … . +𝑎1𝑗 𝑥𝑗 … … . +𝑎1𝑛 𝑥𝑛 ≥ 𝑏1

𝑎11 𝑥1 + 𝑎12 𝑥2 + … … … . +𝑎1𝑗 𝑥𝑗 … … . +𝑎1𝑛 𝑥𝑛 ≤ 𝑏1

I.2.2. Forme standard

Le passage de la forme canonique à la forme standard est caractérisé par la transformation des
inéquations en équations. Cette opération s’effectue par l’introduction de nouvelles variables
notées 𝑒𝑘 et appelées variables d’écart.

Chaque contrainte est assortie d’une variable d’écart et une seule. Dans le cas d’un problème
comportant 𝑛 variables d’activités et 𝑚 contraintes, il y a 𝑚 variables d’écart et 𝑛 + 𝑚
variables au total.
Les conditions de non-négativité s’appliquent aux variables d’écart : le coefficient de la
variable d’écart dépend du sens de l’inéquation initiale :

▪ Si la contrainte est du type ≤, le coefficient de la variable d’écart introduite dans le

membre de gauche a pour valeur +1. En effet, la variable d’écart représente ce qu’il est
nécessaire d’ajouter à ce membre afin de l’égaliser à celui de droite ;

▪ Si la contrainte est du type ≥, la valeur du coefficient de la variable d’écart est -1. Il

s’agit alors du nombre à retrancher au membre de gauche pour l’égaliser à celui de
droite.

Le programme linéaire sous la forme standard se présente ainsi :

𝑛

𝑀𝑎𝑥𝑅 = ∑ 𝑐𝑗 . 𝑥𝑗
𝑗=1
▪ Sous les conditions : 𝑥𝑗 ≥ 0, 𝑗 = 1 … … … 𝑛
𝑒𝑘 ≥ 0, 𝑘 = 1 … … … 𝑚
▪ Sous les contraintes :
∑𝑛𝑗=1 𝑎𝑖𝑗 . 𝑥𝑗 + ∑ 𝑎𝑖𝑘 . 𝑒𝑘

𝑖 = 1 … 𝑚 et 𝑎𝑖𝑘 = 1: si 𝑘 = 1 et 𝑎𝑖𝑘 = 0 si 𝑘 ≠ 1

Un programme linéaire à n variables et m contraintes peut être résolu dès lors qu’il est défini
sous sa forme standard. Si n est supérieur à 2 ou m supérieur à 2, la méthode de résolution la
plus appropriée est l’algorithme du simplexe.
Exercices d’application
Exercice 1
Une entreprise fabrique des chaises et des tables à l'aide de deux machines A et B. Chaque
produit passe obligatoirement par les deux machines. Pour produire une chaise, il faut 2 heures
de machine A et 1 heure de machine B. Pour produire une table, il faut 1 heure de machine A
et 2 heures de machine B. L'entreprise réalise un bénéfice de 3F sur chaque chaise et de 4F sur
chaque table. Les deux machines A et B sont disponibles 12 heures par jour maximum.

7
1) Identifier les variables et formuler les contraintes de ce problème ?
2) Quel est l’objectif de l’entreprise ?
3) Donner l’expression de la fonction économique qui traduit l’objectif de cette entreprise.
4) Ecrire la forme canonique du programme qui modélise le problème.
5) En déduire la forme standard du programme.
Exercice 2
Une compagnie possède deux mines a charbon A et B. La mine A produit quotidiennement 1
tonne de charbon de qualité supérieure, 1 tonne de charbon de qualité moyenne et 6 tonnes de
charbon de qualité inférieure. La mine B produit par jour 2, 4 et 3 tonnes de chacune des trois
qualités. La compagnie doit produire au moins 90 tonnes de charbon de qualité supérieure, 120
tonnes de qualité moyenne et 180 tonnes de qualité inférieure.
Sachant que le coût de production journalier est le même dans chaque mine, soit 1000, écrire
la forme canonique du programme qui minimise le coût de production de la compagnie. En
déduire la forme standard du programme.

I.3. Résolutions

Il existe principalement deux méthodes de résolutions des programmes linéaires : la méthode

graphique et l’algorithme de simplexe.

I.3.1. La résolution graphique

Elle n’est applicable que lorsque le nombre de variables d’activités ne dépassent pas deux.

I.3.1.1. Représentation graphique du problème

La représentation graphique des éléments du programme s’effectue dans le cadre d’un repère
orthonormé ou les variables de 𝑥1 figurent sur l’axe des abscisses et celles de 𝑥2 sur celui des
ordonnées.
La représentation graphique des contraintes implique la transformation de la forme sous
laquelle elles sont exprimées. Le passage de la forme canonique à la forme standard s’effectue
en substituant aux signes d’inégalités ceux d’égalités. Ainsi le système des contraintes devient :

𝑥1 + 1,5𝑥2 = 3000
2,5𝑥1 + 1,5𝑥2 = 4500
𝑥1 = 1600
𝑥1 = 1800

Remarques :
▪ Chaque inéquation du système canonique représente un demi-plan fermé, limité par les
droites des équations correspondantes et représentatives du système exprimé sous sa

8
 forme standard. A la contrainte (1) est associée la droite : 𝑥1 + 1,5𝑥2 = 3000. Cette
droite scinde le plan en deux demi-plans.

▪ Un demi-plan correspond à l’ensemble des combinaisons (𝑥1 , 𝑥2 ) qui satisfont la

condition qui résulte de la contrainte.

▪ L’autre demi-plan comporte l’ensemble des combinaisons (𝑥1 , 𝑥2 ) qui ne satisfont pas
la contrainte. Les points situés sur la droite associée à (1) satisfont également la
contrainte.

▪ Si la contrainte prend la forme d’une égalité, l’ensemble des combinaisons acceptables

est une droite.

▪ Les droites associées aux conditions de signes sont confondues avec les axes.

x2

3000

2000 E D x2 = 1800
1333 C
Ro 1000 Rmax

O 1000 A 2000 3000 x1 + 1,5x2 = 3000

2,5x1 + 1,5 x2 = 4500

I.3.1.2. Interprétation et résolution graphique

Le domaine des solutions admissibles est représenté par le polygone OABCDE. Tout sommet
de ce polygone convexe constitue une solution de base. Il y a donc six solutions de base : O,
A, B, C, D, E. La solution optimale est située sur la droite 𝑅𝑚𝑎𝑥

Vérification : La fonction économique a pour expression : 𝑅 = 30𝑥1 + 40𝑥2 ce qui peut

3 𝑅 3
s’écrire : 40𝑥2 = −30𝑥1 + 𝑅 ⇒ 𝑥2 = − 𝑥1 + Pour 𝑅 = 0, 𝑥2 = − 𝑥1
4 40 4

3
La droite 𝑅0 d’équation 𝑥2 = − 𝑥1 est une droite d’isoprofit : tous les points de cette droite
4
procurent le même profit, nul dans ce cas. Il y a donc autant de droites d’isoprofit que de valeurs
de R. Ces droites sont toutes parallèles à 𝑅0 , car elles possèdent le même coefficient angulaire :
3
−
4

Plus les valeurs de 𝑅 augmentent et plus les droites d’isoprofit correspondantes s’éloignent de
l’origine tout en restant parallèles à la droite 𝑅0 . La valeur maximale de 𝑅 est atteinte au point

9
ou la droite est la plus éloignée de l’origine tout en conservant un point de contact avec le
polygone. Ce point correspond à la solution de base C qui se situe à l’intersection des droites :

𝑥1 + 1,5𝑥2 = 3000 (1)

2,5𝑥1 + 1,5𝑥2 = 4500 (2)

Les coordonnées de C sont les solutions de système

𝑥1 = 3000 − 1,5𝑥2 (3)

Transposons l’équation (3) dans (2) :

2,5(3000 − 1,5𝑥2 ) + 3000 + 1,5𝑥2 = 4500 ⇒ 𝑥2 = 1333

La valeur de 𝑥1 est obtenue en remplaçant 𝑥2 par 1333 dans l’équation (1), (2) ou (5) :
𝑥1 = 3000 − 1,5(1333) ⟹ 𝑥1 = 1000

Les coordonnées de C, solution optimale, sont donc : 𝑥1 = 1000 𝑥2 = 1333

Sous forme d’un tableau on a :

Solution de base Coordonnées Fonction

x1 x2 économique
O 0 0 R0 = 0
1600 0 RA = 48000
A
B
1600 333 RB = 61333
C 1000 1333 RC = 83320
D 300 1800 RD = 81000
0 1800 RE = 72000
E

Remarques :
▪ Les distances entre le point optimal C et les droites associées aux contraintes (1) et (2)
sont nulles. Cela signifie que si les deux variables 𝑥1 et 𝑥2 sont remplacées dans les
deux contraintes par leurs valeurs à l’optimum (1000 et 1333), alors il y a égalité entre
les membres de gauche et de droite. Entre d’autres termes, les contraintes (1) et (2) sont
dites saturées à l’optimum.

▪ A l’optimum, le coefficient directeur de la fonction économique est compris entre ceux

des droites associées aux contraintes concourantes. Ainsi, le coefficient directeur de la
droite associée à la contrainte (1) est (-1/1,5) et celui de la droite associée à la contrainte
2,5 3 1
(2) est (-2,5/1,5). Donc − <− <−
1,5 4 1,5

10
 I.3.1.3. Cas dégénérés

On note deux types de cas dits « dégénérés ».

➢ Premier type de dégénérescence

Un tel cas apparait lorsque le coefficient de pente de la droite 𝑅𝑚𝑎𝑥 , solution optimale du
problème, est égal à celui de la droite associée à l’une des contraintes.
Considérons à nouveau les données du problème précédent auxquelles est apportée une
modification, celle relative aux marges unitaires nettes des articles A et B. ces dernières
deviennent respectivement 50 F et 30 F.

La fonction économique se présente alors ainsi 𝑅 = 50𝑥1 + 30𝑥2 . Le système d’inéquations

étant le même, les droites représentatives de la nouvelle fonction économique sont parallèles à
un côté du polygone des solutions admissibles. La droite 𝑅𝑚𝑎𝑥 , est solution optimale du
problème, ne passe plus par un seul sommet (C dans le cas précédent) mais deux : C et B

x2

D
E C
B

O A R max x1

Tous les points du segment de la droite (CB) constituent l’ensemble des solutions optimales du
problème. Ce cas est dit dégénéré.

Un tel cas apparait lorsque le coefficient de pente de la droite 𝑅 est égal à celui de la droite
associée à l’une des contraintes. Le coefficient directeur de la nouvelle fonction économique
5 2,5
est : 𝑚 = − = − il correspond à celui de la droite associée à la contrainte (2) :
3 1,5

Les valeurs prises par la fonction économique en chacun des points du segment de droite [CB]
sont optimales et les mêmes ainsi, les solutions extrêmes correspondant aux sommets C et B
sont :

- En 𝐶(1000; 1333) avec 𝑅 = 90000

- En 𝐵(1600; 333) avec 𝑅 = 90000

11
 ➢ Deuxième type de dégénérescence
La dégénérescence du deuxième type apparaît lorsque par un des sommets du polygone des
solutions possibles, passe plus de deux droites. Dans de telles situations, seules interviennent
dans la résolution du problème les droites qui forment la frontière de la zone des solutions
possibles.
Exemple : On suppose les contraintes d’un problème de maximisation représentées dans la
figure 1. La zone solutions possible est alors donnée par le polygone ABC. Le point B est
l’intersection de trois droites (𝐷1 , 𝐷2 et 𝐷3 ). Pour calculer les coordonnées du point B, on considère
uniquement les droites qui forment la frontière de la zone des solutions possibles. Ainsi, dans la
détermination des coordonnées du point B, seules interviennent les droites 𝐷1 et 𝐷3 . La droite 𝐷2 ne
joue aucun rôle dans le problème.

𝑥2

A
B

C
𝐷3 𝐷2 𝐷1 𝑥1

Exercice d’application
La forme canonique associé à un problème de programmation linéaire est donnée par :
𝑀𝑎𝑥 𝑍 = 20𝑥1 + 30𝑥2
𝑥1 + 3𝑥2 ≤ 18
𝑥 + 𝑥2 ≤ 8
𝑠𝑐. { 1
2𝑥1 + 𝑥2 ≤ 14
𝑥1 ≥ 0; 𝑥2 ≥ 0
Déterminer par la méthode graphique, le programme de production optimale.

I.3.2. Résolution par l’algorithme du simplexe : Méthode des tableaux

La méthode du simplexe, proposé par G. B. Dantzig en 1947, est fondée sur un processus
itératif qui ne prend en considération que les extrêmes correspondant aux sommets de
l’ensemble des solutions admissibles.
Plus précisément, ce processus opère à partir d’une solution de base qui sera soumise à un test
afin de déterminer s’il s’agit ou non de la solution optimale. Si tel est le cas, ce processus prend

12
fin. Si la solution de base considérée n’est pas optimale, le test est alors appliqué à une nouvelle
solution de base.

Tableau initial

Oui
Solution Stop
optimale

Non

Choix de la variable entrante

Pivotage

Choix de la variable sortante

Exemple d’application :
A l’approche des fêtes de fin d’année, la pâtisserie BELFORT décide de confectionner des
gâteaux et des chocolats. En allant inspecter ses réserves, le gérant de la pâtisserie constate
qu’il lui reste 18 kg de cacao, 8 kg de noisette et 14kg de lait.
La pâtisserie propose deux spécialités : gâteau cérémonial et gâteau maison. Un gâteau
cérémonial nécessite 1kg de cacao, 1kg de noisette et 2 kg de lait. Un gâteau maison nécessite
3kg de cacao, 1kg de noisette et 1kg de lait.
Elle réalisera un profit de 20FCFA en vendant un gâteau cérémonial et de 30FCFA en vendant
un gâteau maison. Déterminer par la méthode de simplexe, le programme de production
optimale.
Solution

- Le programme canonique associé à ce problème est le suivant :

𝑀𝑎𝑥 𝑍 = 20𝑥1 + 30𝑥2
𝑥1 + 3𝑥2 ≤ 18
𝑥 + 𝑥2 ≤ 8
𝑠𝑐. { 1
2𝑥1 + 𝑥2 ≤ 14
𝑥1 ≥ 0; 𝑥2 ≥ 0

13
Pour résoudre ce problème, on suit la démarche suivante :

- Forme standard
Le programme canonique est écrit sous forme standard en introduisant trois variables d’écart
non négatives 𝑒1 , 𝑒2 et 𝑒3 , respectivement au niveau de la prémière, deuxième et troisième
contrainte. On obtient ainsi le programme standard suivant :

𝑀𝑎𝑥 𝑍 = 20𝑥1 + 30𝑥2 + 0𝑒1 + 0𝑒2 + 0𝑒3

𝑥1 + 3𝑥2 + 𝑒1 = 18
𝑥1 + 𝑥2 + 𝑒2 = 8
𝑠𝑐. {
2𝑥1 + 𝑥2 + 𝑒3 = 14
𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑒1 ≥ 0; 𝑒2 ≥ 0; 𝑒3 ≥ 0

- Recherche d’une solution de base de départ

Généralement on considère le point (le sommet) 0 comme solution de départ, car c’est plus
facile.

Au sommet 0 (𝑥1 = 0; 𝑥2 = 0) on admet que rien n’est produit. Z est donc nulle.

Si 𝑥1 = 0; 𝑥2 = 0, on obtient 𝑒1 = 18, 𝑒2 = 8 et 𝑒3 = 14 et donc Z = 0.

Au sommet 0 :

✓ Les variables non nulles 𝑒1 , 𝑒2 et 𝑒3 sont appelées variables de base (VB) ;

✓ Les variables nulles 𝑥1 𝑒𝑡 𝑥2 sont appelées variables hors base.
Cette solution de départ correspond à la situation où aucune production n’est engagée. Il
convient de modifier la solution de base afin d’améliorer la fonction économique. Dans cet
exemple, l’objectif étant la recherche d’un maximum, la fonction économique doit augmenter.
L’intérêt majeur de la méthode est de mettre en évidence les principes du calcul algorithmique.
La représentation de ces calculs sous formes de tableaux permet avant tout une économie de
calculs et d’écritures. Le recours à cette méthode suppose une maitrise parfaite de la règle de
pivotage.

Le programme standard initial se présente ainsi (𝑠0′ ) :

𝑀𝑎𝑥 𝑍 = 20𝑥1 + 30𝑥2 + 0𝑒1 + 0𝑒2 + 0𝑒3

𝑥1 + 3𝑥2 + 𝑒1 = 18
𝑥1 + 𝑥2 + 𝑒2 = 8
𝑠𝑐. {
2𝑥1 + 𝑥2 + 𝑒3 = 14
𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑒1 ≥ 0; 𝑒2 ≥ 0; 𝑒3 ≥ 0
Après avoir mis le programme sous forme standard, on peut établir le tableau initial du
simplexe (𝑇0 ).

14
Tableau 0

𝐶𝑗 20 30 0 0 0
VB 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 𝑏𝑖 𝑅𝑇
0 𝑒1 1 3 1 0 0 18 6
0 𝑒2 1 1 0 1 0 8 8
0 𝑒3 2 1 0 0 1 14 14
𝑍𝑗 0 0 0 0 0 0
𝐶𝑗 − 𝑍𝑗 20 30 0 0 0

La partie centrale du tableau donne la matrice des coefficients techniques (coefficients des
contraintes). La colonne 𝑏𝑖 représente celle des seconds membres, elle indique les valeurs
attribuées aux variables situées dans la base. La ligne 𝑍𝑗 donne les coefficients des variables
de base multiplier par les coefficients des contraintes (𝑎𝑖 ). La solution de départ est 0. En
d’autres termes Z = 0.

- Première itération

✓ Sélection de la variable entrante

Selon le critère de Dantzig, on sélectionne la variable affectée du plus grand coefficient positif
( 𝐶𝑗 − 𝑍𝑗 ). Il s’agit ici de 30 : 𝑥2 entre dans la base.

✓ Sélection de la variable sortante

On adjoint une colonne supplémentaire 𝑅𝑇 appelée ratio test représentant le rapport entre les
valeurs respectives du second membre 𝑏𝑖 et les coefficients de la colonne de variable entrante.
On retient le plus petit rapport positif : 𝑒1 sort de la base, car le plus petit rapport positif est 6.

L’intersection de la colonne (variable entrante) et de la ligne (variable sortante) s’appelle le

pivot : c’est le coefficient de la variable entrante dans l’équation qui servira de base aux
calculs : ici le pivot est 3.
Pour passer au tableau suivant et donc effectuer la première itération, il est essentiel d’utiliser
le pivot.
Le pivotage s’effectue de la manière suivante :
On commence par diviser la ligne du pivot par le chiffre du pivot.
Dans notre exemple, on divise par 3.
Nous devons calculer les nouvelles valeurs pour les lignes restantes à partir du tableau
précédent (tableau initial pour la première itération).
𝑃𝑟𝑜𝑗𝑒𝑐𝑡𝑖𝑜𝑛 𝑠𝑢𝑟 𝑙𝑎 𝑙𝑖𝑔𝑛𝑒 ∗ 𝑃𝑟𝑜𝑗𝑒𝑐𝑡𝑖𝑜𝑛 𝑠𝑢𝑟 𝑙𝑎 𝑐𝑜𝑙𝑜𝑛𝑛𝑒
𝑁𝑜𝑢𝑣𝑒𝑙𝑙𝑒 𝑣𝑎𝑙𝑒𝑢𝑟 = 𝐴𝑛𝑐𝑖𝑒𝑛𝑛𝑒 𝑣𝑎𝑙𝑒𝑢𝑟 −
𝑝𝑖𝑣𝑜𝑡

15
Tableau 1

𝐶𝑗 20 30 0 0 0
VB 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 𝑏𝑖 𝑅𝑇
30 𝑥2 1/3 1 1/3 0 0 6 18
0 𝑒2 2/3 0 -1/3 1 0 2 3
0 𝑒3 5/3 0 -1/3 0 1 8 24/5
𝑍𝑗 10 30 10 0 0 180
𝐶𝑗 − 𝑍𝑗 10 0 -10 0 0

Le critère d’arrêt
Nous arrêtons lorsque nous obtenons le critère d'optimalité. L'algorithme du simplexe s'arrête
lorsque : les coefficients 𝐶𝑗 − 𝑍𝑗 ≤ 0.

Dans notre exemple, les coefficients de la ligne 𝐶𝑗 − 𝑍𝑗 ne sont pas tous négatifs ou nuls, la
solution donnée par ce tableau n’est pas optimale. Elle peut être améliorée, d’où la deuxième
itération.

- Deuxième itération

✓ Variable entrante : 𝒙𝟏
✓ Variable sortante : 𝒆𝟐
✓ Pivot : 2/3
La deuxième itération s’effectue de la même façon que la première (on utilise cette fois-ci le
tableau de la première itération).

D’où le tableau 2 :

𝐶𝑗 20 30 0 0 0

VB 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 𝑏𝑖

30 𝑥2 0 1 1/2 -1/2 0 5

20 𝑥1 1 0 -1/2 3/2 0 3

0 𝑒3 0 0 1/2 -5/2 1 3

𝑍𝑗 20 30 5 15 0 210

𝐶𝑗 − 𝑍𝑗 0 0 -5 -15 0

16
Tous les coefficients de la ligne 𝐶𝑗 − 𝑍𝑗 sont négatifs ou nuls. L’algorithme s’arrête. On a donc
atteint la solution optimale.

Cette solution optimale est donc : 𝑥1∗ = 3; 𝑥2∗ = 5; 𝑒3∗ = 3; 𝑒1∗ = 0; 𝑒2∗ = 0

D’où le programme optimal de fabrication : 𝑥1∗ = 3 (3 𝑔â𝑡𝑒𝑎𝑢𝑥 𝑐é𝑟é𝑚𝑜𝑛𝑖𝑎𝑙) ;

𝑥2∗ = 5 (5 𝑔â𝑡𝑒𝑎𝑢𝑥 𝑚𝑎𝑖𝑠𝑜𝑛). 𝑍 ∗ = 210 (le profit total réalisé est de 210 francs.)

La variable d’écart 𝑒3∗ = 3 signifie que 3 kg de lait n’ont pas été utilisés ou sont encore
disponibles.

Les variables d’écart 𝑒1∗ = 0; 𝑒2∗ = 0 signifient que toutes les quantités disponibles de cacao et
de noisette ont été utilisées.

I.4. La dualité

La notion de dualité est à l’origine de nombreux développements théoriques dans l’étude de la

programmation linéaire. Le recours à cette notion permet une simplification notable des
problèmes. Ainsi, à un programme de minimisation est substitué celui, plus commode, de
maximisation et vice versa.
I.4.1. Définition

Considérons le problème de maximisation suivant :

𝑀𝑎𝑥𝑅 = ∑ 𝑐𝑗 𝑥𝑗

▪ Sous les conditions : 𝑥𝑗 ≥ 0 𝑗 = 1, … … … , 𝑛

▪ Sous les contraintes : ∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 𝑖 = 1, … … . . , 𝑚
Ce programme est dit initial ou primal. Le programme complémentaire, ou dual, qui comporte
les variables 𝑦𝑖 est tel que :

𝑀𝑖𝑛𝐶 = ∑𝑚
𝑖=1 𝑏𝑖 𝑦𝑖

Sous les conditions : 𝑦𝑖 ≥ 0 𝑖 = 1, … … . . , 𝑚

Sous les contraintes : ∑𝑚

𝑖=1 𝑎𝑗𝑖 𝑦𝑖 ≥ 𝑐𝑗 𝑗 = 1, … … , 𝑛

Ce programme conduit à la même solution que celle obtenue à partir du primal :

MaxR = MinC

I.4.2. Principe de construction du dual

La construction de tout dual associé à un primal est fondée sur le respect des relations
suivantes :
▪ Le sens des inégalités dans le dual est l’inverse de celui des inégalités du primal,
exception faite des conditions de signe.

17
Primal Dual
n

 aij .x j  bi
m

j =1
a
i =1
ji . yi  c j

i = 1,....., m  j = 1,......, n

Et : 𝑥𝑗 ≥ 0 ⟹ 𝑦𝑖 ≥ 0

▪ Le dual associe une variable à chacune des m contraintes du primal : 𝑦𝑖 (𝑖 =

1, … , 𝑚)

▪ Le dual comporte autant de contraintes qu’il y a de variables dans le programme initial.

Aux n variables du primal correspond n contraintes du dual.

▪ Les colonnes de coefficients des contraintes du primal deviennent les lignes de

coefficients des contraintes du dual et inversement. La traduction formelle de cette
transformation est l’inverse des indices des coefficients a :

Primal Dual
a ij  a ji

▪ Les coefficients de la fonction économique du primal deviennent les seconds membres

des contraintes du dual et inversement.
n
Pri mal : MaxR =  c j .x j
j =1
m
Dual :  a ji . yi  c j
i =1

Exemple : Considérons l’exemple précédant sur la pâtisserie BELFORT.

Programme Primal Programme Dual

𝑀𝑎𝑥 𝑍 = 20𝑥1 + 30𝑥2 𝑀𝑖𝑛 𝑊 = 18𝑦1 + 8𝑦2 + 14𝑦3

𝑥1 + 3𝑥2 ≤ 18 𝑦1 + 𝑦2 + 2𝑦3 ≥ 20
𝑥 + 𝑥2 ≤ 8 𝑠𝑐. { 3𝑦1 + 𝑦2 + 𝑦3 ≥ 30
𝑠𝑐. { 1
2𝑥1 + 𝑥2 ≤ 14 𝑦1 ≥ 0; 𝑦2 ≥ 0; 𝑦3 ≥ 0
𝑥1 ≥ 0; 𝑥2 ≥ 0

I.4.3. Interprétation économique de la dualité

Si l’on suppose qu’une autre pâtisserie PYRAMIDE, par exemple, propose à la pâtisserie
BELFORT de lui racheter ces quantités de matière première cacao, noisette et lait aux prix
respectifs de 𝑦1 F, 𝑦2 F et 𝑦3 F le Kg.

La pâtisserie PYRAMIDE cherche à minimiser le coût total d’acquisition de ces matières

premières à savoir : 𝑊 = 18𝑦1 + 8𝑦2 + 14𝑦3

18
La pâtisserie BELFORT ne pourra accepter que si les prix proposés lui procurent un résultat
au moins égal à ce que lui rapporte la fabrication d’un gâteau cérémonial et d’un gâteau
maison : 𝑦1 + 𝑦2 + 2𝑦3 ≥ 20 , 3𝑦1 + 𝑦2 + 𝑦3 ≥ 30

Cette situation se ramène à la recherche d’un programme appelé programme dual qui se
présente ainsi :
𝑀𝑖𝑛 𝑊 = 18𝑦1 + 8𝑦2 + 14𝑦3
𝑦1 + 𝑦2 + 2𝑦3 ≥ 20
𝑠𝑐. { 3𝑦1 + 𝑦2 + 𝑦3 ≥ 30
𝑦1 ≥ 0; 𝑦2 ≥ 0; 𝑦3 ≥ 0
I.4.4. Résolution du problème dual à partir de la solution du primal
I.4.4.1. Résolution graphique

Considérons le programme dual précédent :

𝑀𝑖𝑛 𝑊 = 18𝑦1 + 8𝑦2 + 14𝑦3
𝑦1 + 𝑦2 + 2𝑦3 ≥ 20
𝑠𝑐. { 3𝑦1 + 𝑦2 + 𝑦3 ≥ 30
𝑦1 ≥ 0; 𝑦2 ≥ 0; 𝑦3 ≥ 0

Résoudre ce programme consiste à déterminer les valeurs de 𝑦1 , 𝑦2 et 𝑦3 . Pour y parvenir, nous

partirons de la solution optimale du primal : 𝑥1∗ = 3; 𝑥2∗ = 5.

En remplaçant ces variables par leurs valeurs dans les contraintes du primal, on obtient :

3 + 3 × 5 ≤ 18 (1) 18 = 18 (1)
{3 + 5 ≤ 8 (2) {8 = 8 (2)
2 × 3 + 5 ≤ 14 (3) 11 ≤ 14 (3)

On constate que les contraintes (1) et (2) du primal sont saturées (les matières premières cacao
et noisette sont pleinement utilisées), alors que la contrainte (3) ne l’est pas (il reste encore 3kg
de lait).
Au niveau du dual, la variable du dual associée à la contrainte non saturée du primal est nulle,
c’est-à-dire 𝑦3 =0. Le programme dual devient :
𝑀𝑖𝑛 𝑊 = 18𝑦1 + 8𝑦2
𝑦1 + 𝑦2 ≥ 20
𝑠𝑐. { 1 + 𝑦2 ≥ 30
3𝑦
𝑦1 ≥ 0; 𝑦2 ≥ 0
Les contraintes du dual associées aux variables non nulles du primal étant saturées, pour
déterminer les valeurs de 𝑦1 𝑒𝑡 𝑦2 , il suffit tout simplement de résoudre le système d’équation
suivant :
𝑦 + 𝑦2 = 20
{ 1
3𝑦1 + 𝑦2 = 30

On obtient la solution suivante : 𝑦1 = 5 , 𝑦2 =15, 𝑦3 = 0

𝑊 = 18 × 5 + 8 × 15 + 14 × 0 = 90 + 120 + 0 = 210
𝑊 = 𝑍 = 210

19
 I.4.4.2. Résolution par le tableau du simplexe

Le dernier tableau du simplexe donne non seulement la solution optimale du primal mais aussi
celle du dual. Pour déduire la solution optimale du dual, il suffit de lire sur la ligne Z. Les
coefficients des variables d’écart ou les taux marginaux de substitution de ces variables
représentent en fait les valeurs des variables du dual à l’optimum.

• Correspondance variables du primal et variables du dual

Le dual et primal mis sous forme standard ont exactement le même nombre de variables. Les
variables d’écart du primal sont en correspondance avec les variables principales du dual.
𝑒1 ↔ 𝑦1 ; 𝑒2 ↔ 𝑦2 ; 𝑒3 ↔ 𝑦3

Les variables principales (d’activités) du primal sont en correspondance avec les variables
d’écart du dual. 𝑥1 ↔ 𝑢1 ; 𝑥2 ↔ 𝑢2

𝑀𝑎𝑥 𝑍 = 20𝑥1 + 30𝑥2 𝑀𝑖𝑛 𝑊 = 18𝑦1 + 8𝑦2 + 14𝑦3

𝑥1 + 3𝑥2 + 𝑒1 = 18
𝑦1 + 𝑦2 + 2𝑦3 − 𝑢1 = 20
𝑥1 + 𝑥2 + 𝑒2 = 8
{ { 3𝑦1 + 𝑦2 + 𝑦3 − 𝑢2 = 30
2𝑥1 + 𝑥2 + 𝑒3 = 14
𝑦1 ≥ 0; 𝑦2 ≥ 0; 𝑦3 ≥ 0; 𝑢1 ≥ 0; 𝑢2 ≥ 0
𝑥1 ≥ 0; 𝑥2 ≥ 0; 𝑒1 ≥ 0; 𝑒2 ≥ 0; 𝑒3 ≥ 0

• Les variables de base du dual

Les variables hors base du primal sont en correspondance avec les variables de base du dual.
Or, les variables hors base du primal sont 𝑒1 et 𝑒2 . Elles sont en correspondance respectivement
avec les variables du dual 𝑦1 et 𝑦2 . Les variables de base du dual sont donc 𝑦1 et 𝑦2 .

A l’optimum, une variable de base du dual prend comme valeur le coefficient, sur la ligne Z
du tableau optimal du primal, de la variable avec laquelle elle est en correspondance dans le
primal.

𝐶𝑗 20 30 0 0 0

VB 𝑥1 𝑥2 𝑒1 𝑒2 𝑒3 𝑏𝑖

30 𝑥2 0 1 1/2 -1/2 0 5

20 𝑥1 1 0 -1/2 3/2 0 3

0 𝑒3 0 0 1/2 -5/2 1 3

𝑍𝑗 20 30 5 15 0 210

𝐶𝑗 − 𝑍𝑗 0 0 -5 -15 0

𝑦1 ↔ 𝑒1 ⟹ 𝑦1 = 5
𝑦2 ↔ 𝑒2 ⟹ 𝑦2 = 15
𝑦3 ↔ 𝑒3 ⟹ 𝑦3 = 0, 𝑒3 étant une variable de base du primal, son correspondant dual 𝑦3 est nul.
La valeur de 𝑊 à l’optimum est donc : 𝑊 = 18 × 5 + 8 × 15 + 14 × 0 = 210

20
 Travaux dirigés

Exercice 1
Quality shoes (Qs) est une société implantée à Ouagadougou, spécialisée dans la confection
des chaussures de luxe en cuirs pour homme. Au regard de la tendance actuelle, elle vient de
mettre au point deux modèles de chaussures : la « pointini » et le « mocasin ». Compte tenu
des contraintes de main-d’œuvre, de machine et de marché, le directeur de Qs veut prévoir un
plan de production en lui permettant de maximiser son profit. La vente d’une « pointini » laisse
une marge bénéficiaire de 60 euros, celle d’un « mocasin » de 40 euros.
La confection d’une « pointini » demande 10 heures de main-d’œuvre directe et 8 heures de
machine, celle d’un « mocasin » nécessite 4 heures de main-d’œuvre directe et 2 heures de
machine.
L’entreprise dispose pour l’année, de 12000 heures de main-d’œuvre directe et de 8000 heures
de machine.
Une étude de marché indique que les possibilités de vente au niveau domestique pour l’année
s’élèvent à 900 pointinis et à 1500 mocasins.
1) Après avoir correctement défini les variables, formuler les contraintes de ce problème.
2) Quel est l’objectif de Qs ?
3) Donner l’expression de la fonction économique qui traduit l’objectif de la société Qs.
4) En déduire la forme canonique du programme qui modélise le problème.
5) Déterminer le plan de production permettant à Qs d’atteindre son objectif (résolution
graphique).
6) Interpréter les résultats, en précisant les facteurs pleinement utilisés et sous employés.
7) Ecrire le programme dual associé et donner sa solution optimale.

Exercice 2
Une entreprise fabrique les produits A et B. la fabrication de ces produits nécessite un passage
dans 3 ateliers pour lesquels on dispose des renseignements suivants :

Atelier T Atelier F Atelier M

Nombre d’heures Pour la fabrication d’un produit A 3 3 8
nécessaires Pour la fabrication d’un produit B 2 7 6
Coût d’une heure de travail dans l’atelier 40 45 60

Les capacités de chaque atelier sont limitées à :

• 400 heures pour T

• 1000 heures pour F
• 1100 heures pour M
On signale que les produits A et B sont vendus respectivement 935 F et 920 F l’unité.

21
 1. En utilisant la méthode du simplexe, déterminer les quantités de produits A et B que
l’entreprise a intérêt à fabriquer si elle veut maximiser son profit.
2. Préciser dans quel atelier l’on peut faire de sous-traitance. Justifier la réponse.
Exercice 3
Un comité d’entreprise organise un repas pour 150 personnes. Il prévoit pour chaque personne
3 assiettes en carton, 2 verres et 4 serviettes en papiers. Le fournisseur de l’entreprise propose
deux lots : un lot de type 1 comprenant 50 assiettes, 50 verres et 50 serviettes au prix 50 euros
et un lot de type 2 comprenant 30 assiettes, 25 verres et 60 serviettes au prix 40 euros. Le
comité veut déterminer combien il doit acheter de lots de chaque type pour minimiser la
dépense globale.
1) Ecrire la forme canonique du programme (P) qui traduit cet objectif.
2) Déterminer le programme dual (D) du programme (P).
3) Résoudre le programme dual par la méthode du simplexe.
4) En déduire la solution optimale du programme primal (P).
5) Interpréter les résultats du primal.

22
Chapitre II : Théorie de l’ordonnancement

Dans la vie courante, les agents économiques sont confrontés à des problèmes
d’ordonnancement dès lors qu'il est nécessaire d'organiser et/ou de repartir le travail entre
plusieurs entités.
Au départ, les problèmes d’ordonnancement ont été appréhendés dans la planification des
grands projets ou la réalisation des grands ensembles complexes qui nécessitent une multitude
d’opérations ou de tâches, soumises à de nombreuses contraintes, et qui mettent en jeu des
capitaux, de matériaux et des matériels variés, des hommes de spécialités et de compétences
très différentes.
Le but de l’ordonnancement est d’ordonner dans le temps un ensemble d’opérations ou tâches
contribuant à la réalisation d’un même projet. Le déroulement de ces opérations doit respecter
un ensemble de contraintes qui peuvent être :

- des contraintes de temps : certains délais sont à respecter lors de l’exécution des tâches.
- des contraintes de non simultanéité : certaines tâches ne peuvent être réalisées en
même temps.
- des contraintes de production : qui sont liées à la disponibilité des facteurs de
production.
- des contraintes de succession : certaines tâches ne peuvent être exécutées avant
d’autres.
L'objectif est de minimiser la durée de réalisation du projet compte tenu des contraintes
d'antériorité reliant les différentes tâches. De plus, on détermine les calendriers de réalisation
de chacune de ces tâches ainsi que les marges de manœuvre associées.
Deux méthodes sont classiquement utilisées dans les problèmes d’ordonnancement : la
Méthode des Potentiels Metra (MPM), et la méthode PERT (Program Evaluation and
Research Task). Toutes les deux utilisent les graphes pour résoudre le problème.
Les graphes constituent ainsi, une manière commode de présenter un problème
d’ordonnancement car ils donnent une représentation aisément manipulable des relations qui
peuvent exister lors de l’analyse du phénomène.

II.1.Généralités sur les graphes

II.1.1. Définitions

Un graphe est un ensemble de nœuds ou sommets qui sont reliés entre eux par des arcs.
Mathématiquement, un graphe est représenté par un couple de deux ensembles 𝐺 = (𝑋; 𝑈) où
𝑋 est l’ensemble des nœuds et 𝑈 l’ensemble des arcs.

Un arc relie deux nœuds entre eux, il sera donc représenté par un couple (𝑥; 𝑦) où 𝑥 et 𝑦 sont
des nœuds. Un arc peut être orienté, c’est-à-dire que l’ordre de 𝑥 et de 𝑦 est important dans le
couple (𝑥; 𝑦). Un arc peut ne pas être orienté et dans ce cas, l’ordre de 𝑥 et de 𝑦 dans le couple
(𝑥; 𝑦) n’a aucune importante, donc (𝑥; 𝑦) = (𝑦; 𝑥). Les arcs sont représentés de la manière
suivante :

23
 - Arc orienté : X
y

X y
- Arc non orienté :

Un graphe orienté 𝐺 est un couple (𝑋, 𝑈) où 𝑋 est un ensemble de sommets {𝑥1 , . . . , 𝑥𝑛 } et 𝑈

un ensemble de couples orientés (𝑥𝑖 , 𝑥𝑗 ) appelés arcs.

Pour un arc (𝑥𝑖 , 𝑥𝑗 ) d'origine 𝑥𝑖 et d'extrémité 𝑥𝑗 , 𝑥𝑖 est un précédent de 𝑥𝑗 , et 𝑥𝑗 est un suivant

de 𝑥𝑖 .

Si l’origine d’un arc est l’extrémité d’un autre, ils sont adjacents

Un chemin est une suite ordonnée (𝑥1 , . . . , 𝑥𝑛 ) de sommets reliés par des arcs. La longueur du
chemin est le nombre d'arcs qu'il contient.

Un circuit est un chemin (𝑥1 , . . . , 𝑥𝑛 ) tel que 𝑥1 = 𝑥𝑛 .

II.1.2. Dictionnaire des suivants et des précédents

On définit l’application Γ: 𝑋 → 𝑋 qui à chaque sommet 𝑋 du graphe associe l’ensemble Γ(𝑋)

des sommets accessibles par un arc à partir de celui-ci. On peut alors représenter le graphe en
associant à chaque sommet, la liste de ses suivants : G(𝑋, Γ)

On définit le dictionnaire des précédents qui à chaque sommet associe la liste de ses ‘‘pères’’
Γ −1 (𝑋), (c’est-à-dire les sommets depuis lesquels on peut arriver par un arc).
Outre une représentation graphique sagittale, un graphe peut être représenté par un tableau,
appelé dictionnaire, qui à chaque sommet énumère les suivants et les précédents :

𝑋2
t
𝑋4
t 𝑋6
𝑋1
t t Précédents Suivants
𝑋3 𝑋5 P(x) S(x)
t t

𝑋1 - 𝑋2 ,𝑋3
𝑋2 𝑋1 ,𝑋3 𝑋4
𝑋3 𝑋1 𝑋2 ,𝑋4
𝑋4 𝑋2 ,𝑋3 𝑋5 ,𝑋6
𝑋5 𝑋4 𝑋6
𝑋6 𝑋4 ,𝑋5 -

24
 II.1.3. Niveaux

Dans un graphe sans circuit, le niveau d'un sommet 𝑥 est la longueur du plus long chemin
d'extrémité 𝑥 (le nombre de sommets). La détermination des niveaux se fait à partir du
dictionnaire des précédents :

Sommets X Précédents P(x)

𝑋1 -
𝑋2 𝑋1 ,𝑋3
𝑁0 = {𝑠𝑜𝑚𝑚𝑒𝑡 𝑑𝑒 𝑛𝑖𝑣𝑒𝑎𝑢 0}
𝑋3 𝑋1 = {𝑠𝑜𝑚𝑚𝑒𝑡𝑠 𝑛′𝑎𝑦𝑎𝑛𝑡 𝑝𝑎𝑠 𝑑𝑒 𝑝𝑟é𝑐é𝑑𝑒𝑛𝑡} = {𝑋1 }
𝑋4 𝑋2 ,𝑋3
𝑋5 𝑋4
𝑋6 𝑋4 ,𝑋5

Les autres niveaux s’obtiennent en supprimant les sommets des niveaux précédents.
Pour le niveau 1, tous les sommets X1 sont barrés d'où le tableau ci-dessous
Sommets X Précédents P(x)
𝑋1 - 𝑁1 = {𝑠𝑜𝑚𝑚𝑒𝑡 𝑑𝑒 𝑛𝑖𝑣𝑒𝑎𝑢 1}
𝑋2 𝑋1 ,𝑋3
= {𝑠𝑜𝑚𝑚𝑒𝑡𝑠 𝑛′𝑎𝑦𝑎𝑛𝑡 𝑝𝑎𝑠 𝑑𝑒 𝑝𝑟é𝑐é𝑑𝑒𝑛𝑡} = {𝑋3 }
𝑋3 𝑋1
𝑋4 𝑋2 ,𝑋3 Les sommets barrés sont considérés comme n'existant plus.
𝑋5 𝑋4
𝑋6 𝑋4 ,𝑋5

Pour obtenir le niveau 2, il suffit de supprimer le sommet X3 du tableau précédent.

Sommets X Précédents P(x)
𝑋1 -
𝑋2 𝑋1 ,𝑋3 𝑁2 = {𝑋2 }
𝑋3 𝑋1
𝑋4 𝑋2 ,𝑋3
𝑋5 𝑋4
𝑋6 𝑋4 ,𝑋5

25
 Pour obtenir le niveau 3, il suffit de supprimer le sommet X2 du tableau précédent. On obtient :

Sommets X Précédents P(x)

𝑋1 -
𝑋2 𝑋1 ,𝑋3 𝑁3 = {𝑋4 }
𝑋3 𝑋1
𝑋4 𝑋2 ,𝑋3
𝑋5 𝑋4
𝑋6 𝑋4 ,𝑋5

Pour obtenir le niveau 4, il suffit de supprimer le sommet X4 du tableau précédent.

On obtient :
Sommets X Précédents P(x)
𝑋1 -
𝑋2 𝑋1 ,𝑋3 𝑁4 = {𝑋5 }
𝑋3 𝑋1
𝑋4 𝑋2 ,𝑋3
𝑋5 𝑋4
𝑋6 𝑋4 ,𝑋5

Pour obtenir le niveau 5, il suffit de supprimer le sommet X5 du tableau précédent.

On obtient :
Sommets X Précédents P(x)
𝑋1 -
𝑋2 𝑋1 ,𝑋3 𝑁5 = {𝑋6 }
𝑋3 𝑋1
𝑋4 𝑋2 ,𝑋3
𝑋5 𝑋4
𝑋6 𝑋4 ,𝑋5
Les niveaux sont alors :

𝑁0 = {X1 }
𝑋3 𝑋4 𝑋5
𝑋1 𝑁1 = {X 3 }
t t t
t
𝑁2 = {X 2 }

1X 1X 𝑋6 𝑁3 = {X 4 }
1X 1X 𝑋2 t
t 𝑁4 = {X 5 }
𝑁5 = {X 6 } 26
𝑁0 𝑁1 𝑁2 𝑁3 𝑁4 1X
𝑁5
1X
Exercice d’application : Soit le graphe ci-dessous :

- Déterminer le dictionnaire des suivants du graphe ;

- Déterminer les différents niveaux du graphe ;
- Représenter le graphe ordonnancé

II.2.Méthode MPM

II.2.1. Principe de construction du graphe

La construction du graphe MPM se fait en appliquant les principes suivants :

− Un sommet correspond à une tâche

− Un arc définit une relation d'antériorité
− La valeur de l'arc définit le temps minimum séparant deux tâches successives.
− Chaque sommet de la représentation graphique est figuré par un rectangle

𝑇𝑋 𝑇 ∗𝑋
𝑋
Où 𝑋=nom de la tâche
𝑇𝑋 = date de début au plus tôt de la tâche
𝑇 ∗𝑋 = date de début au plus tard de la tâche

− Un sommet terminal permettant de dater la fin des travaux est rajouté au graphe.
− La représentation graphique est ordonnée par niveaux des sommets, c.à.d. des tâches.

II.2.2. Calendrier au plus tôt

Une tâche 𝑋 ne pouvant débuter que lorsque toutes les tâches qui y aboutissent sont
terminées, 𝑇 𝑥 correspond à la valeur du chemin de valeur maximale aboutissant à 𝑋. Ceci
sera obtenu après avoir ordonné le graphe par niveaux des tâches.

T x = max [T y + V(y, x)] , le max étant pris sur les précédents 𝑦 de 𝑥.

27
 II.2.3. Calendrier au plus tard

Il s'agit de la date au plus tard à laquelle peut commencer une tâche sans remettre en cause la
date de fin des travaux. Ceci sera obtenu en commençant par les sommets de niveau les plus
élevés jusqu'aux sommets de niveau les plus faibles.

𝑇 ∗𝑋 = 𝑇𝑋 pour le sommet terminal

𝑇 ∗𝑋 = 𝑚𝑖𝑛 [𝑇 ∗ 𝑌 − 𝑉(𝑥, 𝑦)] , le min étant pris sur les suivants y de x.

Remarque : sur les tâches critiques, 𝑇 ∗𝑋 = 𝑇𝑋

II.2.4. Calcul des marges

Marges totales
C'est le retard maximum que l'on peut prendre dans la mise en route d'une tâche sans remettre
en cause les dates au plus tard des tâches suivantes (donc sans retarder la fin des travaux).

𝑚𝑇(𝑥) = 𝑇 ∗𝑋 − 𝑇𝑋

Marges libres
C'est le retard maximum que l'on peut prendre dans la mise en route d'une tâche sans remettre
en cause les dates au plus tôt des tâches suivantes (donc sans retarder la fin des travaux).

𝑚𝐿(𝑥) = 𝑚𝑖𝑛 [𝑇𝑦 − 𝑇𝑋 − 𝑉(𝑥, 𝑦)] , le min étant pris sur les suivants 𝑦 de 𝑥.

Exemple d’application
Les opérations de mise en jeu dans la construction d’un ensemble hydroélectrique sont les
suivantes :
A : construction des voies d’accès
B : travaux de terrassement
C : construction des bâtiments administratifs
D : commande du matériel électrique
E : construction de la centrale
F : construction du barrage
G : installation des galeries et conduites forcées
H : montage des machines
I : essais de fonctionnement

Les contraintes d’antériorité de cet ordonnancement sont données par le tableau suivant :

28
 Opérations Durée (mois) Opérations antérieures
A 4 -
B 6 A
C 4 -
D 12 -
E 10 B, C, D
F 24 B, C
G 7 A
H 10 E, G
I 3 F, H

- Le dictionnaire des précédents :

x P(x)
A -
B A
C -
D -
E B, C, D
F B, C
G A
H E, G
I F, H

- Les niveaux des sommets :

𝑁0 = {𝐴, 𝐶, 𝐷} , 𝑁1 = {𝐵, 𝐺} , 𝑁2 = {𝐸, 𝐹} , 𝑁3 = {𝐻} , 𝑁4 = {𝐼}.

- Le graphe MPM :

29
Calendriers au plus tôt et au plus tard des tâches
Calcul des dates au plus tôt des tâches Calcul des dates au plus tard des tâches
𝑇𝐴 = 𝑇𝐶 = 𝑇𝐷 = 0 𝑇𝑍∗ = 𝑇𝑍 = 37
𝑇𝐵 = 𝑇𝐴 + 4 = 0 + 4 = 4 𝑇𝐼∗ = 𝑇𝑍∗ − 𝐿(𝐼, 𝑍) = 37 − 3 = 34
𝑇𝐺 = 𝑇𝐴 + 4 = 0 + 4 = 4 𝑇𝐻∗ = 𝑇𝐼∗ − 𝐿(𝐻, 𝐼) = 34 − 10 = 24
𝑇𝐹 = max(𝑇𝐵 + 6; 𝑇𝐶 + 4) = max(10; 4) 𝑇𝐹∗ = 𝑇𝐼∗ − 𝐿(𝐹, 𝐼) = 34 − 24 = 10
= 10
𝑇𝐸 = max(𝑇𝐵 + 6; 𝑇𝐶 + 4; 𝑇𝐷 + 12 ) 𝑇𝐸∗ = 𝑇𝐻∗ − 𝐿(𝐸, 𝐻) = 24 − 10 = 14
= max(10; 4; 12) = 12
𝑇𝐻 = max(𝑇𝐸 + 10; 𝑇𝐺 + 7) 𝑇𝐺∗ = 𝑇𝐻∗ − 𝐿(𝐺, 𝐻) = 24 − 7 = 17
= max(22; 11) = 22
𝑇𝐼 = max(𝑇𝐹 + 24; 𝑇𝐻 + 10) 𝑇𝐵∗ = min[𝑇𝐸∗ − 𝐿(𝐵, 𝐸) ; 𝑇𝐹∗ − 𝐿(𝐵, 𝐹)]
= max(34; 32) = 34 = 𝑚𝑖𝑛[14 − 6; 10 − 6] = min(8; 4)
=4
𝑇𝑍 = 𝑇𝐼 + 3 = 37 𝑇𝐴 = min[𝑇𝐵 − 𝐿(𝐴, 𝐵) ; 𝑇𝐺∗ − 𝐿(𝐴, 𝐺)]
∗ ∗

= 𝑚𝑖𝑛[4 − 4; 17 − 4] = min(0; 13)

=0
∗
𝑇𝐶 = min[𝑇𝐹 − 𝐿(𝐶, 𝐹) ; 𝑇𝐸∗ − 𝐿(𝐶, 𝐸)]
∗

= 𝑚𝑖𝑛[10 − 4; 14 − 4] = min(6; 10)

=6
∗ ∗
𝑇𝐷 = 𝑇𝐸 − 𝐿(𝐷, 𝐸) = 14 − 12 = 2
En reportant ces résultats sur le graphe, on obtient :

Pour le sommet terminal 𝑧, 𝑇𝑍 correspond à la durée minimale du projet (qui correspond au

chemin de valeur maximale aboutissant à z).
Le chemin de valeur maximale associé est appelé chemin critique, constitué de tâches
critiques : un retard sur l'une de tâches critiques entraînerait un allongement de la durée
du projet.
Dans le cadre de cet exemple, le chemin de valeur maximale est le chemin (A, B, F, I) et a pour
durée 37 mois. Autrement dit, la durée minimale du projet est de 37 mois.
Calcul des marges
Marges totales

30
C'est le retard maximum que l'on peut prendre dans la mise en route d'une tâche sans remettre
en cause les dates au plus tard des tâches suivantes.

𝑚𝑇(𝑥) = 𝑇 ∗𝑋 − 𝑇𝑋

𝑀𝑡 (𝐴) = 𝑇𝐴∗ − 𝑇𝐴 = 0 − 0 = 0
𝑀𝑡 (𝐵) = 𝑇𝐵∗ − 𝑇𝐵 = 4 − 4 = 0
𝑀𝑡 (𝐶) = 𝑇𝐶∗ − 𝑇𝐶 = 6 − 0 = 6
𝑀𝑡 (𝐷) = 𝑇𝐷∗ − 𝑇𝐷 = 2 − 0 = 2
𝑀𝑡 (𝐸) = 𝑇𝐸∗ − 𝑇𝐸 = 14 − 12 = 2
𝑀𝑡 (𝐹) = 𝑇𝐹∗ − 𝑇𝐹 = 10 − 10 = 0
𝑀𝑡 (𝐺) = 𝑇𝐺∗ − 𝑇𝐺 = 17 − 4 = 13
𝑀𝑡 (𝐻) = 𝑇𝐻∗ − 𝑇𝐻 = 24 − 22 = 2
𝑀𝑡 (𝐼) = 𝑇𝐼∗ − 𝑇𝐼 = 34 − 34 = 0

Marges libres
C'est le retard maximum que l'on peut prendre dans la mise en route d'une tâche sans remettre
en cause les dates au plus tôt des tâches suivantes.

𝑚𝐿(𝑥) = 𝑚𝑖𝑛 [𝑇𝑦 − 𝑇𝑋 − 𝑉(𝑥, 𝑦)] , le min étant pris sur les suivants 𝑦 de 𝑥.

𝑀𝑙 (𝐴) = 𝑚𝑖𝑛[𝑇𝐵 − 𝑇𝐴 − 𝐿(𝐴, 𝐵); 𝑇𝐺 − 𝑇𝐴 − 𝐿(𝐴, 𝐺)] = min(0; 0) = 0

𝑀𝑙 (𝐵) = 𝑚𝑖𝑛[𝑇𝐹 − 𝑇𝐵 − 𝐿(𝐵, 𝐹); 𝑇𝐸 − 𝑇𝐵 − 𝐿(𝐵, 𝐸)] = min(0; 2) = 0
𝑀𝑙 (𝐶) = 𝑚𝑖𝑛[𝑇𝐹 − 𝑇𝐶 − 𝐿(𝐶, 𝐹); 𝑇𝐸 − 𝑇𝐶 − 𝐿(𝐶, 𝐸)] = min(6; 8) = 6
𝑀𝑙 (𝐷) = 𝑇𝐸 − 𝑇𝐷 − 𝐿(𝐷, 𝐸) = 0
𝑀𝑙 (𝐸) = 𝑇𝐻 − 𝑇𝐸 − 𝐿(𝐸, 𝐻) = 0
𝑀𝑙 (𝐹) = 𝑇𝐼 − 𝑇𝐹 − 𝐿(𝐹, 𝐼) = 0
𝑀𝑙 (𝐺) = 𝑇𝐻 − 𝑇𝐺 − 𝐿(𝐺, 𝐻) = 11
𝑀𝑙 (𝐻) = 𝑇𝐼 − 𝑇𝐻 − 𝐿(𝐻, 𝐼) = 2
𝑀𝑙 (𝐼) = 𝑇𝑍 − 𝑇𝐼 − 𝐿(𝐼, 𝑍) = 0

II.3.Méthode PERT
II.3.1. Principes de construction du graphe

Pour la construction du graphe PERT, il faut avoir à l’esprit les principes suivants :
− Un arc correspond à une tâche
− La valeur de l'arc représente la durée de la tâche.
− Un sommet est une étape signifiante :
▪ Toutes les tâches qui y arrivent sont terminées
▪ Toutes les tâches qui en partent peuvent commencer

c
a et b doivent être terminées pour que
b c et d puissent commencer
d

31
Remarque 1 : il est quelque fois nécessaire d'introduire des tâches fictives de durée nulle

a c
a et b doivent être terminées pour que
c puisse commencer et uniquement b
doit être terminée pour que d
d commence
b

Remarque 2 : deux arcs ne peuvent avoir à la fois la même origine et la même extrémité. Il
est nécessaire de rajouter une tâche fictive dans ces conditions :

a
sera a
transformé
en

b b

Par exemple, si la tâche 𝐴 a une durée 4 et la tâche 𝐵 de durée 6 ont la même étape « début »
qui est (1) et même étape « fin » (2). Sa représentation correcte est la suivante.

Ou encore de façon symétrique :

Chaque sommet de la représentation graphique est figuré par un cercle

où n = nom ou numéro de l′étape

𝑇𝑛 𝑇 ∗
𝑛
Tn = date de début au plus tôt de l′étape
T ∗ n = date de début au plus tard de l′étape
n

− Un sommet terminal et un sommet initial sont rajoutés au graphe.

32
 − La représentation graphique est ordonnée par niveaux des sommets, c.à.d. des étapes.

II.3.2. La construction PERT

Il n’existe véritablement pas une démarche bien élaborée pour construire le graphe PERT.
Généralement, on construit par tâtonnement un graphe provisoire d’abord (au brouillon), en
collant ou en réunissant les différentes relations partielles (contraintes d’antériorité), données
par le dictionnaire des précédents.
Dans la construction de ce graphe, on doit respecter les principes de construction du graphe
ainsi que les règles d’antériorité. Dans cette optique, pour débuter, on relie les tâches qui n’ont
pas de précédents à « l’étape de début », et celles qui n’ont pas de suivants à « l’étape de fin ».
Les différentes étapes sont ensuite numérotées. Bien que l’ordre de cette numérotation importe
peu, on donne en général un nombre plus petit aux étapes proches du début. La première étape,
sommet origine porte le nombre « 1 » et le dernier porte le plus grand nombre.
En reprenant l’exemple précédent, le graphe PERT se présente comme suit :

II.3.3. Calendrier au plus tôt des étapes

Une étape 𝑛 ne pouvant débuter que lorsque toutes les étapes qui y aboutissent sont terminées,
𝑇𝑛 correspond à la valeur du chemin de valeur maximale aboutissant à 𝑛. Après avoir ordonné
le graphe par niveaux des étapes, on applique la démarche suivante :

- On pose 𝑡𝑛 = 0, pour le sommet initial,

- Pour tout sommet sélectionné n, sa date de début au plus tôt est donnée par l’expression
suivante :

𝑇𝑛 = 𝑚𝑎𝑥 [𝑇𝑚 + 𝑉(𝑚, 𝑛)] , le max étant pris sur les précédents 𝑚 de 𝑛.

Pour le sommet terminal 𝑧, 𝑇𝑍 correspond à la durée minimale du projet (qui correspond au

chemin de valeur maximale aboutissant à 𝑧). Le chemin de valeur maximlale associé est appelé
chemin critique, constitué de tâches critiques : un retard sur l'une de ces tâches critiques
entraînerait un allongement de la durée du projet.

33
 Calendrier au plus tôt des étapes
𝑡1 = 0
𝑡2 = 𝑡1 + 𝐿(1,2) = 0 + 4 = 4
𝑡3 = 𝑚𝑎𝑥[𝑡1 + 𝐿(1,3); 𝑡2 + 𝐿(2,3)] = 𝑚𝑎𝑥(4; 10) = 10
𝑡4 = 𝑚𝑎𝑥[𝑡1 + 𝐿(1,4); 𝑡3 + 𝐿(3,4)] = 𝑚𝑎𝑥(12; 10) = 12
𝑡5 = 𝑚𝑎𝑥[𝑡2 + 𝐿(2,5); 𝑡4 + 𝐿(4,5)] = 𝑚𝑎𝑥(11; 22) = 22
𝑡6 = 𝑚𝑎𝑥[𝑡3 + 𝐿(3,6); 𝑡5 + 𝐿(5,6)] = 𝑚𝑎𝑥(34; 32) = 34
𝑡7 = 𝑡6 + 𝐿(6,7) = 34 + 3 = 37

Calendrier au plus tôt des tâches

La date de début au plus tôt d'une tâche 𝑥 est égale à la date de début au plu tôt de l'étape dont
elle est issue.
𝑇𝑋 = 𝑇𝑛 si la tâche 𝑥 est issue de l'étape 𝑛

Tâche x Sommet n dont est issue x 𝑇𝑥

A 1 0
B 2 4
C 1 0
D 1 0
E 4 12
F 3 10
G 2 4
H 5 22
I 6 34

II.3.4. Calendrier au plus tard des étapes

Il s'agit de la date au plus tard à laquelle peut commencer une étape sans remettre en cause la
date de fin des travaux. Ceci sera obtenu en commençant par les sommets de niveau les plus
élevés jusqu'aux sommets de niveau les plus faibles.

𝑇 ∗ 𝑍 = 𝑇𝑍 pour le sommet terminal

𝑇 ∗ 𝑛 = 𝑚𝑖𝑛 [𝑇 ∗ 𝑚 − 𝑉(𝑛, 𝑚)] , le min étant pris sur les suivants 𝑚 de 𝑛.

34
 Calendrier au plus tard des étapes
𝑡7∗ = 𝑡7 = 37
𝑡6∗ = 𝑡7∗ − 𝐿(6,7) = 37 − 3 = 34
𝑡5∗ = 𝑡6∗ − 𝐿(5,6) = 34 − 10 = 24
𝑡4∗ = 𝑡5∗ − 𝐿(4,5) = 24 − 10 = 14
𝑡3∗ = 𝑚𝑖𝑛[𝑡6∗ − 𝐿(3,6); 𝑡4∗ − 𝐿(3,4)] = 𝑚𝑖𝑛[34 − 24; 14 − 0] = min(10; 14) = 10
𝑡2∗ = 𝑚𝑖𝑛[𝑡5∗ − 𝐿(2,5); 𝑡3∗ − 𝐿(2,3)] = 𝑚𝑖𝑛[24 − 7; 10 − 6] = min(17; 4) = 4
𝑡1∗ = 𝑚𝑖𝑛[𝑡4∗ − 𝐿(1,4); 𝑡2∗ − 𝐿(1,2); 𝑡3∗ − 𝐿(1,3)] = 𝑚𝑖𝑛[14 − 12; 4 − 4; 10 − 4]
= min(2; 0; 6) = 0

Calendrier au plus tard des tâches

La date de début au plus tard d'une tâche 𝑥 est égale à la date de début au plus tard de l'étape à
laquelle elle aboutit, diminuée de la durée de la tâche.

𝑇 ∗𝑋 = 𝑇 ∗ 𝑚 − 𝑉(𝑛, 𝑚) , si la tâche 𝑥 va du sommet 𝑛 au sommet 𝑚

Remarque : sur les tâches critiques, 𝑇 ∗𝑋 = 𝑇𝑋

𝑇𝐴∗ = 𝑡2∗ − 𝐿(1,2) = 4 − 4 = 0
𝑇𝐵∗ = 𝑡3∗ − 𝐿(2,3) = 10 − 6 = 4
𝑇𝐶∗ = 𝑡3∗ − 𝐿(1,3) = 10 − 4 = 6
𝑇𝐷∗ = 𝑡4∗ − 𝐿(1,4) = 14 − 12 = 2
𝑇𝐸∗ = 𝑡5∗ − 𝐿(4,5) = 24 − 10 = 14
𝑇𝐹∗ = 𝑡6∗ − 𝐿(3,6) = 34 − 24 = 10
𝑇𝐺∗ = 𝑡5∗ − 𝐿(2,5) = 24 − 7 = 17
𝑇𝐻∗ = 𝑡6∗ − 𝐿(5,6) = 34 − 10 = 24
𝑇𝐼∗ = 𝑡7∗ − 𝐿(6,7) = 37 − 3 = 34

En reportant ces résultats sur le graphe, on obtient :

35
 II.3.5. Calcul des marges totales

Marges totales
C'est le retard maximum que l'on peut prendre dans la mise en route d'une tâche sans remettre
en cause les dates au plus tard des tâches suivantes (donc sans retarder la fin des travaux).
𝑚𝑇(𝑥) = 𝑇 ∗𝑋 − 𝑇𝑋

En appliquant les données de l’exercice, on a :

𝑀𝑡 (𝐴) = 𝑇𝐴∗ − 𝑇𝐴 = 0 − 0 = 0
𝑀𝑡 (𝐵) = 𝑇𝐵∗ − 𝑇𝐵 = 4 − 4 = 0
𝑀𝑡 (𝐶) = 𝑇𝐶∗ − 𝑇𝐶 = 6 − 0 = 6
𝑀𝑡 (𝐷) = 𝑇𝐷∗ − 𝑇𝐷 = 2 − 0 = 2
𝑀𝑡 (𝐸) = 𝑇𝐸∗ − 𝑇𝐸 = 14 − 12 = 2
𝑀𝑡 (𝐹) = 𝑇𝐹∗ − 𝑇𝐹 = 10 − 10 = 0
𝑀𝑡 (𝐺) = 𝑇𝐺∗ − 𝑇𝐺 = 17 − 4 = 13
𝑀𝑡 (𝐻) = 𝑇𝐻∗ − 𝑇𝐻 = 24 − 22 = 2
𝑀𝑡 (𝐼) = 𝑇𝐼∗ − 𝑇𝐼 = 34 − 34 = 0

Marges libres
C'est le retard maximum que l'on peut prendre dans la mise en route d'une tâche sans remettre
en cause les dates au plus tôt des tâches suivantes (donc sans retarder la fin des travaux).

𝑚𝐿(𝑥) = 𝑇𝑚 − 𝑇𝑛 − 𝑉(𝑛, 𝑚) , si la tâche 𝑥 va du sommet 𝑛 au sommet 𝑚

Remarque : si du sommet d'arrivée 𝑚 ne partent que des tâches fictives, on retiendra le

minimum sur tous les premiers sommets suivants d'où partent au moins une tâche réelle.
Pour l’exercice précédent, on aura :
𝑀𝑙 (𝐴) = 𝑇2 − 𝑇1 − 𝐿(1,2) = 4 − 0 − 4 = 0
𝑀𝑙 (𝐵) = 𝑇3 − 𝑇2 − 𝐿(2,3) = 10 − 4 − 6 = 0
𝑀𝑙 (𝐶) = 𝑇3 − 𝑇1 − 𝐿(1,3) = 10 − 0 − 4 = 6
𝑀𝑙 (𝐷) = 𝑇4 − 𝑇1 − 𝐿(1,4) = 12 − 0 − 12 = 0
𝑀𝑙 (𝐸) = 𝑇5 − 𝑇4 − 𝐿(4,5) = 22 − 12 − 10
=0
𝑀𝑙 (𝐹) = 𝑇6 − 𝑇3 − 𝐿(3,6) = 34 − 10 − 24
=0
𝑀𝑙 (𝐺) = 𝑇5 − 𝑇2 − 𝐿(2,5) = 22 − 4 − 7 = 11
𝑀𝑙 (𝐻) = 𝑇6 − 𝑇5 − 𝐿(5,6) = 34 − 22 − 10
=2
𝑀𝑙 (𝐼) = 𝑇7 − 𝑇6 − 𝐿(6,7) = 37 − 34 − 3 = 0

36
 II.4.Le diagramme de GANTT

Le diagramme de Gantt, est l’un des outils les plus efficaces pour représenter visuellement
l’état d’avancement des différentes activités (tâches) qui constituent un projet.
Le premier diagramme de Gantt fut élaboré dans les années 1890 par l’ingénieur polonais Karol
Adamiecki dans le cadre de ses recherches en techniques de gestion et de planification. Mais
c’est la version de ce diagramme réalisée quinze ans plus tard par l’américain Henry Gantt,
ingénieur et consultant en management, qui fut définitivement adopté par les pays occidentaux
sous le nom de diagramme de Gantt.
Dans un diagramme de Gantt, on représente :
− En abscisse les unités de temps (exprimées en mois, en semaine ou en jours) ;
− En ordonnée les différents postes de travail (ou les différentes tâches)

Chaque tâche est matérialisée par une barre horizontale dont la position et la longueur
représentent la date de début, la durée et la date de fin.
Ce diagramme permet donc de visualiser très rapidement :
- Les différentes tâches à envisager
- La date de début et la date de fin de chaque tâche ;
- La durée escomptée de chaque tâche ;
- Le chevauchement éventuel des tâches et la durée de chevauchement ;
- La date de début et la date de fin du projet dans son ensemble.

Exemple d’application
Soit l’ordonnancement des opérations suivantes du projet d’un promoteur du privé.

Tâches Tâches antérieures Durée en semaine

F B 5
C A, H, B 6
G R 5
E G, S, R 5
R - 5
S D, F 4
D R 4
H B 6
A D, F, R 7
B - 6

Construire le digramme de Gantt de cet ordonnancement et en déduire la durée minimale de

réalisation du projet ainsi que les tâches constituant le chemin critique.
Résolution

37
Le digramme de Gantt montre que la durée de réalisation de ce projet est de 24 semaines. Les
tâches constituant le chemin critiques sont : B, F, A et C.

38