COURS DE GESTION

DE PRODUCTION

Professeur : Mohammed IDRISSI KAITOUNI

1
ORDONNANCEMENT

2
I/ Introduction:

L'ordonnancement est un ensemble de techniques utilisées dans la gestion

des projets pour planifier d'une manière optimale, les différentes tâches du
projet. La méthode la plus utilisée s'appelle P.E.R.T qui constitue la base
théorique du logiciel MS . PROJECT de Microsoft, et qui consiste à élaborer une
configuration optimale du planning du projet appelé " Réseau P.E.R.T , qui doit
avoir une seule entrée et une seule sortie qui correspondent au début et à la
fin du projet respectivement.
Cette méthode permet d'obtenir la durée minimale pour réaliser le projet, ainsi
que le chemin critique.

II/ Exemple :

Pour réaliser un projet, il est nécessaire d'exécuter les tâches présentées dans
le tableau suivant avec leurs contraintes d'antériorité et leurs durées
d'exécution prévisionnelles.

Tâches Précédents Durée ( Jours )

A F 10
B / 3
C A - I 11
D F 6
E B 5
F / 4
G B 15
H G-J 12
I D-E 7
J D–E 12

3
 La première étape de la méthode P.E.R.T consiste à déterminer les niveaux du
projet.
Le premier niveau est constitué des tâches qui n'ont pas de précédentes.
Pour notre exemple, N1 = B – F .
Pour trouver le niveau 2, on supprime les tâches du niveau 1 dans la colonne
des précédentes, et on cherche à nouveau les tâches qui n'ont pas de
précédentes.
Ainsi Niveau 2 = A – D – E – G
On continue ainsi et on obtient :
Niveau 3 = I – J
Niveau 4 = C – H

Ensuite, on trace le planning avec les étapes schématisées par des cercles et
les tâches par des arcs. Chaque cercle contient 3 informations : Le numéro de
l'étape en haut, la date au plus tôt en bas à gauche et la date au plus tard en
bas à droite.
Chaque étape doit être réalisée entre sa date au plus tôt et sa date au plus tard
pour que la durée du projet soit optimisée.
Pour la date au plus tôt, on choisit le maximum des durées des chemins qui
mènent vers cette étape à partir de l'étape E 0 = début du projet qui a comme
date au plus tôt 0.
Pour la date au plus tard, on raisonne de la même manière à partir de la fin du
projet, à condition de soustraire les durées et de choisir le minimum.
On définit le chemin critique comme étant le chemin des tâches critiques qui
ont imposé la date de livraison du projet.
Remarquons qu'une tâche critique doit impérativement commencer à sa date
au plus tôt et ne tolère aucune interruption pendant son exécution.
Les tâches critiques sont des tâches difficiles à gérer qui demandent de la
vigilance de la part du chef du projet et de ses collaborateurs.

4
Remarquons aussi que le chemin critique est le chemin de longueur maximale
entre le début et la fin du projet, cette longueur est égale à la date de
réalisation du projet (34 jours pour notre exemple).
Enfin la date au plus tôt et au plus tard d'une étape critique sont identiques.

5
 N1 = B – F N2 = A - D - E – G N3 = I – J N4 = C – H
Tâches Précédents
A F
B /
C A - I
E1 E5
G ( 15 ) D F
E B
3 5 22 22
F /
G B
B(3) E(5) H G-J
I D-E
J ( 12 ) H ( 12 ) J D–E

E0 E3 E6
0 0 10 10 34 34

D(6) I(7) C ( 11 )
F(4)
A ( 10 )
E2 E4

4 4 17 23

6
III/ Marges libres – Marges totales :

Soit X une tâche qui commence à l'étape E i ( t i , t' i ) et qui aboutit à l'étape
E j ( t j , t' j ) et qui a comme durée d'exécution d

On définit la marge libre et la marge totale de la tâche X par :

ML (X) = tj - ti - d
MT (X) = t'j - ti - d

Ces marges sont interprétées, comme étant le décalage maximal qu'on peut
accorder au démarrage d'une tâche à partir de sa date au plus tôt pour qu'elle
se termine exactement à la date au plus tôt (respectivement au plus tard ) de
l'étape E j .

Pour notre exemple le tableau des marges libres et totales est le suivant :

Tâches Marge libre Marge totale

A 17 – 4 – 10 = 3 j 23 – 4 – 10 = 9 j
B 3–0–3=0j 5–0–3=2j
C 34 – 17 – 11 = 6 j 34 – 17 – 11 = 6 j
D 10 – 4 – 6 = 0 j 10 – 4 – 6 = 0 j
E 10 – 3 – 5 = 2 j 10 – 3 – 5 = 2 j
F 4–0–4=0j 4–0–4=0j
G 22 – 3 – 15 = 4 j 22 – 3 – 15 = 4 j
H 34 – 22 – 12 = 0 j 34 – 22 – 12 = 0 j
I 17 – 0 – 17 = 0 j 23 – 10 – 7 = 6 j
J 22 – 10 – 12 = 0 j 22 – 10 – 12 = 0 j

7
On peut distinguer 3 types de tâches donc 3 stratégies de gestion des équipes :

1. Les tâches critiques : ML = MT = 0

Ce sont les tâches les plus difficiles à gérer ( D , F , H , J )

2. Les tâches non critiques qui aboutissent à une étape critique :

ML = MT ≠ 0
C'est le cas pour notre exemple des tâches ( C , E , G )

3. Les tâches non critiques qui n'aboutissent pas à une étape critique :
ML ≠ MT
C'est le cas des tâches A , B , I

IV/ Chronogramme d'un projet :

Comme l'indique son nom, le chronogramme est une représentation

graphique du projet par rapport à une échelle temporelle horizontale qui va du
début à la fin du projet.

Il permet de mettre en évidence les marges libres pendant lesquelles les

équipes concernées et leurs machines sont libres, ce qui permet au chef du
projet de les affecter à d'autres tâches pendant ces périodes.

8
0 3 4 8 10 14 17 18 22 28 34

G 4j

E J H
B
2j 6j

D I C
F A
3j

9
V/ Exercice :

Un projet est défini par les tâches présentées dans le tableau suivant avec leurs contraintes
d’antériorité ainsi que leurs durées d’exécution.

Tâche Tâches antérieures Durée (en jours)

A H 7
B A -G 11
C E 15
D - 12
E - 8
F E 6
G J-K 7
H - 9
I J–K 10
J H 8
K D-F 14

1) Trouver les niveaux de ce projet.

