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 1 resolution graphique

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 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 x x sous les contraintes économiques x x n x x nn et les contraintes de signe x n x nn les inconnues x et x 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 FORME USUELLE D'UN PROGRAMME LINEAIRE Considérons la forme usuelle d'un Programme Linéaire Max ou Min z c x c x cn xn a x a x a n xn n b a x a x a n xn n b am x am x amn xn n bm x n x n xn n Gestion de la production M PALE SIE Page PROGRAMMATION LINEAIRE FORME NON USUELLE D'UN PROGRAMME LINEAIRE La résolution du problème précédent nécessite les assertions suivantes n Les seconds membres sont non-négatifs bi n nécessaire pour avoir une solution initiale n Les variables d'activité sont non-négatives xi n n Les contraintes sont de type n 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 - 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 - - 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 c Une contrainte n'est pas du type nnn Nous distinguons deux cas la contrainte est du type n ou du type - Contrainte du type n Il suffit de rajouter une variable d'écart non-négative ai x ai x ain xn n bi devient ai x ai x ain xn - ti n bi Il est à noter qu'il n'y a plus de solution initiale évidente en effet pour x n x n xn n ti n -bi ce qui n'est pas une solution admissible car ti doit être non-négative Gestion de la production M PALE SIE Page 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 n Dans le cas usuel les