3eme annee finance esssec recherche operationnelle serie 1 -
Télécharger PDFUniversité de Tunis ESSEC, 3ème Année Finance, Recherche Opérationnelle, Série n°1.
Exercice n°1 : Identification des contraintes linéaires
Pour qu'une contrainte soit utilisable dans un programme linéaire, elle doit être une fonction linéaire des variables de décision. Cela signifie qu'elle ne doit contenir ni produits (ex: x₁x₂), ni quotients, ni puissances (ex: x₁²) des variables. Une contrainte linéaire prend la forme ax₁ + bx₂ + ... + kzₙ [relation] C, où [relation] peut être ≤, ≥ ou =.
Analysons les expressions données :
x₁x₂ = 20: Non linéaire. La présence du produit des variablesx₁etx₂rend cette contrainte non linéaire.3x₁ + 7x₂ = 5(ou≤ 5,≥ 5) : Linéaire. Les variables sont combinées de manière additive et multipliées par des constantes.1 2 15 21 x x x: Cette expression est mal formulée et ambiguë. Si elle devait représenter une combinaison linéaire commex₁ + 2x₂ = 15/21, elle serait linéaire. Cependant, telle qu'écrite, elle n'est pas une contrainte valide dans un programme linéaire sans clarification.2x₁x₂ = 40: Non linéaire. Comme pour le premier cas, le produitx₁x₂rend la contrainte non linéaire.3x₁ + 2x₂ = 12(ou≤ 12,≥ 12) : Linéaire. C'est une combinaison linéaire simple des variables.5 x 1 4 x x 1 2: Cette expression est également mal formulée et ambiguë. Si elle devait représenter une forme linéaire comme5x₁ + 4x₂ = K, elle serait linéaire. Mais sans une écriture mathématique claire, elle ne peut être classée.
En résumé, seules les expressions de la forme ax₁ + bx₂ [relation] C sont linéaires.
Exercice n°2 : Optimisation de la marge hebdomadaire
Soit une entreprise qui fabrique deux types de pièces P1 et P2 usinées dans deux ateliers A1 et A2. Les temps d’usinage sont pour P1 de 3 heures dans l’atelier A1 et de 6 heures dans l’atelier A2, et pour P2 de 4 heures dans l’atelier A1 et de 3 heures dans l’atelier A2. Le temps de disponibilité hebdomadaire de l’atelier A1 est de 160 heures et celui de l’atelier A2 est de 180 heures. La marge bénéficiaire est de 1200 Dinars pour une pièce P1 et 1000 Dinars pour une pièce P2. L'objectif est de maximiser la marge hebdomadaire de cette entreprise.
Formulation du Programme Linéaire
Variables de décision :
x₁: Nombre de pièces P1 à produire par semaine.x₂: Nombre de pièces P2 à produire par semaine.
Fonction objectif (à maximiser) :
- Maximiser
Z = 1200x₁ + 1000x₂(Marge totale en Dinars).
Contraintes :
- Contrainte de disponibilité de l'atelier A1 :
3x₁ + 4x₂ ≤ 160(heures). - Contrainte de disponibilité de l'atelier A2 :
6x₁ + 3x₂ ≤ 180(heures). - Contraintes de non-négativité :
x₁ ≥ 0,x₂ ≥ 0.
Exercice n°3 : Maximisation du profit d'un menuisier
Un menuisier fabrique trois types de chaises : A, B et 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 profit unitaire est réalisé pour 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) | Chaise B (h) | Chaise C (h) | Capacité journalière (h) |
|---|---|---|---|---|
| 1 | 1 | 2 | 4 | 4 |
| 2 | 3 | 1 | 5 | 9 |
| 3 | 1 | 3 | 1 | 2 |
Profit unitaire : Chaise A (2), Chaise B (1), Chaise C (1).
L'objectif est de maximiser le profit du menuisier.
Formulation du Programme Linéaire
Variables de décision :
x_A: Nombre de chaises de type A à produire par jour.x_B: Nombre de chaises de type B à produire par jour.x_C: Nombre de chaises de type C à produire par jour.
Fonction objectif (à maximiser) :
- Maximiser
Z = 2x_A + 1x_B + 1x_C(Profit total).
Contraintes :
- Contrainte de capacité pour l'Opération 1 :
1x_A + 2x_B + 4x_C ≤ 4(heures). - Contrainte de capacité pour l'Opération 2 :
3x_A + 1x_B + 5x_C ≤ 9(heures). - Contrainte de capacité pour l'Opération 3 :
1x_A + 3x_B + 1x_C ≤ 2(heures). - Contraintes de non-négativité :
x_A ≥ 0,x_B ≥ 0,x_C ≥ 0.
Exercice n°4 : Maximisation du profit avec plusieurs machines
Pour fabriquer deux produits P1 et P2, des opérations doivent être effectuées sur trois machines M1, M2 et M3. Les temps unitaires d’exécution sont donnés par le tableau suivant :
| Produit | M1 (mn) | M2 (mn) | M3 (mn) |
|---|---|---|---|
| P1 | 11 | 7 | 6 |
| P2 | 9 | 12 | 16 |
Les disponibilités pour chaque machine sont : 165 heures (9900 minutes) pour la machine M1 ; 140 heures (8400 minutes) pour la machine M2 ; 160 heures (9600 minutes) pour la machine M3. Le produit P1 donne un profit unitaire de 900 dinars et le produit P2 un profit unitaire de 1000 dinars. L'objectif est de maximiser le profit.
Formulation du Programme Linéaire
Variables de décision :
x₁: Nombre d'unités du produit P1 à fabriquer.x₂: Nombre d'unités du produit P2 à fabriquer.
Fonction objectif (à maximiser) :
- Maximiser
Z = 900x₁ + 1000x₂(Profit total en Dinars).
Contraintes :
- Contrainte de disponibilité de la machine M1 :
11x₁ + 9x₂ ≤ 9900(minutes). - Contrainte de disponibilité de la machine M2 :
7x₁ + 12x₂ ≤ 8400(minutes). - Contrainte de disponibilité de la machine M3 :
6x₁ + 16x₂ ≤ 9600(minutes). - Contraintes de non-négativité :
x₁ ≥ 0,x₂ ≥ 0.
Exercice n°5 : Optimisation de la production multi-produits multi-départements
Une entreprise fabrique trois produits P1, P2, P3. La fabrication de chaque produit passe nécessairement par quatre départements D1, D2, D3 et D4. On dénote par a_ij le nombre d’heures nécessaires dans le processus de fabrication d’une unité du produit P_i dans le département D_j. Le profit unitaire de chaque produit P_i est c_i dinars et le temps disponible de chaque département D_j est b_j heures. L'objectif est de maximiser le profit total de cette entreprise.
Formulation du Programme Linéaire
Variables de décision :
x_i: Quantité du produitP_ià fabriquer, pouri = 1, 2, 3.
Fonction objectif (à maximiser) :
- Maximiser
Z = c₁x₁ + c₂x₂ + c₃x₃(Profit total).
Contraintes :
- Pour chaque département
D_j(pourj = 1, 2, 3, 4) : - Contrainte de capacité pour le département D1 :
a₁₁x₁ + a₂₁x₂ + a₃₁x₃ ≤ b₁(heures). - Contrainte de capacité pour le département D2 :
a₁₂x₁ + a₂₂x₂ + a₃₂x₃ ≤ b₂(heures). - Contrainte de capacité pour le département D3 :
a₁₃x₁ + a₂₃x₂ + a₃₃x₃ ≤ b₃(heures). - Contrainte de capacité pour le département D4 :
a₁₄x₁ + a₂₄x₂ + a₃₄x₃ ≤ b₄(heures). - Contraintes de non-négativité :
x₁ ≥ 0,x₂ ≥ 0,x₃ ≥ 0.
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 (exprimée en unités monétaires) de manière à maximiser le revenu. Il considère les six possibilités suivantes :
| Type | Intérêt | Somme investie |
|---|---|---|
| A1 | 3% | x₁ |
| A2 | 2,5% | x₂ |
| B1 | 3,5% | y₁ |
| B2 | 4% | y₂ |
| C1 | 5% | z₁ |
| C2 | 4,5% | 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 en des valeurs du type A, et pas plus de 35% dans l’une quelconque des autres valeurs. L'objectif est de maximiser le revenu de ce directeur.
Formulation du Programme Linéaire
Variables de décision :
x₁: Montant investi dans le type A1.x₂: Montant investi dans le type A2.y₁: Montant investi dans le type B1.y₂: Montant investi dans le type B2.z₁: Montant investi dans le type C1.z₂: Montant investi dans le type C2.
Fonction objectif (à maximiser) :
- Maximiser
R = 0.03x₁ + 0.025x₂ + 0.035y₁ + 0.04y₂ + 0.05z₁ + 0.045z₂(Revenu total).
Contraintes :
- Contrainte sur la somme totale investie :
x₁ + x₂ + y₁ + y₂ + z₁ + z₂ = 100. - Contrainte d'investissement minimum en type A :
x₁ + x₂ ≥ 0.40 * 100, soitx₁ + x₂ ≥ 40. - Contraintes d'investissement maximum pour les autres types (B1, B2, C1, C2) :
y₁ ≤ 0.35 * 100, soity₁ ≤ 35.y₂ ≤ 0.35 * 100, soity₂ ≤ 35.z₁ ≤ 0.35 * 100, soitz₁ ≤ 35.z₂ ≤ 0.35 * 100, soitz₂ ≤ 35.- Contraintes de non-négativité :
x₁, x₂, y₁, y₂, z₁, z₂ ≥ 0.
Exercice n°7 : Optimisation des recettes de production
Trois types de machines peuvent être utilisées pour fabriquer quatre produits selon les durées d’occupation suivantes (par unité produite) :
| Produit | Machine 1 (h) | Machine 2 (h) | Machine 3 (h) |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 0,5 | 1,5 | 1 |
| 3 | 1,5 | 1 | 1 |
| 4 | 0,75 | 1,5 | 1,25 |
L'objectif est de maximiser les recettes en fonction des durées d’utilisation maximales des trois types de machines et des prix de vente des quatre produits.
Formulation du Programme Linéaire
Variables de décision :
x_i: Quantité du Produitià fabriquer, pouri = 1, 2, 3, 4.
Paramètres :
P_i: Prix de vente unitaire du Produiti.M_k: Durée d'utilisation maximale (capacité) de la Machinek.
Fonction objectif (à maximiser) :
- Maximiser
R = P₁x₁ + P₂x₂ + P₃x₃ + P₄x₄(Recettes totales).
Contraintes :
- Contrainte de capacité de la Machine 1 :
1x₁ + 0.5x₂ + 1.5x₃ + 0.75x₄ ≤ M₁(heures). - Contrainte de capacité de la Machine 2 :
1x₁ + 1.5x₂ + 1x₃ + 1.5x₄ ≤ M₂(heures). - Contrainte de capacité de la Machine 3 :
1x₁ + 1x₂ + 1x₃ + 1.25x₄ ≤ M₃(heures). - Contraintes de non-négativité :
x₁, x₂, x₃, x₄ ≥ 0.
Exercice n°8 : Maximisation du profit 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 3 heures, tandis que le second produit nécessite le passage dans le 2ème atelier pendant 2 heures et dans le 3ème atelier 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. L'objectif est de déterminer combien il faut produire de châssis de chaque type par semaine pour maximiser le profit net.
Formulation du Programme Linéaire
Variables de décision :
x₁: Nombre de châssis du premier type à produire par semaine.x₂: Nombre de châssis du second type à produire par semaine.
Fonction objectif (à maximiser) :
- Maximiser
Z = 3x₁ + 5x₂(Profit total en $).
Contraintes :
- Contrainte de capacité de l'Atelier 1 :
1x₁ ≤ 4(heures). - Contrainte de capacité de l'Atelier 2 :
2x₂ ≤ 12(heures). - Contrainte de capacité de l'Atelier 3 :
3x₁ + 2x₂ ≤ 18(heures). - Contraintes de non-négativité :
x₁ ≥ 0,x₂ ≥ 0.
FAQ (Foire Aux Questions)
Qu'est-ce qu'un programme linéaire ?
Un programme linéaire (PL) est un modèle mathématique utilisé pour optimiser (maximiser ou minimiser) une fonction linéaire, appelée fonction objectif, sous un ensemble de contraintes représentées par des inégalités ou égalités linéaires. Les variables de décision dans un PL doivent être continues et non négatives. C'est un outil fondamental en recherche opérationnelle pour la prise de décision.
Quelles sont les conditions essentielles pour qu'un problème puisse être modélisé par un programme linéaire ?
Pour qu'un problème puisse être formulé comme un programme linéaire, il doit satisfaire à plusieurs conditions :
- Linéarité : La fonction objectif et toutes les contraintes doivent être des fonctions linéaires des variables de décision. Il ne doit pas y avoir de produits, de quotients ou de puissances de variables.
- Additivité : L'effet total des activités est la somme des effets individuels.
- Divisibilité : Les variables de décision peuvent prendre des valeurs fractionnaires (continues).
- Certitude : Tous les coefficients des variables et les valeurs des contraintes sont connus avec certitude.
- Non-négativité : Les variables de décision ne peuvent généralement pas prendre de valeurs négatives.
Pourquoi la programmation linéaire est-elle utile en gestion et en production ?
La programmation linéaire est un outil puissant pour les entreprises car elle permet de prendre des décisions optimales face à des ressources limitées. En gestion, elle aide à l'allocation optimale des ressources (main-d'œuvre, matières premières, temps machine, budget), à la planification de la production, à la gestion des stocks, à la planification financière et à la logistique. Elle permet de maximiser des objectifs comme le profit, le revenu ou l'efficacité, ou de minimiser des coûts et des risques, fournissant ainsi une base scientifique pour des stratégies opérationnelles efficaces.