2) Elaborer le planning PERT avec pour chaque étape sa date au plus tôt et au plus tard
ainsi que le délai minimal de livraison.
3) Donner le chemin critique avec interprétation.
4) Tracer le chronogramme de ce projet et interpréter les marges mises en évidence par
ce dernier.
5) On veut réduire le délai de livraison du projet. Sur quel type de tâches doit-on agir ?
6) Donner une proposition pour réduire ce délai de 8 jours.

10
GESTION DES STOCKS

11
I) Introduction :
Pour aborder la problématique de la gestion des stocks, commençons par se
poser les deux questions suivantes :
- Comment maximiser l'approvisionnement de sorte à éviter la rupture du
stock ?
- Comment minimiser l'approvisionnement de sorte à ne pas dépasser la
capacité de stockage, et à minimiser le coût de gestion ?
Parmi les articles intéressants qui ont bien traité cette problématique, celui
paru dans la revue de l'université de HARVARD, par WILSON.
C'est pourquoi, l'un des modèles les plus sollicités porte le nom de WILSON.

II) Modèle déterministe sans rupture :

Ce modèle est déterministe c.a.d que la demande D du produit concerné est
connue sur une période θ (qui représente une année en général).
On suppose que les frais d'approvisionnement (transport, taxes…) sont fixes
et notés C L = Coût de Lancement d'un approvisionnement.
On désigne par C s le coût de stockage par jour par unité.
Ce premier modèle propose de répartir la demande D sur x fois avec à
chaque fois une quantité N t:q
D= x N et θ = x T où T est la période qui sépare 2 approvisionnements
selon le schéma suivant :
N N N

___________________________________________________________
---

T T T

12
Le coût de stockage sur la période T est :
NT
CT = CL + Cs
2
NT
C θ = x CT = x CL + x Cs
2
D Nϴ
= CL + Cs
N 2

Ce coût de gestion Cθ est une fonction de N.

Comme on cherche à le minimiser, on annule sa dérivée.
C'θ = - DC L / N2 + C s ϴ /2 = 0

2 D CL
2 DC L = Cs ϴ N2 ⇨ N=�
ϴ Cs

C'est la quantité d'approvisionnement optimale.

Le nombre d'approvisionnements est x=
D
N

ϴ
La période T qui sépare 2 approvisionnements est T=
X

Exemple :
Une entreprise importe des machines pour les vendre sur le marché local.
La demande annuelle du marché est D = 300 000 unités/an.
Le coût de lancement d'un approvisionnement est :
C L = 1764 €
Le coût de stockage est C s = 0.06 € / unité / jour.
Cette demande D va être répartie sur plusieurs fois avec à chaque fois,
la quantité :

2∗ 300 000∗ 1764

N=� = 7000 unités.
360∗0,06

13
 D 300 000
X= = = 42,857 ≈ 43 fois.
N 7000
ϴ 360
T= = ≈ 8,4 jours.
x 42,857

Le coût de gestion annuel est :

D Nϴ
Cθ = CL + Cs
N 2
300 000 0,06∗7000∗360
= * 1764 +
7000 2

= 75 600 + 75 600
= 151 200 € / an.

Remarquons l'égalité entre les 2 termes de C θ à cause de C' θ = 0 (condition

qui a permis de minimiser C θ).
Par conséquent :

C θ = 2 C s Nϴ/2 = C s Nϴ .
Supposons que le délai de livraison qui permet à la quantité N d'arriver à
partir du lancement de la demande d'approvisionnement, est D L = 2 jours
par exemple.
Il faut donc lancer la demande d'approvisionnement 2 jours avant la fin
de T= 8,4 j.

N = 7000

Q'

1667= Q T-

T-D L = 6,4 j T=8,4

14
 Q′ T−DL
N
=
T
⇨ Q' =T−DL
T
*N
6,4
Q'= * 7000 = 5333,33
8,4

D'où Q= N – Q' ≈ 1667 unité

Finalement, lorsque la quantité N=7000 arrive, on commence à écouler ces
machines, jusqu'à ce que la quantité en stock arrive à 1667 unités.
A ce moment, il faut lancer la demande d'approvisionnement.
Q s'appelle la quantité qui déclenche une demande d'approvisionnement.

III) Modèle de WILSON avec pénurie :

Contrairement au premier modèle qui interdit toute rupture du stock,

ce deuxième modèle tolère une rupture provisoire pendant une période T 2 de
chaque période T qui sépare deux réapprovisionnements (T= T 1 + T 2 ).
Pendant la période T 1 , il y'a des unités en stock et on peut honorer les
demandes exprimées.
Pendant la période T 2 , il y'a rupture et on fait "patienter" les demandes jusqu'à
l'arrivée de l'approvisionnement N ; on commence alors par livrer les
demandes en attente, et on stocke le reste S.

N S
T1 T2 T1 T2

...
x fois
15
 Pendant T 2 , il y'a un risque de "perdre" des clients, ce qui se traduit par
