<r /

Breve introducción al programa AMPL

Jesús Sáez Aguado Departamento de Estadística e Investigación Operativa

Universidad de Valladolid

February 28, 2003

Parte I: Introducción

1 Introducción.

AMPL es un programa dirigido a la construcción y resolución de modelos de op­timización, fundamentahnente modelos de Programación Lineal, Programación Entera y Programación no lineal. A diferencia de otros programas parecidos, como LINGO, una vez definido un modelo en AMPL puede especificarse el cómo queremos resolverlo, lo que permite el diseño de muchos tipos de algoritmos, como bucles repetitivos, generación de columna.'>, planos de corte, relajación La­grangeana o descomposición. Simultáneamente existe una variedad muy grande de 'solvers' que pueden ser llamados desde AMPL, algunos de dominio público, lo que da una gran potencia y versatilidad al programa. Otro hecho a destacar e..'! la continua incorporación de mejoras y procedimientos recientes.

Para una descripción completa de los elementos básicos dellenguage la mejor fuente sigue siendo el libro

R. FOURER, D. M. GAY & B. W. KERNIGHAN AMPL, A Modeling Language for Mathematical Programming, The Scientific Press 1993.

Para una descripción de todas las mejora.'> que se han ido incorporando desde entonces, de los solvers disponible..'> y de otras muchas cuestione..<>, en las direcciónes Web siguientes: http:f fnetlib.bell-labs.comfcmfcsfwhatfampl/index.html http:f fwww.ampl.com

El programa AMPL consta fundamentalmente de la.'> siguientes componentes:

l. El procesador dellenguage AMPL, que corresponde al programa ampl.exe y que compila todos los ficheros y comandos. El procesador puede ser ejecutado en modo comando en una ventana de DOS, o bien puede ser ejecutado más cómodamente desde una ventana windows ejecutando el programa ~~·wimla•&f·

<

1

