Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

PROGRAMME LINEAIRE FORMES CANONIQUE ET STANDARD I) Exemples a) Problème de prod

PROGRAMME LINEAIRE FORMES CANONIQUE ET STANDARD I) Exemples a) Problème de production Une usine fabrique 2 produits A et B à l’aide de 3 matières premières. A B Qté Disponible M.P I 2 1 8 M.P II 1 2 7 M.P III 0 1 3 Profit unitaire 4 5 Le problème consiste à déterminer les quantités à produire en A et B de sorte que le profit total soit maximum. Formulation mathématique : Maximiser la quantité (réel) Z = 4X1 + 5X2 sous les contraintes : 2X1 + X2 ≤ 8 (I) X1 + 2X2 ≤ 7 (II) Xi ≥ 0 X2 ≤ 3 (III) Résolution : Graphique X2 (I) 3 B C (III) 2 D La solution est au point D D (II) 1 A E X1 1 2 3 4 X1 = 3, X2 = 2 et Z = 22 b) Problème de transport : Une entreprise possède 3 usines a, b et c sur le territoire tunisien. Elle reçoit de la marchandise en deux ports I et II. Q(a) = 400 Tonnes ; Q(b) = 300 Tonnes ; Q(c) = 200 Tonnes Q(I) = 550 Tonnes ; Q(II) = 350 Tonnes Tableau des coûts de transport unitaire : Usine a Usine b Usine c Port I 5 6 3 Port II 3 5 4 Le problème consiste à trouver un plan de transport minimisant le coût total de transport. Formulation mathématique : Minimiser la quantité (réel) Z = 5X1a + 6X1b + 3X1c + 3X2a + 5X2b + 4X2C X1a + X1b + X1c ≤ 550 X2a + X2b + X2c ≤ 350 X1a X2a ≥ 400 Xi ≥ 0 X1b + X2b ≥ 300 X1c + X2c ≥ 200 Résolution : ???? II) Notations a) Soit I un ensemble, | I | représente le cardinal de I. b) Soit A une matrice ayant m lignes et n colonnes. On note | A | = m*n et Ai j représente l’élément de l’ième ligne et la jème colonne. c) Si | A | = m*n et | B | = n*q alors | C | = |A*B| = m*q et Ci j = Σ Ai k * Bk j d) Soit X un vecteur de Rn et J  {1 ;….. ;n} ; XJ désigne le |J|-vecteur dont les éléments sont Xj ; j  J e) Soit C un vecteur ligne et X  Rn ; CX = Σ Cj * Xj et CJXJ = Σ Cj * Xj f) | A | = m*n ; J  {1 ;… ;n}, I  {1 ;… ;m} | AJ | = m*| J | AJXJ = Σ Aj * Xj | AI | = | I | *n YIAI = Σ Yi * Ai | AI J| = | I | *| J | g) La transposée de A est notée tA . h) X  Rn ; on note X  0 Xj  0 j= 1 ; 2 ; … ;n i) Um est la matrice unité ayant m lignes. III) Programme linéaire ; Forme canonique et standard Définition 1: Soit D  Rn. Tout point de D est appelé solution réalisable. Soit la fonction f : D R et le problème : Trouver x0  D qui rend maximum f(x) Toute solution du problème est appelée solution optimale. Exemples : 1- D = [ -1 ; 4] et f(x) = -2x + 1 donc : x0 = -1 et f(x0) = 3 2- D = [-1 ;4] ∩ [5 ; 7] et f(x) = -2x + 1 D = Ø 3- D = ] -∞ ; 4] ≠ Ø et f(x) = -2x + 1 D est non vide mais f est non bornée 4- D = ]-1 ; 4] ≠ Ø et f(x) = -2x + 1, D est non vide et f est bornée mais la solution optimale n’existe pas. Remarque 1 : Min[f(x)] = Max[ f(x)]. On notera par : Z -(Max) x0  D x0  D Définition 2: Un programme linéaire est un programme dans lequel :  Le domaine D est défini par un ensemble d’équations et d’inéquations linéaires de type (≤ ; ≥ ) (les inégalités strictes sont interdites) appelées contraintes.  D’une fonction f dite fonction objective ou économique qui est linéaire. Formes canoniques : Soit D = { x / AX ≤ b ; X ≥ 0 } Soit D = { x / AX ≥ b ; X ≥ 0 } (PC1) (PC2) Trouver x  D / CX = Z(Max) Trouver x  D / CX = Z(Min) On note : CM (A,b,C) On note : Cm (A,b,C) Ou : AX ≤ b AX ≥ b (PC1) CX = Z(Max) X ≥ 0 (PC2) CX = Z(min) X ≥ 0 Définition 3: Deux P.L (P) et (P’) sont dits équivalents, et on note (P) ~ (P’), si à toute solution réalisable de l’un on peut faire correspondre une solution réalisable de l’autre de telle façon que les valeurs des deux fonctions objectives soit égales pour cette paire de solutions. Formes standard : Soit D = { x / AX = b ; X ≥ 0 } Soit D = { x / AX = b ; X ≥ 0 } (PS1) (PS2) Trouver x  D / CX = Z(Max) Trouver x  D / CX = Z(Min) On note : SM (A,b,C) On note : Sm (A,b,C) Ou: AX = b AX = b (PS1) CX = Z(Max) X ≥ 0 (PS2) CX = Z(min) X ≥ 0 Remarque 2 : a) Cm(-A, -b, -C) ~ - CM(A, b, C) b) SM(A, b, C) ~ -Sm(A, b, -C) ~ Sm (-A, -b, -C) c) Sm(A, b, C) ~ -SM(A, b, -C) ~ SM (-A, -b, -C) d) SM(A, b, C) ~ CM(A’, b’, C) e) CM(A, b, C) ~ SM(A”, b, C”) A” = (A, Um); C” = (C, 0) Notion de variable d’écart. la ième contrainte de (P) s’écrit :  AiX ≤ bi : il existe yi ≥ 0 / AiX + yi = bi  AiX ≥ bi : il existe yi ≥ 0 / AiX - yi = bi Exemple : 1) Exemple 1 du paragraphe 1 : Maximiser la quantité (réel) Z = 4X1 + 5X2 sous les contraintes : 2X1 + X2 + y1 = 8 (I) X1 + 2X2 + y2 = 7 (II) Xi ≥ 0 et yi ≥ 0 X2 + y3 = 3 (III) 2) Exemple 2 du paragraphe 1 ? Remarque 3 :  Cas où Xi ≤ 0. Changement de variable : Xi : = - Xi ≥ 0  Cas où Xi  R. Xi = X′i - X″i . X′i = Max(0, Xi) ≥ 0 et X″i = - Min(0, Xi) ≥ 0 Théorème : Tout programme linéaire peut s’écrire sous forme canonique ou standard. Exercice : a) Ecrire le programme linéaire suivant sous forme canonique et standard: 2X1 – 3X2 + 7X3 ≤ 5 X1 ≥ 0 (P1) X1 + 2X2 - 4X3 ≥ 18 X2 ≤ 0 4X1 + X2 + 6X3 = 12 X3 < > 0 5X1 - 8X2 + 10X3 = Z(Max) b) D’une façon générale, soient I , J et K  {1,…,n} , L, M et N  {1,…,m}. Considérons le programme linéaire suivant : ALX ≤ bL (P) AMX ≥ bM XI ≥ 0, XJ ≤ 0 et XK < > 0 ANX = bN CX = Z(Max) Ecrire (P) sous forme canonique et standard. uploads/s3/ pl-chap-i-copie-pdf.pdf