un manque à gagner, évalué par un coût de pénurie C p par unité par jour.
Le coût de gestion sur T est :
ST1 (N−S)T2
CT = CL + CS + Cp
2 2
𝑆𝑆 𝑋𝑋 𝑇𝑇1 𝑋𝑋 𝑇𝑇2
C θ = x CT = x CL + Cs + C p ( N-S)
2 2

Nous avons les relations :

T1 S T2 N−S
= et =
T N T N
1
et on pose θ= 1 donc x = .
T

Ainsi :
D
Cθ= C L + C s S2/ 2N + C p (N – S )2 / 2N
N

Le coût de gestion annuel C θ est fonction de 2 variables S et N.

Pour minimiser C θ , on annule les dérivées partielles de C θ.
S (N−S)
C’θ /S = C s - Cp =0
N N
Cp S
(C s + C p ) S = C p N ⇨ =
Cs+Cp N

Cp
On note r= appelé taux de pénurie.
Cs+Cp

C’θ / N = 0 et en substituant S à r N
On obtient

2 𝐷𝐷𝐷𝐷𝐷𝐷
N=� / √𝑟𝑟
θ Cs

Ou bien N WAP = N WSP / √𝑟𝑟

16
 N WAP est la quantité d'approvisionnement, ( WILSON Avec Pénurie ) de ce
deuxième modèle.
N WSP est la quantité d'approvisionnement, ( WILSON Sans Pénurie ) du
premier modèle.

𝐷𝐷
x WAP = 𝑁𝑁 Nombre d'approvisionnement
𝑊𝑊𝑊𝑊𝑊𝑊

θ
T WAP = 𝑥𝑥
𝑊𝑊𝑊𝑊𝑊𝑊 Période qui sépare 2 approvisionnements.

T1 = r T et T2 = T WAP - T1

S= r NWAP

17
Exemple :
Si on reprend : D = 300 000 unités/an,
C L = 1764 € , C s = 0,06 € / unité/ jour.
et supposons que le coût de pénurie est :
C p = 0,10 € / unité / jour.

0,10
r= = 0,625 et √𝑟𝑟 ≈ 0,79
0,06+0,10

7000
N WAP = = 8854 , 377 ≈ 8854 unités
0,79

𝐷𝐷
x WAP = 𝑁𝑁 𝑤𝑤𝑤𝑤𝑤𝑤 ≈ 34 fois

S = r N WAP ≈ 5534 unités

T = 10,625 j
T 1 ≈ 6,64 j
T2 ≈ 4 j

300 000
C θ, WAP = * 1764 + 0,06 * ( 5534 2 / (2 * 8854,377 ) )
8854,377

+ 0,10 * (( 8854,377 – 5534 )2 / ( 2 * 8854,377 ) )

≈ 59 933 €

18
Conclusion :
Pour comparer les deux modèles présentés :

N WAP = 8854 unités > N WSP = 7000 unités

X WAP = 34 fois < X WSP = 43 fois

T WAP = 10 , 625 j > T WSP ≈ 8,4 j

Malgré la complexité du deuxième modèle, il permet de réaliser des
économies, et de réduire d'une manière significative le coût de gestion annuel :

C θ, WAP < C θ, WSP

19
Exercice :
Une société importe des voitures pour les vendre sur le marché local.
La demande annuelle est 10 000 voitures. Le coût de lancement d’une
demande d’approvisionnement ainsi que le coût de stockage sont
respectivement : 250 € et 20 €/voiture/an.
1) Utiliser le modèle de Wilson sans pénurie pour déterminer la quantité
optimale, le nombre d’approvisionnements par année ainsi que la
période qui sépare deux approvisionnements.
2) Calculer le coût annuel de gestion du stock et déterminer la quantité qui
déclenche une demande de réapprovisionnement si le délai de livraison
est 3jours.
3) Elaborer un graphique qui illustre l’évolution du stock en mettant en
évidence toutes les variables d’action précédentes.
4) On suppose que le coût de pénurie est 30 €/voiture/an.
Utiliser le modèle de Wilson avec pénurie pour déterminer toutes les
variables d’action et élaborer un graphique qui montre l’évolution du
stock.
5) Comparer les deux modèles.

20
 PROBLEME
D'AFFECTATION

21
 I) Position du problème :
On dispose de n stocks a i qu'on cherche à transporter vers des destinations
qui ont exprimé des demandes :

bj , j = 1 , … , m .

Considérons par exemple n = 3 usines u1, u2 , u3 qui disposent de 3 stocks :

a 1 = 260 caisses, a 2 = 340 , a 3 = 300 . Ces caisses sont destinées à 5 centres
commerciaux C1 , C2 , … , C5 qui ont exprimé les demandes :
b 1 = 120 caisses, b 2 = 180 , b 3 = 220 , b 4 = 180 et b 5 = 200 .

Les coûts unitaires C i j pour transporter une unité ( une caisse ) de l'usine u i
vers le centre C j sont présentés dans le tableau :
C1 C2 C3 C4 C5

u1 70 95 70 65 60

u2 80 90 100 80 95

u3 90 100 120 85 100

Résoudre le problème de transport revient à trouver une configuration

optimale qui permet de transporter les stocks a i des origines ( usines ) vers les
destinations ( centres commerciaux ) , de sorte à respecter les 3 conditions
suivantes :
1) On doit minimiser le nombre de véhicules qui assurent cette opération.
2) On doit respecter les contraintes au départ , CD à chaque origine i :
a i = ∑𝑗𝑗 𝑥𝑥 𝑖𝑖𝑖𝑖 , ∀ i = 1 , … , n . où x i j est la quantité d'unités affectée au
véhicule de i vers j.
Le stock a i doit correspondre au total des quantités qui partent de
l'origine i .
On doit également respecter les contraintes à l'arrivée CA pour chaque
destination j :
b j = ∑𝑖𝑖 𝑥𝑥 𝑖𝑖𝑖𝑖 , j = 1 , … , m

