gams_ejem

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

slide 1:

GAMS ejemplos introductorios H´ ector Manuel Mora Escobar Marzo de 2009 hectormorayahoo.com El programa comercial Gams General Algebraic Modeling System es una herramienta de alto nivel para modelamiento y soluci´ on de problemas de optimizaci´ on y programaci´ on matem´ atica. Su p´ agina es www.gams.com. All´ ı se puede descargar un demo de Gams la gu´ ıa del usuario un tutorial ... Su calidad versatilidad y gran uso han hecho que se convierta en un est´ andar para la es- critura de problemas de optimizaci´ on. En NEOS servidor para problemas de optimizaci´ on www-neos.mcs.anl.gov la mayor´ ıa de los solucionadores “solvers” tienen como uno de los formatos predeterminados el de Gams. Es posible descargar e instalar Gams sin haber comprado la licencia pero funciona como un demodeusolibrequetienerestriccionesdetama˜ no. Paralamayor´ ıadelosejemplosacad´ emicos esm´ asquesuficiente. MuchasgraciasalosdirectivosdeGams. Losl´ ımitessuperioresdetama˜ no son entre otros: • N´ umero de restricciones y variables: 300. • N´ umero de elementos no nulos: 2000. • N´ umero de variables discretas: 50. Gams viene para muchas plataformas Windows Linux Solaris Mac ... 32 y 64 bits. A continuaci´ on hay indicaciones someras para los primeros pasos de Gams en Windows y Linux. 0.1 Windows EnWindows GamstieneunIDEambienteintegradodedesarrolloquepermite entremuchas cosas m´ as editar escribir el archivo y ejecutar Gams. Este archivo donde se escribe el prob- lema tiene extensi´ on .gms. El archivo .gms es de tipo ASCII y puede ser escrito con cualquier editor para este tipo de archivos Emacs Bloc de notas .... El editor del ambiente Gams tiene una gran ventaja resalta con diferente color las palabras espec´ ıficas de Gams. Tambi´ en desde el ambiente Gams se puede activar Gams mediante la tecla F9 o mediante el bot´ on de la barra de men´ u Run Gams. Gams mira el archivo .gms y si est´ a bien escrito resuelve el problema. Gams env´ ıa algunos resultados al ambiente y crea un archivo .lst donde est´ a la informaci´ on sobre la soluci´ on. Si en el archivo .gms hay errores entonces en el archivo .lst aparece una transcripci´ on del archivo .gms con numeraci´ on de los renglones e inmediatamente despu´ es de una l´ ınea err´ onea aparece algo semejante a 409 1

slide 2:

El valor 409 u otro valor es un c´ odigo de error. Un poco m´ as adelante en el archivo .lst aparece el significado de cada uno de los c´ odigos de los errores ocurridos. 0.2 Linux En Linux Gams no viene con ambiente integrado. El archivo .gms se puede escribir con cualquier editor de texto Emacs vi Kate ... . Para invocar Gams desde una ventana se da la orden gams archivo.gms Tambi´ en se puede dar la orden sin explicitar la extensi´ on gams archivo De nuevo se crea un archivo .lst donde est´ a el resultado bien sea la soluci´ on o bien infor- maci´ on sobre los errores de la misma manera que en Windows ver secci´ on anterior. 0.3 Un archivo expl´ ıcito de datos Los ejemplos de modelos en Gams de este documento est´ an muy lejos de ser exhaustivos con el n´ umero de temas o con la profundidad utilizada. El prop´ osito es explicar someramente algunos de los conceptos involucrados en un ejemplo. El lector interesado podr´ a encontrar informaci´ on mas amplia y precisa en la gu´ ıa del usuario de Gams. Consideremos un problema de fabricaci´ on de sillas y escritorios cuyo modelo sea: min z −x 1 −1.4x 2 x 1 +x 2 ≤ 400 x 1 +2x 2 ≤ 580 x 1 ≤ 300 x≥ 0. El archivo de datos en Gams puede ser el siguiente: problema de OL formulacion explicita VARIABLES x1 x2 z POSITIVE VARIABLES x1 x2 EQUATIONS obj restr1 restr2 obj.. z e -x1 - 1.4x2 restr1.. x1 + x2 l 400 restr2.. x1 + 2x2 l 580 2

slide 3:

x1.UP 300 MODEL ejemplo /ALL/ SOLVE ejemplo USING LP MINIMIZING z Supongamos que el archivo se llama ej01.gms. Al utilizar Gams ´ este producir´ a un archivo con los resultados llamado ej01.lst. • En el archivo anterior las palabras propias de Gams est´ an escritas en may´ usculas simple- mente por presentaci´ on pero no es necesario. • Algunas de estas palabras se pueden escribir en singular o plural SET o SETS VARIABLE EQUATION SCALAR PARAMETER • Si en la primera columna de una l´ ınea hay un asterisco ´ esta se considera como una l´ ınea de comentarios. • Las igualdades y desigualdades en las restricciones y funci´ on objetivo se escriben con e para l para≤ g para≥. • Las cotas inferiores y superiores se escriben utilizando .LO y .UP • Algunos de los procesos de soluci´ on previstos por Gams son: lp linear programming nlp nonlinear programming mip mixed integer programming rmip relaxed mixed integer programming minlp mixed integer nonlinear programming mcp mixed complementarity problems cns constrained nonlinear systems • Si en el archivo de resultados en el sitio donde deber´ ıa aparecer un valor vemos . esto quiere decir que el valor es 0.0. • En la definici´ on de las cotas no se usa e se usa simplemente . Las variables no tienen que llamarse x1 x2 etc. El nombre de una variable el identificador puede tener hasta 63 caracteres alfanum´ ericos letras o d´ ıgitos sin espacios. Aparentemente tambi´ ensepuedeutilizarelgui´ onbajo_peronopuedeserelprimercaracterdelidentificador. ONTEXT Problema de OL. Estos son renglones de comentarios. OFFTEXT VARIABLES Sillas escrit z 3

