C0DE : 050 / 2024 /MAMBU

ENSEIGNEMENT SUPERIEUR ET UNIVERSITAIRE

UNIVERSITE DE KIKWIT (UNIKIK)

KIKWIT / LUKOLELA

Raoul MBELA KUSUMBULA

Professeur

RECHERCHE OPERATIONNELLE
IIIème LMD EN ECONOMIE, GESTION
ET INGENIERIE

2023-2024
 1

0. Introduction
01. Définition

La Recherche Opérationnelle peut être définie comme l’ensemble des méthodes et

techniques rationnelles orientées vers la recherche du meilleur choix dans la façon
d’opérer en vue d’aboutir au résultat visé ou au meilleur résultat possible.

Exemples :

 Ordonnancement
 Routage
 Optimisation industrielle
 Aide à la décision

C’est une discipline des mathématiques appliquées qui traite des questions
d'utilisation optimale des ressources dans l'industrie et dans le secteur public. Depuis
une dizaine d'années, le champ d'application de la RO s'est élargi à des domaines
comme l'économie, la finance, le marketing et la planification d'entreprise. Plus
récemment, la RO a été utilisée pour la gestion des systèmes de santé et d'éducation,
pour la résolution de problèmes environnementaux et dans d'autres domaines d'intérêt
public.

Quelques exemples pratiques

 Planifier la tournée d'un véhicule de livraison qui doit passer par des points
fixés à l'avance puis revenir à son point de départ en cherchant à minimiser la
distance parcourue est un problème typique de recherche opérationnelle. On
appelle ce problème le problème du voyageur de commerce.
 Remplir un conteneur avec des objets de tailles et de valeurs variables. Si le
conteneur a une capacité finie, on va chercher à maximiser la valeur placée
dans le conteneur. On appelle ce problème le problème du sac-à-dos.
 2

 Ordonnancer les tâches sur un chantier. Pour chaque tâche T, on connaît sa

durée. De plus, on connaît les autres tâches dont T dépend directement et
combien de temps avant ou après le début de chacune d'elles T doit démarrer.
On désire minimiser la durée totale du chantier. On dit que ce problème est un
problème d'ordonnancement.

Dans ce cours, on restera relativement simple, quelques contraintes de plus suffisent

en effet à faire de ces problèmes de véritables sujets de recherche.

02. Aspect historique de la R.O.

La recherche opérationnelle est née pendant la Seconde Guerre mondiale des efforts
conjugués d'éminents mathématiciens (dont von Neumann, Dantzig, Blackett) à qui il
avait été demandé de fournir des techniques d'optimisation des ressources militaires.
Le premier succès de cette approche a été obtenu en 1940 par le Prix Nobel de
physique Patrick Blackett qui résolut un problème d'implantation optimale de radars
de surveillance. Le qualificatif opérationnelle vient du fait que les premières
applications de cette discipline avait trait aux opérations militaires. La dénomination
est restée par la suite, même si le domaine militaire n'est plus le principal champ
d'application de cette discipline, le mot Opérationnelle prenant alors plutôt le sens
d'effectif. Ce sont donc ces mathématiciens qui ont créé une nouvelle méthodologie
caractérisée par les mots-clés modélisation et optimisation.

A partir des années 50, la recherche opérationnelle fait son entrée dans les
entreprises. En France, des entreprises comme EDF, Air France, la SNCF créent à
cette époque des services de recherche opérationnelle (qui existent toujours). La
discipline commence à être enseignée dans les universités et les grandes écoles.

Puis, au milieu des années 70, sans doute à cause d'un excès d'enthousiasme au départ
et à l'inadéquation des moyens informatiques à l'application des méthodes de la RO,
la discipline s'essouffle.
 3

A partir du milieu des années 90, on assiste à un retour en force la RO, les outils
informatiques étant maintenant à la hauteur des méthodes proposées par la recherche
opérationnelle. On assiste depuis à une explosion du nombre de logiciels
commerciaux et l'apparition de nombreuses boîtes de conseil. Pour la France, notons
Ilog (65 millions d'euros de CA), Eurodécision (2,8 millions d'euros de CA), Artelys
(1,6 millions d'euros de CA) à l'étranger Dash-Optimization (racheté début 2008 pour
32 millions de dollars par Fair Isaac), IBM Optimization et beaucoup d'autres (le site
de INFORMS Institute of Operations Research and Management Science en liste près
de 240).

03. Racines de la RO

Si l'on cherche à trouver des précurseurs à la Recherche Opérationnelle, on peut

penser à Alcuin ou à Euler qui se sont tous deux intéressés à des problèmes du type
RO, bien qu'aucune application n'ait motivé leur travail.

Alcuin est le moine irlandais chargé par Charlemagne de construire l'école palatine et
qui inventa le problème du loup, de la chèvre et du chou devant traverser une rivière
dans une barque où au plus un élément peut prendre place.

Euler est le mathématicien allemand à qui les notables de Königsberg demandèrent

s'il était possible de parcourir les ponts de la ville en passant sur chacun des 7 ponts
exactement une fois (voir Figure 1). Ce genre de problème se rencontre maintenant
très souvent dans les problèmes de tournées du type facteur ou ramassage de déchets
ménagers, dans lesquels il faut parcourir les rues d'une ville de façon optimale.