22
 Le total des quantités livrées à la destination j doit correspondre
exactement à la demande b j

3) Le coût global de cette opération doit être minimal :

F = ∑𝑖𝑖 ,𝑗𝑗 𝑥𝑥 𝑖𝑖𝑖𝑖 . 𝐶𝐶 𝑖𝑖𝑖𝑖

Comme la recherche d'une solution optimale de ce problème est relativement
complexe, on va procéder en 2 étapes :
- On commence par chercher une solution de base qui respecte les deux
premières conditions.
- On utilisera ensuite un algorithme qui va transformer la solution de base,
itération par itération , en diminuant à chaque itération le coût F jusqu'à
la convergence vers la solution optimale.

II) Solutions de base :

La solution qu'on cherche peut être modélisée par un graphe connexe,

biparties c.a.d les connections ou arcs du graphe (véhicules) ne peuvent avoir
qu'un sens : des origines vers les destinations.
On montre grâce à la théorie des graphes, qu'une telle solution possède
exactement n + m - 1 arcs c.a.d: 3 + 5 - 1 = 7 arcs pour l'exemple.
Une première solution de base donne la priorité à l'arc (première usine ,
premier centre) qui correspond à la Case Nord Ouest CNO du tableau.
On a un stock a 1 = 260 caisses à l'usine 1 , et la demande du premier centre est
b 1 = 120 .
On satisfait au mieux cette demande en envoyant x 11 = 120 caisses .
Cette demande b 1 est complètement satisfaite ( la première colonne est
saturée ) .
On passe à la deuxième demande b 2 = 180 , et on commence par envoyer le
reste du stock 1 , 140 caisses ce qui aboutit à l'épuisement du stock 1
( saturation de la première ligne ) , et il reste 40 caisses à envoyer de
l'usine 2 , …

23
 C1 C2 C3 C4 C5

u1 120 140 260

u2 40 220 80 340

u3 100 200 300

120 180 220 180 200

C1 ( b 1 = 120 )
120

( a 1 = 260 ) u1
140
C2 ( b 2 = 180 )
40

( a 2 = 340 ) u2 220 C3 ( b 3 = 220 )

80
C4 ( b 4 = 180 )
100

( a 3 = 300 ) u3
200
C5 ( b 5 = 200 )

Cette solution CNO est une solution de base.

En effet le nombre d'arcs du graphe est 7 qui correspond à
3 (origines) + 5 (destinations ) – 1.

24
Les contraintes de départ sont vérifiées :
a 1 = 260 = 120 + 140 , a 2 = 340 = 40 + 220 + 80
a 3 = 300 = 100 + 200 .
Les contraintes à l'arrivée sont vérifiées
b 1 = 120 = 120 , b 2 = 180 = 140 +40 , b 3 = 220 = 220
b 4 = 180 =80 + 100 , b 5 = 200 = 200 .

Le coût de cette solution de base CNO est

F = 120 * 70 + 140 * 95 + 40 * 90 + 220 * 100 + 80 * 80 + 100 * 85 + 200 * 100
= 82 200 € .

Exercice 1 :
Chercher la solution CNE , qui donne la priorité à l'arc ( Nord , Est ) , qui va de
l'usine 1 vers le centre 5 , et vérifier que c'est une solution de base.

III) Algorithme d'optimisation de la solution de base :

L'idée principale de cette étape , consiste à tester chaque liaison ou arc non
retenue par la solution de base ( il y'a 8 cases vides ,
8 = (3-1) (5-1) = (n-1) (m-1) ) .
Pour tester un arc ( i , j ) , on calcule la variation du coût Δ( i , j ) , générée par
l'introduction d'une unité sur cet arc .
Si Δ > 0 alors on augmente le coût , donc on élimine
Si Δ < 0 alors on diminue et on calcule le Maximum d'Unités qu'on peut affecter
à cet arc noté M U ( i , j ) . La réduction du coût est alors R( i , j ) .

25
 Commençons par ( u1 , C3 ) , première case vide du tableau , ce qui
correspond à créer une liaison de l'usine 1 vers le centre 3 , avec une seule
unité pour test .

La chaine de substitution pour aller de u1 vers C3 est

CS (u1 , C3 ) = u1 – C2 – u2 – C3
( Une propriété des graphes connexes biparties , est l'existence d'une chaine
unique entre n'importe quelle origine et n'importe quelle destination )

C1

u1 C2 C3

C2 u1 140 0 139 1

u2 C3 u2 40 220 41 219

C4

u3
C5

C2 C3

u1 -95 +70 Δ ( u1,C3 ) = +70 – 95 + 90 - 100 = -35 €

u2 +90 -100

Ce qui signifie une réduction de 35 € pour chaque caisse de l'usine 1 vers le

centre 3 .

26
Il faut maintenant maximiser la quantité de caisses pour cet arc :

C2 C3 C2 C3

u1 140 0 140 u1 0 140 140

u2 40 220 260 u2 180 80 260

180 220 180 220

M u ( u1, C3 ) = 140
La réduction du coût est

R ( u1, C3 ) = Δ ( u1, C3 ) . M u ( u1, C3 )

= 35 * 140
= 4900 €

Remarquons que l'introduction de l'arc ( u1, C3 ) a impliqué l'élimination de

l'arc ( u1, C2 ) .
Ce qui garde le nombre d'arcs 7 inchangé.

Testons maintenant la liaison ( u1, C4 ) .

CS ( u1, C4 ) = u1 – C2 – u2 – C4

C2 C4

u1 -95 +65 Δ ( u1,C4 ) = +65 – 95 + 90 - 80 = - 20 €

u2 +90 -80

27
 C2 C4 C2 C4

u1 140 0 140 u1 0 140 140

u2 40 220 260 u2 180 80 260