slide 4:

POSITIVE VARIABLES /ALL/ EQUATIONS obj madera m_obra obj.. z e sillas + 1.4escrit madera.. sillAs + escrit l 400 m_obra.. sillas + 2escrit l 580 sillas.UP 300 MODEL ejemplo /obj madera m_obra/ SOLVE ejemplo USING LP MAXIMIZING z Observaciones: • Gams no diferencia entre min´ usculas y may´ usculas pero por ejemplo el nombre “prin- cipal” de la primera variable ser´ a Sillas el primero que aparece. Las otras escrituras equivalentes se le asimilar´ an. • ONTEXT y OFFTEXT sirven para empiezo y fin de comentarios. Estas dos palabras deben empezar en la primera columna. • Cuando se define el modelo ejemplo es posible considerar todas las ecuaciones con ALL o explicitarlas todas una por una o solamente algunas de ellas. 0.4 Estructura de un modelo en Gams UnmodeloenGamsesunasucesi´ ondecomandosoenunciados“statement”enlenguajeGams. El orden no importa pero cualquier entidad variable par´ ametro ... debe ser declarada antes de ser usada. Es posible tener renglones en blanco y varios comandos en el mismo rengl´ on. Usualmente cada comando acaba con punto y coma. En el archivo de entrada .gms los comandos son: • SETS • Datos: PARAMETERS TABLES SCALARS. • VARIABLES : declaraci´ on y asignaci´ on de tipo. • Asignaci´ on de cotas y valores iniciales. • EQUATIONS: declaraci´ on y definici´ on. • MODEL y SOLVE. • DISPLAY opcional. En los modelos que siguen hay varios ejemplos de los comandos. 4

slide 5:

0.5 Un problema de transporte Consideremos un problema cl´ asico de transporte con 3 f´ abricas y 4 destinos. En la siguiente tabla est´ an los costos unitarios de transporte en miles de pesos las capacidades m´ aximas de producci´ on de cada f´ abrica y los pedidos o demandas de cada destino. 1 2 3 4 cap. max. Macondo 23 29 19 31 200 Cali 12 16 20 10 180 Faca 11 13 17 19 100 demanda 105 80 99 135 Usualmente el planteamiento de este problema se hace con las variables x ij i 1...3 j 1...4 que indican en n´ umero de unidades que van de la f´ abrica i al destino j. Denotemos por c ij los costos unitarios de transporte d j las demandas en los destinos y p i las capacidades m´ aximas de producci´ on en las f´ abricas. El modelo matem´ atico es: min z 3 X i1 4 X j1 c ij x ij 4 X j1 x ij ≤ p i i 1...3 3 X i1 x ij d j j 1...4 x ij ≥ 0 ∀ij. A continuaci´ on est´ an dos formulaciones del problema en Gams. La primera formulaci´ on es m´ as expl´ ıcita y no es estructurada. ONTEXT Problema de transporte formulacion NO estructurada. OFFTEXT VARIABLES x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x44 z POSITIVE VARIABLES x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 EQUATIONS obj f1 f2 f3 d1 d2 d3 d4 obj.. z e 1000 23x11 + 29x12 + 19x13 + 31x14 + 5

slide 6:

12x21 + 16x22 + 20x23 + 10x24 + 11x31 + 13x32 + 17x33 + 19x34 f1.. x11 + x12 + x13 + x14 l 200 f2.. x21 + x22 + x23 + x24 l 180 f3.. x31 + x32 + x33 + x34 l 100 d1.. x11 + x21 + x31 e 105 d2.. x12 + x22 + x32 e 80 d3.. x13 + x23 + x33 e 99 d4.. x14 + x24 + x34 e 135 MODEL transporte0 /ALL/ SOLVE transporte0 USING LP MINIMIZING z Esta segunda formulaci´ on aprovecha las facilidades algebraicas de Gams. ONTEXT Problema de transporte formulacion estructurada. OFFTEXT SETS i fabricas u origenes /Macondo Cali Faca/ j destinos /14/ PARAMETERS pi capacidad de produccion de las fabricas / Macondo 200 Cali 180 Faca 100 / dj demanda en los destinos / 1 105 2 80 3 99 4 135 / TABLE cij costo unitario entre una fabrica y un destino 1 2 3 4 Macondo 23 29 19 31 Cali 12 16 20 10 Faca 11 13 17 19 6

slide 7:

SCALAR k coeficiente para costos unitarios /1000/ VARIABLES xij numero de unidades de una fabrica a un destino z costo total de transporte POSITIVE VARIABLES x EQUATIONS costo costo total de transporte capacidadi capacidad en cada fabrica demandaj demanda en cada destino costo.. z e ksum ij cijxij capacidadi.. sumj xij l pi demandaj.. sumi xij e dj MODEL transporte /ALL/ SOLVE transporte USING LP MINIMIZING z DISPLAY x.l x.m • En la orden display para mostrar resultados x.l se refiere al valor “level” de las variables x x.m se refiere al costo reducido o valor marginal de las variables x. • PARAMETER sirve para definir arreglos en una dimensi´ on vectores. TABLE sirve para definir arreglos de dos o m´ as dimensiones matrices .... • Espermitido despu´ esdeunidentificadorconjunto variable ecuaci´ on par´ ametro tabla ... colocar texto explicativo. Por ejemplo pi capacidad de produccion de las fabricas El nombre del par´ ametro es pi. Lo que sigue es un texto explicativo. No debe tener m´ as de 254 caracteres. No debe tener tildes ni / ni comas ni s´ ımbolos raros o sea preferiblemente debe tener ´ unicamente letras d´ ıgitos y espacios. Por ejemplo no es correcto escribir toneladas/mes es preferible ton por mes. Sin embargo es posible tener un texto explicativo m´ as complejo si se coloca todo entre comillas sencillas o dobles. Por ejemplo cpi ’capacidad de produccion en ton/mes’ 0.6 Un problema de vigilantes Una compa˜ n´ ıa de vigilancia evalu´ o sus necesidades de vigilantes por periodos de 4 horas en un gran conjunto residencial de la siguiente manera: 7

slide 8:

Periodo Cantidad 2 a.m. a 6 a.m 84 6 a.m. a 10 a.m 48 10 a.m. a 2 p.m 37 2 p.m. a 6 p.m 35 6 p.m. a 10 p.m 32 10 p.m. a 2 a.m 30 Cada vigilante trabaja 8 horas al d´ ıa pero de manera continua. La compa˜ n´ ıa desea organizar la distribuci´ on de sus vigilantes de tal forma que el n´ umero total de vigilantes sea m´ ınimo. Plantee el anterior problema de OL. Variables: x 1 el n´ umero de vigilantes que empiezan su turno a las 2 x 2 el n´ umero de vigilantes que empiezan su turno a las 6 ... x 6 el n´ umero de vigilantes que empiezan su turno a las 22 Para hacer m´ as compacto el planteamiento denotemos por v 1 un dato el n´ umero m´ ınimo de vigilantes necesarios en el primer periodo 2 a 6 ... v 6 el n´ umero m´ ınimo de vigilantes necesarios en el sexto periodo 22 a 2. min z 6 X i1 x i x 1 +x 6 ≥ v 1 x i +x i−1 ≥ v i i 2...6 x≥ 0. El problema se puede escribir en Gams as´ ı: ONTEXT Problema de vigilantes formulacion estructurada. uso del simbolo pesos y ord OFFTEXT SETS i periodos /2-6 6-10 10-14 14-18 18-22 22-2/ PARAMETERS vi necesidad de vigilantes / 2-6 84 6-10 48 10-14 37 14-18 35 18-22 32 22-2 30 / 8

slide 9:

VARIABLES xi numero de vigilantes que empiezan su trabajo en el periodo i ntv numero total de vigilantes POSITIVE VARIABLES x EQUATIONS objetivo numVig1 numVigii objetivo.. ntv e sumi xi numVig1.. x’2-6’ + x’22-2’ g v’2-6’ numVigiiordi gt 1 .. xi + xi-1 g vi MODEL vigilantes /ALL/ SOLVE vigilantes USING LP MINIMIZING ntv DISPLAY x.l La soluci´ on es ---- 37 VARIABLE x.L numero de vigilantes que empiezan su trabajo 2-6 84.000 6-10 4.000 10-14 33.000 14-18 2.000 18-22 30.000 El s´ ımbolo que se puede leer como tales que permite tener restricciones u operaciones para elementos de un conjunto que cumplen cierta condici´ on. En el ejemplo anterior la restricci´ on numVigii se define ´ unicamente para los elementos del conjunto i tales que su ordinal es mayor que 1 es decir para los elementos de ordinal 2 ... 5. Tambi´ ensepuedehacerusandoels´ ımbolo --queconsideraunconjuntocomounalistacircular cuando se resta 1 al primer elemento se toma el ´ ultimo: ONTEXT Problema de vigilantes formulacion estructurada uso de -- FUNCIONA BIEN OFFTEXT SETS i periodos /2-6 6-10 10-14 14-18 18-22 22-2/ PARAMETERS vi necesidad de vigilantes / 2-6 84 6-10 48 9

slide 10:

10-14 37 14-18 35 18-22 32 22-2 30 / VARIABLES xi numero de vigilantes que empiezan su trabajo en el periodo i ntv numero total de vigilantes POSITIVE VARIABLES x EQUATIONS objetivo numVigi objetivo.. ntv e sumi xi numVigi.. xi + xi--1 g vi MODEL vigilantes /ALL/ SOLVE vigilantes USING LP MINIMIZING ntv DISPLAY x.l 0.7 Un problema de dieta Un ama de casa desea hacer un almuerzo equilibrado utilizando los siguientes productos: carne papashabichuelalecheyguayaba. Lospreciosporkilodeestosalimentossonrespectivamente: 700 80 250 70 y 80. Aqu´ ı estamos suponiendoque la lechese vende por kilos o lo que es aproximadamente lo mismo que un litro de leche pesa un kilo. La familia est´ a compuesta por 6 personas y cada persona debe consumir 800 calor´ ıas en el almuerzo. Para que la alimentaci´ on sea equilibrada debe estar compuesta idealmente de 25 de prote´ ınas 25 de grasas 50 de gl´ ucidos o carbohidratos. En la pr´ actica los porcentajes reales no deben diferir en m´ as de 5 de los porcentajes ideales. Estos porcentajes est´ an dados con respecto a la materia seca es decir sin tener en cuenta el agua contenida en los alimentos. Obviamente hay muchas m´ as condiciones que se deben tener en cuenta y aqu´ ı se hace una simplificaci´ on para facilitar el planteamiento del problema. En la siguiente tabla se expresa la composici´ on de cada alimento y su aporte cal´ orico. Se supone que fuera de proteina grasa y carbohidratos solamente hay agua con el porcentaje restante. Calor´ ıas Prote´ ınas Grasas Gl´ ucidos por kilo Carne 10 10 0 1300 Papas 2 0 20 880 Habichuelas 1 0 5 240 Leche 5 3 5 670 Guayaba 1 0 15 640 10

slide 11:

El ama de casa desea saber c´ omo organizar su mercado de tal forma que se cumplan las restricciones nutricionales y que adem´ as se minimice el costo. Las variables pueden ser: x i : cantidad de kilos del alimento i que hay que comprar para el almuerzo i 1...5 Para facilitar el planteamiento introduzcamos unos nombres unos valores intermedios y una variable adicional: c i costo de un kilo del alimentos i r j requerimiento ideal en porcentaje del componente j 1...3 u j r j −5 requerimiento m´ ınimo en porcentaje del componente j v j r j +5 requerimiento m´ aximo en porcentaje del componente j p ij porcentaje en el alimento i del componente j a i aporte cal´ orico de un kilo del alimento i s i P 3 j1 p ij porcentaje de materia seca en el alimento i y cantidad kilos de materia seca de los alimentos comprados. min z 5 X i1 c i x i 5 X i1 a i x i 6×800 5 X i1 0.01s i x i y 5 X i1 0.01p ij x i ≥ 0.01u j y j 1...3 5 X i1 0.01p ij x i ≤ 0.01v j y j 1...3 x≥ 0 Este modelo se puede escribir enGams as´ ı: ONTEXT Problema de dieta formulacion estructurada OFFTEXT SETS i alimentos /carn papa habi lech guay/ j componentes /prot gras carb/ VARIABLES xi peso en kilos del alimento i y peso de la materia seca en kilos 11

slide 12:

z costo del almuerzo POSITIVE VARIABLES x y TABLE pij porcentaje en el alimento i del componente j prot gras carb carn 10 10 0 papa 2 0 20 habi 1 0 5 lech 5 3 5 guay 1 0 15 PARAMETER rj requerimientos ideales de cada componente en porcentaje / prot 25 gras 25 carb 50 / ci precio de un kilo de cada alimento / carn 700 papa 80 habi 250 lech 70 guay 80 / aci aporte calorico de un kilo de cada alimento / carn 1300 papa 880 habi 240 lech 670 guay 640 / SCALAR k coeficiente para convertir a fraccion /0.01/ n numero de personas /6/ calp calorias por persona /800/ delta diferencia permitida en requerimientos /5/ PARAMETER pmsi porcentaje de materia seca de cada alimento pmsi sumj pij PARAMETER uj cota inferior para el porcentaje de j uj rj - delta PARAMETER vj cota superior para el porcentaje de j vj rj + delta 12

slide 13:

DISPLAY pms u v EQUATIONS obj funcion objetivo peso_ms peso materia seca calorias total de calorias reqminj requerimiento minimo reqmaxj requerimiento maximo obj.. z e sumi cixi peso_ms.. y e ksumi pmsixi calorias.. sumi acixi e ncalp reqminj.. ksumi pijxi g kujy reqmaxj.. ksumi pijxi l kvjy MODEL dieta /ALL/ SOLVE dieta USING LP MINIMIZING z DISPLAY x.l La soluci´ on es x 0.768 0 0 3.84 1.92 z 960. 0.8 Optimizaci´ on entera Consideremos el siguiente problema max z 8x 1 +11x 2 +6x 3 +4x 4 6.7x 1 +10x 2 +5.5x 3 +3.4x 4 ≤ 19 1 x j ∈01 j 1...4. Al resolver la siguiente relajaci´ on lineal max z 8x 1 +11x 2 +6x 3 +4x 4 6.7x 1 +10x 2 +5.5x 3 +3.4x 4 ≤ 19 x≥ 0 escrita en Gams as´ ı: ONTEXT Ejemplo de Cornuejols pag. 193 13

slide 14:

sin considerar integralidad de variables ni cotas superiores OFFTEXT VARIABLES x1 x2 x3 x4 z POSITIVE VARIABLES x1 x2 x3 x4 EQUATIONS obj restr obj.. z e 8x1 + 11x2 + 6x3 + 4x4 restr.. 6.7x1 + 10x2 + 5.5x3 + 3.4x4 l 19 MODEL pag193 /ALL/ SOLVE pag193 USING LP MAXIMIZING z La soluci´ on obtenida es x 2.8358 0 0 0 z 22.6866 muy diferente de lo esperado. Coloquemos ahora cotas superiores: ONTEXT Ejemplo de Cornuejols pag. 193 sin considerar integralidad de variables. OFFTEXT VARIABLES x1 x2 x3 x4 z POSITIVE VARIABLES x1 x2 x3 x4 EQUATIONS obj restr obj.. z e 8x1 + 11x2 + 6x3 + 4x4 restr.. 6.7x1 + 10x2 + 5.5x3 + 3.4x4 l 19 x1.UP 1 x2.UP 1 x3.UP 1 x4.UP 1 MODEL pag193 /ALL/ SOLVE pag193 USING LP MAXIMIZING z Se obtiene x 1 0.89 0 1 z 21.7900 que casi cumple con las restricciones de 1. Finalmente al escribir en Gams la informaci´ on sobre integralidad de las variables y diciendo que se trata de un problema MIP mixed integer programming ONTEXT ejemplo de Cornuejols pag. 193 con variables enteras. OFFTEXT 14

slide 15:

VARIABLES x1 x2 x3 x4 z INTEGER VARIABLES x1 x2 x3 x4 EQUATIONS obj restr obj.. z e 8x1 + 11x2 + 6x3 + 4x4 restr.. 6.7x1 + 10x2 + 5.5x3 + 3.4x4 l 19 x1.UP 1 x2.UP 1 x3.UP 1 x4.UP 1 MODEL pag193 /ALL/ SOLVE pag193 USING MIP MAXIMIZING z se obtiene x 0 1 1 1 z 20. El problema 1 no solamente es de optimizaci´ on entera tambi´ en es un problema de variables binarias. Entonces en Gams se puede escribir m´ as corto ONTEXT ejemplo de Cornuejols pag. 193 con variables binarias. OFFTEXT VARIABLES x1 x2 x3 x4 z BINARY VARIABLES x1 x2 x3 x4 EQUATIONS obj restr obj.. z e 8x1 + 11x2 + 6x3 + 4x4 restr.. 6.7x1 + 10x2 + 5.5x3 + 3.4x4 l 19 MODEL pag193 /ALL/ SOLVE pag193 USING MIP MAXIMIZING z Enlosproblemasdeoptimizaci´ on enteraesmuyimportantetenerencuentaunvalor producido por Gams se trata de Relative gap. Normalmente Gams no realiza un estudio exhaustivo del ´ arbol del m´ etodo de ramificaci´ on y acotamiento. Sea δ el valor absoluto de la diferencia relativa entre el mejor valor de z obtenido para un punto entero y el valor estimado del mejor valor posible de z. Gams se detiene cuando δ es menor que un valor predeterminado. Si en los resultados Relative gap es cero todo funcion´ o bien y el valor de x y z producidos por Gams son ´ optimos. Cuando el valor no es cero no hay seguridad sobre el resultado obtenido. En el ´ ultimo ejemplo de Gams el valor de Relative gap es cero y se obtuvo la soluci´ on. Consideremos un problema parecido a 1: max z 8x 1 +11x 2 +5x 3 +4x 4 6.7x 1 +10x 2 +5.5x 3 +3.4x 4 ≤ 19 2 x∈01 4 . Al resolverlo con 15

slide 16:

VARIABLES x1 x2 x3 x4 z BINARY VARIABLES x1 x2 x3 x4 EQUATIONS obj restr obj.. z e 8x1 + 11x2 + 5x3 + 4x4 restr.. 6.7x1 + 10x2 + 5.5x3 + 3.4x4 l 19 MODEL pag193 /ALL/ SOLVE pag193 USING MIP MAXIMIZING z se obtiene x 1 1 0 0 z 19 pero Best possible: 20.000000 Absolute gap: 1.000000 Relative gap: 0.052632 El valor 0.052632 1/20−1 deja dudas sobre el x obtenido. Entonces es mejor redefinir el par´ ametro OPTCR con un valor peque˜ no: ONTEXT Optimizacion con variables binarias. y definiendo OPTCR OFFTEXT OPTION OPTCR 0.0001 VARIABLES x1 x2 x3 x4 z BINARY VARIABLES x1 x2 x3 x4 EQUATIONS obj restr obj.. z e 8x1 + 11x2 + 5x3 + 4x4 restr.. 6.7x1 + 10x2 + 5.5x3 + 3.4x4 l 19 MODEL pag193b /ALL/ SOLVE pag193b USING MIP MAXIMIZING z As´ ı se obtiene x 1 1 1 0 z 20 soluci´ on ´ optima ya que el valor de Relative gap es cero. 0.9 Un ejemplo de optimizaci´ on estoc´ astica Tomado de BiL97. Un granjero cultiva trigo ma´ ız y remolacha en un terreno de 500 acres. El desea saber en el invierno cuantos acres dedicar a cada cultivo el a˜ no que viene. Para sus animales el necesita por lo menos 200 T toneladas de trigo y 240 T de ma´ ız. Si su producci´ on no es suficiente el puede comprar cada tonelada a US238 y US210 respectivamente. Si 16

slide 17:

sobra de su producci´ on el puede vender a US170 y US150 cada tonelada. Cada tonelada de remolacha la puede vender a US36 pero hasta un m´ aximo de 600 T. Por encima de esa cantidad cada tonelada la puede vender a 10. El costo total de cultivar un acre es de US150 US230 y US260 para trigo ma´ ız y remolacha. En un planteamiento determinista se conoce el rendimiento de cada cultivo en toneladas por acre: 2.5 3 y 20 para trigo ma´ ız y remolacha respectivamente. ¿Cu´ antos acres debe dedicar el granjero a cada cultivo para maximizar su beneficio Para facilitar el planteamiento y hacerlo m´ as general denotemos los datos de la siguiente manera: s i costo total de sembrar un acre con el cultivo i 123 v i precio de venta de una tonelada del cultivo i 123 ¯ v r segundo precio venta para una tonelada de remolacha c i precio de compra de una tonelada del cultivo i 12 d i necesidad o demanda en T del cultivo i 12 r i rendimiento en toneladas por acre del cultivo i. El problema se puede plantear ´ unicamente con las variables relativas al n´ umero de acres por cultivo pero puede ser m´ as claro si se introducen otras variables intermedias: x i n´ umero de acres dedicados al cultivo i 123 y i n´ umero de toneladas compradas del cultivo i 12 w i n´ umero de toneladas vendidas del cultivo i 123 ¯ w r n´ umero de toneladas de remolacha vendidas al segundo precio p i n´ umero toneladas producidas del cultivo i 123 z i ingreso por ventas de los tres cultivos z g gastos por siembra y compras max z z i −z g z i 3 X i1 v i w i +¯ v r ¯ w r z g 3 X i1 s i x i + 2 X i1 c i y i 3 X i1 x i ≤ 500 p i r i x i i 1...3 p i +y i −w i d i i 12 p 3 −w 3 − ¯ w r 0 w 3 ≤ 600 xyw ¯ w r ≥ 0 En Gams se puede esribir as´ ı: 17

slide 18:

ONTEXT ejemplo del granjero Birge Louveaux p. 4 modelo determinista OFFTEXT SETS i clase de cultivo /tr mz rm/ ji granos /tr mz/ PARAMETERS ri "rendimiento del cultivo en ton/acre" / tr 2.5 mz 3 rm 20 / si costo de siembra en dolares por ton / tr 150 mz 230 rm 260 / vi precio de venta de cultivos en dolares por ton / tr 170 mz 150 rm 36 / cj precio de compra de granos en dolares por ton / tr 238 mz 210/ dj requerimiento o demanda de granos en toneladas / tr 200 mz 240 / SCALARS at area total disponible en acres /500/ tmax tonelaje maximo de remolachas para primer precio /6000/ pr2 segundo precio de venta de la remolacha /10/ VARIABLES xi numero de acres sembrados con el cultivo i pi produccion en toneladas del cultivo i yj numero de ton compradas de grano j wi numero de ton vendidas del cultivo i wr2 num de ton de rem vendidas al segundo precio egr gastos o egresos ing ingresos 18

slide 19:

z beneficio total POSITIVE VARIABLES x y w wr2 EQUATIONS benef gastos ingresos requerj requerimiento del cultivo j produci produccion del cultivo j area remo benef.. z e ing - egr gastos.. egr e sumi sixi + sumj cjyj ingresos.. ing e sumi viwi + pr2wr2 produci.. pi e rixi requerj.. pj + yj - wj g dj area.. sumixi l at remo.. w’rm’ + wr2 e p’rm’ w.UP’rm’ tmax MODEL granjero /ALL/ SOLVE granjero USING LP MAXIMIZING z DISPLAY x.l p.l y.l w.l wr2.l z.l El resultado es: ---- 79 VARIABLE x.L numero de acres sembrados con el cultivo i tr 120.000 mz 80.000 rm 300.000 ---- 79 VARIABLE p.L produccion en toneladas del cultivo i tr 300.000 mz 240.000 rm 6000.000 ---- 79 VARIABLE y.L numero de ton compradas de grano j ALL 0.000 ---- 79 VARIABLE w.L numero de ton vendidas del cultivo i tr 100.000 rm 6000.000 ---- 79 VARIABLE wr2.L 0.000 num de ton de rem vendidas al segundo precio VARIABLE z.L 118600.000 beneficio total Enelmodeloestoc´ asticolosrendimientosnosondeterministas. Elgranjeropreveetresposibles 19

slide 20:

escenarios en funci´ on del tiempo de los ´ ultimos tres meses anteriores a la cosecha: rendimiento bajo medio y alto: alto medio bajo trigo 3 2.5 2 ma´ ız 3.6 3 2.4 remolacha 24 20 16 Estos valores los podemos denotar r ie rendimiento del cultivo i en el escenario e. El granjero cree que cada uno de los tres escenarios tiene una probabilidad de 1/3. Sean π i los valores de la tres probabilidades. Ahora se desea maximizar el valor esperado del beneficio. Es c´ omodo plantear el problema con variables semejantes a las anteriores pero todas salvo las x i tendr´ an un sub´ ındice adicional correspondiente al escenario: y ie w ie ¯ w r e p ie z i e z g e z e . max ζ 3 X e1 π e z e z e z i e −z g e z i e 3 X i1 v i w ie +¯ v r ¯ w r e e 1...3 z g e 3 X i1 s i x i + 2 X i1 c i y ie e 1...3 3 X i1 x i ≤ 500 p ie r ie x i i 1...3 e 1...3 p ie +y ie −w ie d i i 12 e 1...3 p 3e −w 3e − ¯ w r e 0 e 1...3 w 3e ≤ 600 e 1...3 xyw ¯ w r ≥ 0 En Gams: ONTEXT ejemplo del granjero Birge Louveaux p. 4 modelo estocastico representacion de escenarios OFFTEXT SETS 20

slide 21:

i clase de cultivo /tr mz rm/ ji granos /tr mz/ e escenarios para el rendimiento/ alto medio bajo/ TABLE rie rendimiento del cultivo segun escenario alto medio bajo tr 3 2.5 2 mz 3.6 3 2.4 rm 24 20 16 PARAMETERS si costo de siembra en dolares por ton / tr 150 mz 230 rm 260 / vi precio de venta de cultivos en dolares por ton / tr 170 mz 150 rm 36 / cj precio de compra de granos en dolares por ton / tr 238 mz 210/ dj requerimiento o demanda de granos en toneladas / tr 200 mz 240 / pre probabilidad de escenarios / alto 0.333333 medio 0.333333 bajo 0.333333 / / alto 0 medio 1 bajo 0 / SCALARS at area total disponible en acres /500/ tmax tonelaje maximo de remolachas para primer precio /6000/ pr2 segundo precio de venta de la remolacha /10/ VARIABLES xi numero de acres sembrados con el cultivo i pie produccion del cultivo i en el escenario e yje num de ton compradas de grano j en el escenario e wie num de ton vendidas del cultivo i en el escenario e 21

slide 22:

wr2e num de ton de rem vendidas al sdo precio en el escenario e egre gastos o egresos en el escenario e inge ingresos en el escenario e ze beneficio en un escenario zz beneficio esperado POSITIVE VARIABLES x y w wr2 EQUATIONS ben_esp ben_esce beneficio en un escenario gastose ingresose requerje requerimiento del cultivo j en un escenario producie produccion del cultivo i area remoe ben_esp.. zz e sume preze ben_esce.. ze e inge - egre gastose.. egre e sumi sixi + sumj cjyje ingresose.. inge e sumi viwie + pr2wr2e producie.. pie e riexi requerje.. pje + yje - wje g dj area.. sumixi l at remoe.. w’rm’e + wr2e e p’rm’e w.UP’rm’e tmax MODEL granjero /ALL/ SOLVE granjero USING LP MAXIMIZING zz DISPLAY x.l p.l y.l w.l wr2.l z.l zz.l Resultados: ---- 88 VARIABLE x.L numero de acres sembrados con el cultivo i tr 170.000 mz 80.000 rm 250.000 ---- 88 VARIABLE p.L produccion del cultivo i en el escenario e alto medio bajo tr 510.000 425.000 340.000 mz 288.000 240.000 192.000 rm 6000.000 5000.000 4000.000 ---- 88 VARIABLE y.L num de ton compradas de grano j en el escenario e bajo 22

slide 23:

mz 48.000 ---- 88 VARIABLE w.L num de ton vendidas del cultivo i en el escenario e alto medio bajo tr 310.000 225.000 140.000 mz 48.000 rm 6000.000 5000.000 4000.000 ---- 88 VARIABLE wr2.L num de ton de rem vendidas al sdo precio en el escenario e ALL 0.000 ---- 88 VARIABLE z.L beneficio en un escenario alto 167000.000 medio 109350.000 bajo 48820.000 ---- 88 VARIABLE zz.L 108389.892 beneficio esperado 0.10 El problema lockbox Tomado de CoT07. Una compa˜ n´ ıa de nivel nacional recibe cheques de todo el pa´ ıs. Por el correo mismo y por los tr´ amites bancarios transcurre un tiempo en d´ ıas entre el momento en que el cheque es recibido en la oficina de correo y el momento en que la compa˜ n´ ıa recibe en su cuenta el valor del cheque. Este tiempo de tr´ amite var´ ıa dependiendo de las ciudades. La compa˜ n´ ıa desea abrir algunas oficinas “lockboxes” para centralizar la recepci´ on de cheques. Supongamos que hay cuatro regiones R 1 R 2 R 3 y R 4 y que habr´ ıa oficinas centrales en cuatro ciudades C 1 C 2 C 3 y C 4 . Los tiempos de tr´ amite entre las regiones y las ciudades son: Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 10 6 Regi´ on 1 2 4 6 6 1200 Regi´ on 2 4 2 5 5 480 Regi´ on 3 6 5 2 5 1440 Regi´ on 4 7 5 6 3 720 En la ´ ultima columna aparece el promedio diario en millones de pesos de la suma total proveniente de cada una de las cuatro regiones. El manejo y administraci´ on anual de cada central es de 180 millones de pesos. Supongamos por facilidad que para calcular la p´ erdida de inter´ es por la demora en el cheque la tasa nominal es de 5 anual y que para estas cuentas todos los d´ ıa del a˜ no son h´ abiles. Supongamos adem´ as que como el n´ umero de d´ ıas es peque˜ no se puede usar la f´ ormula de inter´ es simple. Los cheques de una regi´ on se env´ ıan a una sola ciudad pero es posible enviar los cheques de dos regiones diferentes a la misma central. Se desea saber qu´ e centrales abrir y a qu´ e central se deben enviar los cheques de cada regi´ on. Consideremos las siguientes variables todas binarias: 23

slide 24:

• y j 1 si se abre la oficina central en la ciudad j y j 0 en caso contrario. • x ij 1 si los cheques de la regi´ on i se env´ ıan a la ciudad j. Sea n el n´ umero de d´ ıas en un a˜ no. Entonces la tasa diaria de inter´ es es 0.05/n. As´ ı por ejemplo si los cheques de R 1 se env´ ıan a C 2 entonces diariamente se dejan de ganar 1.200 ′ 000.000 0.05 n 4 Al hacer la cuenta para todo el a˜ no la p´ erdida es de n 1.200 ′ 000.000 0.05 n 4 240 ′ 000.000 As´ ı podemos construir una tabla donde est´ an los valores p ij de p´ erdidass anuales en millones de pesos. Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 Regi´ on 1 120 240 360 360 Regi´ on 2 96 48 120 120 Regi´ on 3 432 360 144 360 Regi´ on 4 252 180 216 108 min z 4 X i1 4 X j1 p ij x ij +180 4 X j1 y j 4 X j1 x ij 1 i 1...4 4 X i1 x ij ≤ 4y j j 1...4 x ij y j ∈01. La segunda restricci´ on quiere decir: si y j 0 entonces x 1j x 2j x 3j x 4j 0. ONTEXT problema lockbox Cornuejols p. 213-215 escritura estructurada OFFTEXT OPTION OPTCR 0.0001 SETS i regiones /r1r4/ j ciudades /c1c4/ TABLE pij perdida de intereses en millones c1 c2 c3 c4 24

slide 25:

r1 120 240 360 360 r2 96 48 120 120 r3 432 360 144 360 r4 252 180 216 108 SCALAR coc de una oficina central /180/ VARIABLES xij los cheques de la region ri van a la ciudad cj yj la central en la ciudad cj se abre z costo total en millones BINARY VARIABLES x y EQUATIONS costo funcion ojetivo salei lo que sale de una region llegaj lo que llega a una ciudad costo.. z e sum ij pijxij + cocsumj yj salei.. sum j xij e 1 llegaj.. sumi xij - 4yj l 0 MODEL lockbox /ALL/ SOLVE lockbox USING MIP MINIMIZING z 0.11 Subasta combinatoria Tomado de CoT07. En algunas subastas los elementos aparecen agrupados por paquetes no necesariamente disyuntos y la oferta que hace el posible comprador por cada paquete no es la suma de los precios de sus elementos puede ser mayor o menor. Sea M 12...m el conjunto de elementos. El subastador recibe n ofertas cada una es una pareja B j S j p j donde S j es un conjunto de elementos S j ⊆ M y p j es el valor propuesto por el posible comprador. El subastador desea saber cuales ofertas aceptar para maximizar los ingresos. Sea x j una variable que vale 1 si el subastador acepta la oferta j y vale cero en caso contrario. max n X j1 p j x j X j:i∈S j x j ≤ 1 i 1...m x j ∈01 j 1..n. Ejemplo: Sean 4 elementos y 6 ofertas 25

slide 26:

B 1 1 6 B 2 2 3 B 3 34 12 B 4 13 12 B 5 24 8 B 6 134 16 max 6x 1 +3x 2 +12x 3 +12x 4 +8x 5 +16x 6 x 1 +x 4 +x 6 ≤ 1 x 2 +x 5 ≤ 1 x 3 +x 4 +x 6 ≤ 1 x 3 +x 5 +x 6 ≤ 1 x j ∈01 j 1...6. En Gams ONTEXT Subasta combinatoria Cornuejols p. 213 OFFTEXT VARIABLES x1 x2 x3 x4 x5 x6 z BINARY VARIABLES x1 x2 x3 x4 x5 x6 EQUATIONS obj el1 el2 el3 el4 obj.. z e 6x1 + 3x2 + 12x3 + 12x4 + 8x5 + 16x6 el1.. x1 + x4 + x6 l 1 el2.. x2 + x5 l 1 el3.. x3 + x4 + x6 l 1 el4.. x3 + x5 + x6 l 1 MODEL pag213 /ALL/ SOLVE pag213 USING MIP MAXIMIZING z La soluci´ on es x 111000 z 21. REFERENCIAS Bil97 Birge J.R. Louveaux F. Introducci´ on to stochastic Programming Spinger New York 1997. CoT07CornuejolsG. TutuncuR. Optimization Methods in Finance CambridgeUniv. Press 2007. 26

authorStream Live Help