Examen l3 fseg tunis mathematiques juin 2017 -Programmation
Télécharger PDFIntroduction à la Programmation Linéaire et Cas Pratiques
La programmation linéaire est un outil mathématique puissant et largement utilisé en recherche opérationnelle pour l'optimisation. Elle permet de trouver la meilleure solution possible (maximiser un profit, minimiser un coût, etc.) pour un problème donné, sous un ensemble de contraintes spécifiques. Ces contraintes sont toutes représentées par des équations ou des inégalités linéaires. Cet article explore les principes fondamentaux de la programmation linéaire à travers des exemples concrets de formulation de problèmes.
Exercice 1 : Identification des Contraintes Linéaires
Pour qu'une contrainte soit considérée comme linéaire et utilisable dans un programme linéaire standard, elle doit respecter des critères stricts : les variables de décision doivent être à la puissance 1, sans être multipliées entre elles, et la relation doit être une égalité ou une inégalité non stricte (c'est-à-dire ≤ ou ≥).
Analyse des Contraintes Proposées :
x1 + x2 ≤ 20: Cette contrainte est linéaire. Les variables sont à la puissance 1 et l'inégalité est non stricte.3x1 + 7x2 < 5: Cette contrainte n'est pas directement utilisable car elle contient une inégalité stricte (<). En programmation linéaire, les inégalités doivent être non strictes (≤ou≥). Elle peut être reformulée comme3x1 + 7x2 ≤ 5 - ε, oùεest un très petit nombre positif, ou, plus couramment dans la pratique pour des variables continues, comme3x1 + 7x2 ≤ 5.x1 + 0.5x2 = 7.5(interprétée à partir de1 2 15 2 x1 + x x =;) : En supposant une correction de la syntaxe pour signifierx1 + (1/2)x2 = 15/2, cette contrainte est linéaire. Les variables sont à la puissance 1 et c'est une égalité. Si le terme avait signifiéx1*x2, elle aurait été non linéaire.2x1 + x2 = 40: Cette contrainte est linéaire. Les variables sont à la puissance 1 et c'est une égalité.3x1 + 2x2 ≤ 12: Cette contrainte est linéaire. Les variables sont à la puissance 1 et l'inégalité est non stricte.x1 - 4x2 ≤ 0(interprétée à partir de5 x 1 ≤ 4 x + x 1 2) : En interprétant cette expression comme5x1 ≤ 4(x1 + x2), ce qui se simplifie en5x1 ≤ 4x1 + 4x2puisx1 - 4x2 ≤ 0, la contrainte est linéaire. Les variables sont à la puissance 1 et l'inégalité est non stricte. Si l'expression originale impliquait des variables au dénominateur ou des opérations non linéaires, elle ne serait pas valide.
Il est crucial de s'assurer que toutes les contraintes respectent la forme linéaire pour pouvoir appliquer les algorithmes de programmation linéaire.
Exercice 2 : Optimisation de la Production d'un Menuisier
Un menuisier fabrique trois types de chaises (A, B, C). Chaque chaise passe par trois opérations distinctes, chacune ayant une capacité horaire journalière limitée. L'objectif est de déterminer les quantités de chaque type de chaise à produire quotidiennement pour maximiser le profit total, sachant que toute la production est vendue.
Définition des 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.
Données du Problème :
| Opération | Temps pour Chaise A (h/unité) | Temps pour Chaise B (h/unité) | Temps pour Chaise C (h/unité) | Capacité journalière (h) |
|---|---|---|---|---|
| 1 | 1 | 2 | 4 | 4 |
| 2 | 3 | 1 | 5 | 9 |
| 3 | 1 | 3 | 1 | 2 |
Profits unitaires : Chaise A : 2, Chaise B : 1, Chaise C : 1
Formulation du Programme Linéaire :
Objectif : Maximiser le profit total (Z)
Maximiser Z = 2x_A + 1x_B + 1x_C
Sous les contraintes de capacité des opérations :
1x_A + 2x_B + 4x_C ≤ 4(Contrainte de capacité pour l'Opération 1)3x_A + 1x_B + 5x_C ≤ 9(Contrainte de capacité pour l'Opération 2)1x_A + 3x_B + 1x_C ≤ 2(Contrainte de capacité pour l'Opération 3)
Contraintes de non-négativité :
x_A, x_B, x_C ≥ 0(Les quantités produites ne peuvent pas être négatives)
Exercice 3 : Optimisation de la Production Multi-Produits et Multi-Départements
Une entreprise fabrique trois produits (P1, P2, P3), dont la production passe par quatre départements (D1, D2, D3, D4). Chaque produit nécessite un temps spécifique dans chaque département. L'objectif est de maximiser le profit total de l'entreprise en déterminant les quantités optimales de chaque produit à fabriquer.
Définition des Variables de Décision :
x_i: Quantité du produitP_ià fabriquer (oùi = 1, 2, 3).
Paramètres du Problème :
a_ij: Représente le nombre d'heures nécessaires pour fabriquer une unité du produitP_idans le départementD_j.c_i: Représente le profit unitaire généré par la vente d'une unité du produitP_i.b_j: Représente le temps total disponible (en heures) dans le départementD_j.
Formulation du Programme Linéaire :
Objectif : Maximiser le profit total (Z)
Maximiser Z = c1*x1 + c2*x2 + c3*x3
Sous les contraintes de capacité des départements :
Pour chaque département j (de 1 à 4), la somme des temps requis par tous les produits ne doit pas excéder la capacité disponible :
a11*x1 + a21*x2 + a31*x3 ≤ b1(Contrainte pour le Département D1)a12*x1 + a22*x2 + a32*x3 ≤ b2(Contrainte pour le Département D2)a13*x1 + a23*x2 + a33*x3 ≤ b3(Contrainte pour le Département D3)a14*x1 + a24*x2 + a34*x3 ≤ b4(Contrainte pour le Département D4)
Contraintes de non-négativité :
x1, x2, x3 ≥ 0(Les quantités produites ne peuvent pas être négatives)
Exercice 4 : Optimisation des Recettes de Production avec Différentes Machines
Une entreprise dispose de trois types de machines pour fabriquer quatre produits. Chaque produit nécessite un certain temps d'occupation sur chaque machine. L'objectif est de déterminer les quantités de chaque produit à fabriquer pour maximiser les recettes totales, en tenant compte des durées d'utilisation maximales pour chaque machine et des prix de vente des produits.
Définition des Variables de Décision :
x_i: Quantité du produitià fabriquer (pouri = 1, 2, 3, 4).
Paramètres du Problème :
Temps d'occupation par unité produite (en heures) :
| Produit | Machine 1 (h/unité) | Machine 2 (h/unité) | Machine 3 (h/unité) |
|---|---|---|---|
| Produit 1 | 1 | 1 | 1 |
| Produit 2 | 0.5 | 1.5 | 1 |
| Produit 3 | 1.5 | 1 | 1 |
| Produit 4 | 0.75 | 1.5 | 1.25 |
M_j: Représente la durée d'utilisation maximale disponible pour la machinej(pourj = 1, 2, 3).c_i: Représente le prix de vente unitaire du produiti.
Formulation du Programme Linéaire :
Objectif : Maximiser les recettes totales (Z)
Maximiser Z = c1*x1 + c2*x2 + c3*x3 + c4*x4
Sous les contraintes de capacité des machines :
1*x1 + 0.5*x2 + 1.5*x3 + 0.75*x4 ≤ M1(Contrainte de capacité pour la Machine 1)1*x1 + 1.5*x2 + 1*x3 + 1.5*x4 ≤ M2(Contrainte de capacité pour la Machine 2)1*x1 + 1*x2 + 1*x3 + 1.25*x4 ≤ M3(Contrainte de capacité pour la Machine 3)
Contraintes de non-négativité :
x1, x2, x3, x4 ≥ 0(Les quantités produites ne peuvent pas être négatives)
Foire Aux Questions (FAQ) sur la Programmation Linéaire
Qu'est-ce qu'un programme linéaire ?
Un programme linéaire (PL) est un modèle mathématique qui permet d'optimiser une fonction linéaire (appelée fonction objectif) soumise à un ensemble de contraintes, elles aussi linéaires. L'objectif peut être de maximiser un profit ou une recette, ou de minimiser un coût ou un temps, par exemple. C'est un outil fondamental en recherche opérationnelle.
Pourquoi les inégalités strictes (< ou >) ne sont-elles pas utilisées directement en programmation linéaire ?
Les inégalités strictes créent un "trou" dans l'ensemble des solutions réalisables, rendant parfois impossible la détermination d'une valeur optimale. Par exemple, si une contrainte est x < 5, la valeur maximale de x est indéfinie (on pourrait choisir 4.9, 4.99, 4.999, etc., sans jamais atteindre un maximum précis). Pour cette raison, la programmation linéaire utilise des inégalités non strictes (≤ ou ≥) qui définissent des régions fermées, garantissant l'existence de sommets où les solutions optimales sont souvent trouvées.
Quels sont les éléments clés pour formuler un problème de programmation linéaire ?
La formulation d'un programme linéaire repose sur trois composantes principales :
- Les variables de décision : Ce sont les inconnues du problème dont vous devez trouver les valeurs optimales (ex: quantités de produits à fabriquer, ressources à allouer).
- La fonction objectif : C'est l'expression linéaire que vous souhaitez maximiser ou minimiser (ex: le profit total, le coût total).
- Les contraintes : Ce sont des équations ou des inégalités linéaires qui représentent les limitations ou les exigences du problème (ex: capacités de production, budget disponible, demande minimale). Les contraintes de non-négativité pour les variables sont également essentielles.