180 220 180 220

R ( u1, C4 ) = 140 * 20 = 2800 €

Pour ces 2 cas testés , le premier donne plus de réduction . Nous allons tester
le reste des arcs non retenus par la solution de base ( les cases vides du tableau
CNO ) et nous choisissons l'arc qui donne le maximum de réduction .

CS ( u1, C5 ) = u1 – C2 - u2 - C4 - u3 – C5

C2 C4 C5
-95 +60
u1
u2 +90 -80 Δ ( u1,C5 ) = +60 – 95 + 90 - 80 + 85 - 100= - 40 €

u3 +85 -100

C2 C4 C5 C2 C4 C5

u1 140 0 140 u1 140 140

u2 40 80 120 u2 ! 120

u3 100 200 300 u3 240 60 300

180 180 200 180 180 200

28
La quantité ( u2,C4 ) plus 240 doit donner 180 !
Ceci n'est pas possible ce qui signifie que la quantité initiale 140 unités affectée
à ( u1,C5 ) a dépassé le plafond de ( 240 – 180 ) = 60 unités

Donc on recommence avec 140 – 60 = 80 unités

C2 C4 C5
60 80
u1 140

u2 120 0 120 M u ( u1 , C5 ) = 80

u3 180 120 300 R ( u1 , C5 ) = 80 * 40 = 3200 €

180 180 200

Test : Arc ( u2 , C1 )

CS ( u2 , C1 ) = u2 – C2 - u1 – C1

C1 C2

u1 -70 +95 Δ ( u2 , C1 ) = +95 – 90 + 80 - 70 = + 15 > 0

u2 +80 -90 Augmentation du coût !

29
Test : Arc ( u2 , C5 )

CS ( u2 , C5 ) = u2 – C4 - u3 – C5

C4 C5

u2 -80 +95 Δ ( u2 , C5 ) = +95 – 100 + 85- 80 = 0

u3 +85 -100 Ceci signifie que la liaison ( u2 , C5 ) ne modifie pas le coût.

Test : Arc ( u3 , C3 )

CS ( u3 , C3 ) = u3 – C4 - u2 – C3

C3 C4

u2 -100 +80 Δ ( u3 , C3 ) = +120 – 100 + 80- 85 = 15 > 0

u3 +120 -85 Donc augmentation du coût !

Test : Arc ( u3 , C1 )

CS ( u3 , C1 ) = u3 – C4 - u2 – C2 - u1 – C1
C1 C2 C4
-70 +95
u1
u2 -90 +80 Δ ( u3,C1 ) = +90 – 70 + 95 – 90 + 80 – 85 = 20 € > 0

u3 +90 -85

30
 Test : Arc ( u3 , C2 )

CS ( u3 , C2 ) = u3 – C4 - u2 – C2

C2 C4

u2 -90 +80 Δ ( u3 , C2 ) = +100 – 85 + 80 - 90 = 5 € > 0

u3 +100 -85

Finalement , après avoir testé les 8 cases vides qui correspondent aux 8 arcs
non retenus par la solution CNO , la meilleure réduction est celle de
l'arc ( u1,C3 ) avec 4900 €
C'est elle qui définit la première itération CNO par :
C1 C2 C3 C4 C5

u1 120 140 260

u2 180 80 80 340

u3 100 200 300

120 180 220 180 200

Cette première transformation CNO reste une solution de base ( 7 connexions )

avec les contraintes au départ et à l'arrivée satisfaites , mais elle coûte 4900 €
de moins que CNO c.a.d : 82 200 – 4900 = 77 300 €
L'algorithme continue en déterminant la deuxième itération exactement de la
même manière en testant les 8 cases vides de la première itération , en
éliminant les cas de variation Δ positives et de choisir le maximum de
réduction R ce qui définit la deuxième itération .
L'algorithme continue à déterminer les itérations une après l'autre jusqu'à la
convergence lorsque toutes les variations Δ deviennent positives .

31
 L'algorithme converge en un nombre fini d'itérations car dans le cas contraire ,
le coût des itérations est une suite strictement décroissante , ce qui signifie
qu'à partir d'une certaine itération le coût va devenir négatif ce qui est
absurde .

Exercice 2 :
Un problème d'affectation est défini par 4 origines qui qui disposent des
4 stocks .
a 1 = 320 unités , a 2 = 230 , a 3 = 150 , a 4 = 100 .
Les demandes des 4 destinations sont :
b 1 = 155 , b 2 = 360 , b 3 = 120 , b 4 = 165

Les coûts unitaires sont :

D1 D2 D3 D4
origine 1 46 82 49 15
origine 2 52 43 30 41
origine 3 15 18 60 70
origine 4 94 72 71 52

1) Déterminer la solution de base CNO , en vérifiant que c'est une solution

de base et en calculant son coût .
2) Tester tous les arcs non retenus par cette solution et en déduire la
première transformation par l'algorithme d'optimisation .

32
 PROGRAMMATION
Programmation Linéaire
LINEAIRE

33
 I- Introduction

La programmation linéaire est un ensemble de techniques utilisées dans divers

domaines relevant de l’optimisation.

Une étude de programmation linéaire passe en général par trois étapes

fondamentales :

1. La modélisation : consiste à élaborer un modèle appelé Programme

linéaire noté PL qui traduit toutes les données du problème (données

techniques, budgétaires, logistiques, temporelles, …) en équations.

2. La résolution : consiste à résoudre le programme linéaire par deux

méthodes : la méthode de la résolution graphique et l’algorithme du

simplexe.

3. L’analyse de la solution obtenue.

34
 II- Exemple

Une entreprise industrielle fabrique et commercialise deux types de machines P

et Q. La fabrication de ces machines passe par trois ateliers dont les capacités

pendant une période de production, ainsi que les coûts horaires sont présentés

dans le tableau suivant :

