40119931-AMPL

5/17/2018 40119931-AMPL - slidepdf.com

http://slidepdf.com/reader/full/40119931-ampl 1/29

UNIVERSIDAD

ANDRES BELLO

Clase Ayudantía 1VHerramientas complementarias para la resolución

de problemas de optimizaciónAMPL

Enmarcada en el curso deInvestigación de Operaciones I

Segundo Semestre de 2009

SANTIAGO DE CHILE - 2009

PROFESORA: PAMELA ÁLVAREZ M.AYUDANTE: IRVING CONTRERAS R.



IntroducciónLINGO como herramienta de resolución de problemas de optimización

AMPL: (A Modeling Language for Mathematical Programming) AMPL es un lenguaje demodelado algebraico para programación matemática capaz de expresar en notaciónalgebraica problemas de optimización tales como los problemas de programación lineal.

Es un lenguaje de programación especializado en la formulación de modelos deoptimización y programación matemática. Permite formular los modelos con notacióncomún y conceptos matemáticos familiares.

Además, AMPL resuleve distintos tipos de problemas de optimización (lineales, no lineales,enteros, cuadráticos, etc.) mediante solvers especializados para cada caso. Traduce laformulación del modelo matemático y los datos del problema a lenguaje de máquina, quees el que utilizan los solvers y el computador.

La gran potencia del lenguaje AMPL está en separar el modelo en sí por un lado y por otrolos datos particulares del problema concreto.



Componentes de AMPLElementos Componentes de AMPL en la construcción de un modelo

Lenguaje

AMPL

Archivo de Modelo.mod

Archivo de Datos.dat

Archivo de Instrucciones.run

SalidaResultados

SOLVER(Minos / CPLEX o NEOS Server)

archivo que contiene el modelode un problema.

archivo que contiene los datos delproblema.

Ejecuta comandos de AMPL, sirvepara incluir archivos de modelo ydatos, incluir otras opciones deconfiguración y de solver, etc.



Lenguaje AMPLCaracterísticas Generales del lenguaje de programación

AMPL permite además expresar tanto expresiones aritméticas y funciones matemáticas,tales como:

Expresiones Aritméticas: +, -, *, /, =, <, >, >=, <=, sum, min, max, prod

Funciones matemáticas: cos(x), sin(x), tan(x), acos(x), asin(x), atanh(x), exp(x), log(x), log10(x)

Además, posee AMPL posee algunas reglas léxicas de programación:

Cada línea de comentario debe comenzar con un #, varias líneas se delimitan por /* y */.

Cada línea de instrucción debe finalizar con un punto y coma (;)

AMPL considera que las letras mayúsculas y minúsculas son distintas



Lenguaje AMPL

s.a.

Entonces, como AMPL es un Lenguaje de Programación, debemos de considerar elcómo se declaran los elementos en este lenguaje:

Comando set:Define y declara un conjunto de elementos del problema

Comando param:Define y declara un conjunto de parámetos del problema

Comando var:Define las variables del problema

Comandos maximize o minimize:Se utiliza para declarar la función objetivo

Comando subjet to:Se utiliza para declarar las restricciones del problema

Características Generales del lenguaje de programación



Lenguaje AMPL

s.a.

Comando reset: resetea AMPL, limpia la memoria del programa para comenzar un nuevoproblema.

Comando model:se utiliza para ingresar el archivo de modelo al compilador AMPL.

Comando data:se utiliza para ingresas el archivo de datos al solver.

Comando solve:resuelve el modelo con el solver predeterminado (MINOS).

Comando options:se utiliza para cambiar algunas opciones de AMPL.

Comando display :se utiliza para ver los resultados después de resolver.




Imagen 1 - Ensayo de lenguaje de programación en AMPL

Comando set define los conjuntosde restricciones (Restr) y variables(Var)

Lenguaje AMPL

Comando param define losparámetros del modelo, quedependen de los conjuntos Restr y/o Var

Comando var define la variable X y,además, la especifica como no negativa

Se maximiza la función objetivollamada Total que es una suma.

Se declaran las restricciones delmodelo llamadas Restricciones consuject to. Hay tantas restricciones

como elementos en el conjuntoRestr, donde cada una es una suma.

Si no se desea utilizar un archivo dedatos, se pueden ingresar los datosabajo del comando data.

Primero, debe crear un documento en algún editor de texto, de sugerencia wordpad o notepadEscriba el archivo de datos y guardelo con la extensión .mod




Imagen 2 - Ensayo de lenguaje de programación en AMPL

Comando data para ingresarlos datos, no es necesario en elarchivo .dat

Lenguaje AMPL

Comando param declara losparámetros a utilizar en elproblema, enumerados de acuerdoa los elementos de los conjuntosdel problema.

Comando set declara y enumeracon nombre los conjuntos enarchivo .dat

Primero, debe crear un documento en algún editor de texto, de sugerencia wordpad o notepadEscriba el archivo de datos y guardelo con la extensión .dat




Lenguaje AMPL

- Extraer archivo amplcml.zip a un directorio conocido.

- Ejecutar sw.exe en windows o abrir línea de comando en DOS.

- El archivo de modelo y el archivo de datos deben estar en directorio AMPL.

Imagen 3 - Versión windows de sw.exe Imagen 4 - Versión DOS de sw.exe




Resultados del problema

El comando display se utiliza para visualizar los resultados:

Para ello, se puede ver el valor de la función objetivo, el valor de las variables yel valor de las restricciones con la siguiente sintaxis:

display nombre_función_objetivo;display nombre_variable;

display nombre_restricción;

Se puede ver información adicional para las variables y las restricciones con lasiguientes sintaxis:

display nombre_variable.sufijo_variables;display nombre_restricción.sufijo_restricción;

donde sufijo_variables puede ser, entre otras:

.init: valor inicial .ub: cota superior .rc: costo reducido

.val: valor actual .lb: cota inferior .slack: holgura

y el sufijo_restricción puede ser, entre otras:

.body : valor actual .ub: cota superior .dinit: valor inicial variable dual

.slack: holgura .lb: cota inferior .dual: valor actual variable dual




Solvers de AMPLCaracterísticas de los solvers para AMPL

CPLEX:Resuelve problemas lineales y no lineales cuadráticos,continuos o enteros. Utiliza Simplex, métodos de PuntoInterior y Branch and Bound.

DONLP2:Resuelve problemas de optimización no lineales. UtilizaAlgoritmo Secuencial Cuadrático y Dense-Matrix LinearAlgebra

LOQO:Resuelve problemas de optimización lineales y nolineales en variables continuas. Utiliza métodos de PuntoInterior

lp_solve:Resuelve problemas lineales y lineales enteros.

Minos:Resuelve problemas lineales y no lineales en variablecontinua. Utiliza Simplex Primal y Gradiente Reducidorespectivamente. SNOPT:Resuelve problemas lineales y no lineales en variablecontinua. Utiliza Simplex Primal y método secuencialcuadrático respectivamente.

Solvers de AMPL versión estudiantil

Solvers de AMPL versiones en internet



Ejemplo 1Problema desarrollado

Una compañía fabrica tres productos, P1, P2 y P3, que precisan para su elaboración dosmaterias primas, M1 y M2. Las disponibilidades semanales de estas materias son 25 y 30unidades, respectivamente.

El beneficio neto que proporciona cada unidad de producto, así como las unidades de

materia prima que necesita para su elaboración, vienen dados en la siguiente tabla:

P1 P2 P3

M1 1 2 2

M2 2 1 3

Beneficio(u.m.)

2 6 3

Planificar la producción semanal de forma que se maximice el beneficio.

Tabla 1 - Unidades de materia prima, producto y beneficio.



Resolución

Por ende el problema se resume en resolver el siguiente modelo:

s.a.

Problema desarrollado



Escritura en lenguaje AMPL

# FABRICACION DE 3 PRODUCTOS CON 2 MATERIAS PRIMAS

# VARIABLES DE DECISION Y RESTRICCIONES NO NEGATIVIDAD

var x1 >= 0;

var x2 >= 0;

var x3 >= 0;

# FUNCION OBJETIVO DEL MODELO

maximize z : 2*x1 + 6*x2 + 3*x3;

# RESTRICCIONES DEL MODELO

subject to restriccion1 : x1 + 2*x2 + 2*x3 <= 25;