Euler trouva la solution en 1736 car un tel parcours était impossible en procédant à
une modélisation subtile par des mots. La solution actuelle, beaucoup plus simple,
utilise une modélisation par un graphe (voir Chapitre 2). On voit sur cet exemple
qu'une bonne modélisation peut simplifier de manière drastique la résolution d'un
problème.
 4

La solution correcte pour trouver l'optimum est connue depuis les années 40 et utilise
la programmation linéaire (que nous verrons au Chapitre 4), ou mieux, la théorie des
flots (que nous verrons au Chapitre 5).

04. Modélisation et optimisation

Un modèle mathématique est une traduction de la réalité pour pouvoir lui appliquer
les outils, les techniques et les théories mathématiques, puis généralement, en sens
inverse, la traduction des résultats mathématiques obtenus en prédictions ou
opérations dans le monde réel.

Les problèmes d'organisation rencontrés dans une entreprise ne sont pas

mathématiques dans leur nature. Mais les mathématiques peuvent permettre de
résoudre ces problèmes. Pour cela, il faut traduire le problème dans un cadre
mathématique, cadre dans lequel les techniques de la recherche opérationnelle
pourront s'appliquer. Cette traduction est le modèle du problème. La résolution d'un
problème dépend crucialement du modèle choisi. En effet, pour un même problème,
différentes modélisations sont possibles et il n'est pas rare que le problème semble
insoluble dans une modélisation et trivial dans une autre.

Souvent, la phase de modélisation est accompagnée ou précédée de nombreuses

discussions avec le commanditaire (lequel n'a d'ailleurs pas toujours une idée claire
de ce qu'il cherche à obtenir, ces discussions lui permettent alors également de
préciser ses objectifs). Une des vraies difficultés de départ est de savoir quels
éléments doivent être modélisés et quels sont ceux qui n'ont pas besoin de l'être. Il
faut parvenir à trouver le juste équilibre entre un modèle simple, donc plus facilement
soluble, et un modèle compliqué, plus réaliste, mais plus difficile à résoudre.

Cela dit, pour commencer, un modèle simple est toujours préférable et permet
souvent de capturer l'essence du problème (2), de se construire une intuition et de
proposer des solutions faciles à implémenter. Ce qui est demandé au chercheur
opérationnel, c'est de proposer une meilleure utilisation des ressources, voire une
 5

utilisation optimale. Les bonnes questions à se poser, face à un problème du type

recherche opérationnelle, sont les suivantes :

 Quelles sont les variables de décision ? C'est-à-dire quels sont les éléments de
mon modèle que j'ai le droit de faire varier pour proposer d'autres solutions ?
 Quelles sont les contraintes ? Une fois identifiées les variables de décision,
quelles sont les valeurs autorisées pour ces variables ?
 Quel est l'objectif ou le critère ? Quelle est la quantité que l'on veut maximiser
ou minimiser ?

La recherche opérationnelle dispose d'outils théoriques qui permettent a priori

d'apprécier ces points (rapidité de l'algorithme, qualité de la solution,...) sans avoir à
expérimenter. On parle de validation théorique. Ensuite, il faut réaliser un prototype
de l'algorithme (on peut parler de code académique si ce prototype est développé en
laboratoire) qui permet de démontrer sa réalisabilité pratique on parle de validation
pratique. Eneffet, si ces étapes sont validées, on passe au déploiement de la solution,
qui consiste à produire un code robuste, programmer une interface, discuter les
formats des fichiers d'input, de discuter la question de la maintenance du code, etc.
mais là on s'éloigne du cœur du métier du chercheur opérationnel. En résumé, la
méthodologie de la recherche opérationnelle suit en général le schéma suivant.

1. Objectifs, contraintes, variables de décision.

2. Modélisation.
3. Proposition d'un algorithme, validité théorique de l'algorithme (temps d'exécution
pour trouver la solution, qualité de la solution fournie).
4. Implémentation, validation pratique de la solution.

05. Objectif de ce cours

La recherche opérationnelle occupe une place grandissante dans l'industrie, la
logistique et les transports. Pour un ingénieur souhaitant faire un travail technique
dans ces disciplines, elle est quasi-incontournable.
 6

L'objectif de ce cours est :

 de donner les bases de recherche opérationnelle : la méthodologie, les
problèmes et les modèles typiques, les principales techniques de résolution.
 Un étudiant maîtrisant les exercices de ce cours est capable de proposer une
modélisation d'une grande part des problèmes de recherche opérationnelle
rencontrés dans l'industrie,
 de proposer des approches de résolution et d'en discuter les qualités
respectives.
 7

Chapitre Premier : Gestion de Stocks

1.1. Introduction

La gestion de stocks aide le responsable de stocks à bien le maintenir pour qu’il n’y
ait pas rupture. Il doit en effet, déterminer la quantité optimale à commander et
l’instant de commande.
Le stock est défini comme un réserve des articles quelconques qui doivent satisfaire
une demande future. On distingue plusieurs types de stocks :
 Stocks des matières premières
 Stocks des produits finis
 Etc.

1.2. Structure d’un modèle de gestion de stock

Un modèle de gestion de stocks est défini comme un ensemble d’hypothèses

représentées de manière rigoureuse, des variables essentielles du problème ainsi que
des que des relations qui existent entre elles.
Les variables peuvent être endogènes ou exogènes
 Les variables endogènes sont celles qui sont contrôlables par le gestionnaire. Il
s’agit de la quantité à commander et la fréquence de commande (instant de
commande).
 Les variables exogènes sont :

A. La demande : le gestionnaire ne connait pas la demande qui est la quantité

des articles consommés durant un temps donné. On parle de demande
annuelle, par cycle…
B. Le délai de livraison : le temps qui s’écoule entre la commande et
l’obtention des articles.
 8

C. Le cycle ou la période de réapprovisionnement, c’est le temps d’épuisement

du stock. Si on place en abscisse le temps et en ordonné les quantités, on le
graphique suivant :

Graphique 1

T= Cycle

D. Les couts : Gérer un stock implique les couts suivants :

 Cout d’approvisionnement : c’est le cout que doit supporter le

gestionnaire pour pouvoir acquérir les articles à stocker en dehors du
prix d’achat. On parle de cout de Lancement si le stock vient du
dedans de l’entreprise et de cout de passation si le stock vient du
dehors.
Ka = ka * N
Ka = Cout d’Approvisionnement
ka = Cout d’approvisionnement par commande
N = Nombre de commandes sur un exercice.
 9

 Le cout de stockage : toutes les charges correspondant au séjour des

articles dans le stock.
Graphique 2

Le cout de stockage sur une période infinitésimale ‘’dt’’ est : dKs = ks*q*dt
avec ks = le cout de stockage par unité d’article et par unité de temps.

 Le cout de Pénurie : Dans une gestion qui connait la pénurie, on peut

avoir 2 situations :
 La demande est différée (les clients sont patients)
 La demande est perdue (les clients sont impatients)
La détermination du cout se fait en considérant que la quantité q est
fictive.

dKp = kp*q*dt
kp = Cout de pénurie par unité d’article et par unité de temps.
 Le prix d’achat : les moyens mis en jeu pour acheter les articles.
Pour élaborer un modèle de gestion de stocks, il faut avoir les variables et les
hypothèses associées :
a. Hypothèses de la demande : la demande peut être déterministe c’est-à-dire
connue avec certitude ou aléatoire si les paramètres sont déterminés sur base
 10

des statistiques passées (probabilistes). En plus, la demande peut être une

variable continue ou discrète.
b. Hypothèse sur le délai : le délai peut etre déterministe c’est-à-dire la demande
et le délai sont connus ou aléatoires. Dans ce cas où le délai est déterministe,
plusieurs cas peuvent etre envisagés :
I=0, I<0 (I <T ou I ≥ T) avec I = Délai et T= Cycle.
c. Hypothèses sur le cycle (T) : on peut distinguer 3 cas :

 Le cycle n’est pas imposé : est une variable de décision

dont on doit déterminer la valeur optimale au même titre que la
quantité commandée.
Graphique 3

 Le cycle est imposé : on retrouve 2 types de modèles dans ce cas :

 Modèle à réapprovisionnement périodique
 11

Graphique 4

 Modèle à inventaire périodique : l’inventaire se fait à la fin de

la période mais on n’est pas obligé nécessairement de
commander. On commande selon certaines conditions.
Graphique 5

On commande lorsque le niveau de stock est inférieur à S. on devra déterminer So et

S.
 12

 Le cycle est unique : ce modèle a une période unique. Il faut donc déterminer
la quantité à commander pour ce type de modèle pour toute la période
considérée.

d. Hypothèse sur le cout de stockage. Si la demande est importante au cours d’un

cycle, le cout de stockage est fonction du niveau moyen de stock au cours de ce
cycle. Le stock moyen est calculé comme suit :
S = (S1+SF)/2
S1 = Stock initial et Sf Stock final
Si la demande est faible, le cout de stockage sera fonction du Sf seulement. Le cout
de stockage peut être aussi fonction de modalités d’entrées en stock. On distingue 2
modalités :
 Entrée immédiate ; les articles commandés sont stockés en une seule fois
 Entrée progressives : la livraison se fait progressivement.

e. Hypothèse sur la pénurie : on a deux situations

 Aucune rupture de stock n’est acceptée

 La rupture de stock est acceptée pour une période donnée ou peut être imposée.

Il faudra tenir compte aussi du comportement des clients, ceux-ci peuvent être
patients ou impatients.
 13

Graphique 6 et 7

f. Hypothèse sur le prix d’achat unitaire : ce prix peut être constant ou variable en
fonction de la qualité commandée (allègement si on commande une grande
quantité par exemple).
Au-delà des facteurs cités ci haut, le gestionnaire de stocks doit tenir compte de
certaines contraintes avant de considérer la solution à appliquer. Il s’agit entre autre
de :
- L’interaction ou l’incompatibilité entre différents produits lorsqu’ils doivent
etre stockés ensembles
- Limite des moyens ou des ressources disponibles : volumes, surfaces, poids,
temps opératoires, disponibilités financières.
 14

1.3. Modèles de Gestion de stocks

Généralement il existe deux types de modèles, à savoir le modèle déterministe et le

modèle aléatoire.

1.3.1. Modèle déterministe

