Remerciez-le!

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

Mardi, le avril 2019 TP 02 : Résoudre des Programmes Linéaires à l’aide de GLPK

Mardi, le avril 2019 TP 02 : Résoudre des Programmes Linéaires à l’aide de GLPK (GNU linear programming kit) GNU Linear Programming Kit (GLPK) est un logiciel dédié à la résolution des programmes linéaires (PLs), et des programmes linéaires à variables mixtes. GLPK a été conçu (en ANSI C) par Andrew Makhorin du département d’informatique appliquée, institut de l’aviation de Moscou en Russie. GLPK fait partie du projet GNU et est publié sous licence GNU General Public License (GPL). Le package GLPK comprend principalement les composants suivants : — Méthode simplex révisée (pour les PLs). — Méthode du point intérieur Primal-Dual (pour les PLs). — Méthode par séparation et évaluation (pour les PLNEs). — Traducteur pour le langage de modélisation GNU MathProg. — Application Program Interface (API). — glpsol, solveur autonome des PLs. Solveur : glpsol Modèle sous format : - MathProg/GMPL .mod - CPLEX LP - MPS . . . etc. Données : (GMPL .dat) Solution : ﬁchier séquentielle (.txt,.out,.sol, . . . ) Figure 1 – Schéma d’utilisation du GLPK GLPK peut traiter des programmes linéaire fournis sous diﬀérents formats : CPLEX LP, MPS, ou décrits à partir d’un langage spécialisé, appelé modeleur GNU MathProg, en séparant les données (ﬁchiers .dat) du modèle (ﬁchier .mod). 1 Installation et documentation oﬃcielle : liens utiles Installez GLPK et GUSEK. Lisez le guide de l’utilisateur Modeling Language GNU MathProg fourni avec GLPK. Les instructions d’installation et la documentation détaillée sont également dispo- nibles sur : — GLPK sous Linux : www.gnu.org/software/glpk/, — Si vous utilisez Ubuntu, lancez simplement la commande : >> sudo apt -get install glpk — GLPK sous Windows (WinGLPK) : winglpk.sourceforge.net/, — Guide d’installation sous Windows 10 : http://www.osemosys.org/uploads/1/8/5/0/18504136/ glpk_installation_guide_for_windows10_-_201702.pdf 1 — GLPK code source : ftp://ftp.funet.fi/pub/gnu/prep/glpk/, — GUSEK (GLPK Under SciTE Extended Kit), une GUI pour GLPK : gusek.sourceforge. net/. — Manuel du langage MathProg/GMPL (GNU Mathematical Programming Language) : en an- glais, gusek.sourceforge.net/gmpl.pdf. En français, http://lim.univ-reunion.fr/staff/ fred/Enseignement/Optim/doc/GLPK/CoursGLPK.pdf. 2 Langage de Modélisation basique : CPLEX LP Format (".lp") GLPK peut donc lire diﬀérents formats d’entrée. Le plus simple a été créé pour le solveur CPLEX. Il revient à écrire un PL ou un PLNE sous le format habituel. <Max,Min>imize <étiquette> : <fonction objectif>, format : s r x s r x ... s r x <Subject To, such that, s.t., st., st> <étiquette> : <Contrainte> format : s c x s c x ... s c x (<=, >=, >, <, =) b ... Bounds <Borne> format : x >(=) l, l <(=) x <(=) u, x = t, x free. ... <Integer, general, binary> <variable> ... Où <fonction objectif> est remplacé par un nom symbolique de la fonction objectif, <étiquette contr.> est remplacé par un nom symbolique d’une contrainte (par exemple : disponibilité), s est un signe + ou -, c est une constante numérique qui désigne un coeﬃcient objectif, x est un symbole nom d’une variable. Voici un petit exemple de programme linéaire sous le format CPLEX LP : (PL)        max Z(x) = CT x, s.c. Ax ≤B, xi ∈Di, ∀i ∈{1, . . . , n}. (P)                                          max Z(x) = x1 + 2 x2 + 3 x3 + x4, s.c. −x1 + x2 + x3 + 10 x4 ≤ 20 x1 −3 x2 + x3 ≤ 30 x2 −3.5 x4 = 0 0 ≤x1 ≤40, x3 ≤4, 2 ≤x4 ≤3, x2 ∈R+, x3, x4 ∈N. Maximize obj: x1 + 2 x2 + 3 x3 + x4 Subject To c1: - x1 + x2 + x3 + 10 x4 <= 20 c2: x1 - 3 x2 + x3 <= 30 c3: x2 - 3.5 x4 = 0 Bounds 0 <= x1 <= 41.5 x3 <= 4 2 <= x4 <= 3 Integer x3 x4 End 2 Remarques : — Un point-virgule doit mettre ﬁn à chaque ligne de code ("instruction"), — les noms des variables, objectifs et contraintes sont obligatoires, ne peut contenir d’espaces, et ne peut être répétés. 1) Créer le ﬁchier Premier.lp contenant le modèle ci-dessus. 2.1 Compilation/résolution Aﬁn de résoudre le LP (lancer le solveur glpsol) déﬁni dans le ﬁchier premier.lp sous format CPLEX LP, utilisez la ligne de commande ci-dessous. Le résultat est écrit dans le ﬁchier premier.sol. >> glpsol --cpxlp premier.lp --output premier.sol Ou, suivre les étapes suivantes pour résoudre le PL sous GUSEK : — Cliquer sur menu Tools →Go pour résoudre votre modèle (ou même, tapper F5). — Aﬁn d’aﬃcher la solution, sélectionner l’option Tools →Generate Output on the Fly. 2) Résoudre le PL déﬁni dans le ﬁchier premier.lp. Commenter sur la qualité de solution fournie. Justiﬁer votre réponse. 2.2 Fichier de sortie glpsol peut fournir en sortie un ﬁchier séquentielle donnant la solution du PL ou du PLNE. Le tableau suivant est le ﬁchier correspondant au programme précédent. Il indique le statut de la solution (optimale ou irréalisable) et la valeur de la fonction objective optimale. Dans le cas d’un PLNE, une valeur supplémentaire ﬁnissant par (LP) est en fait la valeur du PLNE relaxée des contraintes d’intégrité. Problem: Rows: 3 Columns: 4 (2 integer, 0 binary) Non-zeros: 9 Status: INTEGER OPTIMAL Objective: obj = 77.5 (MAXimum) No. Row name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 c1 3 20 2 c2 14 30 3 c3 0 0 = No. Column name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 x1 41.5 0 41.5 2 x2 10.5 0 3 x3 * 4 0 4 4 x4 * 3 2 3 3 Integer feasibility conditions: KKT.PE: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality KKT.PB: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality End of output 2.2.1 Interprétation des résultats Le ﬁchier Premier.sol généré par le solveur, contenant la solution du modèle, est divisé en quatre parties. Noter que les détails décrits dans ce ﬁchier peuvent diﬀérer selon le langage de modélisation utilisé. 1. Informations sur le problème et la valeur de la fonction objectif obtenu. Problem: Rows: 3 Columns: 4 (2 integer, 0 binary) Non-zeros: 9 Status: INTEGER OPTIMAL Objective: obj = 77.5 (MAXimum) 2. Quelques détails sur la fonction objectif et/ou contraintes (la fonction objectif ﬁgure dans le cas l’un modèle GMPL). No. Row name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 c1 3 20 2 c2 14 30 3 c3 0 0 = 3. Préciser les détails des variables de décision et leur valeurs obtenu (le symbole ’*’ signiﬁe que la variable correspondante est entière). No. Column name Activity Lower bound Upper bound ------ ------------ ------------- ------------- ------------- 1 x1 41.5 0 41.5 2 x2 10.5 0 3 x3 * 4 0 4 4 x4 * 3 2 3 4. Informations sur les conditions d’optimalité (conditions de Karush-Kuhn-Tucker). Integer feasibility conditions: 4 KKT.PE: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality KKT.PB: max.abs.err = 0.00e+00 on row 0 max.rel.err = 0.00e+00 on row 0 High quality 3 Langage GMPL/AMPL (GNU MathProg Language) GMPL est un langage de modélisation qui permet de simpliﬁer la modélisation d’un problème d’optimisation à l’aide d’ensembles, de sommes, etc. Voici une description courte et simpliﬁée du langage. Remarques : — Chaque variable a un nom (x1, x2, etc.), la fonction objectif a un nom (z, objectif, etc.) et chaque contrainte a un nom (con1, c1, contrainte, etc.). — Vous êtes libre de choisir des noms, mais ils doivent être diﬀérents. — Pour écrire des commentaires sur le modèle, utilisez d’abord le signe #. — Chaque ligne doit se terminer par un point-virgule (;). — Pour résoudre le même modèle avec plusieurs données diﬀérentes, il est préférable de séparer le modèle et les données. Considérons la formulation générale d’un PL : (PL)                      max Z(x) = n X j=1 cixj, s.t. n X j=1 aij xj ≤bi, i ∈{1, . . . , m} xj ≥0, ∀j ∈{1, . . . , n}, Ensuite, le ﬁchier modèle (.mod) pour GMPL est créé comme suit. Nous utilisons les paramètres introduits, bien qu’ils n’ont pas encore de valeurs numériques. param n; # nombre de variables param m; # nombre of constraints param c{1..n}; # coefficients de la fonction objectif param a{1..m,1..n}; # Matrice de contraintes param b{1..m}; # Bornes des contraintes var x{1..n} >= 0; # Variables de décision maximize objectif: sum{j in 1..n} c[j]*x[j]; subject to contrainte{i in 1..m}: sum{j in 1..n} a[i,j]*x[j] <= b[i]; end; 3) Créer le ﬁchier Premier.mod contenant le modèle déﬁni ci-dessus. 5 Ici n, m, c, a et b sont des paramètres (param) et x sont des variables (var). n est uploads/Management/ tp-glpk.pdf