Recherche Opérationnelle BAC+3 MP et SCAI

ENSEIGNEMENT SUPERIEUR ET UNIVERSITAIRE

INSTITUT SUPERIEUR PEDAGOGIQUE D’UVIRA

ISP-UVIRA

B.P 2316 Bujumbura/Burundi

E-mail: [Link]@[Link]
Site internet: [Link]

Cours de Recherche Opérationnelle destiné

aux étudiants de BAC+3 MP et BAC+3 IG &
GCA
Par AMANI MAISHA Sulutani
Chef de Travaux

Année Académique :2025-2026

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

I. Intitulé du cours :Recherche Opérationnelle (RO)

II. Promotion :BAC+3MP et BAC + 3 SCAI
III. Nombre d’heures :45H théoriques et 15H pratiques
IV. Enseignant :AMANI MAISHA Sulutani, Chef de Travaux au
Département d’Informatique de Gestion à l’ISP-Uvira
(contact : 0978130173, amanimaisha8@[Link])
V. Objectif du Cours :

Le cours de Recherche Opérationnelle en sigle R.O a comme objectifs :

- D’initier les étudiants de BAC+3 MP et SCAI à la modélisation et à la résolution de
problèmes du monde réel et de problèmes d’optimisation surgissant en applications
statistiques ;
- De donner aux étudiants de licence en BAC+3 MP et SCAI les bases de recherche
opérationnelle : la méthodologie, les problèmes et les modèles typiques, les principales
techniques de résolution ;
- Reconnaitre des structures concourantes des problèmes linéaires, de la programmation
dynamique, de la théorie des graphes, des problèmes stochastiques….
Aussi, ce cours est de présenter à l’étudiant d’une part de modélisation de solution
sous forme de graphe, d’autre part ce cours contiendra un ensemble de techniques permettant à
l’étudiant de résoudre ses problèmes à travers des algorithmes comme la recherche de chemin
minimal, le flot maximal, le chemin critique, les problèmes de transport, d’affectation, de
voyageur du commerce, etc.
Un étudiant maitrisant les exercices de ce cours sera capable de proposer une
modélisation d’une grande part des problèmes de recherche opérationnelle rencontrés dans la
gestion, dans le commerce, dans la finance et en informatique, de proposer des approches de
résolution et d’en discuter les qualités respectives.
VI. Plan du Cours

Chapitre 1 : INTRODUCTION A LA RECHERCHE OPERATIONNELLE

1.1. Définition
[Link] de la Recherche Opérationnelle
[Link] de la Recherche Opérationnelle
1.4.Démarche de la Recherche Opérationnelle
[Link] de problème traités par la RO
[Link] de la RO avec d’autres disciplines

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

[Link] pratique de la RO
Chapitre 2 : LA PROGRAMMATION LINEAIRE
2.1. Généralités
2.2. Définition
2.3. Formulation d’un problème linéaire
2.4. Méthodes de résolution
A. Méthode Graphique
B. Méthode Algorithme du Simplexe
c) Initiation à un logiciel d’optimisation ou Excel
2.5. Dualité d’un Programme linéaire
2.6. Exercices d’Application
Chapitre 3 : NOTIONS GENERALES SUR LES GRAPHES ET LES PROBLEMES
D’ORDONNANCEMENT D’UN PROJET
3.1. Notions Générales sur les Graphes
a) Définition
b) Premier contact avec les graphes
c) Types des Graphes
d) Niveau de Graphes
3.2. Chemins dans un Graphes
3.3. Le Problème d’optimisation dans un graphe valué
a) Problèmes du plus cours chemin dans un graphe
b) Problème du chemin de valeur maximal dans un graphe
c)Pr oblème du chemin critique dans un graphe
3.4. Les Problèmes d’Ordonnancement et Gestion de Projet
a) Notions préliminaires
b) Construction du Graphes
c) Par la Méthode Française ( Potentielle-Tâche)
d) Par la Méthode Américaine (Potentielle-Étape)
c) Recherche de Chemin(Chemin critique, Chemin de valeur maximale et chemin de
valeur minimale,….).

Chapitre 4 : LES PROBLEMES DE FLOTS DANS LES GRAPHES

4.1. Notions
4.2. Formalisation du problème de flot maximal
4.3. Détermination du flot maximal par l’algorithme de Ford et Fulkerson

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

4.4. Application aux problèmes de circulation

4.5. Problème (Exercice) d’application

Chapitre 5 : LES PROBLEMES DE TRANSPORT, D’AFFECTATION ET DE
VOYEGEUR DU COMMERCE
5.1. Généralités
5.2. Le Problème d’Affectation
5.3. Le Problème de Transport
5.4. Le Problème du Voyageur de Commerce (PVC)
Chapitre 6 : LES PROBLEMES DE GESTION DES STOCKS ET DE REMPLACEMENT
DES EQUIPEMENTS
6.1. Les Problèmes de Stocks
6.2. Les Problèmes de renouvellement et remplacement des équipements
Chapitre 7 : PROBLEMES DE FILE D’ATTENTE
7.1. Notions
7.2. Quelques Illustrations
VII. Méthodologie d’enseignements
Cours est théorique et pratique avec tableau et craies et démonstration au TN plus
les interactions des étudiants. Pour une meilleure acquisition de la matière, l’enseignant
utilisera la méthode participative et démonstrative. On partira d’étude de cas pour chaque
notion développée afin de bien illuminer la matière. Pour favoriser l’échange et la
collaboration, les étudiants seront en face à des exercices qu’ils doivent résoudre en groupe.
Toutefois, les étudiants de SCAI sont concernés uniquement par les premiers chapitres
du cours.
La langue d’enseignement est le Français.
VIII. Les Prérequis
Pour aborder la Recherche Opérationnelle (RO) efficacement, certains prérequis sont
essentiels, car la discipline combine les mathématiques, la modélisation et prise de décision. Voici
une liste détaillée :
1. Mathématiques (Algèbre linéaire, calcul différentiel et intégral ainsi que probabilités
et statistiques…) ;
2. Programmation et Informatique (Notions de base en algorithmique, logiciel de
calcul…) ;
3. Méthodes de modélisation (formulation de problème, programmation linéaire et non
linéaire ainsi que la théorie des graphes) ;

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

4. Connaissances en gestion et économie (Très utile) ;

5. Compétence analytique et esprit critique (capacité d’analyser les données et aptitude
à interpréter les résultats et proposer des solutions concrètes).
En résumé, la RO est un croisement des mathématiques appliquées, de
l’informatique et de la gestion. Sans ces bases, il est très difficile de modéliser correctement et
d’optimiser efficacement.
IX. Mode d’évaluation
Les évaluations se feront en premier lieu par des travaux dirigés, des
interrogations et des travaux pratiques. L’étudiant brillant aura droit à 1 points de plus pour
chaque intervention pertinente. La présence au cours est obligatoire et chaque présence
vaut un (1) point afin de constituer les travaux journaliers qui prendront 40 points et un
examen à notes ouvertes qui prendra à son tours 40 points.
X. Références bibliographiques
- CT Lucien Zihindula Biguru, notes de cours d’introduction à la recheche
opérationnelle, L1IG, ISIG-Goma, 2011-2012, inédit
- L. Zihindula, Notes de cours de Recherche Opérationnelle L2 Mathématiques 2007-2008,
ISP-Bukavu, inédit.
- Michel Rigo, Cours de théorie des graphes, Faculté des Sciences, Département des
Mathématiques, Université de Liège 2006-2007
- R. Faure, Précis de Recherche Opérationnelle, Dunod, Paris 1979
- Y. Norbert, La recherche opérationnelle, Gaëtan Morin, 1997
- P. Danko, Exercices et problèmes de Mathématiques supérieures, Editions Mir, Moscou
1985
- R.J. Vanderbei, Linear programming foundations and extentions, Kluwer 2001
- V.K. Balakristnan, Network optimization, Capman 1985
- CT Kyenda SULIKA, Cours d’Initiation à la Recherche Opérationnelle, G3IG, Inédit, ISP-
BKV, 2014-2015.
- Prof. Joël Mètogbé ZINSALO, Manuel du cours de la Recherche Opérationnelle,
Tome1/EPAC-UAC.
- Prof. KAMIANTAKO Miyamueni, cours de Recherche Opérationnelle, Inédit, UNDT-
Uvira, 2020-2021
- Vidal. C, la recherche opérationnelle, Que sais-je ?, PUF, 1995, 10. Maurras J. F.,
programmation linéaire, compléxité, Springer, 2002. 11. Nobert Y., Ouellet R., Parent R.,
la recherche opérationnelle, Gäetan Morin, 1995. 12. Phélizon J. F., Méthodes et modèles

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

de la recherche opérationnelle, Economica, 1998.

- Prof. MUANASAKA KABUITA Léonard, Cours de Recherche Opérationnelle et gestion
des exploitations agricoles, cours, Inédit, IFA-YANGMBI, 2016-2017.
- CT. NYONGOLO LUWAWA Martin, Cours de Séminaire informatique : Optimisation
sous Excel, Inédit, ISP-Uvira, 2016-2017.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

La clé du succès réside dans la Recherche

Opérationnelle: analyser, modéliser, décider.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

Chapitre 1 : INTRODUCTION A LA RECHERCHE OPERATIONNELLE

Dans un monde complexe et compétitif, prendre de bonnes décisions est un défi
majeur. La Recherche Opérationnelle offre des méthodes scientifiques pour analyser, modéliser
et optimiser les systèmes afin de résoudre efficacement des problèmes concrets. Qu’il s’agisse de
logistique, de production, de gestion des stocks, de télécommunication et informatique, de
l’assurance, gestion des projets, de la finance, la RO permet d’améliorer les performances, de
réduire les coûts et de mieux utiliser les ressources disponibles
1.1.Définition
[Link] est communément admis que la Recherche Opérationnelle (R.O.), en tant qu’activité
scientifique organisée, est née durant la seconde guerre mondiale. Des groupes de chercheurs
attachés à des organismes de Défense avaient alors pour tâche de donner le maximum
d’efficacité à différentes ‖opérations‖ militaires ; d’où le nom de R.O.).
La RO est une discipline carrefour où se rencontrent les économistes, les
mathématiciens et les informaticiens. On peut donc l’enseigner de manière très différente selon
que l’on veuille insister sur l’aspect économique ou bien mathématique ou encore informatique. Il
est difficile de donner une définition d’une science qui puisse satisfaire tous les pratiquants de
cette science. La définition de la R.O. n’a pas échappé à cette loi générale.
La recherche opérationnelle (aussi appelée aide à la décision) peut être définie
comme l'ensemble des méthodes et techniques rationnelles orientées vers la recherche de la
meilleure façon d'opérer des choix en vue d'aboutir au résultat visé ou au meilleur résultat
possible. Elle fait partie des «aides à la décision» dans la mesure où elle propose des modèles
conceptuels en vue d'analyser et de maitriser des situations complexes pour permettre aux
décideurs de comprendre et d'évaluer les enjeux et d'arbitrer et/ou de faire les choix les plus
efficaces. Le domaine fait largement appel au raisonnement mathématique (logique, probabilités,
analyse de données) et à la modélisation des processus. Il est fortement lié à l'ingénierie des
systèmes, ainsi qu'au management du système d'information.
En d’autres termes, la Recherche Opérationnelle transforme des problèmes réels
souvent complexes et multidimensionnels en modèles mathématiques permettant de trouver la
solution la plus rationnelle et optimale possible.
[Link] de la Recherche Opérationnelle
Au début du 20ème siècle, l’étude de la gestion des stocks peut être considérée
comme étant à l’origine de la Recherche Opérationnelle moderne avec la formule du lot
économique (dite formule de Wilson) proposée par Harris en 1913.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

Pour le grand public, la recherche opérationnelle est née vers 1940 lorsque le
physicien anglais Blackett fut appelé à présider une équipe multidisciplinaire chargée de résoudre
l’épineuse question de l’implantation optimale des radars de surveillance britanniques qui a joué
un rôle déterminant dans la bataille d’Angleterre.
L’appellation Recherche opérationnelle, tire probablement son origine des
applications aux opérations militaires de cette discipline durant la seconde guerre mondiale.
Dès la fin des hostilités, de nombreux essais furent tentés pour appliquer à l’économie
industrielle des méthodes jusqu’alors tentées par des états major alliés. D’après Robert Faure, la
recherche opérationnelle est l’ensemble des techniques rationnelles et des méthodes d’analyse et
de synthèse des phénomènes d’organisation utilisables pour élaborer les meilleures décisions.
En réalité, cette discipline date de plusieurs siècles avant la seconde guerre mondiale:
dès le 17ème siècle, Blaise Pascal et Pierre de Fermat, suivis de peu par Jacques Bernoulli et
d’autres savants cherchaient à établir des méthodes permettant les meilleurs décisions dans
l’incertain.
Vers 1776, Gaspard Monge attaquait avec succès des problèmes économiques de
nature combinatoire alors qu’Augustin Cournot s’était, vers 1838, frotté sur la théorie
mathématique des richesses devenant, de l’avis de beaucoup, le précurseur de l’économétrie.
Aux environs de 1925, Emile Borel introduisait la théorie mathématique des jeux
sous sa forme moderne tandis que quelques années avant lui, Erlang fondait la célèbre théorie des
files d’attente. Enfin, la veille de la seconde guerre mondiale, KANTOROVITCH concevait et
appliquait la programmation linéaire à la planification avant que KÖNIG ne se soit intéressé aux
graphes vers 1936.
Bien évidemment, il est impossible de dresser une liste exhaustive de tous les cadres
dans lesquels la R.O s’applique. On peut juste résumer que les techniques de la R.O s’appliquent
dans des problèmes combinatoires, les domaines de l’aléatoire ainsi que des situations de
concurrence. Chacune de ces trois catégories englobent une foule de techniques et des champs de
recherche.
Actuellement, la Recherche opérationnelle constitue une discipline très vaste et très
complexes, à cheval sur les Mathématiques, l’Économie, l’Informatique et bien d’autres
domaines.
[Link] de la Recherche Opérationnelle
Quelles sont les qualités requises de la part d’un chercheur opérationnel ? On exige de
lui avant tout un esprit scientifique, c’est-à-dire aussi bien capable de raisonner correctement par
déduction que par induction. On lui demande aussi la faculté de s’adapter pour lui permettre de

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

passer d’un problème à un autre sans perdre trop de temps. Il faut aussi, et c’est une condition
essentielle, qu’il sache se taire, garder un secret. Ceci est une condition primordiale car, de cette
aptitude dépend la confiance que l’on peut mettre dans sa personne, et des facilités de
renseignement qui lui seront accordées.
[Link] de la Recherche Opérationnelle
Le but de la Recherche Opérationnelle est d’obtenir une solution optimale (maximale
ou minimale) à un problème donné, en mettant en évidence les aspects critiques sur lesquels les
responsables portent leurs analyses et leurs jugements et en livrant des données réelles qui
permettent aux responsables d’avoir une opinion fondée.
La Recherche Opérationnelle permet donc aux responsables de décider en
connaissance de cause : elle élève le niveau où se manifeste le choix.
2.4.Démarche de la Recherche Opérationnelle
Les principales phases d’un travail de recherche opérationnelle sont les suivantes :
1) Énoncer ou définir le problème
Définir le problème implique la spécification des objectifs de l’organisation et les
parties du système qui doivent être étudiées avant de résoudre le problème. A ce stade, on
détermine ce que le projet est supposé accomplir. Pratiquement cela consiste entre autre :
- A tenir compte de toute hypothèse et commentaire des personnes ou organisations
impliquées dans ce projet ;
- A réexaminer toute notion préconçue liée au problème que l’on traite ;
- A se mettre à la place d’un opérateur et d’examiner le projet sous cet angle ;
2) Établir un modèle mathématique du problème
Le gestionnaire développe un modèle mathématique analytique ou un modèle de
simulation qui rende un ordinateur capable d’approcher le comportement du système actuel. Un
modèle exprime une ou plusieurs relations entre les différentes variables et constantes. D’un
modèle construit dépend l’efficacité d’éventuelles décisions à prendre. Un modèle peut être écrit
à l’aide d’un langage formel ou dans un langage naturel.
Exemple. Supposons que l’on se trouve devant le problème suivant :
- Formulation en langage naturel.
Une entreprise conçoit et commercialise deux produits, le premier est vendu avec un bénéfice de
10 francs l’unité, le second avec un bénéfice de 20 francs l’unité. La production étant soumise à la
contrainte suivante : La quantité journalière fabriquée ne peut dépasser 100 unités tous produits
confondus. On demande de définir un plan de production quotidien qui optimise le bénéfice de
l’entreprise. Dans cette formulation,

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

Les constantes sont 10, 20, 100 ;

Les variables sont les quantités de produits fabriquées chaque jour ;
Les relations doivent exprimer le bénéfice et le fait que les quantités produites sont
positives et ne peuvent dépasser quotidiennement 100 unités.
- Formulation dans le langage des mathématiques.
On retrouvera dans cette formulation les constantes 10, 20, 100. Mais on introduira
des noms de variable : x resp. y pour représenter les quantités de produit 1 resp. 2. D’autre part on
utilisera une fonction f représentant le bénéfice telle que f(x, y) = 10 × x + 20 × y. On utilisera
enfin une relation d’ordre pour exprimer les contraintes de production: x + y ≤ 100, 0 ≤ x, 0 ≤ y.
Finalement on arrive à la formulation mathématique suivante : Maximiser f(x, y) = 10 × x + 20 ×
y, tel que x + y ≤ 100, 0 ≤ x, 0 ≤ y.
3) Envisager une solution à partir du modèle
Deux méthodes peuvent permettre au gestionnaire de déduire une solution optimale
(ou presque optimale) d’un modèle à savoir la méthode analytique et la méthode numérique. La
première fait intervenir la déduction mathématique. La seconde consiste essentiellement à essayer
plusieurs valeurs de variables du modèle avant de choisir celle qui donne la meilleure solution ;
4) Mettre à l’épreuve le modèle et la solution qui en découle (validation du modèle)
L’analyste doit maintenant vérifier si le modèle proposé à l’étape 2 est une bonne
représentation de la réalité. On teste à partir de jeux de données judicieusement choisies, le
modèle et les solutions retenues. Un des critères est de minimiser l’écart entre les variables
observées et les variables estimées.
5) Elaborer des moyens de vérifier la solution
Une solution à un modèle ne reste valable qu’aussi longtemps que les relations entre
les différentes variables du modèle restent constantes. Sinon elle échappe au contrôle. L’analyste
devra donc prévoir des mécanismes de contrôle ;
6) Mettre la solution en pratique
La solution proposée doit pouvoir être transposée dans d’autres situations semblables.
[Link] de la RO avec d’autres disciplines
La RO est une discipline carrefour où se rencontrent les économistes, les
mathématiciens et les informaticiens. On peut donc l’enseigner de manière très différente selon
que l’on veuille insister sur l’aspect économique ou bien mathématique ou encore informatique.
Par exemple, l'analyse économique est souvent nécessaire pour définir l'objectif à
atteindre ou pour identifier les contraintes d'un problème. Elle est aussi liée à l'ingénierie des
systèmes. Par rapport à celle-ci, le champ d'application de la recherche opérationnelle est

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

historiquement plus axé sur les événements incertains et l'industrie, et ses méthodes plus
particulièrement mathématiques. La recherche opérationnelle utilise de nombreuses méthodes
issues de théories mathématiques diverses. En ce sens, une partie de la recherche opérationnelle
peut être considérée comme une branche des mathématiques appliquées. Les mathématiques,
notamment les statistiques, contribuent aussi à poser efficacement les termes d'un problème. La
théorie des graphes sert de support à la résolution d'un vaste échantillon de problèmes, notamment
certains issus de l'algorithmique classique, tels que les problèmes de plus court chemin, le
problème du voyageur de commerce, les problèmes d'ordonnancement de tâches, les problèmes de
planning ou encore les problèmes d'optimisation de flux.
Les progrès de l'informatique sont intimement liés à l'accroissement des applications
de la recherche opérationnelle. Une puissance de calcul importante est nécessaire à la résolution
de problèmes de grande taille. Cette puissance est cependant loin de constituer une panacée : la
théorie de la complexité des algorithmes nous apprend que certains problèmes ne peuvent pas être
résolus de manière optimale dans un temps raisonnable, même si l'on considère des ordinateurs un
milliard de fois plus puissants que ceux d'aujourd'hui.
Actuellement, la Recherche opérationnelle constitue une discipline très vaste et
très complexes, à cheval sur les Mathématiques, l’Economie, l’Informatique et bien d’autres
domaines.
2.6. Application pratique de la RO
Les domaines d’intervention de la R.O. sont très divers (social, ´économique, militaire
...). En tant que science, la R.O. interagit avec d’autres activités scientifiques comme les
mathématiques ou l’informatique, qu’elle utilise et qu’elle enrichit aussi. Cependant un emploi
sans discernement de la R.O. en tant qu’aide à la décision d’opérateurs, peut conduire dans
certaines situations à des erreurs. Ces erreurs sont souvent conséquentes à un mauvais emploi de
techniques issues de la R.O. ou à l’inadaptation de ces techniques par rapport à la réalité d’un
problème L’idée à retenir est que la Recherche Opérationnelle ne s’occupe pas de problèmes dans
lesquels une solution de bons sens intervient tout naturellement. Elle concerne des situations dans
lesquelles, pour une raison quelconque, le bon sens humain se révèle faible ou impuissant. Ces
problèmes types sont regroupés en trois grandes catégories, à savoir :
2.6.1. Les problèmes combinatoires
Un problème est dit combinatoire lorsqu'il comprend un grand nombre de solutions
admissibles parmi lesquelles on cherche une solution optimale ouproche de l'optimum.
Il s’agit de problèmes pour lesquels il existe plusieurs solutions qu’il est impossible
d’énumérer toutes. Dans ce cas, l’utilisation d’un algorithme judicieux permet d’aller très
rapidement à la solution optimale. Les principaux exemples sont :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

- Les problèmes d’investissement où il est question de rechercher les investissements

les plus rentables dans un projet déterminé ;
- Les problèmes de production qui consistent à optimiser les niveaux d’activité en
tenant compte des ressources qui sont limitées ;
- Les problèmes d’affectation : sachant qu’un agent ou une machine ne peut être
affectée qu’à une tâche et une tâche à un ouvrier ou une machine, comment répartir les
travaux de façon à rendre minimum le coût d’affectation ?
- Les programmes de transport qui consistent à organiser le transport entre les
points de départ et les points d’arrivée de manière la moins coûteuse possible ;
- Les problèmes de circulation à travers un réseau (problème du voyageur de
commerce, problème de flot maximal, problème de chemin optimal, …) ;
- Les problèmes d’ordonnancement : il s’agit ici de planifier dans le temps un
ensemble d’opérations ou tâches contribuant à la réalisation d’un même projet ainsi que de
déterminer la durée optimale de réalisation de ce projet ;
2.6.2. Les problèmes stochastiques ou aléatoire
Ce sont des problèmes dans lesquels le hasard joue un rôle important. Nous mentionnons:
Les problèmes de file d’attente qui consistent à organiser les arrivées ou à
déterminer la quantité ou l’organisation des guichets qui minimise la somme des
coûts d’attente des clients (sujets attendant d’être servis) et des serveurs ;
Les problèmes de stocks où il est question de répondre d’une façon optimale à
l’une ou l’autre des questions suivantes : Combien (quelle quantité) et quand
faut-il commander ?
Les problèmes de réparation et de renouvellement des équipements : ils
consistent, pour les matériels qui se détériorent, à prévoir le moment du
remplacement de façon à minimiser la somme des éléments suivants : - Coût du
nouveau matériel ; - Coût du maintien du rendement de l’ancien matériel ; -
Coût de la perte de rendement.
Pour les matériels sujets à des pannes, les problèmes consistent à déterminer les
pièces à remplacer et selon quelle fréquence, de façon à minimiser la somme des
éléments suivants : - coût du matériel considéré ; - coût du remplacement des
pièces ; - coût de la panne.
2.6.3. Les problèmes concurrentiels
Les problèmes de concurrence sont ceux dans lesquels les conséquences de la

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

décision de l’une des parties risquent d’être amenuisées du fait de la décision de l’autre partie.
Parmi les exemples, on peut citer la définition de politiques d’approvisionnement, de vente, etc.,
domaine de la théorie des jeux. Ces trois grandes catégories constituent les trois parties principales
de notre cours de R.O.
[Link] informatique
L’informatique apporte des solutions pour des problèmes de la Recherche
Opérationnelle. Les applications ont été mises à la disposition du publique. On peut citer : Ms
Excel, Lotus-1-2-3, Or Simplex, Linear Programmation, Ms Project, Gantt (pour
l’ordonnancement),… Parmi ces solutions informatiques, certaines sont gratuits et d’autres
payants.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

Chapitre 2 : LA PROGRAMMATION LINEAIRE

2.1. Généralités

À partir de la fin de la Seconde Guerre mondiale, de nouvelles méthodes permirent

de résoudre des problèmes complexes là où les méthodes classiques échouaient. Ces méthodes
furent connues sous le nom de programmation linéaire, développées principalement par George
B. Dantzig (né le 8 novembre 1914), mathématicien américain et créateur de la méthode du
Simplexe, et L. Kantorovich (1912-1986). Danzig, outre la programmation linéaire, étudia entre
autres la programmation mathématique, la prise de décision et les modèles de planification à large
échelle. L’impact de son œuvre fut considérable en gestion et en économie et ses méthodes
restent totalement d’actualité.

De manière générale, la résolution de problèmes de programmation mathématique

