Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Réalisé par :  Mohamed ZAOUI Encadré par :  Prof. Ahmed ASIMI Étude théorique

Réalisé par :  Mohamed ZAOUI Encadré par :  Prof. Ahmed ASIMI Étude théorique de certains logiciels de la programmation linéaire Université Ibn Zohr, Faculté des Sciences, Agadir Master Informatique des Systèmes Répartis Mini-Projet ETUDE THEORIQUE DE CERTAINS LOGICIELS DE LA PROGRAMMATION LINEAIRE 1 MISR-fsa-Agadir Mohamed ZAOUI Tables des matières : I. Introduction :……………………………………………………………………………………..2 II. Les logiciels actuels :…………………………………….…………………………………..3 1. Principes de fonctionnement : ……………………………………………....3 2. Les principaux solveurs :……………………………………………………...4 3. Les principaux modeleurs :…………………………………………………..4 4. Les environnements de développement intégrés (EDI) :………………5 5. Sites web des éditeurs de logiciels:………………………………………..5 III. Étude théorique de certains logiciels de la programmation linéaire : Excel……………………………………………………...…………………………6 Lindo…………………………………………..…………………………………..12 Cplex………………………...…………………………………………………....25 Opl Studio……………………………….……………………………………...27 Matlab…………………………………………………………………………….29 Ampl……………………………………………………………………………….33 MPL for windows………………………..…………………………………...36 GAMS………………………………………….…………………………………..37 Maple……………………………………………………………………………..42 IV. Conclusion :……………………………………...…………………………….……………48 Mini-Projet ETUDE THEORIQUE DE CERTAINS LOGICIELS DE LA PROGRAMMATION LINEAIRE 2 MISR-fsa-Agadir Mohamed ZAOUI I. Introduction : L’importance de l’optimisation et la nécessité d’un outil simple pour modéliser des problèmes de décision que soit économique, militaire ou autres on 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. Les problèmes de programmations linéaires sont généralement liés à des problèmes d’allocations de ressources limitées, de la meilleure façon possible, afin de maximiser un profit ou de minimiser un coût. Le terme meilleur fait référence à la possibilité d’avoir un ensemble de décisions possibles qui réalisent la même satisfaction ou le même profit. Ces décisions sont en général le résultat d’un problème mathématique. Généralement il y a trois étapes à suivre pour pouvoir construire le modèle d'un programme linéaire : 1. Identifier les variables du problème à valeur non connues (variable de décision) et les représenter sous forme symbolique (exp. x1, y1 ). 2. Identifier les restrictions (les contraintes) du problème et les exprimer par un système d’équations linéaires. 3. Identifier l’objectif ou le critère de sélection et le représenter sous une forme linéaire en fonction des variables de décision. Spécifier si le critère de sélection est à maximiser ou à minimiser. Mini-Projet ETUDE THEORIQUE DE CERTAINS LOGICIELS DE LA PROGRAMMATION LINEAIRE 3 MISR-fsa-Agadir Mohamed ZAOUI II. Étude théorique de certains logiciels de la programmation linéaire : Grâce aux progrès de l’informatique, l’offre de logiciels commerciaux permettant de résoudre des PL de plus en plus gros a considérablement augmenté. On peut maintenant résoudre en routine des PL à 100 000 variables et contraintes et des PLNE à 1 000 variables et contraintes avec les codes les plus performants. Les prix de ces logiciels autrefois réservés à une petite communauté ont fortement diminué et deviennent très abordables. 1. Principes de fonctionnement : La résolution d’un problème de programmation linéaire s’effectue en deux grandes phases : La modélisation, puis la résolution (on pourrait aussi ajouter une troisième phase d’analyse des résultats). Historiquement, les premiers logiciels ne servaient qu’à résoudre des programmes linéaires déjà modélisés et donnés sous forme numérique. Il s’agissait donc de codes algorithmiques de résolution, appelés aussi solveurs. Par la suite sont venus se greffer les langages de modélisation ou modeleurs. Les solveurs sont distribués sous forme de logiciels autonomes, ou encore de bibliothèques de sous-programmes à inclure dans des programmes d’application. Le programme linéaire doit être au préalable préparé en mémoire, sous forme de matrices ou de listes de valeurs numériques. La plupart des solveurs offrent cependant une fonction permettant de charger un PL saisi au préalable dans un fichier texte. Selon les produits, les PL sont stockés dans des fichiers sous forme matricielle ou sous forme d’équations proches de l’écriture mathématique, par exemple “3*X1+2*X2 = 3”. Le format matriciel MPS a été popularisé par le premier solveur célèbre, MPSX d’IBM. Il permet de découper la matrice d’un grand PL en lignes de longueur fixe, de définir des portions de lignes et de colonnes, etc. Ce format est encore utilisé comme moyen d’échanger des données entre les logiciels actuels. Les modeleurs aident l’utilisateur à formuler son problème correctement et à analyser les solutions obtenues après résolution par un solveur. Un modeleur s’appuie sur un langage de description du problème et lie cette modélisation symbolique (le modèle) à un jeu de données. Typiquement, un modeleur permet de définir des paramètres (par exemple un nombre de produits à fabriquer), des variables indicées, des tableaux de données, des sommations de variables indicées, etc. L’utilisateur peut ainsi formuler son problème de façon compacte, dans une syntaxe proche de l’écriture mathématique. Avec un solveur, l’ajout d’un produit supplémentaire dans un problème de planification de production oblige à insérer des nouvelles colonnes ou lignes de valeurs numériques dans la matrice du programme linéaire. Un modeleur permet de définir un modèle générique, paramétré par le nombre n de produits. Ce modèle peut être rendu complètement indépendant des valeurs numériques, stockées dans des fichiers séparés. Pour ajouter un nouveau produit, il suffira de préciser la nouvelle valeur de n et de modifier les fichiers de données. Le modèle ne sera pas changé. Cette souplesse accélère les développements, diminue les risques d’erreurs et donne des modèles faciles à documenter et à relire. Comment marche un modeleur ? Il commence par compiler le modèle pour détecter d’éventuelles erreurs de syntaxe. Si la syntaxe est correcte, il ouvre les fichiers de données et se charge de la tâche fastidieuse de générer le programme linéaire sous forme matricielle. La matrice des valeurs numériques, qui peut être énorme par rapport au modèle sous forme symbolique, sera traitée par un solveur. Aujourd’hui, certains modeleurs peuvent être achetés seuls puis interfacés avec divers solveurs d’autres éditeurs de logiciels, par exemple grâce au format d’échange matriciel MPS. D’autres modeleurs sont étroitement imbriqués avec un solveur propriétaire, c’est une des raisons pour laquelle l’amalgame entre modeleur et solveur est très vite fait. Il est tout de même important de bien faire la distinction. Mini-Projet ETUDE THEORIQUE DE CERTAINS LOGICIELS DE LA PROGRAMMATION LINEAIRE 4 MISR-fsa-Agadir Mohamed ZAOUI 2. Les principaux solveurs : En tête de liste on retrouve deux concurrents : OSL, renommé Optimization Solutions (d’IBM) et Cplex Callable Library (d’ILOG), qui ont été les premiers à proposer des codes commerciaux robustes et rapides. OSL a été le premier solveur commercial comprenant un algorithme de point intérieur. Il n’est pas proposé avec un modeleur particulier. Robuste et rapide, il est interfaçable avec la plupart des langages de modélisation. Depuis une récente acquisition de Cplex Inc. par ILOG, l’offre du solveur Cplex s’est beaucoup développée. On le retrouve par exemple comme solveur interne dans des logiciels d’optimisation comme ILOG Planner. A côté de ces deux grands, on trouve d’autres codes très robustes et qui ont su se faire une place sur le marché des logiciels d’optimisation. Citons C-Whiz de Ketron Management Science qui tourne sur mainframe et PC, HS/LP, le solveur de Harvely System Inc. qui s’interface très bien avec le modeleur OMNI de la même société, LAMPS d’Advanced Mathematical Software Ltd., LINDO de Lindo Systems Inc., GAUSS d’Aptech Systems Inc., LOQO de l’université de Princeton qui propose des versions gratuites pour le monde académique, MINOS de Stanford Business Software Inc., et bien d’autres encore. Des produits plus connus comme Maple, Matlab ou Excel proposent aussi des extensions permettant de résoudre des PL. Enfin, il existe même un solveur simple du domaine public, LPSolve, diffusé avec son source en C. 3. Les principaux modeleurs : Parmi les modeleurs, AMPL est le plus connu et le plus célèbre. Sa particularité est de pouvoir appeler pratiquement tous les solveurs existants. Les éditeurs de codes algorithmiques en ont fait une référence et se servent de la popularité d’AMPL pour promouvoir leur solveur. C’est sans doute ce qui a rendu AMPL plus célèbre encore. Ce type de langage, qui est très utile aux décideurs d’entreprise en simplifiant la modélisation et la résolution de problèmes d’optimisation, est en pleine expansion. L’offre s’est considérablement étoffée ces cinq dernières années. Les autres langages de modélisation les plus connus, et qui seront brièvement décrits au paragraphe 3.3, sont GAMS (de Gams Developpement Corp.), qui permet des modèles non linéaires, OPL Studio (d’ILOG), qui peut appeler des solveurs de propagation de contraintes en parallèle avec la programmation linéaire, Lingo (de Lindo Systems), très employé dans le monde académique pour les enseignements outre-Atlantique, et MPL for Windows (de Maximal Software). On ne peut pas dire qu’un langage est définitivement Mini-Projet ETUDE THEORIQUE DE CERTAINS LOGICIELS DE LA PROGRAMMATION LINEAIRE 5 MISR-fsa-Agadir Mohamed ZAOUI supérieur à un autre. En fait, pour choisir un langage, la meilleure façon est de tester les versions limitées qui sont proposées sur les sites web des éditeurs de logiciels. 4. Les environnements de développement intégrés (EDI) : Pour satisfaire une clientèle de plus en plus exigeante, les interfaces de développement (EDI) sont apparues et proposent des menus, des fenêtres et d’autres fonctionnalités pour aider l’utilisateur à rédiger et déboguer son modèle. Pour les PC, la plupart des éditeurs fournissent un EDI agréable à utiliser. Cette interface est souvent la version disponible gratuitement sur le web. Parmi uploads/s3/ pl-121104171652-phpapp01.pdf