U.M.B.B - Département de Mathématiques - 3 emeAnnée RO - 2020/2021- Respons Mo

U.M.B.B - Département de Mathématiques - 3 emeAnnée RO - 2020/2021- Respons Module : Optimisation Lin eaire Chapitre1 : Notion G en erales de Pr ogrammation Math ematiques et de Dualit e I. Exemple Introductif : Une usine fabrique trois produits P1; P2 et P3; pour réaliser sa production, elle utilise deux matières premières m1 et m2 et deux machines M1 et M2:  La production (fabrication) d’une unité de P1 nécessite 2 mn de travail sur la machine M1 et 6 mn sur M2; 2 unités m1 et 1 unité de m2:  La production (fabrication) d’une unité de P2 nécessite 4 mn de travail sur la machine M1 et 12 mn sur M2; 5 unités m1 et 3 unités de m2:  La production (fabrication) d’une unité de P3 nécessite 3 mn de travail sur la machine M1 et 3 mn sur M2; 2 unités m1 et 4 unités de m2:  La machine M1 est disponible 5 heures par jours.  La machine M2 est disponible 6 heures par jours.  Les quantités de matières premières m1 et m2 disponibles sont 40 et 20 respectivement.  Les pro…ts réalisés sur l’unité de production P1 est de 5 UM (unité monitaire).  Les pro…ts réalisés sur l’unité de production P2 est de 8 UM:  Les pro…ts réalisés sur l’unité de production P3 est de 6 UM: Le patron de l’usine cherche à déterminer le meilleur plan de production c’est-à-dire à déterminer le nombre d’unités de chaque produit à fabriquer en réalisant un pro…t maximum, compte tenu du temps de travail disponible et des quantités de matières premières m1 et m2 disponibles. :On résume les données dans le tableau suivant : P1 P2 P3 quatit es(temps) disponible m1 2 5 2 40 m2 1 3 4 20 M1 2 4 3 300 M2 6 2 3 360 profil 5 8 6 Soit xj : la quantité du produit Pj à fabriquer par jours, j = 1; 2; 3: xj  0 Les relations pour que la production soit possible : 8 > > < > > : 2x1 + 5x2 + 2x3  40 x1 + 3x2 + 4x3  20 2x1 + 4x2 + 3x3  300 6x1 + 12x2 + 3x3  360 (1) Le pro…t réalisé pour la fabrication de xj (j = 1; 2; 3) : 5x1 + 8x2 + 6x3 (2) Le modèle mathématique de ce problème est le suivant : (P) 8 > > > > < > > > > : 2x1 + 5x2 + 2x3  40 x1 + 3x2 + 4x3  20 2x1 + 4x2 + 3x3  300 6x1 + 12x2 + 3x3  360 max imiserZ (x1; x2; x3) = 5x1 + 8x2 + 6x3 Le programme linéaire (P) est dit linéaire à cause de la linéarité du système (1) et (2) : 1 II. Notions de programmation mathématiques : II.1 Dé…nitions : Soit D un domaine de Rn et f : D ! R: Dé…nition 1 : Un programme mathématique (P) est le problème qui consiste à chercher un élément x 2 D tel que f (x)  f (x) (ou f (x)  f (x) ) 8x 2 D Dé…nition 2 : Soit (P) un programme mathématique.
Un point x 2 D est appelé solution réalisable de (P) :
Le domaine D est appelé domaine des solutions réalisables de (P) :
la solution x 2 D est appelé solution optimale de (P) :
La fonction f est appelé fonction objectif de (P) : Remarque 1 :  Un programme mathématiques (P) est représenté par la notation : Max f (x) ; x 2 D (problème de maximisation) ou Min f (x) ; x 2 D (problème de minimisation)  Résoudre le programme (P) : minimiser f (x) ; x 2 D revient à résoudre le programme (P 0) : maximiser ( f (x) ; x 2 D) et réciproquement : Min x2D f (x) = Max(x2D f (x)) Par conséquant, on considère en générale dans toute la suite que les problèmes à maximisation. Dé…nition 3 : Un programme linéaire est un programme mathématique dans lequel :
la fonction f est linéaire ;
le domaine (D) dé…ni par un ensemble d’équations ou d’inéquations linéaires de type  ou  : Les inéquations dé…nissant (D) sont appelées des contraintes. Exemple Le programme mathématique donné dans l’exemple introductif est un programme linéaire. Remarque 2 : Etant donné un programme mathématique (P) dé…ni par un domaine D et une application f . On peut avoir l’un des 4 cas suivants : 1: D = ?; le PL (P) n’a pas solution réalisable. Exemple : Max fx>2 et x<3g(x) 2: D 6= ?; f non bornée sur D;le PL (P) n’a pas de solution optimale Exemple : Max fx2 g(x) 3: D 6= ?; f bornée sur D;mais le PL (P) n’a pas de solution optimale Exemple : Max fx<2 g(x) 4: D 6= ?;le PL (P) a une solution optimale 2 Exemple : Max fx2 g(x) En programmation linéaire le cas 3 ne peut se produire, par conséquent on adopte à la convention suivante : Max f (x) = 8 < : f (x) si x est solution opt de (P) 1 si D = ? +1 si f non bornée II.2 Notations : 1. Si I est un ensemble …ni, jIj désigne le cardinal de I: 2. Soit A m  n matrice
Aj i élément de i eme ligne et j eme colonne
tA est la matrice transposée de A: 3. Soient A et B deux m  n matrices
A = B , Aj i = Bj i :
A  B , Aj i  Bj i : 4. Un (ou In) est la matrice identité d’ordre n: 5. A1 est l’inverse de la matrice A si A est inversible. 6. x est le n vecteur colonne et C est le n vecteur ligne : Cx = n P k=1 Ckxk est le produit scalaire. 7. Soit A une matrice m  n, I  f1; 2; :::; mg et J  f1; 2; :::; ng b : est un m vecteur colonne. x : est un n vecteur colonne. y : est un m vecteur ligne.  i 2 I; j 2 J Aj est la j eme colonne de A: AJ la m  jJj matrice ayant pour colonnes Aj; j 2 J Ai est i eme ligne de A: AI la jIj  n matrice ayant pour lignes Ai; i 2 I AJ I la jIj  jJj matrice ayant pour élément Aj i; i 2 I; j 2 J: ) AJxJ = P j2J Ajxj ; ) yIbI = P j2J yibi: Exemple 1 : A = 3 2 1 0 5 2 0 1  ; b = 120 100  ; x =t 0 50 0 0
; C = 10 5 0 0
) I = f1; 2g et J = f1; 2; 4g AJ = 3 2 0 5 2 1  ; AI = A; AJ I = AJ; CJ = 10 5 0
; bI = b ; xJ =t 0 50 0
AJxJ = 3 2 0 5 2 1  0 @ 0 50 0 1 A = 100 100  ; CJxJ = P j2J Cixj = 250: Exemple 2 : Ecrire le PL dé…ni précedement (exemple introductif) en utilisant les notations matricielles. III. Formulations générales de la Programmation Linéaire Dé…nition 1 : Soient A une m  n matrice, b un m vecteur colonne et C un n vecteur ligne :  Le programme linéaire (Pc) : Max fx=Axb; x0gCx est dit écrit sous forme canonique (S:F:C)  Le programme linéaire (Pc) est noté : (Pc)  Ax  b Cx = Z (Max) ; x  0: Remarque 1 : Deux propréités caractérisent la forme canonique : 1. Toutes les variables x1; x2; ::::; xn sont astreintes à être positives ou nulles. 2. Toutes les contraintes sont des inéquations du type : 3 a)  s’il s’agit d’un problème de maximisation a)  s’il s’agit d’un problème de minimisation: Dé…nition 2 : Le PL (Ps)  Ax = b Cx = Z (Max) ; x  0 est dit écrit sous forme standard. Remarque 2 : Soit A une matrice m  n, b est un m vecteur colonne, C est un n vecteur ligne. Soient I1  f1; 2; :::; mg et I2  f1; 2; :::; mg ; J1  f1; 2; :::; ng et J2  f1; 2; :::; ng telsque :
I1 [ I2 = f1; 2; :::; mg et I1 \ I2 = ?
J1 [ J2 = f1; 2; :::; ng et J1 \ J2 = ?  Le PL (Pg) 8 > > > > < > uploads/Industriel/ chap-1 1 .pdf

Documents similaires

NATIONS UNIES gONSEIL fcONOMIOUE It social Distr. LIMITEE / 19 aout 1964 FRANCA 0 0

Introduction Informatique?: construit sur la contraction de l’expression « in 0 0

Outils d’amélioration continue III 3eme année ingénierie de la maintenance des 0 0

Sièges et dispositifs de retenue ....................... 1-1 Sièges avant ..... 0 0

1 2012-2013 Université de Jijel Département :TCST (2eme Année) Module: informat 0 0

Révisions ISO Révisions ISO Livre blanc ISO Revisions Quelle est la différence 0 0

~ 1 ~ سلك الجذوع المشتركة المهنية - الجذع المشترك الصناعي- - الجذع المشترك الخد 0 0

ENSEIGNANT : M.DJIB FAYE UCAD/CESAG/FOCS Travaux de groupe : Société MINA : (Sy 0 0

SED complexes - 1 – Conception des systèmes à événements discrets complexes Mir 0 0

USTHB, Faculté d’Electronique et Informatique Faculté d’Electronique et Informa 0 0

• Détails
• Publié le Oct 04, 2022
• Catégorie Industry / Industr...
• Langue French
• Taille du fichier 0.1224MB