vise à déterminer l’allocation optimale (c’est-à-dire la meilleure combinaison possible) de
ressources limitées pour atteindre certains objectifs. Les allocations doivent minimiser ou
maximiser une fonction dite objectif. En économie, ces fonctions sont par exemple le profit ou le
coût. Ces problèmes, traités par la programmation mathématique, se distinguent des problèmes
d’optimisation classique par le fait que leurs solutions sont d’ordre numérique. Celles-ci sont
obtenues par une technique numérique itérative, alors que les solutions à un problème classique
sont en général données sous forme de formules fermées.
2.2. Définition
On appelle Programmation Linéaire (PL), 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. Les problèmes de programmations linéaires sont
généralement liés à des problèmes d’allocations de ressources limitées, de la meilleure façon
possible, afin de maximiser un profit oude minimiser un coût. Le terme meilleur fait référence à la
possibilité d’avoir un ensemble de décisions possibles qui réalisent la même satisfaction ou le
même profit. Ces décisions sont en général le résultat d’un problème mathématique. La
programmation linéaire est définie donc comme étant un cas particulier de la programmation
mathématique pour laquelle la fonction objectif et les contraintes sont linéaires.
2.3. Formulation d’un problème linéaire
Pour formuler un Programme Linéaire, il est obligatoire de suivre les conditions et étapes
suivantes :
2.3.1. Condition de formulation d’un PL
La programmation linéaire comme étant un modèle admet des hypothèses (des
conditions) que le décideur doit valider avant de pouvoir les utiliser pour modéliser son problème.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

Ces hypothèses sont1 :

1) Les variables de décision du problème sont positives ;
2) Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces
variables, c’est à dire, que la fonction ne peut pas contenir par exemple un produit croisé
de deux de ces variables. La fonction qui représente le critère de sélection est dite fonction
objectif (ou fonction économique) ;
3) Les restrictions relatives aux variables de décision (exemple: limitations des ressources)
peuvent être exprimées par un ensemble d’équations linéaires. Ces équations forment
l’ensemble des contraintes ;
4) Les paramètres du problème en dehors des variables de décisions ont une valeur connue
avec certitude.
2.3.2. Étapes de formulation d’un PL
Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d'un
programme linéaire :

1) Identifier les variables du problème à valeur non connues (variable de décision) et les
représenter sous forme symbolique (exp. x1, y1 ) ;
2) Identifier les restrictions (les contraintes) du problème et les exprimer par un système
d’équations linéaires ;
3) Identifier l’objectif ou le critère de sélection et le représenter sous une forme linéaire en
fonction des variables de décision. Spécifier si le critère de sélection est à maximiser ou à
minimiser.
2.4. Méthodes de résolution
Il existe généralement deux (2) méthodes de résolution d’un Programme Linéaire.
Exemples introductifs

1) Une usine fabrique 2 pièces A et B usinées dans deux ateliers et . Les temps d'usinage
sont pour A: de 3 heures dans l'atelier et de 6 heures dans l'atelier pour B: de 4 heures
dans l'atelier et de 3 heures dans l'atelier . Le temps de disponibilité hebdomadaire de
l'atelier est de 160 heures et celui de l'atelier de 180 heures. La marge bénéficiaire est
de 1200 F pour une pièce A et 1000 F pour une pièce B. Quelle production de chaque
type doit-on fabriquer pour maximiser la margehebdomadaire ?
Le problème peut se formaliser de la façon suivante : variables économiques ou
d'activités ce sont les inconnues :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

- x = quantité de pièces A à fabriquer,

- y = quantité de pièces B à fabriquer

2) Un spécialiste en médecine a fabriqué un médicament (des pilules) pour guérir les sujets
atteints d’un rhume. Ces pilules sont fabriquées selon deux formats :

 Petite taille : elle contient 2 grains d’aspirine, 5 grains de bicarbonate

et 1grain de codéine.

 Grande taille : elle contient 1 grain d’aspirine, 8 grains de bicarbonate et 6

grains de codéine.
Pour guérir la maladie, le sujet a besoin de 12 grains d’aspirine, 74 grains de bicarbonate et
24 grains de codéine. Déterminer le nombre de pilules minimales à prescrire au sujet pour
qu’il soit guérit.

Formulation du problème en un PL :

Le problème de médecine présente certaines ressemblances avec le problème de

l’agriculture, dans les deux cas c’est un problème d’allocation de ressources.
Les variables de décision qui représentent des valeurs inconnues par le décideur qui
est dans ce cas le spécialiste en médecine sont :

 x1 : le nombre de pilules de petite taille à prescrire.

 x2 : le nombre de pilules de grande taille à prescrire.
On vérifie bien que les variables de décision x1 et x2 sont positives : x1 et x2
Les contraintes imposées par le problème sur les valeurs possibles de x1 et x2 sont :

 La prescription doit contenir des pilules avec au moins 12 grains d’aspirine.

Sachant qu’une petite pilule contient 2 grains d’aspirine et qu’une grande
pilule contient un seul grain d’aspirine, on obtient la contrainte suivante
:2x1  x2  12 .
 De la même façon que pour l’aspirine, la prescription du spécialiste en

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

médecine doit contenir au moins 74 grains de bicarbonate. Ainsi la contrainte

suivante doit être satisfaite : 5x1  8x2  74 .

 Finalement la contrainte imposée par le fait que la prescription doit

contenir au moins 24 grains de codéine est x1  6x2  24

Etape 3 : Identification de la fonction objectif.

On remarque qu’il y a plusieurs couples de solutions (x1 , x2 ) qui peuvent
satisfaire les contraintes spécifiées à l’étape 2. La prescription doit contenir le minimum
possible de pilules. Donc lecritère de sélection de la quantité de pilules à prescrire est celle qui
minimise le nombre total des pilules z= x1  x2.
Le programme linéaire qui modélise ce problème médical est donc le suivant :

2.4.1. Méthode Graphique

a) Notions

Cette méthode n'est applicable que dans le cas où il n'y a que deux variables. Son
avantage est de pouvoir comprendre ce que fait la méthode générale du Simplexe, sans entrer dans
la technique purement mathématique.

Les contraintes économiques et de signe sont représentées graphiquement par des

demi-plans dont l'intersection est un ensemble convexe (c.à.d. tout segment de droite dont les
extrémités appartiennent à l'ensemble est entièrement inclus dans cet ensemble). Les solutions, si
elles existent appartiennent donc à cet ensemble appelé région des solutions admissibles.
b) Application des méthodes
Exemple 1 :
Soit la fonction objectif ou économique ci-après :Max z(x,y)= 1200x+1000y sous

contraintes :{

Ces premières contraintes peuvent être représentées dans par le graphique en

considérant simultanément toutes les quatre contraintes on obtient l’ensemble de solutions

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

admissibles représenté par la figure en posant simultanément (x= 0 et y =0) :

On résout le système de contraintes soit par la méthode d’addition, de

comparaison, de cramer ou de substitution. Le point d’intersection entre ces deux droites est
P(x, y) = (16, 28). A ce point correspond un bénéfice de: P(16,28) = 1200*16+1000*28 =
47200.
2.4.2. Méthode Algorithme du Simplexe
Ce point est consacré à l’étude de la méthode du simplexe. Cette méthode est
l’outil principal de résolution des problèmes de programmation linéaire. Elle consiste à suivre
un certain nombre d’étapes avant d’obtenir la solution d’un problème donné. Il s’agit
d’une méthode algébrique itérative qui permet de trouver la solution exacte d’un problème de
programmation linéaire en un nombre fini d’étapes.
La résolution graphique est inapplicable au-delà de deux variables. Il est aussi
nécessaire de recourir à une autre méthode : la méthode du simplexe dite également méthode
des tableaux ou méthode de Dantzig. Cette méthode, applicable quelque soit le nombre de
variables, sera présentée pour des problèmes de maximisation dont toutes les contraintes
(autres que celles de positivité) sontde type ≤.
a) Définition
On peut définir un algorithme comme étant un ensemble de règles ou une
procédure systématique permettant de trouver la solution à un problème donné. Pour ce qui est

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

de l’algorithme du simplex, il s’agit d’une méthode (ou d’une procédure de calcul)

permettant de déterminer les solutions de base accessibles d’un système d’équations et de
vérifier si les solutions sont optimales. Le simplex passe d’une solution de base à une autre,
toujours meilleure que la précédente, jusqu’à ce que la solution optimale soit atteinte.
Comme nous l’avons souligné plus haut, le problème général consiste à
optimiser la fonction économique sous une série des contraintes :

b) Mise sous forme standard

La mise sous forme standard consiste à introduire des variables supplémentaires
(une pour chaque contrainte) de manière à réécrire les inégalités (  ) sous la forme d'égalités.
Chacune de ces variables représente le nombre de ressources non utilisés. On les appelle
variable d'écart.

Illustration Maximiser le profit sous les contraintes :

Sous forme standard, les contraintes se présenterons comme suit :

c) Forme simpliciale : Un programme est dit sous forme simpliciale si :

- elle est sous forme standard
- et les constantes du second membre sont toutes positives.
Le programme doit être mis sous forme simpliciale avant l'utilisation de l'algorithme de simplexe.
d) Résolution

Afin de comparer avec la résolution graphique, nous pouvons considérer que nous

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

sommes dans un espace à n dimensions (nombre de variables d'activité). Les contraintes

délimitent un polyèdre convexe, région des solutions admissibles; la fonction objectif est un
hyperplan que l'on va déplacer le plus loin possible de l'origine, jusqu'à l'extrême limite où il n'y
aura plus qu'un point d'intersection (éventuellement un segment, un plan...) avec la région
des solutions admissibles. La solution se trouvant forcément sur le pourtour du polyèdre
admissible, la méthode du simplexe consiste en itérations qui font passer d'un sommet du
polyèdre à un autre en sélectionnant le sommet adjacent maximisant la fonction objectif. Pour
démarrer l'algorithme, il est nécessaire d'avoir une solution initiale. Dans le cas simple, l'origine
est solution, c.à.d. que la première solution est x1  0 ; x2  0 ; .........; xn  0 ; t1  b1 ; t2  b2 ;
.........; tm  bm (ceci suppose que les bi ne soient pas négatifs pour satisfaire les contraintes de signe).
L'algorithme, basé sur la méthode du pivot de Gauss pour la résolution des systèmes
d'équations linéaires, est présenté sous forme de tableau.

Solution :
1) On transforme les inéquations en équations en ajoutant à chacune des équations
une variable d’écart :

2) On exprime le système obtenu sous forme matricielle :

3) On établit alors le tableau initial du simplex qui se compose de la matrice des

coefficients des contraintes, du vecteur colonne des constantes et d’une ligne
d’indicateurs située sous la précédente, qui contient les coefficients de la fonction
objectif (fonction économique) précédés du signe moins et d’un coefficient nul pour
chaque variable d’écart. La case située sur la dernière ligne de la colonne des constantes
est aussi un zéro, qui représente la valeur que prend la fonction objectif à l’origine
(lorsque ).
a) Le tableau initial du simplex

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 Recherche Opérationnelle BAC+3 MP et SCAI

b) On peut lire directement sur le tableau initial la première solution de base

accessible : en posant on obtient
. Dans cette première solution
de base accessible, la fonction objectif a une valeur nulle.
1) Le pivot et les changements de base
Pour accroitre la valeur de la fonction objectif, on examine une nouvelle solution de
base. Pour l’obtenir, on doit introduire une nouvelle variable dans la base et exclure une des
variables qui y figuraient précédemment.

Par changement de base on entend le processus qui consiste à choisir la variable à

insérer et la variable à exclure :
a. L’indicateur négatif dont la valeur absolue est la plus élevée détermine la
variable à entrer dans la base. Comme pour ce cas l’indicateur négatif de plus
forte valeur absolue est égal à 5 et se situe dans la première colonne (celle de ),
on introduit dans la base. La colonne devient donc la colonne pivot.
b. La variable à éliminer est déterminée par le plus petit ratio de
déplacement. On trouve les ratios déplacement en divisant les éléments de la colonne
des constantes par les éléments de la colonne pivot. La ligne pour laquelle le ratio
de déplacement est la plus faible (ligne pivot), les ratios inférieurs ou égaux à
zéro étant ignorés, détermine la variable à éliminer de la base.

Comme alors la ligne 1 est la ligne pivot. Comme le vecteur unitaire

portant 1 dans la première ligne apparaît dans la colonne de s1, on sort s1 de la base. Le pivot
est 6 et se situe à l’intersection de la colonne de la variable entrant dans la base et de la ligne
associée à la variable qui quitte la base.
3)Pivotage

C’est en bref le processus permettant de résoudre les m équations pour les m

variables figurant « maintenant » dans la base. Comme c’est une seule nouvelle variable qui est
admise dans la base à chaque étape de la procédure et comme l’étape précédente implique

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

toujours une matrice identité, le pivotage consiste concrètement à transformer le pivot en 1 et

à rendre nuls tous les autres éléments de la colonne pivot comme on le fait dans la méthode
d’élimination de Gauss (cfr résolution des systèmes linéaires, cours de Maths générales en G1).

- On multiplie la ligne pivot par l’inverse du pivot (ici ) :

- Une fois le pivot égalé à 1, il faut maintenant annuler tous les autres éléments de la colonne
pivot : Dans ce cas, il faut (naturellement) soustraire 5 fois la première ligne de la
deuxième ligne, 2 fois la première ligne de la troisième ligne et ajouter 5 fois la
première ligne à la quatrième. On obtient alors le deuxième tableau :
Deuxième tableau :

On peut lire directement sur ce tableau la deuxième solution de base accessible : en

posant et nous conservons une matrice identité qui donne :
et . Le dernier élément de la dernière ligne (ici 30) donne la
valeur de la fonction objectif dans la deuxième solution accessible.
4) Optimisation :
La fonction objectif ne sera maximisée que lorsqu’il n’y aura plus d’indicateurs
négatifs dans la dernière ligne: on poursuit donc les changements de base et les pivotages,
conformément aux règles exposées ci-dessus, jusqu’à ce qu’on y parvienne.

Comme il ne reste plus comme indicateur négatif que qui est dans la deuxième
colonne on introduit dans la base : la deuxième colonne devient la colonne pivot. La division
de la colonne des constantes par la colonne pivot révèle que le plus faible ratio de
déplacement se situe dans la deuxième ligne :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

Dans ce cas devient le nouveau pivot. Comme le vecteur unitaire portant 1 sur la
deuxième ligne est situé sous s2 c’est s2 alors qui est exclu de la base.

- Pour le pivotage : Multiplions la deuxième ligne par et nous obtenons :

- Soustrayons (naturellement) le tiers de la deuxième ligne de la première ligne, le de la

deuxième ligne de la troisième et ajoutons le de la deuxième ligne à la quatrième. Nous

obtenons alors le troisième tableau :

On peut lire directement sur ce tableau la troisième solution de base accessible : quand
et et . Comme il n’ y a plus d’indicateurs négatifs sur
la dernière ligne, c’est la solution optimale. Le dernier élément de la dernière ligne indique que,
lorsque et , la fonction objectif atteint un maximum tel que
, . Comme s1 et s2, alors les variables d’écart sont
nulles dans les deux premières contraintes et il en résulte que les deux premiers facteurs de
production sont utilisés à plein. Par contre comme alors six unités du troisième facteur de
production restent inutilisés !
La valeur de l’indicateur situé sous chaque variable d’écart dans le tableau final exprime la
valeur marginale, ou prix fictif, du facteur de production associé à la variable, c’est-à-dire qu’il
révèle de combien changerait la valeur de la fonction objectif si le facteur de production
augmentait d’une unité.
Ainsi, on peut dire que les profits s’accroîtraient d’une demi-unité, ou de 50 centimes, si la

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

constante de la contrainte 1 était augmentée d’une unité, de 2/5 ou de 40 centimes, si la constante

de la contrainte 2 était augmentée d’une unité ; et de 0 si la constante de la contrainte 3 était
majorée d’une unité.
Comme la variable d’écart est positive dans la contrainte 3, le troisième facteur de
production n’est pas totalement utilisé dans la solution optimale et sa valeur marginale est nulle
(c’est-à-dire que l’apport d’une nouvelle unité n’augmenterait en rien la fonction des profits).
Remarquons en passant que la valeur optimale de la fonction objectif sera toujours égale à la
somme des produits de la valeur marginale de chaque facteur de production par la quantité

disponible de ce facteur :
Retrouver graphiquement cette solution représentant l’ensemble de solutions
admissibles on a :

Sur ce graphique il est évident que les sommets du polygone des solutions
admissibles sont : .
En calculant la fonction objectif : ( ) 3x1+5x2 sur chacun de ces
sommets on obtient :
Il est donc évident que prend sa valeur maximale au point (5,3).

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 Recherche Opérationnelle BAC+3 MP et SCAI

2.4.3. Résumé de la procédure de la méthode du simplexe (dans le cas d'un problème de

maximisation sous contraintes  et avec un second membre positif).

Etapes Justification
1. Formuler un programme linéaire pour le Pour obtenir une représentation mathématique du
problème réel. problème
2. Vérifier que le second membre du programme Ceci est nécessaire pour obtenir comme variable de
linéaire est positif base initiale l’origine
3. Ecrire le programme linéaire sous une forme Mettre toutes les contraintes sous forme d’égalité
standard
4. Construire le premier tableau de simplexe Ce tableau correspond à la solution initiale de base
5. Choisir comme variable entrante dans la base La valeur de cj-zj indique la quantité d’augmentation
celle qui admet le plus grand effet net positif cj-zj. de la fonction objectif si on augmente la valeur de xj
d’une unité.
6. Choisir la variable sortante de la base celle qui La plus petite valeur de Qi/aij indique le nombre
admet le plus petit ratio supérieur à zéro. maximal d’unité de xj qu’on peut introduire avant que
la variable de base de l’ième ligne ne soit égale à zéro.
7. Construire le nouveau tableau en utilisant la Cette règle nous permet entre autre de calculer les
règle de pivot valeurs des nouvelles variables de décision
8. Faire le test d’optimalité. Si Si (cj-zj)  0 alors on n’a pas d’intérêt à faire entrer
(cj-zj)  0 pour toutes les variables (hors base), la dans la base aucune de ces variables. Une telle
solution obtenue est donc optimale. Sinon introduction engendra une diminution de la fonction
retourner à l’étape 5. objectif.

2.5. Dualité d’un Programme linéaire

2.5.1. Notions
La notion de dualité a été introduite par Von Neumann en 1947, puis développée par
Gale, Kuhn et Tucker en 1951. Les propriétés fondamentales des problèmes de dualité ont été
définies par Goldman and Tucker en 1956. A tout programme linéaire appelé PRIMAL
correspond un programme linéaire appelé DUAL obtenu de la manière suivante :

PRIMAL DUAL
m contraintes d'infériorité n contraintes de supériorité
n variables d'activité n variables d'écart
m variables d'écart m variables d'activité
écriture en ligne écriture en colonne

2.5.2. Principes de base

- La dualité permet de résoudre les problèmes de minimisation dont les contraintes

(autres quecelles de positivité des signes) sont de sens .

- Le nombre de variables du dual est égal au nombre de contraintes du primal. Elles

doivent êtredifférenciées de celles du primal.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

- Le nombre de contraintes du dual est égal au nombre de variables du primal.

- Les coefficients des colonnes (lignes) du primal sont les coefficients des lignes
(colonnes) dudual.

- Les inégalités du dual sont de sens opposé à celles du primal.

- Les coefficients de la fonction économique du primal sont les contraintes du dual.

- Si le primal est une minimisation, le dual est une maximisation et inversement.

- Les coefficients de la fonction économique du dual sont les contraintes du primal.

- Le dual du dual est le primal.

- Un programme linéaire possède une solution optimale finie si et seulement si lui

et son dualpossèdent des solutions réalisables.

- Si le problème primal possède une solution optimale infinie, alors le dual n’a
pas de solutionréalisable.

- Si le dual ne possède pas de solution réalisable, alors que le primal en possède,

alors la solutiondu primal est une solution optimale infinie.

- Une contrainte est dite saturée lorsque la variable d'écart qui lui est associée
est nulle à l'optimum. Si pour une solution optimale d'un programme linéaire une
contrainte n'est pas saturée, alors la valeur optimale (duale) correspondante est
nulle. La réciproque n'est pas (nécessairement) vraie.

- Si la valeur optimale d'une variable n'est pas nulle, alors la contrainte duale
correspondante est saturée pour la solution optimale. Le corollaire est très utile
pour résoudre un programme à partir de la solution de son dual.

- Si pour une solution optimale d'un programme linéaire une contrainte n'est pas
saturée, alors la valeur optimale (duale) correspondante est nulle. En terme
économique, par exemple, si un bien est abondant (il n'y en a plus qu'on ne peut
utiliser efficacement), son coût marginal (une heure de location supplémentaire)
considéré comme son prix d'équilibre (la variable duale associée)est nul.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

Exemple

PRIMAL DUAL
3 x1 + 4 x2  160 3 y1 + 6 y2  
6 x1 + 3 x2  180 4 y1 + 3 y2  
Min w = 160 y1 + 80 y2
Max z = 1200 x1 + 1000 x2
y1  0 ; y2  0
x1  0 ; x2  0

A l'optimum, le primal et le dual sont liés par

les règles suivantes :
- les fonctions objectifs z et w ont la même
valeur optimale
- la valeur marginale d'une variable dans un programme est égale à
l'opposé de la valeur optimale de la variable associée dans l'autre programme
et réciproquement.
2.5.3. Exemple Introductif

Trouver le dual de chacun des problèmes suivants :

a) Maximiser sous les contraintes contraintes

Solution : Son dual est : Minimiser sous les

b) Minimiser sous les contraintes

Solution : Le problème dual correspondant est :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

Maximiser sous les contraintes

RMQ : le dual du dual est le primal.
On démontre les résultats suivants, qui jouent un rôle central dans la résolution des
problèmes de programmation linéaire :

R1 : La valeur optimale de la fonction objectif du primal est toujours égale à la valeur

optimale de la fonction objectif du dual, dès lors qu’une solution optimale accessible
existe.
R2 : Si dans la solution optimale accessible,
i) une variable de décision du programme primal a une valeur autre que zéro, la
variable d’écart correspondante du programme dual a nécessairement une
valeur optimale égale à zéro ;
ii) une variable d’écart du primal a une valeur autre que zéro, la variable de
décision correspondante du programme dual a nécessairement une valeur
optimale égale à zéro.

Illustration :
Minimiser sous les contraintes

Solution : Le dual s’écrit de ce problème consiste à maximiser

sous les contraintes

En résolvant, d’après la méthode du simplexe le programme dual on commence par introduire les
variables d’écart pour avoir :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

Sous forme matricielle, ce système s’écrit :

Le tableau initial du simplex devient alors :

En divisant la ligne du pivot par le pivot on obtient :

Au vu des coefficients des autres lignes sur la colonne pivot, les opérations naturelles :
s’imposent sur toutes les
lignes et donnent :

En divisant la ligne pivot par le pivot on obtient :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
Recherche Opérationnelle BAC+3 MP et SCAI

Les opérations naturelles :

donnent finalement :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 32
Recherche Opérationnelle BAC+3 MP et SCAI

Comme tous les indicateurs sont non négatifs, alors il suffit de poser

pour obtenir la solution optimale correspondant à et

.
Il résulte du premier résultat sur le programme dual que pour ce primal la valeur maximale de
est .

Cherchons présentement les valeurs des variables de décision correspondant à

cette solution optimale .

Pour la solution optimale du dual nous avons trouvé pour ses variables

d’écart les valeurs .

En utilisant les résultats relatifs au dual ci-dessous nous avons les déductions suivantes :
- Comme la variable d’écart du dual , il en résulte que la variable de
décision correspondante du primal, est nécessairement égal à zéro.
- Comme les deux dernières variables d’écart du dual sont nulles (
), il en résulte que les variables de décision
correspondantes du primal sont non nulles : .
- Puisque les valeurs optimale des variables de décision du dual

sont différentes de zéro, il en résulte que les variables d’écart

correspondantes du primal sont nécessairement nulles.

En bref, la résolution complète du dual nous donne les renseignements suivants
sur le primal : la valeur optimale de la première variable de décision du primal (x1) ainsi
que les valeurs optimales respectives de deux premières variables d’écart du primal (s1
et s2)sont nulles :
.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 33
Recherche Opérationnelle BAC+3 MP et SCAI

Les contraintes du primales deviennent alors :

La résolution de ce dernier (petit) système donne : et en définitive

on conclut que le programme primal admet la solution optimale

Nb : Avec la technologie de l’informatique, il y a des logiciels informatiques permettant

de trouver des solutions de maximisation ou de minimisation en PL. Exemple : MS
Excel, OR Simplex,….
2.6. Résolution des programmes linéaires
Les programmes linéaires se résolvent avec plusieurs méthodes faisant recours aux
mathématiques. Leur application devient fastidieuse voire très difficile lorsqu’on se retrouve en
face d’un modèle avec plusieurs variables et plusieurs contraintes (20 et 50 par exemple).
Dans ce cas, l’utilisation de l’informatique devient obligatoire pour assouplir la tâche. Sur le
marché, il existe des logiciels conçus pour la cause. Toutefois, le tableur Excel dispose d’un
solveur à même de le faire sans beaucoup de technicités, bien entendu, après avoir organisé les
données dans une feuille de calcul.
Il importe de souligner que, de fois, la commande solveur n’est pas immédiatement
disponible dans les menus (Office 2010) ou à travers les onglets (office 2007). Pour l’activer,
sous Office 2007, à l’aide du ruban office ( ) ou du menu fichier (version d’office
postérieur à 2007), cliquer sur Options Excel comme l’indique sur l’image ci-dessous :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 34
Recherche Opérationnelle BAC+3 MP et SCAI

Dans la boîte de dialogue qui s’affiche, cliquer sur la commande Compléments de

la partie gauche de cette boîte, sélectionner en suite Complément Solver puis sur le bouton
Atteindre comme l’illustre l’image ci-dessous :

Cette action vous amène une autre boîte de dialogue dans laquelle, vous êtes invité
de cocher Complément Solver puis cliquer sur ok pour que cette commande fait partie
intégrante de l’onglet données.

Etudions alors la préparation des données et la résolution d’un programme linéaire

par voie de tableur à l’aide d’un programme linéaire à maximiser qui se présente ci-dessous :
Soit à maximiser le programme linéaire ci-dessous :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 35
Recherche Opérationnelle BAC+3 MP et SCAI

Voici la démarche à suivre pour le résoudre à l’aide d’EXCEL Il y a trois principales

parties à fournir au solveur d’Excel.
- La cellule à maximiser/minimiser ,
- La plage de variables de décision (x1, x2),
- Les contraintes.
Pour le faire, il faudra procéder par l’introduction du modèle dans une feuille de
calcul. Nous basant de notre exemple :
1) La première ligne va reprendre les intitulés des variables de base ici, la cellule A1
contiendra l’intitulé, variables, la cellule B1, la première variable de décision (X1) et la
cellule C1 la deuxième variable de décision (X2). La deuxième ligne est celle réservée à
contenir alors les quantités optimales à calculer. Elles doivent pour le moment être
laissées vides car elles seront remplies automatiquement à l’aide du solveur. Dans A1,
on pourra inscrire l’intitulé « valeurs recherchées », B2 et C2 sont alors laissées vides
pour attendre les valeurs que le solveur calculera en fonction des contraintes du modèle.
2) La troisième ligne est dédiée aux contraintes du modèle. Ainsi, la cellule A3 aura
Contraintes comme intitulé, la cellule B3, la variable X1, la cellule C3, la variable X2, la
cellule D3, le calcul de la valeur de la contrainte et la cellule E4, la quantité des
ressources disponibles (le second membre des inégalités).
3) Ensuite, vers la ligne 7, en respectant les colonnes des variables X1 et X2, reprendre les
coefficients de ces variables dans la fonction économique. Ainsi, la cellule A7
contiendra l’intitulé « fonction économique », la cellule B7, le coefficient de la variable
X1 (66) et C7 (84), le coefficient de la variable X2. En dessous, à la huitième ligne, la
cellule du calcul du profit comme c’est un problème de maximisation (elle sera du coût
lors d’un problème à minimisation). Pour ce faire, la cellule A8 contient l’intitulé Profit.
La cellule B8 jusque-là doit être laissée et contiendra la formule pour le calcul
automatique du profit.
Voici, ci-dessous, l’image qui illustre cela dans une feuille de calcul :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 36
Recherche Opérationnelle BAC+3 MP et SCAI

4) Comme vous pouvez le constater sur cette image, la colonne D est restée vide jusque là.
L’ordinateur ne pouvant pas comprendre les variables et les contraintes, il est nécessaire
de lui fournir les données numériques pour qu’il agisse. Ainsi, cette colonne recevra le
calcul des valeurs de contraintes à même de vérifier les inéquations. Pour ce faire, au
niveau de D4, première contrainte du programme linéaire à résoudre : 3x1 + 4x2≤4200,
B2 devant contenir la valeur optimale de X1 et C2, la valeur optimale de la variable X2,
la cellule D4 sera alors la multiplication du contenu de B2 par B4 lequel produit sera
ajouté du produit C2 et C4. En Excel, il faudra, dans la cellule D4, introduire le signe
d’égalité (=) puis cliquer sur B2 puis saisir le signe de multiplication à l’aide du clavier
(*) et puis cliquer sur B4, mettre le signe d’addition (+) ensuite cliquer sur C2 puis saisir
le signe de multiplication à l’aide du clavier (*) et en fin sur C4 ce qui donnera la
formule suivante = B2*B4 + C2*C4. La valeur sera égale à zéro. Ne vous inquiétez pas.
Il faudra alors reprendre cette opération jusqu’à terminer toutes les contraintes. Pour la
deuxième contrainte, dans la cellule D5, on aura le résultat (formule) suivant :
B2*B5+C2*C5, pour la troisième contrainte, dans la cellule D6, on aura le résultat
(formule) suivant : B2*B6+C2*C6, et pour la quatrième et dernière contrainte, dans la
cellule D7, on aura le résultat (formule) suivant : B2*B7+C2*C7.
5) Ce qui vous reste à faire en termes d’introduction de données est la formule de calcul du
profit total qui s’obtient en multipliant les quantités optimales reprises en B2 et C2 par
les prix unitaires contenues dans les cellules B8 et C8. En faisant cela, on obtient alors la
formule =B8*B2+C8*C2 à inscrire dans la cellule B9. C’est cette cellule qu’on
maximisera car elle correspond à la fonction objectif 66x1 + 84x2. L’image ci-dessous
illustre cela.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 37
Recherche Opérationnelle BAC+3 MP et SCAI

1) Menu: Outils/Solveur (office 2003) ou sous l’onglet Données (office 2007 à 2016), la
commande Solveur .
2) Entrez les paramètres du solveur comme vous pouvez le voir sur l’image ci-dessous :

 La Cellule cible à définir est celle qui doit contenir la cellule du profit total ou du coût
minimal en fonction du problème. Dans le cas de notre exemple, B9.
 Égale à permet de préciser le type de problème à résoudre : Minimisation ou
maximation. Pour notre exemple, nous allons cocher Max.
 Cellules variables: Cette zone reçoit les cellules de valeurs recherchées. Pour notre cas,

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 38
Recherche Opérationnelle BAC+3 MP et SCAI

les cellules B2 : C2 représentant les variables de décisions qui doivent être déterminées
automatiquement par le solveur.
 Contraintes: Cette zone contiendra toutes contraintes du programme linéaire sans
oublier les contraintes de non-négativité x1≥ 0, x2≥ 0.
Pour le faire,
1) Cliquez sur « Ajouter ». Cela vous apporte la boîte de dialogue « ajouter une contrainte »
ci-après :

2) Dans la zone de texte Référence de la cellule, cliquer dedans et allez sélectionner la

première contrainte contenue dans la cellule D4 dans laquelle vous avez entré la formule
du calcul de la contrainte.
3) Inscrivez le sens d’inégalité telle que repris dans le programme linéaire qu’on est en train
de résoudre. Dans le cadre de notre exemple, c’est le signe <= venant après la cellule
Référence de cellule.
4) Dans la colonne contrainte de la boîte de dialogue, sélectionner la ressource disponible
correspondante à la contrainte. Pour cet exemple, cliquer sur la cellule E4. Cette
opération sera faite autant de fois des contraintes. Il faudra aussi ajouter la contrainte de
la non négativité en sélectionnant la plage réservée aux valeurs recherches, B2:C2 mais
elles avec >= comme sens d’inégalité et 0 dans la zone contrainte de la boite de dialogue
« Ajouter une contrainte ». Une fois terminé, vous êtes alors demandé de cliquer sur OK.
Afin de permettre le solveur de passer au calcul, il faudra alors spécifier qu’il s’agit d’un
programme linéaire. Cela fait à travers la boîte de dialogue Options du Solveur obtenue par un
clic sur le bouton Options de la boîte des Paramètres du solveur dans le cas d’office antérieur
à 2007. Sous la boîte Options du solveur, cochez “Modèle supposé linéaire et cliquez sur
“OK”. Pour office de 2007 à 2016, la détermination de la méthode de résolution se fait par le
choix de Simplex Pl dans la zone de texte « Sélect. une résolution » située à côté du bouton «
Options».

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 39
Recherche Opérationnelle BAC+3 MP et SCAI

5) Cliquez sur le bouton ―Résoudre‖ de la boîte de dialogue Paramètres du solveur : Le

solveur va alors fournir la solution optimale selon les contraintes. La variable X1 sera
de 1000 unités, la variable X2, 300 unités et le bénéfice sera de 91200$. Il va aussi
vous apporter la boîte de dialogue ci-dessous dans laquelle vous allez cliquer sur l’item
Réponses dans l’option rapports et enfin sur le bouton Ok.

6) Le solveur crée alors une feuille de rapport de manière automatique portant le nom de la
feuille contenant les données du programme auquel il ajoute 1.
2.7. Exercices d’Application
1) Le gérant d'un hôtel souhaite renouveler le linge de toilette de son établissement. Il a besoin
de : 90 draps de bain, 240 serviettes et 240 gants de toilette. Une première entreprise de vente

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 40
Recherche Opérationnelle BAC+3 MP et SCAI

lui propose un lot A comprenant 2 draps de bain, 4 serviettes et 8 gants pour 200 francs. Une
deuxième entreprise vend pour 400 francs un lot B de 3 draps de bains, 12 serviettes et 6 gants
de toilettes. Pour répondre à ses besoins, le gérant achète x lots A et y lots B.
1. Traduire par un système d'inéquations les contraintes auxquelles satisfont x et y.
2. Par la méthode graphique trouver la fonction objectif.

2) Pour fabriquer deux produits P1 et P2 on doit effectuer des opérations sur trois machines
M1, M2 et M3, successivement mais dans un ordre quelconque. Les temps unitaires
d’exécution sont donnés par le tableau suivant :
M1 M2 M3
P1 11 mn 7 mn 6 mn
P2 9 mn 12 mn 16 N
On supposera que les machines n’ont pas de temps d’inactivité. La disponibilité
pour chaque machine sont :
- 165 heures (9900 minutes) pour la machine M1 ;
- 140 heures (8400 minutes) pour la machine M2 ;
- 160 heures (9600 minutes) pour la machine M3 .
Le produit P1 donne un profit unitaire de 900 dinars et le produit P2 un profit unitaire de 1000
dinars. Dans ces conditions, combien doit-on fabriquer mensuellement de produits P1 et P2
pour avoir un profit total maximum ?
3) Une entreprise désire effectuer une campagne publicitaire dans la télévision, la radio et
les journaux pour un produit lancé récemment sur le marché. Le but de la campagne est
d’attirer le maximum possible de clients. Les résultats d’une étude de marché sont
donnés par le tableau suivant :
Télévision Radio Journaux
Locale Par satellite
Coût d’une publicité 40 DT 30 DT 75 DT15 DT
Nombre de client potentiel 400 500 900 200
par publicité
Nombre de client potentiel 300 400 200 100
femme par publicité
Pour la campagne, on prévoit de ne pas payer plus que 800DT pour toute la campagne et on
demande que ces objectifs soient atteints :
- Au minimum 2000 femmes regardent, entendent ou lisent la publicité ;
- La campagne publicitaire dans la télévision ne doit pas dépasser
500 DT ;
- Au moins 3 spots publicitaires seront assurer par la télévision locale et au moins
de deux spots par la télévision par satellite.
- Le nombre des publicités dans la radio ou dans les journaux sont pour chacun
entre 5 et 10.
4) Minimiser sous les contraintes :
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 41
Recherche Opérationnelle BAC+3 MP et SCAI

Réponses :

5) Minimiser sous les contraintes :

Réponses :

4) Une entreprise fabrique du sirional et des engrais. Les installations spécifiques à la

production d’engrais, unité de séchage et du criblage, limitent pour l’instant cette production à
180 tonnes par mois, mais exigent aussi une production minimale de 40 tonnes. De plus, la
capacité mensuelle de traitement est de 700 heures pour la station de filtrage et 600 heures pour
celle de cristallisation. Le temps de passage par tonne de produit fini est de :
 Pour le sirional : 5 heures en atelier filtration et 6 heures en atelier cristallisation ;
 Pour l’engrais : 3,5 heures en atelier filtration et 2 heures en atelier cristallisation.
La marge sur coût variable par tonne de produit fini est de 12 $ pour le sirional et 10$ l’engrais.
TD : Déterminer le programme optimale de production mensuelle (résolution graphique) et en
déduire la marge totale.

5) Une entreprise utilise au moins 800 kg d’une alimentation spécial par jour. Cette alimentation
est un mélange de blé et de soja, avec les compositions suivantes :

Les besoins alimentaires de cette alimentation spéciale sont d’au moins 30% de protéines et au
plus 5% de fibre végétale. L’entreprise veut déterminer le coût minimum journalier de ce
mélange d’alimentation.
6) Un atelier fabrique deux pièce A et B. La capacité de production de l’atelier est de 40
heures. En une heure, l’atelier fabrique 6 pièces A ou 8 pièces B. Les pièces A et B sont
vendues respectivement à 3,25$ et 2,50$; les charges variables s’élèvent à 3 $ par kg de

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 42
Recherche Opérationnelle BAC+3 MP et SCAI

matières premières utilisées. La fabrication d’une pièce A consomme 0,4kg de matières,

celle de de B, 0,25kg. Présenter les contraintes sous la forme d’une inéquation ainsi que
la fonction économique permettant la marge sur coût variable.
2.8. Limites de la programmation linéaire.
Certes la programmation linéaire a ses propres limites mathématiques (linéarité,
indépendance, divisibilité des facteurs), mais elles ne sont généralement pas contraintes.
Aujourd’hui la programmation linéaire peut être utilisée sur n’importe quel micro-ordinateur et
ne coûte presque rien. Les principales limites ne sont pas imputables à la programmation
Linéaire., mais plutôt aux capacités de l’analyste économique et de l’utilisateur. La théorie des
anticipations reste à construire. L’insuffisance est aussi très grande dans des domaines comme
les modifications de structure d’exploitation et surtout le niveau technique. Il est en effet très
difficile p. ex d’apprécier les variations des niveaux techniques. Comment les mesurer ? D’où
proviennent-elles ? Comment se diffusent les innovations techniques ? Ce sont autant de
questions très importantes pour l’utilisation de l’outil sur lesquelles il y a encore très peu
d’informations. La programmation linéaire reste un outil qui peut être utile dans de nombreuses
analyses et indispensable pour certaines. La possibilité de tenir compte d’un très grand nombre
de variables et d’en obtenir la solution optimale est d’un très grand secours pour interpréter les
conditions de production si l’on évite deux pièges dont il faut se rappeler. D’une part, le piège
normatif, c'est-à-dire l’interprétation du résultat obtenu comme la meilleure solution à appliquer
(norme). D’autre part, le piège du quantifiable : refuser d’introduire les considérations dites
subjectives (incertitude, imitation, loisirs…) comme si les informations quantifiées pouvaient
être déterminées de façon strictement objective.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 43
Recherche Opérationnelle BAC+3 MP et SCAI

Chapitre 3 : NOTIONS GENERALES SUR LA THEORIE DES GRAPHIES ET

LES PROBLEMES D’ORDONNANCEMENT D’UN PROJET
Plusieurs situations concrètes de notre vie quotidienne (vie sociale, économique,
politique, etc.) peuvent être formalisées au moyen de dessin permettant d’exprimer
commodément le problème posé et parfois même d’en suivre aisément la solution par un
algorithme approprié.

Les situations suivantes peuvent être traduites en graphe :

- Différentes tâches exécutées par une ménagère lors de la préparation d’un déjeuner ; -
trafic routier ;
- Réseau de voies ferrées ;
- Fils électriques ;

- Rues d’une ville ;

- Echanges commerciaux ;
- Réseau de communications entre individus ;
- Circulations des informations dans un système ;
- Distribution de marchandises ;

- etc.

3.1.Définition
3.1.1. Graphe
Soit G, une relation sur un ensemble X ; on pourra représenter le fait que deux
éléments a, b de X sont en relation par un arc de a vers b : a → b. Si a, b et b, a sont en
relation, on aura une ligne non orientée (appelée arête) a — b. Une relation sera donc
représentée par un ensemble
d’arcs (ou d’arêtes) pouvant
se succéder.

Graphes non orientés

V=* +
E *( ) ( ) ( ) ( ) ( ) ( )+
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 44
Recherche Opérationnelle BAC+3 MP et SCAI

[Link] Types des Graphes

3.2.1. Graphe Orienté
Un graphe orienté G est un couple (X,R) où X est un ensemble de sommets
{x1,...,xn} et R unensemble de couples orientés (xi, xj) appelés arcs. Pour un arc (xi, xj) d'origine
xi et d'extrémité xj, xi est un précédent de xj, et xj est un suivant de xi . Un chemin est une suite
ordonnée (x1,...,xn) de sommets reliés par des arcs. La longueur du chemin est le nombre d'arcs
qu'il contient. Un circuit est un chemin (x1,...,xn) tel que x1 = xn.

La relation D définie sur X = {1, 2, 3, 6, 12} telle que: ∀x, y ∈ X, D(x, y) ssi x divise y peut être
représentée par :

3.2.2. Graphe Simple

Un graphe est simple si au plus une arête relie deux sommets et s'il n'y a pas de
boucle sur un sommet.

3.2.3. Graphe Connexe

Un graphe est connexe s'il est à partir de n’importe quel sommet, de rejoindre tous
les autres en suivant les arêtes. Un graphe connexe se décompose en composantes connexes. Sur
le graphe ci-dessous, les composantes connexes sont : { l,2, 3,4} et {5,6} mais le graphe est
non connexe.

3.2.4. Graphe complet

Un graphe est complet si chaque sommet du graphe est relié directement à tous
les autres sommets-

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 45
Recherche Opérationnelle BAC+3 MP et SCAI

3.2.5. Graphe Bipartie

Un graphe est biparti si ses sommets peuvent être divisés en deux ensembles X
et Y, de sorte que Inules les arêtes du graphe relient un somme dans X à un sommet dans Y
(dans l'exemple ci-dessous, on a X = {1,3 51 et Y = 12,4} cm vice versa).

3.2.6. Graphe Partiel et sous-graphe

Soit G = (V, E) un graphe. Le graphe G' = (V, E’) est un graphe partiel de G, si
E’ est inclus dans E. Autrement dit, on obtient G’ en enlevant une ou plusieurs arêtes au graphe
G. Pour un sous-ensemble de sommets A inclus dans V, le sous-graphe de G induit par A est le
graphe G=(A.E(A)) dont l’ensemble des sommets est A et l'ensemble des arêtes E(A) est formé
de toutes les arêtes de G ayant leurs deux extrémités dans A. Autrement dit, on obtient G' en
enlevant un ou plusieurs sommets au graphe G, ainsi que toutes les arêtes incidentes à ces
sommets.

3.2.7. Graphe Orienté valué

Un Graphe orienté valué est un graphe orienté G= (V, E) muni d’une fonction
supplémentaire w : E R qui associe une valeur (coût, poids ou longueur) à chaque arc. Le
graphe G deviendra alors G= (V,E w). Autrement dit, un graphe orienté valué est d’un graphe
G dont toutes les flèches ou arcs associé(es) ont des valeurs numériques.
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 46
Recherche Opérationnelle BAC+3 MP et SCAI

3.2.8. Graphe acyclique

Un graphe acyclique est un graphe ne pouvant contenir au cycle quel qu’il soit.

3.2.9. Graphe isomorphe

En mathématiques, dans le cadre de la théorie des graphes, un isomorphisme de
graphes est une bijection entre les sommets de deux graphes qui préserve les arêtes. Ce
concept est en accord avec la notion générale d'isomorphisme, une bijection qui préserve les
structures.

3.2.10. Digraphe
Un Digraphe ou « graphe orienté » est un graphe dont les arrêtes sont orientées
et dont le couple est défini comme suit ! (Départ, Arrivée). Par conséquence, le couple (x, y)
est différent du couple (y, x) puisque leur orientation est différente.
3.2.11. Graphe non orienté
En théorie des graphes, un graphe non orienté G=(V,E) est un couple formé
de V un ensemble de sommets et E un ensemble d'arêtes, chaque arête étant une paire de
sommets. Cette définition ne s'applique qu'aux graphes simples et n'est pas valable pour
les multigraphes.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 47
Recherche Opérationnelle BAC+3 MP et SCAI

3.3.Détermination des Degrés dans un graphe

3.3.1. Degré d’un sommet
En mathématiques et en informatique, et plus particulièrement en théorie des
graphes, le degré (ou valence) d'un sommet d'un graphe est le nombre de liens (arêtes ou arcs)
reliant ce sommet, avec les boucles comptées deux fois. Le degré d'un sommet est noté par
d(v).
Autrement dit, on appelle degré du somme v, et on note par d(v), le nombre d’arrêtes
incidentes à ce sommet.
Attention : Une boucle sur un sommet compte double.

3.3.2. Degré d’un Graphe

Le degré d'un graphe est le degré maximum de tous ses sommets. . Dans l'exemple
ci. dessous, le degré du graphe est 4, à cause du somme v3. Un graphe dont tous les sommets
ont le même. degré est dit régulier. Si le degré commun est k, alors on dit que le graphe est k-
régulier.

[Link] et Cycles
3.4.1. Chaine
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 48
Recherche Opérationnelle BAC+3 MP et SCAI

Une chaîne dans un graphe G est une suite ayant pour éléments alternativement des
sommets et des arêtes, commençant et se terminant par un sommet, et telle que chaque arête est
encadrée par ses extrémités.
En outres, Une chaîne est une suite d’arêtes telle que l’extrémité terminale de
chaque arête coïncide avec l’extrémité initiale de l’arête suivante. On dira que la chaine relie le
premier sommet de la suite au dernier sommet. En plus, on dira que la chaîne a pour' longueur le
nombre d’arrêtes de la chaîne. Le graphe ci-dessous contient entre autres les chaines (

NB : Il existe :
- Chaîne simple est une chaîne qui n’utilise pas deux fois la même arête.
- Chaîne eulérienne est une chaîne simple passant par toutes les arêtes d’un graphe.
- Chaîne hamiltonienne est une chaîne simple passant par tous les sommets d’un graphe
une et une seule fois.
3.4.2. Cycle
Un cycle est une chaîne simple se fermant sur elle-même. C’est donc une chaîne qui
revient à son point de départ. Dans le cas des graphes non orientés, un circuit est un cycle et un
chemin est une chaîne.
NB : Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives distinctes
(chaine simple) dont les deux sommets extrémités sont identiques. Dans les graphes orientés, la
notion équivalente est celle de circuit, même si on parle parfois aussi de cycle (par exemple
dans l'expression graphe acyclique orienté).

NB : Il existe généralement :
- Un cycle hamiltonien est un cycle simple passant par tous les sommets d’un graphe
une et une seule fois.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 49
Recherche Opérationnelle BAC+3 MP et SCAI

- Un cycle élémentaire est un cycle ne passant pas deux fois par le même sommet, sauf
que le sommet final coïncide toujours avec le sommet de départ.
- Cycle eulérien : cycle simple passant par toutes les arêtes d’un graphe une et une
seule fois.
3.4.3. Une boucle
Une boucle est une ligne orientée qui revient à son sommet de départ.

NB : Le sommet V5 est bouclé.

3.4.4. Arborescence et arbre

Une arborescence est un graphe orienté d’un seul tenant et sans circuit tel que,
pour tout couple de sommets de ce graphe, il existe toujours un autre sommet, origine d’un
chemin conduisant aux premiers sommets. L’origine de l’arborescence est appelée «centre»
ou «racine».
Un arbre est un graphe non orienté d’un seul tenant et sans cycle tel que pour aller d’un
sommet à un autre sommet du graphe, il existe toujours une chaîne.

Arborescence Arbre

[Link] graphes remarquables et présentation non graphique d’un graphe

3.5.1. Quelques graphes remarquables
[Link]. Graphes eulériens
En théorie des graphes, un parcours eulérien ou chemin eulérien, ou
encore chaine eulérienne d'un graphe non orienté est un chemin qui passe par toutes les arêtes,
une fois par arête. Le nom a été donné en référence à Leonhard Euler. Si un tel chemin revient
au sommet de départ, on parle de circuit eulérien ou cycle eulérien, ou encore tournée
eulérienne. Un graphe qui admet un circuit eulérien est dit eulérien. S'il admet
un parcours eulérien, il est dit semi-eulérien.
En d’autres termes, on appelle cycle eulérien d’ un graphe G un cycle passant une et

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 50
Recherche Opérationnelle BAC+3 MP et SCAI

une -seule fois par chacune des arêtes de G. Un graphe est dit eulérien s'il possède un cycle
eulérien. On appelle chaîne eulérienne d'un graphe G une chaîne passant une et une seule fois
par chacune des arêtes de G, Un graphe ne possédant que des chaînes eulériennes est semi-
eulérien.
En résumé : Un cycle qui passe exactement une fois par chaque arête d’un graphe est dit «
eulérien ».

3.5.1. 2. Graphe Hamiltonien

En Informatique et en Mathématique, dans le cadre de la théorie des graphes,
un chemin hamiltonien d'un graphe orienté ou non orienté est un chemin qui passe par tous les
sommets une fois et une seule. Un cycle hamiltonien est un chemin hamiltonien qui est
un cycle. Un graphe hamiltonien est un graphe qui possède un cycle hamiltonien.

Un graphe hamiltonien ne doit pas être confondu avec un graphe eulérien, où l'on
passe par toutes les arêtes une fois et une seule : dans un cycle hamiltonien, on peut très bien
négliger de passer par certaines arêtes. Un graphe peut être eulérien, hamiltonien, les deux à la
fois, ou aucun des deux : le graphe papillon est un exemple de graphe eulérien mais pas
hamiltonien.

3.5.1. 3. Types particuliers des graphes

a) Graphe (d’une relation) symétrique
C’est un graphe dans lequel deux sommets adjacents sont toujours reliés par deux
arcs (ou flèches) doubles (un dans chaque sens).

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 51
Recherche Opérationnelle BAC+3 MP et SCAI

b) Graphe (d’une relation) antisymétrique

C’est un graphe dans lequel aucune flèche n’est double, ce qui veut dire que deux
sommets ne sont pas reliés par deux arcs.

c) Graphe d’une relation non symétrique

Une flèche ou moins n’est pas double.

d) Graphe d’une relation non antisymétrique

Une flèche au moins est double. (a,d) et (d,a).

3.5.1. 4. Graphe d’une relation réflexive

Tous les sommets possèdent une boucle.

e) Graphe d’une relation non réflexive

Un sommet au moins n’est pas bouclé.

f) Graphe d’une relation anti-réflexive

Aucun sommet n’est bouclé.

g) Graphe d’une relation non anti-réflexive

La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 52
Recherche Opérationnelle BAC+3 MP et SCAI

Un sommet au moins est bouclé

3.5.2 Présentation non Graphique des Graphes

On peut représenter un graphe de diverses façons, entre autres par :
- une représentation sagittale (par flèche) ;
- une énumération de tous les sommets et arcs qui le composent ;
- des dictionnaires ou tableaux à simple entrée ;
- des matrices appropriées : matrice d’adjacence, matrice d’incidence sommets –
arcs, matrice aux arcs ;
- une grille.

[Link]. Représentation sagittale d’un graphe

Une représentation sagittale d’un graphe se caractérise par un schéma pourvu de
sommets reliés entre eux par des lignes orientées ou non.

Gr1

[Link]. Représentation d’un graphe sous forme de méthode énumérative des sommets et
arcs
Le graphe Gr1 se traduit par les sommets et arcs suivants :

[Link]. Représentation d’un graphe à l’aide de dictionnaire

Soit un graphe G = (X, U).
On appelle « dictionnaire des suivants » de ce graphe un tableau à simple entrée
dont chaque ligne concerne un sommet précis et contient tous les suivants dudit sommet. On
appellera « dictionnaire des précédents » du graphe G un tableau à simple entrée dont chaque
ligne relève d’un sommet précis et contient tous les précédents du sommet en question.
Soit le graphe orienté ci-après :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 53
Recherche Opérationnelle BAC+3 MP et SCAI

Grap. A

[Link]. Représentation matricielle d’un graphe

a) Matrice d’adjacence( sommet – sommet)

La matrice d’adjacence associée au graphe Grap A est :

La lecture ligne par ligne de cette
matrice donne le dictionnaire des
suivants.
La lecture colonne par colonne donne le
dictionnaire des précédents.
La matrice d’adjacence d’un graphe
non orienté est une matrice symétrique.

Les termes non nuls de la diagonale

principale représentent des boucles. La
matrice d’adjacence d’un graphe non
orienté est une matrice symétrique.
b) Matrice aux arcs associée à un graphe
Si dans la matrice d’adjacence ci-dessus on remplace les « 1 » par les arcs
concernés, on obtient une matrice dite « matrice aux arcs ».

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 54
Recherche Opérationnelle BAC+3 MP et SCAI

Matrice aux arcs correspondant au graphe Grap A

c) Matrice d’incidence sommets – arcs d’un graphe sans boucle.
En mathématiques et informatique, et plus particulièrement en théorie des graphes,
la matrice d'incidence d'un graphe est une matrice qui décrit le graphe en indiquant quels liens
arrivent sur quels sommets.
La matrice d'incidence est une matrice n x p, où n est le nombre de sommets du graphe
et p est le nombre de liens (arêtes ou arcs). Cette matrice est définie de deux façons différentes selon que
le graphe est orienté ou non orienté.
Si le graphe est orienté, la matrice est appelée « matrice d'incidence sommets-arcs1 » ; le
coefficient de la matrice d'incidence en ligne i et en colonne j vaut:
 -1 si l'arc xj sort du sommet vi
 1 si l'arc xj entre dans le sommet vi
 0 sinon
Certains auteurs utilisent une autre convention où les rôles de 1 et -1 sont permutés.
Si le graphe est non orienté, la matrice est appelée « matrice d'incidence sommets-arêtes »; le
coefficient de la matrice d'incidence en ligne i et en colonne j vaut :

 1 si le sommet vi est une extrémité de l'arête xi

 2 si l'arête xj est une boucle sur vi
 0 sinon
Prenons le cas du graphe ci-contre. Il possède 5 sommets et 6 arêtes, la matrice
d'incidence aura donc 5 lignes et 6 colonnes :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 55
Recherche Opérationnelle BAC+3 MP et SCAI

ce qui donne la matrice d'incidence :

 le e sommet 1 est l'aboutissement des arêtes 1 et 5

 le sommet 2 est l'aboutissement des arêtes 1, 2 et 6
 le sommet 3 est l'aboutissement des arêtes 2 et 3
 le sommet 4 est l'aboutissement des arêtes 3 et 4
 le sommet 5 est l'aboutissement des arêtes 4, 5 et 6

On remarque que chaque colonne a une somme égale à 2, puisque chaque arête a deux
extrémités.
La matrice d’incidence sommets-arcs A d’un graphe G = (X, U) est une matrice à m lignes et n
colonnes telle que si u(i, j) est un arc de U, la colonne u vaut 0 partout sauf en :
aiu = +1 et aju = –1.

Ici, les lignes représentent les sommets et les colonnes les arcs. Pour le graphe 1.24
ci-dessous, la matrice d’incidence sommets-arcs est :
Remarques :

• Chaque colonne comporte exactement 1 terme égal à 1 (dans la ligne du sommet initial de l’arc) et
un terme égal à –1 (dans la ligne du sommet terminal) ; les autres termes de la colonne étant tous
nuls ;
• La somme de chaque colonne est égale à 0 (un arc a une origine et une destination) ;
• La matrice est totalement uni modulaire i.e., toutes les sous-matrices carrées extraites de la
matrice ont pour déterminant +1, –1 ou 0.

3.6. Chemins dans un Graphes

3.6.1. Définition et 1er exemple
Il s’agit de chercher le ou les chemins de longueur extrémale (minimum ou
maximum) partant du sommet n°1 et aboutissant à un sommet donné.
Soit G = (X, U) un graphe orienté donné que nous supposons sans circuit. Les arcs du graphe
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 56
Recherche Opérationnelle BAC+3 MP et SCAI

sont de plus valués. Un chemin µ permettant d’aller d’un sommet x du graphe à un autre
sommet xh est optimal si la somme des valeurs l(xi, xj) valuant chaque arc xixj = µh est soit
minimale, soit maximale. Dans le premier cas, l’optimum est un minimum, dans le second, un
maximum, la valeur extrémale étant :

et on obtient le chemin µ de valeur minimale ou le chemin

de valeur maximale.
Plusieurs algorithmes existent pour rechercher un tel chemin notamment l’algorithme de
Dijkstra, l’algorithme de Bellman - Kalaba, l’algorithme de Demoucron.
Dans ce cours, il a été plus commode d’utiliser l’algorithme de Bellman -Ford qui procède par
des marquages progressifs des sommets du graphe, de la manière suivante :

Exemple

3.6.2. Les Parcours de Graphes orientés

En théorie des graphes, un parcours de graphes est un algorithme consistant à
explorer les sommets d’un graphe de proche en proche à partir d’un sommet initial. Un cas
particulier important est le parcours d’un arbre. Le mot parcours est également utilisé dans
un sens différent, comme synonyme de chemin (parcours fermé étant un circuit). Pour
parcourir un graphe, on peut utiliser l’algorithme de Dijkstra.
a) Boucle : Une boucle est une ligne orientée qui revient à son sommet de départ. Le
graphe 1.5 contient deux boucles. L’arc u6 du graphe 1.22 est une boucle.
b) Chaîne : Une chaîne est une suite d’arêtes telle que l’extrémité terminale de chaque
arête coïncide avec l’extrémité initiale de l’arête suivante.
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 57
Recherche Opérationnelle BAC+3 MP et SCAI

- Chaîne simple est une chaîne qui n’utilise pas deux fois la même arête.
- Chaîne eulérienne est une chaîne simple passant par toutes les arêtes d’un graphe.
---- Chaîne hamiltonienne est une chaîne simple passant par tous les sommets d’un
graphe une et une seule fois.
c) Cycle :Un cycle est une chaîne simple se fermant sur elle-même. C’est donc une
chaîne qui revient à son point de départ. Dans le cas des graphes non orientés, un
circuit est un cycle et un chemin est une chaîne.
- Un cycle hamiltonien est un cycle simple passant par tous les sommets d’un graphe
une et une seule fois.
- Un cycle élémentaire est un cycle ne passant pas deux fois par le même sommet, sauf
que le sommet final coïncide toujours avec le sommet de départ.
- Cycle eulérien : cycle simple passant par toutes les arêtes d’un graphe une et une seule
fois.
d) Arborescence et arbre
Une arborescence est un graphe orienté d’un seul tenant et sans circuit tel que, pour
tout couple de sommets de ce graphe, il existe toujours un autre sommet, origine d’un chemin
conduisant aux premiers sommets. L’origine de l’arborescence est appelée «centre» ou «racine».
Un arbre est un graphe non orienté d’un seul tenant et sans cycle tel que pour aller
d’un sommet à un autre sommet du graphe, il existe toujours une chaîne.

3.7. Le Problème d’optimisation dans un graphe valué

3.7.1. Problèmes du plus cours chemin dans un graphe

A chaque arc (x,y) est associé un nombre positif V(x,y) appelé la valeur de l'arc.
L'algorithme de Ford va nous permettre de déterminer le chemin de valeur maximale entre un
sommet D (Départ) et un sommet F (Fin).
- On ordonne le graphe par niveaux
- On fait la représentation du graphe par niveaux.
A partir de cette représentation, on supprime les sommets et les arcs par lesquels on ne

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 58
Recherche Opérationnelle BAC+3 MP et SCAI

peut pas passer pour aller de D à F.

- En partant du sommet D de niveau le plus faible (le plus à gauche) jusqu'au
sommet F de niveau le plus fort (le plus à droite), on associe à chaque sommet x
une marque m(x) correspondant à la valeur du chemin de valeur maximale
aboutissant à x.
m(D) = 0
m(x) = max [m(y) + V(y,x)] , le max étant pris sur tous les précédentsy de x

La marque de F donnera donc la valeur du chemin le valeur maximale entre D et F.

Le chemin de valeur maximale est le chemin qui a permis d'aboutir à la marque de F. Il est
obtenu en partant de F et en regardant quel est le sommet précédent qui a permis d'obtenir m(F),
et ainsi de suite jusqu'à revenir en D.
Exemple : Considérons le graphe suivant ordonné par niveaux

On désire chercher le chemin de valeur maximale entre le sommet 4 et le sommet

7. On supprimedonc les sommets et les arcs par lesquels on ne peut pas passer pour
aller de 4 à 7, c.à.d.
 les sommets 1 et 2, ainsi que les flèches issues de ces sommets
 les sommets 8 et 9, ainsi que les flèches aboutissant à ces sommets

m(4) = 0
m(3) = m(4) + V(4,3) = 0 + 5 = 5
m(5) = m(4) + V(4,5) = 0 + 2 = 2
m(6) = Max { m(3) + V(3,6) ; m(5) + V(5,6) } = Max { 5 + 5 ; 2 + 1 }= Max { 10 ; 3 } =
10

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 59
Recherche Opérationnelle BAC+3 MP et SCAI

m(7) = Max { m(3) + V(3,7) ; m(6) + V(6,7) } = Max { 5 + 3 ; 10 + 6 }= Max { 8 ; 16 }

=16
Le chemin de valeur maximale entre 4 et 7 a donc pour valeur 16. Pour déterminer
quel est ce chemin, en partant du sommet final, on regarde quel est le sommet
précédent qui a permis d'obtenir la marque retenue. Ci-dessous est repris l'algorithme
précédent où le cheminement suivi est surligné en rouge en partant du sommet final 7
:
m(7) = Max { m(3) + V(3,7) ; m(6) + V(6,7) } = Max { 5 + 3 ; 10 + 6 }= Max { 8 ; 16 }
=16
Pour aboutir à 7, on est passé par 6
m(6) = Max { m(3) + V(3,6) ; m(5) + V(5,6) } = Max { 5 + 5 ; 2 + 1 }= Max { 10 ; 3 } =
10
Pour aboutir à 6, on
est passé par 3m(3)
= m(4) + V(4,3) = 0
+5=5
Pour aboutir à 3, on
est passé par 4m(4)
=0
4 est le sommet initial; d'où le chemin de valeur maximale (4,3,6,7).
Exemple : trouver le chemin plus long (le chemin de valeur maximale) de graphe ci-après :

b) Problème du chemin de valeur minimale dans un graphe

Pour un chemin de valeur minimale, il suffit de remplacer "max" par "min" dans
l'algorithme. D’où l’algorithme devient alors :
m(D) = 0
m(x) = min [m(y) + V(y,x)] , le min étant pris sur tous les précédentsy de x

Exemple :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 60
Recherche Opérationnelle BAC+3 MP et SCAI

Il est utile de rappeler que quand plusieurs trajets convergent vers un nœud ou sommet,
c’est le plus court qui a la primauté.
Remarques
Rappelons encore que la recherche du chemin le plus court revient, en d’autres termes,
à remplacer le maximum par le minimum chaque fois que plusieurs arcs aboutissent au même
sommet.
Enfin, l’utilité de la recherche d’un chemin de valeur minimale réside dans la
détermination de l’itinéraire le plus court permettant de se rendre d’un point x0 à un point xb,
les arcs représentant les routes et les valeurs portées sur les arcs les distances kilométriques.
On peut avoir l’itinéraire le plus rapide si la valuation concerne le temps de parcours, ou
encore le moins coûteux si l’on fait état de la consommation de carburant.
La recherche d’un chemin de valeur maximale a une importance capitale dans les
modèles d’ordonnancement.
3. 8. Les Problèmes d’Ordonnancement et Gestion de Projet
3.8.1. Notions préliminaires

Un problème d'ordonnancement consiste à ordonner dans le temps un

ensemble de tâches contribuant à la réalisation d'un même projet. 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. L’ordonnancement est
une programmation des activités et des ressources nécessaires à l’exécution de ces
dernières. Cette programmation tient compte des différentes contraintes techniques du
projet et de la disponibilité des ressources utilisées.
3.8.2. Objectif
L’objectif visé est de permettre au projet d’atteindre ses objectifs de délai, de coûts
et de performances. Pour définir un problème d’ordonnancement, il faut :
- décomposer le projet en tâches élémentaires ;
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 61
Recherche Opérationnelle BAC+3 MP et SCAI

- préciser les contraintes qui s’opposent à ce que les tâches soient exécutées
arbitrairement.
Une telle méthode doit donc permettre :
- d’analyser le projet en profondeur, c’est-à-dire le décomposer en tâches ;
- de mettre sur pied un plan d’action contribuant à réaliser ledit projet tout en respectant
les contraintes, c’est-à-dire de déterminer le meilleur temps nécessaire à la réalisation
de l’ensemble de l’ouvrage entrepris ;
- et enfin, de contrôler le bon déroulement du projet, c’est-à-dire de localiser les tâches
ou les étapes-critiques ou celles qui ne peuvent être ni retardées, ni ralenties, sans que
la fin des travaux soit décalée du temps correspondant.
3.8.3. Construction du Graphes

Exemple : Les opérations mises en jeu dans la construction d'un ensemble hydro-
électrique sont lessuivantes :
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é sont les suivantes :

Opérations durée (mois) opérations prérequises

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
Deux méthodes sont classiquement utilisées : la Méthode des Potentiels Metra

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 62
Recherche Opérationnelle BAC+3 MP et SCAI

(MPM), et la méthode PERT (Programm Evaluation and Research Task). Toutes les deux
utilisent des graphes pour résoudre le problème.

NB : Faute du temps, on développera beaucoup plus Méthode Française (

Potentielle-Tâche).
h) Par la Méthode Française ( Potentielle-Tâche)
- Notions
Cette méthode, appelée aussi méthode des potentiels-tâches, fait appel à une
représentation diamétralement opposée à celle de PERT. En effet, les tâches sont maintenant
identifiées par les sommets (non plus par des arcs), les arcs correspondant pour leur part aux
conditions d’antériorité entre les tâches. De plus, les arcs sont valués chacun par un nombre
donnant la durée minimale devant s’écouler entre le début de la tâche représentée par l’extrémité
initiale et celui de la tâche placée à l’extrémité terminale. La formalisation du projet est
également plus souple : si de nouvelles tâches ou de nouvelles contraintes doivent être
introduites, il est très facile de les ajouter. Dans la méthode PERT, cela nécessiterait la
construction d’une partie du graphe.

- Construction du graphe
- 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 :
Tx T*x
X
où :
- x = nom de la tâche,
- Tx = date de début au plus tôt de la tâche
- T*x = 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.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 63
Recherche Opérationnelle BAC+3 MP et SCAI

Calendrier au plus tôt

Une tâche x ne pouvant débuter que lorsque toutes les tâches qui y aboutissent
sont terminées, Tx correspond à la valeur du chemin de valeur maximale aboutissant
à x. Ceci sera obtenu en utilisant l'algorithme de Ford (voir chapitre sur les graphes),
après avoir ordonné le graphe par niveaux des tâches.
Tx = max [Ty + V(y,x)] , le max étant pris sur les précédents y de x.

Exemple:
Ta = Tc = Td = 0Tb = Ta + 4 = 4
Tg = Ta + 4 = 4
Tf = Max (Tb + 6 ; Tc + 4) = Max (10 ; 4) = 10
Te = Max (Tb + 6 ; Tc + 4 ; Td + 12 ) = Max
(10 ; 4 ; 12) = 12Th = Max (Te + 10 ; Tg + 7) =
Max (22 ; 11) = 22
Ti = Max (Tf + 24 ; Th + 10) =
Max (34 ; 32) = 34Tz = Ti + 3 = 37
Ces résultats peuvent être reportés sur le graphe

Pour le sommet terminal z, Tz 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
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 64
Recherche Opérationnelle BAC+3 MP et SCAI

sur l'une de tâches critiques entraînerait unallongement de la durée du projet.

Exemple :
Le chemin de valeur maximale est le chemin a, b, f, i. (voir chapitre sur les graphes)
et a pour durée 37.
- Calendrier au plus tard
Il s'agit de la date au plus tard à laquelle peut commencer une tâche sans remettre
en cause la datede 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.
T*z = Tz pour le sommet terminal
T*x = min [T*y - V(x,y)] , le min étant pris sur les suivants y de x.
Exemple :
T*i = T*z - V(i,z) = 37 - 3 = 34 T*h = T*i - V(h,i) = 34 - 10 = 24T*f = T*i - V(f,i) = 34 -
24 = 10

T*e = T*h - V(e,h) = 24 - 10 = 14T*g = T*h - V(g,h) = 24 - 7 = 17

T*b = Min [T*e - V(b,e); T*f - V(b,f) = Min [14 - 6; 10 - 6 ] = 4
T*a = Min [T*b - V(a,b); T*g - V(a,g) = Min [4 - 4; 17 - 4 ] = 0
T*c = Min [T*f - V(c,f); T*e - V(c,e) = Min [10
- 4; 14 - 4 ] = 6T*d = T*e - V(d,e) = 14 - 12 = 2
Ces résultats peuvent être reportés sur le graphe

Remarque: sur les tâches critiques a, b, f, i, on a T*x = Tx

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

mt(x) = T*x - Tx

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 65
Recherche Opérationnelle BAC+3 MP et SCAI

Exemple :

mt(a) = T*a - Ta = 0 - 0 = 0

mt(b) = T*b - Tb = 4 - 4 = 0

mt(c) = T*c - Tc = 6 - 0 = 6

mt(d) = T*d - Td = 2 - 0 = 2

mt(e) = T*e - Te = 14 - 12 = 2

mt(f) = T*f - Tf = 10 - 10 = 0

mt(g) = T*g - Tg = 17 - 4 = 13

mt(h) = T*h - Th = 24 - 22 = 2

mt(i) = T*i - Ti = 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 encause les dates au plus tôt des tâches suivantes (donc sans retarder la
fin des travaux).

mL(x) = min [Ty - Tx - V(x,y)] , le min étant pris sur les suivants y de x.

Exemple :
mL(a) = Min [Tb - Ta - V(a,b) ; Tg - Ta -
V(a,b)] = Min (0 ; 0) = 0
mL(b) = Min [Tf - Tb - V(b,f) ; Te - Tb -
V(b,e)] = Min (0 ; 2) = 0
mL(c) = Min [Tf - Tc - V(c,f) ; Te - Tc -
V(c,e)] = Min (6 ; 8) = 6
mL(d) = Te - Td - V(d,e) = 0
mL(e) = Th - Te - V(e,h) = 0
mL(f) = Ti - Tf - V(f,i) = 0
mL(g) = Th - Tg - V(g,h) = 11
mL(h) = Ti - Th - V(h,i) = 2
mL(i) = Tz - Ti - V(i,z) = 0

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 66
Recherche Opérationnelle BAC+3 MP et SCAI

i) Par la Méthode Américaine (Potentielle-Étape)

Le PERT (Programm of Evaluation and Review Technic) est, comme la MPM, une
technique d'ordonnancement basée sur la théorie des graphes, visant à optimiser la planification
des tâches d'un projet. Le P.E.R.T. est une méthode consistant à mettre en ordre sous forme de
réseau plusieurs tâches qui grâce à leur dépendance et à leur chronologie concourent toutes à
l’obtention d’un produit fini.

Cette technique aurait été conçue sous l'appellation initiale de méthode CPM
(Critical Method Path) par la marine américaine, en 1958, pour coordonner les tâches des
milliers d'entreprises impliquées dans son projet "Polaris" (programme de développement de
missiles à ogive nucléaire). Compte tenu de son efficacité (elle aurait permis de réduire de 14 à
7 ans la durée globale de réalisation du projet Polaris) elle s'est rapidement imposée dans les
organisations, gouvernementales ou non, ayant à gérer des projets importants (programme
Apollo de la NASA, construction d'autoroute, etc.) au détriment du diagramme de Gantt.
L'utilisation du PERT permet, notamment, de déterminer la durée minimum nécessaire pour
mener à bien un projet et les dates auxquelles peuvent ou doivent débuter les différentes tâches
nécessaires à sa réalisation pour que cette durée minimum soit respectée.
Construction du graphe
Le recours au PERT suppose qu'aient préalablement été identifiées les différentes
tâches nécessaires à la réalisation d'un projet, leur durée et leurs relations d'antériorité.
Généralement ces informations sont synthétisées dans un tableau du type suivant dit tableau des
tâches et antériorité.

Tâches Durée Antériorité(s)

Le PERT permet de représenter l'ensemble des tâches sur un graphe orienté, à partir
duquel il sera possible d'identifier leurs dates au plus tôt et au plus tard et de calculer leurs
marges. Un graphe orienté est un réseau composé d'une entrée et d'une sortie, ainsi que de points
(appelés "sommets") reliés entre eux par des flèches (appelées "arcs").
Les principales conventions d'un réseau PERT sont les suivantes :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 67
Recherche Opérationnelle BAC+3 MP et SCAI

- chaque tâche est symbolisée par un arc, auquel est associé une valeur numérique
correspondant à sa durée.
- les sommets auxquels aboutissent les arcs correspondent donc à des étapes, qui
marquent l'aboutissement d'une ou plusieurs tâches.
- chaque étape est identifiée par un numéro d'ordre et renseignée sur la date à
laquelle elle peut être atteinte au plus tôt ("date au plus tôt") et au plus tard ("date au
plus tard") pour respecter le délai optimal de réalisation du projet.
- le graphe possède une entrée (sommet sans antécédent) et une sortie (sommet sans
descendant) qui correspondent respectivement aux étapes "Début des opérations" et
"Fin desopérations".
Du fait de ses conventions, il est parfois nécessaire d'introduire des "tâches fictives"
de durée nulle pour traduire correctement sur un graphe les relations d'antériorité de certaines
tâches, notamment lorsque celles-ci partagent avec d'autres une partie de leurs antécédents.

- 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 signifiant que :
toutes les tâches qui y arrivent sont
terminées toutes les tâches qui en
partent peuvent commencer
Un réseau est constitué par des étapes et des tâches. On appelle étape le commencement
ou la fin
d’une tâche symbolisé par :
On appelle tâche le déroulement dans le temps d’une opération symbolisé par
sur laquelle seront indiqués l’action à effectuer et le temps de réalisation
de cette [Link] alléger le réseau PERT on attribut à chaque définition
une lettre alphabétique.
Les tâches suivant leur disposition dans un réseau peuvent être :
- successives
- simultanées
- convergentes
- Chaque sommet de la représentation graphique est figuré par un cercle

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 68
Recherche Opérationnelle BAC+3 MP et SCAI

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

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

- La représentation graphique est ordonnée par niveaux des sommets, c.à.d. des étapes.
Les tâches n’ayant aucune antériorité sont représentées en première position.
L’utilisation de lamatrice des antériorités facilite la détermination des niveaux d’exécution
des tâches.
Le graphe se lit de gauche à droite (de l'étape "DÉBUT" à celle de "FIN").
Chaque arc symbolise une tâche qui permet d'atteindre une nouvelle étape dans la
réalisation du projet. Une nouvelle tâche ne peut commencer que lorsque toutes les
tâches préalables à sa réalisation sont terminées. Chaque sommet correspond à une
étape qui est identifié par une cartouche où sont précisés : son "numéro d'ordre", la
date à laquelle elle peut être atteinte au plus tôt ("date au plus tôt") et la date à
laquelle elle doit être atteinte au plus tard pour respecter le délai optimal de
réalisation du projet ("date au plus tard").
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.
j) Recherche de Chemin(Chemin critique, Chemin de valeur maximale et chemin de
valeur minimale,….).
NB : Il y a aujourd’hui des solutions informatiques pour toutes questions d’ordonnancement
moyennant des applications informatiques. Ces applications sont à titre d’exemple : MS
Project (très puissant pour faire la gestion des taches et toutes les contraintes), Gantt
Project,….
EXERCICES

1) Le service de marketing de la Société des Huileries de RDC a projeté entretenir

les différents appareils utilisés dans la production d’huile de coton. Cet entretien
consiste à exécuter un certain nombre d’activités qu’il faut planifier. A cet effet,
le tableau suivant a été dressé :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 69
Recherche Opérationnelle BAC+3 MP et SCAI

Opérations Antériorités Durée

(mois)
A J 2
B I, G, J 4
C H 1
D C, H, E 2
E A, F 5
F H 3
G J 1
H - 2
I A, F, H 4
J - 2

a) Tracer une esquisse du réseau MPM de la planification du projet

d’entretien (matrice desantériorités et niveaux d’exécution des tâches).
b) Identifier le chemin critique et la durée du projet.
c) Dresser le tableau du programme du projet en y indiquant les marges totale,
libre et liée dechaque tâche.

2) Reprendre les questions de l’exercice d’application pour les contraintes suivantes :

Opérations durée Opérations
(mois) pré-requises
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

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 70
Recherche Opérationnelle BAC+3 MP et SCAI

3) On donne le tableau des tâches et antériorités suivant.

Tâches Activité Antériorités durée (jours)

A acceptation des plans - 4
B préparation terrain - 2
C commande matériaux A 1
D creusage fondations A,B 1
E commande portes, fenêtres A 2
F livraisons matériaux C 2
G coulage fondations D,F 2
H livraison portes, fenêtres E 10
I pose des murs, du toit G 4
J mise en place portes, fenêtre H,I 1

a) Calculer le temps minimum de réalisation du projet.

b) Finaliser le tracé du réseau MPM,.
c) Dresser le tableau des marges des tâches ou le programme du projet.
4) Un programme de construction comporte les opérations suivantes :
Tâches Tâches antérieures Durée (en jours)
A J,K 14
B - 4
C G,M 7
D - 10
E - 12
F C,L 18
G E 5
H J 11
I A,B,H 13
J B 9
K B 3
L B,K 15
M D,E 6

En utilisant la méthode MPM, déterminez la durée totale du projet, ainsi que, pour
chaque tâche, la date de début au plus tôt, la date de début au plus tard, la marge
libre, la marge totale. Quelles sont les tâches critiques pour la réalisation du projet ?
La tâche D est retardée de 3 jours. Cela implique-t-il un retard sur le délai
d’exécution du programme ?

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 71
Recherche Opérationnelle BAC+3 MP et SCAI

5) Lors d’un stage, votre responsable en entreprise vous demande d’exécuter un travail.
Après avoir recensé les différentes tâches que vous aurez à réaliser, vous estimez
leur duréed’exécution et disposez du tableau suivant :

Tâches Tâches antérieures durée (enjours)

A H 4
B A,G,J 8
C E 14
D - 12
E - 8
F E 6
G D,K,J 6
H - 8
I J,K 10
J H 6
K E,D,F 8

A partir de la représentation MPM ou PERT, définir le calendrier au plus tôt, au plus

tard, lesmarges totales et libres, ainsi que les tâches critiques.
En fait vous ne disposez que de 30 jours effectifs de stage. Vous informez votre
responsable que letravail ne pourra être achevé pendant le stage.
Il examine votre planning et estime que la durée de certaines tâches peut être réduite
(vos estimations étaient trop larges et on vous aidera dans la réalisation de certaines
opérations).
Voici les réductions possibles :

Tâches A B C D E F G H I J K
Réduction 0 2 0 0 4 0 2 0 1 2 0

Quelles sont les tâches que vous réduirez pour que le projet ne dure que 30 jours ?
Dressez la liste des tâches critiques. (On s’attachera à réduire les tâches critiques en
commençant par les tâches finales.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 72
Recherche Opérationnelle BAC+3 MP et SCAI

Chapitre 4 : LES PROBLEMES DE FLOTS DANS LES GRAPHES

4.1. Notions

De nombreux problèmes de gestion présentent une analogie avec l’écoulement d’un

flot dans des canalisations. C’est le cas, notamment, de certains problèmes de transport où l’on
cherche à acheminer, d’un lieu vers un autre, des flux de marchandises donnés, alors que les
voies de communications ont des capacités limitées. Soulignons que les problèmes de transport
ne sont pas les seuls à recevoir une solution par les méthodes qui seront exposées dans ce
chapitre. Ainsi en est-il des problèmes de « transfèrement », par exemple les problèmes
d’affectation abordés au chapitre 5. En outre, un problème de flot se transforme très rapidement
en un problème de coût minimal.

4.2. Formalisation du problème de flot maximal

La formulation du problème de flot maximal demande tout d’abord de définir les

deux notions suivantes : réseau de transport et flot sur un graphe.

4.2.1. Réseau de transport

On appelle « réseau de transport » un graphe fini G sans boucles, où à chaque arc

(i,j) est associé un nombre C(i, j)  0, appelé « capacité de l’arc ij » et où :

 Il existe un sommet x0 et un seul tel que -1 x0 : ce sommet x0 est appelé l’entrée du
réseau ;

 Il existe un sommet xn et un seul tel que  xn   : ce sommet xn est appelé la sortie du

réseau. Les capacités de transport peuvent représenter des tonnages disponibles sur des
bateaux, des camions, des wagons, ou encore des débits des oléoducs, canalisations,
voies de transmissions, etc.

4.2.2. Flot sur un graphe

Un flot  du réseau est une quantité (i, j) associée à chaque arc (i, j) du réseau tel
que :

(4.1)

(4.2)

(4.3)

La relation (4.2) établit que pour tout sommet x, la somme algébrique des flux entrant dans x est

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 73
Recherche Opérationnelle BAC+3 MP et SCAI

égale à la somme algébrique des flux sortants. Cette égalité est dite équation de nœud par
analogie aux modèles physiques et aux lois de Kirchhoff2 en électricité.

4.2.3. Enoncé du problème

Soit x0 l’afflux au point x0 ou la « valeur du flot x0 ». Le problème devient alors de

chercher un flot maximal dans un réseau, c’est-à-dire de trouver dans le réseau de transport G
un flot x0 satisfaisant aux contraintes 0  (i, j)  C(i, j) et rendant maximal l’afflux au sommet
x0. Ceci correspond au problème de programmation suivant :

(4.4)

(4.5)

4.3. Détermination du flot maximal par l’algorithme de Ford et Fulkerson

Nous définissons dans un premier temps les concepts « saturé » et « complet »,

puis développons les différentes étapes de l’algorithme.

Un arc (i, j) est dit saturé si (i, j) = C(i, j).

Un chemin est dit saturé si au moins un des arcs qui le composent est saturé.

Un flot est dit complet s’il n’y a plus sur le graphe de chemin de x0 à xn non saturé.

L’algorithme de Ford et Fulkerson fournit un processus de résolution par itérations

successives. Le mécanisme de calcul est décrit en considérant qu’un flot circule déjà sur le
graphe, c’est-à-dire que des flux (i, j) sont affectés à chaque arc (i,j).

Dans l’étape initiale, il s’agira éventuellement d’un flot nul. Les étapes de cet algorithme sont
les suivantes :

4.3.1. Détermination d’un flot au jugé

Dans un premier temps, on détermine un flot « approximatif » ou sommaire

respectant les conditions de capacité et de conservation énoncées plus loin. Le flot nul qui à tout
arc (i, j) associe (i, j) = 0 est toujours possible, mais pour aboutir plus vite à l’optimum, on peut
essayer de partir d’un flot de valeur supérieure.

2
Il s’agit en particulier de la première loi de Kirchoff
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 74
Recherche Opérationnelle BAC+3 MP et SCAI

4.3.2. Détermination d’un flot complet

Rappelons qu’un flot est dit complet si et seulement si tous les chemins du graphe
sont saturés. Les chemins non saturés, s’il en existe, peuvent être saturés en ajoutant au flot de
chacun de ses arcs la quantité d avec :

d = Min [C(i, j) – (i, j)]. (4.6)

La quantité

C(i, j) – (i, j) (4.7) est dite « capacité résiduelle de l’arc (i, j) ».

4.3.3. Détermination d’un flot maximal à partir d’un flot complet

Définition

On appelle chaîne de x0 à xn, une suite ordonnée des sommets (x0, x1, …, xi, xi+1, …,
xn) telle que pour tout xi ≠ xn,

xi+1  G(xi) xi+1 est un suivant de xi (4.8)

ou xi +1  P(xi) xi +1 est un précédent de xi (4.9)

En d’autres termes, il y a une chaîne de x0 à xn, si on peut aller de x0 à xn en suivant

les arcs dans les sens des flèches ou en sens inverse.

Une chaîne est dite saturée :

si, parmi tous les arcs parcourus dans le sens des flèches, il y en a au moins un pour lequel
(xi,xi+1) = C(xi, xi+1) (4.10)

ou si, parmi tous les arcs parcourus en sens inverse des flèches, il y en a au moins un pour lequel
(xi+1, xi) = 0 (4.11)

On obtient un flot maximal lorsque toutes les chaînes sont saturées. Lorsqu’une
chaîne n’est pas saturée, on peut toujours l’améliorer en augmentant de d le flot sur les arcs de
A+ et en le diminuant de d sur les arcs de A- avec :

- d = Min [d1, d2] (4.12)

- d1 = min [C(xi, xi+1) – (xi, xi+1)] (4.13)

- d2 = min [(xi +1, xi)] (4.14)

- A+ = l’ensemble des arcs parcourus dans le sens des flèches sur la chaîne non saturée
trouvée ;

- A- = l’ensemble des arcs parcourus dans le sens inverse des flèches sur la même
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 75
Recherche Opérationnelle BAC+3 MP et SCAI

chaîne.

4.4. Application aux problèmes de circulation

Une application intéressante de la théorie des graphes est la représentation et la

résolution des problèmes de « circulation ». Considérons par exemple le schéma ci-dessous qui
représente l’ensemble des liaisons routières permettant de nous rendre de la localité E vers la
localité S. Notons que chacune de ces liaisons est à sens unique.

A ce schéma peut être associé un graphe dont les sommets correspondent :

- aux localités de départ et d’arrivée. Le sommet E sera dit « entrée du réseau » car E n’a pas de
précédent et S « sortie du réseau » car c’est un sommet sans suivant.

- aux intersections de routes (tous les autres sommets qui seront appelés « nœuds de transit ».
Les arcs correspondent aux liaisons routières et sont orientés dans le même sens.

On obtient ainsi le graphe suivant :

Le problème à résoudre est de déterminer le flux maximum de voitures qui peuvent

se rendre de E à S. Par flux, il faut entendre un certain nombre de véhicules par heure. On
raisonnera par la suite en régime stationnaire (débit constant), en supposant qu’il ne se forme de
file d’attente en aucun point du réseau. Associons à chaque arc (i, j) un nombre C(i, j) qui est la
capacité de l’arc joignant le sommet i au sommet j. Ce nombre est le nombre maximum de
véhicules que chaque route peut faire passer chaque heure, celui-ci est fonction de la largeur de

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 76
Recherche Opérationnelle BAC+3 MP et SCAI

la route, de la vitesse maximale autorisée, du caractère plus ou moins accidenté, etc. Associons
également à chaque arc (i, j) un nombre (i, j) appelé flot sur l’arc (i, j). C’est la circulation
réelle sur chaque route. Les capacités sont données par les nombres encerclés du graphe 3.2 (en
milliers de véhicules par heure). Les nombres non encadrés portés sur les arcs se rapportent au
flot sur chaque arc. Nous faisons l’hypothèse que le flux de véhicules (flot) est constant le long
de chaque arc (aucun ne s’arrête en route) et à chaque nœud de transit, il arrive autant de
véhicules qu’il en repart (principe de la conservation du flot).

Sur le graphe, les nombres non encadrés sur les arcs respectent ces conditions. Un
flux de 6.000 véhicules par heure entre E et S est donc compatible avec la capacité des routes (6
= 2 + 3 + 1 flux partant de E = 4 + 2 = flux arrivant en S). Le flot sur chaque arc doit
respecter la contrainte de capacité (4.4).

Pour trouver un flot complet sur le graphe ci-haut, on cherche un chemin non saturé
de E à S. Reprenons le graphe ci-haut où l’on reporte le flot de départ en marquant les arcs
saturés. On a :

Le chemin (E, 4, S) est non saturé. Pour le saturer, on ajoute au flot de chacun de ses arcs la
quantité Min [C(i, j) – (i, j)]. Sur le graphe, c’est l’arc (E, 4) sur le chemin non saturé qui nous
donne la capacité résiduelle minimum qui est égale à C(E, 4) – (E, 4) = 2 – 1 = 1. En l’ajoutant
au flot de chaque arc du chemin non saturé (E, 4, S), on obtient le nouveau flot du graphe qui
donne aussi les arcs saturés.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 77
Recherche Opérationnelle BAC+3 MP et SCAI

Ce flot est complet car il n’existe aucun chemin non saturé de E à S. Mais ce flot n’est pas
nécessairement maximum. En effet, sur le graphe du graphe ci-haut, la chaîne (E, 2, 1, 3, 4, S)
n’est pas saturée. Sur cette chaîne non saturée, la capacité résiduelle minimale sur les arcs de
A+ est 4 – 3 = 1. Le flot minimal sur les arcs de A- est 1. On modifie donc le flot selon les
règles énoncées plus haut (augmenter de d = min [d1, d2] le flot sur les arcs de A+ et le
diminuer de d sur les arcs de A- ). On obtient alors le graphe ci-après :

Sur cette dernière figure, il existe encore une chaîne non saturée de E à S. C’est la chaîne (E, 1,
3, 4, S). La valeur de d sur cette chaîne est égale à 2. On obtient ainsi le flot du graphe ci-après :

Puisque toutes les chaînes de ce graphe sont maintenant saturées, le flot ainsi obtenu est
maximal, avec (S) = 10.

4.5. Problème (Exercice) d’application

Une société agro-industrielle dispose de café brut dans les Centres d’exploitation
suivants :
- Aketi (A), Bumba (B), Kikwit (K) et Manterne (M).
Elle doit assurer l’approvisionnement de ses différentes usines de torréfaction
situées à Faradji (F), Likasi (L), Tumba (T) et Uvira(U). Le tableau ci-dessous donne en
milliers de tonnes:

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 78
Recherche Opérationnelle BAC+3 MP et SCAI

- les quantités disponibles dans chaque usine d’exploitation;

- la demande de chaque usine de torréfaction ;

- les capacités de transport disponibles sur des véhicules assurant la liaison entre les différentes
origines et les usines de traitement.

Tableau : Capacités de transport entre les centres d’exploitation et les centres de

torréfaction ainsi que les demandes et les quantités disponibles en milliers de tonnes
Destination F L T U Stocks disponibles

Origine
Aketi 150 100 50 - 200
Bumba 150 150 50 50 350
Kikwit 100 100 200 400
Manterne 200 100 200
Demande 300 400 200 200
On demande de définir les quantités à transporter de chaque origine vers chaque
destination de façon à satisfaire au maximum la demande des usines de traitement.
Solution
On construit un graphe dont les sommets correspondent aux centres d’origine et
aux usines de traitement, les arcs représentant les différentes possibilités de transport avec les
capacités disponibles. Les sommets correspondant aux centres origine sont reliés au sommet
d’entrée E par un arc dont la capacité est égale au stock disponible. Les sommets correspondant
aux usines de traitement sont reliés au sommet de sortie S par un arc dont la capacité est égale à
la demande. Il conviendra de rendre maximale la valeur de (S) indiquant la demande satisfaite.
Première étape : Détermination d’un flot au jugé.

Il est proposé ci-après un flot qu’il faudra par la suite optimiser. Les valeurs en
gras sont les flots.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 79
Recherche Opérationnelle BAC+3 MP et SCAI

Deuxième étape : Détermination d’un flot complet

On vérifie si le flot du graphe, égal à 900 tonnes, est complet. Rappelons qu’un flot
est dit complet si tous les chemins du graphe de E a S sont saturés, c’est-à-dire ont un arc au
moins pour lequel la capacité, C(i, j), est égale au flot (i, j). On constate que les chemins E, K,
U, S et E, M, U, S ne sont pas saturés. Donc le flot du graphe n’est pas complet. Considérons le
premier chemin non saturé E, K, U, S. La capacité résiduelle minimale est 200 – 150 = 50. En
augmentant le flot de cette quantité sur chacun des arcs du chemin, le flot passe à 950. Ce flot
est maintenant complet car l’arc (U, S) est devenu saturé (le deuxième chemin empruntant le
même arc l’est devenu aussi).

Troisième étape : Détermination du flot maximal

Bien que complet, le flot obtenu n’est pas maximal car la chaîne E, M, T, A, L, S
est non saturé. On calcule alors d = min {d1, d2} par la formule (4.12) ; ce d étant égal à 50, on
ajoute cette quantité au flot des arcs parcourus dans le bon sens et on la retranche au flot des
arcs parcourus en sens inverse. D’où le graphe sur lequel toutes les chaînes de E à S sont à
présent saturées. Ce flot est alors égal à 1000 tonnes.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 80
Recherche Opérationnelle BAC+3 MP et SCAI

Flot maximal = 1000 tonnes

Solution optimale

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 81
Recherche Opérationnelle BAC+3 MP et SCAI

Chapitre 5 : LES PROBLEMES DE TRANSPORT,

D’AFFECTATION ET DU VOYAGEUR DE COMMERCE
5.1. Généralités
De nombreux problèmes de gestion présentent une analogie avec l’écoulement d’un
flot dans des canalisations. C’est le cas, notamment, de certains problèmes de transport où l’on
cherche à acheminer, d’un lieu vers un autre, des flux de marchandises donnés, alors que les
voies de communications ont des capacités limitées. Soulignons que les problèmes de transport
ne sont pas les seuls à recevoir une solution par les méthodes qui seront exposées dans ce
chapitre. Ainsi en est-il des problèmes de « transfèrement », par exemple les problèmes
d’affectation. En outre, un problème de flot se transforme très rapidement en un problème de
coût minimal.
5.2. Problèmes du Transport
a) Définition
En mathématique, en économie et en informatique, la théorie du transport est le
nom donné à l’étude du transfert optimal de matière et à l’allocation optimale de ressources.
Le problème a été formalisé par le mathématicien français Gaspar MONGE en 1781.
D’importants développement ont été réalisés dans ce domaine pendant la Seconde Guerre
mondiale par le mathématicien et économiste russe Léonid KANTOROVITCH. Par
conséquent, le problème dans sa forme actuelle est parfois baptisé problème (du transport) de
Monge-Kantorovitch.
b) Présentation et formalisation
Un problème de transport peut être défini comme l’action de transporter depuis "m
origines" vers "n destinations" des matériaux, au moindre coût. Donc, la résolution d’un
problème de transport consiste à organiser le transport de façon à minimiser son coût.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 82
Recherche Opérationnelle BAC+3 MP et SCAI

c) Méthode de résolution: recherche d’une solution de base réalisable

1) Solution de base
On appelle solution de base d'un programme de transport, une solution admissible
comportant M= (m+n-1) xij>0, c’est-à-dire qu’une solution de base comporte (m.n – M) zéros.
Le graphe d’une solution de base est un graphe connexe sans cycle, c’est-à-dire un arbre
comportant N=m+n sommets soit M=N-1 arcs. (Un graphe est connexe s’il existe au moins une
chaîne entre toute paire de sommets. Une chaine qui se ferme sur elle-même est un cycle.).
2) Méthode du COIN NORD-OUEST :

La méthode du coin Nord-Ouest, ou MCNO (North-west Corner Method,

NWCM), est utilisée pour trouver une solution à un programme de transport sans prise
en compte du coût.
- Présentation : La méthode du coin nord-ouest est une méthode facile mais elle n’a pas de
sens économique. Puisqu’elle consiste à affecter au coin nord-ouest de chaque grille la quantité
maximale possible sans se préoccuper de l’importance du coût.
- Principe : On considère à chaque étape, le Nord-Ouest de la grille. On part donc de la route
(i1, j1) ; on sature soit la ligne i 1 soit la colonne j1. Puis on recommence sur la sous-grille
formée des lignes et des colonnes non saturées.
Cette procédure aboutit en général à une solution de base. Si à chaque choix d’une
relation, on a épuisé une demande ou une disponibilité mais non les deux, (sauf pour la
dernière), donc on a sélectionné (m + n – 1) liaisons et obtenu (m -1)(n – 1) zéros.
- Application de la méthode du coin nord-ouest
Exemple 1 :
Exemple Initialement
Soit la matrice du transport ci-après :
Coûts / Besoins / Stocks
Sources/Destinataires 1 2 3 4 5 Stocks
1 10 6 3 5 25 49
2 5 2 6 12 5 30
Demandes 15 20 5 25 14

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 83
Recherche Opérationnelle BAC+3 MP et SCAI

Par le méthode du Nord-Ouest, déterminer le coût.

Transports
Sources/Destinataires 1 2 3 4 5
1
2

Étape 1 :

Coûts / Besoins / Stocks

Sources/Destinataires 1 2 3 4 5 Stocks
1 10 6 3 5 25 49
2 5 2 6 12 5 30
Demandes 15 20 5 25 14

Transports
Sources/Destinataires 1 2 3 4 5
1 15
2 0

Etape 2

Coûts / Besoins / Stocks

Sources/Destinataires 1 2 3 4 5 Stocks
1 10 6 3 5 25 49-15= 34
2 5 2 6 12 5 30
Demandes 0 20 5 25 14

Transports
Sources/Destinataires 1 2 3 4 5
1 15 20
2 0 0

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 84
Recherche Opérationnelle BAC+3 MP et SCAI

Étape 3

Coûts / Besoins / Stocks

Sources/Destinataires 1 2 3 4 5 Stocks
1 10 6 3 5 25 34-20= 14
2 5 2 6 12 5 30
Demandes 0 0 5 25 14

Transports
Sources/Destinataires 1 2 3 4 5
1 15 20 5
2 0 0 0

Étape 4

Coûts / Besoins / Stocks

Sources/Destinataires 1 2 3 4 5 Stocks
1 10 6 3 5 25 14-5= 9
2 5 2 6 12 5 30
Demandes 0 0 0 25 14

Transports
Sources/Destinataires 1 2 3 4 5
1 15 20 5 9
2 0 0 0 16

Etape 5

Coûts / Besoins / Stocks

Sources/Destinataires 1 2 3 4 5 Stocks
1 10 6 3 5 25 0
2 5 2 6 12 5 30-16= 14
Demandes 0 0 0 0 14

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 85
Recherche Opérationnelle BAC+3 MP et SCAI

Transports
Sources/Destinataires 1 2 3 4 5
1 15 20 5 9 0
2 0 0 0 16 14

Coût de la solution
La solution trouvée avec cette méthode n'est pas optimale en termes de coût.

On trouve ici : 15*10 + 20*6 + 5*3 + 9*5 + 0*25 + 0*5 + 0*2 + 0*6 + 16*12
+ 14*5 = 592.
Exemple2 :
Soit, la société Alpha possédant quatre dépôts A1, A2, A3 et A4 dans lesquels
existent des quantités respectives de 896, 782, 943, 928 unités d’une matière première, et cinq
usines D1, D2, D3 , D4 et D5 demandant respectivement 800, 439, 50, 790 et 1470 unités de
celles-ci. Les coûts de transport, C ij, sont donnés par le tableau ci-dessous. Comment
organiser le transport au moindre coût total?

Première étape :
A1-D1 est le coin Nord-Ouest, on lui affecte min (800;896) soit 800 unités demandées par D1et
fournies en A1.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 86
Recherche Opérationnelle BAC+3 MP et SCAI

On sature ainsi la demande D1 dont la colonne disparaît et on obtient le tableau 2

pour lequel le coin N-O est A1-D2.

Deuxième étape : A1-D2 est le coin N-O, on lui affecte 96 unités demandées par D2 et fournies
en A1.

On sature ainsi l’offre en A1, qui disparaît. On obtient le tableau 3 pour lequel le
coin N-O est A2-D2.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 87
Recherche Opérationnelle BAC+3 MP et SCAI

Troisième étape :
A2-D2 est le coin N-O, on lui affecte 343 unités demandées par D2 et offert par A2.

On satisfait ainsi la demande D2, qui disparaît. On obtient le tableau 4 pour lequel le
coin N-O est A2-D3.

Quatrième étape : A2-D3 est le coin N-O, on lui affecte 50 unités fournies par A2 et demandée
en D3.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 88
Recherche Opérationnelle BAC+3 MP et SCAI

On sature la demande D3, qui disparaît. On obtient le tableau 5 pour lequel le coin
N-O est A2-D4.

Cinquième étape : A2-D4 est le coin N-O, on lui affecte 389 unités fournies par A2 et
demandée par D4.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 89
Recherche Opérationnelle BAC+3 MP et SCAI

On sature l’offre A2, qui disparaît. On obtient le tableau 5 pour lequel le coin N-O est A3-D4.

Sixième étape : A3-D4 est le coin N-O, on lui affecte 401 unités fournies par A3 et demandée
par D4.

On sature la demande D4, qui disparaît. On obtient le tableau 5 pour lequel le coin N-O est A3-
D5.

Dernière étape : Il ne reste qu'une colonne D5 on affecte aux liaisons existantes le transport de
façon évidente

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 90
Recherche Opérationnelle BAC+3 MP et SCAI

Nous avons ainsi obtenu une solution de base réalisable puisque la condition
d’avoir (n -1)(m -1) variables nulles dans la solution est satisfaite (12 cases vides dans le dernier
tableau).

Le coût de cette solution de base est de :

Le coût de cette solution est : 800* 21+ 96*11+ 343* 52 + 50* 43 + 389* 29 + 401* 80 +
542*93 + 928*54 = 181 721 UM
3) Méthode de BALAS – HAMMER
- Présentation :
Cette méthode est basée sur le calcul des regrets. Le regret associé à une ligne ou à
une colonne est la différence entre le coût minimum et le coût immédiatement supérieur dans
cette ligne ou dans cette colonne. C’est une mesure de la priorité à accorder aux transports de
cette ligne ou de cette colonne, car un regret important correspond à une pénalisation importante
si on n’utilise pas la route de coût minimum. La méthode de Balas-Hammer fournit, en
général, une solution très proche de l’optimum; le nombre de changements de base nécessaires
pour arriver à une solution optimale est peu élevé (il arrive même assez fréquemment que la
solution donnée par cette règle soit optimale).
- Principe :
D’abord, on calcule pour chaque rangée, ligne ou colonne, la différence entre le coût
le plus petit avec celui qui lui est immédiatement supérieur. Ensuite on affecte à la relation de
coût le plus petit correspondant à la rangée présentant la différence maximale la quantité la plus

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 91
Recherche Opérationnelle BAC+3 MP et SCAI

élevée possible. Ce qui sature une ligne ou une colonne. Et on reprendre le processus jusqu'à ce
que toutes les rangées soient saturées.
- L’algorithme de Balas -Hammer:
∆l représente la différence entre le coût minimum et celui immédiatement supérieur
sur une ligne. ∆c représente la différence entre le coût minimum et celui immédiatement
supérieur sur une colonne.
1) Calculer les différences ∆l et ∆c pour chaque ligne et colonne.
2) Sélectionner la ligne ou la colonne ayant le ∆l ou ∆c maximum.
3) Choisir dans cette ligne ou colonne le coût le plus faible.
4) Attribuer à la relation (i, j) correspondante le maximum possible de matière
transportable de façon à saturer soit la destination soit la disponibilité.
5) calculer la quantité résiduelle soit demande soit en disponibilité.
6) Eliminer la ligne ou la colonne ayant sa disponibilité ou demande satisfaite.
7) SI nombre de lignes ou colonnes> 2 retour en 2. SINON affecter les quantités
restantes aux liaisons.
- Application de l’algorithme de Balas-Hammer
Exemp1e1
Données initiales
- Tableau représentant les coûts entre des sources et des destinataires, ainsi queles
stocks disponibles pour les sources et les demandes des destinataires :
Coûts / Besoins / Stocks
Sources/Destinataires 1 2 3 4 5 Stocks
1 10 6 3 5 25 49
2 5 2 6 12 5 30
Demandes 15 20 5 25 14

- Calcul des regrets

Coûts / Besoins / Stocks / Regrets

Sources/Destinataires 1 2 3 4 5 Stocks Regrets
1 10 6 3 5 25 49 5-3=2
2 5 2 6 12 5 30 5-2=3
Demandes 15 20 5 25 14
Regrets 10- 6- 6- 12- 25-
5=5 2=4 3=3 5=7 5=20

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 92
Recherche Opérationnelle BAC+3 MP et SCAI

- Le regret le plus important est celui de la colonne 5 : 20. Dans cette rangée, on
repère le coût minimal : C(2,5) = 5.
- Remplissage de la matrice des transports
-
Transports
Sources/Destinataires 1 2 3 4 5
1 0
2 14

- Réitération du principe

Coûts / Besoins / Stocks / Regrets

Sources/Destinataires 1 2 3 4 Stocks Regrets
1 10 6 3 5 49 5-3=2
2 5 2 6 12 30-14=16 5-2=3
Demandes 15 20 5 25
Regrets 10-5=5 6-2=4 6-3=3 12-5=7

- ETC...
- Résultat
- On en arrive à établir le tableau des transports :
-
Transports
Sources/Destinataires 1 2 3 4 5
1 0 19 5 25 0
2 15 1 0 0 14

- Le coût total se calcule par un produit scalaire entre les matrices des coûts et des
transports.
- Ici, le coût optimal est donc : 0*10 + 19*6 + 5*3 + 25*5 + 0*25 + 15*5 + 1*2 + 0*6
+ 0*12 + 14*5 = 401
Exemple 2 : Reprenons l’exemple précédant, et cherchons une solution de base par l’algorithme
de Balas-Hammer.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 93
Recherche Opérationnelle BAC+3 MP et SCAI

Première étape :

Deuxième étape :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 94
Recherche Opérationnelle BAC+3 MP et SCAI

Troisième étape :

Quatrième étape :

Cinquième étape :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 95
Recherche Opérationnelle BAC+3 MP et SCAI

Sixième étape :

Septième étape :

Dernière étape :
Il nous reste qu’une source non épuisée A3, on l’affecte à D5 qui demande
exactement 85 unités. Enfin, la solution de base est :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 96
Recherche Opérationnelle BAC+3 MP et SCAI

Son coût est : 439*11+457*13+782*29+800*11+50*14+8*80+85*93+928*54 = 101.605 UM

5.3. Problèmes d’Affectation
a) Définition
En informatique, plus précisément en Recherche Opérationnelle et l’optimisation
combinaison, le problème d’affectation consiste à attribuer aux lieux des tâches à des
agents. Chaque agent peut réaliser une unique tâche pour un coût donné et chaque tâche doit
être réalisée par un unique agent. Les affectations (c-à-d les couples agent-tâche) ont toutes
un coût défini. Le but est de minimiser le coût total des affectations afin de réaliser toutes
les tâches.
b) Présentation et formalisation
Il s’agit d’un cas particuliers du problème de transport avec n entrepôts et n
magasins, et où la demande associée à chaque destination égale à 1. Le problème consiste à
affecter les éléments d’un ensemble à ceux d’un autre ensemble de sorte que la somme des coûts
des affectations soit minimale.
Supposons que, dans une entreprise, n ouvriers puissent travailler indifféremment
sur n machines, mais avec plus ou moins d'efficacité. L'efficacité peut se mesurer par le revenu
provenant de la vente des produits fabriqués par les divers ouvriers travaillant sur les différentes
machines. L'unité i exécute la tâche j avec un coût ou un profit cij. Comment doit-on affecter
chaque unité à une seule tâche pour que la rentabilité soit optimale ?
La matrice des coûts (profits) associée est C =

Le programme à résoudre est :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 97
Recherche Opérationnelle BAC+3 MP et SCAI

Plusieurs algorithmes permettent de résoudre le problème d’affectation, pour ce

cours on développera l’uniquement l’algorithme Hongroise.
c) La méthode Hongroise
- 1) Présentation
Cet algorithme repose essentiellement sur la constatation suivante. On ne change pas
la ou les solutions optimales en augmentant ou en diminuant d'une même quantité ߣtous les
éléments d'une même ligne (ou d'une même colonne) de la matrice des Cij.
Après une telle opération, la valeur totale est augmentée ou diminuée de . ߣ Par
conséquent, si l'on fait apparaître, par des transformations de ce type, suffisamment de zéros
dans le tableau, mais pas de coûts négatifs, et qu'il existe n zéros "indépendants" (c'est-à-dire un
seul zéro dans chaque ligne et dans chaque colonne), on aura alors trouvé l'affectation optimale.
2) Résolution d’un problème d’affectation par la Méthode de Khun (Algorithme
hongrois)
Afin d'expliquer la démarche suivie, considérons l'exemple suivant :
Soit La société Beta possédant quatre ateliers : fonte, moulage, laminage et
traitement thermique, qu’on va nommer respectivement F, M, L et T, pour lesquels elle veut
affecter quatre chef de service polyvalents, monsieur A, B, C et D.
Les coûts d’affectation pour chaque liaison sont donnés par le tableau ci-dessous.
Comment organiser l’affectation de façon à en minimiser le coût?

Première étape :
Réduction des lignes : on crée une nouvelle matrice des coûts en choisissant le coût
minimal sur chaque ligne et en le soustrayant de chaque coût sur la ligne.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 98
Recherche Opérationnelle BAC+3 MP et SCAI

Exemple : pour la première ligne (A) :

 Relation (A, F) : 60 -60 = 0
 Relation (A, M) : 170-60=110
 Relation (A, L) : 330-60=270
 Relation (A, T) : 360-60=300
Deuxième étape :
Réduction des colonnes : on crée une nouvelle matrice des coûts en choisissant le
coût minimal dans chaque colonne et en le soustrayant de chaque coût dans la colonne.
Troisième étape :
Maintenant, il faut déterminer le nombre minimal de lignes nécessaires sur les
lignes et les colonnes pour couvrir tous les zéros. Si ce nombre est égal au nombre de lignes
(ou colonnes), la matrice est réduite; aller à l’étape 5. Si ce nombre est inférieur au nombre de
lignes (ou colonnes), aller à l’étape 4.

Dans ce cas, le nombre minimal de lignes est de 3 qui est inférieur au nombre de
ligne ou colonne (4), alors on passe à l’étape 4.
Quatrième étape :
Premièrement, il faut trouver la cellule de valeur minimum non couverte par une
ligne, puis, soustraire cette valeur de toutes les cellules non couvertes. Ensuite, ajouter cette
valeur aux cellules situées à l’intersection de deux lignes. Et enfin, retourner à l’étape 3.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 99
Recherche Opérationnelle BAC+3 MP et SCAI

La valeur minimum des cellules non couvertes est 20. On soustrait 20 des cellules
non couvertes et on l’ajoute aux cellules qui se trouvent à l’intersection des lignes, ceci nous
donne le tableau suivant :

Maintenant, le nombre minimal de ligne est égale à 4.

La solution optimale est donc la suivante :

Résultat donné par la méthode Hongroise :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 100
Recherche Opérationnelle BAC+3 MP et SCAI

La solution à pour coût :

Le coût total= 60 + 200 + 180 + 90 = 530 UM pour les affectations :

A
B
C
D

d) Cas de maximisation
La même technique s'applique à la recherche d'un maximum. Il suffit, au départ,
de transformer le problème en un problème à minimum soit en changeant le signe tous les
termes de la matrice, soit en retranchant tous les éléments de la matrice d'un nombre au moins
égal au plus grand de ces éléments. En appliquant la technique, on minimise ainsi l'écart par
rapport à un certain plafond. Il est évident que le maximum du problème d'affectation formé
avec les cij correspond au minimum de celui formé avec les c"ij. On recherche la solution
optimale du tableau formé avec les c"ij.
Example
Le Chef de Section des SCAI doit affecter 5 enseignants aux cours suivants :
Info et Bureautique, Algo1, RO, Gestion des Stocks et Théorie des Graphes. Le Chef de
Section souhaite affecter ces enseignants en optimisant leurs aptitudes à enseigner les cours
souhaités. Ces aptitudes sont mesurées par les cotes obtenues dans ces différentes branches à
l’ISP-Uvira. Elles sont données dans le tableau ci-dessous.
Info et Algo1 RO GeStock Théorie des
Bureautique Graphes
E1 15 09 07 08 02
E2 03 17 04 10 09
E3 06 06 08 07 16
E4 11 02 16 16 11
E5 18 15 03 12 09
Etant un problème de maximisation, il est nécessaire, avant d’appliquer la méthode
hongroise, de transformer préalablement les données du tableau ci-haut, soit en les multipliant
par -1 soit en les retranchant de la donnée la plus élevée, ici 18.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 101
Recherche Opérationnelle BAC+3 MP et SCAI

Info et Algo1 RO GeStock Théorie Min Info et B. Algo1 RO GeStock Théorie des G Min
des G
B.
E1 -15 -09 -07 -08 -02 -15 E1 3 9 11 10 16 3
E2 -03 -17 -04 -10 -09 -17 E2 15 1 14 8 9 1
E3 -06 -06 -08 -07 -16 -16 E3 12 12 10 11 2 2
E4 -11 -02 -16 -16 -11 -16 E4 7 16 2 2 7 2
E5 -18 -15 -03 -12 -09 -18 E5 0 3 15 6 9 0

On appliquera ensuite la méthode hongroise au problème ainsi transformé, en

commençant par l’étape d’obtention de zéros. On constatera que les deux tableaux donneront une
matrice identique.
Info et B. Algo1 RO GeStock Théorie des G Matrice réduit de :

E1 0 6 8 7 13 3

E2 14 0 13 7 8 1

E3 10 10 8 9 0 2

E4 5 14 0 0 5 2

E5 0 3 15 6 9 0

Dans ce cas ci-haut s, le nombre minimal de lignes est de 4 qui est inférieur au
nombre de ligne ou colonne (5), alors on passe à l’étape suivante.
- Premièrement, il faut trouver la cellule de valeur minimum non couverte par une ligne,
puis, soustraire cette valeur de toutes les cellules non couvertes. Ensuite, ajouter cette
valeur aux cellules situées à l’intersection de deux lignes. Et enfin, retourner à l’étape
précédente.
- La valeur minimum des cellules non couvertes est 3. On soustrait 3 des cellules non
couvertes et on l’ajoute aux cellules qui se trouvent à l’intersection des lignes, ceci nous
donne le tableau suivant :

Info et B. Algo1 RO Ge Stock Théorie des G

E1 0 6 8 7 13

E2 14 0 13 7 8

E3 10 10 8 9 0 -3
+3
E4 5 14 0 0 5

E5 0 3 15 6 9

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 102
Recherche Opérationnelle BAC+3 MP et SCAI

Le minimum est 3

Les cellules non couvertes sont :

6 8 7 13

3 15 6 9

Info et B. Algo1 RO Ge Stock Théorie des G

E1 0 6 5 4 10

E2 17 0 13 7 8

E3 13 10 8 9 0
E4 7 14 0 0 5

E5 0 0 12 3 6

Info et B. Algo1 RO Ge Stock Théorie des G

E1 0 6 5 4 10
E2 17 0 13 7 8
E3 13 10 8 9 0
E4 7 14 0 0 5
E5 0 0 12 3 6
La solution au problème est :

Enseignants Cours Coût

E1 I. B 15
E2 Algo 17
E3 RO 16
E4 Ge Stock 12
E5 Théorie des G 16
Total 76

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 103
Recherche Opérationnelle BAC+3 MP et SCAI

e) Cas particulier (Nombre d’Ouvriers est différents au nombres de tâches et vice versa)
N M ( avec N= nombre de tâches et M = nombre d’ouvriers)
1) Nombre d’Ouvriers Nombre de tâches (M N)
Dans ce cas, on recherche la fonction de séparation uniquement sur les
lignes. Certaines tâches ne seront pas exécutées.
Choisir B(S0) =∑
( )
( ) ( )
1) Nombre de Tâches Nombre d’Ouvriers (N M)
Dans ce cas, on recherche la fonction de séparation uniquement sur les
colonnes.
Certains ouvriers ne seront pas affectés.
Choisir B(S0) =∑
( )
( ) ( )
Exemple : Trouver une affectation au moindre coût des ouvriers aux tâches, la
matrice des coûts étant :

Cij T1 T2 T3 T4 T5 T6
1 30 25 41 14 28 24
2 7 28 18 3 32 27
3 20 13 21 32 6 0
4 21 16 25 13 18 18

Etape 1 ( On cherche le minimal de chaque ligne et on le réduit ligne par ligne dans la matrice)

Cij T1 T2 T3 T4 T5 T6
Ci (On réduit de :)
1 30 25 41 1414 28 24
2 7 28 18 3 3 32 27
3 20 13 21 320 6 0
4 21 16 25 1313 18 18
30
Etape 2 (On réitère la procédure jusqu’à la fin)
Cij T1 T2 T3 T4 T5 T6 Ci (on réduit de :)
1 16 11 27 0 14 10 14
2 4 25 15 0 29 24 3
3 20 13 21 32 6 0 0
4 8 3 12 0 5 5 13
Somme 30

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 104
Recherche Opérationnelle BAC+3 MP et SCAI

On affecte 1 T4 par la couverture des 0

La matrice devient :
Cij T1 T2 T3 T5 T6 Ci (on
réduit de :)
2 4 25 15 29 24 4
3 20 13 21 6 0 0
4 8 3 12 5 5 3
Somme 7

Etape 3
Cij T1 T2 T3 T5 T6 Ci (on
réduit de :)
2 0 21 11 25 20 4
3 20 13 21 6 0 0
4 5 0 9 2 2 3
Somme 7

2 T1
Cij T2 T3 T5 Ci (on réduit de :)
4 0 9 2 0

3 T6
Cij T2 T3 T5 Ci (on réduit de :)
4 0 9 2 0
4 T2
D’où le tableau d’affectation ( 1= affection, 0 = pas d’affectation)
Cij T1 T2 T3 T4 T5 T6
1 0 0 0 1 0 0
2 1 0 0 0 0 0
3 0 0 0 0 0 1
4 0 1 0 0 0 0

1 T4 = 14
2 T1 = 7
3 T6 = 0
4 T2 = 16
Total coût = 37
5.4. Les problèmes du voyageur de commerce
a) Notions
Le problème du voyageur de commerce est un problème célèbre en Informatique
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 105
Recherche Opérationnelle BAC+3 MP et SCAI

théorique, qui a de nombreuses applications dans des domaines variés. Il consiste à trouver,
pour un certain nombre de villes données, la boucle la plus courte passant par toutes les
villes.
b) Définition
En informatique, le problème du voyageur de commerce, ou problème du
commis voyageur, est un problème d’optimisation qui consiste à déterminer, étant donné un
ensemble de villes, le plus court-circuit passant par chaque ville une seule fois. C’est un
problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est
souvent utilisé comme introduction à l’algorithmique ou à la théorie de la complexité. Il
présente de nombreuses applications que ce soit en planification, en logistique ou dans des
domaines éloignés, comme la génétique, les gènes étant les villes et la similarité la distance.
2) Description
Etant donné n villes et leurs distances par paire, il s’agit de déterminer le
chemin le plus petit qui passe exactement une fois par chaque ville et revienne à la ville de
départ. On modélise le problème du voyageur de commerce comme un problème sur un
graphe non orienté pondéré. Les villes sont des sommets du graphe. Le voyageur emprunte
les arrêtes sur le graphe. Le coût d’une arrête entre deux (2) sommets est la distance entre
deux (2) villes correspondantes. Souvent, on considère un graphe complet c-à-d il y a une
arrête entre toutes paires de sommets : G = (V, E, ) avec V un ensemble de sommets, E = V
X V un ensemble d’arrêtes , et :E une fonction de coût sur les arrêtes. Le problème
est de trouver le plus court cycle hamiltonien dans le graphe G.
3) Formalisation du problème
Formellement, le problème du voyageur de commerce peut s’écrire comme un
programme linéaire. Ci dessous, V est l’ensemble des n sommes du graphe, x ij désigne l’arc
(i,j) et vaut 1 s’il fait partie de la solution, 0 sinon, Cij représente le poids de l’arc (i,j).

Cette matrice est parfois symétrique, les frais de déplacement de xi à xj et de xj à xi étant

identiques, mais il n'en est pas nécessairement ainsi. Si les coûts de transport au km sont égaux,
le circuit le moins coûteux est alors le plus court.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 106
Recherche Opérationnelle BAC+3 MP et SCAI

4) Résolution d’un PVC

L’algorithme, conçu par J.D.C. Little, K.G. Murty, D.W. Sweeney et C. Karel, met
en ouvre une méthode par séparation et évaluation basée sur l’heuristique du regret. Il s’agit
maintenant de résoudre le TSP dans un cadre plus général : sa version asymétrique. Le regret
est la façon d’évaluer coût, que l’on pourrait qualifier d’inopportunité, de la non-
incorporation d’un arc à la solution ; pour calculer, les distances doivent au préalable subir
une opération appelée réduction. On commence par retirer à chaque arc ⃗ ( , ) le plus petit
coût pour partir de i, soit formellement : ∀ =1,. . . .n, on note { ( )} et l’on
pose, pour tout j ’, d’ (vi,vj) = d (vi,vj)- D’. C’est en suite le plus petit coût pour arriver en
i et relativement à d’ que l’on retire :∀ = 1,. . ., n, on note D’j = { ( )} et l’on
pose d’’(vi,vj)= d’(vi,vj)- D’j pour tout i j. il est aisé de constater que la fonction d’’ ne
transforme pas l’ordre relatif des tours réalisables ; en effet, si l’on note D’ =
∑
∀ ( ) ( )
( ) .

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 107
Recherche Opérationnelle BAC+3 MP et SCAI

5) Exemple illustratif
Soit le problème du voyageur de commerce ci-après :
Cij V1 V2 V3 V4 V5 V6
V1 8 12 14 14 26
V2 13 56 35 54 20
V3 23 23 33 21 26
V4 2 7 37 15 22
V5 25 30 1 16 7
V6 20 24 10 37 21

Le problème consiste de traverser qu’une seule fois chaque ville.

Etape1 (On détermine le coût minimal par ligne) : On détermine le coût minimal de
chaque ligne, puis on fait la différence entre de tous éléments de la ligne et coût
minimal
Cij V V2 V3 V4 V5 V6 Ci (réduit
1 de) :
V1 8 12 14 14 26 8
V2 13 56 35 54 20 13
V3 23 23 33 21 26 21
V4 2 7 37 15 22 2
V5 25 30 1 16 7 1
V6 20 24 10 37 21 10
55
Etape 2 : Même opération, mais selon les colonnes.
Cij V1 V2 V3 V4 V5 V6 Ci
V1 0 4 6 6 18 0
V2 0 43 22 41 7 0
V3 2 2 12 0 5 0
V4 0 5 35 13 20 0
V5 24 29 0 15 6 0
V6 10 14 0 27 11 0
Réduit 0 0 0 6 0 5 11
de :

Etape 3 : On commence le voyage en respectant l’algorithme.

Cij V1 V2 V3 V4 V5 V6 Ci
V1 0 4 0 6 13 0
V2 0 43 16 41 2 0
V3 2 2 6 0 0 0
V4 0 5 35 13 15 0
V5 24 29 0 9 1 0
V6 10 14 0 21 11 0

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 108
Recherche Opérationnelle BAC+3 MP et SCAI

Pour éviter le cyclage, passer par C36 = , il faut aller de la ville 6 vers
ville 3 (V6 V3).
Cij V1 V2 V4 V5 V6 Ci
V1 0 0 6 13 0
V2 0 16 41 2 0
V3 2 2 6 0 0 0
V4 0 5 13 15 0
V5 24 29 9 1 1
1
Réitère l’algorithme et on a :
Cij V1 V2 V4 V5 V6 Ci
V1 0 0 6 13 0
V2 0 16 41 2 0
V3 2 2 6 0 0 0
V4 0 5 13 15 0
V5 23 28 8 0 1
V2 V1
Cij V2 V4 V5 V6 Ci
V1 0 0 6 13 0
V3 2 6 0 0 0
V4 5 13 15 5
V5 28 8 0 0

Cij V2 V4 V5 V6 Ci
V1 0 0 6 13 0
V3 2 6 0 0 0
V4 0 8 10 5
V5 28 8 0 0
V1 V4
Cij V2 V5 V6 Ci
V3 2 0 0 0
V4 0 8 10 0
V5 28 0 0
V5 V6
Cij V2 V5 Ci
V3 2 0 0
V4 0 8 0
NB : En fin de trouver un circuit hamiltonien et éviter le cyclage dans ce problème du
voyageur du commerce, on doit partir de la V3 vers la ville V2 (V3 V2 ) et de la ville V4

à la ville V5 ( V4 V5) parce que on ne peut plus affecter V3 V5 car ça créera un

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 109
Recherche Opérationnelle BAC+3 MP et SCAI

retour vers l’origine sans passer par d’autres villes.

Solution
V6 V3 = 10
V5 V6 =7
V3 V2=23
V4 V5=15
V1 V4 =14
V2 V1 =13
Le coût total minimal est de 82.

Le circuit est ainsi formé par les villes ci-après:

V6 V3

V5 V2

V4 V1

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 110
Recherche Opérationnelle BAC+3 MP et SCAI

Chapitre 6 : LES PROBLEMES DE GESTION DES STOCKS ET

DE REMPLACEMENT DES EQUIPEMENTS
La gestion des stocks est une fonction fondamentale pour la majorité des fonctions
donc une mauvaise gestion des stocks peut compromettre sérieusement les activités d'une
entreprise à court-terme pour cela il faut trouver le point d'équilibre afin de maximiser
l'efficacité de l'entreprise. La création d'un stock se produit lorsque l'arrivée des marchandises
est plus élevée que la sortie des marchandises. La rupture de stock, elle, se produit lorsque les
sorties de marchandises excèdent les entrées.
Pour les équipements, Il existe 2 catégories de problèmes de renouvellement
suivent qu’il concerne un matériel dont le rendement décroit avec usage et que nous
appelons matériel d’usure ou matériel du rendement constant mais sujet à défaillance
brutale comme par exemple les composantes électroniques.
6.1. Les Problèmes de Stocks
Afin de promouvoir le fonctionnement efficace de leurs affaires, les entreprises
accumulent les articles en magasin. Cette accumulation des articles est appelée un « stock ».
Dans une entreprise, on rencontre généralement des stocks des matières 1ères; d’articles semi-
finis et des produits finis. Même s’il est nécessaire de garder le stock, une entreprise peut
fonctionner avec une certaine efficacité à des niveaux des stocks variables. Le niveau de stocks
peut être contrôlé principalement en faisant varier la taille des lots. Il y a des avantages et des
inconvénients associés à toute politique de gestion de stock.
L’optimisation des stocks est la recherche d'un équilibre entre les contraintes ou les
objectifs liés aux investissements de capitaux et les exigences liées à la qualité de service
attendue, sur un ensemble d’unités de gestion des stocks, tout en prenant en compte l’instabilité
de l’offre et de la demande.
6.1.1. Modèle Déterministe
Ce modèle fait partie des systèmes de batch qui sont des systèmes déterministes à
demande constante.
Ainsi, les éléments suivants doivent être connus avec certitude :
La demande ou la consommation des matières premières,
La production ou la demande des produits finis,
Les autres éléments tels que la quantité à approvisionner, de coûts unitaires,
le coût d’acquisition,… interviendront lors de l’application du modèle.
a) Modèle de Wilson
Divers modèles mathématiques sont à la disposition du gestionnaire qui désire
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 111
Recherche Opérationnelle BAC+3 MP et SCAI

d’optimiser la gestion d’approvisionnement et de stock. Les méthodes déterministes admettent

que l’avenir est connu avec certitude.
Parmi ces modèles, le plus anciens et le plus célébré également a été développé
vers 1913 par Harris. Ce modèle permet de déterminer la quantité économique qui minimise
les coûts de gestion de stock, ce qui autorise l’automatisation des procédures
d’approvisionnement.
Ce modèle a comme hypothèse de base :
D(r) = la demande connues et constante exprimée en unité de temps ;
Cs= le coût des possessions (de stockage ou déstockage) ou encore coût de
détention par unité de produit et de temps ;
Cr= coût de lancement (de passation) d’une commande ;
Q= la quantité commandée à chaque réapprovisionnement ;
L= le délai de réapprovisionnement ;
P= taux de reconstitution ou de réapprovisionnement.
Ces hypothèses sont généralement respectées pour les produits finis dont la
demande est indépendante et régulière. Les profils de stock avec les hypothèses de base
présentées ci-haut, peuvent se présenter graphiquement comme suit :

Q
Q/2-------------------------------------------------------------------stock moyen
0
t1 t2 t3 t4 t5 t
NB : la distance séparant t1 et t2 c’est T
Le stock atteint la quantité Q au moment des réapprovisionnements puis diminue
progressivement e de façon constante suivant la demande D. quand il atteint le niveau nul,
on lance une nouvelle commande ou fabrication qui entre en stock aussitôt.
Soit :
C(Q) = coût total de gestion de stock ou coût total par unité de temps ;
a = coût unitaire de l’article ;
t = taux de possession des stocks en pourcentage par an de la valeur
stockée ;
Cs= le coût des possessions (de stockage ou déstockage) ou encore coût de
détention par unité de produit et de temps ;

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 112
Recherche Opérationnelle BAC+3 MP et SCAI

Cr= coût de lancement (de passation) d’une commande ;

Q= la quantité commandée à chaque réapprovisionnement ;
L= le délai de réapprovisionnement ;
P= taux de reconstitution ou de réapprovisionnement.
Ainsi, on aura :
 Le coût annuel de possession de stock sera égal au produit du stock moyen annuel
par le taux de possession et le coût unitaire de l’article.

C.-à-d., on a aura alors : ou encore : avec

 Le coût annuel du possession de la commande ou de lancement

(réapprovisionnement) = au produit du nombre aux commandes annuelles par le
coût d’une commande ou d’un lancement.

On a donc : ou encore

D’où la fonction économique C(Q)= + ou + (1) à minimiser

Graphiquement ceci se présente comme suit :

 Le coût total de gestion de stock diminue d’abord lorsque la quantité demandée de

chaque approvisionnement augmente, en suite passe par le minimum qui
correspond à la quantité optimal (Q*) et en fin remonte jusqu’à être parallèle au
coût de stockage.
( )
=0 après dérivée et démonstration Q*=√
( )

On sait que C(Q) = + , ainsi, pour trouver la quantité optimale (Q*), on aura alors :

C(Q*)= + ( ), remplaçons Q* par sa valeur dans (2) (Q*=√ )

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 113
Recherche Opérationnelle BAC+3 MP et SCAI

√
C (Q*)= + , après démonstration C(Q*)=√ ou √
√

Exemple
Mr NYONGOLO est responsable des approvisionnements chez un commerçant
détaillant d’articles de sport. La demande annuelle d’une référence des ballons de football est
2000U, t est 20%. Le coût de commande est de 300FF, le coût unitaire (a) est de 150FF, la
quantité (Q) actuelle d’approvisionnement actuel est Q. Déterminer la quantité optimale à
demander ainsi que les coûts inhérents à la gestion de stock.
Solution
Dou r = 2000unités, a = 150FF, Cr =300FF, Q*=? C (Q*) =? , coût annuel de Possession =?,
coût de lancement ?
Q*=200unités, (Q*)= 6000FF, CAP= 3000FF, CAL=300FF
Nbre de la demande ( ) 10 commandes

Cas particulier du modèle de Wilson

Ce modèle consiste à analyser la sensibilité de Q (la commande) par rapport
à . Si la commande optimale (Q*), la commande effective sera Q’ = Q* avec et
.

On sait que (Q) = + ( ) et (Q*) = + ( )

On aura alors :(Q’)= + ( ), nous savons que Q*

On aura alors :C ( ) +

Q’ = Q* , or , ( ) ( )- donc on aura

( )
, or à l’optimum : et puis remplaçons
( )

( )
Après démonstration C(Q’) =1/2 ( ) C(Q*) ou alors 1/2 ( )
( )

b) Manifacturing Modele
Dans ce modèle toutes les hypothèses de WILSON sont recommandées pour P
(taux d’approvisionnement) =P/L, P étant fini et uniforme.
Graphiquement, nous aurons :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 114
Recherche Opérationnelle BAC+3 MP et SCAI

Q
-----------------------------------C-----------------------------------

Q/2 ----------------------------------D--------------------------

P E r B t
L

T
Avec r= taux d’épuisement de stock, Q= la quantité commande ou à produire
P= taux de reconstitution (d’approvisionnement).
Le niveau moyen du stock à déterminer pour une période d’une année sera égal :
P=Q/L et r = Q/T
Le niveau moyen du stock sera égal à la quantité totale à commande moins DC :
DE = Q-CD, DE niveau de stock
Or nous savons que : r=CD/L
. Donc DE= Q-rL , or Q = PL, donc

DE = PL-rL . /

Donc DE = Q(1-rL/PL) ( ).

Le stock minimum du stock moyen sera donné par la relation ci-dessous : DE/2=
Q/2(1-r/p)
Le nombre de commande à passer sera donnée par la relation ci-après : r/Q ou
D/Q
Remplaçons Q/2 par sa valeur dans la fonction du coût total par unité de temps ;

on aura la fonction : C(Q)= . / , fonction à minimiser.

C(Q) = . /
( )
=0 . / =0, après avoir minimisé, on aboutira au résultat :Q*=
( )

√. si p , on aura : Q*= √ (modèle de WILSON)

/

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 115
Recherche Opérationnelle BAC+3 MP et SCAI

Pour calculer C(Q*)= = . / avec Q*= √ , après

. /

démonstration, on aboutira à la formule C(Q*)=√ . / , si p on aura alors

C(Q*)=√ (modèle de WILSON)

c) Modèle avec remise

Les remises sur la quantité, sont de réductions consenties pour des commandes
importantes offertes aux clients pour les inciter à acheter en grande quantité. Le modèle avec
remise obéis à certaines hypothèses ou tarif dégressif avec un seuil de commande portant sur
la totalité de la livraison.
Si K est le rabais ou réduction lorsque la quantité q est supérieure au seuil QK ;
on aura alors :
 Q q
 Q1 ;
 Q2 ;
 Q3
 Qn ( )
étant applicable à la totalité de la commande, le coût d’achat et le coût total

par unité de temps sera donné par : C(Q) = ra+ .

C(K) ( ) ( ) ( )

Le modèle sans réduction sera donc: C0= ra+

C1 : Da(1- )+ ( ) = réduction =

C2 : Da(1- )+ ( ) = réduction =

Ck : Da(1- )+ ( ) = réduction =

Et donc la fonction du coût total avec rabais est donnée par :

C(k)= Da(1- )+ ( ) ou Da(1- )+ ( ) , la fonction à minimiser.

Après avoir minimisé, q2 = ( )

q =√ ( )
ou q* =√( )

Si on aura alors que : q* =√

Connaissant le modèle de la fonction du coût total sans rabais et la fonction du

La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 116
Recherche Opérationnelle BAC+3 MP et SCAI

coût total avec rabais, on peut déterminer la fonction économique du rabais.

Sans rabais : C0= Da+

Avec remise (Réduction) : C1 : Da(1- )+ ( ) , la fonction

économique du réduction sera alors donnée :

C0-C1= Da+ , ( ) ( ) -

Après démonstration
C0-C1=Cs( ) ( ) ( )

Exemple graphique :

Exemple
On utilise régulièrement 480 tonnes par mois d’une certaines matières premières. On
évalue à 200FF le frais direct relatif à une commande tandis que le coût de possession est
estimé pour cette matière est estimé à 20%. On reçoit une offre pour 200FF la tonne avec
proposition de rabais de 1% la livraison de 500tonnes ou plus.
Quelle est doit être la politique d’approvisionnement pour cette matière.
Solution
D ou r = 480T/mois, Cr=200FF, a=200FF, t=20%, q= 500T q1 =500T, rabais 1%

Sans rabais : Q*= √ Q*= 240T

Avec rabais : Q*= √ Q*= 246,18T

( )

Tous les coûts : Sans réduction C(Q)= 1161600FF et Avec rabais C(Q)= 1197748,84FF.
La politique d’approvisionnement doit être faite avec rabais pour essayer de
minimiser les coûts car si on s’approvisionne les 500T sans réduction on aura un coût supérieur.
Soit le coût de 1161600 FF pour 480Tonnes par mois, le coût total pour 500
tonnes sans réduction sera alors égal : 1161600/480 = 2420 la tonne. Le coût des 500 tonnes
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 117
Recherche Opérationnelle BAC+3 MP et SCAI

vaut : 500*2420= 1210000FF.

1197748,84FF 1210000FF. La bonne politique est celle de s’approvionner
avec la réduction (remise).
d) Modèle avec rupture de stock ou avec pénurie
La pénurie étant une rupture de stock de l’entreprise, elle est représentée par
son coût qui est un ensemble de frais résultat pour une entreprise du manque de
disponibilité d’un article donné pendant un temps. Dans ce modèle, toutes les hypothèses de
Wilson sont admises sauf en ce qui concerne la pénurie. Cette dernière est permise en
admettant en quant de manquant la demande ne disparait pas mais elle est survie avec
retard et l’on doit supporter un certain coût supplémentaire appelé coût de pénurie ou coût
de rupture de stock. Ainsi, le coût de pénurie sera proportionnel au temps mais aussi aux
quantités manquantes. La fonction du coût total par cycle à minimiser et les variables de
contrôles à maitriser sont les suivantes :
- Il faut calculer et maitriser Q(quantité à commander) et S (la valeur absolue du
niveau minimal négatif des stock) ;
- La fonction à minimiser du coût total par cycle sera la suivante :

Q---------------------------D-----------------------------------------------------------

l L r q=

r E
0 A
S-------------------------------B--------------------------------------------------------------
T
Q= B*D
S=r*L
D=L*r
T=l+L
( )
L=C*D/r = or r=

L= la durée d’un stock

q= stock réel
Cs= coût de stockage
Crup= Coût de rupture
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 118
Recherche Opérationnelle BAC+3 MP et SCAI

( ) ( )
C(Q) = Cr + Cs + * Crup C(Q) = Cr+ Cs +
( )
La fonction dévient alors : C(Q) = Cr + +Cs + Crup

C’est la fonction du coût à rendre minimal or au minimum les dérivées partielles

de Kt par rapport à Q et S sont nulles.
( )
=0 après dérivée et démonstration S=
( )

Si nous posons que on aura alors S= Q avec égal risque de rupture des

stocks ou paramètre mesurant la sensibilité entre Q et S.

( )
Alors : =0 après dérivée et démonstration, = or on sait que
( )

si Q2 = ( )
= en fin nous avons
( )

( )
Q*=√ or nous savons que S* = Q* S*= Q*

On a donc S*=√( )

Ce modèle est simple à appliquer et représente la réalité de la plupart

d’entreprise du tiers monde qui doivent s’approvisionner en produits ou matières dans les
pays développer. Cela entraine parfois une rupture de stock pendant un certain temps. Il
représente l’inconvénient d’être plus mathématique entrainant une frustration de certaines
personnes non averties.
6.1.2. Le(s) modèle(s) probabiliste(s)
Ces sont des modèles où la demande est incertaine. En réalité, les paramètres qui
interviennent dans les calculs de la quantité de la demande sont entachés d’incertitude. On
se borne le plus souvent à considérer que la demande de la consommation est la principale
variable aléatoire. La demande n’étant jamais connus avec certitude dans la réalité, il faut
dans la gestion de stock tenir compte de ces facteurs aléatoires. On le fait d’habitude au
moyen d’un stock de sécurité. Mais pour exposer les principes de raisonnement, nous avons
les modèles simples de réapprovisionnement périodique.
On suppose un réapprovisionnement à intervalle fixe, le niveau Q du stock en
début de période est choisi comme variable de décision.
Désignons par :
- Q : le niveau de commande
- T : Unité de temps

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 119
Recherche Opérationnelle BAC+3 MP et SCAI

- Cs : Coût de stockage par unité en stock enfin de période

- Crup : Coût de rupture par unité manquante en fin de période
- r : La demande aléatoire.
- ( ) fonction de probabilité de la demande.
Suivant l’importance de la demande, en rapport avec le niveau de stock au début de la
période, on distingue 2 cas :
- On arrive en fin de période avec un manquant (situation de rupture) ;

Q --------------------------------------------------------
r

Stock
t
1er cas : Cr+(Q-r)Cs
- On arrive en fin de période avec un surplus.

Q-----------------------------------------------

t
2ème cas : Cr+(r+Q) Crup
La fonction économique à rendre minimum est ici l’espérance mathématique du
coût d’approvisionnement par cycle. Comme l’intervalle entre réapprovisionnement est fixe,
le coût de lancement ou de réapprovisionnement n’a pas d’importance dans le modèle.

E,( )- = ∫ ( ) ( ) dr +∫ ( ) ( ) dr.

C’est la fonction de la variable constitue Q. Pour chercher Q* (Q optimal), on

obtiendra une équation en Q en égalant à 0 la dérivée première ou encore en utilisant la
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 120
Recherche Opérationnelle BAC+3 MP et SCAI

formule suivante :

F(Q*) = 1- F(Q*)= 1- F(Q*)= F(Q*)=

Cette relation donne implicitement Q* par l’intermédiaire de la fonction cumulée de la

demande.
6.1.3. Les Stocks de Sécurité
Dans toutes les entreprises, les stocks de sécurité sont d’une grande importance
car ils interviennent aux éventualités futures. Pour mettre en pratique la formulation de la
quantité économique de la commande (de la demande) basée sur les hypothèses de la demande
certaine, il faut toujours tenir des facteurs aléatoires.
Comme nous avons défini le stock de sécurité est une protection face aux
variations aléatoires de la demande et du délai de livraison.
En effet, si le fournisseur livre avec retard ou si la demande augmente entre la
demande d’approvisionnement et de réception en stock, les gestionnaires des stocks en
situation de rupture des stocks.
Cette situation de pénurie ne se présente que lorsque la demande et/ou le délai de
réapprovisionnement sont supérieurs aux valeurs moyennes utilisées dans les paramètres de
gestion du système de réapprovisionnement. Dans le cas contraire, c’est une situation de sur
stockage à laquelle les gestionnaires seront confrontés. La détermination du stock de sécurité
s’appuie traditionnellement sur un objectif de minimisation de risques de rupture de stocks.
La loi de la demande la plus fréquemment utilisée est la loi normale ou la répartition de
GAUSS. Cette loi de distribution est caractérisée par une variable symétrique de la demande
et/ou le délai autours d’une valeur moyenne mesurée par l’écart type. C’est cette dernière
possibilité que nous allons examiner.
On peut présenter graphiquement la loi de Gauss :

Pour ce faire, on doit :

 Calculer l’écart-type de la variation de la demande et/ou le délai de
réapprovisionnement sur la période de la protection,

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 121
Recherche Opérationnelle BAC+3 MP et SCAI

 La détermination de stock de sécurité par la relation Ss= Z ,

Avec :
- Z= variation aléatoire de la distribution normale et fonction du risque de pénurie
acceptable et
- = écart-type de la demande ou de la consommation durant les délais
d’approvisionnement.
Les variations seront appropriées de la formule de base de la sécurité en fonction
de la situation particulière suivante :
a) Le cas où seul le taux de commande est entré de varié
Ss=Z*√ * avec :
- = écart-type de taux de commande
- d= délais d’approvisionnement

b) Le cas où seul le délai de livraison est entré de varié

Ss=Z* .
Avec :
- taux de consommation ou de la demande
-
c) Le cas où le délai d’approvisionnement et le taux de la demande sont entrés
de varié

Ss=Z*√
Avec :
- = distribution da la demande
- d et = moyenne et écart-type de la distribution de délai d’approvisionnement.

Exemple :
Considérons un article de consommation suivant une loi de Gauss de moyenne
hebdomadaire x = 50 et d’écart type σ x = 5. Le délai moyen de livraison est de 4 semaines (20
jours) avec une variation d’écart type de 2 jours.

- Considérant le délai fixe, on peut calculer :  4 52 100

- En considérant la consommation fixe, on peut calculer :
(Conso) (Consommation/jour) l(jours)= 10 2 20 soit = 400

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 122
Recherche Opérationnelle BAC+3 MP et SCAI

- En considérant la consommation et le délai variable, on peut calculer :

= 400+100= 500 soit √

- En acceptant un risque de rupture de 2,5 % (z = 1,96) le stock de sécurité est alors : Ss
=Z = 1,96 × 22,36 = 44 pièces
6.1.4. Le point de Commande
Les principes du système de point de commande consistent à passer une
commande ou à lancer une fabrication d’une quantité fixe par exemple : la quantité
économique dès que le niveau du stock disponible atteint un niveau prédéterminé appelé
POINT DE COMMANDE.
Le point de commande est alors la quantité nécessaire en stock au moment de la
commande pour satisfaire la consommation pendant le délai d’approvisionnement.
Graphiquement nous avons :

L’intervalle entre 2 approvisionnements est variable et dépende de la demande

réelle.
Le système à point de commande nécessaire un suivi précis et fréquent du niveau
de stock. Il sera donc utilisé de préférence pour des articles apportés par leur utilisation. Il
permet une variabilité de la demande en déclenchant la demande avant le point de
commande.
En situation déterministe les facteurs suivants déterminent le point de
commande :
 Le taux de demande basé en général sur de prévision des ventes ;
 Le délai d’approvisionnement.
Si la demande et délai d’approvisionnement sont tous fixe comme c’est le cas du
modèle déterministe, le point de commande sera calculé par :
P=
Notons que la demande et le délai d’approvisionnement seront calculés en

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 123
Recherche Opérationnelle BAC+3 MP et SCAI

fonction de même unité de temps. En situation probabiliste les facteurs qui influencent sur la
quantité de stock de sécurité sont :
 Le taux de la demande moyen,
 Le délai d’approvisionnement ou délai moyen ;
 La variabilité de la demande et/ou de délai d’approvisionnement ;
 Le niveau de service désiré.
Lorsqu’il y a une variabilité de la demande et/ou du délai d’approvisionnement, il
est possible que la demande réelle excédée la demande prévue.
Par conséquent, il devient nécessaire de garder un stock additionnel ou un stock de
sécurité pour réduire les risques de rupture des stocks durant le délai d’approvisionnement.
Dans ce cas, le point de commande sera calculé par :
PC=
Le gestionnaire doit évaluer avec soin les coûts de possession d’un stock de
sécurité tout en tenant compte de la réduction du risque de ses ruptures de stock.
Le niveau de service sera alors inversement proportionnel aux risques ruptures de
stock.
Le risque de rupture de stock sera donc :

NC= probabilité de détention (1- )

6.2. Les Problèmes de renouvellement et remplacement des équipements
Il existe 2 catégorie de problèmes de renouvellement suivent qu’il concerne un
matériel dont le rendement décroit avec usage et que nous appelons matériel d’usure ou
matériel du rendement constant mais sujet à défaillance brutale comme par exemple les
composantes électroniques.
Le problème général de gestion du matériel est celui du choix, du moment de
remplacement, remplacement de l’ensemble ou des composantes.
S’ il s’agit d’un matériel d’usure, il faut trouver le point d’équilibre entre le coût
d’acquisition entre le nouvel équipement et augmentative du rendement qui en résulte.
S’il s’agit d’un matériel sujet à défaillance brutale, on peut réparer ou changer la
pièce lors d’une défaillance mais on peut aussi remplacer ou réparer préventivement les
pièces avant qu’elle ne cesse de fonctionner.
6.2.1. Éléments qui interviennent dans la décision de remplacement
a) Le coût d’acquisition

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 124
Recherche Opérationnelle BAC+3 MP et SCAI

C’est le coût de revient du matériel lors de l’achat. Ces frais étant supportés par
l’entreprise on conçoit que la charge annuelle qui leurs est due est d’autant plus faible que
l’on conserve l’équipement le plus longtemps possible. Il faut évidemment tenir compte de
la valeur et de revente du matériel et de la déduire du prix de revient à l’achat pour obtenir
montant de frais d’acquisition.
b) Le coût de Fonctionnement
C’est l’ensemble de frais dus à l’utilisateur de l’équipement à savoir : la
consommation de l’énergie, l’entretien, l’amortissement,… Pour les matériels d’usure, ces
frais croissent généralement en fonction d’utilisation et donc de l’âge.
Ainsi, on aura ce cas :
Coût d’acquisition Coût de fonctionnement

t1 t2 t3 Durée de vie

Le problème ici consiste à trouver la durée de l’équipement la plus favorable c.-à-

d. seul qui correspond au minimum de la somme des coûts d’acquisition et de fonctionnement
par unité de temps. On peut alors représenter de la manière suivante :
Coût d’acquisition
Coût annuel

Coût de fonctionnement

Coût d’acquisition

t(durée de vie)
Notons qu’il ne faut pas l’équipement dure longtemps dans l’entreprise on risque
de voir les coûts de fonctionnement devenir supérieurs aux coûts d’acquisition.

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 125
Recherche Opérationnelle BAC+3 MP et SCAI

6.2.2. modèle de remplacement

Dans ce modèle on désigne par :
A : Coût d’acquisition,
Ct : Coût de fonctionnement de l’année t ;
Rt : La valeur de revente en fin d’année t
r : Nombre d’année avant le remplacement de l’équipement ;
K(r) : Le coût moyen total de l’équipement pour la durée r
k(r) : Coût moyen de l’équipement par an.
Si on remplace l’équipement après r années, on a le coût total qui est donnée
par la relation suivante :
K(r)=A+C1+C2+…Ct-k(r)
La fonction économique à rendre minimal est évidement : k(r) =K(r). Dans ce cas
l’optimum a lieu quand le coût marginal (supplément de coût total si l’on garde l’équipement
un an de plus) vient de dépasser le coût moyen.
Exemple :
Le prix d’achat d’une machine est 60000 FF (matériel A) sa valeur de revente
s’établi comme suit :
Année Valeur
1 30000
2 20000
3 12000
4 8000
5 6000
6 5000
Le coût de fonctionnement est 20000FF la première année et s’accroit en suite de
5000FF par an. Combien de temps faut-il la conserver avant le remplacement par une machine
identique.
Année Dépréciation Ct de fonctionnement Ct total K(r) Ct moyen k(r)
Nominal Cumulé
1 30000 20000 20000 50000 50000
2 40000 25000 45000 85000 42500
3 48000 30000 75000 123000 41000
4 52000 35000 110000 162000 40500
5 54000 40000 150000 204000 40800
6 55000 45000 195000 250000 41666,67
On voit que la période 4 est celle qui procure le coût moyen annuel minimum. On
remarque que ce moment de remplacement correspond au point où le coût dépasse le coût

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 126
Recherche Opérationnelle BAC+3 MP et SCAI

moyen.
En effet, si on conservait l’équipement un a de plus, il coûterait un supplément dû
aux coûts du fonctionnement de la cinquième année auxquels s’ajouterait la différence de la
valeur de revente.
C5= 40000+(8000-6000)= 42000
C4=35000+(12000-8000) =39000

6.1.3. Actualisation des valeurs

La durée de conservation des équipements d’usure couvre plusieurs années. Il est
donc normal de tenir compte non seulement de montant mais aussi du montant où il
survienne. Pour permettre de comparaison on ramène ses dépendances à un même moment.
La valeur actuelle portant to d’une dépense future est le montant qui est placé au temps to
deviendrai par le jeu d’intérêt équivalent à la dépense équivalent à la dépense au moment de
l’échéance de celui-ci.

Si i est le taux d’intérêt, on a les facteurs d’escompte qui est égal à : Vt=( )

ou Vt= (1+i)-t
Dans le modèle avec actualisation, chaque dépense doit être escomptée pour
trouver son équivalent à un moment fixe, le plus souvent au moment d’investissement. Si l’on
désigne par K(r), la valeur actuelle du coût total avec un remplacement au bout de r années
et en supposant que toutes les dépenses de fonctionnement sont effectuées au début de la
période, on a maintenant l’expression suivante :
K(r) = A+C1Vo +C2V1+C3V2+…+CrVr-1-krVr, comme tout nombre exposant 0
donne 1, l’expression deviendra alors :
K(r) = A+C1 +C2V1+C3V2+…+CrVr-1-krVr
La fonction économique qu’il faudra rendre minimum doit correspondre à un coût
moyen. Puis que l’on tient compte ici de l’échelonnement des dépenses dans le temps, on ne
peut pas se contenter d’une simple moyenne.
La fonction économique que l’on voit considérer est l’annuité d’une rente de r
années dont la valeur actuelle correspond à la valeur actuelle des dépenses totales relatives à
l’équipement.
On sait que, la valeur actuelle d’une rente d’annuité X payable d’avance pendant r
année s’exprime par la relation suivante :

V = XV0 +XV1+XV2+…+XVr-1 ou encore V=

On doit donc trouver la valeur X(r) tel que le coût total actuel K(r) =V*X(r).
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 127
Recherche Opérationnelle BAC+3 MP et SCAI

Ainsi donc, K(r)= X(r) X(r)=K(r)

Exemple
En prenant l’exemple précédant (matériel A) on vous demande de déterminer
l’année de remplacement optimal de ce matériel sachant que le taux d’intérêt annuel est 10%.
Année Valeur de rente Ct Ct de fonctionnement Ct Total Annuité
nominal actualisé d’acquisition Nominal Actualisé Cumulé X(r)
1 30000 27272,72 32727,27 20000 20000 20000 52727,27 52727,27
2 20000 16529 43471 25000 22727,2 42727,2 86498 45196
3 12000 9016 50984 30000 24793 67520 108504 43320
4 8000 5464 54536 35000 26296 93816 148352 42546
5 6000 3725 56274 40000 27320 121136 177410 42546
6 5000 2822,36 57178 45000 27941 149077 206255 43052
Par le fait de l’actualisation, on constate que le minimum correspond à un
remplacement après 5 ans. La valeur de l’annuité pratique égale à celle correspondant à un
remplacement après 4ans.
EXERCICES
1) Une entreprise utilise une matière première M pour laquelle la consommation annuelle
de 1 000 kg est régulière. Le prix d’achat est de 360FF le kg. Le coût de passation d’une
commande s’élève à 500 FF, le taux de possession du stock représente 10% de la valeur
du stock moyen TD : Chercher la cadence d’approvisionnement N et la quantité
économique les plus rentables pour la matière première M.
2) Les dirigeants de la société de produits Z souhaitent connaître la cadence la plus rentable
pour leurs approvisionnements en matières premières. Le coût de passation d’une
commande est évalué à 100 FF, le taux de possession des stocks est de l’ordre de 15% de
leur valeur. On estime que la consommation annuelle à retenir comme base est de 25 000
kg. Le coût unitaire d’un élément du stock s’élève à 102 FF.
3) Dans une étude de sensibilité du modèle de WILSON, on dit que Q’=2 Q*. Etudier
la sensibilité de Q par rapport à avec
4) Soit dans un modèle classique de WILSON, on a la fonction :

C(Q)=Cs ( ) , tels que Q’= Q* avec . Calculer

la sensibilité de Q par rapport à pour = 0,3 ; 0,4 ; 0,8 et 12

5) Le contre maitre d’un chantier de construction connait par expérience que la
consommation de sable durant la période de livraison est de 50T. Son adjoint
administratif l’informe que la consommation durant la période de livraison suit une loi

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 128
Recherche Opérationnelle BAC+3 MP et SCAI

normale avec une moyenne de 50T et un écart-type de 5T. Sachant que le contre
maitre est prêt à prendre les risques de rupture de stock à 3%. Déterminer :
a) Le stock de réserve à garder
b) Le point de commande
6) Mr KAKA utilise 1440Kgs par trimestre de semoule. Il évalue à 400FF les frais qui
entrent en jeux pour une commande. Il évalue en suite le coût de possession de
stock pour 25% sur la valeur de semoule. On suppose une offre avec réduction de
1,5% pour une livraison de 1600Kgs minimum.
Déterminer la vraie politique d’approvisionnement.
7) On considère un appareil électroménager dont le coût d’achat est de 925060 FF. Sa
valeur de revente se présente comme suit :
Année Valeur
1 450000
2 360000
3 227650
4 109005
5 75950
6 60800
7 55550
Le coût de fonctionnement est 150000FF la 1ère année et s’accroit de 20% par an.
Les dépendances doivent être actualisées au taux d’intérêt annuel de 12%.
TD : Déterminer à combien de temps faut-il remplacer cet appareil (par le modèle
sans actualisation et le modèle avec actualisation)?

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 129
Recherche Opérationnelle BAC+3 MP et SCAI

Chapitre 7 : PROBLEMES DE FILE D’ATTENTE

7.1. Notions
Chacun de nous sait ce qu'est une file d'attente car la vie quotidienne en offre de
multiples exemples : qu'il s'agisse de payer ses frais de scolarité à la caisse d'une institution
d'enseignement, de prendre rendez-vous avec un médecin spécialiste, de faire lire son manuscrit
de Mémoire par le Professeur Directeur, de faire traiter un dossier par une administration
publique, de régler ses factures d'eau ou d'électricité aux caisses de l'agence de son quartier, etc,
il faut généralement attendre. Mais le problème d'attente se pose aussi lorsque les personnes et
les installations susceptibles de servir un service donné attendent aussi. On peut classer les
problèmes d’attente en deux catégories selon leur structure. La première catégorie comprend les
problèmes dans lesquels les arrivées et/ou les temps de services sont aléatoires. Il s’agit de
déterminer soit le nombre optimal de personnes et d’installations susceptibles d’accomplir le
service, soit la cadence optimale d’arrivée (ou même le moment des arrivées) ou encore les
deux. On cherche en fait à déterminer le nombre d’installations permettant de minimiser le total
de deux éléments suivants : coût de l’attente du client et coût de l’inactivité de l’installation. Ces
problèmes relèvent de la théorie des files d’attente ou théorie des queues.
Dans la seconde catégorie des problèmes d’attente, on ne s’intéresse plus à
l’action que l’on peut avoir sur les arrivées ou sur le nombre des serveurs mais à l’ordre dans
lequel sont servies, par une suite de points de service, les unités qui peuvent l’être. Ici, le
problème posé est l’inverse du précédent. En effet, le nombre d’installations est donné avec
possibilité d’agir sur les arrivées et sur l’ordre dans lequel les clients seront servis. Le problème
consiste alors à régler les arrivées ou à ordonnancer les tâches de façon à minimiser le coût total.
Le mot « ordonnancement » désigne ici l’ordre dans lequel les unités de la file sont servies.
Dans un problème de files d'attente, il s'agit d'une manière générale, de déterminer le nombre
optimal des stations (où les clients viennent chercher un service) de manière que les clients ne
perdent qu'un temps raisonnable. Cela revient à minimiser le coût total de l'inactivité des
stations et de l'attente des clients, donc finalement à établir un compromis entre le prix des
serveurs (exprimés par les charges qui résultent de l'amélioration du service) et le prix de
l'attente des clients, ces deux prix variant en sens inverse. Mais le coût des serveurs est
proportionnel à leur nombre, tandis que celui de l'attente de clients dépend de données
(l'affluence de la clientèle et la durée du service). Il faut donc estimer le prix de l'attente : o
coût de l'attente des clients : qui doit tenir compte du temps perdu, du mécontentement de la
clientèle, des ventes perdues, etc. o coût du centre de service : coût des installations,

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 130
Recherche Opérationnelle BAC+3 MP et SCAI

constructions, équipement, capitaux ; o coût de fonctionnement : personnel, frais d'entretien, ...

Quelques exemples de phénomènes d'attente

Les files d'attente sont des phénomènes qui nous sont familiers parce que observables très
fréquemment dans notre activité personnelle ; mais on les rencontre aussi dans de nombreux
problèmes économiques, militaires, sociaux, etc.
On peut considérer deux régimes possibles dans l'étude des phénomènes d'attente. Le régime
stationnaire ou permanent et le régime transitoire. On parlera du régime permanent lorsque le
processus doit se dérouler pendant un temps suffisamment long pour que l'état du système ne
soit plus influencé par les conditions de départ du processus. Le régime est transitoire quand
l'état du système dépend des conditions initiales.
7.2. Structure d'un phénomène d'attente
Pour qu'une file d'attente apparaisse, il suffit que les entrées et/ou les services se
produisent à des intervalles irréguliers ou réguliers. Sous sa forme la moins complexe, un
phénomène d’attente (figure 8.1) comporte trois phases principales, à savoir :
- Une arrivée d’unités,
- Une file d’attente,
- Un service

Ce schéma reproduit les principaux aspects que l’on rencontre dans un problème
d’attente. On peut y voir comment les clients, venant de la source, entrent dans le système
d’attente en commençant par former une file d’attente dans le centre d’attente ensuite ils se font

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 131
Recherche Opérationnelle BAC+3 MP et SCAI

servir et enfin sortent. Ceci est bien entendu la forme plus simple. Les modèles d’attente ne sont
pas toujours les mêmes. Ils varient en fonction des différents aspects qui caractérisent soit les
arrivées des clients, soit la manière dont le service est rendu. Dans l’optique de la manière
dont le service est rendu, donnons certaines autres formes des files. Ceci étant, rappelons que :
- la source : le loge des clients potentiels. Elle peut-être à capacité infinie c'est-à-dire,
comprenant les clients potentiels en nombre infini. Dans ce cas, les unités servies dans le
système ne sont pas nécessairement celles qui y étaient antérieurement. Exemples : des
individus se présentant à un guichet d’un service public ou d’un grand magasin ; des
véhicules à une station d’essence. On a dans ce cas un modèle de type ouvert ou
linéaire.
- La source est aussi à capacité finie, c'est-à-dire comprenant un nombre fini des clients
potentiels. Le client, une fois servi et satisfait, revient à la source et est susceptible de se
représenter plus tard dans le système (exemple, les véhicules ou les machines d’une
entreprise réparés dans le garage ou l’atelier de réparation de cette entreprise). On dit
que le modèle est à type fermé ou cyclique.
- Le centre de service est l’endroit exact où est rendu le service. Le fonctionnement du
centre de service est caractérisé par le temps qui lui est nécessaire pour "traiter" une
arrivée. Il est le plus souvent décrit par la loi de probabilité des temps de service. Le
taux moyen de service représente la capacité du centre de service en nombre d'unités
traitées par unité de temps. Le centre de service peut comprendre un ou plusieurs
guichets dans lesquels on trouve des serveurs. Il peut être de différents modèles, classés
en fonction du nombre des serveurs. Nous distinguons :
- Le modèle à serveur unique : c’est le modèle le plus simple, il n’y a qu’un seul
guichet qui rend service.
- Le modèle à S serveurs, où S > 1 : ici nous trouvons plusieurs guichets qui
peuvent être organisés de différentes manières :
1) Guichets en parallèle
Il y a plusieurs guichets qui rendent indifféremment le même service. Les clients n’ont besoin
d’être servis que par un seul des guichets, bien qu’il y en ait plusieurs. Ils se présentent au
guichet qu’ils trouvent ouvert pour être servis (exemple : les pompes à essence dans une station
service).

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 132
Recherche Opérationnelle BAC+3 MP et SCAI

2) Guichets en série
Ici, ne peut être considéré comme servi que le client passé par tous les guichets.

3) Guichets en réseaux
- Les guichets en séries parallèles

Le client choisit une série et la suit jusqu’à la fin.

- Les guichets en séries parallèles amorties.

Quelle que soit la série choisie, à la fin tous les clients passent par le même guichet
- Les guichets en série parallèles explosives.

Tous les clients commencent par le même centre de service, mais après se
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 133
Recherche Opérationnelle BAC+3 MP et SCAI

répartissent en séries.
Les clients entrent dans le système par des porte-tambours. Ils se dirigent vers les files
d'attente et y prennent la dernière place. Les entrées peuvent être, soit séparées par des
intervalles de temps égaux, soit séparées par des intervalles de temps inégaux mais déterminés,
soit séparées par des intervalles de temps inégaux connus en probabilité (on dit que les
intervalles sont aléatoires).
Dès qu'un client a obtenu le service désiré auprès d'une station (voie, guichet, vendeur,
etc.), il sort du système et il est remplacé par l'un des premiers clients attendant dans les files.
- Une file d'attente ou queue qui précède éventuellement le centre de service. Nous
appellerons "file d'attente" l'ensemble des clients (unités arrivées) qui attendent d'être
servis, à l'exclusion de celui qui est en train de se faire servir dans le centre de service.
La longueur de la file d’attente est déterminée par la capacité du centre d’attente qui peut
être infinie (lorsque le nombre d’unités dans la file est indénombrable, tels les avions
attentant l’atterrissage dans le ciel) ou finie (lorsque le nombre d’unités dans la file est
fini, exemple, les malades attendant la consultation dans une salle d’attente d’un centre
médical). Ici, toute unité devant attendre au-delà de la capacité du centre d’attente est
considérée comme perdue.
- Le système d'attente qui est l'ensemble des clients qui font la queue, y compris celui
qui se fait servir.
- La discipline du service qui précise quel individu parmi ceux actuellement en attente
sera traité le premier. Les règles de priorité sont très variées. On en distingue
généralement cinq.
 La règle FIFO (First in, First out ou First come, First served) ou en Français
PEPS (Premier Entré, Premier Sorti) qui est normalement d'application dans
tous les phénomènes de files d'attente. D'après cette règle, le premier arrivant est
le premier servi.
 La règle LIFO (Last in, First out ou Last come, First served), en Français
DEPS (Dernier Entré, Premier Sorti) qui veut que le dernier venu soit le
premier servi. Par exemple lorsqu'un ascenseur descend au rez-de-chaussée, la
personne se trouvant au deuxième niveau d'un immeuble de 20 étages sera servi
avant une autre se trouvant au 19ème.
 La règle NIFO (Next in, First out) qui veut que le prochain arrivant soit le
premier servi. Cette règle est pratiquée dans la comptabilité des compagnies
pétrolières.
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 134
Recherche Opérationnelle BAC+3 MP et SCAI

 La règle avec priorité qui veut qu'on puisse accorder une certaine priorité à
certains clients se trouvant dans la file.
 La méthode quelconque ou « au hasard » qui veut qu'on puisse servir les
clients dans un ordre quelconque (pêle-mêle).
- Le processus d'arrivée des "clients" qui est décrit par une loi de probabilité des
arrivées. Le taux moyen d'arrivées est le nombre moyen de "clients" qui se présentent
par unité de temps. Les arrivées des clients sont aléatoires.
En ce qui concerne le comportement des clients, on distingue les clients patients et les
clients impatients.
Les premiers sont ceux qui restent dans la file jusqu'à ce qu'ils soient servis. Quant aux
derniers, on distingue les clients impatients a priori et les clients impatients a
posteriori.
Les clients impatients a priori sont des unités qui arrivent et trouvant d'autres unités
décident de partir (sans entrer dans le système).
Les clients impatients a posteriori sont des unités qui sont déjà dans la file d’attente
et qui décident de partir vu que le temps dont elles disposent pour attendre est écoulé
Appelons :
S : le nombre de stations ;
m : le nombre d'unités dans l'ensemble du phénomène (rappelons que m peut être constant) ;
n : le nombre d'unités dans le système (en attente dans une file et en cours de service) ;
v : le nombre d'unités dans les files d’attente ;
j : le nombre d'unités en cours de service ;
q : le nombre de stations inoccupées ;
tf : le temps moyen d'attente dans la file avant le service ;
ts : le temps moyen d'attente dans le système ;
n, v, j, q: les valeurs moyennes de n, v, j et q
On a donc :
n = j si n S, tous les clients peuvent être servis
=v+j si n > S.
Les quantités n, v et j varient en fonction du temps et sont aléatoires et on se
propose de découvrir les lois de probabilité auxquelles elles peuvent satisfaire.
Soit pn la probabilité qu'il y ait n unités dans le système.
Nous avons à considérer les événements suivants : 0 événement, 1 événement, ..., n événements,
..., m événements. Ceci définit une variable aléatoire.
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 135
Recherche Opérationnelle BAC+3 MP et SCAI

dont la moyenne ou espérance mathématique

où m peut être infini.

Dans le cas d'une seule file d'attente et d'un nombre S de stations qui assurent le
service, le nombre moyen d'unités dans la file sera :

Cette formule s'explique par le fait qu'il y a des unités en attente dès que n dépasse
S, c'est-à-dire pour n = S + i, avec i = 1 à m - S et que les probabilités correspondantes sont pS
+ 1, pS + 2, ... On pourrait encore exprimer le nombre moyen d'unités en cours de service, mais
on préfère souvent s'intéresser au nombre moyen ̅ de stations inoccupées. Ce qui donne :

Il est évident qu'il y a S stations inoccupées quand il n'y a pas de client dans le
système, (S-1) pour un client, etc. Il existe entre ces moyennes ̅, ̅ , et ̅, une relation
importante :
̅= ̅ +S - ̅,

En effet,

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 136
Recherche Opérationnelle BAC+3 MP et SCAI

D'où la relation indiquée.

7.3. Etude de la loi des arrivées et de la loi des services

Les lois des arrivées et des durées de service permettent de caractériser le système
et de calculer des résultats intéressants tels que le temps moyen d'attente des clients et le temps
moyen d'inactivité des stations. Considérons le cas très simple où il n'existe qu'une file d'attente
et une seule station.
File d'attente à une station

Dans ces conditions, on a j = 1 et n = v + 1. Les clients arrivent au hasard et le

temps passé à la station par chaque client est aléatoire. Par exemple, les automobilistes viennent
au hasard à un parc (cela veut que dire que l'heure d'arrivée de chacun est aléatoire) ; ils y
stationnent un temps variable qui ne peut pas exactement être prévu pour chacun d'eux (c'est
encore une variable aléatoire).
L'expérience montre que, dans beaucoup de phénomènes d'attente, les lois des
arrivées et des services sont respectivement poissonniennes et exponentielles négatives. Il est
utile de savoir que ce ne sont pas les seules formes que peuvent affecter ces lois, mais ce sont les
plus fréquentes et aussi les plus simples à employer pour obtenir un exposé clair des principes et
de la théorie des phénomènes d'attente.
7. 3.1 Processus de Poisson
Imaginons une suite d'événements identiques E (exemple arrivées des clients dans
un système d'attente, passages de véhicules sur le boulevard Lumumba) qui se succèdent dans le
temps.
A partir d'une origine arbitrairement choisie cherchons à évaluer la probabilité pn(t)
pour que n événements se produisent pendant un intervalle de temps égal à t avec les hypothèses
suivantes :
les événements sont indépendants. Deux événements ne se produisent jamais
en même temps (par exemple, jamais deux clients n'entrent exactement en
même temps dans le magasin).
le phénomène est homogène dans le temps ou stationnaire, c'est-à-dire que
pn(t) ne dépend que de l'intervalle de temps t et ne dépend pas de l'instant
initial à partir duquel t est mesuré. Par exemple, si la probabilité du passage
de neuf véhicules sur le boulevard Lumumba entre10h30’ et 10h31’ est de
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 137
Recherche Opérationnelle BAC+3 MP et SCAI

0,12, on doit avoir la même probabilité entre 9h28’ et 9h29’ ou 10h41’ et

10h42’.
Si l'on considère un intervalle de temps très petit t choisi à n'importe quel
instant, la probabilité qu'un événement se produise pendant cet intervalle est
proportionnelle à t et égale à λ t, λ (le taux moyen d'arrivées) étant une
constante. De plus, la probabilité que deux événements se produisent plus
d'une fois dans l'intervalle t est du second ordre par rapport à la première.
Evaluons maintenant la probabilité que n événements se produisent pendant
l'intervalle de temps t+ t, soit pn (t+ t ).
On a : (1)
Puisque λ t est la probabilité de réalisation d'un événement pendant le temps t et
1- λ t, la probabilité contraire. Cette formule est vraie pour tout n, sauf n = 0 car si aucun
événement ne s'est produit pendant l'intervalle de temps (t+ t ), c'est qu'aucun n'était réalisé
pendant l'intervalle t.
On a donc : P0 (t+ t ) = P0(t) , -. (2)

Cette relation s'écrit aussi : (5 (3)

En prenant la limite de cette expression lorsque 0, on obtient : (4) (4)

De même la relation (1) peut s'écrire : (5)

et en faisant tendre t 0, on a : (6)

Les conditions initiales étant P0(0) = 1 et Pn(0) = 0, l'équation différentielle (4)

s'écrit :

(7) puis intégrant les deux membres, on obtient :

et faisant intervenir le logarithme népérien e, on a : (8) la constante

d'intégration étant nulle.
Passons alors à la première équation du type (6). On a :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 138
Recherche Opérationnelle BAC+3 MP et SCAI

Soit équation différentielle non homogène dont la solution est :

Par récurrence et de proche en proche, on obtient :

La formule générale est : (9) dans laquelle on reconnaît une loi

de Poisson de paramètre λ t.
Cette expression donne la probabilité d'enregistrer n événements, ici des arrivées
dans la file d'attente, pendant une période de durée t, si en moyenne il se produit t événements

pendant une telle durée (Pour t = 1, E(n) = ̅ = λ, et, =√ ).

Supposons qu'en moyenne, un poste de traitement enregistre 4 arrivées à l'heure. A
partir d'une table de la loi de Poisson, il est possible d'évaluer la probabilité que n demandes se
produisent pendant une heure.
Table de la loi de Poisson pour λ = 4

Ainsi, si le système étudié a une capacité de traitement de 4 unités à l'heure, ce qui

est suffisant pour absorber en moyenne les flux de demandes ; il fera cependant apparaître une

file d'attente avec une probabilité de 0,37 (∑ ).

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 139
Recherche Opérationnelle BAC+3 MP et SCAI

Calculons le nombre moyen d'événements ei pour l'intervalle de temps t :

( (10)

(11)
qui est bien le paramètre m = λ t de la loi de Poisson.
a) Modèle à serveur unique (M\M\1\ :PAPS)
C’est le système d’attente avec un serveur et pour lequel les taux d’arrivées
moyens et de services sont des constantes indépendantes de l’état de système.
Notations utilisées

1) Distribution du nombre moyen des clients dans le système

2) Distribution du nombre d’entités dans le système

3) Longueur moyenne de la ligne d’attente

4) Longueur moyenne de la file d’attente

5) Temps d’attente d’une entité arrivant dans le système

Le temps de service est une variable aléatoire suivant une loi exponentielle avec
fonction de densité f(t)= ( )=Me-Mt, t> .Ainsi la probabilité qu’il y ait n entités

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 140
Recherche Opérationnelle BAC+3 MP et SCAI

dans le système est Pn. Il s’en suit que pour Pn 0 la probabilité de taux t:

6) Temps d’attente moyen dans le système au temps t

7) Temps d’attente moyen dans la file

8) Longueur de la ligne d’attente

L=λW

9) La longueur de la file d’attente

Lq=λWq

b) Modèle à plusieurs serveurs (M\M\S\ : PAPS)

Dans ce cas, les arrivées suivent une loi de Poisson avec paramètre λ et lorsque le

temps de service pour chaque unité suit une loi exponentielle avec une moyenne . Par

conséquent quel que soit le nombre S de serveurs qui fournissent le service, la distribution du
temps de service est la même. Le taux moyen de service pour tout le système d’attente c'est-
à-dire la vitesse moyenne à laquelle les unités quittent le système dépend de l’état du système
En.
Puisque le taux moyen de service (serveur occupé) est , on a :

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 141
Recherche Opérationnelle BAC+3 MP et SCAI

Distribution du temps d’attente

Distribution du temps qu’une entité passe dans le système, en incluant le service

Exemple
Une compagnie maritime possède un quai dans un port où ses bateaux déchargent
leurs cargaisons. L’arrivée des bateaux dans le port suit une loi de poisson avec un temps
moyen de 10h entre chaque arrivée. Le temps requis pour le déchargement suit une loi
exponentielle avec une moyenne de 3h. Calculez :
i) le facteur d’utilisation des facilités de service
ii) la probabilité qu’un bateau ait à attendre
iii) le nombre moyen des bateaux dans le port (longueur ligne d’attente)
iv) le nombre moyen des bateaux qui attendent pour être déchargés (longueur de la file
d’attente).
v) le temps moyen qu’un bateau passe dans le système
vi) le temps moyen d’attente pour un bateau
vii) la probabilité qu’un bateau passe plus que t=10h dans le système.
La polycopie sans permission de l’auteur est un manquement scientifique.
Par le Chef de Travaux AMANI MAISHA Sulutani
 142
Recherche Opérationnelle BAC+3 MP et SCAI

Solution

1) Supposons un râtelier dans une usine où les mécaniciens viennent retirer des outils
spéciaux nécessaires pour l’accomplissement d’une tâche particulière leur assignée. Une
étude a été faite sur le temps entre les arrivées et les temps requis de service. Toutes ces
distributions sont adéquatement décrites de façon inversement exponentielle. Le temps
moyen entre arrivées est de 60 secondes et le temps moyen de service est de 50
secondes.
Calculer :
i) la longueur de file d’attente
ii) la longueur de la ligne d’attente
iii) le temps d’attente
iv) le % de temps inoccupé du surveillant
v) le temps qu’un mécanicien passe dans le système

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 143
Recherche Opérationnelle BAC+3 MP et SCAI

Solution

EXERCICES

1) Un système clients serveur reçoit en moyenne 1000 requêtes par secondes, arrivant
selon un processus de Poisson. Il dispose d’un unique serveur pouvant traiter en
moyenne 2000 clients par seconde. On suppose que le temps de service d’un client est
distribué selon la loi exponentielle.
a) Calculer la probabilité que le temps de service dépasse 2ms.
b) Quel est le pourcentage de clients rejetés pour un système ne comportant pas de
file d’attente ?
c) Même question pour un système comportant une fille d’attente de 1 place. Calculer
le taux d’application du serveur.
2) Des camions arrivent dans une station-service pour passer des tests de sécurité, suivant
un processus de Poisson de taux de 6/jour. La durée des testes pour camion est une
valeur exponentielle d’espérance mathématique de 1h30mn. On suppose que le
processus d’arrivée ne s’interrompt pas et que la station travaille 24 heures sur 24.
a) Le système admet-il une distribution stationnaire ? Si oui, calculer et donner le nombre
moyen d’usagers dans le système, la longueur moyenne de la file d’attente et le temps
moyen passé dans la file (en régime stationnaire).

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani
 144
Recherche Opérationnelle BAC+3 MP et SCAI

CONCLUSION
La Recherche Opérationnelle s’impose aujourd’hui comme un outil indispensable pour
la prise de décision dans des environnements complexes et incertains. En combinant des
méthodes quantitatives rigoureuses, telles que la programmation linéaire, la théorie des files
d’attente, la gestion des stocks, la simulation ou encore la théorie des graphes, la RO permet
d’optimiser les ressources, de réduire les coûts et d’améliorer l’efficacité des systèmes. Au-delà
des calculs et des modèles, elle développe également la capacité d’analyser des problèmes
concrets, de structure la réflexion et de proposer des solutions rationnelles face à des situations
pratiques variées, que ce soit en logistique, en production, en finance ou en gestion.
Toutefois, la RO ne se limite pas à des calculs ou des méthodes : elle est l’art de
transformer des problèmes complexes en solutions efficaces. En fournissant des méthodes
rigoureuses pour analyser, optimiser et prévoir, elle permet aux organisations de prendre des
décisions intelligentes, d’utiliser au mieux leurs ressources et de gagner en performances.
Ainsi, la RO n’est pas seulement une discipline théorique : elle constitue un véritable
levier stratégique pour la performance organisationnelle et la compétitivité, préparant les
décideurs à affronter des défis complexes avec méthode et précision.

Merci pour votre attention

La polycopie sans permission de l’auteur est un manquement scientifique.

Par le Chef de Travaux AMANI MAISHA Sulutani