Cours de recherche operationnelle

Résumé du document

Cours de recherche opérationnelle permettant de mieux comprendre la recherche opérationnelle : son fondement, sa définition, les matrices, la programmation linéaire utilisée dans diverses domaines (économique, militaire...).

Extraits

[...] Pour passer au tableau suivant, il faut trouver la variable entrante. Trouver la variable entrante On veut minimiser w donc la variable entrante doit permettre de diminuer w. En considérant la colonne des Λ j , on remarque que 120 -7M est la valeur la plus négative. u2 est donc la valeur entrante NB : La variable entrante entre avec Cj correspondant dans la colonne des M Variable sortante Deuxième édition, Septembre 2007 Support de Cours de recherche opérationnelle de première et deuxième année de BTS Pour trouver la variable sortante, on procède de la même façon que dans le cas de la maximisation. [...]

[...] Sur le marché, E1 et E2 coutent 2F et 3F respectivement. Indiquer le tableau de programmation linéaire Indiquer la formulation mathématique Solution Le problème qui est posé ici est un problème de formulation d'un produit chimique. Ici, ce produit est un engrais chimique. Dans certains cas, on a des problèmes de formulation de produit alimentaire pour bétail, volaille etc . Deuxième édition, Septembre 2007 Support de Cours de recherche opérationnelle de première et deuxième année de BTS Indiquons le tableau de programmation linéaire E2 E1 F.O 60 A B 0 C 110 D 50 Indiquons la formalisation mathématique Min 2 E1 + 3 E2 s/c 0,2 E1 E2 E1 + 0,1 E2 E1 + 0,2 E2 170 E1, E2 0 Section II : résolution d'un problème de programmation linéaire Après la formalisation mathématique d'un problème de programmation linéaire, il faut le résoudre. [...]

[...] Celle aura une valeur telle que l'une des valeurs dans la base passera de la valeur supérieure à 0. Cette variable sera appelée variable sortante. En claire donc, l'interaction consiste à faire quitter une variable de la base et à en faire rentrer une autre. III-1-2 : Choix de la variable entrante Il faut transformer la fonction économique en ceci. En exprimant Z en fonction de X1 et X2, on remarque Z = 4X1 + 5X2. Les coefficients 4 et 5 sont les accroissements marginaux de Z lorsque X1 et X2 passe de 0 à 1 respectivement. [...]

[...] Chaque passage à un tableau constitue une itération. Le passage se fait selon des règles bien précises et en deux phases. Première phase : Trouver le pivot Il est le coefficient qui se trouve à l'intersection de la ligne de la variable sortante et de la colonne de la variable entrante c'est-à-dire que le pivot est 2. Deuxième phase : Le pivotage Le pivotage permet de passer d'un nouveau tableau à un ancien tableau. Les règles pratiques sont les suivantes : Diviser tous les coefficients y compris la valeur de droite de la ligne du pivot par le pivot. [...]

[...] Mais ces contraintes A1 et A2 sont affectées du coefficient 1. Ainsi, le modèle devient : Min w = 40u1 + 120u 2 + 0u 3 + 0u 4 + MA1 + MA2 s/c u1 + 4u 2 u 3 + 0u 4 + A1 + 0 A2 = 4 2u1 + 3u 2 + 0u 3 u 4 + 0 A1 + A2= 5 u u u u A A2 0 Deuxième édition, Septembre 2007 Support de Cours de recherche opérationnelle de première et deuxième année de BTS Ici, une solution de départ est : u1 = u2 = u3 = u4 = 0 w = 9M Le système peut être réécrit comme suit : + 4u2 u3 + 0u4 + A1 + 0 A2 = 4 + 3u2 + 0u3 u4 + 0 A1 + A2 = 5 + 120u + 0u + 0u + MA + MA w = 1 u1 u2 u3 u4 A1 A2 VE M A - M A - Cj M M Λj M M -3M -7M M M Formule pour calculer Λ j Λ j = Cj - a1 j a 2 j [ ] Les Λ j sont les TMS et on postule que M>0 est très grand. [...]