El entorno GAMS GAMS (General Algebraic Modeling System) es un entorno para definir, analizar y resolver problemas de optimizaci´n. o Los elementos m´s importantes de GAMS son: a 1. Su capacidad para resolver problemas peque˜os (docenas n de variables y restricciones) y grandes problemas (miles de variables y restricciones) escribiendo b´sicamente el a mismo programa. Dispone de una forma compacta y eficiente para escribir bloques de ecuaciones similares sin m´s que escribir “una de ellas”. a 2. Se separa la definici´n del modelo de la t´cnica de reo e soluci´n. El usuario de GAMS formula el modelo cono sistentemente, y una vez expresado en notaci´n GAMS, o uno de los programas disponibles se encarga de generar la soluci´n. Como resultado, el usuario se centra en el o modelado, sin ser perturbado por los problemas t´cnicos e de los algoritmos de resoluci´n. Esto hace posible un o proceso de modelado muy sencillo y agradable. 3. GAMS pr´cticamente reproduce la descripci´n del proa o blema de programaci´n matem´tica. Como resultado, el o a c´digo GAMS is casi auto-explicativo para los lectores o que tengan una m´ ınima formaci´n en optimizaci´n. o o 4. GAMS suministra tambi´n mecanismos que permiten ree solver colecciones de problemas de optimizaci´n estruco turados, tales como los de t´cnicas de descomposici´n. e o 273 EL problema del transporte Distancias en Km. mercados plantas m1 m2 m3 p1 2.0 1.6 1.8 p2 2.5 1.2 1.4 El problema consiste en Minimizar j i j cij xij sujeta a Los datos son: xij ≤ ai, ∀i i xij ≥ bj , ∀j xij ≥ 0, ∀i, j, i: N´mero de plantas (2). u j: N´mero de mercados (3). u a o ai: La m´xima capacidad de producci´n de la planta i en toneladas (300 y 500 toneladas), bj : La demanda del mercado j en toneladas (100, 200 y 300 toneladas), y cij : el coste de transporte de la planta i al mercado j (0.09 d´lares por tonelada y km). o Las variables de decisi´n son: o xij : la cantidad de producto a enviar de la planta i al mercado j, en toneladas. 274 Problema del transporte ´ Codigo GAMS $Title The Transportation Problem * Simple transportation example Sets i production plants / p1, p2 / j markets / m1*m3 /; Table d(i,j) distance in km m1 m2 m3 p1 2.0 1.6 1.8 p2 2.5 1.2 1.4; Scalar f freight (dollars per ton y km) /0.09/; Parameters a(i) capacity of plant i in tons / p1 300 p2 500 / b(j) demand at market j in tons / m1 100 m2 200 m3 300 / c(i,j) transportation cost in dollars per ton; c(i,j) = f * d(i,j); Variables x(i,j) shipment quantities in tons z total transportation costs in dollars; Positive Variable x; Equations cost objective function supply(i) meet supply limit at plant i demand(j) satisfy demand at market j; cost .. z =e= sum((i,j), c(i,j)*x(i,j)); supply(i) .. sum(j, x(i,j)) =l= a(i); demand(j) .. sum(i, x(i,j)) =g= b(j); Model transport /all/; Solve transport using lp minimizing z; Display x.l; 275 Algunos comandos de GAMS Comando Set(s) Prop´sito o Dar nombre a los ´ ındices y definir sus posibles valores Scalar(s) Dar nombre a los escalares y asignarles valores Parameter(s) Dar nombre a los vectores y asignarles valores Table(s) Dar nombre a las matrices y asignarles valores Variable(s) Declarar variables, asignarles un tipo (opcional) y darles cotas inferior y superior Equation(s) Definir la funci´n a optimizar o y las restricciones Model Dar nombre a los modelos y asignarles la lista de restricciones Solve Indicar a GAMS el programa que debe resolverlo Display Decir a GAMS los elementos a listar en el informe de salida 276 Reglas de GAMS 1. GAMS no diferencia entre letras may´sculas y u min´sculas. u 2. Todo comando debe terminar en punto y coma. 3. Los comandos pueden definirse en cualquier orden, con la unica restricci´n de que un elemento debe haber sido ´ o definido antes de usarlo. 4. GAMS tiene palabras reservadas, que no pueden usarse para otro fin que el suyo propio. 5. Algunos comandos se identifican por sus primeras letras, por lo que puede a˜adirse una ‘s’ para facilitar la lectura. n 6. Los comandos pueden escribirse en estilo libre (una o varias l´ ıneas, uno o varios espacios, etc.) 7. Para definir un bloque de elementos basta usar el comando una vez. 8. Una l´ ınea precedida por un asterisco (en la primera columna) es interpretada como un comentario. 9. La mayor´ de los comandos (sets, scalar, parameter, ıa table, variables, equations y model) se utilizan para declarar elementos y/o darles valores, lo que los convierte en v´lidos para GAMS. a 10. Los nombres deben comenzar por una letra y seguir con letras o d´ ıgitos, hasta un m´ximo de 9. a 277 SETS y SCALARS La palabra reservada Set o Sets identifica el comando SET, que se usa en GAMS para declarar ´ ındices, y especificar el conjunto de valores que toman. Por ejemplo Sets i production plants / p1, p2 / j markets / m1*m3 /; que define los dos ´ ındices i y j. El texto tras el n´mero de los ´ u ındices es ignorado por el compilador de GAMS. La asignaci´n de valores se hace entre dos s´ o ımbolos ‘/’. El s´ ımbolo ‘∗’ ayuda a definir, en forma compacta, conjuntos num´ricos, e es decir, /m1∗m3/ es equivalente a /m1, m2, m3/. Sin embargo, GAMS trata los valores de los ´ ındices como cadenas de caracteres. El comando concluye con el punto y coma. Los conjuntos anteriores tienen car´cter est´tico, es decir, no cambian a a durante la ejecuci´n del programa. En GAMS se pueden definir tambi´n o e conjuntos din´micos, que son subconjuntos de los conjuntos est´ticos, pero a a que pueden cambiar durante la ejecuci´n del programa. o Un comando ligado a la definici´n de conjuntos es el comando alias. Este o comando permite dar variaos nombres equivalentes, al mismo conjunto: Alias(i,k); ´ da un segundo nombre k, al conjunto i. Estos se usan en sumas, productos, etc., cuando hay dos o m´s ´ a ındices implicados y necesitan variar independientemente. Los escalares GAMS son escalares de datos. La palabra reservada Scalar o Scalars identifica el comando: Scalar f freight (dollars per ton y km) /0.09/; Se define el escalar ‘f’ y se le asigna el valor 0.09 entre dos ‘/’. 278 PARAMETERS y TABLES I Los comandos PARAMETER y TABLE se usan en GAMS para definir vectores y matrices de datos. Ambos son equivalentes, excepto que para definir vectores es necesario usar el comando PARAMETER. La palabra reservada Parameter, o Parameters, identifica el comando parameter the PARAMETER., que sirve para declarar vectores y matrices. Los vectores de datos se declaran con ayuda de un ´ ındice, como en. Parameters a(i) capacity of plant i in tons / p1 300 p2 500 /; que define el par´metro a(i) en funci´n del conjunto (´ a o ındice) i. Para cada valor del ´ ındice (elemento del conjunto) (p1, p2) se da un valor del par´metro (300, 500) entre dos s´ a ımbolos ‘/’. El comando termina con punto y coma. Para asignar valores a vectores deben tenerse en cuenta las reglas siguientes: 1. La lista opcional de posibles ´ndices y sus correspondientes valores ı deben ir entre s´ ımbolos ‘/.../’ y separados por comas o pasos de l´ ınea. 2. Las parejas ´ ındice-valor pueden ir en cualquier orden. 3. El valor por defecto de cualquier par´metro es ‘cero’, por lo que s´lo a o aquellos que tomen valores diferentes, deben darse. 4. GAMS comprueba que los ´ ındices son v´lidos. a Se pueden definir valores de los par´metros mediante funciones: a Parameter c(i,j) transportation cost in dollars per ton; c(i,j) = f * d(i,j); 279 PARAMETERS y TABLES II La definici´n anterior es la forma compacta de la que sigue: o Parameter c(i,j) transportation cost in dollars per ton / p1.m1 0.180 p2.m1 0.225 p1.m2 0.144 p2.m2 0.108 p1.m3 0.162 p2.m3 0.126 /; Las matrices de datos se definen en GAMS mediante tablas. La palabra reservada Table o Tables identifica este comando. Las tablas se definen usando dos o m´s ´ a ındices. Se pueden introducir comentarios tras el nombre de la tablas, como en: Table d(i,j) p1 p2 distance in km m1 m2 2.0 1.6 2.5 1.2 m3 1.8 1.4; que define la matriz d(i,j) mediante los ´ ındices indices i y j. Para cada pareja cruzada de ´ ındices (p1.m1, p1.m2, p1.m3, p2.m1, p2.m2, p2.m3) se especifica un valor (2.0, 1.6, 1.8, 2.5, 1.2, 1.4). Para mostrar la equivalencia entre los comandos PARAMETER y TABLE se define la matriz c(i,j) usando ambos Table c(i,j) transportation cost in dollars per ton m1 m2 m3 p1 0.180 0.144 0.162 p2 0.225 0.108 0.126; N´tese que ´sta no es la forma m´s compacta de definir c(i,j). o e a 280 ´ Expresiones matematicas Para asignar valores utilizando expresiones matem´ticas hay a que tener en cuenta las reglas siguientes: 1. El uso de ´ ındices en la asignaci´n indica que la asignaci´n o o se hace para todos sus posibles valores y combinaciones de ellos. 2. Se puede hacer una asignaci´n espec´ o ıfica dando los valores de los ´ ındices entre comillas: c(’p1’,’m1’)=0.180; 3. Se pueden asignar m´s de una vez valores a los escalares, a par´metros y tablas. Los nuevos valores reemplazan a los a antiguos. 4. Las expresiones matem´ticas pueden incorporar funciones a matem´ticas est´ndar (ver tabla adjunta). a a 281 ´ Funciones matematicas en GAMS Funci´n o abs(x) arctan(x) ceil(x) cos(x) errorf(x) Descripci´n o Valor absoluto de x Arco tangente (en radianes) M´ ınimo entero mayor o igual que x Funci´n coseno (x en radianes) o Funci´n de distribuci´nn o o de la normal N (0, 1) en x exp(x) Funci´n exponencial o floor(x) Mayor entero menor o igual que x log(x) Logaritmo natural de x log10(x) Logaritmo en base 10 de x mapval(x) Funci´n proyecci´n o o max(x1,x2,...) M´ximo de una lista a min(x1,x2,...) M` ınimo de una lista mod(x,y) Resto al dividir x por y normal(x,y) N´mero aleatorio de una variable normal u con media x y desviaci´n t´ o ıpica y power(x,y) Funci´n potencial xy (donde y debe ser un entero) o x ∗ ∗y Funci´n potencial xy (donde x debe ser positiva) o round(x) Redondeo de x al entero m´s cercano a round(x,y) Redondea x a y decimales sign(x) Signo de x, 1 si positivo, -1 si negativo, y 0 si nulo. sin(x) Funci´n seno (en radianes) o sqr(x) Cuadrado de x sqrt(x) Ra´ cuadrada de x ız trunc(x) Es igual a sign(x) * floor(abs(x)) uniform(x,y) N´mero aleatorio uniforme U (x, y) u 282 Variables Las variables se declaran en GAMS como sigue: Variables x(i,j) z Cantidades enviadas en toneladas coste total del transporte en d´lares; o La palabra reservada Variable o Variables identifica el comando variable. La declaraci´n de las variables debe incluir las dimensiones de las o mismas. Debe utilizarse siempre una variable para representar la funci´n o objetivo. Tambi´n se pueden definir diferentes tipos de variables (ver tabla): e Positive Variable x; Binary Variable r; Tipo de variable Rango Rango por defecto binary {0, 1} {0, 1} free (default) (−∞, ∞) (−∞, ∞) integer {0, 1, . . . , n} {0, 1, . . . , 100} negative (−∞, 0) (−∞, 0) positive (0, ∞) (0, ∞) Se pueden fijar tambi´n cotas para las variables, o fijar sus valores (no e cambian durante la ejecuci´n): o r.lo = 2.0; r.up = 5.0; y.fx(i) = 3.0; y cambiar los valores de las variables durante la ejecuci´n: o s.l(i,j) = 3.0; 283 EQUATIONS La palabra reservada Equation o Equations identifica el comando epara definir restricciones en GAMS. Las ecuaciones deben ser declaradas primero y definidas despu´s, usando el s´ e ımbolo ‘..’ para acoplar los nombres con las definiciones de ´stas. e Equations cost objective function supply(i) meet supply limit at plant i demand(j) satisfy demand at market j; cost .. z =e= sum((i,j), c(i,j)*x(i,j)); supply(i) .. sum(j, x(i,j)) =l= a(i); demand(j) .. sum(i, x(i,j)) =g= b(j); El sumatorio i xij se expresa sum(i, x(i,j)), y Πixij , se escribe prod(i, x(i,j)). Los s´ ımbolos que se utilizan en las ecuaciones son: • =e= indica ‘es igual a’, • =l= indica ‘es menor o igual que’, y • =g= indica ‘es mayor o igual que’. Se pueden definir muchas ecuaciones simult´neamente, usando ´ a ındices: supply(i) .. es equivalente a: supply1 .. supply2 .. sum(j,x(’p1’,j)) sum(j,x(’p2’,j)) =l= =l= a(’p1’); a(’p2’); sum(j, x(i,j)) =l= a(i); 284 MODEL AND SOLVE El comando Model se usa para indicar a GAMS las restricciones que debe incluir un determinado modelo. El comando Model que sigue indica que el problema considerado incluye todas las restricciones definidas previamente: Model transport /all/; Tambi´n puede escribirse como: e Model transport /cost,supply,demand/; El comando Solve indica a GAMS que resuelva el problema indicado. El comando Solve que sigue indica a GAMS que resuelva el problema transport usando el programa de programaci´n lineal (lp) y minimizano do la variable z. Solve transport using lp minimizing z; La palabra reservada lp se usa para programaci´n lineal. Otras opciones o se dan en la tabla. Programa lp nlp dnlp mip rmip minlp rminlp mcp mpec cns Prop´sito o Programaci´n lineal o Programaci´n no lineal o Programaci´n no lineal con derivadas discontinuas o Programaci´n entera mixta o Programaci´n entera mixta relajada o Programaci´n no lineal entera mixta o Programaci´n no lineal entera mixta relajada o Problemas complementarios mixtos Problemas matem´ticos con restricciones de equilibrio a Sistemas no lineales con restricciones 285 ´ Informacion sobre recursos En GAMS pueden usarse sub´ ındices para obtener informaci´n valiosa soo bre ciertos recursos, una vez que se ha resuelto el problema. Algunos sub´ ındices notables son: modelstat para comprobar el estado del modelo, solvestat para comprobar el estado del programa que lo resuelve y resusd para comprobar el tiempo (en segundos de CPU) empleado para resolverlo. V´anse los posibles valores de modelstat y e solvestat en la tabla adjunta. Un ejemplo es: Display transport.resusd; Valor 1 2 3 4 5 6 7 8 9 10 11 12 13 modelstat optimal locally optimal unbounded infeasible locally infeasible intermediate infeasible intermediate non-optimal integer solution intermediate non-integer integer infeasible error unknown error no solution solvestat normal completion iteration interrupt resource interrupt terminated by solver evaluation error limit unknown error: preprocessor error error: setup failure error: solver failure error: internal solver error error: post-processor error error: system failure 286 Uso del asterisco Se puede usar el asterisco para: • A˜adir comentarios (primera columna de una l´ n ınea). • Para listar los elementos de un conjunto en forma compacta. • Para marcar errores en el fichero de salida (cuatro asteriscos al comienzo de la l´ ınea). • Para indicar en el fichero de salida que las restricciones no lineales no son factibles en el punto de partida (tres asteriscos al final de la l´ ınea). • Como operador producto. • Para definir conjuntos indirectamente en las estructuras de GAMS (sets, parameters, tables, variables o equations). Por ejemplo: Set A conjunto de art´culos /a1,a2/; ı Table g(A,*) aspectos de los A art´culos ı altura anchura peso * (cm) (cm) (kg) a1 1.0 2.7 3.5 a2 2.4 1.8 4.4; es euivalente a Sets A set of articles /a1,a2/ B set of features /height,width,weight/; Table g(A,B) features of the A articles altura anchura peso * (cm) (cm) (kg) a1 1.0 2.7 3.5 a2 2.4 1.8 4.4; 287 Comandos condicionales El s´ ımbolo ‘$’ puede utilizarse para generar subconjuntos convenientes de los conjuntos ordenados originales. La sentencia. demand(j)$(ord(j) gt 1).. sum(i, x(i,j))=g=b(j); es equivalente a demand2.. demand3.. sum(i, x(i,’m2’)) sum(i, x(i,’m3’)) =g= =g= b(’m2’); b(’m3’); N´tese que $(ord(j) gt 1) indica que s´lo los elementos cuyo ordinal o o sea mayor que 1 deben ser inclu´ ıdos. Estas condiciones se pueden utilizar tambi´n en otros comandos de GAMS e como: asignaciones de datos, comando ‘put’, etc. En todos estos casos es posible reemplazar el operador ‘$’ por los comandos ‘if-then-else’. Sin embargo, por compacidad se usa m´s el ‘$’. a Otros operadores comunes en otros lenguajes son tambi´n v´lidos en e a GAMS: • not, y, or, xor como operadores l´gicos; o • < (lt), = (ge), > (gt) como operadores relacionales. 288 ´ Conjuntos dinamicos I Una caracter´ ıstica muy potente de GAMS es que permite usar conjuntos din´micos. Usando ´stos se pueden modificar los elementos que a e pertenecen a un conjunto durante la ejecuci´n de un programa GAMS. o Los conjuntos din´micos se definen siempre como subconjuntos de uno a est´tico previamente definido. Las variables, par´metros, tablas y ecuaa a ciones que dependen de un conjunto din´mico pueden ser modificadas cada a vez que se actualiza un conjunto din´mico. La tabla que sigue muestra la a equivalencia entre las expresiones matem´ticas y las de GAMS. a Expresi´n matem´tica o a k = {a, b, c} s⊆k s=∅ s = {c} s = {b, c} Expresi´n GAMS o Set k /a,b,c/ s(k); s(k)=no; s(k)=no; s(k)$(ord(k) eq card(k))=yes; s(k)=no; s(k)$(ord(k) gt 1)=yes; En la primera fila se define el conjunto est´tico ‘k’ y luego el subconjunto a din´mico ‘s(k)’ como funci´n de ‘k’. a o Antes de usar un conjunto din´mico hay que definir su estado inicial. a Uno de ellos es el conjunto vac´ que se define en la segunda fila. ıo, 289 ´ Conjuntos dinamicos II La tercera fila muestra c´mo asignar el ultimo elemento de ‘k’ al ‘s(k)’, o ´ mediante los operadores‘ord(k)’ y ‘card(k)’. El operador ‘card’ devuelve el n´mero de elementos, y el ‘ord’, la posici´n de un elemento. u o El operador ‘ord’ s´lo es v´lido para conjuntos est´ticos). o a a La ultima fila indica c´mo asignar dos elementos a ‘s(k)’. ´ o Se pueden implementar en GAMS operaciones entre conjuntos usando conjuntos din´micos. Los ejemplos de la tabla adjunta muestran algunos a interesantes: Expresi´n matem´tica o a A = {a1, a2, a3, a4, a5} b ⊆ A, b = {a1, a2, a5} c ⊆ A, c = {a2, a3, a5} b ∪ c = {a1, a2, a3, a5} b ∩ c = {a2, a5} ¯ = {a3, a4} b b − c = {a1} Expresi´n GAMS o set A static set /a1*a5/; set B(A) subset /a1,a2,a5/; set C(A) subset /a2,a3,a5/; set UN(A) dynamic subset; UN(A)=B(A)+C(A); set IN(A) dynamic subset; IN(A)=B(A)*C(A); set COMP(A) dynamic subset; COMP(A)=not B(A); set DIFF(A) dynamic subset; DIFF(A)=B(A)-C(A); 290 Comandos de control El ejemplo siguiente ilustra c´mo se usan los comandos de control. o loop(S, loop(JJ, x0=0.0001; x1=2.0; aux=W0.l(JJ)+sum(I,W.l(JJ,I)*X(I,S)); error=1000; f0=sum(R$(ord(R)