Ce modèle est illustré par le modèle classique et simple de Wilson dont les
hypothèses sont :
- La demande est connue avec certitude
- La demande est considérée comme une variable continue
- La demande est importante au cours du cycle
- La livraison est immédiate
- Le délai de livraison est connu avec certitude
- Le prix d’achat unitaire est constant
- Aucune rupture de stock n’est tolérée
- Le cycle n’est pas imposé.
Le gestionnaire doit choisir une des alternatives suivantes :
- Commander en une fois : le cout d’approvisionnement est bas et le cout de
stockage est élevé
- Commander en plusieurs fois : le cout d’approvisionnement est élevé et le cout
de stockage est bas.
Graphique 8
 15

Si N est le nombre d’approvisionnement sur la période sur la période , le cycle sera

calculé de la manière suivante :

Le stock Optimal est avec Da la demande totale sur le temps

On peut écrire

L’analyse des couts peut se faire de la manière suivante :

1. Le cout d’approvisionnement

2. Le cout de Stockage
( )

( ) et
3. Le cout de Pénurie

4. Le cout d’achat

Le cout global de gestion sera la somme de tous les couts.

 16

Le cout total étant fonction de Q, le stock optimal (Qo) devra être la quantité qui rend
minimal le cout global de stockage, d’où il doit être trouvé en annulant la dérivée
première de Kt par rapport à Q :

Alors le cycle T optimal est : et avec le nombre des fois de commande

optimal sur le temps

Remarque : N doit être un entier naturel, si cela n’est pas le cas, on calcule Kt en
considérant les valeurs entières qui encadre N et, No sera la valeur qui minimise Kt.

Le cout Kt étant fonction de Q, d’où la courbe suivante :

Graphique 9

Si l’on égale le cout de stockage et le cout d’approvisionnement, on a :

 17

Ceci veut dire que la quantité optimale est la quantité qu’il faut pour que le cout de
stockage soit égal au cout d’approvisionnement.

Exemple

Une entreprise a un stock d’essence qui s’écoule régulièrement et répondant à la la

gestion de Wilson. Ce stock doit fournir 16,5 m3 par mois et le cout de stockage de
10 m3 est en moyenne 200$ par an. Sachant que le cout d’approvisionnement est de
100$. Déterminer la quantité à commander, le temps d’écoulement du stock et la
cadence des commandes.

Solution

To = 2,7 et No=4.4

No est compris entre 4 et 5

Si N=4

Kt = ka.

Si N=5
 18

Conclusion

On considère N=4 comme son cout Kt est faible, donc T=3 mois avec Qo=49.5 m3.
Nous pouvons élaborer les variantes du modèle de Wilson en modifiant les
hypothèses.

a. La demande est une variable discrète

Pour déterminer le cout total sur un temps de stockage, on découpe chaque cycle en
unités de temps suffisamment petit de sorte que la demande qu cours de cette unité de
temps soit égale à 1. Dans ce contexte, étant donné le caractère discret de la demande,
la pente représentant l’évolution du niveau du stock pour le cycle prendra la forme
d’un escalier.

Graphique 10

Il en résulte que le niveau maximal du stock au cours du cycle sera Q-1.

et
 19

Comme la variable est discontinue ou discrète, on ne peut dériver Kt, on va plutôt

utiliser le principe d’accroissement.

( ) ( ) ( ) ( )

Soit ( )

( )

( )

( )

( )

Si l’on reprend l’exercice précédent, en considérant que le stock contient des sacs de
ciments avec une demande de 16 sacs par mois, on aura :

( )

( )

on aura en résolvant Q=44.3

Comme No est décimal, il faut raisonner comme précédemment.

Pour N= 4 et
 20

Pour N= 5 et

Après comparaison, on va adopter N= 4 et Q = 48 sacs et T=0.25 = 3 mois.

b. Les entrées sont progressives

Les quantités n’entrent pas dans le stock dans un lot unique mais par plusieurs lots
pour une commande. On suppose connue la période de production ou délai de
fabrication de la quantité nécessaire pour satisfaire la demande. On connait aussi la
quantité d’articles produits par unité de temps.

Soit pu = la production par unité de temps

Du = la demande par unité de temps

La quantité stockée réellement par cycle est : )

La quantité produite pendant un cycle est

Les couts sont

( ) ( )

Le cout global de stockage :

( )

( )

√
( )

Si Qw est la quantité optimale pour le modèle Wikson, on écrire

 21

√
( )

Exemple : En reprenant l’exemple du modèle de Wilson et en considérant que la

demande et la production hebdomadaire sont de 3.8 m3 et 5 m3 , calculer Qo.

c. Possibilité de rupture de stock

On suppose que les clients sont patients

Graphique 11

FC = Dd = Demande différée

AO = Q = Quantité par cycle

BF = Q – Dd

Il faut remarquer que le gestionnaire doit déterminer Qo, To, No, et Dd.

( )
( )

Comme les triangles AOE et ACB sont semblables,

 22

( ) ( )

( )

Le triangle ACB et EFC étant semblables,

Kp = Cout de pénurie par unité d’article et par unité de temps.

( )
Donc

Pour Trouver la quantité optimale, on doit égaler les dérivées partielles de Kt à Zéro.

Nous avons un système de deux équations à 2 inconnues Q et Dd. La solution est :

√
( )

√ √

d.
 23

