diapositivas programacion a parte ii

1

ESCUELA SUPERIOR POLITECNICA DEL LITORAL

INGENIERIA EN LOGISTICA Y TRANSPORTE

CURSO: PROGRAMACION MATEMATICA

(DIAPOSITIVAS GAMS)

Quito, EcuadorOctubre 2010

Guayaquil, EcuadorSeptiembre 2009

2

9. CODIFICACION DE PROBLEMAS DE OPTIMIZACION

Las principales alternativas (actuales) para el desarrollo de modelos de optimización (Sharda, 1995):

• Lenguajes de programación de propósito general (C, C++, Java, FORTRAN, Visual Basic) que llaman a una biblioteca de optimización: Se utilizan cuando el tiempo de resolución es crítico, o se necesitan interfaces a medida para entradas y salidas, cuando el modelo tiene que ser integrado a otras aplicaciones, etc. Desventajas: tiempo de desarrollo elevado, consumo de recursos para el mantenimiento del código.

• Lenguajes o entornos de cálculo numérico o simbólico (hoja electrónica, MATLAB, MATHEMATICA, etc) facilidad de uso, facilidad de presentar resultados. Desventajas: no inducen una buena práctica de programación, dificultad en la validación, mantenimiento del modelo.

3


Lenguajes Algebraicos de modelado (GAMS, AMPL, XPRESS): Son las alternativas más complejas y potentes por su capacidad de indexación de las variables y ecuaciones, permiten cambiar sin dificultad las dimensiones del modelo, de forma natural separan datos de resultados. Desde el punto de vista del modelador permiten la detección de errores de consistencia en la definición y verificación del modelo. Desde el punto de vista del usuario simplifican su mantenimiento.

GAMS: www.gams.comAMPL: www.ampl.com XPRESS: www.dash.co.uk

GAMS es el lenguaje mas ampliamente difundido comercialmente con su propia lista de discusión de usuarios: [email protected]

4

9. CODIFICACION DE PROBLEMAS DE OPTIMIZACIONLos lenguajes Algebraicos de modelado son lenguajes de alto nivel que han sido diseñados específicamente para el desarrollo e implantación de modelos de optimización de forma mas directa para los programadores y mas inteligible para los usuarios.

Ventajas:•Proporcionan una formulación sencilla de modelos grandes y complejos•Mejoran la productividad de los modeladores pues permiten dedicar más tiempo al diseño, ejecución del modelo y análisis de los resultados y menos tiempo a la codificación del mismo.•La formulación del problema es independiente del tamaño. Permiten el uso de la estructura del modelo para diferentes casos. Generalmente se desarrolla una maqueta (caso pequeño) y una vez depurado y verificado su validez se lo utiliza para resolver el problema real.•Permiten la realización de cambios en el modelo de una manera sencilla y segura.•Permiten la portabilidad de los modelos entre plataformas y sistemas operativos

5


Como única desventaja de los lenguajes Algebraicos de modelado se puede anotar las siguiente:

Desventaja:•No son adecuados para la resolución de problemas de tamaño pequeño por parte de usuarios esporádicos por la barrera de entrada que supone el aprendizaje de un nuevo lenguaje, en ese caso lo preferible sería el uso de SOLVER de Excel tiempo a la codificación del mismo.

Tendencias:•Interfaces de entrada y salida de datos más estrechamente relacionadas con las bases de datos y ERP’s.•Posibilidad de ocultar el código fuente produciendo versiones ejecutables para usuarios finales•Desarrollo de interfaces gráficas que faciliten al usuario la formulación visual.

6

9. CODIFICACION DE PROBLEMAS DE OPTIMIZACION• El modelador debe ir acompañado de un solver (optimizador), el cual

toma el modelo desarrollado en GAMS (u otro) y lo resuelve. Actualmente CPLEX es el optimizador más usado comercialmente, y una versión que soporta un número limitado de variables viene incluido en GAMS. Ultimamente se han producido avances significativos en los solvers, incluyendo nuevos métodos. Por ejemplo se observa una mejora global, de software y algorítmica de 1000 veces entre la versión de CPLEX de 1988 y la 7.0 del 2000. (como referencia, se estima que la mejora en el rendimiento del hardware ha sido del mismo orden de magnitud). Si se toman conjuntamente ambas mejoras hoy se pueden resolver en segundos problemas que habrían tomado una decena de años en resolverse (hace unos 14 años). (Nemhauser)

• Según expertos hoy es posible resolver un problema LP de 150.000 ecuaciones con 150.000 variables y 106 elementos no nulos en la matriz de coeficientes Tecnológicos en unas pocas horas.

7

10. Modelado en GAMSResolución de problemas de dimensiones pequeñas o medianas:

Sin una licencia válida GAMS opera en modo DEMO, o versión estudiantil, con las siguientes limitaciones:

• Número de restricciones: 300 • Número de variables: 300 • Número de elementos diferentes de cero: 2000• Número de variables discretas: 50

8

10. Modelado en GAMSRESOLUCION DE PROBLEMAS DE GRANDES DIMENSIONES:

• Existe un proyecto denominado NEOS (www.neos.mcs.anl.gov) que permite el envío de problemas de optimización escritos en GAMS a través de internet y estos son resueltos en servidores de la red devolviendo los resultados.

• Se puede crear el archivo con GAMS, y una vez creado (con todas las opciones necesarias) enviarlo vía WEB a la dirección:http://www-neos.mcs.anl.gov/neos/solvers/milp:XpressMP/GAMS.html.

Se trata de una página del NEOS Server que admite la posibilidad de resolver en sus computadores Sun Solaris los archivos que no es posible resolver con la versión estudiantil. Junto con el archivo hay que adjuntar una dirección de correo electrónico en donde recibir la resolución. Una vez resuelto se lo recibe en un archivo LST tal como se lo hubiera resuelto en un computador local.

9

Servicios en-línea

Inicialmente, los servicios de optimización en línea usaban como medio de comunicación protocolos de transferencia de archivos.

Actualmente, protocolos específicos y sistemas de envío (Web) son usados para la comunicación con los servidores.

Servidores académicos (NEOS) y comerciales.

Metacomputación: procesamiento distribuido

10

Optimización Cliente/Servidor

Cliente: un browser que envía problemas y recibe resultados.

Servidor: compilación y resolución de problemas

Limitaciones computacionales y de restricciones de seguridad imponen condiciones sobre la transferencia de parámetros.

11

Conclusión

WWW ofrece acceso remoto a servidores de solvers

Los sistemas cliente/servidor enfrentan varios desafíos.

Se tiende a servicios de modelación y optimización.

12

10. Modelado en GAMSRECOMENDACIONES PARA LA ESCRITURA DEL MODELO:

• MODULARIDAD: Estructurarlo en diversos módulos: la inclusión de datos (tal como son entendidos y recogidos) y la escritura de los resultados deben separarse en diferentes archivos que son convenientemente insertados mediante la instrucción $include en el módulo principal. Utilización de las entidades (parámetros, escalares, etc.) con el mismo propósito y significado en las diferentes partes del código.

• ESCRIBIR CODIGO: Es el primer paso en el desarrollo profesional de un modelo. El código debe ser limpio y claro para que pueda ser mantenido y ampliado. Mantener una coherencia en las reglas de escritura:- Indentación en las instrucciones repetitivas.- Sangría de 3 espacios cada vez que se usa una instrucción LOOP, IF- Las palabras reservadas del lenguaje van en mayúsculas: THEN, ELSE, SET, SCALAR, TABLE, LOOP, IF, etc.

13

10. Modelado en GAMSINSTALACION DE GAMS

• El programa GAMS (General Algebraic Modeling System) es un software desarrollado por A. Brooke, D. Kendrick y A. Meeraus. Este programa fue desarrollado a finales de la década de los años 80 en el World Bank por un grupo de economistas, aprovechando la experiencia de su trabajo sobre programas de desarrollo económico, que requieren en primer lugar una modelización exhaustiva y posteriormente la aplicación de los correspondientes programas de optimización para poder hallar la solución numérica a los modelos propuestos

• En el CD del curso, en la carpeta GAMS, subcarpeta INSTALADOR está la aplicación SETUP que instalará el programa GAMS-IDE v. 2.0.35.10. Una vez ejecutado hay que seguir las instrucciones, al finalizar le indica si tiene el archivo GAMLICE.txt (para copias registradas del programa en su versión profesional), hay que poner NO.

• También podemos acceder a la ultima versión de GAMS en la siguiente dirección: http://www.gams.com/download/. En esa pagina web (web site) es necesario registrarse con una dirección de correo electrónico. Una vez registrados se recibe una contraseña para poder acceder

14

10. Modelado en GAMS

GAMS: REFERENCIAS BASICAS

• Este programa permite muchas interrelaciones con otros lenguajes de alto nivel (Fortran, C etc., ), así como la aplicación de diversos algoritmos de resolución. En la actualidad se están desarrollando nuevas versiones de GAMS que permiten importar y exportar datos con hojas de cálculo, que son herramientas de uso muy común en las tareas informatizadas.

15

10. Modelado en GAMSGAMS: REFERENCIAS BASICAS

• Para poder ejecutar el programa GAMS es necesario crear un archivo de datos donde recoger toda la información necesaria del problema, aunque todo ello introducido en un formato particular. GAMS-IDE incorpora un editor que facilita la escritura y resolución de los problemas.

• En los archivos de modelos, hay que organizar una serie de bloques que son obligatorios y otros bloques que son opcionales.

• Nos centraremos primero en los bloques obligatorios, para revisar las instrucciones mínimas de funcionamiento de GAMS.

16


• Los bloques obligatorios son:Variables VARIABLESEcuaciones EQUATIONSModelo MODELSolución SOLVE

• Los bloques optativos son:Conjuntos SETDatos DATAVisualización DISPLAY

17

10. Modelado en GAMSGAMS: REFERENCIAS BASICASLíneas de comentario.

• En todos los ficheros que generemos siempre es conveniente introducir líneas de comentario que, si bien no forman parte del modelo y por lo tanto no van a ser compiladas, nos pueden facilitar la lectura posterior tanto del fichero de datos como el de la solución. Las líneas de comentarios pueden ser introducidas de dos formas distintas:

a) Comenzando cada línea con un asterisco (*), en este caso hay que tomar en consideración que ciertos símbolos están prohibidos, como por ejemplo los acentos, la letra ñ, etc.

b) Cuando hay que escribir varias líneas, para no tener que escribir cada vez un asterisco (*), es conveniente utilizar el comando $ONTEXT, a continuación de él podemos escribir tantas líneas como queramos y además utilizar cualquier carácter (acentos, ñ, etc.), para indicar que han finalizado las líneas de comentarios hay que utilizar el comando $OFFTEXT.

18


Bloque de variables.

• Este bloque debe comenzar con la palabra VARIABLES. Dentro de este bloque se han de definir las variables que se van a usar en el modelo, indicando de que clase son, que tipo de restricciones presentan, si tienen o no cotas y el punto de partida.

Bloque de ecuaciones.

• Este bloque ha de comenzar con el título EQUATIONS. En este bloque hay que declarar y definir las ecuaciones que se van a usar en el modelo.

19


Bloque de modelo.

• En este grupo se han de definir las ecuaciones que componen el modelo. No es obligatorio incluir todas las ecuaciones utilizadas. Este bloque tiene que comenzar con el nombre de MODEL.

Bloque de solución.

• En este bloque hay que indicar que tipo de algoritmo deseamos usar para poder resolver el modelo que se ha definido previamente. A la hora de inicializar este bloque ha de aparecer la palabra SOLVE.

