Remerciez-le!

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

Programmation linéaire Après la 2ème guerre mondiale, durant cette guerre, la p

Programmation linéaire Après la 2ème guerre mondiale, durant cette guerre, la programmation linéaire était une application militaire qui est devenue une application de la gestion. La recherche d’informations en minimisant les coûts. Programmation linéaire Programmation dynamique Méthode des graphes Recherche opérationnelle = PERT Méthode des potentiels 1) définition et vocabulaire : la programmation linéaire peut se définir comme un outil mathématique qui permet d’analyser des problèmes dans lesquels on trouve une fonction linéaire d’un certains nombre de variables appelées fonctions économiques que l’on désire optimiser ( maximiser ou minimiser ). Ces variables sont soumises à des restrictions imposées par la situation physique, pratique ou économique du problème. Les restrictions qui sont imposées prennent la forme d’équation ou d’inéquation linéaire dans la formulation d’un modèle de programmation linéaire. Le mot programmation veut dire dans notre contexte, un processus ordonné avec lequel nous résolvons les problèmes, il n’a aucun lien avec la programmation d’un ordinateur, ce dernier est utilisé pour résoudre des problèmes de programmation linéaires en effectuant les opérations arithmétiques nécessaires à l’obtention de la solution. 2) historique : la 1ére publication en PL a été en 1939 par les mathématiciens russes L.V Kantorovich, cependant Dantzig a le mérite de découvrir l’algorithme le plus utilisé pour résoudre un problème de PL ( le simplexe ). Les premières applications étaient de nature militaires mais maintenant elles sont nombreuses et réparties dans multiples domaines ( gestion, finance, économie… ). La PL est peut être aujourd’hui l’outil mathématique le plus efficace qui soit permis d’utiliser dans la résolution de problèmes industriels et économiques. 3) formes d’un PL : un PL peut se présenter sous l’une des 3 formes suivantes : 1- forme générale ou mixte 2- forme canonique 3- forme standard notons x1 ; x2 ………xn les x variables du problème, ces variables sont soumises à un système de n contrainte d’indice 1, 2, 3 …….n. ces contraintes représentent soit des inégalités, d’infériorité (<) de supériorité (>) , soit des égalités. Tout problème de PL se représente sous la forme générale suivante : Z = Σ Ck Xk Sous les contraintes de non négativité : Xk ≥ 0 V K appartenant à [ 1 ; n ] Et les autres contraintes de non négativité :  ∑ aij . xj ≤ di  ∑ aij . xj ≥ di  ∑ aij . xj = di exemple : Z = 5x1 + 2x2 Z = ∑ Ck Xk Z = Cx = [ 5 ; 2 ] [X1] X2 Ax ≤ d X ≥ 0 Un tel programme sous une forme mixte ≤ ; ≥ ; = , si toutes les contraintes représentent des inégalités au sens large. Le PL est dit sous forme canonique si toutes les contraintes représentent des égalités, le programme est dit sous sa forme standard. Remarque : Quelque soit la forme sous laquelle se présente le problème, on peut toujours le ramener à la forme qu’on souhaite. Exemple : Z = 2x1 + 3x2 2x1 +2x2 ≥ 2 2x1 – x2 ≤ 3 3x1 + 2x2 = 5 pour les égaliser, le programme peut s’écrire : Z = 2x1 + 3x2 + 0x3 + 0x4 → 2x1 + 2x2 – x3 + 0x4 = 2 ┌ ┐ → 2x1 – x2 – 0x3 + x4 = 3 2 2 -1 0 → 3x1 + 2x2 + 0x3 + 0x4 = 5 2 -1 0 1 3 2 0 0 └ ┘ la forme canonique est plus pratique quand il s’agit d’interprétation graphique. La forme standard est plus pratique quand il s’agit d’interprétation matricielle. 2x1 + 2x2 ≥ 2 → x2 ≥ 1 – x1 ≥ ≤ Exemple : Un industriel dispose de 3 machines N1 , N2 et N3 Pour fabriquer 3 biens A , B et C. Le tableau de fabrication des biens A, B et C est le suivant : ≤ 40 ≤ 45 ≤ 38 Interprétation : pour fabriquer un bien A, il faut une heure de machine N1, 3h machine N2 et 1h machine N3, même pour B et C. Chacune des machines M1 M2 et M3 ne peuvent fonctionner qu’à nombre limité d’heure par semaine : → 40h pour M1 → 45h pour M2 → 38h pour M3 l’industriel connaît de plus le prix unitaire de chaque un des bien A B et C : 10 pour A ; 14 pour B ; et 12 pour C. déterminer la production des biens A, B et C qui assure à l’industriel le CA optimum. Si on maximise le CA, Z = 10A + 14B +12C Il faut que A B et C ≥ 0 X1, x2, x3 les quantités respectives des biens A B et C. 4) résolution de PL par la méthode des graphes : lorsque le nombre de variables est inférieur à 3, les problèmes de PL peuvent être représentés et résolus graphiquement. ( pour plus de 2 variables, la méthode graphique reste inopérationnelle ) exemple : maximiser Z = 5x1 + 3x2 sous 3x1 + 5x2 ≤ 15 5x1 + 2x2 ≤ 10 x1 et x2 ≥ 0 Y x2 5 C B O A2 5 x 1 X L’ensemble des points x1 et x2 satisfaisant au système de contraintes se trouve à l’intérieur du polyèdre OABC ; on l(appelle l’ensemble programmes admissibles. L’objectif est dons de déterminer parmi la famille de droite d’équation Z = 5x1 + 3x2 ( obtenus en faisant varier la valeur du paramètre Z celle qui étant la plus éloignée de l’origine ( max ) ait au moins un point de contact avec le domaine des programmes admissibles ( B dans notre cours ) A B C M1 1A 3B 2C M2 3A 2B 1C M3 1A 1B 4C Les points qui maximisent Z = {O, A, B, C} B est obtenu par l’intersection des droites : {5x1 + 2x2 = 10 {3x1 + 5x1 = 15 x1 = 20/19 ; x2 = 45/19 et on remplace Z pour trouver Z = 235/19 U2 exemple : minimiser Z = 15 U1 + 10 U2 U1 ≥ 0 ; U2 ≥ 0 A {3U1 + 5U2 ≥ 5 {5U1 + 3U2 3 ≥ B C O U1 On cherche parmi tous les points ( U1, U2 ) les domaines hachurés, celui qui rend minimum : Z = 15U1 + 10U2 ( B le moins éloigné de l’origine ) Le programme optimale est donc déterminé par le système : {3U1 + 5U2 = 5 {5U1 + 3U2 = 3 → U1 = 5/19 ; U2 = 16/19 ; Z = 235/19 remarque : si la direction de la fonction économique est parallèle à l’aide des segments définissants la frontière du programme admissible alors il y’a une infinité de solutions optimales. D C la maximisation est toute en segment B Si le système des contraintes est incompatible, il n’y a O A aucune solution. Max : x1 + 2x2 X1 ≥ 0 et x2 ≥ 0 { x1 + x2 ≤ 1 { X2 – x1 ≤ -2 Dans le cas où l’ensemble des programmes n’est pas borné, il peut ne pas y avoir des solutions optimales. Exemple : Maximiser Z = x1 + x2 X2 – X1 ≤ 1 → X2 ≤ 1 + X1 X1 ≥ 0 ; X2 ≥ 0 → - ½ X1 + x2 ≤ 2 → x2 ≤ 2 + ½ x1 X2 B A X1 Pour la fonction économique x2 – ¾ x1 il y a un programme optimale unique, bien que le domaine ne soit pas borné. II) résolution d’une PL : la méthode de simplexe L’algorithme de simplexe consiste à : - déterminer une solution de base. - Faire subir un test d’optimalité à cette solution optimale.  s’il s’agit de la solution optimale, le problème est terminé.  S’il ne s’agit pas de solution optimale, il faut changer la solution de base et puis reprendre la procédure précitée, jusqu’à l’obtention de la solution optimale. Notons enfin que pour réaliser des opérations successives complexes, il convient de mettre le programme sous une forme standard. La méthode de simplexe peut être formuler de différentes manières : - formulation algébrique - formulation matricielle - la résolution pratique : méthode des tableaux A) formulation matricielle : soit le PL : Z = C1 X1 + C2 X2 + ……..+ Cn Xn x1, x2, ……, xn ≥ 0 A11 X1 + A12 X2 + ……….. ……….A1n Xn = d1 A21 X1 + A22 X2 + ……….. ……….A2n Xn = d2 An1 X1 + An2 X2 + ……….. .............Ann Xn = dn X1 d1 X2 d2 . . X = . et D = . . . Xn dn A1 A2 An le programme s’étend a11 a12 ……. a1n sous forme : Z = CX a21 a22 .……. a2n X > 0 A = …….. ……. .……. …….. AX = D an1 an2 …….. ann Soit en notant A1, A2, …… An les matrices colonnes de la matrice A , l’expression Ax = D devient A1X1 uploads/Industriel/ programmation-lineaire.pdf