Examen recherche operationnelle juin 2015 -Programmation lin
Télécharger PDFIntroduction à la Programmation Linéaire en Recherche Opérationnelle
La programmation linéaire (PL) est une technique mathématique utilisée pour optimiser une fonction objectif (par exemple, maximiser un profit ou minimiser un coût) sous un ensemble de contraintes. Ces contraintes sont exprimées sous forme d'inégalités ou d'égalités linéaires. Les problèmes ci-dessous illustrent diverses applications de la PL dans des contextes de production, de logistique et de gestion de ressources.
Problème de Planification de Production d'un Artisan
Un artisan fabrique deux articles, A et B, nécessitant chacun deux opérations : un usinage et un traitement thermique. Le produit A subit un usinage d'une heure et un traitement thermique de trois heures. Le produit B subit un usinage de deux heures et un traitement thermique d'une heure. De plus, deux kilogrammes de matière première entrent dans la composition de A et un kilogramme dans celle de B. La fabrication de B se termine par un travail de finition qui dure une heure.
Toutes les trois semaines, l'artisan dispose de l'atelier d'usinage pendant 80 heures et du four pendant 120 heures. De plus, pendant cette période, il ne peut pas consacrer plus de 35 heures au travail de finition ni stocker plus de 90 kilogrammes de matière première. Les marges bénéficiaires s'élèvent, respectivement, à 30 dinars pour l'article A et 20 dinars pour l'article B.
Formulation du Programme Linéaire
Pour déterminer le plan de production optimal, il est nécessaire de formuler un programme linéaire. Cela implique de définir :
- Les variables de décision : Les quantités à produire de chaque article. Par exemple,
xApour le nombre d'unités de l'article A etxBpour le nombre d'unités de l'article B. - La fonction objectif : Maximiser le profit total. Dans ce cas,
Maximiser Z = 30 * xA + 20 * xB. - Les contraintes : Les limites des ressources disponibles (temps d'usinage, temps de traitement thermique, temps de finition, matière première disponible). Ces contraintes doivent être exprimées sous forme d'inégalités linéaires. Par exemple, la contrainte d'usinage serait
1 * xA + 2 * xB ≤ 80(capacité d'usinage). La contrainte de matière première serait2 * xA + 1 * xB ≤ 90(quantité de matière première). - Les contraintes de non-négativité : Les quantités produites ne peuvent pas être négatives (
xA ≥ 0, xB ≥ 0).
Résolution par la Méthode Graphique
La méthode graphique est particulièrement adaptée pour les problèmes de programmation linéaire à deux variables de décision. Elle consiste à tracer les droites correspondant à chaque contrainte et à identifier la région admissible (l'ensemble des points qui respectent toutes les contraintes). Le plan de production optimal se trouve à l'un des sommets de cette région, là où la fonction objectif est maximisée.
Optimisation du Revenu Agricole par Programmation Linéaire
Un agriculteur a le choix entre deux types de culture : A et B. Il souhaite obtenir le revenu maximal de ses cultures. Pour maximiser son profit, il voudrait produire le maximum possible. Cependant, des limites lui sont imposées :
- La part de sa propriété vouée à la culture est limitée à 9 hectares.
- Sa famille et lui-même peuvent fournir au mieux 4 500 heures de travail.
- Enfin, le commerce international lui impose un quota minimum sur le type A de 6,6 hectares.
Nous savons aussi que :
- Un kilogramme de la récolte du type A nécessite 0,0012 hectare et 0,9 heure de travail.
- Un kilogramme de la récolte du type B nécessite 0,0015 hectare et 0,5 heure de travail.
À la fin de la saison, on estime vendre à 40 dinars par kilogramme le type de culture A et 60 dinars par kilogramme le type de culture B.
Formulation du Programme Linéaire
Pour ce problème, les variables de décision pourraient représenter les quantités (en kilogrammes) de culture A (qA) et B (qB) à produire. La fonction objectif serait de maximiser le revenu total (Maximiser Z = 40 * qA + 60 * qB), sous des contraintes de superficie totale disponible, de travail disponible et de quota minimum pour la culture A. Il sera nécessaire de convertir les hectares en kilogrammes ou les kilogrammes en hectares pour homogénéiser les unités dans les contraintes.
Résolution par la Méthode du Simplexe
La méthode du simplexe est un algorithme itératif largement utilisé pour résoudre des problèmes de programmation linéaire de toute taille. Elle explore les sommets de la région admissible (le polyèdre des solutions possibles) de manière systématique jusqu'à trouver la solution optimale. Cette méthode est indispensable lorsque le nombre de variables de décision est supérieur à deux, rendant la méthode graphique inapplicable.
Optimisation de Mélanges de Café et de Stratégie d'Achat/Vente
Un négociant de café importe deux variétés de cafés verts (Colombien et Brésilien) qu'il torréfie et revend sous forme de mélanges. Une tonne de café vert colombien coûte à l'achat 2 800 dinars et permet de produire 800 kilogrammes de café torréfié ; ce dernier a un indice de qualité de 16. Une tonne de café vert brésilien coûte 2 700 dinars et donne 900 kilogrammes de café torréfié avec un indice de qualité de 12.
Le même équipement est partagé pour la torréfaction des deux cafés, et il est disponible 160 heures par mois. Son débit normal est de 40 kilogrammes de café torréfié par heure pour le colombien, et 50 kilogrammes par heure pour le brésilien.
Le négociant vend deux mélanges de café torréfié : le Suprême, au prix de 6 dinars le kilogramme, et l'Insipide, au prix de 4 dinars le kilogramme. L'indice de qualité du mélange Suprême doit être d'au moins 15. Le mélange Insipide ne peut pas contenir plus de 90 % en poids de café torréfié d'origine brésilienne. Pour maintenir une image de qualité, on souhaite que le mélange Suprême assure au moins 70 % du revenu des ventes chaque mois. Le négociant ne peut pas acheter plus de 8 tonnes de café vert colombien ni vendre plus de 4 000 kilogrammes de mélange Suprême par mois.
Formulation du Programme Linéaire (Quantités vendues)
Dans cette première formulation, les variables de décision peuvent représenter les quantités (en kilogrammes) de chaque mélange à vendre (par exemple, xS pour le mélange Suprême et xI pour le mélange Insipide), ainsi que les proportions de café colombien et brésilien torréfié utilisées dans chaque mélange. La fonction objectif serait de maximiser le profit total, calculé à partir des revenus des ventes moins les coûts d'achat des cafés verts. Les contraintes incluraient les limites de torréfaction, les exigences de qualité des mélanges, les proportions de mélange, les quotas d'achat et de vente, et la contrainte sur le revenu minimum du mélange Suprême.
Formulation du Programme Linéaire (Quantités achetées)
Dans la seconde formulation, les variables de décision représenteraient les quantités (en tonnes) de café vert colombien (tC) et brésilien (tB) à acheter. Les quantités de mélanges vendus seraient alors des fonctions de ces quantités achetées et des processus de torréfaction et de mélange. Bien que les variables soient différentes, l'objectif et l'ensemble des contraintes, après conversion et en tenant compte des rendements de torréfaction, devraient être équivalents à la première formulation, menant au même profit optimal.
Maximisation du Profit dans la Production de Châssis
Une entreprise de châssis envisage la production de deux nouveaux modèles au moyen des capacités résiduelles de ses trois ateliers. Le premier produit nécessite le passage dans le premier atelier pour une heure et dans le troisième atelier pour trois heures, tandis que le second produit nécessite le passage dans le deuxième atelier pendant deux heures et dans le troisième atelier pendant aussi deux heures. Le profit unitaire est de 3 $ pour le premier produit et 5 $ pour le second produit. Les capacités hebdomadaires de ces ateliers 1, 2 et 3 sont respectivement 4 heures par semaine, 12 heures par semaine et 18 heures par semaine.
Formulation du Programme Linéaire
Pour déterminer combien de châssis de chaque type produire par semaine afin de maximiser le profit net, nous devons définir :
- Les variables de décision : Les quantités de chaque modèle de châssis à produire. Soient
x1pour le nombre de châssis du premier type etx2pour le second type. - La fonction objectif : Maximiser le profit total, soit
Maximiser Z = 3 * x1 + 5 * x2. - Les contraintes : Les capacités hebdomadaires de chaque atelier.
- Pour l'atelier 1 :
1 * x1 ≤ 4 - Pour l'atelier 2 :
2 * x2 ≤ 12 - Pour l'atelier 3 (partagé) :
3 * x1 + 2 * x2 ≤ 18
- Pour l'atelier 1 :
- Les contraintes de non-négativité :
x1 ≥ 0, x2 ≥ 0.
Formulation d'un Programme Linéaire pour la Fabrication d'un Produit Composé
Une unité d'un certain produit P est fabriquée par l'assemblage de quatre unités d'un élément A et trois unités d'un élément B. Dans la fabrication de A et B, on utilise deux types de matières premières (M1 et M2) disponibles en quantités de 100 et 200 unités respectivement par mois. Les éléments A et B sont fabriqués dans trois départements utilisant chacun un processus de production différent. La technologie utilisée est résumée dans le tableau ci-après qui indique les "entrées" de matières M1 et M2 et les "sorties" d'unités A et B par "application" du processus de production par département.
| Département | Entrée de matière | Sortie d'élément | ||
|---|---|---|---|---|
| M1 | M2 | A | B | |
| 1 | 8 | 6 | 7 | 5 |
| 2 | 5 | 9 | 6 | 9 |
| 3 | 3 | 8 | 8 | 4 |
Formulation du Programme Linéaire
L'entreprise veut déterminer le nombre d'applications de chaque processus de production (de chaque département) qui permettrait de maximiser le nombre total d'unités de produit P. Pour cela :
- Les variables de décision : Le nombre d'applications de chaque processus (département), soit
d1,d2etd3. - La fonction objectif : Maximiser la production de P. Puisque P nécessite 4 unités de A et 3 unités de B, nous cherchons à maximiser une variable
z, telle queTotal A produit ≥ 4zetTotal B produit ≥ 3z. La fonction objectif devient alorsMaximiser Z = z. - Les contraintes : Les disponibilités en matières premières M1 et M2, ainsi que les équilibres entre production de A et B pour l'assemblage de P.
- Contrainte M1 :
8*d1 + 5*d2 + 3*d3 ≤ 100 - Contrainte M2 :
6*d1 + 9*d2 + 8*d3 ≤ 200 - Production totale de A :
Total A = 7*d1 + 6*d2 + 8*d3 - Production totale de B :
Total B = 5*d1 + 9*d2 + 4*d3 - Contraintes d'assemblage de P :
4*z ≤ Total Aet3*z ≤ Total B
- Contrainte M1 :
- Les contraintes de non-négativité :
d1, d2, d3 ≥ 0etz ≥ 0.
Problème de Découpage Optimal dans la Production de Papier
La compagnie de papier Nord-Ouest produit et commercialise des rouleaux de papier de quatre longueurs différentes : 12 pouces, 5 pouces, 3,5 pouces et 2 pouces. Tous les rouleaux ont une même longueur de 100 pieds. La compagnie ne fabrique que des rouleaux de 12 pouces de largeur, appelés des rouleaux standards. Les autres largeurs sont obtenues par le découpage des rouleaux standards. La compagnie est en train d'envisager les six plans de découpage suivants, dont chacun résulte en une chute inférieure ou égale à un pouce.
| Plan de découpage | Largeur du rouleau (pouces) | Chute en pouces | ||
|---|---|---|---|---|
| 5 pouces | 3,5 pouces | 2 pouces | ||
| 1 | 0 | 0 | 6 | 0 |
| 2 | 2 | 0 | 1 | 0 |
| 3 | 0 | 2 | 2 | 1 |
| 4 | 1 | 2 | 0 | 0 |
| 5 | 1 | 0 | 3 | 1 |
| 6 | 0 | 1 | 4 | 0,5 |
Exploration des Plans de Découpage
Un plan de découpage est une combinaison spécifique de largeurs de rouleaux qui peut être obtenue à partir d'un rouleau standard (12 pouces), tout en minimisant la chute. Pour déterminer si un septième plan de découpage est possible avec une chute inférieure ou égale à un pouce, il faut explorer les combinaisons possibles de rouleaux de 5, 3,5 et 2 pouces dont la somme des largeurs est comprise entre 11 et 12 pouces (12 pouces de standard - 1 pouce de chute max = 11 pouces). Par exemple, la combinaison de deux rouleaux de 5 pouces et un rouleau de 2 pouces donne un total de 12 pouces (2*5 + 1*2 = 12), soit 0 pouce de chute (ce qui correspond au plan 2). D'autres combinaisons systématiques devraient être testées pour vérifier s'il existe une nouvelle configuration valide.
Les demandes minimales pour les rouleaux obtenus par le découpage sont données par le tableau suivant :
| Largeur du rouleau | Demande minimale |
|---|---|
| 5 pouces | 1 500 |
| 3,5 pouces | 2 000 |
| 2 pouces | 500 |
Formulation du Programme Linéaire pour les Demandes Minimales
Ce problème est un exemple classique de problème de "cutting stock" ou de découpe. Le but est de satisfaire la demande minimale pour chaque type de rouleau découpé en utilisant le minimum de rouleaux standards de 12 pouces. Les variables de décision seraient le nombre de fois que chaque plan de découpage (x1 pour le plan 1, x2 pour le plan 2, etc.) est utilisé. La fonction objectif serait de minimiser la somme de ces variables (Minimiser Z = x1 + x2 + ... + x6). Les contraintes assureraient que la somme des rouleaux de chaque largeur produits par tous les plans utilisés est supérieure ou égale à la demande minimale. Par exemple, pour les rouleaux de 5 pouces : 0*x1 + 2*x2 + 0*x3 + 1*x4 + 1*x5 + 0*x6 ≥ 1 500. Les variables xi doivent être des entiers non-négatifs.
Foire Aux Questions (FAQ) sur la Programmation Linéaire
Qu'est-ce que la Programmation Linéaire (PL) ?
La Programmation Linéaire est une technique mathématique d'optimisation utilisée pour trouver la meilleure solution (maximiser un profit, minimiser un coût, etc.) parmi un ensemble de solutions possibles. Elle s'applique lorsque la fonction objectif et toutes les contraintes peuvent être exprimées comme des relations linéaires, et les variables de décision sont continues.
Pourquoi la Programmation Linéaire est-elle importante en gestion et production ?
La PL permet aux entreprises de prendre des décisions éclairées face à des ressources limitées. Elle aide à optimiser l'allocation des ressources (temps, matériaux, main-d'œuvre, capital) pour atteindre des objectifs spécifiques, ce qui peut se traduire par des économies significatives ou une augmentation de l'efficacité et des profits. C'est un outil puissant pour la planification de la production, la logistique, la gestion de portefeuille, et plus encore.
Quelle est la différence entre la méthode graphique et la méthode du simplexe ?
La méthode graphique est une approche visuelle pour résoudre des problèmes de PL avec seulement deux variables de décision. Elle implique de tracer les contraintes sur un graphique pour identifier la région admissible et le point optimal. La méthode du simplexe est un algorithme algébrique plus général, capable de résoudre des problèmes avec un nombre quelconque de variables de décision et de contraintes, et est implémentée dans la plupart des logiciels de résolution de PL.