20

10. Modelado en GAMS$ONTEXTSe trata de resolver vía gams el problema de la granja$OFFTEXT

VARIABLESC,L,Z;POSITIVE VARIABLESC,L;

EQUATIONSOBJ, TERRENO, HH, CEB;OBJ.. Z =E= 50*C+80*L;TERRENO.. C+L =L= 110;HH.. 4*C+8*L =L= 720;CEB.. C =L= 80;

MODEL GRANJA /OBJ, TERRENO, HH, CEB/;

SOLVE GRANJA USING LP MAXIMIZING Z;

21


Bloques Opcionales:

• Bloque de Conjuntos, SET. Consiste en definir una serie de conjuntos, por lo general índices y asignarles unos valores a estos conjuntos.

• Bloque de Datos, DATA. No se trata de un único bloque, sino que puede contener diferentes grupos. Se usa para definir una serie de datos fijos dentro del modelo, así podemos definir parámetros (PARAMETERS), tablas (TABLES) y escalares (SCALARS).

• Bloque de visualización, DISPLAY. Este bloque permite indicar la clase de salida de datos y formato que deseamos para el problema. En principio nos limitaremos a comentar la salida estándar (por defecto) que proporciona GAMS.

22

10. Modelado en GAMSGAMS: REFERENCIAS BASICASGRUPO SET

• Este bloque o grupo nos sirve para definir conjuntos, aunque lo normal es definir con él índices, tanto de variables como de restricciones.

• Como todos los grupos debe comenzar con el nombre del bloque: SET y a continuación definir el nombre y los elementos que lo forman. Por ejemplo:SET i /D1, D2, D3,D 4/

• O también podemos escribirlo con nombre de comentario:SET i Los cuatro depósitos

/ D1 Uio

D2 Gye

D3 Ambato

D4 Manta/

23


GRUPO SET• A veces, cuando hemos de introducir algunos elementos con nombres

comunes se pueden introducir con un asterisco entre el primer elemento y el último. Así el conjunto anterior de índices también lo podemos definir como:SETi /D1*D4/

• En determinados problemas pueden existir índices de longitud y elementos iguales, para estos casos no es necesarios definirlos dos veces. Así por ejemplo si los índices I y J son:SET I /1, 2, 3, 4/

J /1, 2, 3, 4/• podemos definir solo uno, y asociar los elementos de este conjunto a

otro conjunto mediante la declaración de un ALIAS. :SET I /1* 4/ALIAS (I,J).

24


GRUPO DATA• La introducción de los datos en los modelos es siempre una

fuente de errores, y por esto es muy importante ser cuidadosos en el manejo de los datos. Así que siempre es preferible introducir los datos de la forma más cómoda y fácil posibles, así como introducirlos una sola vez.

• Dentro del grupo DATA, podemos distinguir tres tipos de elementos: PARAMETER, SCALAR y TABLES

• El grupo PARAMETER suele estar asociado a vectores y sirven normalmente para indicar disponibilidades o requerimientos de los conjuntos sets.

25


GRUPO DATA• El grupo SCALAR se usa para declarar e inicializar los

parámetros de dimensión cero, es decir, que no están asociados a ninguna clase de conjuntos.

• El grupo TABLE proporciona una forma fácil de introducir los datos del problema lo habitual es trabajar con tablas de dos dimensiones, ya que en el caso de una dimensión estaríamos hablando de PARAMETER. Dentro de este bloque podemos distinguir tres tipos de tablas: tablas simples (dos dimensiones), tablas continuadas (tablas de dos dimensiones pero con ancho o largo mayor que una pantalla) y tablas de más de dos dimensiones.

26


GRUPO TABLE: tablas simples• Como podemos observar junto a la identificación de TABLE hemos

añadido el nombre correspondiente A seguido de los conjuntos que están incluidos en la matriz, en este caso los conjunto I y J. Pero en cualquier caso la primera fila contiene los nombres de los elementos del conjunto J, convenientemente espaciados mediante los tabuladores correspondientes.

27


GRUPO TABLE: tablas continuadas• Permite hasta 256, pero se debe usar solo las primeras 80 columnas o

menos. Cuando tenemos que incorporar tablas de grandes dimensiones, se pueden escribir todas las filas y las correspondientes columnas sin más que añadir el signo “+” a la izquierda de la columna de los nombres.

28


GRUPO TABLE: tablas de más de dos dimensiones

29


ANALISIS DE SENSIBILIDAD:Algunos SOLVERS (como CPLEX) han añadido a su versión demo el análisis de sensibilidad. Para poder obtener los resultados con este análisis, se debe definir el SOLVER por defecto de LP a CPLEX (haciendo dos veces click con el cursor sobre este solver). Luego en el archivo GMS se debe crear un archivo de opciones: nombre.OPTFILE = 1 y que se use un archivo nombre.DICTFILE = 4 para que guarde los nombres y la solución en el LST.

El archivo de opciones debe ser creado con el nombre: nombre del solver.OPT (en este caso sería CPLEX.OPT), que debe ubicarse en el directorio correspondiente,y debe contener las opciones para el análisis de sensibilidad, esto es:

objrng allrhsrng all

Que significa que queremos el análisis de sensibilidad de los coef. de la función objetivo y de los términos independientes.

30

10. Modelado en GAMSGAMS: REFERENCIAS AVANZADASGRUPO DISPLAY: Despliega en la tabla de resultados las variables que se indican, por ejemplo en el problema de la granja (el sufijo .l es válido para los valores óptimos, .m para los valores marginales o costos reducidos, .lo para la cota inferior, .up para la cota superior):

$title PROBLEMA DE LA GRANJA

VARIABLES

C,L,Z;

EQUATIONS

OBJ, TERR, HH, CEB;

OBJ.. Z =E= 50*C + 80*L;

TERR.. C+L =L= 110;

HH.. 4*C+8*L =L= 720;

CEB.. C =L= 80;

MODEL GRANJA /ALL/;


DISPLAY C.L, Z.L

$title PROBLEMA DE LA GRANJA

OPTION LIMCOL=0, LIMROW=0; $OFFLISTINGOPTION SOLPRINT=OFF;

VARIABLES

C,L,Z;

EQUATIONS

OBJ, TERR, HH, CEB;

OBJ.. Z =E= 50*C + 80*L;

TERR.. C+L =L= 110;

HH.. 4*C+8*L =L= 720;

CEB.. C =L= 80;

MODEL GRANJA /ALL/;


DISPLAY C.L, Z.L

31

10. Modelado en GAMSGAMS: REFERENCIAS AVANZADAS

ALGO MAS SOBRE EL GRUPO VARIABLES: • El momento de declarar variables con este comando también se puede

indicar su naturaleza, por ejemplo:Positive variable X;Binary variable Y;Integer variable T;

• También se puede indicar un intervalo [a,b] de variación para una variable X de la siguiente manera:

X.lo = a;X.up = b;

32


EXPRESIONES CONDICIONALES:

• El símbolo $ puede utilizarse en GAMS para condicionar las instrucciones (es equivalente a una sentencia IF-THEN-ELSE:(ver ejemplo de secuenciación de órdenes de trabajo)

Por ejemplo: Sum( (i,j,k) $ (condición), (expresión) );SUMA expresión SOBRE TODO (i,j,k) QUE VERIFICA condición

33


INCLUSION DE ARCHIVOS (comando $include): • Si el modelo consta de varias partes o módulos (datos, modelo, salidas),

se pueden reunir mediante este comando. Por ejemplo, los datos para alimentar el modelo pueden provenir de otras fuentes (hojas de cálculo, bases de datos, etc), para ello se debe usar el comando:

• $include ‘archivo.gms’• Lo que hace este comando es incluir al archivo cuyo nombre se

especifica justo en el punto en que aparece dentro del archivo que se está compilando.

• Lo clásico es hacer un programa GAMS que declare toda su estructura de conjuntos, parámetros, variables y ecuaciones en un archivo principal a compilar.

• Los datos pueden aparecer en otros archivos incluidos en el principal antes de invocar al SOLVER.

34

10. Modelado en GAMSGAMS: REFERENCIAS AVANZADASREPORTES EN ARCHIVOS EXTERNOS (comandos file, PUT):

• Gams puede enviar los resultados a archivos externos para que puedan ser usados por otros programas.

• Primero la instrucción file abre un archivo de salida, y luego el comando put escribe lo deseado en este archivo, en el formato que elija el usuario

• Mientras el comando DISPLAY trata automáticamente los índices de las variables, el comando PUT debe recorrer estos índices mediante estructuras iterativas.

• En el ejemplo de la granja generemos un archivo resultado, en el que se encuentren los valores óptimos de utilidad, cebada y lechuga y la variable dual de terreno con 2 decimales

35

10. Modelado en GAMSVARIABLESC, L, Z;

EQUATIONSOBJ FUNCION DE UTILIDADTER DISPONIBILIDAD DE TERRENOTRA DISPONIBILIDAD DE MANO DE OBRACOTA TERRENO DISPONIBLE PARA CEBADA;

OBJ.. Z =E= 50*C + 80*L;TER.. C + L =L= 110;TRA.. 4*C+8*L =L= 720;COTA.. C =L= 80;

MODEL GRANJA /ALL/;SOLVE GRANJA USING LP MAXIMIZING Z;

FILE RES /C:\RESULTADO.TXT/;

PUT RES;PUT "UTILIDAD DEL GRANJERO = " Z.L:8//;PUT "CEBADA = " C.L:5:2, " LECHUGA = " l.L:5:2//;PUT "MEJORA DE LA UTILIDAD POR CADA HECTAREA EXTRA DE TERRENO = " TER.M:5:2

36

GAMS: REFERENCIAS AVANZADAS

INSTRUCCIÓN LOOP

• Una ventaja de GAMS es la posibilidad de resolver varios problemas que tengan la misma estructura y que se diferencien en unos pocos datos, esto resulta sencillo usando la instrucción LOOP (bucle), por ejemplo en el problema de la granja, haciendo variar las cantidades de terreno apto para sembrar cebada en 20, 30, 35 y 40 hectáreas :


37

scalar m /40/;option limrow=0;option limcol=0;

VARIABLESC, L, Z;

EQUATIONSOBJ, TER, TRA, COTA;

OBJ.. Z =E= 50*C + 80*L;TER.. C + L =L= 110;TRA.. 4*C+8*L =L= 720;COTA.. C =L= m;MODEL GRANJA /ALL/;set k /1*4/;parameter t(k)/1 202 303 354 40/;parameter salida(*,k)OPTION SOLPRINT = OFF;loop (k, m = t(k); SOLVE GRANJA USING LP MAXIMIZING Z; salida("terreno disponible para cebada",k)=m; salida("Utilidad del granjero",k)=z.l; salida("hectareas de lechuga",k)=L.l);display salida;


38


GAMS: REFERENCIAS AVANZADAS

INSTRUCCIÓN LOOP

• Usando la instrucción LOOP (bucle), en el problema de la granja, hacer variar las cantidades de terreno que dispone el granjero en 110, 112, 115, 120 y 130 hectáreas, presentar en un archivo de salida una tabla con los siguientes resultados:

• Cantidades óptimas a sembrar de cebada y lechuga• Terreno sobrante• Cuánto estaría dispuesto a pagar en cada caso por cada hora de mano

de obra extra

39

10. Modelado en GAMSGAMS:PROGRAMACION ENTERA Y ENTERA MIXTA (BINARIA)

Como el problema de programación IP o MIP (problemas NP) es mucho mas complejo que un problema LP, los softwares no necesariamente reportan la solución óptima, sino sólo una buena solución factible (que satisfaga las restricciones), salvo en problemas pequeños, en los cuáles si se halla esta solución.

Esto significa que GAMS no es capaz de encontrar la solución optima?.

La respuesta es NO.

40


• GAMS como todo programa de uso "profesional" incorpora la opción de búsqueda de una solución "buena" en poco tiempo antes que la óptima usando muchos recursos, es decir, GAMS detiene el proceso de búsqueda en aquellas soluciones que difieran menos de un 10 por ciento de la mejor solución. Esto queda reflejado en el fichero LST

• Si se quiere encontrar una mejor solución (mas cercana al óptimo, o el óptimo mismo), solamente hay que incorporar la opción de que la tolerancia sea muy baja, por ejemplo un 0.00001 (0.001 por ciento). Para lo cual se debe poner (al inicio del programa):

• *DECLARACION DE MARGEN DE TOLERANCIA• OPTION OPTCR=0.00001;

41


• Ejemplo:La empresa FERCA, S.A., se dedica al envasado de fertilizantes para el suministro a sus clientes, debe determinar el plan de envasado de tres tipos de fertilizantes (tipo 1, 2 y 3). Estos tipos de fertilizantes se envasan en cajas con peso diferentes, a partir de tres componentes básicos (A, B y C). Los beneficios obtenidos por cada tipo de fertilizante son de 25, 30 y 35 unidades monetarias, respectivamente.Cada tipo de fertilizantes tiene una mezcla diferentes de componentes, así el tipo 1 requiere 10 kilos de componente A, 20 de la clase B y 18 de clase C. Para el tipo 2 los requerimientos son de 13, 22 y 20 kilos de cada uno de los componentes, mientras que para el tipo 3 los requerimientos son de 18, 20 y 24, respectivamente.La empresa dispone en el almacén actualmente de 2324 kilos de componente A, de 2550 de B y de 1568 de C.Con estos datos determinar el número de cajas de fertilizantes que la empresa puede suministrar al mercado de forma que se maximice su beneficio.

42


* FERCA, S.A.VARIABLES X1, X2, X3, F;INTEGER VARIABLES X1, X2, X3;EQUATIONSOBJ, R1, R2, R3;OBJ.. F=E= 25*X1 + 30*X2 + 35*X3;R1.. 10*X1 + 13*X2 + 18*X3 =L= 2324;R2.. 20*X1 + 22*X2 + 20*X3 =L= 2550;R3.. 18*X1 + 20*X2 + 24*X3 =L= 1568;MODEL ENT11 /ALL/;SOLVE ENT11 USING MIP MAXIMIZING F;

**** SOLVER STATUS 1 NORMAL COMPLETION**** MODEL STATUS 8 INTEGER SOLUTION**** OBJECTIVE VALUE 2345.0000

Solution satisfies tolerances.

MIP Solution: 2345.000000 (1 iterations, 0 nodes)Final Solve: 2345.000000 (0 iterations)

Best integer solution possible: 2351.666667Absolute gap: 6.666667Relative gap: 0.002843

LOWER LEVEL UPPER MARGINAL

---- VAR X1 . . 100.000 25.000---- VAR X2 . 77.000 100.000 30.000---- VAR X3 . 1.000 100.000 35.000---- VAR F -INF 2345.000 +INF .

43


•FERCA, S.A.OPTION OPTCR = 0.00001;VARIABLES X1, X2, X3, F;INTEGER VARIABLES X1, X2, X3;EQUATIONSOBJ, R1, R2, R3;OBJ.. F=E= 25*X1 + 30*X2 + 35*X3;R1.. 10*X1 + 13*X2 + 18*X3 =L= 2324;R2.. 20*X1 + 22*X2 + 20*X3 =L= 2550;R3.. 18*X1 + 20*X2 + 24*X3 =L= 1568;MODEL ENT11 /ALL/;SOLVE ENT11 USING MIP MAXIMIZING F;

**** SOLVER STATUS 1 NORMAL COMPLETION**** MODEL STATUS 1 OPTIMAL**** OBJECTIVE VALUE 2350.0000

Proven optimal solution.

MIP Solution: 2350.000000 (2 iterations, 0 nodes)Final Solve: 2350.000000 (0 iterations)

Best integer solution possible: 2350.000000Absolute gap: 0.000000Relative gap: 0.000000

LOWER LEVEL UPPER MARGINAL

---- VAR X1 . . 100.000 25.000---- VAR X2 . 76.000 100.000 30.000---- VAR X3 . 2.000 100.000 35.000---- VAR F -INF 2350.000 +INF .

44

10. Modelado en GAMSGAMS: PROGRAMACION ENTERA BINARIA 0-1IP (Knapsack P)

• Un excursionista debe determinar que objetos debe llevar consigo en la mochila para realizar una excursión de un día. Cada uno de los objetos tiene asociado un peso y una utilidad personal para el excursionista. Los objetos que puede llevar, así como su peso y utilidad son los que se recogen en la tabla siguiente:

OBJETO PESO UTILIDAD

LINTERNA 40 40

SACO 50 80

COCINA 30 10

MANTA 10 10

COMIDA 10 4

ROPA 40 20

VARIOS 30 60

Sabiendo que el peso máximo que puede llevar en la mochila es de 100. Determinar que objetos debe llevar nuestro excursionista en la mochila para que la utilidad de los objetos sea máxima.

DESARROLLAR EL PROGRAMA EN GAMS QUE LO RESUELVA

45

10. Modelado en GAMSGAMS: PROGRAMACION ENTERA MIXTA MIP

• Estudiemos un típico problema MIP, es decir, con variables binarias y continuas: el problema de localización de unidades logísticas:

• Una empresa tiene que servir seis zonas comerciales, con un máximo de cuatro fabricas. Las zonas comerciales y sus demandas (expresadas en unidades anuales de producto) son las siguientes:

ZONA DEMANDAGUAYAS 480NORTE 356NOROESTE 251ESTE 349CENTRO 598SUR 326

• La empresa tiene en la actualidad dos fábricas en funcionamiento, una de ellas esta situada en Guayaquil y tiene una capacidad productiva de 500 unidades/año, la segunda fábrica esta situada en Quito y tiene una capacidad productiva de 700 unidades/año.

46


• Las alternativas de inversión que se plantean en la empresa son las de ampliar las dos fábricas existentes o bien construir nuevas plantas en Portoviejo y/o Cuenca. Los costes variables de suministros cij, que comprenden tanto los costes de producción, de transporte y los de distribución en las zonas de demanda son los siguientes:Planta\Zona Guayas Norte Noroeste Este Centro Sur

Guayaquil 10 62 110 35 62 100

Portoviejo 62 10 63 63 40 83

Quito 62 40 60 35 7 54

Cuenca 35 63 96 10 35 67

Las diferentes fábricas tienen los costes anuales y los niveles de producción siguientes:

CAPAC ACTUAL AMPL CAPAC COSTO FIJO

Guayaquil 500 1000 100000

Portoviejo 1000 100000

Quito 700 1000 80000

Cuenca 1000 100000

47


Cual ha de ser la decisión que tome la empresa de manera que se satisfagan las demandas y el coste sea mínimo. (las tablas están en la carpeta clase)

DESARROLLAR UN PROGRAMA EN GAMS QUE RESUELVA ESTE PROBLEMA Generar un reporte con lo siguiente: ¿qué fabricas ampliar? Qué nuevas plantas construir? Cómo se debe realizar la distribución para satisfacer la demanda? Cuál es la producción que se debe realizar en cada fábrica? Cuáles serán estos óptimos si la demanda de la zona Norte cambia a 400,

500 y 600 unidades?

diapositivas programacion a parte ii

Documents