Le terme «recherche opérationnelle», d'origine militaire, n'est pas très suggestif, c'est le moins qu'on puisse dire. La recherche opérationnelle constitue autant une façon de traiter des problèmes à l'aide d'outils mathématiques et informatiques. La programmation linéaire en occupe une place important, L'importance de l'optimisation est la nécessité d'un outil simple pour modéliser des problèmes de décision que ce soit économique, militaire ou autres, ont fait de la programmation linéaire un des champs de recherche les plus actifs au milieu du siècle précédent. Les premiers travaux (1947) sont celle de George B. Dantzig et ses associés du département des forces de l'air des Etats Unis d'Amérique (De nombreux mathématiciens, parmi eux le Russe L. V. Kantorovich 1938, se sont penchés sur le problème de programmation linéaire avant 1947).
Limité au départ aux problèmes industriels et militaires, de nos jours plusieurs problèmes de divers domaines sont représentés ou approximés par des modèles de PL. L'utilisation de ces techniques de modélisation s'est renforcée encore après avoir construit des algorithmes et des logiciels capables de résoudre de plus larges problèmes avec autant de variables de décision que de contraintes.
Après la publication de la méthode de simplexe, la théorie de la programmation linéaire a été développé d'une façon remarquable, la naissance et l'évolution des méthodes de la programmation en nombre entier. Le développement des méthodes de décompositions des grands systèmes linaires, la fusion de la programmation mathématique avec la théorie des graphes.
La programmation linéaire permet d'optimiser une fonction linéaire appelé fonction-objectif sur un domaine définie par des inéquations appelées contraintes. La détermination des variables de base constitue une première étape, puis le suivie du processus de résolution.
Dans le présent exposé nous allons présenter dans un premier chapitre, les fondements théoriques de la programmation linéaire. Puis, nous allons traiter l'aspect concernant la procédure de résolution d'un programme.
[...] Les coefficients économiques représentés par C = ( C Ck) mesure le degré de participation de chaque activité à la réalisation de l'objectif. La combinaison linéaire des activités et des coefficients économiques, nous donne la fonction -objectif : Les ressources représentées par le vecteur se sont des éléments qui limitent le problème rencontré : des capacités de production limité, normes à respecter, des potentialités de vente limité etc. Les coefficients techniques représentés par A mesurent le degré de consommation d'une ressource par une activité. [...]
[...] compte tenu du fait que la matrice b' a les même éléments que la matrice B à l'exception des éléments d'une colonne, il est possible à l'aide de formules de transformation de calculer la nouvelle solution x*'B à partir de la solution x*B , ce qui permet d'aboutir plus rapidement au résultat. Remarque pratique : Critère de détermination des variables d'entrée et de sortie : On remarque que les n variables de la nouvelle base sont constituées par n des anciennes variables de base et par une variable secondaire. Nous appellerons variable entrante cette variable secondaire et variable sortante la variable de base qui n'y figure plus. [...]
[...] Nous verrons que ce système permet une recherche systématique de solutions de base améliorant la fonction économique. Nous allons maintenant effectuer les mêmes transformations sur la fonction économique, en explicitant celle-ci en fonction : d'une part, de la valeur de la fonction économique correspondant au programme de base x*B d'autre part, en fonction des variables secondaires, La fonction à optimiser s'écrivait CX. Notons CB la matrice ligne correspondant aux coefficients des variable de base xB et CR la matrice ligne correspondant aux coefficients des variables secondaires XR, et remarquons que l'ordre des équations ainsi que l'ordre des variables dans le système AX = D étant indifférents, nous pouvons considérer que la matrice B est constituée des m premières colonnes de la matrice A. [...]
[...] Avec X X La formulation linéaire : Puisque nous avons transformé les problèmes d'ordre de gestion ou courant, à des problèmes sous forme mathématique, nous allons par la suit résoudre ces problèmes. II. Résolution D'un P.L. par le Simplexe Après avoir illustré par des exemples, comment un problème pratique peut être modélisé par un programme linéaire, l'étape qui va suivre sera certainement celle de la résolution de ce problème mathématique. On distingue deux méthodes de résolution : la méthode graphique et la méthode des tableaux de Simplexe. [...]
[...] Résolution d'un problème de minimisation par la méthode de simplexe : (problème de médecine) En fait en cas de minimisation, pour passer de la forme canonique à la forme standard on introduit deux séries de variables : les variables d'écarts dont les coefficients économiques sont nuls et les variables artificielle ( a ) dont les coefficients économique sont arbitrairement grand. Donc la forme standard du problème de médecine est : Min x1 + x2 + Ma1 + Ma2+ Ma3 Sc 2x1 + x2 - e1 + a1 = 12 5x1 + 8x2 - e2 + a2 = 74 x1 + 6x2 - e3 + a3 = 24 x x e e e a1 ,a2 ( 0 Donc le processus d'optimisation va consister à minimiser le résultat économique. C. [...]
Référence bibliographique
Source fiable, format APALecture en ligne
avec notre liseuse dédiée !Contenu vérifié
par notre comité de lecture
