Ecole des Hautes Etudes Commerciales Module RO – 1ère Année Master Ecole des Hautes Etudes Commerciales Module
e des Hautes Etudes Commerciales Module RO – 1ère Année Master
EHEC, Alger Année Universitaire 2013/2014 EHEC, Alger Année Universitaire 2013/2014
Enseignante : Amina GACEM Groupes 10 11 Enseignante : Amina GACEM Groupes 10 11
Cours 1 : Introduction à la Programmation Linéaire
1. Introduction [Link] contraintes
La prise de décision est au cœur de toute activité économique : agricole, industrielle, bancaire, Une contrainte est une équation ou inéquation linéaire où apparaissent les variables de
commerciale…etc. Une décision ne peut être prise aléatoirement, elle est le résultat d’une décision. La contrainte indique une limitation de ressource qui va influencer la prise de
modélisation rigoureuse, d’une analyse poussée et de la prise en compte de plusieurs décision, chose qui se produit souvent dans les entreprises.
paramètres, et ce afin d’atteindre un objectif stratégique. Au milieu du 20ième siècle, la
[Link] variables de décisions
complexité des problèmes à caractère décisionnel apparus aussi bien dans le monde
économique que politique ou militaire est devenue telle qu’il est devenu impératif de proposer Elles représentent la décision à prendre dans le problème à traiter. La décision consiste à
des outils efficaces pour pouvoir apporter des solutions. Les méthodes traditionnelles des déterminer un ensemble de valeurs qui maximise un profit tout en respectant un nombre de
mathématiques classiques tendaient à être trop lentes dans des secteurs où le critère temps est contraintes. On les reconnait dans un énoncé aisément : ce sont les seuls paramètres qui
crucial pour la prise de décision. C’est dans ce contexte que la recherche opérationnelle est peuvent être contrôlés par le décideur.
apparue (RO). La RO est une discipline qui propose des méthodes de résolutions efficaces
pour traiter des problèmes relatifs à la prise de décision. La RO compte plusieurs branches : la [Link] général d’un PL
programmation mathématique, la théorie des graphes, les méta-heuristiques..etc. Un PL se présente sous la forme suivante :
La maîtrise de la RO vous permettra d’être capable de transformer un problème économique Fonction Objectif : Max Z = ……+
décisionnel en un modèle mathématique sur lequel vous appliquerez une méthode de
résolution de manière simple et intuitive. Contraintes : ……+ ≤
2. La modélisation en PL ……+ ≤
L’une des techniques de programmation mathématique les plus connues est la programmation …………………………………………………..
linéaire (PL). Elle fournit des outils de modélisation et de résolution à des problèmes où l’on
est sous contrainte de ressources limités pour réaliser des activités concurrentes dans un but ……+ ≤
de profit maximum. La solution serait de trouver un plan optimal d’affectation/combinaison Les variables de décision : ≥ 0, ≥ 0, ≥ 0, … … . ≥0
de ressources. En effet, le monde de l’entreprise regorge de problèmes qui consistent à
élaborer des plans financiers, plans de productions, plans de couvertures publicitaires, circuits Exemple : problème de production 1
logistiques, transports, distribution et acheminement. Ces plans doivent permettre à
l’entreprise de réaliser le maximum de profit. 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
Un programme linéaire est un ensemble de contraintes linéaires traduisant un état dans lequel d’exécution sont donnés par le tableau suivant :
les ressources sont limitées, une fonction objectif qui représente l’objectif à maximiser et des M1 M2 M3
variables de décision qui représentent la décision à prendre. La résolution du PL consistera P1 11 mn 7 mn 6 mn
alors à déterminer les meilleures valeurs pour les variables de décision, c’est-à-dire celles qui P2 9 mn 12 mn 16 mn
respectent les contraintes tout en optimisant la fonction objectif. On supposera que les machines n’ont pas de temps d’inactivité.
La disponibilité pour chaque machine sont :
[Link] objectif • 165 heures (9900 minutes) pour la machine M1 ;
• 140 heures (8400 minutes) pour la machine M2 ;
Une décision est prise afin d’atteindre un objectif. Généralement les entreprises ont un • 160 heures (9600 minutes) pour la machine M3 .
objectif de maximisation de profit ou de rendement. La fonction objectif est alors représentée Le produit P1 donne un profit unitaire de 900 dinars et le produit P2 un profit unitaire de
sous forme d’expression linéaire où apparaissent les variables de décision. On peut également 1000 dinars.
avoir des PL où l’objectif consiste à minimiser les coûts. Dans ces conditions, combien doit-on fabriquer mensuellement de produits P1 et P2 pour
avoir un profit total maximum ?
1
Méthodes et modèles de la recherche opérationnelle, A. Kaufmann, pp 22-23
1 2
Ecole des Hautes Etudes Commerciales Module RO – 1ère Année Master
EHEC, Alger Année Universitaire 2013/2014
Enseignante : Amina GACEM Groupes 10 11
Formulation en un PL :
Etape 1 : Déterminer les variables de décision.
Nous avons deux produits P1 et P2 dont on doit déterminer les quantités mensuelles à
produire.
Les variables de décisions sont :
• x1 : le nombre d’unités du produit P1 à fabriquer.
• x2 : le nombre d’unités du produit P2 à fabriquer.
Etape 2 : déterminer les contraintes.
Nous voyons que chaque machine dispose d’un temps de disponibilité mensuelle à ne pas
dépasser. La fabrication de chaque produit consomme un temps de chaque machine. Ici, le
temps de disponibilité représente la ressource limitée. Nous devons veiller que le temps de
fabrication de tous les produits ne dépassent pas la disponibilité de chaque machine.
Les contraintes sont donc:
• 11x1 + 9 x 2 ≤ 9900 pour la machine M1
• 7 x1 + 12 x 2 ≤ 8400 pour la machine M2
• 6 x1 + 16 x 2 ≤ 9600 pour la machine M3
Etape 3 : Déterminer la fonction objectif.
D’après l’énoncé, on souhaite maximiser le profit. Le profit dépend de la quantité de produits
fabriqués. Nous avons le profit unitaire de chaque unité de produit.
Le profit à maximiser est : z = 900 x1 + 1000 x 2
Le programme linéaire résultant est :
Max ( Z ) = 900 x 1 + 1000 x2
s .c . 1 1 x 1 + 9 x 2 ≤ 9900
7 x 1 + 12 x 2 ≤ 8400
6 x 1 + 16 x 2 ≤ 9600
x1 ≥ 0 , x 2 ≥ 0