subject to restriccion2 : 2*x1 + x2 + 3*x3 <= 30

Realizando la escritura en lenguaje AMPL, tenemos:

Imagen 5 - Programación Problema 1




Modelo general en AMPL

# MODELO: EJEMPLO1.MOD

# FABRICACION DE n PRODUCTOS CON m MATERIAS PRIMAS

# PARAMETROS DEL MODELO

param n >=0, integer;

param m >=0, integer;# CONJUNTOS DE INDICES

set PRODUCTOS := 1..n;

set MPRIMAS := 1..m;

# VARIABLES DE DECISION Y RESTRICCIONES NO NEGATIVIDAD

var x {j in PRODUCTOS} >= 0;

# MAS PARAMETROS DEL MODELO

param c {i in PRODUCTOS};

param b {j in MPRIMAS};

param a {(i,j) in {MPRIMAS,PRODUCTOS}};# FUNCION OBJETIVO DEL MODELO

maximize z : sum {j in PRODUCTOS} c[j]*x[j];

# RESTRICCIONES DEL MODELO

subject to restriccion {i in MPRIMAS} :

sum {j in PRODUCTOS} a[i,j]*x[j] <= b[i];

Ahora bien, AMPL nos permite la escritura del modelo general, en dondetenemos:

# DATOS: EJEMPLO1.DAT

param n := 3;param m := 2;

param c:=

1 2

2 6

3 3;

param a : 1 2 3:=

1 1 2 2

2 2 1 3;

param b:=

1 25

2 30;

Datos para nuestro caso:

Imagen 6 - Programación problema 1 como modelo general

Imagen 7 - Datos problema 1




AMPL PlusPlanteamientos gráficos de desarrollo de problemas

Imagen 8 - AMPL Plus for Windows



Servidor NEOSAMPL Servidor NEOS Online

AMPL Servidor Neos Online

Subir los archivos de modelo, dedatos y de instrucciones al Servidor

Neos en:

www-neos.mcs.anl.gov/neos/

Imagen 9 - Página principal de NEOS



Servidor NEOS

Listados de Solvers por tiposde problema

Por ejemplo:Combinatorial Optimization

Linear Network ProgrammingLinear Programming

Mixed Integer Linear ProgrammingMixed Integer NonlinearlyConstrained OptimizationNonlinearly Constrained

OptimizationUnconstrained Optimization

Etc.

Imagen 10 - Solvers de la página NEOS

AMPL Servidor NEOS Online



Servidor NEOS

Solvers disponibles para laprogramación lineal

Elija uno con AMPL imput, comoMOSEK

Imagen 11 - Solvers de programación lineal




Servidor NEOS

Solvers MOSEK

Para ingresar los datos, utiliceWWW Form

Imagen 11 - Descripción del Solver MOSEK




Servidor NEOS

Ingreso de modelo .MOD

Imagen 12 - Ingreso de datos

Ingreso del archivo dedatos .DAT

Ingreso de instrucciones.TXT opcional

Comentarios

Mail de contacto




Ejemplo de aplicación de NEOSProblema de transporte

Analicemos el problema de transporte:



Ejemplo de aplicación de NEOSCaracterísticas en la programación del modelo de transporte

Creamos el archivo Transporte.MOD

Imagen 13 - Ingreso de datos en transporte.mod



Ejemplo de aplicación de NEOS

Creamos el archivo Transporte.DAT

Imagen 14 - Ingreso de datos en transporte.dat

Características en la programación del modelo de transporte




Creamos el archivo Transporte.TXT

Imagen 15 - Ingreso de datos en transporte.txt

Características en la programación del modelo de transporte




Ingreso de modelo .MOD

Ingreso del archivo dedatos .DAT

Ingreso de instrucciones.TXT opcional

Comentarios

Mail de contacto

Imagen 14 - Ingreso de datos solver MOSIK

Características en la resolución en NEOS Online




Se obtiene un númerode trabajo y una

contraseña para poderacceder a los resultados

Imagen 15 - Obtención de datos en NEOS





Imagen 16 - Resultados obtenidos en NEOS




AMPLA Modeling Language for Mathematical Programming

Documents

40119931-AMPL