La programmation linéaire

Résumé du document

Lorsque les variables du modèle sont astreintes aux valeurs entières, on aura un programme linéaire en nombres entiers (PLNE), lorsque chaque variable de décision peut prendre toutes les valeurs d'un intervalle, on aura un programme linéaire continu.
Une solution (xa, xo) est dite admissible si elle satisfait toutes les contraintes, inadmissible dans le cas contraire. Une solution admissible est dite optimale lorsque la valeur que prend alors la fonction objectif z est optimale (...)

Extraits

[...] Partant d'un sommet initial, l'algorithme effectue une opération itérative, dite pivotage, qui correspond à passer d'un sommet à un autre adjacent, plus rentable Nous limitant dans un 1er temps aux modèles de type dont le point de départ reste l'origine nous adapterons ensuite l'algorithme à un modèle linéaire quelconque. 1ère ITERATION ETAPE A : Mise en évidence d'une solution de base admissible initiale. Construction du tableau initial Nous avons obtenu le modèle : S.C. = 200 (1') = 60 (2') = 34 (3') = 14 (4') (5') Les points extrêmes de (PLS) correspondent aux solutions de base admissibles de obtenues en annulant 2 des 6 variables de (PLS=). [...]

[...] Dans le modèle il s'agit d'un problème de maximisation. Les variables sont appelées variables de décision du problème : Le modèle (PLS) comporte n variables de décision, qui sont toutes non- négatives. Le modèle comporte m+n contraintes : Les m premières sont qualifiées de contraintes technologiques. Dans le modèle elles prennent la forme d'inéquations linéaires du type . Les n dernières sont des contraintes de non-négativités ou contraintes de bornes. Le modèle est dit continu lorsque . Une solution est une affectation de valeurs aux variables du problème. [...]

[...] La forme générale du programme linéaire (PLC) est présentée ci-après. Elle diffère de la forme simplifiée en deux principaux points : - le fait qu'il s'agit d'optimiser la fonction objectif, ce n'est pas forcément un problème de maximisation, - les contraintes technologiques peuvent être du type , = ou Max(Min) z = S.C. sous les contraintes ; = = 0 ; j = .,n = = 0 ; j = .,n III - MODELISATION : exemples de modélisation et applications L'ENTREPRISE CRM A partir des matières premières M & l'entreprise CRM fabrique deux produits finis, P & vendus 42 et 48 l'unité respectivement, à un grossiste qui absorbe toute sa production. [...]

[...] Tout point d'un segment de droite peut s'écrire comme combinaison linéaire des deux points extrémités du segment. L‘ensemble des solutions admissibles d'un modèle linéaire continu constitue toujours un ensemble convexe de telle façon que si cet ensemble contient 2 points distincts, il en contient une infinité. La région admissible d'un modèle linéaire est dite non bornée si au moins une des variables peut prendre des valeurs de plus en plus grandes sans violer aucune des contraintes technologiques. Dans le cas contraire, on dit que la région admissible est bornée ) TYPOLOGIE DES SOLUTIONS ADMISSIBLES L'ensemble des solutions de notre modèle linéaire continu comporte trois types de points : intérieurs, frontières et extrêmes. [...]

[...] 16,667 = 14 - 14 Par conséquent : Choix de la variable sortante : Le pivot , ici égal à 10, se situe à l'intersection de : - la colonne de la variable entrante : - la ligne de la variable sortante : Construction du 4ème tableau - les variables de base : - les variables hors base : , Pour écrire le 4ème tableau, on doit exprimer notre modèle en fonction des variables hors base, ce qui revient à remplacer la variable entrante par son expression en fonction des variables hors base, ici et , utilisant pour cela la ligne où se trouve le pivot, que je dois transformer de manière à ce que le pivot soit égal à ce qui revient ici à diviser la ligne par valeur du pivot. Soit : 0,1. -0,5. + = 4 = 4 + 0,5. Cette expression, utilisée dans le tableau ‘2' préalablement obtenu va aboutir à la construction de ‘3' correspondant au sommet C et au modèle suivant : S.C - 0,5. + = 4 -0,25. = 15 +0,25. = 19 - 0,10. [...]