2. Los solvers, que son los algoritmos para resolver diferentes tipos de prob­lemas. La edición Standar AMPL Student for Windows puede ejecutarse con diferentes solvers, entre los que destacan CPLEX (para problema.'> de PL, PE y Rede..">) y MINOS (para problemas de PL y PNL), y tiene la limitación de hasta 300 variables y 300 restricciones. ·

Además de la versión Standar AMPL Student for Windows, h~ otras versione..<J como AMPL Plus para Windows, o versiones para Linux, Unix y otras platafor­mas.

Cuando se crean modelos con AMPL pueden aparecer los siguientes tipos de archivos:

Tipo de archivo .mod .dat .run .amp .qry .nl

Descripción Componentes del modelo Archivo de datos Comandos y scripts Proyecto (sólo para AMPL Plus) Archivo SQL para datos externos Archivo creado por AMPL

La forma más habitual de trabajar con AMPL es editar primero tre..'> ficheros, con extensiones .mod, .dat y .run contenien..-;· respectivamente, las compo­nentes del modelo, los datos en el formato AMPL, y los comandos que se van a ejecutar. Estos ficheros de texto pueden editarse y mantenerse con cualquier editor de textos, como el bloc de notas o cualquier otro editor de texto. Aunque muchos de los comandos que aparecen en el archivo .run podrían ser ejecutados manualmente en la ventana de comandos, es má..'> conveniente agruparlos en un archivo· o script con extensión .run, donde además pueden ir todo tipo de op­ciones, bucles repetitivos, etc.. Además de las tres ventanas de texto, es preciso tener activo el procesador de comandos o bien en una ventana de DOS, o más cómodamente de..">de una ventana windows en sw.exe.

2 Modelos explícitos de Programación Lineal

En e..">ta sección vamos a ver cómo se introducen ejemplos sencillos de Progra­mación Lineal de poca.<> variables, y cómo se ejecutan archivos de comandos para las sesiones iniciales de AMPL. En estos ejemplos los datos del problema, como los coeficientes de la función objetivo, las restricciones y del lado derecho, están incluidos en el modelo, por lo que no es preciso crear un archivo con los datos. Posteriormente veremos que es importante lograr la separaci6n completa del modelo de los datos.

Para definir un modelo de Prgramación Lineal se pueden usar las siguientes declaraciones, que deberán ir incluidas en un fichero con extensión .mod:

2

1 i

1

L

~ Declaración sat param var minimiza maximiza subjact to

Uso para definir un conjunto declaración de parámetro declaración de variable declaración de objetivo (minimizar) declaración de objetivo (maximizar) declaración de restricción

Un modelo de muy pocas variables puede ser introducido en AMPL de forma explícita con las siguientes consideraciones:

• Comentarios pueden ser añadidos desde el súnbolo # hasta el final de la línea.

• Al final de cada declaración o comando debe ir un punto y coma ;

• Cada variable debe ser declarada explícitamente (con la declaración var), así como su tipo o su,.c:; cotas.

• Cada restricción debe ser declarada explícitamente (con la declaración subjact to), ~es conveniente darle un nombre, inmediatamente antes de los dos puntos :..

• La función objetivo se introduce después de maximiza o minimiza, y también es conveniente darle un nombre.

#Ejemplo de un modelo de PL explícito con dos variables (modl.mod):

'• #Modelo de PL explicito var X>=0,<=15; var Y>=0,<=15;

x'\. 3.s H1"' o.( '{*::; '(S' ¡,{ ;¡ ~ o

maximize obj:20*X+30*Y; '¡-.f -··--"-.tJ4 ;: ~2)) y,P :e 0

, , subject to res1 :X+Y<=19; subject to res2:2*X+3*Y<=52; Yt-;.1o

U na sesión inicial para resolver el problema anterior podría consistir de los siguientes comandos: ~1

Q\'' \)~· reset;"

model ~\:modl.mod; MO~L C•.'\MOM. MOb )

option solver cplex; sol ve;' printf1 "\n Modelo mod1. Solucion optima\n"; displar obj; displl:\f X,Y;

j\')

?l'

El comando reset elimina de la memoria de AMPL el modelo y los datos presentes. El comando model envía al procesador el modelo especificado, y es preciso indicar todo'el camino donde esté el archivo correspondiente. A contin­uación se elige el solver con el comando option solver, dependiendo del tipo

3

de problema que vaya a resolverse. El comando sol ve llama al solver elegido y aplica el algoritmo correspondiente, obteniendose una solución óptima. Por último, con los comandos printf y display se envían mensajes de texto y se visualizan los valores de las variables. Con el comando display se pueden también visualizar otros valores asociados a las variables y a las restricciones, mediante el uso de sufijos. En las siguientes tablas aparecen los sufijos más habituale.."l para variables: '-

Sufijo .lb .ub .re .val

Interpretación Cota inferior Cota superior Coste reducido Valor actual

Y los sufijos para restricciones:

reset;

Sufijo .body .dual .slack

model c:\modi.mod;

Interpretación Valor actual de la expresión Variable dual o precio sombra Holgura

printf "\n\n***Modelo mod1. Componentesdel modelo***\n\n"; show; printf "\n***Modelo mod1. Modelo completo***\n\n"; expand; option solver minos; solve;

, printf "\n***Modelo mod1. Solucion optima***\n"; display obj; display X,X.rc;. display Y,Y.rc; display res1.body,res1.dual,res1.slack; display res2.body,res2.dual,res2.slack;

Estos comandos producen la siguiente salida, que puede ser guardada en un archivo para su posterior edición o exámen:

4

'~ ***Modelo mod1. Componentes del modelo***

variables: X y

constraints : res1 res2

objective: obj

***Modelo mod1. Modelo completo***

maximize obj: 20*X + 30*Y;

s.t. res1: X + Y <= 19;

s.t. res2: 2*X + 3*Y <= 52;

1-o( 3 • .f)+ 3<> (.1 !>)., f;l,_,Q

'2.0 (o)+ ~~ (\~ 1~) :o. sz.o Zo(S")+ !>o(~~)-= ~z.o

MINOS 5.5: optimal solution found. 2 iterations, objective 520

***Modelo mod1. Solucion optima*** obj = 520~

X = 3.5 X.rc = -3.55271e-15 ~'O

Y = 15 Y.rc = -7 .10543e-15 ~ 1:\

1 res1.body = 18.5 res1.dual = O res1.slack = 0.5

( . res2.body =52 res2.dual = 10 res2.slack = 7.10543e-15~o

\ t-J.,v\.¡-¡ fu;~ So\A.)Cit>t.JCS'

i S oL1.1 e\ o tJ es. A LTf:fLt>J/It;S !

5

Parte II: Ellenguage AMPL, elementos básicos

Normalmente los modelos tienen algún tipo de estructura que permite el uso de conjuntos, que generalmente son lo.<J conjuntos de índice..<; de un modelo. Esto facilita todas las declaraciones del modelo y .además per~ite la separación completa del modelo de los datos. En las siguientes seccioneS de esta parte II se describen los elementos fundamentales del lenguage AMPL, y cómo se introducen en AMPL los archivos .mod, .dat y .run, y en la parte 111, se aplica lo anterior a una serie de ejemplos sencillos de PL y otros tipos de modelos.

Conjuntos e índices

Conjuntos simples

El tipo más sencillo de conjunto está definido explícitamente mediante sus el­emento.<; como sucesión de caracteres. Así, podemos definir en el archivo .mod dos conjuntos mediante las declaraciones:

set productos; set maquinas;

Y en al archivo .dat especificar sus elementos mediante: ,set productos:=pl p2 p3 p4; set maquinas:=m1 m2 m3;

Esta forma de definición de conjuntos suele hacerse sólo para conjuntos pequeñ os, donde además se quiere conservar el nombre de los elementos. Los tipos de conjuntos más utilizados son los conjuntos de número..,, y generalmente van a corresponder a lo.'! conjuntos de índices de un modelo. Por ejemplo, para definir un conjunto de 12 elementos con nombre productos, basta doclarar:

set productos:=1 .. 12¡ ~ Aunque la anterior declaración es válida, es más conveniente declarar en el mod-elo: ,

param n; set productos:=1 .. n;

y entonces en el fichero de dato.<; especificar: param n: =12;

De esta forma se logra la separación efectiva del modelo de los datos. Cuando en la definición de un conjunto interviene un período distinto de 1, esto puede indicarse mediante la claúsula by, indicando el período. Por ejemplo, son equiv­alentes: set quinquenios:={1990,1995,2000,2005,2010,2015,2020}; set quinquenios :=1990 .. 2020by5;

Esta tíltima declaración puede ser sustituida por las siguientes más eficientes, aunque más largas:

• J.

,. param inicio integer; param final > inicio integer; param intervalo > O integer; set quinquenios := inicio .. final by intervalo;

Y posteriormente en el archivo de datos declarar: param inicio : = 1990; param final :=2020; param intervalo : = 5;

Operaciones sobre conjuntos

AMPL di'lpone de cuatro operadores para construir nuevos conjuntos a partir de otros ya existentes:

A union B union: o en A o en B A inter B intersección: a la vez en A y en B A diff B diferencia: en A pero no en B A symdiff B diferencia simetrica: en A o en B pero no en ambos

Otros operadores valen para examinar la pertenencia de elementos a conjunto..'! o la inclusión de conjuntos:

in pertenece wi thin contenido not in not within card

no pertenece no contenido cardinal /

Indicando expresiones sobre conjuntos

A veces, para: d~fi:nir parámetros, variables o restricciones es necesario introducir ' d' dF¡.:nc•o-F~~~os• l l d . P . 1 un m tce ummy que recorre os e ementos e un conJunto. or eJemp o, para

introducir cotas superiores sobre variables asociada.'! a un conjunto de productos, puede hacerse:

set productos; param cota{productos}>=O; o de forma equivalente param cota{j in productos}>=O; var X{j in productos}>=O,<=cota[j];

Notar gue todas la..'l declaraciones referentes a con,iuptos .. Y.~~on,l~_!la,~es.J,~ mientras que los índices de las variables o :earámetros van con corchetes X [j] , o cota[j~. A diferencia de los nombres de la..~bl;y'OtráS componentesndel modelo, los índices dummy tienen un alcance (scope) que termina en la misma declaración donde se introdujo. Por esto mismo puede volverse a usar el mismo índice en otra declaración.

Conjuntos de pares ordenados

En la mayoría de modelos aparecen matrices de datos, como Cij, o variables con dos índices, como Xij, donde i, j recorren ciertos conjuntos de índices. Para

7

definir estas componentes en AMPL se puede usar el conjunto de todos los pares, o producto cartesiano, de dos conjuntos, por ejemplo conjl y conj2, de las siguientes formas equivalentes:

{conj1,conj2}; {i in conj1,j in conj2}; conj1 cross conj 2;

Y para definir parámetros o varaibles con dos índices basta p&per: param costo{conj1,conj2}; " var X{conj1,conj2};

Conjuntos de n tuplas

De la misma forma que para pares, pueden definirse parámetros y variables con tres o más índices, definiendo primero los conjuntos simples y después el pro­ducto cartesiano. Así, si se han definido tres conjuntos con nombres productos, periodos y metodos, y queremos definir una variable con tres índices Xijt, ba..qta poner: var x{productos,periodos,metodos}>=O; y lo mismo para parámetros.

Parámetros y expresiones

Declaración de parámetros

Los dato..'! de un modelo son introducidos en éste mediante su declaración como parámetros. Para parámetros unidimensionales basta una declaración del tipo:

param n; param T;

Parámetros asociados a conjuntos se declaran poniendo en conjunto entre llaves, por ejemplo:

param demanda{plantas}; param costo{origenes,destinos};

E.'lta..'l declaraciones son equivalentes a: param demanda{i in plantas}; param costo{i in origenes,j in destinos};

Lo..'l parámetros asociados a conjuntos simples son los análogos de los vectores y los ~~r,'~ los a..qociados a pares de conjuntos corresponden a las matrices. Para acceder a un parámetro particular basta poner el índice o los índices entre corchetes, como en: demanda[i] o costo[i,jl. /

Expresiones aritméticas

Como la mayoría de los lenguages de programación, AMPL dispone de una serie de operadores aritméticos y lógicos, y una serie de funciones aritméticas/En la siguiente Tabla aparecen los operadores arimétícos con orden de precedencia creciente: /

8

" ~Estno usual tipo de operandos tipo de resultado + - less aritmético aritmético sum prod max min aritmético aritmético * 1 div mod aritmético aritmético + - (unario) aritmético aritmético -o** aritmético aritmético

Con estos operadores se pueden combinar números, parámetros y variables con las convenciones estandar sobre precedencias (en caso de duda es mejor poner paréntesis}. Los operadores más sencillos son los estandar de adición (+),sustracción(-), multiplicación(*), división(/) y exponenciación e- o**}. También puede usarse el operador div que devuelve el cociente truncado al dividir el operando de la izquierda por el de la derecha; el operador mod devuelve el resto de la división, y el operador less devuelve el operando de la izquierda menos el de la derecha si el resultado es positivo, y cero en otro caso.

Otra manera de construir expresiones aritméticas es aplicando funciones a otras expresiones. AMPL dispone de gran variedad de funciones como son las funciones aritméticas, las funciones de redondeo y la..'l funciones de números aleatorios. A continuación aparecen las funciones aritmética..'! más usuales:

abs (x) exp(x) log(x} loglO(x} max(x,y, ... ) min (x, y, ... ) sqrt(x}

y las funciones de redondeo:

valor absoluto, jxj exponencial, ex

logaritmo natural, loge(x) logaritmo común, loglo(x) máximo (2 o más argumentos) mínimo (2 o má.'l argumentos) raíz cuadrada

foil. ~~·d 1-\1.\ ceil(x) ceiling of x (nexfh.ígher integer); fil' floor of x (next lower integer), LxJ r~..dJt~-

~ru~

floor (x} precision (x, n) round(x, n} round (x) trunc (x, n) trunc (x)

x rounded to n significant decimal digits x rounded to n digits pa..'lt decimal point x rounded to an integer x truncated to n digits past decimal point x truncated to an integer

Por último, la..'l siguientes funciones u operadores actúan recorriendo un índice sobre los elementos de un conjuntos, y efectuando la operación corre­spondiente:

L._

1í

Operador sum prod

uso suma ~-+-4,, producto 'l?IA.¿., •. .,z '~*'~;,.

max máximo min mínimo

Para la construcción de modelos de optimización el má.'l utilizado es el op­erador sum, que suma cierta expresión cuando se recorre los elementos de un conjunto, y corresponde a 1&'> sumatoriS. en modelos matemáticos. Así, se pueden usar expresiones del tipo:

sum {i in plantas}capacidad[i]; sum {i in origenes, j in destinos}coste[i,j]*X[i,j];

En las expresiones con índices pueden aparecer tanto parámetr&~J como variables definidas en el conjunto correspondiente. De esta forma se definen en AMPL la función objetivo y las restricciones de los modelos de optimización como una simple traslación de l~ sumatori~ en los modelos genéricos o matemáticos. En la parte III de esta introducción ªe definen diferentes modelos de Programación Lineal usando fundamentalmente el operador sum. ~

Expresiones lógicas y condicionales

De un uso algo más avanzado son los operadores lógicos que aparecen en la siguiente tabla:

Estilo usual estilo alternativo if-then-else or 11 exists forall F1>1t. P..ll

and &;&; not < <= = <> > >= < <= == != > >= in not in

Restricciones sobre parámetros

tipo de operandos lógico-aritmético lógico lógico lógico lógico aritmético aritmético

tipo de resultado aritmético lógico lógico lógico lógico lógico aritmético

Cuando se declara un parámetro, tanto los sencillos como los asociados a un conjunto, se puede añadir una restricción sobre el parámetro para que AMPL rechace valores inadecuados de éste. Así, pueden declararse parámetros de la forma:

param T > 1 integer; param dem {plantas} > = O; param U{j in productos}>=L[j];

Otras veces es preciso introducir condiciones más compleja..'! sobre los datos. Esto se hace mediante la sentencia check. Por ejemplo, en los modelos para el problema del transporte se suele añadir la condición de que la suma de ofertas sea igual a la suma de demandas:

check:sum{i in origenes}oferta[i] = sum{j in destinos}demanda[j];

Si hay varias condiciones check, se puede dar un nombre a cada una de ellas. Notar que una condición check no es una restricción del modelo, e.."l sólo una comprobación de que los datos que se vayan a introducir verifican la condici6n.

9 10

.. Parámetros calculados

En la mayor parte de los modelos, los parámetros son datos, cuyos valores son especificados en el archivo de datos mediante : =. En algunas ocasiones hay parámetros que son calculados en el mismo modelo en función de otros parámetros. Así por ejmplo se pueden declarar:

param dem_total := sum { j in productos }dem[j]; param dist_corr {i in plantas} :=dist[i]*factor;

Variables, objetivos y restricciones

La.<s declaraciones fundamentales para definir un modelo son la.<s siguientes, ya vistas en la parte I:

Declaración set param var node are minimize maximize subject to

Uso para definir un conjunto declaración de parámetro declaración de variable declaración de nodo para los modelos de redes declaración de arco para los modelo..<s de redes declaración de objetivo (minimizar) declaración de objetivo (maximizar) declaración de restricción

Cuando se declara una variable, si no se especifica nada la variable es con­tinua y no tiene restricción de signo. Las restricciones de signo, las cota.<s sencillas y las restricciones de ser entera o binaria se especifican en la misma declaración, como en:

var X > = O, < = cota; var y >=0, integer; var delta binary; .

Cuando una variable está asociada a un conjunto la declaración puede hacerse en la misma línea, y así son equivalentes:

var X {productos}> = O; var X {j in productos}> = O;

Sin embargo, si en las restricciones sobre la variable interviene algún parámetro, hay que poner necesariamente la expresión con un índice:

var X {j in productos}>= O, < = cota[j]; A partir de la.'! variables y parámetros definidos, se pueden formar expre­

siones utilizando ~as funciones y operadores vistos. Estas expresiones forman parte de la función objetivo y las restricciones del problema. Como se vió en la parte I, la función objetivo se declara mediante maximize o minimize, seguido de un nombre, los dos puntos : ·y la expresión correspondiente. Así, puede definirse: minimize costo_total :sum{j in productos}costo[j]*X[j]; maximize beneficio: sum{i in plantas, j in productos}g[i,j]*x[i,j];

11

Las restricciónes se introducen con subject to, o abreviadamente s. t., seguido de un nombre, los dos puntos : y la expresión definiendo la re..<striccíón. Para restricciones asociadas a conjuntos es indispensable un índice, como en :

subject to res_cota{j in productos}:x[j] <= cota[j]; subject to tiempo{i in seccion}: ~·ilt" pedN~• Ullllf u te', :f't*x [j] <= total [t];

" Datos

Como se ha indicado en varias ocasione..<s, en AMPL es importante la distinción entre un modelo para un problema de optimización, y un conjunto de datos que definen un ejemplo específico de ese modelo. En las secciqnes anteriores hemos vistos cómo se definen modelos mediante las declaraciones de conjuntos, parámetros, variables, objetivos y restricciones. En esta sección veremos cómo se introducen datos para modelos sencillos, aunque existen formas alternativas más avanzadas de introducir datos de..'!de archivos externos, hojas de cálculo y bases de datos.

Los datos de un modelo son guardados en un archivo de texto con la extensión .dat, por ejemplo produ.dat, para ser leídos con el comando data mediante:

ampl: data produ.dat; Cuando AMPL lee datos, trata cualquier sucesión de espacios en blanco, ta

buladores y final de línea como un tínico espacio en blanco. De esta forma los datos son colocados en tabla.'! fáciles de ver y mantener. La asignación de datos se hace mediante : =, y al finalizar cualquier sentencia de declaración de datos debe figurar el punto y coma ; .

En el archivo de datos se especifican en primer lugar los conjuntos simple..'! que intervienen en el modelo, bien definiendo sus nombre..'! explícitamente o bien mediante un índice numérico. Así, son declaraciones válida.'!:

set productos :• p1 p2 p3 p4; set períodos:=ene feb mar abr may jun jul; set periodos:=1 .. 12;

Los parámetros de dimensión 1 son especificados con asignaciones como: param n:=15; pai.am T:=12;

Los datos de un parámetro definido sobre un conjunto se dan en forma de lista donde aparecen cada elemento del conjunto y a continuación valor del parámetro. Así, si en el modelo se han declarado set productos ; param coste{productos} > O;

se puede especificar:

set productos := p1 p2 p3 p4; param coste:=

p1 35 p2 22 p3 43

12

l

~· .. p4 29; ¡

También pueden usarse comas como separadores, de forma que la anterior asig­nación sería equivalente a:

param coste:= p1 35, p2 22, p3 43, p4 29;

Frecuentemente se tienen definidos varios parámetros sobre el mismo con­junto, como en:

param coste{productos}; param L{productos}; param U{j in productos}>=L(j];

En vez de dar valores a cada parámetro en una declaración distinta, como en

param coste:= p1 35 p2 22 p3 43 p4 29;

param L:= p1 100 p2 150 p3 150 p4 i80¡

param U:= pi 1000 p2 i500 p3 1200 p4 2000;

se puede hacer todo en la misma declaración:

param coste L U:= pi 35 iOO iOOO p2 22 150 i500 p3 43 150 1200 p4 29 i80 2000;

Los parámetros de dimensión dos se especifican de forma análoga. Lo vemos con el siguiente ejemplo, donde en el modelo se tienen declarados:

set PRODUCTOS; set RECURSOS¡ param a{RECURSOS,PRODUCTOS} >= O;

y en los datos se especifica:

13

set PRODUCTOS := p1 p2 p3 p4; set RECURSOS : = mi m2 m3; param a: pi p2 p3 p4:=

m1 i 1.5 2 1 m2 3 2 O 2 m3 2 0.5 3 1;

" Si la matriz tiene más columnas qu~ filas,_ a yeces~~~~odti._cirlB;> en forma traspuesta con la notación (tr) como en:

-·· . -~""'"~-----~"-·*'~~~--.--~.-----~~--.. ~----·-~--=~

param a (tr): m1 m2 m3 pi. 1 3 2 p2 1.5 2 0.5 p3 2 o 3 p4 1 2 i;

Comandos más utilizados.

Aunque no está completa, en la siguiente lista aparecen los comandos AMPL más utilizados, con una breve descripción:

Comando Descripción model Lee las declaraciones del modelo de un archivo data data Lee la.c; declaraciones de datos de un archivo sol ve Resuelve el modelo acual display Visualiza conjuntos, parámetros y variables print Para obtener salidas sin formatear printf Permite salidas de texto r include Incluye archivos externos option Para incluir opciones reset Elimina de memoria el modelo y los datos actuales drop Elimina restricciones resto re fix unfix let reset data update data for repeat while repeat until if then else problem expand show

Vuelve a activar restricciones Fija variables a los valores actuales Elimina la fijación Cambia el valor de parámetros Elinima de la memoria los datos actuales Actualiza datos cambiados con let Bucle de repetición sobre un conjunto Bucle de repetición mientras Bucle de repetición ha.c;ta Bucle condicional si-entonces-en otro ca.'!o Define un problema Expande el modelo actual Muestra las componentes del modelo

14

.. Algunos comandos ya han sido vi'ltos en la parte I, y pueden ser suficientes

para las sesiones iniciales de AMPL. En la parte IV se verá un uso más intensivo de este tipo de comandos y bucles, lo que permite el dio:reño de algoritmos y opcione.<J avanzadas para diferentes problemas de optimización.

Parte III: Modelos 1

Modelos de Programación Lineal.

Un modelo de producción con un único recurso.

Supongamos que hay n posibles productos a producir, un único recurso oon tma cantidad di"lponible b (por ejemplo el tiempo di"lponible para fabricación), y para cadaj=1, ... ,n se tienen los siguientes datos:

9J = ganancia por unidad del producto j Uj = cantidad máxima del producto j aj = tasa de producción del producto j, es decir Toneladas producidas en

una hora. El modelo matemático para este problema sería:

n Maximizar Z = 2: YJ Xj

j=l n

Sujeto a E (1/ai )xj ~ b j=l

O< Xj s ui ,j = 1, ... , n

El modelo en formato AMPL Prod.mod para este problema podría ser:

set P; param a {j in P}; param b; param g {j in P}; param u {j in P}; var X {j in P}>=O,<=u[j]; maximize ganancia: sum {j in P} g[j] * X[j); subject to tiempo:sum{jinP} (1/a(j)) * X[j) <= b;

Y un conjunto de datos (en el archivo Prod.dat) puede ser:

set P := p1 p2; param: a g u :=

p1 200 25 6000 p2 140 30 4000 ;

param b := 40;

Finalmente, el fichero de comandos más sencillo (en Prod.run) puede ser:

15

reset; model C:\Prod.mod; data C:\Prod.dat; option solver cplex; sol ve; display X.lb,X,X.ub,X.rc;

produciendo la siguiente salida en la ventana de comandos~" CPLEX 6.5.3: optimal solution; objective 192000 2 simplex iterations (O in phase I)

X.lb X X.ub X.rc := pl o: 6000 6000 4 p2 o! 1400 4000 o

Por último, el comando expand produce el modelo expandido siguiente:

maximiza ganancia: 25*X('p1'] + 30*X['p2']; s.t. tiempo: 0.005*X['p1']+0.00714286*X['p2'] <= 40; s.t. Limites['p1'): O <= X['p1'] <= 6000; s.t. Limites['p2']: O<= X('p2'] <= 4000;

Un modelo de producción con varios recursos.

Existen multitud de problemas de optimización que pueden englobarse en los término..'! de Análisis de Actividades u Optimización de Recursos, y que consti­tuyen el núcleo de los problemas clásicos de Investigación Operativa. Supong­amos que se tienen n actividades, para las que hay que determinar su nivel de actividad, y m recursos que limitan el nivel de la."l actividades. El ejemplo más común de actividades es la cantidad que se va a producir de ciertos productos. Para cada actividad (o producto) j = 1, ... ,n sea Xj la variable indicando su nivel de actividad (o cantidad producida), 93 la ganancia obtenida por unidad , lj el nivel mínimo y Uj el nivel máximo permitido; para cada recurso i=1, ... ,m sea bi > O la cantidad disponible; y para cada i,j sea aij la cantidad del recurso i necesaria para producir una unidad del producto j. Un modelo matemático para este problema sería:

r• Maximizar Í: 9jXj

j=l n

Sujeto a E ~jXj ~ bi, i = 1, ... , rn j=l

lj ~ Xj ~ Uj,j = 1, ... ,n Como ejemplo específico supongamos que van a procesarse 3 productos a

través de 3 operaciones diferentes. Los tiempos (en minutos) requeridos por unidad de cada producto, la capacidad diaria de la."l operaciones (en minutos), las cantidades mínimas y máximas y la."l ganancias por unidad fabricada de cada producto vienen en la siguiente tabla:

16

.. "

... '

Tiempo/u Cp.pacidad Operación Producto 1 Producto 2 Producto 3 tiA. 01 1 2 1 430 02 3 o 2 460 03 1 4 o 420 Cant..min 10 10 10 Cant..max 100 150 100 Ganancia/u 3 2 5

Los archivos con el moaelo y los daJos para AMPL podrían ser:

• Contenido del archivo recursos.mod:

set PRODUCTOS;

set RECURSOS;

pararn usos{RECURSOS,PRODUCTOS} >= O;

pararn rec~so_disponible {RECURSOS}>= O;

pararn beneficio {PRODUCTOS};

pararn cant..min {PRODUCTOS} >= O;

pararn cant..max {PRODUCTOS} >= O;

• var X {j in PRODUCTOS}>= canLminf.il, <= cant..maxfj];

maximize ganancia: sum {j in PRODUCTOS} beneficio[j] * XUJ;

' subject to tiempo {i in RECURSOS}:

sum {j in PRODUCTOS}usos[i,j]* XUJ <= recurso_disponible[i];

• Conteniddo del archivo recursos.dat: set PRODUCTOS := p1 p2 p3;

set RECURSOS := 01 02 03;

pararn usos: p1p2 p3 :=

01131

02 204

03 120;

pararn: beneficio cant..min cant..max :=

p1 310100

p2 210150

p3 510100;

pararn recurso_disponible:= 01 430 02 460 03 420;

Todas las salidas obtenidas con display o printf, o cualquier otra, pueden ser desviadas a un archivo de la forma habitual con > o > >. Así, con un comando display Trans>Trans.out; se envían los valores de las variables Trans al archivo Trans.out, de forma que si no existía se crea uno con e..'le nombre, y si existe uno

17

lo sustituye. Sin embargo con > > se añade la salida al final del archivo si ya existía.

Observar cómo pueden sacarse diferentes valores relacionados con las vari­ables y las restricciones. Así, para una variable con nombre X los valores X.lb, X, X.ub y X.rc indican, re..'lpectivarnente los valores de la cota inferior, el valor de X, la cota superior y el coste reducido. Mientras que para una restricción con nombre genérico Res, y de la forma lb <= Re..'l <= ub, las ca.p.tidade..'l Res.lb, Res.body, Res.ub y Res.dual indican, respectivamente la cota inferior, el valor tomado, la cota superior y el precio dual o precio sombra.

IAAXÍMi 2:-Aíl... ~ = 3X ,+ 2. )(._ r5X>

c.~.tt. x, + z. -¡.,.. +· "/.1> ~ +lo

3)(, + Z.}(J ~ 4~0

y: 1 ~~" 4.)<'t 4 4l.O

1 0L\t """•o ""\ ,;, ¡; " ¡ .~ ll o 1,.. ,f., V., t: 1 f''i', ,.,.~ .. f•s. e: \..,t:.J>

}0 !;:. "{ 'j /¡00 !. ~- f\ ""'?f

.r~

,.'L 1 ('

·~ p, ·'_(, '-.;; ¿

18

'! t--;.. .2: crx ~·

~.':\

~ ~·\ ~

• 1 \_. • l,_ 1 r, 7 '""j: (-."" Ct,.,J X 1 .. ' '¡ L l¡. '"

,r~

;: