Ecole supérieure de Gestion et d’Economie Numérique, KOLEA
2023-2024
Recherche Opérationnelle
Chapitre 1 : Généralités sur la programmation linéaire
Chapitre 2 : Méthode du simplexe
Chapitre 1 : Généralités sur la Programmation Linéaire
1- Introduction générale
La Recherche Opérationnelle, en abrégé RO, est une branche des
mathématiques appliquées qui s’intéresse à l’élaboration de meilleures
décisions (décisions optimales) dans les problèmes d’organisations. Cette
organisation peut représenter des domaines très divers tels que l’industrie, le
transport, la production, le bâtiment, la télécommunication, la finance, les soins
de santé, etc.
Si la recherche opérationnelle est aujourd’hui présente dans la plupart des
domaines civils, ses racines sont habituellement attribuées aux services
militaires. En effet, durant la seconde guerre mondiale, l’organisation militaire
Britannique et Américaine, ont formé une équipe de scientifiques pour
effectuer des recherches sur des opérations à caractère militaires, d’où sa
nomination. Les problèmes traités durant cette période étaient liés à
l’implantation optimale des radars de surveillance, la composition des convois
maritimes et l’optimisation du parcours. La résolution de tels problèmes a
suscité le terme Programmation linéaire, inventé par George Dantzig. En effet,
le terme programmation, désigne planification, vient de l’usage du mot
programme par les forces de l’armée américaine pour établir des horaires de
formation et des choix logistiques que Dantzig étudiait à l’époque.
1
Après le deuxième conflit mondial, la croissance importante de l’industrie a
entrainé des problèmes proches de ceux présent lors du conflit, ainsi, la
dénomination est restée, même si le domaine militaire n’est plus le principal
champ d’application de cette discipline. Sans oublier que le développement de
l’outil informatique a facilité l’intégration de la RO dans l’industrie, car La
plupart des outils de la RO nécessitent en effet un support informatique pour
résoudre les problèmes auxquels ils s'attaquent.
Les champs d’application de la RO dans l’entreprise
Les contributions de la RO au sein de l’entreprise sont différentes. On peut citer
quelques exemples :
● Production : Plusieurs activités liées à la production de biens et de
services bénéficient des apports de la RO. Supposons à titre d’exemple qu’une
entreprise dispose de moyens limités (personnels, machines, matières
premières). On peut s’intéresser initialement à la disposition optimale des
machines afin de maximiser le rendement des ouvriers ou de faciliter le cycle
de production. Par ailleurs, en fonction de ces moyens limités, la RO peut
fournir un plan de production (quantités des différents produits à fabriquer)
journalier ou hebdomadaire permettant un meilleur retour à l’entreprise en
matière de bénéfices.
Dans le bâtiment, tout projet d’une certaine importance comporte plusieurs
tâches (fondations, murs, toits, fenêtres,…) présentant entre elles des relations
d’antériorités. Pour réaliser ces tâches, on dispose de temps et de moyens et on
s’intéresse à déterminer la durée minimale du projet ainsi son cout de
réalisation.
Dans les entreprises qui fournissent des services (gares, aéroports,…), on peut
rencontrer des applications de la RO dans les problèmes liés à la dimension des
locaux, nombre des guichets et à l’élaboration des règles de passage des clients
afin de minimiser leurs durées d’attentes dans les files.
● Logistique : La RO peut couvrir les problèmes de localisations de
dépôts et de magasins. En effet, on peut se proposer de déterminer
l’emplacement des dépôts chargés d’approvisionner des points de ventes, en
tenant compte par exemple des coûts liés au fonctionnement des dépôts et à
2
l’approvisionnement des clients, ainsi, on cherche à trouver
l’approvisionnement qui minimise le coût global.
Le choix des meilleures routes à partir des dépôts est une autre préoccupation
à laquelle répond la RO. Dans ce contexte, on peut s’intéresser à effectuer une
seule tournée pour approvisionner tous les points de ventes, de façon à
minimiser la distance globale parcourue.
● Ressources humaines : La gestion des ressources humaines
bénéficie également de la RO. Par exemple, dans une entreprise, un ensemble
de postes étant décrit et chaque personne disponible à les compétences pour
occuper certains d’entre eux. Ainsi, on s’intéresse à l’affectation optimale du
personnel aux différents postes afin d’avoir un rendement global meilleur.
La répartition des tâches entre des agents ou des équipes est une
préoccupation de la RO. Un exemple classique est fourni dans les compagnies
aériennes lors de la répartition des missions entes les équipages.
Démarche de la RO
Face à une problématique réelle, l’approche de la Recherche opérationnelle
consiste à :
● Elaborer un modèle mathématique. Un modèle mathématique est une
représentation graphique, ou une série d’équations qui décrivent des
relations entre variables d’une manière précise pour traduire certains
aspects d’un problème réel.
● Résoudre le modèle.
● Evaluer la qualité des solutions dans l’environnement réel du problème.
2- La programmation linéaire
La programmation linéaire (PL), désignée parfois sous l’appellation
d’optimisation linéaire, occupe une place centrale dans la Recherche
Opérationnelle. En effet, beaucoup de problèmes réels de RO peuvent être
exprimés comme étant un problème de PL. Ainsi, cette dernière est le sujet
central de ce module. Afin de mieux introduire les concepts et les notations que
nous utiliserons, considérons l’exemple suivant, version simplifiée d’un
problème de programmation linéaire réel.
3
Exemple
Une entreprise fabrique deux types de camions (types A et B). Cette entreprise
Est divisée en trois ateliers, l'atelier I fabriquant les moteurs, l'atelier II
fabriquant les carrosseries, l'atelier III étant chargé de l’assemblage.
Les temps unitaires pour chacune des trois opérations et pour chaque type de
camions sont représentés dans le tableau suivant :
Ateliers Camion de type A Camion de type B
I (Moteurs) 1h 3h
II (Carrosseries) 2h 1h
III (Assemblage) 1h 1h
Par ailleurs, l'étude des capacités de production des 3 ateliers a dégagé qu'en
un mois, 450 heures de travail pouvaient être utilisées dans l'atelier I, 350
heures dans l'atelier II, 200 dans l'atelier III.
Enfin, on sait que le bénéfice unitaire réalisé par l'entreprise sur les camions de
type A s'élève à 4000 et que celui réalisé sur les camions de type B est de 8000.
La question que l'on se pose est la suivante : quelle doit être la production
mensuelle en camions de chaque type pour rendre le bénéfice de l'entreprise le
plus grand possible ?
