Remerciez-le!

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

CHAPITRE 6 Logiciel pour la résolution des programmes linéaires : LINDO (Linear

CHAPITRE 6 Logiciel pour la résolution des programmes linéaires : LINDO (Linear INteractive and Discrete Optimizer) I. Introduction Lindo est un logiciel utilisé pour résoudre les modèles d’optimisation linéaires, entiers et quadratiques. Une des caractéristiques de Lindo c’est qu’il offre des outils qui peuvent aider à l’analyse des modèles en utilisant la méthode de Simplexe. On présente dans ce chapitre la version étudiant 6.0 (1997). Cette version résout des problèmes de dimension maximale de 200 variables et de 100 contraintes. II. Installation du Logiciel Pour utiliser cette version de Lindo il est conseillé d’avoir au moins un processeur 486 et 8Mo de mémoire RAM. Il faut aussi prévoir un espace disque dur de 2Mo pour pouvoir l’installer. Les étapes de l’installation sont : 1. Démarrer Windows. 2. Insérer le CD-ROM ou la disquette. 3. Cliquer sur l’icône Setup (install) dans votre explorateur de Windows 4. Suivre les instructions sur l’écran Pour plus d’information sur ce logiciel visiter l’adresse web : www.lindo.com III. Résolution d’un exemple Dans cette section, et sur la base de l’exemple de l’agriculteur, on va focaliser notre attention sur les opérations suivantes : introduire les données, résoudre le problème, et analyser les résultats que donne LINDO. a. Le problème de l’agriculteur Le programme linéaire qui modélise le problème de l’agriculture est : 0 2 , 0 1 90 1 480 2 4 1 440 2 2 1 4 150 2 1 . . 2 200 1 100           x x x x x x x x x c s x x Max b. Introduction des données Double cliquer sur l’icône «lindo 6.0 for Windows » de votre menu démarrer/programmes. Le logiciel va s’exécuter et vous aurez cette fenêtre qui s’affiche sur votre écran : Dans tous les modèles de Lindo la fonction objectif est définie en première ligne. Dans notre exemple la fonction objectif est : 2 _ 200 _ _ 1 _ 100 _ x x Max  Les tirés bas indique la présence d’un espace obligatoire entre les entrées pour pouvoir les différentiées. Il faut noter qu’on peut remplacer x1 et x2 par n’importe quel mot qui indique ces deux variables, par exemple, on peut remplacer x1 par "tomates" et x2 par "piments". Une autre caractéristique est que Lindo ne fait pas de différence entre majuscule et minuscule. Pour lui la variable « TOMATE » est la même que la variable « tomAtE ». Pour commencer à écrire les contraintes, il faut introduire la mention « subject to » ou tout simplement son abréviation « st ». Dans notre exemple les contraintes sont : 90 _ _ 1 bureau) 480 _ _ 2 _ 4 _ _ 1 Mo) 440 _ _ 2 _ 2 _ _ 1 _ 4 eau) 150 _ _ 2 _ _ 1 terrain) _        x x x x x x x to subject On remarque qu’on peut appeler chaque contrainte par un nom nominatif que Lindo va utiliser pour afficher les résultats. L’écran qu’on obtient après avoir introduit les différents paramètres est le suivant : On n’a pas à ajouter les contraintes de non-négativité, Lindo suppose par défaut que les variables de décision sont de types nonnégative. c. Résolution du problème Après avoir écrit convenablement le programme linéaire, on passe maintenant à la résolution. Pour résoudre notre programme il faut cliquer sur le bouton « » dans la barre d’outils. Lindo va commencer ainsi à compiler le modèle. Si un message d’erreur s’affiche c’est que le programme, par exemple, est non borné ou bien non réalisable... Lors de la compilation, on voit une barre qui montre le pourcentage de travail effectué. d. Interprétation des résultats S’il n’y a pas d’erreur de formulation, Lindo va commencer à résoudre le problème. Par défaut, il va vous demander si vous voulez faire une analyse de sensibilité. Pour le moment on va répondre « Non ». Avant que Lindo nous propose un premier rapport sur la solution optimale, il nous donne l’état du problème exprimé par cette fenêtre : Ce rapport préliminaire nous indique que : a) Status : Optimal ; Il nous informe sur l’état de la solution actuelle. Elle peut être Optimal (optimale), Feasible (réalisable), Infeasible (non réalisable) ou Unbounded (non bornée). b) Iterations : 2 ; Il indique le nombre d’itérations nécessaire pour résoudre le problème (en utilisant la version révisée de la méthode de Simplexe). c) Infeasibility : 0 ; Ceci indique la quantité de violation dans les contraintes. d) Objective : 26000 ; C’est la valeur de fonction objectif relative à la solution actuelle. e) Best IP : N/A ; C’est la meilleure valeur de la fonction objectif. Ceci n’est vrai que pour les problèmes de type entier. f) IP Bound : N/A ; C’est la borne de la fonction objectif pour cette solution. Ceci n’est vrai que pour les problèmes de type entier. g) Branches : N/A ; C’est le nombre de variables entiers « branched on » par Lindo. Ceci n’est vrai que pour les programmes de type entier. h) Elapsed Time : 00 :06 :45 ; C’est le temps écoulé avant que le résolveur ne soit invoqué (ce temps est variable même pour le même exemple). Si on ferme cette fenêtre, on remarque qu’un autre rapport s’affiche. Ce rapport contient des informations sur la solution optimale. Dans le tableau ci-dessus s’affichent dans la première colonne les différentes variables de décision et aussi les variables d’écart relatives à chaque contrainte du programme. Leurs valeurs sont données dans la deuxième colonne. On vérifie bien que la solution optimale coïncide avec la solution déjà retrouvée dans les précédants chapitres. La troisième colonne représente les valeurs nettes, i.e. j j z c  . Pour les variable d’ecart c’est les prix duals. III. Les commandes de Lindo Dans cette section, on décrit brièvement les différentes commandes présentes dans le logiciel Lindo. Dans l’environnement Windows, Lindo divise ces commandes en six catégories. 1. File a) New : Créer un nouveau document. b) Open : Ouvrir un document existant et le placer dans une fenêtre d’édition (cette fenêtre a une capacité maximale de 64000 caractères). c) View : Ouvrir un document existant dans une fenêtre de vision (view window). Ce genre de fenêtre permet d’importer des programmes à plus de 64000 caractères de votre éditeur (tels que Word). Quelques opérations ne sont pas autorisées dans un view window tels que : couper, copier, coller, effacer… d) Save : Enregistrer. Le format par défaut est le *.ltx, et c’est le format texte de Lindo. e) Save as : Enregistrer sous. D’autres formats sont présents tels que le *.lpk (c’est un format compressé qui ne peut être lu par aucun autre éditeur autre que celui de Lindo) ou le *.mps (malgré qu’il n’accepte pas les commentaires dans le rapport, ce format est utilisé par d’autres logiciels) f) Close : fermé. g) Print : Imprimé. h) Priter setup : propriétés de l’imprimante. i) Log Output : Pour ouvrir ou fermer des log file utilisés pour enregistrer les résultats de votre session. j) Take Commands : Pour exécuter des macros. k) Basis Read : Pour charger du disque une solution de base pour le modèle actif. l) Basis Save : Enregistrer sur le disque la solution de base du modèle actif. m) Title : Afficher le nom pour le modèle actif. n) Date : Afficher la date. o) Elapsed Time : Afficher le temps écoulé depuis le commencement de la session. p) Exit : Quitter Lindo. 2. Edition a) Undo :Annuler la dernière opération. b) Cut : Couper c) Copy : Copier d) Paste : Coller e) Clear : Effacer f) Find /Replace : Rechercher/Remplacer g) Options : Utiliser pour modifier les paramètres par défaut du système. h) Go to Line : aller à la ligne numéro .. de la fenêtre active. i) Paste Symbol : Elle affiche une fenêtre de dialogue qui contient les syntaxes, les variables et les noms des lignes réservés par Lindo. On peut utiliser cette commande pour ajouter des contraintes supplémentaires au modèle. j) Select All : Sélectionner Tout k) Clear All : Effacer tout l) Choose New Font : Choisir les polices dans la fenêtre active. 3. Solve a) Solve : Résoudre le modèle dont la fenêtre est active b) Compile Model : Compiler (sans résoudre) le modèle dont la fenêtre est active c) Debug : Débugger le modèle dont la fenêtre est active, s’il est non réalisable ou non borné. Dans le cas d’un problème non réalisable, la commande Debug détecte l’ensemble des contraintes (sufficient set), dont l’élimination est suffisante pour garantir une solution optimale. Et il détermine aussi un ensemble de contraintes (necessary set), dont la modification entraîne nécessairement un modèle réalisable. Dans le cas d’un problème non borné, la commande Debug détecte l’ensemble des variables de décision (sufficient set), dont la fixation de leurs valeurs est suffisante pour garantir une solution optimale. Et il détermine aussi un ensemble de variables uploads/Management/ chap6.pdf