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 LINEAIRE RESOLUTION GRAPHIQUE SIMPLEXE DUAL On appelle Programmat

PROGRAMMATION LINEAIRE RESOLUTION GRAPHIQUE SIMPLEXE DUAL On appelle Programmation Linéaire, le problème mathématique qui consiste à optimiser (maximiser ou minimiser) une fonction linéaire de plusieurs variables qui sont reliées par des relations linéaires appelées contraintes. 1) RESOLUTION GRAPHIQUE Cette méthode n'est applicable que dans le cas où il n'y a que deux variables. Son avantage est de pouvoir comprendre ce que fait la méthode générale du Simplexe, sans entrer dans la technique purement mathématique. Soit à résoudre le problème suivant: Maximiser la fonction objectif z = 1200 x1 + 1000 x2 sous les contraintes économiques 3 x1 + 4 x2  160 6 x1 + 3 x2 180 et les contraintes de signe x1  0 ; x2  0 les inconnues x1 et x2 sont appelées variables d'activité Les contraintes économiques et de signe sont représentées graphiquement par des demi-plans dont l'intersection est un ensemble convexe (c.à.d. tout segment de droite dont les extrémités appartiennent à l'ensemble est entièrement inclus dans cet ensemble). Les solutions, si elles existent appartiennent donc à cet ensemble appelé région des solutions admissibles. 1) FORME USUELLE D'UN PROGRAMME LINEAIRE Considérons la forme usuelle d'un Programme Linéaire: Max ou Min z = c1 x1 + c2 x2 + .......... + cn xn a11 x1 + a12 x2 + .......... + a1n xn  b1 a21 x1 + a22 x2 + .......... + a2n xn  b2 ............................................................................ am1 x1 + am2 x2 + .......... + amn xn  bm x1  0 ; x2  0 ; .........; xn  0 Gestion de la production M. PALE SIE Page 1 PROGRAMMATION LINEAIRE 2) FORME NON USUELLE D'UN PROGRAMME LINEAIRE La résolution du problème précédent nécessite les assertions suivantes:  Les seconds membres sont non-négatifs: bi  0 (nécessaire pour avoir une solution initiale)  Les variables d'activité sont non-négatives : xi  0  Les contraintes sont de type " " Que peut-on faire lorsque ces conditions ne sont pas respectées? a) Un second membre est négatif Il suffit de multiplier la contrainte par -1. Ceci a pour effet de changer le sens de l'inégalité [voir c)] b) Une variable d'activité n'est pas contrainte à la non-négativité Tout nombre, positif ou négatif, peut toujours être écrit comme la différence de deux nombres non-négatifs (par exemple, - 4 = 6 - 10). Il suffit donc de remplacer la variable d'activité par la différence de deux nouvelles variables d'activité non-négatives (le nombre de variables d'activité augmente de 1). c) Une contrainte n'est pas du type "  " Nous distinguons deux cas: la contrainte est du type "  " ou du type " = " - Contrainte du type "  " Il suffit de rajouter une variable d'écart non-négative ai1 x1 + ai2 x2 + .......... + ain xn  bi devient ai1 x1 + ai2 x2 + .......... + ain xn - ti  bi Il est à noter qu'il n'y a plus de solution initiale évidente: en effet pour x1  0 ; x2 0 ; .........; xn 0, ti  -bi, ce qui n'est pas une solution admissible car ti doit être non-négative. Gestion de la production M. PALE SIE Page 2 PROGRAMMATION LINEAIRE Tout se passe comme si cette variable d'écart était une variable d'activité et que nous étions en présence d'une contrainte de type " = " que nous allons traiter maintenant. - Contrainte du type " " Dans le cas usuel les variables d'écart introduites étaient représentatives des contraintes. Suivant le même principe, nous rajoutons une variable non-négative, dite variable artificielle, qui sera représentative de la contrainte dans la base. ai1 x1 + ai2 x2 + .......... + ain xn  bi devient ai1 x1 + ai2 x2 + .......... + ain xn + ei  bi Il est clair que pour que la contrainte d'égalité soit respectée il faut que ei = 0. La solution initiale étant x1  0 ; x2 0 ; .........; xn0, ei  bi, l'algorithme doit permettre de mettre hors base cette variable artificielle afin qu'elle soit nulle lorsqu’on atteindra la solution optimale. Si ceci n'est pas possible, le problème n'aura alors pas de solution. Exemple de forme non-usuelle (1) 3 x1 + 4 x2 - 2 x3  10 (2) 6 x1 + 3 x2 + 5 x3 =20 (3) -2 x1 + 5 x2 - 4 x3 -5 (4) x1  0 ; x3  0 Max z = 12 x1 + 10 x2 + 8 x3 (1) On rajoute une variable d'écart t1 3 x1 + 4 x2 - 2 x3 + t1  10 (2) On rajoute une variable artificielle e2 6 x1 + 3 x2 + 5 x3 + e2 =20 (3) On multiplie par -1 2 x1 - 5 x2 + 4 x3  5 On rajoute une variable d'écart t3 et une variable artificielle e3 2 x1 - 5 x2 + 4 x3 - t3 + e3 5 (4) x2 n'est pas contrainte à la non-négativité x2 = x'2 - x''2 Gestion de la production M. PALE SIE Page 3 PROGRAMMATION LINEAIRE Finalement le problème se ramène à la forme standard suivante 3 x1 + 4 x'2 - 4 x''2 - 2 x3 + t1  10 6 x1 + 3 x'2 - 3 x''2 + 5 x3 + e2 =20 2 x1 - 5 x2 + 5 x''2 + 4 x3 - t3 + e3 5 x1  0; x'2  0; x''2  0; x3  0; t1  0; t3  0; e2  0; e3  0 Max z = 12 x1 + 10 x'2 - 10 x''2 + 8 x3 3) METHODE DES PENALITES ( ou du grand M) Cette méthode permet de tenir compte des variables artificielles. On les pénalise en leur affectant un coefficient de valeur très élevée dans la fonction économique (- M pour un problème à maximum, + M pour un problème à minimum). Les pénalités ont pour objet de provoquer l'élimination des variables artificielles au fil des itérations. Normalement, à l'optimum (s'il existe) les variables artificielles sont hors base. Si celles-ci sont à l'optimum dans la base, avec une valeur non nulle, le programme n'a pas de solution. Soit à résoudre le programme linéaire suivant sous sa forme canonique 5 x1 + 6 x2  10 2 x1 + 7 x2  14 Min z = 3 x1 + 10 x2 x1  0 ; x2  0 * Forme standard 5 x1 + 6 x2 - 1 t1 + 0 t2 + 1 e1 + 0 e2  10 2 x1 + 7 x2 + 0 t1 - 1 t2 + 0 e1 + 1 e2 14 Min z = 3 x1 + 10 x2 + 0 t1 + 0 t2 + M e1 + M e2 x1  0 ; x2  0 ; t1  0 ; t2  0; e1  0 ; e2  0 * Tableau 0 HB B x1 x2 t1 t2 e1 e2 C Gestion de la production M. PALE SIE Page 4 PROGRAMMATION LINEAIRE e1 5 6 -1 0 1 0 10 e2 2 7 0 -1 0 1 14 ' 3 10 0 0 M M 0 La ligne ' donne les coefficients de la fonction économique, mais pas les valeurs marginales des variables HB; de plus les variables artificielles sont dans la base et devraient donc avoir des valeurs marginales nulles. De manière générale, dans tout tableau du simplexe, si on note ck les coefficients de la fonction économique et aik les coefficients du tableau, * les valeurs marginales mj sont - nulles pour les variables dans la base - égales à cj -  aik ck pour les variables hors base, la sommation étant faite sur toutes les variables de la base (les lignes du tableau) * la valeur de la fonction économique est égale à -  aik ck d'où le tableau 0 (les calculs annexes ont été rajoutés) cj 3 10 0 0 M M aik ck HB B x1 x2 t1 t2 e1 e2 C ck x1 x2 t1 t2 C e1 5 6 -1 0 1 0 10 M 5M 6M -M 0 10M e2 2 7 0 -1 0 1 14 M 2M 7M 0 -M 14M  3-7M 10- 13M M M 0 0 -24 M  aik ck 7M 13M -M -M 24M * Tableau 1 Puisqu'on recherche un minimum, la variable entrante est celle qui a le plus grand coefficient négatif, c.à.d. x2. En fait il suffit de regarder le coefficient de M car M est très grand; le coefficient indépendant de M n'intervient que dans le cas où plusieurs variables ont le même coefficient pour M. Gestion de la production M. PALE SIE Page 5 PROGRAMMATION LINEAIRE HB B x1 x2 t1 t2 e1 e2 C R e1 5 6 -1 0 1 0 10 5/3 e2 2 7 0 -1 0 1 14 2  3-7M 10-13M M M 0 0 -24M variable sortant uploads/Voyage/ programmation-lineaire-1-resolution-graphique.pdf