Source: http://slideplayer.es/slide/1640939/
Timestamp: 2016-10-25 19:10:53+00:00

Document:
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. INTRODUCCIÓN A GAMS Modelos de Programación Lineal Aplicados a la Economía. - ppt descargar
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. INTRODUCCIÓN A GAMS Modelos de Programación Lineal Aplicados a la Economía.
Publicada porIgnacio Villanova
Presentación del tema: "ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. INTRODUCCIÓN A GAMS Modelos de Programación Lineal Aplicados a la Economía."— Transcripción de la presentación:
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. INTRODUCCIÓN A GAMS Modelos de Programación Lineal Aplicados a la Economía 2
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. GAMS GAMS (General Algebraic Modeling System) es un lenguaje de programación que permite el modelado, análisis y resolución de diversos problemas de optimización. Como su nombre lo indica es un lenguaje de modelización, más que un programa para resolver problemas de optimización. Lenguajes algebraicos: Separan los datos de las soluciones, permiten detectar errores de consistencia en la definición y verificación del modelado: GAMS, AMPL, AIMMS, XPRESS-MP 3
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. CARACTERÍSTICAS Entre las características más importantes de GAMS caben destacar : 1. Su capacidad para pasar de resolver problemas de pequeña dimensión (docenas de variables y restricciones) a problemas mayores (miles de variables y restricciones) sin variar el código sustancialmente. El manejo eficiente de sus índices permite escribir de manera compacta restricciones similares mediante una sola restricción. 2. Separa el proceso de modelado del proceso de resolución del problema. Así, el usuario de GAMS debe ser capaz de conseguir una formulación consistente del problema, y una vez la expresa en la notación de GAMS, este lenguaje hace uso de alguno de los optimizadores (solvers) disponibles para obtener su solución. De esta manera, el usuario sólo ha de centrarse en obtener un modelo del problema y puede ignorar el funcionamiento interno del algoritmo que se necesita para resolverlo. La separación de estas dos tareas permite cambiar el modelo para mejorarlo o completarlo cómodamente. 4
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. 3. La forma en que GAMS representa un problema de optimización coincide, prácticamente, con la descripción matemática de ese problema. Por tanto, el código GAMS es sencillo de comprender para aquellos lectores familiarizados con la optimización. 4. Además, GAMS proporciona los mecanismos necesarios para resolver problemas de optimización con estructuras similares, como son aquellos que se derivan de las técnicas de descomposición. 5. La ventaja que presenta este programa GAMS, es que junto al módulo de modelización (base) incorpora diferentes solver (algoritmos de resolución de problemas) tanto de programación no lineal, como lineal y entera. CARACTERÍSTICAS 5
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. ¿Aprender GAMS? El usuario de GAMS debe ser cuidadoso con las reglas gramaticales de GAMS. El incumplimiento de una sola de ellas puede provocar muchos errores de compilación. Entre la bibliografía de este lenguaje de programación cabe destacar el manual de GAMS (http://www.gams.com), cuyo segundo capítulo ofrece un resumen con las características principales para empezar a programar en este lenguaje, y el artículo de Chattopadhyay, D., Application of General Algebraic Modeling System to Power System Optimization, IEEE Trans. Power Systems 14(1), 15–22 (Feb. 1999), que proporciona un enfoque ingenieril de GAMS. 6
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Poder de GAMS El lenguaje GAMS posee diferentes versiones (estudiante, profesional, workstation,mainframe, etc.) que se diferencian básicamente en las posibilidades de resolución de problemas de diferente tamaño, así por ejemplo, en la versión básica de estudiante existen una serie de limitaciones en cuanto al tamaño del problema que admite un máximo de 1000 elementos distintos de cero en los problemas lineales y no lineales, y de 20 variables enteras. 7
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Tipos de problemas que resuelve Con el método que uno escoja: Primal Simplex Dual Simplex Network Interior Point 8
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Desventajas Quizá uno de los inconvenientes de GAMS de cara a su aplicación práctica con los estudiantes es lo poco amigable que resulta su uso las primeras veces, pero creemos que este inconveniente se ve superado, con creces, por la potencia y flexibilidad de este programa. Para poder resolver un problema con GAMS, es necesario generar un fichero de datos (en adelante lo denominaremos fichero GMS) que debe contener todas la instrucciones básicas y planteamiento del modelo que se desea resolver. Una vez generado el fichero, se ejecuta GAMS y el resultado se genera de forma automática en un fichero distinto (fichero LST). Si comparamos este procedimiento con la resolución de problemas de optimización con programas, como por ejemplo, EXCEL, LINDO, etc. podemos observar que resulta un poco más complicado, pero a medida que vayamos exponiendo los procedimientos y posibilidades de GAMS, nos daremos cuenta que no se trata de un grave inconveniente y que por el contrario, presenta una serie de ventajas como son el hecho de que con GAMS podemos usar un fichero de datos que contenga todas las instrucciones y datos necesario del problema, o bien podemos recurrir a leer ficheros de datos externos. 9
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Reglas gramaticales 1. En GAMS, es indiferente el uso de mayúsculas o minúsculas. 2. Cada comando debe terminar con un punto y coma. El olvido de este separador de órdenes puede provocar muchos errores de compilación. 3. Los comandos pueden aparecer en cualquier lugar siempre que los datos y variables que se utilizan hayan sido declarados con anterioridad. 4. Como en cualquier otro lenguaje de programación, los identificadores que se utilicen para declarar datos o variables no pueden coincidir con las palabras reservadas de GAMS. 5. En algunos comandos de GAMS, el uso de la s final es indiferente. Así, se puede emplear indistintamente el comando Set o Sets para definir uno o varios conjuntos de índices. 6. Es posible escribir varios comandos en una misma línea siempre que estén separadas por punto y coma. El compilador considera sucesivos espacios en blanco como uno solo. 10
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. 7. Un simple comando es válido para declarar o definir uno o varios elementos del mismo tipo. No hay necesidad de repetir el nombre del comando. 8. Para documentar el código GAMS es necesario incluir líneas de comentarios. El compilador de GAMS ignora cualquier línea cuya primera columna es un asterisco, considerándola un comentario. También es posible añadir un texto aclaratorio (opcionalmente entre comillas) tras algunos comandos de declaración en GAMS, como son: set, scalar, parameter, table, equation, y model. Este texto debe ayudar a comprender la utilidad del elemento. 9. La mayoría de los comandos son necesarios en la declaración de elementos y, opcionalmente, para asignarle valores. Declarar un elemento (escalar, vector, matriz, etc...) consiste en asignarle un identificador mediante cualquiera de los comandos declarativos (sets, scalar, parameter, table, variables, equations, y model). La declaración permite que un elemento pueda utilizarse en comandos posteriores. 10. Los identificadores usados en GAMS deben comenzar por una letra y pueden ir seguidos por hasta nueve caracteres alfanuméricos, no estando permitida la letra ñ, ni los caracteres especiales como los acentos o tildes (esto último tampoco está permitido en los textos explicativos). Reglas gramaticales 11
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Variables 12
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Opciones de problemas a resolverse 13
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Modelo de transporte 14
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Modelo de transporte Considérese un conjunto de consumidores y productores. Conocida (1) demanda de cada consumidor, (2) la producción máxima de los productores, y (3) el coste del transporte de los productos desde los productores hasta los consumidores, el problema del transporte consiste en determinar la cantidad de producto a transportar de forma que el coste sea mínimo. Considérense dos productores y dos consumidores. Las producciones máximas son 300 y 500 toneladas. Las demandas son de 100, 200 y 300 toneladas. Las distancias en kilómetros entre productores y consumidores vienen dadas en la tabla que se muestra más abajo. El coste de transporte en euros es de 0.09 por tonelada y kilómetro. La formulación del problema anterior es como sigue. 15
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Modelo de transporte 16
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Resolución en GAMS 17
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Resolución en GAMS 18
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Observaciones Se puede comprobar con este ejemplo la similitud entre la formulación matemática y el código GAMS; concretamente, en la parte donde se definen las restricciones (la definición comienza en coste..). En la primera línea del código anterior se da nombre al problema, y en la segunda se escribe un texto a modo de comentario. En GAMS, cualquier línea que comienza con el símbolo (asterisco) se interpreta como un comentario. El comando Sets se emplea para definir dos estructuras típicas de GAMS: los índices, usados posteriormente para recorrer los vectores del problema, y los rangos de valores entre los que pueden variar estos índices. En el ejemplo propuesto, el índice i se refiere a los posibles productores p1 y p2. De igual manera, el índice j se refiere a los posibles consumidores de m1 a (representado por un asterisco) m3. 19
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Observaciones El comando Table permite definir matrices de datos (como puede ser la matriz de la Tabla de distancias en el ejemplo). Obsérvese la facilidad con que se pueden representar las tablas en GAMS. El comando Scalar es necesario en la declaración y asignación de escalares (como el escalar f en el ejemplo). El comando Parameters se utiliza para declaración y asignación de vectores de datos. En este ejemplo se emplean dos vectores: a(i) y b(j), que se refieren a la producción máxima, y a la demanda, respectivamente. La asignación mediante este comando se realiza para cada elemento del vector, por lo que es necesario especificar en primer lugar la posición del vector y en segundo, el valor a asignar. 20
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Observaciones Para declarar la matriz correspondiente al coste de transporte, c(i,j), también se utiliza el comando parameter, sin embargo, la asignación de los elementos se realiza posteriormente como función de otros datos. Las variables del problema de optimización se declaran mediante el comando Variables. Sólo cuando se completa la ejecución del código GAMS el optimizador determina el valor de estas variables. En GAMS se debe especificar el carácter de las variables, en este caso, se indica que x(i,j) es una variable positiva (no negativa). El comando Equations permite indicar el nombre con que se referenciará a las restricciones del problema, incluida la función objetivo. Tras el comando, aparece el nombre en primer lugar; si es necesario indicar que existen varias restricciones con la misma estructura, se indica seguidamente mediante el índice correspondiente entre paréntesis. Una vez declaradas las restricciones con este comando, se pasa a su definición colocando el símbolo.. y su formulación correspondiente en formato GAMS tras el nombre con el que se han declarado. Muchas funciones matemáticas se pueden emplear en la definición de las restricciones, como suma y multiplicación, entre otras. 21
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Observaciones El siguiente paso consiste en asociar un nombre al modelo y especificar qué conjunto de restricciones lo forman mediante el comando Model. En el ejemplo, el modelo se denomina transporte, y está formado por todas las restricciones previamente definidas (lo indica la palabra all). Por último, se emplea el comando Solve para que GAMS llame al optimizador (solver) pertinente que finalmente resuelve el problema (en el ejemplo, la palabra lp indica que se debe usar un optimizador para programación lineal). De manera opcional, se puede ordenar a GAMS que muestre el valor de los resultados más interesantes en un fichero de salida. Aquí, por ejemplo, el comando Display x.l tiene como objetivo mostrar el valor obtenido para el vector de variables x(i,j). Una vez que se ha escrito el código GAMS en el fichero de entrada, se compila; si no existen errores de sintaxis se resolverá el problema mediante el optimizador correspondiente y se escribirá la solución en un fichero de salida con extensión.lst. En este fichero, aquellos valores de la solución que son cercanos a cero se representan mediante EPS, y aquellos que son cero se denotan mediante un punto. 22
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Resumen de comandos 23
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. El poder del asterisco El asterisco puede utilizarse en GAMS en los siguientes casos: Hacer comentarios aclaratorios en el fichero de entrada. Aquellas líneas que contienen este símbolo en la primera columna son comentarios en GAMS. Definir conjuntos de índices de manera compacta. Esta función se explicó en el ejemplo. Indicar errores de compilación en el fichero de salida. Con cuatro asteriscos consecutivos se indica la línea que contiene errores. Indicar en el fichero de salida que las restricciones no lineales son infactibles para el punto inicial. En este caso, aparecen tres asteriscos al final de la formulación de la restricción afectada. Operador del producto * y de la potenciación **. 24
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Representar un conjunto comodín cuando se definen vectores, matrices, tablas, variables o restricciones. Este comodín tiene sentido si los índices que recorren dichas estructuras no guardan relación entre sí y, por tanto, no tiene sentido agruparlos en un conjunto. El siguiente ejemplo ayuda a comprender esta característica de GAMS. El poder del asterisco 25
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Resuelva y analice el siguiente problema Un productor fabrica una pieza, cuya demanda varía en el tiempo, de acuerdo con el gráfico de la siguiente figura: 26
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. El productor debe siempre atender la demanda mensual. En general, cualquier problema de planificación admitirá diversas posibilidades que aseguren que la demanda es convenientemente atendida. Existen dos posibilidades: 1. Producción variable. El fabricante puede producir cada mes el número exacto de unidades que le solicitan. Sin embargo, como una producción que varía es costosa de mantener, por los costos de horarios más largos en los meses de producción alta y los costes asociados al descanso del personal y la maquinaria en los meses de producción baja; este tipo de producción no es eficiente. 2. Producción constante. El fabricante que debe atender una demanda que cambia con el tiempo puede producir por encima de dicho nivel en periodos de baja demanda y almacenar la sobreproducción para los periodos de demanda mayor. Así, la producción puede mantenerse constante, compensando la demanda alta con la sobreproducción de periodos pasados. Sin embargo, debido a los costes de almacenamiento, tal opción puede no ser deseable si requiere costes altos de almacenamiento durante varios meses. 27
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. Nuestro objetivo es llevar a cabo una planificación de la producción que maximice los beneficios después de considerar los costes de las variaciones en la producción y los almacenes. Los cuatro elementos principales que intervienen en el problema de la planificación de la producción son: 28
ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. 29
Descargar ppt "ESCUELA POLITÉCNICA NACIONAL Dra. SANDRA GUTIÉRREZ P. INTRODUCCIÓN A GAMS Modelos de Programación Lineal Aplicados a la Economía."
Presentaciones similares Conceptos básicos de programación. Ordenador y periféricos Un ordenador solo es capaz de ejecutar ´órdenes y operaciones muy básicas, tales como: Aritmética.
PROBLEMA DE LA PRODUCCIÓN. La programación matemática es una técnica de modelización muy potente. Cuando se resuelve un problema hay que considerar las.
ALGORITMOS M.S.C. Ivette Hernández Dávila. Solución de problemas La mayoría de problemas tienen algunos elementos en común: un estado inicial; una meta,
Excel es un programa que permite la manipulación de libros y hojas de cálculo. En Excel, un libro es el archivo en que se trabaja y donde se almacenan.
1 ILOG OPL 3.7 Profesor: Julio Canales. 2 Introducción OPL es un lenguaje de programación, que es empleado en el software ILOG OPL STUDIO, el cual permite.
Clase Martes 28 de enero Notas de estructura de datos con lenguaje C ARREGLOS (ARRAYS) DE ESTRUCTURA Se puede crear un arreglo de estructuras tal.
1.1 Concepto de Complejidad de Algoritmos. 1.2 Aritmética de la notación O. 1.3 Complejidad Tiempo de ejecución de un algoritmo Complejidad.
Basado en: Sentencias de control Estructuras.

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 Resolución