e. Le cycle est imposé

Le cycle n’est plus une variable de décision. La préoccupation du gestionnaire est de

déterminer le niveau auquel le stock doit être ramené à chaque réapprovisionnement.
La variable de décision est So (Stock optimal).

Si Dc est la demande du cycle, on peut avoir 2 cas : Dc< S et Dc>S.

 Dc<S

Graphique

Dc = S -Sf avec Sf = Stock final. AB = Dc

Pour un cycle :

( ) ( )

Or ( )

( )
( )

( )
 24

 Dc>S

Graphique 12

AB = Dc

or

( )
( )( )

( )

( )
 25

1.3.2. Modèles aléatoires

Dans ces modèles, la demande est aléatoire et on suppose que la distribution des
probabilités est la même pour chaque cycle. Comme la demande est aléatoire, le cout
global du cycle Kt est aléatoire aussi, d’où on doit chercher à minimiser l’espérance
mathématique de Kt.

Si r est la demande au cours du cycle , on aura le cout associé Kr(S) avec la

probabilité Pr.

1er cas : la Demande est discrète

L’espérance mathématique du cout total est :

( ) ∑ ( )

( )
( ) ∑ ( ) ∑ ( )

On doit calculer l’accroissement de ( ) :

( ) ( ) ( )

On arrive à ( ) ( ) ( )

Avec ( ) ∑ ( ) ∑

( ) ( )

L(S) augmente avec S, il arrive à un moment avec ( ) cesse d’etre négatif pour
devenir positif. Alors So (Stock Optimal) est déterminé par :

( ) ( )

Exemple

Pour un stock dont la demande est aléatoire allant de 0 à 4 articles, les probabilités
respectives sont 10%, 20%, 40%, 20% et 10%. Déterminer le stock qu’il faut si les
 26

couts de stockage et de pénurie par unité d’article et par unité de temps sont
respectivement de 1000 FC et 19.000 FC.

( )
∑ ∑ ( )∑

0 0 0.1 - 0.1 0.492 0.246 0.346

1 1 0.2 0.2 0.3 0.292 0.438 0.738

2 2 0.4 0.2 0.7 0.092 0.230 0.930

3 3 0.2 0.067 0.9 0.025 0.0875 0.9875

4 4 0.1 0.025 1 0 0 1

( )

( )

( )

Suivant le tableau, le stock correspondant est So=2

2eme cas : la Demande est une variable continue

L’espérance mathématique est :

( ) ∫ ( )

Avec = densité de probabilité

( )
( ) ∫ ( ) ∫ ∫ ∫

On doit avoir :
 27

( ) ( )

( ) ∫ ∫

( )

Très souvent, on procède comme si la variable était discrète :

( ) ∑ ∑

Pour trouver le stock Optimal, on procède à l’interpolation.

Exemple

Reprenons l’exemple précédent en considérant que la demande est continue. Le

tableau se présente de la manière suivante selon l’expression de r(S) :

( )
∑ ∑ ∑

0 0 0.1 - 0.1 0.492 0 0.1

1 1 0.2 0.2 0.3 0.292 0.292 0.592

2 2 0.4 0.2 0.7 0.092 0.183 0.883

3 3 0.2 0.067 0.9 0.025 0.075 0.975

4 4 0.1 0.025 1 0 0 1

On trouve S entre 2 et 3

Interpolation ( ) y]1

On a 0.95-0.883 =0.067 et 0.975 – 0.883 =0.092

0.067 = y.0.092 = 0.73

Donc So=2+0.73=2.7
 28

Chapitre Deuxième : Théorie d’Ordonnancement

2.1. Introduction

L’ordonnancement permet d’organiser un planning optimal des taches mais

également d’indiquer celles qui ne peuvent souffrir de retard sans compromettre la
durée totale du projet.

Dans l’ordonnancement, il s’agit d’ordonner dans le temps un ensemble d’opérations

contribuant à la réalisation d’un projet. Le déroulement de ces diverses opérations ou
taches doit respecter certaines contraintes qui peuvent être :

- Des contraintes d’antériorité c’est à dire une tache j ne peut commencer que
lorsqu’une tache I est terminée

- Des contraintes de dates c’est-à-dire une tache ne peut commencer avant une
certaine date.

L’objectif consiste à minimiser la durée totale de réalisation du projet compte tenu de

la durée nécessaire à la réalisation de chacune des opérations et des contraintes
qu’elles doivent respecter.

Dans les entreprises, l’ordonnancement peut porter sur la préparation et la mise en

œuvre d’un lancement d’un nouveau d’un nouveau produit afin de coordonner la
politique commerciale et sa mise en fabrication.

Cette théorie peut être utilisée dans :

- La construction d’immeubles, navires, usines

- La planification du plan d’embauche et de formation du personnel

- L’organisation d’une campagne d’information

- La préparation des manifestations commerciales

 29

- La réalisation d’un produit manufacturé complexe.

2.2. Théorie de Graphes

Un graphe est une correspondance ou une application multivoque qui associe à un

élément Xj de l’ensemble A, une partie de A.

A={x1, x2, x3, x4, x5}

Graphe = {(x1, x2) ;(x1, x3) ; (x3, x2) ;(x3, x4),(x4, x5), (x4, x6), (x5, x6)}