Mach P Mach Q Coût Capacité

Atelier 1 3h 1,5 h 8 €/h 300 h

Atelier 2 1,5 h 6,75 h 10 €/h 810 h

Atelier 3 6h 4,5 h 15 €/h 720 h

Les prix de vente de machines sont :

179 € pour une machine P et 177 € pour une machine Q.

Soient X et Y les quantités de machines P et Q qu’on peut fabriquer pendant une

période de production.

Commençons par calculer le bénéfice unitaire :

Bénéfice (1 mach P) = 179 – (3 x 8 + 1,5 x 10 + 6 x 15) = 50 €

Bénéfice (1 mach Q) = 177 – (1,5 x 8 + 6,75 x 10 + 4,5 x 15) = 30 €

La marge bénéficiaire Z pour X machines P et Y machines Q est :

35
Z = 50 X + 30 Y

Pour l’atelier 1, une machine P consomme 3 h donc pour X machines P, on

consomme 3 X. De même, une machine Q consomme 1,5 h dans l’atelier 1, donc

Y machines Q consomment 1,5 Y.

Comme la capacité de l’atelier 1 est de 300 h pendant une période de

production :

3 X + 1,5 Y ne doit pas dépasser 300 h , cad 3 X + 1,5 Y ≤ 300

De la même manière, pour les ateliers 2 et 3 respectivement :

1,5 X + 6,75 Y ≤ 810 et 6 X + 4,5 Y ≤ 720

On obtient alors le programme linéaire :

Max Z = 50 X + 30 Y

1 3 X + 1,5 Y ≤ 300

2 1,5 X + 6,75 Y ≤ 810

3 6 X + 4,5 Y ≤ 720

4 X>0

5 Y>0

Un PL est constitué d’une fonction Z à maximiser ou minimiser sous contraintes

explicites 1, 2, 3 et implicites 4, 5.
36
On vient de terminer la première étape de l’étude (modélisation) et on passe

donc à la deuxième étape résolution en commençant par la méthode de

résolution graphique.

Comme toutes les contraintes sont linéaires, on trace les droites

correspondantes et on choisit les demi-plans au-dessous des droites pour des

contraintes d’infériorité ou au-dessus des droites pour des contraintes de

supériorité.

On choisit deux points de chaque droite :

D1 : (0,200) , (100, 0)

D2 : (0,120) , (90, 100)

D3 : (0,160) , (120 , 0)

37
 250

200

150

D1
D2
D D3
100 C

50

O
A
0
0 20 40 60 80 100 120 140

La zone (S) représente la zone des solutions acceptables qui respectent toutes

les contraintes.

Dans cette zone, il faut chercher le point optimal qui maximise la fonction Z.

Un théorème mathématique montre que le point optimal ne peut être qu’un

sommet du polygone OABCD.

On élimine les trois sommets O, A et D car ils correspondent à une production

nulle pour les machines P ou Q.

38
Il reste à comparer entre B et C pour choisir celui qui maximise la marge du

bénéfice Z.

B ∈D 1 ∩D 3

3 X + 1,5 Y = 300

6 X + 4,5 Y = 720

1,5 Y = 120  Y = 80  X = 60

Z(B) = 50 x 60 + 30 x 80 = 5400 €

C ∈D 2∩D 3

1,5 X + 6,75 Y = 810

6 X + 4,5 Y = 720

22,5 Y = 2520  Y = 112 et X = 36

Z(C) = 50 x 36 + 30 x 112 = 5160 €

Donc parmi les deux points B et C, celui qui maximise Z est B : c’est le point

optimal.

Finalement, pour maximiser la marge bénéficiaire Z pendant une période de

production pour atteindre le bénéfice maximal, il faut fabriquer exactement :

X optim = 60 machines P et Y optim = 80 machines Q

et le bénéfice maximal est : Z = 5400 €

39
Avant de présenter l’algorithme du simplexe, analysons la solution obtenue en

ce qui concerne la saturation des contraintes.

Une contrainte est dite saturée si sa variable d’écart est nulle ce qui signifie que

le point optimal appartient à la droite frontière de cette contrainte.

Pour notre étude, le point optimal B ∈D 1 ∩D 3 donc la première et la troisième

contrainte sont saturées ce qui revient à dire que le premier et le troisième

atelier ont tourné au maximum de leurs capacités 300 h et 720 h.

Néanmoins, le deuxième atelier n’a pas saturé sa capacité de 810 h.

Il reste un écart :

E 2 = 810 – (1,5 x 60 + 6,75 x 80) = 180 h

C’est l’écart entre le point B et D 2 .

N.B : La méthode graphique est une méthode simple qui donne facilement la

solution du PL.

Cependant, lorsque le nombre de variables dépasse 3, cette méthode devient

non praticable, d’où la nécessité d’un algorithme.

40
 III- Algorithme du Simplexe

Cet algorithme permet de converger vers la solution optimale, par des itérations

successives du PL.

Il est initialisé par le PL standard, obtenu par introduction des variables d’écart

E i et en remplaçant les contraintes d’infériorité par des égalités. Pour le PL du

paragraphe précédent, le PL standard est :

Max Z = 50 X + 30 Y

3 X + 1,5 Y + E 1 = 300

1,5 X + 6,75 Y + E 2 = 810

6 X + 4,5 Y + E 3 = 720

X>0

Y >0

E1 ≥ 0

E2≥ 0

E3≥ 0

41
 1) Premier tableau simplexe

X Y E1 E2 E3 Résultat Base Test

l1 3 1,5 1 0 0 300 E1 100 (VS)

l2 1,5 6,75 0 1 0 810 E2 540

l3 6 4,5 0 0 1 720 E3 120

l4 50 30 0 0 0 0 Z

(VE)

Pour passer d’un tableau simplexe au suivant, on commence par effectuer un

