general algebraic modeling system · gasolina, lubricante y combustible para aviones. las demandas...
TRANSCRIPT
General Algebraic Modeling
System
GAMS
Gabriela Hernández Luna
Temario1. ¿Qué es GAMS?
2. Instalación de GAMS
3. Modelo
4. Modelo de optimización
5. Estructura básica de modelo de optimización
6. Etapas de desarrollo de modelo
7. Método de optimización
8. Expresiones generales
9. Estructura básica GAMS
10. Análisis de grados de libertad
11. Ejemplos 3
¿Qué es GAMS?
GAMS (General Algebraic Modeling System) es un sistema de
modelado de programación matemática que permite resolver
problemas de optimización.
Emplea un lenguaje de alto nivel en un ambiente fácil de editar
(ambiente integrado de desarrollo) donde el usuario escribe la
formulación del modelo seguido de la selección y ejecución del
programa de solución.
Permite trabajar en diversas plataformas, UNIX, LINUX, etc. así como
también permite interrelación con otros lenguajes de programación.4
5
-T
T
T
T
Para trabajar con GAMS Disponer de una versión GAMS
www.gams.com
Limitaciones
Máximo número de filas 300
Máximo número columnas 300
Máximo número de elementos distintos de cero 2000
Máximo número de elementos no lineales 1000
Máximo número de variables discretas 50
6
-T
T
T
T
Es conveniente crear un proyecto mediante el menú File, Proyect,
New Proyect asignarle el nombre y guardarlo donde deseemos.
Posteriormente crear fichero, mediante el editor de GAMS,
eligiendo de la barra de Menú la opción file y de ésta new, y
aparecerá la siguiente pantalla
Instalación
7
-T
T
T
T
Una vez descargado el fichero de web, la instalación es muy
sencilla, casí automática: sólo hay que elegir el directorio donde
se instalará.
Finalizada la instalación, se accede al programa, desde ícono
creado o desde inicio de programas, obteniendo la siguiente
ventana
Instalación
Situaciones reservadas en GAMS
Los archivos en GAMS
tienen extensión *.gms
La solución de algún modelo,
se presenta en un archivo de
resultados en formato de texto,
con el mismo nombre del archivo
del código pero con extensión
*.lst 8
8
Modelo
9
Un modelo es una representación matemática simplificada de una
realidad compleja elaborado para facilitar la comprensión y
estudio de su comportamiento.
Es una herramienta que ayuda a la toma
de decisiones cuyos resultados deben ser
entendidos y útiles.
9
Modelos de optimización
10
Modelos donde existe un conjunto de variables de decisión que deben
maximizar/minimizar una función objetivo sometidas a un conjunto de
restricciones.
10
Función objetivo (of)
• Es la medida cuantitativa del funcionamiento del sistema que se deseaoptimizar (maximizar o minimizar).
Variables (v)
• Son las decisiones a tomar que influencian el valor de la función objetivo. Seclasifican en:
• Variables independientes (principales o de control)
• Variables dependientes (auxiliares o de estado)
Restricciones (st)
• Conjunto de relaciones, expresadas mediante ecuaciones o inecuaciones, que
ciertas variables están obligadas a satisfacer.
Optimizar consiste en encontrar el valor de una alternativa mejor, en
algún sentido, que las demás alternativas posibles.11
-T
T1
2
-T
T
T
Estructura de modelos de optimización
Etapas de desarrollo de un modelo
1. Identificación del problema
2. Especificación matemática y formulación
3. Resolución
4. Verificación, validación y refinamiento
5. Interpretación y análisis de resultados
12
-T
Etapas de desarrollo de un modelo
1. Identificación del problema
Colección de datos
Análisis de los mismos
Para hacer traducción e interpretación convertibles en
ecuaciones matemáticas13
-T
2
T
Etapas de desarrollo de un modelo
2. Especificación matemática y formulación
Escritura matemática del problema
Definición de variables, ecuaciones, función objetivo
y parámetros
Analiza el tamaño del problema
Analiza estructura de matriz de restricciones14
-T
2
T
T
Etapas de desarrollo de un modelo
3. Resolución
Implementar un algoritmo de obtención a la solución
numérica óptima o cuasi-óptima.
El tiempo de resolución depende cómo esté formulado
La solución debe ser suficientemente satisfactoria.
15
2
T
Etapas de desarrollo de un modelo
4. Verificación, validación y refinamiento
Eliminación de errores en codificación, conseguir que
el modelo realice las acciones especificadas incluso
comprobando validez de simplificaciones realizadas
16
Conocer detalle desempeño del modelo haciendo
análisis de sensibilidad, identificar soluciones
alternativas cuasióptimas pero atractivas
17
T
Etapas de desarrollo de un modelo
5. Interpretación y análisis de resultados
Optimización lineal
Optimización lineal entera mixta
Clásicos Optimización no lineal
Optimización estocástica
Métodos Optimización dinámica
de optimización etc.
Optimización evolutiva
Metaheurísticos Optimización simulada
Optimización multiagente
etc.
18
-T
T
T
T
De manera general los métodos clásicos buscan y garantizan un óptimo
local mientras que los metaheurísticos tienen mecanismos específicos para
un óptimo global (aunque su alcance no está garantizado)
Expresiones generales de algunos tipos de optimización
Como principales estructuras de programación tenemos disponibles en GAMS las siguientes:
19
𝐦𝐢𝐧 𝐜𝐓𝐱A x = b
x ≥ 0
x ∈ 𝑹𝒏 , c ∈ 𝑹𝒏 , A ∈ 𝑹𝒏 𝒙𝒎, b ∈ 𝑹𝒎
𝐦𝐢𝐧 𝐜𝐓𝐱 + 𝐝𝐓
A x + B y = b
x, y ≥ 0
x ∈ 𝒁𝒏, y ∈ 𝒁𝒏, c ∈ 𝑹𝒏 , 𝐝 ∈ 𝑹𝒍
A ∈ 𝑹𝒏 𝒙𝒎, B ∈ 𝑹𝒏 𝒙𝒎, b ∈ 𝑹𝒎
𝐦𝐢𝐧 𝐜𝐓𝐱A x = b
x ≤ 0 ≤ x
x ∈ 𝒁𝒏 , c ∈ 𝑹𝒏 , A ∈ 𝑹𝒏 𝒙𝒎, b ∈ 𝑹𝒎
20
Programación cuadrática
Quadratic prograamming
(QP)
Programación no lineal
Non linear prograamming
(NLP)
𝐦𝐢𝐧 f(x)
g(x) = 0
h(x) = 0
l ≤ 𝒙 ≤ 𝒖f : 𝑹 𝒏 → 𝑹g, h :𝑹𝒏 → 𝑹𝒏
𝐦𝐢𝐧 𝐜𝐓𝐱 + 𝟏
𝟐𝒙𝐓𝑸𝒙
A x = b
x ≥ 0
x ∈ 𝑹𝒏, A ∈ 𝑹𝒏 𝒙𝒎
Q ∈ 𝑹𝒏 𝒙𝒎, b ∈ 𝑹𝒎
21
Estructura básica en GAMS
Nombre del bloque Nombre en GAMS
Comentarios TEXT
Variables VARIABLES
Ecuaciones EQUATIONS
Modelo MODEL
Solución SOLVE
22
1. Líneas de comentarios
Líneas de comentarios.
- $ONTEXT, $OFFTEXT para párrafos
Ejemplo
$ONTEXT
Comentario 1
Comentario 2
Comentario 3
$OFFTEXT
- * para líneas aisladas. No acentuar ni usa ñ
Ejemplo
* Comentario en una sola linea
23
2. Bloque de variablesCabecera: VARIABLES .Nombre de variables: (hasta 63 caracteres alfanuméricos)
- una variable por línea (sugerencia) o todas seguidas en una línea
separadas por comas
- seleccionar un variable para la función objetivo sin restricción, sin ser positiva,
binaria
- colocar ; después de la última variable
Ejemplo:
Opción 1 x, y, z, F;
Opción 2 x variable 1
y variable 2
z variable 3
F función objetivo ;
24
2. Bloque de variablesClase de variables: (optativo).
- libres (FREE): valor por defecto - ∞, + ∞
- no negativas (POSITIVE) 0 , + ∞
- binarias (BINARY) 0, 1
- enteras positivas (INTEGER) 0, 1,…, 100
Ejemplo:
POSITIVE VARIABLES x, y;
Cotas sobre variables: (optativo)
- cota superior: Nom.UP = valor
- cota inferior: Nom.LO = valor
Ejemplo:
x.UP= 10; x.LO=3;
25
3. Bloque de ecuacionesAsignar nombre diferentes de las variables
- Cabecera: EQUATIONS
- Nombre de las funciones y restricciones: (máximo 8 caracteres)
- una línea o todas seguidas en una línea separas por comas
- después del último colocar ;
Ejemplo:
Opción 1: REST1, REST2, OBJ;
Opción 2: REST1 nombre de ecuación 1
REST2 nombre de ecuación 2
OBJ nombre de función objetivo (recomendado);
- Definición de funciones y restricciones- Una por línea y al final, colocar ;
- Signos de igualdad y desigualdad
- =E= para =
- =L= para ≤
- =G= para ≥
26
3. Bloque de ecuaciones
- Definición de funciones y restricciones- Signos de operaciones
+ para adición
- para diferencias
* para productos
/ para cocientes
** para potencias (con exponente entero)
Ejemplo
OBJ.. F=E= 2+4*x**2+y*z;
REST1.. 4*x+ 2*z =L=3;
27
4. Bloque de modelo
- Una línea única
- Necesario asignar nombre a modelo
- Declarar entre barras (/…. /) las ecuaciones que formarán parte del
modelo conocido.
En caso de incluir todas ecuaciones, incluir /ALL/.
Esto permite para una sola entrada de datos definir varios modelos y
resolvernos todos, en caso deseado, en una sola ejecución de GAMS.
Ejemplo
Opción 1: MODEL Problema1 /OBJ, RESTR1/;
Opción 2: MODEL Problema2 /ALL/;
28
5. Bloque de solución
- Una única línea con:- Palabra SOLVE
- Nombre del modelo (mismo usado en nombre del modelo)
- Tipo de problema precedido por palabra: USING: NLP, LP, MIP, RIMP, DNLP
- Dirección de optimización
- MAXIMIZING o MINIMIZING
- Nombre de la variable correspondiente a la función objetivo
- Finalizar con ;
Ejemplo:
SOLVE Problem1 USING NLP MAZIMING F;
29
Análisis de grados de libertad
- Para un sistema de M ecuaciones y N variables, el número de grados de
libertad, F, está dado por
𝐹 = 𝑀 −𝑁
Presentan tres casos
𝐹 = 0
Solución única 𝐹 ≥ 1
𝐹 0
Sistema factible de optimizarse
Sistema sobreespecificado
30
Ejemplo 01
Consideremos un problema de fabricación de sillas y escritorios, cuyo
modelo es
min 𝑧 = − 𝑥1 − 1.4 𝑥2𝑥1 + 𝑥2 ≤ 400𝑥1+ 2𝑥2 ≤ 580𝑥1 ≤ 300𝑥1 > 0
31
Ejemplo 01$ONTEXT
Problema de elaboración de sillas y escritorios
$OFFTEXT
o
*Problema de elaboración de sillas y escritorios
VARIABLES x1, x2, z;
EQUATIONS obj, rest1, rest2;
Obj.. z =E= -x1 – 1.4*x2;
rest1.. x1 + x2 =L= 400;
rest2.. x1 + 2*x2 =L= 580;
x1.UP = 300;
MODEL ejemplo /ALL/;
SOLVE ejemplo USING LP MINIMIZING z;
32
33
34
Ejemplo 02Caso del transporte.
Sean i fábricas de envasado, j mercados de consumo. Cada fábrica tiene
capacidad máxima de producción de 𝑎𝑖 cajas y cada mercado tiene una
demanda de 𝑏𝑖 cajas (se supone que la capacidad de producción total de las
fábricas es superior a la demanda total).
El coste de transporte entre cada fábrica i y cada mercado j por caja es 𝑐𝑖𝑗.
Se desea satisfacer la demanda de cada mercado al mínimo coste.
34
35
Ejemplo 02
Las variables de decisión serán las cajas transportadas en cada fábrica i, y cada mercado j, xij.
Las ecuaciones a satisfacer son:
Límite de capacidad máxima de producción de cada fábrica
𝑗 𝑥𝑖𝑗 ≤ 𝑎𝑖 para cada fábrica i
Satisfacción de demanda de cada mercado
𝑖 𝑥𝑖𝑗 ≥ 𝑏𝑗 para cada mercado j
La función objetivo será la minimización de los costes totales de transporte
𝑖 𝑗 𝑐𝑖𝑗 𝑥𝑖𝑗 ∀𝑖,𝑗
Ésta es la forma algebraica de representación de este problema de optimización.
36
Ejemplo 02
$TITLE MODELO TRANSPORTE
SETS
i fábricas de envasado /Toluca, Cuernavaca/
j mercados de consumo /León, Tlaxcala, Aguascalientes/
Existen tres formato de entrada de datos:
1.- Listas
2.- Tablas
3.- Asignaciones directas
37
Ejemplo 02
1.- LISTAS
PARAMETERS
a(i) capacidad de producción de la fábrica i (cajas)
/Toluca 350
Cuernavaca 700/
b(j) demanda del mercado j (cajas)
/ León 400
Tlaxcala 450
Aguascalientes 150/ ;
38
Ejemplo 02
2.- TABLAS
TABLE c(i, j) coste unitario transporte entre i y j (miles de $ por caja)León Tlaxcala Aguascalientes
Toluca 0.6 0.12 0.09
Cuernavaca 0.05 0.15 0.11
3.- ASIGNACIÓN DIRECTA
varb1 descripción /8.13/ ;
39
Ejemplo 02
VARIBLES
x(i,j) cajas transportadas entre fábrica i y mercado j (miles de $)
ct coste del transporte (miles de $)
POSITIVE VARIABLE
x
EQUATIONS
coste coste total del transporte (miles de $)
capacidad(i) capacidad máxima de cada fábrica i (cajas)
demanda (j) satisfacción de demanda de cada mercado (cajas)
40
Ejemplo 02
coste.. ct = E = SUM[(i, j), c(i,j) * x(i,j) ];
capacidad(i).. SUM [j, x(i,j) ] =L= a (i) ;
demanda(j).. SUM [i, x(i,j)] =G= b(j);
MODEL transporte /coste, capacidad, demanda/
SOLVE transporte USING LP MINIMIZING ct;
*Notación de producto (índice de sumatoria , sumandos)
41
Ejemplo 02
En cada variable o ecuación podemos apreciar cuatro columnas:
LOWER, LEVEL, UPPER y MARGINAL (contiene el valor de los
multiplicadores de las restricciones).
La columna LEVEL refleja el valor de cada variable optimizada (valor en la
solución).
La columna LOWER representa en valor de cota inferior de la variable en
cuestión.
La columna UPPER representa en valor de cota superior de la variable en
cuestión.
42
Ejemplo 03Una compañía petrolera construye una refinería para elaborar cuatro productos: diésel,
gasolina, lubricante y combustible para aviones. Las demandas de barriles por día son
14000, 30000, 10000 y 8000, respectivamente.
Debido a las cuotas de producción que especifica la OPEP, la nueva refinería puede
recibir al menos 40% de su crudo de Irán y el resto de Dubái. La empresa pronostica que
estas cuotas de demanda y de crudo permanecerán estables durante los 10 años
siguientes. Las especificaciones de los crudos son las siguientes
Rendimiento por barril Irán Dubái
diésel 0.20 0.10
barril de gasolina 0.25 0.65
barril de lubricante 0.10 0.15
barril de combustible para avión 0.15 0.10
43
Ejemplo 03Variables
𝑥1 = 𝑏𝑎𝑟𝑟𝑖𝑙𝑒𝑠 𝑑𝑒 𝑐𝑟𝑢𝑑𝑜 𝑑𝑒 𝐼𝑟𝑎𝑛𝑥2 = 𝑏𝑎𝑟𝑟𝑖𝑙𝑒𝑠 𝑑𝑒 𝑐𝑟𝑢𝑑𝑜 𝑑𝑒 𝐷𝑢𝑏á𝑖
Función objetivo
Minimizar la cantidad de barriles de crudo requeridos para satisfacer la demanda, z
Restricciones
0.20 𝑥1 + 0.10 𝑥2 ≥ 140000.25 𝑥1 + 0.60 𝑥2 ≥ 300000.10 𝑥1 + 0.15 𝑥2 ≥ 100000.15 𝑥1 + 0.10 𝑥2 ≥ 80000.60 𝑥1 − 0.4 𝑥2 ≥ 0
44
1. https://www.uv.es/mmocholi/CGyF/APUNTES-GAMS-CGYF.pdf
2. http://www.academia.edu/30336966/GAMS_ejemplos_introductorios
3. https://www.uv.es/~sala/CUADERN.pdf
Referencias
General Algebraic Modeling
System
GAMS
Gabriela Hernández Luna