Nous remarquons que :

X1 est en relation avec x2, x3

X2 n’est pas en relation

X3 est en relation avec X2 et X4

La représentation d’un graphe se fait par des ares reliant des sommets.

Xi Xj

Xi est l’origine et Xj est l’extrémité

Dans cet exemple Xj est appelé Suivant de Xi et Xi est le Précédent de Xj. Ainsi, on
peut avoir des tables des suivants ou des précédents que l’on appelle Dictionnaires.

Pour l’exemple ci haut, on aura :

 30

X S(x) X P(x)

X1 X2, X3 X1 -

X2 - X2 X1 X3

X3 X2, X4 X3 X1

X4 X5, X6 X4 X3

X5 X6 X5 X4

X6 - X6 X4, X5

On peut aussi utiliser la matrice booléenne :

X1 X2 X3 X4 X5 X6 Total

X1 0 1 1 0 0 0 2

X2 0 0 0 0 0 0 0

X3 0 1 0 1 0 0 2

X4 0 0 0 0 1 1 2

X5 0 0 0 0 0 1 1

X6 0 0 0 0 0 0 0

Total 0 2 1 1 1 2 7

Le graphe se présente de la manière suivante :

X1 X2

X3 X4

X5 X6
 31

Le chemin est la succession des sommets dans un graphe (ex : x1, x23, x4). Un
chemin est appelé circuit s’il est fermé (origine coïncide avec l’extrémité).

La longueur d’un chemin de n sommets est n-1 pour les chemins non fermés et est
égale à n si le chemin est fermé.

On a de cas particuliers suivants :

- Chemin Hamiltonien , s’il passe une fois et une seule par chaque sommet

- Chemin PréHamiltonien, s’il passe au moins une fois par chaque sommet du
graphe

- Chemin Eulerien, s’il passe une fois et une seule par chaque arc du graphe

- Chemin PréEulerien, s’il passe au moins une fois par chaque arc du graphe.

On appelle niveau du sommet Xi, la longueur du plus long chemin ayant pour
extrémité Xi. Ainsi un sommet sans précédent a un niveau 0.

Pour déterminer les niveaux de sommets d’un graphe, on dresse le dictionnaire des
précédents :

5 4 6

1 2

7
 32

X S(x) X P(x)

1 5,2,3 1 -

2 3,6,7 2 1

3 4,6,7 3 1,2,5

4 6 4 3,5

5 3,4 5 1

6 - 6 3,4

7 - 7 2,3

Le niveau permettant une représentation claire du graphe serait le suivant

2.2 Pratique d’ordonnancement

Pour arriver à planifier un projet fait de plusieurs taches ou étapes de manière

rationnelle, on détermine les éléments suivant :

- Les dates

- Les marges

2.2.1. Les Dates

Les dates sont représentées par le graphique suivant :

Tx T°x dx Ty T°y
X Y
MT ML MT ML

X, Y sont les noms des taches

 33

Tx et Ty sont les dates de début au plutôt

T°x et T°y sont les dates de début au plutar

Dx est la durée entre le début de la tache x et le début de la tache y.

Si la contrainte est celle de succession, la longueur de l’arc est égale à la durée de la

tâche.

 La date au plutôt pour les sommets de niveau 0, Tx = 0 et pour les autres, Tx

est égal au plus long chemin qui arrive à la tache x

 La date au plutard : T°x = Min (T°yi – dxi)

Comme la tache Z est la fin des travaux, alors Tz = T°z c’est-à-dire la fin des travaux
ne peut etre retardée.

3.2.2. Les Marges

On distingue deux types de marge :

- Les Marges totales (MT) : c’est un retard maximum que l’on peut prendre dans
la mise en route d’une tache sans remettre en cause les dates au plus tard des
taches suivantes c’est-à-dire sans retarder la fin des travaux.

MT = T°x - Tx

- Les Marges livres (ML) : C’est un retard maximum que l’on peut apporter à la
mise en route d’une tache sans remettre en cause la date au plus tot d’aucune
tache.

