100% encontró este documento útil (1 voto)

333 vistas29 páginas

Introducción a AMPL para Optimización

Este documento presenta AMPL como una herramienta para resolver problemas de optimización. AMPL es un lenguaje de modelado matemático que permite expresar problemas de optimización en notación algebraica. Permite formular modelos y usar solvers especializados para resolver distintos tipos de problemas. El documento explica los componentes básicos de AMPL como archivos de modelo, datos e instrucciones, y características del lenguaje como declarar conjuntos, parámetros y variables. También presenta algunos solvers compatibles con AMPL.

Cargado por

atlontercero

Derechos de autor

Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.

Formatos disponibles

Descarga como PDF, TXT o lee en línea desde Scribd

100% encontró este documento útil (1 voto)

333 vistas29 páginas

Introducción a AMPL para Optimización

Cargado por

atlontercero

Derechos de autor

Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.

Formatos disponibles

Descarga como PDF, TXT o lee en línea desde Scribd

UNIVERSIDAD

ANDRES BELLO

Clase Ayudantía 1V
Herramientas complementarias para la resolución
de problemas de optimización
AMPL

Enmarcada en el curso de
Investigación de Operaciones I
Segundo Semestre de 2009

PROFESORA: PAMELA ÁLVAREZ M.

AYUDANTE: IRVING CONTRERAS R.

SANTIAGO DE CHILE - 2009

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

AMPL: (A Modeling Language for Mathematical Programming) AMPL es un lenguaje de

modelado algebraico para programación matemática capaz de expresar en notación
algebraica 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 de

optimización y programación matemática. Permite formular los modelos con notación
comú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 la
formulación del modelo matemático y los datos del problema a lenguaje de máquina, que
es 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 otro
los datos particulares del problema concreto.
Componentes de AMPL
Elementos Componentes de AMPL en la construcción de un modelo

Archivo de Modelo
.mod

archivo que contiene el modelo

de un problema.

Lenguaje
Archivo de Datos
.dat AMPL
archivo que contiene los datos del SOLVER
problema. (Minos / CPLEX o NEOS Server)

Archivo de Instrucciones
.run

Ejecuta comandos de AMPL, sirve

para incluir archivos de modelo y Salida
datos, incluir otras opciones de
configuración y de solver, etc. Resultados
Lenguaje AMPL
Caracterí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
Características Generales del lenguaje de programación

Entonces, como AMPL es un Lenguaje de Programación, debemos de considerar el

có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

s.a.
Lenguaje AMPL
Características Generales del lenguaje de programación

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

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.

s.a.
Lenguaje AMPL
Características Generales del lenguaje de programación

Comando set define los conjuntos

de restricciones (Restr) y variables
(Var)
Comando param define los
parámetros del modelo, que
dependen 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 objetivo
llamada Total que es una suma.

Se declaran las restricciones del

modelo llamadas Restricciones con
suject to. Hay tantas restricciones
como elementos en el conjunto
Restr, donde cada una es una suma.
Imagen 1 - Ensayo de lenguaje de programación en AMPL
Si no se desea utilizar un archivo de
datos, se pueden ingresar los datos
abajo del comando data.

Primero, debe crear un documento en algún editor de texto, de sugerencia wordpad o notepad
Escriba el archivo de datos y guardelo con la extensión .mod
Lenguaje AMPL
Características Generales del lenguaje de programación

Comando data para ingresar

los datos, no es necesario en el
archivo .dat

Comando set declara y enumera

con nombre los conjuntos en
archivo .dat

Comando param declara los

parámetros a utilizar en el
problema, enumerados de acuerdo
a los elementos de los conjuntos
del problema.

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

Primero, debe crear un documento en algún editor de texto, de sugerencia wordpad o notepad
Escriba el archivo de datos y guardelo con la extensión .dat
Lenguaje AMPL
Características Generales del lenguaje de programación

- Extraer archivo [Link] a un directorio conocido.

- Ejecutar [Link] 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 [Link] Imagen 4 - Versión DOS de [Link]

Resultados del problema
Características Generales del lenguaje de programación

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 y
el 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 la
siguientes 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 AMPL
Características de los solvers para AMPL

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

DONLP2:
Resuelve problemas de optimización no lineales. Utiliza
Algoritmo Secuencial Cuadrático y Dense-Matrix Linear
Algebra
Solvers de AMPL LOQO:
versión estudiantil Resuelve problemas de optimización lineales y no
lineales en variables continuas. Utiliza métodos de Punto
Interior

Solvers de AMPL lp_solve:

versiones en internet Resuelve problemas lineales y lineales enteros.

Minos:
Resuelve problemas lineales y no lineales en variable
continua. Utiliza Simplex Primal y Gradiente Reducido
respectivamente.

SNOPT:
Resuelve problemas lineales y no lineales en variable
continua. Utiliza Simplex Primal y método secuencial
cuadrático respectivamente.
Ejemplo 1
Problema desarrollado

Una compañía fabrica tres productos, P1, P2 y P3, que precisan para su elaboración dos
materias primas, M1 y M2. Las disponibilidades semanales de estas materias son 25 y 30
unidades, 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
2 6 3
(u.m.)
Tabla 1 - Unidades de materia prima, producto y beneficio.

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

Resolución
Problema desarrollado

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

s.a.
Escritura en lenguaje AMPL
Problema desarrollado

Realizando la escritura en lenguaje AMPL, tenemos:

# 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

Imagen 5 - Programación Problema 1

Modelo general en AMPL
Problema desarrollado

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

# MODELO: [Link]
# FABRICACION DE n PRODUCTOS CON m MATERIAS PRIMAS Datos para nuestro caso:
# PARAMETROS DEL MODELO
param n >=0, integer; # DATOS: [Link]
param m >=0, integer; param n := 3;
# CONJUNTOS DE INDICES param m := 2;
set PRODUCTOS := 1..n; param c:=
set MPRIMAS := 1..m; 1 2
# VARIABLES DE DECISION Y RESTRICCIONES NO NEGATIVIDAD 2 6
var x {j in PRODUCTOS} >= 0; 3 3;
# MAS PARAMETROS DEL MODELO param a : 1 2 3:=
param c {i in PRODUCTOS}; 1 1 2 2
param b {j in MPRIMAS}; 2 2 1 3;
param a {(i,j) in {MPRIMAS,PRODUCTOS}}; param b:=
# FUNCION OBJETIVO DEL MODELO 1 25
maximize z : sum {j in PRODUCTOS} c[j]*x[j]; 2 30;
# RESTRICCIONES DEL MODELO
subject to restriccion {i in MPRIMAS} : Imagen 7 - Datos problema 1
sum {j in PRODUCTOS} a[i,j]*x[j] <= b[i];