Formulation de programmes linéaires PDF

# Formulation de programmes linéaires ## Résumé du cours ### Définition La programmation linéaire est une méthode mathématique qui permet de résoudre des problèmes d'optimisation où l'objectif est de maximiser ou de minimiser une fonction linéaire, appelée fonction objectif, sous des contraintes...

# Formulation de programmes linéaires ## Résumé du cours ### Définition La programmation linéaire est une méthode mathématique qui permet de résoudre des problèmes d'optimisation où l'objectif est de maximiser ou de minimiser une fonction linéaire, appelée fonction objectif, sous des contraintes linéaires présentées par des équations ou inéquations linéaires. Ce type de problème est largement utilisé dans de nombreux domaines tels que l'économie, la finance, la logistique, la production, etc. Les problèmes de programmation linéaire sont généralement formulés sous forme de modèles mathématiques qui suivent les principes suivants : * La fonction objectif: on appelle fonction objectif ou d'objectif ou fonction économique, d'un problème d'optimisation (maximisation ou minimisation), le critère de choix entre les diverses solutions possibles. * Les contraintes : on appelle contraintes du problème toutes les relations limitant le choix des valeurs possibles des variables décisionnelles. Ces contraintes peuvent être des équations linéaires ou des inégalités linéaires qui limitent les valeurs possibles des variables. Ce sont des restrictions de nature techniques, économiques ou logiques. * Les variables décisionnelles doivent être non-négatives, c'est-à-dire qu'elles ne peuvent pas prendre de valeurs inférieures à zéro. ### Formulation mathématique d'un programme linéaire La formulation mathématique d'un programme linéaire peut être générale ou spécifique selon le problème à résoudre. La forme générale d'un programme linéaire peut être présentée comme suit: La forme générale d'un programme linéaire : * **Max (ou Min) Z = C₁x₁ + C2X2 + ... + C„X, ** * **a₁₁x + 12x2 + ... + a₁₁₁x, (≤, =,≥)b₁ ** * **a21x1 +a22x2 + ... + a2nx,, (≤, =, ≥)b₂ ** * **a31x1 + a32x2 + ... + a3x, (≤, =,≥)b3 ** * **amıxı + am2x2 + ... + amnx,, (≤, =,≥)b,,,** * **x; ≥ 0 ; j = 1,2,..., n ** Où : * **Z:** la fonction objectif (fonction économique) ; * **C1, C2, ..., Cn:** les coefficients des variables de la fonction Z; * **X1, X2, ..., Xn:** les variables inconnues du modèle que l'on cherche à déterminer (variables décisionnelles); * **a1, a2, ..., amn:** les coefficients des variables pour les contraintes du modèle ; * **b1, b2, ..., bm:** les quantités disponibles de chaque ressource ; * **m:** le nombre total de contrainte dans le programme * **x ≥ 0:** les contraintes de non-négativité. ### La forme matricielle d'un problème linéaire : La forme matricielle est une façon compacte de représenter un problème linéaire en utilisant des matrices et des vecteurs. Dans cette représentation, les coefficients des variables, les coefficients des contraintes, les constantes des contraintes et les coefficients de la fonction objectif sont organisés sous forme de matrices et de vecteurs. La forme matricielle d'un problème linéaire peut être présentée comme suit : * **Max (ou Min)Z = CX** * **Sous contraintes: AX (≤, =,≥)B** Où : **avec:** X = [x₁ x₂ ... xₙ]ᵀ, C = [C₁C₂...Cₙ], A = [a₁₁ a₁₂ ... a₁ₙ a₂₁ a₂₂ ... a₂ₙ ..., aₘ₁ aₘ₂ ... aₘₙ], B = [b₁ b₂ ..., bₘ] * **X:** est un vecteur colonne de taille n×1 contenant les variables décisionnelles x1, x2, ..., Xin que l'on cherche à déterminer. * **C:** est un vecteur ligne de taille / xn contenant les coefficients de la fonction objectif. * **A:** est une matrice de taille m×n contenant les coefficients des variables dans les contraintes. * **B:** est un vecteur colonne de taille m×1 contenant les constantes à droite des inégalités des contraintes. Dans cette formulation matricielle, la fonction objectif est exprimée par le produit scalaire (CX) entre les vecteurs C et X. Les contraintes sont exprimées sous forme matricielle avec la multiplication entre la matrice A et le vecteur X, et doivent être inférieures ou égales aux valeurs du vecteur B. Si le problème contient des contraintes d'égalité (par exemple, AX = B), il est possible de les reformuler sous forme d'inégalités en utilisant des inégalités larges (≤) et (2) pour les contraintes de supérieur ou égal à zéro. La forme canonique avec des contraintes ≤ s'utilise dans la représentation graphique, et la forme standard avec des contraintes égalité s'utilise dans la résolution algébrique. La résolution d'un problème linéaire en forme matricielle peut être réalisée à l'aide des algorithmes d'optimisation linéaire, tels que le simplexe ou la méthode du gradient, qui utilisent les propriétés linéaires de la fonction objectif et des contraintes pour trouver la meilleure solution. **Exemple: passage de la forme standard à la forme matricielle** On considère le système suivant : * **x₁ + 2x3 = 9** * **2x₁ + 4x2 – 2x3 = 3** * **3x₁ + 8x2 – 5x3 = 0** --- 1x₁ + 0x2 + 2x3 = 9 2x₁ + 4x2 – 2x3 = 3 3x₁ +8x2 – 5x3 = 0 | --- ### Les étapes de construction d'un programme linéaire La construction d'un PL passe généralement par trois étapes : 1. **Identifier les variables décisionnelles** qui décrivent le problème et décider de leur notation (par exemple, x1, x2, etc.). 2. **Formuler les contraintes** qui délimitent les valeurs que peuvent prendre les variables et exprimer ces contraintes sous forme d'inégalités linéaires (≤, 2) ou d'égalités linéaires (=). 3. **Formuler la fonction économique linéaire** qui mesure l'efficacité des variables décisionnelles.