3eme annee finance recherche operationnelle serie 1 -Program
Télécharger PDFIntroduction à la Programmation Linéaire et Exercices Corrigés
Cette série d'exercices corrigés est conçue pour approfondir la compréhension de la programmation linéaire, une technique essentielle en recherche opérationnelle. Chaque problème présente un scénario pour lequel il faut formuler un programme linéaire afin d'optimiser une fonction objectif sous diverses contraintes. Les corrections détaillées aident à maîtriser la modélisation et la résolution de ces problèmes.
Exercice n°1: Identification des Contraintes Linéaires
Déterminez lesquelles des contraintes suivantes (ou leurs équivalentes) peuvent être utilisées dans un programme linéaire :
- x² + x₁x₂ = 15
- √2x₁ + x₂ ≤ 20
- 5x₁ / (x₁ + x₂) ≤ 4
- 3x₁ + 7x₂ < 5
- 2x₁ + x₂ = 40
- √3x₁ + 2x₂ ≤ 12
Correction Exercice n°1
Un programme linéaire (PL) est caractérisé par une fonction objectif et des contraintes qui doivent toutes être linéaires. Une expression est linéaire si elle est une somme de termes, où chaque terme est soit une constante, soit le produit d'une constante par une seule variable (de puissance 1). Les non-linéarités incluent les produits de variables (x₁x₂), les puissances (x²), les racines carrées (√x), et les divisions par des variables.
Analysons chaque contrainte :
x² + x₁x₂ = 15: NON linéaire. Contient un terme quadratique (x²) et un produit de variables (x₁x₂).√2x₁ + x₂ ≤ 20: LINÉAIRE. √2 est une constante. L'expression est une somme de termes linéaires.5x₁ / (x₁ + x₂) ≤ 4: NON linéaire dans sa forme actuelle car elle implique une division par des variables. Cependant, si on suppose que(x₁ + x₂) > 0, on peut la réécrire comme5x₁ ≤ 4(x₁ + x₂), ce qui donne5x₁ ≤ 4x₁ + 4x₂, et finalementx₁ - 4x₂ ≤ 0. Cette dernière forme est linéaire. Pour un PL standard, la transformation doit être valide dans le domaine du problème.3x₁ + 7x₂ < 5: LINÉAIRE. Cependant, en programmation linéaire, les contraintes sont généralement des inégalités larges (≤ou≥) ou des égalités (=). Une inégalité stricte (<) peut être problématique car elle implique un domaine ouvert, ce qui peut rendre la recherche de la solution optimale plus complexe ou nécessiter des ajustements pour des valeurs arbitrairement proches.2x₁ + x₂ = 40: LINÉAIRE. C'est une égalité linéaire.√3x₁ + 2x₂ ≤ 12: LINÉAIRE. √3 est une constante. L'expression est une somme de termes linéaires.
En résumé, les contraintes directement linéaires sont √2x₁ + x₂ ≤ 20, 2x₁ + x₂ = 40, et √3x₁ + 2x₂ ≤ 12. La contrainte 5x₁ / (x₁ + x₂) ≤ 4 peut être linéarisée en x₁ - 4x₂ ≤ 0 sous certaines conditions. La contrainte 3x₁ + 7x₂ < 5, bien que linéaire, utilise une inégalité stricte, ce qui est à éviter dans la formulation standard d'un PL.
Exercice n°2: Maximisation de la Marge dans une Production
Soit une entreprise qui fabrique deux types de pièces, P₁ et P₂, usinées dans deux ateliers, A₁ et A₂. Les temps d'usinage sont les suivants :
- Pour P₁ : 3 heures dans l'atelier A₁ et 6 heures dans l'atelier A₂.
- Pour P₂ : 4 heures dans l'atelier A₁ et 3 heures dans l'atelier A₂.
Le temps de disponibilité hebdomadaire de l'atelier A₁ est de 160 heures, et celui de l'atelier A₂ est de 180 heures. Le bénéfice unitaire est de 1200 Dinars pour une pièce P₁ et de 1000 Dinars pour une pièce P₂.
Formulez ce problème à l'aide d'un programme linéaire dont l'objectif est de maximiser la marge hebdomadaire de cette entreprise.
Correction Exercice n°2
1. Variables de décision
x₁: Nombre d'unités de pièces P₁ à produire par semaine.x₂: Nombre d'unités de pièces P₂ à produire par semaine.
2. Fonction objectif (à maximiser)
Maximiser le bénéfice total hebdomadaire (Z) :
Max Z = 1200x₁ + 1000x₂
3. Contraintes
- Contrainte de capacité de l'atelier A₁ : Le temps total passé dans l'atelier A₁ ne doit pas dépasser sa capacité de 160 heures.
- Contrainte de capacité de l'atelier A₂ : Le temps total passé dans l'atelier A₂ ne doit pas dépasser sa capacité de 180 heures.
3x₁ + 4x₂ ≤ 160
6x₁ + 3x₂ ≤ 180
4. Contraintes de non-négativité
Les quantités produites ne peuvent pas être négatives :
x₁ ≥ 0, x₂ ≥ 0
Exercice n°3: Optimisation de la Production de Chaises
Un menuisier fabrique trois types de chaises : Chaise A, Chaise B, et Chaise C. Le processus de fabrication de chaque chaise passe par trois opérations différentes. Chaque opération nécessite un certain temps (en heures) par unité de produit. Pour chaque opération, la capacité en temps par jour est limitée. Un bénéfice unitaire est réalisé sur chaque type de chaise, sachant que toute la production est vendue.
Les données du problème sont consignées dans le tableau suivant :
| Opération | Chaise A (h/unité) | Chaise B (h/unité) | Chaise C (h/unité) | Capacité (h/jour) |
|---|---|---|---|---|
| 1 | 1 | 2 | 4 | 4 |
| 2 | 3 | 1 | 5 | 9 |
| 3 | 1 | 3 | 1 | 2 |
| Bénéfice unitaire (Dinars) | 2 | 1 | 1 |
Formulez ce problème à l'aide d'un programme linéaire dont l'objectif est de maximiser le profit du menuisier.
Correction Exercice n°3
1. Variables de décision
x₁: Nombre de chaises de type A à produire par jour.x₂: Nombre de chaises de type B à produire par jour.x₃: Nombre de chaises de type C à produire par jour.
2. Fonction objectif (à maximiser)
Maximiser le bénéfice total journalier (Z) :
Max Z = 2x₁ + 1x₂ + 1x₃
3. Contraintes
- Contrainte de capacité d'opération 1 : Le temps total alloué à l'opération 1 ne doit pas dépasser sa capacité.
- Contrainte de capacité d'opération 2 : Le temps total alloué à l'opération 2 ne doit pas dépasser sa capacité.
- Contrainte de capacité d'opération 3 : Le temps total alloué à l'opération 3 ne doit pas dépasser sa capacité.
1x₁ + 2x₂ + 4x₃ ≤ 4
3x₁ + 1x₂ + 5x₃ ≤ 9
1x₁ + 3x₂ + 1x₃ ≤ 2
4. Contraintes de non-négativité
Les quantités produites ne peuvent pas être négatives :
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0
Exercice n°4: Maximisation du Profit avec Plusieurs Machines
Pour fabriquer deux produits P₁ et P₂, des opérations doivent être effectuées sur trois machines (M₁, M₂, et M₃) successivement. Les temps unitaires d'exécution sont donnés par le tableau suivant :
| Machine | P₁ (mn/unité) | P₂ (mn/unité) |
|---|---|---|
| M₁ | 11 | 9 |
| M₂ | 7 | 12 |
| M₃ | 6 | 16 |
Les disponibilités pour chaque machine sont :
- Machine M₁ : 165 heures (soit 9900 minutes)
- Machine M₂ : 140 heures (soit 8400 minutes)
- Machine M₃ : 160 heures (soit 9600 minutes)
Le produit P₁ donne un bénéfice unitaire de 900 Dinars et le produit P₂ un bénéfice unitaire de 1000 Dinars.
Formulez le problème qui permet de maximiser le profit sous la forme d'un programme linéaire.
Correction Exercice n°4
1. Variables de décision
x₁: Nombre d'unités du produit P₁ à fabriquer.x₂: Nombre d'unités du produit P₂ à fabriquer.
2. Fonction objectif (à maximiser)
Maximiser le profit total (Z) :
Max Z = 900x₁ + 1000x₂
3. Contraintes
- Contrainte de capacité pour la machine M₁ : Le temps total d'utilisation de M₁ ne doit pas dépasser sa capacité.
- Contrainte de capacité pour la machine M₂ : Le temps total d'utilisation de M₂ ne doit pas dépasser sa capacité.
- Contrainte de capacité pour la machine M₃ : Le temps total d'utilisation de M₃ ne doit pas dépasser sa capacité.
11x₁ + 9x₂ ≤ 9900 (en minutes)
7x₁ + 12x₂ ≤ 8400 (en minutes)
6x₁ + 16x₂ ≤ 9600 (en minutes)
4. Contraintes de non-négativité
Les quantités produites ne peuvent pas être négatives :
x₁ ≥ 0, x₂ ≥ 0
Exercice n°5: Formulation Générique d'un Problème de Production
Une entreprise fabrique trois produits P₁, P₂, P₃. La fabrication de chaque produit passe nécessairement par quatre départements D₁, D₂, D₃ et D₄. On désigne par aᵢⱼ le nombre d'heures nécessaires dans le processus de fabrication d'une unité du produit Pᵢ dans le département Dⱼ. Le bénéfice unitaire de chaque produit Pᵢ est cᵢ dinars, et le temps disponible de chaque département Dⱼ est bⱼ heures.
Formulez ce problème à l'aide d'un programme linéaire dont l'objectif est de maximiser le profit total de cette entreprise.
Correction Exercice n°5
Ce problème est une généralisation des exercices précédents, utilisant des indices pour représenter les différentes entités.
1. Variables de décision
xᵢ: Quantité du produit Pᵢ à fabriquer, pour i = 1, 2, 3.
2. Fonction objectif (à maximiser)
Maximiser le profit total (Z) :
Max Z = c₁x₁ + c₂x₂ + c₃x₃
Ou, en notation sommatoire :
Max Z = ∑ᵢ=₁³ cᵢxᵢ
3. Contraintes
Pour chaque département Dⱼ (j = 1, 2, 3, 4), le temps total alloué ne doit pas dépasser sa capacité disponible bⱼ :
- Département D₁ :
a₁₁x₁ + a₂₁x₂ + a₃₁x₃ ≤ b₁ - Département D₂ :
a₁₂x₁ + a₂₂x₂ + a₃₂x₃ ≤ b₂ - Département D₃ :
a₁₃x₁ + a₂₃x₂ + a₃₃x₃ ≤ b₃ - Département D₄ :
a₁₄x₁ + a₂₄x₂ + a₃₄x₃ ≤ b₄
Ou, en notation sommatoire, pour chaque département j :
∑ᵢ=₁³ aᵢⱼxᵢ ≤ bⱼ (pour j = 1, 2, 3, 4)
4. Contraintes de non-négativité
Les quantités produites ne peuvent pas être négatives :
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0
Ou, de manière générale :
xᵢ ≥ 0 pour i = 1, 2, 3.
Exercice n°6: Optimisation d'un Portefeuille d'Investissement
Le directeur financier d'une firme désire investir une somme d'argent totale de 100 unités monétaires de manière à maximiser le revenu. Il considère les six possibilités d'investissement suivantes :
| Type d'investissement | A₁ | A₂ | B₁ | B₂ | C₁ | C₂ |
|---|---|---|---|---|---|---|
| Taux d'intérêt annuel | 3% | 2.5% | 3.5% | 4% | 5% | 4.5% |
| Somme investie (variable) | X₁ | X₂ | Y₁ | Y₂ | Z₁ | Z₂ |
Ce directeur n'est pas totalement libre de son choix, car selon la règle de conduite de la firme :
- Au moins 40% de la somme totale doit être investie dans des valeurs du type A (A₁ ou A₂).
- Pas plus de 35% de la somme totale ne doit être investie dans l'une quelconque des autres valeurs (B₁, B₂, C₁, C₂).
Formulez le problème qui permet de maximiser le revenu de ce directeur sous la forme d'un programme linéaire.
Correction Exercice n°6
1. Variables de décision
X₁: Somme investie dans le type A₁.X₂: Somme investie dans le type A₂.Y₁: Somme investie dans le type B₁.Y₂: Somme investie dans le type B₂.Z₁: Somme investie dans le type C₁.Z₂: Somme investie dans le type C₂.
2. Fonction objectif (à maximiser)
Maximiser le revenu total (Z) :
Max Z = 0.03X₁ + 0.025X₂ + 0.035Y₁ + 0.04Y₂ + 0.05Z₁ + 0.045Z₂
3. Contraintes
- Contrainte de la somme totale à investir : La somme de tous les investissements doit être égale à la somme totale disponible.
- Contrainte d'investissement minimal pour le type A : Au moins 40% de 100 unités monétaires doivent être investies dans des valeurs de type A.
- Contrainte d'investissement maximal pour les autres types (B₁, B₂, C₁, C₂) : Pas plus de 35% de 100 unités monétaires pour chaque type individuel.
X₁ + X₂ + Y₁ + Y₂ + Z₁ + Z₂ = 100
X₁ + X₂ ≥ 0.40 * 100 ⇒ X₁ + X₂ ≥ 40
Y₁ ≤ 0.35 * 100 ⇒ Y₁ ≤ 35
Y₂ ≤ 0.35 * 100 ⇒ Y₂ ≤ 35
Z₁ ≤ 0.35 * 100 ⇒ Z₁ ≤ 35
Z₂ ≤ 0.35 * 100 ⇒ Z₂ ≤ 35
4. Contraintes de non-négativité
Les sommes investies ne peuvent pas être négatives :
X₁ ≥ 0, X₂ ≥ 0, Y₁ ≥ 0, Y₂ ≥ 0, Z₁ ≥ 0, Z₂ ≥ 0
Exercice n°7: Maximisation des Recettes avec Durées d'Occupation des Machines
Trois types de machines peuvent être utilisées pour fabriquer quatre produits selon les durées d'occupation suivantes (par unité produite) :
| Machine | Produit 1 | Produit 2 | Produit 3 | Produit 4 |
|---|---|---|---|---|
| Machine 1 | 1 h | 0 h 30 mn (0.5 h) | 1 h 30 mn (1.5 h) | 1 h |
| Machine 2 | 1 h | 1 h 30 mn (1.5 h) | 1 h | 1 h 15 mn (1.25 h) |
| Machine 3 | 1 h 30 mn (1.5 h) | 1 h | 0 h 45 mn (0.75 h) | 1 h |
Écrivez, en fonction des durées d'utilisation maximales (capacités) des trois types de machines et des prix de vente des quatre produits, le problème d'optimisation qui maximise les recettes.
Correction Exercice n°7
Pour formuler ce problème, nous allons utiliser des symboles génériques pour les capacités des machines et les prix des produits, car ces valeurs ne sont pas données numériquement dans l'énoncé. Nous convertirons toutes les durées en heures pour une cohérence.
1. Variables de décision
xⱼ: Quantité du produit j à fabriquer, pour j = 1, 2, 3, 4.
2. Fonction objectif (à maximiser)
Maximiser les recettes totales (Z) :
Soit Pⱼ le prix de vente unitaire du produit j.
Max Z = P₁x₁ + P₂x₂ + P₃x₃ + P₄x₄
3. Contraintes
Soit Cₖ la durée d'utilisation maximale (capacité) de la machine k (pour k = 1, 2, 3).
- Contrainte de capacité pour la Machine 1 :
- Contrainte de capacité pour la Machine 2 :
- Contrainte de capacité pour la Machine 3 :
1x₁ + 0.5x₂ + 1.5x₃ + 1x₄ ≤ C₁
1x₁ + 1.5x₂ + 1x₃ + 1.25x₄ ≤ C₂
1.5x₁ + 1x₂ + 0.75x₃ + 1x₄ ≤ C₃
4. Contraintes de non-négativité
Les quantités produites ne peuvent pas être négatives :
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0
Exercice n°8: Production de Châssis pour Maximiser le Profit
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 (P₁) nécessite le passage dans l'atelier 1 pendant 1 heure et dans l'atelier 3 pendant 3 heures.
- Le second produit (P₂) nécessite le passage dans l'atelier 2 pendant 2 heures et dans l'atelier 3 pendant aussi 2 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.
Combien faut-il produire de châssis de chaque type par semaine pour maximiser le profit net ?
Correction Exercice n°8
1. Variables de décision
x₁: Nombre de châssis du premier type (P₁) à produire par semaine.x₂: Nombre de châssis du second type (P₂) à produire par semaine.
2. Fonction objectif (à maximiser)
Maximiser le profit total (Z) :
Max Z = 3x₁ + 5x₂
3. Contraintes
- Contrainte de capacité pour l'atelier 1 : Seul le produit P₁ utilise cet atelier.
- Contrainte de capacité pour l'atelier 2 : Seul le produit P₂ utilise cet atelier.
- Contrainte de capacité pour l'atelier 3 : Les deux produits utilisent cet atelier.
1x₁ ≤ 4
2x₂ ≤ 12
3x₁ + 2x₂ ≤ 18
4. Contraintes de non-négativité
Les quantités produites ne peuvent pas être négatives :
x₁ ≥ 0, x₂ ≥ 0
5. Solution graphique et optimale
Les contraintes peuvent être simplifiées :
x₁ ≤ 4x₂ ≤ 6(obtenu de2x₂ ≤ 12)3x₁ + 2x₂ ≤ 18x₁ ≥ 0, x₂ ≥ 0
Le domaine des solutions réalisables est un polygone défini par ces inégalités. Les points extrêmes (sommets) de ce polygone sont évalués pour trouver la solution optimale de la fonction objectif Z = 3x₁ + 5x₂ :
- Point (0,0) : Z = 3(0) + 5(0) = 0
- Point (0,6) : Z = 3(0) + 5(6) = 30
- Point (4,0) : Z = 3(4) + 5(0) = 12
- Point (4,3) : Ce point est l'intersection de
x₁ = 4et3x₁ + 2x₂ = 18. En remplaçantx₁par 4 dans la deuxième contrainte :3(4) + 2x₂ = 18⇒12 + 2x₂ = 18⇒2x₂ = 6⇒x₂ = 3. Donc, Z = 3(4) + 5(3) = 12 + 15 = 27. - Point (2,6) : Ce point est l'intersection de
x₂ = 6et3x₁ + 2x₂ = 18. En remplaçantx₂par 6 dans la deuxième contrainte :3x₁ + 2(6) = 18⇒3x₁ + 12 = 18⇒3x₁ = 6⇒x₁ = 2. Donc, Z = 3(2) + 5(6) = 6 + 30 = 36.
La valeur maximale de Z est 36$ au point (2,6).
La solution optimale est de produire x₁* = 2 châssis de type P₁ et x₂* = 6 châssis de type P₂, pour un profit maximal Z* = 36$.
Foire Aux Questions (FAQ) sur la Programmation Linéaire
Qu'est-ce qu'un programme linéaire (PL) ?
Un programme linéaire est un modèle mathématique utilisé pour optimiser (maximiser ou minimiser) une fonction linéaire (appelée fonction objectif) soumise à un ensemble de contraintes linéaires (égalités ou inégalités). Il est largement utilisé en recherche opérationnelle pour la planification de la production, la logistique, l'affectation des ressources, et la gestion de portefeuilles, etc.
Quelles sont les composantes clés d'un programme linéaire ?
Un PL se compose de trois éléments principaux :
- Variables de décision : Ce sont les inconnues du problème dont les valeurs doivent être déterminées pour atteindre l'objectif. Elles représentent généralement les quantités de produits à fabriquer, de ressources à allouer, ou d'investissements à réaliser.
- Fonction objectif : C'est l'expression mathématique linéaire à maximiser (par exemple, le profit, le revenu, la production) ou à minimiser (par exemple, le coût, le temps, les déchets).
- Contraintes : Ce sont des inégalités ou des égalités linéaires qui représentent les limitations ou les exigences du système, telles que les capacités de production, les budgets disponibles, les niveaux de demande, ou les réglementations. Les contraintes de non-négativité sont également fondamentales, stipulant que les variables de décision ne peuvent pas prendre de valeurs négatives.
Pourquoi la linéarité est-elle essentielle en programmation linéaire ?
La linéarité de la fonction objectif et des contraintes est fondamentale pour plusieurs raisons. Premièrement, elle garantit que le problème peut être résolu efficacement à l'aide d'algorithmes robustes comme la méthode du simplexe, qui sont bien établis et rapides. Deuxièmement, la linéarité assure que le domaine des solutions réalisables est un polygone convexe, ce qui simplifie l'identification de la solution optimale, car elle se situe toujours à un des sommets de ce polygone. Les relations non linéaires introduiraient des complexités qui nécessiteraient des méthodes de résolution différentes et souvent plus difficiles (programmation non linéaire).