Examen de recherche operationnelle juin 2017 -Programmation
Télécharger PDFRecherche Opérationnelle : Exercices de Programmation Linéaire et Optimisation
La recherche opérationnelle est une discipline qui utilise des méthodes scientifiques pour prendre des décisions optimales, notamment dans les domaines de la gestion, de l'ingénierie et de l'économie. La programmation linéaire est un outil fondamental de la recherche opérationnelle, permettant de résoudre des problèmes où l'on cherche à maximiser ou minimiser une fonction linéaire, sous des contraintes exprimées par des inégalités ou égalités linéaires. Ces exercices illustrent des applications concrètes de la programmation linéaire.
Comprendre les Problèmes d'Optimisation
Chaque problème d'optimisation, comme ceux présentés ci-dessous, se décompose en plusieurs étapes clés :
- Identification des variables de décision : Ce sont les quantités inconnues que nous cherchons à déterminer.
- Définition de la fonction objectif : C'est la fonction linéaire que nous souhaitons maximiser (profit, revenu) ou minimiser (coût, temps).
- Formulation des contraintes : Ce sont les limitations linéaires (capacités, budgets, exigences) qui doivent être respectées par les variables de décision.
Exercice 1 : Optimisation de la production de châssis
Une entreprise envisage de produire deux nouveaux modèles de châssis en utilisant les capacités disponibles de ses trois ateliers. L'objectif est de déterminer les quantités optimales à produire de chaque type de châssis par semaine afin de maximiser le profit total.
Description du Problème
- Produit 1 : Nécessite 1 heure dans l'atelier 1 et 3 heures dans l'atelier 3. Le profit unitaire est de 3 dollars.
- Produit 2 : Nécessite 2 heures dans l'atelier 2 et 2 heures dans l'atelier 3. Le profit unitaire est de 5 dollars.
Capacités des Ateliers par Semaine
- Atelier 1 : 4 heures
- Atelier 2 : 12 heures
- Atelier 3 : 18 heures
Formulation du Programme Linéaire
Pour maximiser le profit, nous devons définir :
- Variables de décision :
- X1 : Nombre de châssis de type 1 à produire par semaine.
- X2 : Nombre de châssis de type 2 à produire par semaine.
- Fonction objectif (à maximiser) :
Profit total = 3*X1 + 5*X2 - Contraintes (selon les capacités des ateliers) :
- Atelier 1 : 1*X1 <= 4
- Atelier 2 : 2*X2 <= 12
- Atelier 3 : 3*X1 + 2*X2 <= 18
- Contraintes de non-négativité : X1 >= 0, X2 >= 0
Exercice 2 : Optimisation d'investissement financier
Un directeur financier souhaite investir une somme totale de 100 unités monétaires dans six types de valeurs, afin de maximiser le revenu généré, tout en respectant certaines règles de la firme.
Options d'Investissement et Intérêts
| Type | Intérêt | Somme Investie |
|---|---|---|
| A1 | 3% | x1 |
| A2 | 2,5% | x2 |
| B1 | 3,5% | y1 |
| B2 | 4% | y2 |
| C1 | 5% | z1 |
| C2 | 4,5% | z2 |
Règles de Conduite de la Firme
- Au moins 40% de la somme totale doit être investie dans les valeurs de type A.
- Pas plus de 35% de la somme totale dans l'une quelconque des autres catégories de valeurs (type B ou type C).
Formulation du Programme Linéaire
- Variables de décision : x1, x2, y1, y2, z1, z2 (montants investis dans chaque type).
- Fonction objectif (à maximiser) :
Revenu = 0.03*x1 + 0.025*x2 + 0.035*y1 + 0.04*y2 + 0.05*z1 + 0.045*z2 - Contraintes :
- Somme totale investie : x1 + x2 + y1 + y2 + z1 + z2 = 100
- Investissement minimum en type A : x1 + x2 >= 0.40 * 100 (soit 40)
- Investissement maximum en type B : y1 + y2 <= 0.35 * 100 (soit 35)
- Investissement maximum en type C : z1 + z2 <= 0.35 * 100 (soit 35)
- Contraintes de non-négativité : x1, x2, y1, y2, z1, z2 >= 0
Exercice 3 : Planification de la production sur machines
Une entreprise fabrique deux produits, P1 et P2, qui nécessitent des opérations sur trois machines M1, M2 et M3. L'objectif est de maximiser le profit en déterminant les quantités de P1 et P2 à produire, en tenant compte des temps d'exécution unitaires et de la disponibilité des machines.
Temps Unitaires d'Exécution (en minutes)
| Produit | M1 | M2 | M3 |
|---|---|---|---|
| P1 | 11 minutes | 7 minutes | 6 minutes |
| P2 | 9 minutes | 12 minutes | 16 minutes |
Disponibilité des Machines
- Machine M1 : 165 heures (soit 9900 minutes)
- Machine M2 : 140 heures (soit 8400 minutes)
- Machine M3 : 160 heures (soit 9600 minutes)
Profits Unitaires
- Produit P1 : 900 dinars
- Produit P2 : 1000 dinars
Formulation du Programme Linéaire
- Variables de décision :
- X1 : Nombre d'unités du produit P1 à fabriquer.
- X2 : Nombre d'unités du produit P2 à fabriquer.
- Fonction objectif (à maximiser) :
Profit total = 900*X1 + 1000*X2 - Contraintes (selon la disponibilité des machines) :
- Machine M1 : 11*X1 + 9*X2 <= 9900
- Machine M2 : 7*X1 + 12*X2 <= 8400
- Machine M3 : 6*X1 + 16*X2 <= 9600
- Contraintes de non-négativité : X1 >= 0, X2 >= 0
Exercice 4 : Optimisation de l'usinage en ateliers
Une entreprise fabrique deux types de pièces, P1 et P2, usinées dans deux ateliers, A1 et A2. Il s'agit de déterminer la quantité de chaque pièce à produire hebdomadairement pour maximiser la marge bénéficiaire, compte tenu des temps d'usinage et de la disponibilité des ateliers.
Temps d'Usinage (en heures)
- Pièce P1 : 3 heures dans l'atelier A1 et 6 heures dans l'atelier A2.
- Pièce P2 : 4 heures dans l'atelier A1 et 3 heures dans l'atelier A2.
Disponibilité Hebdomadaire des Ateliers
- Atelier A1 : 160 heures
- Atelier A2 : 180 heures
Marges Bénéficiaires Unitaires
- Pièce P1 : 1200 Dinars
- Pièce P2 : 1000 Dinars
Formulation du Programme Linéaire
- Variables de décision :
- Y1 : Nombre de pièces P1 à fabriquer par semaine.
- Y2 : Nombre de pièces P2 à fabriquer par semaine.
- Fonction objectif (à maximiser) :
Marge bénéficiaire = 1200*Y1 + 1000*Y2 - Contraintes (selon la disponibilité des ateliers) :
- Atelier A1 : 3*Y1 + 4*Y2 <= 160
- Atelier A2 : 6*Y1 + 3*Y2 <= 180
- Contraintes de non-négativité : Y1 >= 0, Y2 >= 0
FAQ sur la Recherche Opérationnelle et la Programmation Linéaire
Qu'est-ce que la recherche opérationnelle ?
La recherche opérationnelle (RO) est une discipline qui applique des méthodes scientifiques, techniques et analytiques pour optimiser la prise de décision. Elle vise à trouver la meilleure ou la plus rentable des solutions pour des problèmes complexes dans divers domaines tels que l'ingénierie, la logistique, la finance et la gestion de la production.
À quoi sert la programmation linéaire ?
La programmation linéaire (PL) est une technique de modélisation mathématique utilisée pour résoudre des problèmes d'optimisation où la fonction objectif et toutes les contraintes sont linéaires. Elle est employée pour maximiser des profits, minimiser des coûts, optimiser l'utilisation des ressources, planifier la production, gérer des stocks et bien d'autres applications concrètes.
Quels sont les composants clés d'un problème de programmation linéaire ?
Un problème de programmation linéaire est typiquement composé de trois éléments principaux : des variables de décision (les quantités inconnues à déterminer), une fonction objectif (une expression linéaire à maximiser ou minimiser), et des contraintes (un ensemble d'inégalités ou d'égalités linéaires qui limitent les valeurs possibles des variables de décision).