changement de variable en remplaçant dans la base la variable sortante(VS) par

la variable entrante(VE).

La variable entrante est celle qui a le plus grand coefficient de la dernière ligne,

cad X pour ce tableau.

La variable sortante est celle qui a le coefficient le plus faible de la colonne test

obtenue en divisant la colonne résultat par la colonne de la variable entrante :

300 / 3 = 100 , 810 / 1,5 = 540 et 720 / 6 = 120

Donc la variable sortante de ce tableau est E 1 .

On définit le pivot d’un tableau comme l’intersection entre la ligne (VS) et la

colonne (VE) , cad 3.

42
 2) Deuxième tableau simplexe

On remplace la (VS) E 1 par la (VE) X dans la base et on transforme la ligne du

pivot l 1 en la divisant par le pivot 3 pour avoir la normalité 1 et l’orthogonalité 0.

X Y E1 E2 E3 Résultat Base Test

L 1 =1/3 l 1 1 1/2 1/3 0 0 1000 X 200

L 2 =l 2 -½l 1 0 6 -1/2 1 0 660 E2 110

L 3 = l 3 -2l 1 0 3/2 -2 0 1 120 E3 80 (VS)

L 4 =l 4 -50/3l 1 0 5 -50/3 0 0 -5000 Z

(VE)

Le test d’arrêt de l’algorithme est obtenu lorsque la dernière ligne devient

complètement négative ou nulle. Comme ce n’est pas le cas pour le deuxième

tableau, on va procéder à une autre transformation avec la (VE) Y et la variable

sortante E 3 et le pivot 3/2.

43
 3) Troisième tableau simplexe

X Y E1 E2 E3 Résultat Base

L 1 - 1/3L 3 0 60 X

L2 - 4 L3 0 180 E2

L 3 / (3/2) 1 80 Y

L 4 – 10/3 L 3 0 0 -10 0 -10/3 -5400 Z

On remarque que la dernière ligne est devenue négative ou nulle donc c’est le

dernier tableau et l’algorithme du simplexe a donc convergé vers la solution

optimale qu’on peut lire sur la colonne résultat :

X = 60 , Y = 80 , E 2 = 180 et Z = 5400 € .

En effet, pour ce tableau et les deux précédents, lorsqu’une variable est présente

dans la base, on lui affecte la valeur voisine de la colonne résultat.

Si une variable est absente, on lui affecte zéro.

Par exemple, E 1 et E 3 sont absentes de la base de ce tableau donc elles valent zéro

ce qui signifie que la première et troisième contrainte sont saturées.

Pour le deuxième tableau, X = 100 et Y = 0 (car elle est absente de la base).

44
Ce deuxième tableau correspond donc au sommet A de la zone des solutions (S)

du graphique précédemment étudié :

250

200

150
D1
D2
100 D C
D3
B
50

0 O A
0 20 40 60 80 100 120 140

La valeur 660 représente l’écart E 2 pour le sommet A.

La valeur 120 représente l’écart E 3 pour le sommet A.

La valeur 5000 représente le bénéfice Z pour A.

Le premier tableau correspond au sommet O (X=0 , Y=0) car X et Y sont absents

de la base du premier tableau.

Finalement, les trois tableaux simplexe de cette étude correspondent au

chemin :

OAB.

45
Remarquons qu’on aurait pu avoir le chemin O D  C  B avec quatre

tableaux, si la variable (VE) du premier tableau était Y au lieu de X cad si le

coefficient de Y dans l’expression de Z était supérieur à 50 €.

46
Exercice

Un problème de production a été modélisé par le programme linéaire suivant :

Max Z = 120 X + 130 Y

6 X + 2 Y ≤120

X + 4 Y ≤ 100

5X + 5 Y ≤ 150

X>0

Y>0

1) Utiliser la méthode de résolution graphique pour obtenir les quantités

optimales X et Y ainsi que le bénéfice maximal Z.

2) Préciser les contraintes saturées et calculer l’écart de la contrainte non

saturée.

3) Appliquer l’algorithme du simplexe avec interprétation de chaque

tableau.

47
IV- Simplexe Dual

Exemple

Un opérateur télécom veut lancer un nouveau service. Pour garantir le succès

de ce lancement, il a confié à un cabinet de communication d’organiser une

campagne de publicité qui cible trois catégories de consommateurs

potentiels. Deux supports médiatiques sont utilisés : la télévision et la radio

selon le tableau suivant :

Catégorie 1 Catégorie 2 Catégorie 3 Coût

Télé 10 25 9 10000 €/unité

Radio 5 30 8 7000 €/unité

Effectifs 9100 25000 9000

Les effectifs sont donnés en milliers. Par exemple, pour la catégorie 1,

l’effectif est 9100 x 1000.

Le reste des chiffres correspond au taux d’audience lorsqu’un message passe

à la télé, il est regardé par 10 mille personnes de la catégorie 1,25 mille

personnes de la catégorie 2 et 9 mille personnes de la catégorie 3.

48
D’autre part, pour que cette campagne soit efficace, le cabinet de

communication a estimé qu’elle doit au moins toucher 50% de la catégorie

1 , 70% de la catégorie 2 et 30% de la catégorie 3.

Soient X et Y le nombre de passages du message à la télé et à la radio.

Le coût total est Z = 10000 X + 7000 Y

Comme il faut toucher au moins 50% de l’effectif 9100 de la catégorie 1 :

10 X + 5 Y ≥ 0,5 x 9100 = 4550

De même pour les autres catégories :

25 X + 30Y ≥ 0,7 x 25000 = 17500

9 X + 8 Y ≥ 0,3 x 9000 = 2700

Le programme linéaire qui minimise le coût Z de la campagne en respectant

les contraintes exigées est donc :

Min Z = 10000 X + 7000 Y