ML= Min (Tyi – Tx - dxi

Remarque :

On appelle Chemin critique, le chemin constitué des taches dont MT=0.

 34

Exemple :

Pour construire un barrage, on a les opérations suivantes avec des durées

correspondantes :

Durée Opérations
Code Opérations (Mois) Pré requises
A Construction des voies d'accès 4
B Travaux de terrassements 6 a
C Construction des bâtiments 4
D Commande des matériels électriques 12
E Construction du Barrage 10 b, c, d
F Commande des matériels de tuyauterie 24 b,c
G Installation des galeries et des conduits 7 a
H Montage des machines 10 e,g
I Essai de fonctionnement 3 f,h

Tracez les graphes et déterminer les marges ainsi que le chemin critique.

Pour y arriver on adopte la démarche suivante :

1. Dictionnaire des précédents

2. Niveaux

3. Graphes

4. dx

5. Tx

6. T°x

7. MT

8. ML
Graphique
 Taches Tx T °x MT ML
A 0 0 0 0
B 4 4 0 0
C 0 6 6 6
D 0 2 2 0
E 12 14 2 0
F 10 10 0 0
G 4 17 13 11
H 22 24 2 2
I 34 34 0 0
Z 37 37 0 0

Chemin critique = a-b-f-i-z

Tx = Le plus long chemin pour arriver à X

T°x = Min (T°yi – dxi)

MT = T°x - Tx

ML = Min (Tyi – Tx – dxi)

 1

Chapitre Troisième : Programmation Linéaire

2
 3

Détermination du maximum de F:

 Fonction objectif ( 1, 2) = 6 1 + 4 2 ⇒ droite de coefficient directeur −1, 6⁄4 .

 Pour déterminer max F, on fait « glisser » la droite (translation parallèle à la
direction de la droite) du haut vers le bas jusqu’à rencontrer l’ensemble des variables
satisfaisant les contraintes ⇒ solution optimale 1, 2 = (15⁄2 , 5) avec max 𝐹𝐹 = 65.
 4

 Remarque:
On remarque que le maximum de F est atteint en un sommet du polygone convexe
des contraintes.
5
6
7
 8

On a 3 équations et 5 inconnues, d’où m=3 et n=5

Solution de base (SB)

 9

Cn m = [mn] =
( )

(35 =
( )

= = 20/2 = 10

Donc on aura 10 solutions de base

N° SB X1 X2 E1 E2 E3 SA ou SNA VALEUR DE Z
1 0 0 0 81 55 20 SBA Z=0
2 A 0 9 0 10 11 SBA Z=36
3 0 11 -18 0 20/11 SBNA
4 0 20 -99 -45 0 SBNA
5 27 0 0 -53 -34 SBNA
6 55/4 0 39,7 0 -7,5 SBNA
7 D 10 0 51 15 0 SBA Z=60
8 B 4,3 7,6 0 0 3,8 SBA Z=56,2
9 6,6 6,8 0 -5,4 0 SBNA
10 C 7,5 5 13,5 0 0 SBA Z=65

La solution optimale est Z= 65

SBA est celle qui satisfait les contraintes Xj≥0 et ou la condition de non négativité.
 10

TRAVAUX PRATIQUES

1. Etablir les graphiques des couts K=f(Q) des modèles déterministes suivants :

- Modèle de Wilson avec variation du prix d’achat

- Modèle de Wilson avec entrées progressives. Etablir pour ce modèle l’équation

K=f(Q)

2. Un fabriquant d’accessoires d’automobiles reçoit une commande de 120.000

tableaux de bord à livrer en une année. A quelle cadence doit il approvisionner
son stock si aucun retard dans les livraisons ne peut être admis ? la demande du
constructeur d’automobiles est à taux constant.

Les couts sont :

- Le cout de stockage : 3.5$/jour

- Le cout de lancement : 300$

3. Si l’on suppose une pénurie dans les conditions de l’exercice précédent de cout
10 fois le cout de stockage, calculer le QTN et le taux de défaillance ou de
pénurie.

4. Une étude statistique menée sur la demande d’un produit révèle la chance
d’avoir une demande donnée dans le tableau ci-après :

Demande 0 1 2 3 4 5

Chance (%) 90 5 2 1 1 1

Déterminer la quantité à stocker si le cout de stockage de 10 unités de produits

est de 500$ et le cout de pénurie 20 fois que le cout de stockage en considérant
que :
- La demande est discrète
- La demande est continue
 11

5. Une usine approvisionne son stock à hauteur de 3 tonnes par semaine. La

demande hebdomadaire étant de 22.5 tonnes, déterminer le stock optimal. Les
couts de stockage et d’approvisionnement sont respectivement de 2.5$ et
84.5$.

N.B : Une année égale 52 semaines

On donne :

- C1 : Cout de possession par unité restant dans le stock, en fin de période ;

- C2 : Cout de pénurie par unité manquante en cours de période
(indépendamment de la durée de la période)
- T : La durée de la période de réapprovisionnement
- Q : la consommation aléatoire pendant une période :
- F(Q) : la fonction de répartition de la variable Q.
L’espérance mathématique du cout d’approvisionnement est minimale pour un stock
S de début de période tel que :

F(S)=C2/C1+C2 (Probabilité d’avoir au plus le stock S).

6. L’entreprise Chic Mode achète à chaque début de saison les robes qui seront
vendues au cours de la saison. La demande de la clientèle au cours d’une
saison suit une loi normale de probabilité s dont l’espérance mathématique est
de 500 robes et dont l’écart type est de 100 robes. Si le nombre de robes en
magasin est insuffisant pour satisfaire la clientèle, l’entreprise Chic Mode subit
un manque à gagner de 600 $ par vente manquée. Les robes invendues en fin
de saison sont soldées avec une perte de 200 $ par robe.

Combien l’entreprise doit-elle acheter en début de saison pour minimiser

l’espérance mathématique de ses couts ?

N.B : L’utilisation de la table de la fonction de répartition de la loi normale est

indispensable.
 12

7. Le stock d’un produit en début du mois est de 50 unités. La demande du mois a

été de 30 uniformément répartie sur le mois. Le cout de stockage est de 10$ par
unité et par jour. Calculer le cout de stockage pour le mois.

8. L’année n, une entreprise dispose d’un stock de 120.000 unités d’un nouvel
article de mode qu’elle lance sur le marché à partir du mois de septembre. Elle
vend 2500 unités le premier mois puis ses ventes diminuent de 20% chaque
mois. Le cout de stockage est de 3$ par unité et par mois.

Déterminer le cout de stockage pour la période de l’année n au 1/3 de l’année

(n+1).

9. Dans une entreprise, la passation d’une commande coute 60$ et 5 $ pour son
achat. Les couts de stockage sont de 0.50$ par unité et par mois. L’entreprise
achète normalement 90.000$ de cette pièce durant l’année (cout des pièces
seulement) et l’utilisation de cette pièce s’effectue d’une façon régulière durant
l’année, déterminer la quantité de chaque commande qui minimise les frais, le
nombre optimum de commandes pendant l’année, le temps entre chaque
réapprovisionnement et le cout total de ce système de stock.

10. Une demande pour un stock peut prendre les valeurs continues X telles que
0≤X≤4, avec des probabilités pour des valeurs entières successives de 10%,
20%, 40%, 20% et 10%. Sachant que les couts de pénurie et de stockage par
unité de stock et par unité de temps sont respectivement de 2000 $ et de 38000
$, estimer le stock optimal.

11.Le Directeur de production d’une entreprise souhaite optimiser la fabrication

de deux produits dont les marges sont respectivement de 26 et 22 $/Kg avant
couverture des frais (marge sur le cout variable). Ces deux produits nécessitent
des temps d’usinage différents au sein de trois ateliers où ils doivent être
progressivement montés.
Temps de fabrication (H)
 13

Atelier1 Atelier2 Atelier3

Produit1 1 3 1
Produit2 2 2 1

Les capacités de production de trois ateliers est respectivement 20, 30 et 12

heures par jour. En fonction des équipes disponibles pour cette fabrication.
Quel est le programme de fabrication optimal ?

12. La société RK fabrique des lessives et les commerciales. Une étude du marché
a montré que l’impact des divers médias peut être caractérisé par le tableau
suivant :

Médias Audiences Audience Cout annonce

(Millions) féminine (Millions de FC)
(Million)
Télé 10 7 500
Radio 1 0.6 60
Presse 2 0.8 65

Le directeur financier de la RK a déterminé le Budget de publicité minimum

qui lui permet d’atteindre le public qu’il s’est fixé. Le directeur voudrait
atteindre au moins 20 millions de personnes dont au moins 14 millions des
femmes.

13.Une femme propose de réaliser un aliment de bétail très économique, lequel

contient obligatoirement 4 sortes de composantes nutritives. A, B, C, D.
L’industrie alimentaire produit précisément deux aliments M et N qui
contiennent ces composantes. 1 Kg d’aliment M contient 100 g de A, 100 g de
C, 200 g de D. 1 Kg d’aliment N contient 100 g de B, 200 g de C, 100 g de B ,
2 Kg de C et 1.7 Kg de D. L’aliment M coute 10$ le Kilo et N coute 4 $ le
Kilo. Quelle quantité d’aliments doit-on utiliser par jour et par animal pour
réaliser l’alimentation la moins couteuse.
 14

14.Un pays en voie de développement veut mettre en valeur une zone de 900 Ha
où deux cultures sont à priori possibles : le maïs et le Soya. Les données
relatives à ces deux cultures sont les suivantes (pour un Ha).

Maïs Soya
Rendement en quintaux à l'Ha 75 2
Prix de vente par Quintal 60 60
Main d'œuvre nécessaire (en nombre d'ouvriers) 1 2
Frais d'exploitation (salaire non compris) 300 3500
Eau nécessaire pour irriguer 14000 m /an 6000 m3/an
3

Les salaires annuels sont dans tous les cas de 500 $ par an et par personne. Les
disponibilités des différents facteurs de production sont les suivantes :

- Terre : 900 Ha

- Main d’œuvre : 1200 ouvriers agricoles

- Eau : 14000 m3/ an

On se propose, dans un premier temps de déterminer les surfaces qui seront

consacrées à chacune des cultures dans le cas où l’exploitation de cette zone est
confiée à une société privée qui a pour objectif de rendre son bénéfice maximum.
 15

TABLES DES MATIERES

0. Introduction...................................................................................................................................... 1
01. Définition ...................................................................................................................................... 1
02. Aspect historique de la R.O. ................................................................................................. 2
03. Racines de la RO .................................................................................................................... 3
04. Modélisation et optimisation ................................................................................................. 4
05. Objectif de ce cours................................................................................................................ 5
Chapitre Premier : Gestion de Stocks ...................................................................................................... 7
1.1. Introduction.............................................................................................................................. 7
1.2. Structure d’un modèle de gestion de stock .............................................................................. 7
1.3. Modèles de Gestion de stocks ................................................................................................ 14
1.3.1. Modèle déterministe ...................................................................................................... 14
1.3.2. Modèles aléatoires ......................................................................................................... 25
Chapitre Deuxième : Théorie d’Ordonnancement ................................................................................. 28
2.1. Introduction................................................................................................................................. 28
2.2. Théorie de Graphes ..................................................................................................................... 29
2.2 Pratique d’ordonnancement ......................................................................................................... 32
2.2.1. Les Dates.............................................................................................................................. 32
3.2.2. Les Marges........................................................................................................................... 33
Chapitre Troisième : Programmation Linéaire ........................................................................................ 1
TRAVAUX PRATIQUES ..................................................................................................................... 10