10 X + 5 Y ≥ 4550

25 X + 30Y ≥ 17500

9 X + 8 Y ≥ 2700

X>0

49
 Y>0

Commençons par la méthode de résolution graphique avec pour chaque

droite un couple de points :

D1 : (0,910) , (455,0)

D2 : (0,583) , (700,0)

D3 : (0,337) , (300,0)

1000

900

800

700

600
D1
500 Zone des solutions (S) D2

400 D3
On remplace la M
300

200

100
entreprise industrielle fabrique et commercialise deux types de machines P et
0
0 100 200 300 400 500 600 700 800

50
La zone (S) est l’ensemble des points M(X,Y) avec un nombre X de passages à la

télé et un nombre Y de passages à la radio qui respectent les seuils exigés par le

cabinet. Comme on cherche à minimiser le coût Z dans cette zone, le seul point

qui convient est M.

M∈D 1 ∩D 2

10 X + 5 Y = 4550

25 X + 30 Y = 17500

En multipliant la première par 6, on obtient :

60 X – 25X = 9800 et X = 9800 / 35 = 280

Y = (4550 – 2800) / 5 = 350

Finalement, pour que cette campagne soit efficace au moindre coût, il faut

diffuser le message 280 fois à la télé et 350 fois à la radio.

Le coût total minimal de cette campagne est :

Z = 10000 x 280 + 7000 x 350 = 5250000 €.

Comme le point optimal M appartient à D1 et D2 , les deux premières contraintes

sont saturées, ce qui s’interprète par le fait que les seuils exigés des deux

premières catégories ciblées 4550 mille et 17500 mille ont été respectés sans

51
aucun dépassement. Cependant, la troisième contrainte n’est pas saturée. En

effet, les 2700 mille exigés pour la troisième catégorie a été dépassé d’un écart :

E 3 = (9 x 280 + 8 x 350) – 2700 = 2620 mille

Passons maintenant à l’algorithme du simplexe qu’on va initialiser par le

programme linéaire standard :

min Z = 10000 X + 7000 Y

10 X + 5 Y – E 1 = 4550

25 X + 30 Y – E2 = 17500

9 X + 8 Y – E 3 = 2700

X>0

Y>0

E1 ≥ 0 , E2 ≥ 0 , E3 ≥ 0

Le premier tableau simplexe est donc :

52
 X Y E1 E2 E3 Résultat Base Test

10 5 -1 0 0 4550 !

25 30 0 -1 0 17500 !

9 8 0 0 -1 2700 !

10000 7000 0 0 0 0 !

On remarque qu’il est impossible d’avoir une base orthonormée à cause des -1

parce que les variables d’écart E i ont été introduites négativement à cause des

contraintes de supériorité.

Pour contourner cette difficulté, on définit une version du simplexe à partir du

programme linéaire primal par transposition.

Porgramme dual :

max W = 4550 A + 17500 B + 2700 C

10 A + 25 B + 9 C ≤10000

5 A + 30 B + 8 C ≤ 7000

A>0

B>0

C>0

53
Le PL dual s’obtient à partir du PL primal grâce aux règles suivantes :

- L’écriture du primal en lignes devient une écriture du dual en colonnes

- Les contraintes de supériorité deviennent des contraintes d’infériorité du

dual

- La fonction Z à minimiser du primal devient une fonction W à maximiser

du dual

Nous allons appliquer le simplexe au PL dual standard :

max W = 4550 A + 17500 B + 2700 C

10 A + 25 B + 9 C + E 1 ’ = 10000

5 A + 30 B + 8 C + E 2 ’ = 7000

A>0

B>0

C>0

E1’ ≥ 0

E2’ ≥ 0

54
 A B C E1’ E2’ Résultat Base Test

l1 10 25 9 1 0 10000 E1’ 400

l2 5 30 8 0 1 7000 E2’ 233 (VS)

l3 4550 17500 2700 0 0 0 W

(VE)

A B C E1’ E2’ Résultat Base Test

L 1 =l 1 -5/6 l 2 35/6 0 14/6 1 -5/6 25000/6 E1’ 714 (VS)

L 2 = 1/30 l 2 5/30 1 8/30 0 1/30 7000/30 B 1400

L 3 =l 3 -1750/3l 2 4900/3 0 -5900/3 0 -1750/3 -12250000/3 W

(VE)

A B C E1’ E2’ Résultat Base

L 1 /(35/6) 1 714,28 A

L 2 – 1/35 L 1 0 114,28 B

L 3 – 280 L 1 0 0 -2620 -280 -350 -5250000 W

55
Comme la dernière ligne du troisième tableau est négative ou nulle, on arrête

les transformations et on utilise la règle suivante :

Les valeurs marginales du dual correspondent aux valeurs optimales du primal

et réciproquement.

Les valeurs marginales sont celles de la dernière ligne du dernier tableau. Ainsi :

marg E 1 ’ = 280 = X optim

marg E 2 ’ = 350 = Y optim

max W = 5250000 = min Z

Les deux zéros de la dernière ligne montrent que les deux premières contraintes

du primal sont saturées : E 1 = E 2 = 0

La valeur 2620 représente l’écart E 3 de la troisième contrainte du primal

(projection de la troisième variable C).

56
Exercice

Un problème de programmation linéaire a été modélisé par le programme

linéaire :

min Z = 30 X + 35 Y

X + Y ≥ 250

X + 2Y ≥ 400

3 X + Y ≥ 350

X>0

Y>0

1) Utiliser la méthode de résolution graphique pour illustrer la zone des

solutions acceptables et calculer les quantités optimales X , Y ainsi que les

charges minimales Z.

2) Calculer l’écart des contraintes non saturées.

3) Ecrire le programme linéaire dual.

4) Appliquer le simplexe et interpréter le dernier tableau dual.

57