Investigación de Operaciones I

Introducción a AMPL

Prof. Ing. Héctor F. Bonilla L.

1. ¿Qué es AMPL?

A Mathematical Programming Language

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.

Permite resolver 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.

2
Marco general de un generador de modelos

FORMULACIÓN DEL MODELO

MATEMÁTICO

ARCHIVO DEL ARCHIVO

MODELO DE DATOS

SOLUCIÓN Y
GENERADOR DE MODELOS (AMPL)
RESULTADOS

SOLVER MODELO
(CPLEX) ESPECÍFICO
(Archivo MPS)
2. ¿Cómo Opera AMPL?

Archivo de
Modelo

Lenguaje Solver
Archivo de (Minos / Cplex o
Datos
AMPL Neos Server)
Archivo de
Instrucciones

Salida
Resultados

4
3. ¿Cómo Obtener AMPL?

AMPL Línea de Comandos:

Versión estudiantil (limitada a 200 variables y 200
restricciones) disponible en:
[Link]

AMPL Servidor Neos Online

Subir los archivos de modelo, de datos y de instrucciones al Servidor
Neos en:
[Link]

5
 4. ¿Cómo Resolver un Problema Usando AMPL?

Archivo de
Modelo

Lenguaje Solver
Archivo de (Minos / Cplex o
Datos
AMPL Neos Server)
Archivo de
Instrucciones

Primero debemos escribir

tres archivos: Salida
Resultados
.mod
.dat
.run
6
4. ¿Cómo Resolver un Problema Usando AMPL?

Archivo de
Contiene los modelos (función objetivo y
Modelo
.mod
restricciones) a usar.

Archivo de
Datos Contiene los datos del problema.
.dat

Llama al modelo contenido en .mod y a los

Archivo de
datos contenidos en .dat, y configura opciones
Instrucciones
.run de entrada y salida

Todos estos archivos pueden ser escritos en cualquier editor de texto

(WordPad, NotePad, etc.)
7
 4. ¿Cómo Resolver un Problema Usando AMPL?

Archivo de
Modelo

Lenguaje Solver
Archivo de (Minos / Cplex o
Datos
AMPL Neos Server)
Archivo de
Instrucciones

Los archivos deben ser

escritos en el lenguaje Salida
apropiado Resultados

8
 4. ¿Cómo Resolver un Problema Usando AMPL?
Lenguaje AMPL

Max F(X)
s.a. gi( X )  bi i  I
Comandos de declaración de elementos del modelo enAMPL:

• set: Define y declara un conjunto de elementos del problema.

• param: Define y declara un conjunto de parámetros del problema.
• var: Define las variables del problema.
• maximize o minimize: Se utiliza para declarar la función objetivo.
• subject to: Se utiliza para declarar las restricciones del problema.

9
4. ¿Cómo Resolver un Problema Usando AMPL?
Lenguaje AMPL

Max  (Pit  Ci ) X it X it : Cantidad de producto i

producida en tiempo t
i t

Declaración de elementos del modelo en AMPL:

• set: Dos conjuntos: 1) Productos, 2) Tiempo
• param: Precio, definido sobre los conjuntos de Productos y Tiempo
Costo de venta, definido sobre el conjunto Productos
• var: Variable x definida sobre los conjuntos Productos y Tiempo
• maximize: Estamos maximizando
• subject to: No hay restricciones

1
0
4. ¿Cómo Resolver un Problema Usando AMPL?
Lenguaje AMPL
Expresiones aritméticas:
Existen muchas expresiones aritméticas que se pueden utilizar en el lenguaje
AMPL, algunos ejemplos …

+ = sum or o ||
- > min and o &&
* != max not o !
/ <= prod

Funciones matemáticas:
Existen muchas funciones matemáticas que se pueden utilizar en el lenguaje
AMPL, algunos ejemplos …

abs(x) acos(x) round(x) max(x,y,…)

cos(x) asin(x) exp(x) min(x,y,…)
sin(x) atanh(x) log(x) ceil(x)
tan(x) sqrt(x) log10(x) floor(x)
11
 4. ¿Cómo Resolver un Problema Usando AMPL?
Lenguaje AMPL
Reglas léxicas:

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

•Cada línea de comentario debe comenzar con un #, varias líneas se

delimitan por /* y */

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

distintas (case sensitive)

•Las constantes con punto decimal se escriben como en este

ejemplo: 1.23E-45

12
 4. ¿Cómo Resolver un Problema Usando AMPL?
Lenguaje AMPL
Otros comandos:
• reset: limpia la memoria de AMPL para comenzar un nuevo problema.
• model: se utiliza para ingresar el archivo de modelo al compilador AMPL.
• data: se utiliza para ingresar el archivo de datos al solver.
• solve: resuelve el modelo (el solver predeterminado es el MINOS).
• options: se utiliza para cambiar algunas opciones deAMPL.
• display: se utiliza para ver los resultados después de resolver.
• include: se utiliza para ejecutar un archivo de [Link]

13
4. ¿Cómo Resolver un Problema Usando AMPL?

Archivo de
Modelo

Lenguaje Solver
Archivo de (Minos / Cplex o
Datos
AMPL Neos Server)
Archivo de
Instrucciones

Una vez escritos los

archivos se resuelven Salida
usando el Solver Resultados
apropiado

14
 4. ¿Cómo Resolver un Problema Usando AMPL?
Se puede utilizar AMPL con distintos solvers de acuerdo a las características del
problema a resolver.

Solvers de AMPL versión estudiantil:

• 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.
• LOQO: Resuelve problemas de optimización lineales y no lineales en variables continuas.
Utiliza métodos de Punto Interior.
• LPSOLVE: Resuelve problemas lineales y lineales enteros.
• MINOS: Resuelve problemas lineales y no lineales en variable continua.
Utiliza Simplex Primal y Gradiente Reducido respectivamente.

Solvers del Servidor Neos:

El servidor Neos tiene una lista de solvers para resolver
todo tipo de problemas de optimización.

15
 4. ¿Cómo Resolver un Problema Usando AMPL?

Archivo de
Modelo

Lenguaje Solver
Archivo de (Minos / Cplex o
Datos
AMPL Neos Server)
Archivo de
Instrucciones

Una vez resuelto el

problema se obtienen
resultados e información Salida
adicional (como la Resultados
necesaria para análisis de
sensibilidad)

16
4. ¿Cómo Resolver un Problema Usando AMPL?

¿Cómo ver los resultados del problema?

• Comando display se utiliza para visualizar los resultados.

• 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;

• Comando show se utiliza ver los nombres de variables, parámetros, etc.

17
4. ¿Cómo Resolver un Problema Usando AMPL?

¿Cómo ver los resultados del problema?

•Se puede ver información adicional para las variables y las restricciones
con la siguiente 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
18
 4. ¿Cómo Resolver un Problema Usando AMPL?

¿Cómo configurar las opciones?

• Comando para cambiar el Solver utilizado por AMPL y sus opciones:

option solver nombre_solver; # Cambia solver utilizado porAMPL.

option nombre_solver_options ‘opción=XX’ # Cambia opciones de solver utilizado.

• Comando para activar/desactivar el presolve:

option presolve 0; # desactiva presolve

option presolve 1; # activa presolve (predeterminado)

Nota: El presolve es un algoritmo que busca reducir el n° de re stricciones o el n°

de variables, cuando se pueda, para reducir el tamaño del problema original.

19
 4. ¿Cómo Resolver un Problema Usando AMPL?

¿Cómo configurar las opciones?

• Comando para activar/desactivar información estadística:

option show_stats 0; # desactivar (predeterminado)

option show_stats 1; # activar

Nota: Activado muestra más información sobre el número de variables y

restricciones del problema.

• Comando para activar/desactivar display de variables con valor cero:

option omit_zero_rows 0; # desactivar (predeterminado)

option omit_zero_rows 1; # activar

Nota: Si está activado omite mostrar variables con valor cero.

20
 5. Ejemplo
1. Crear documento de texto en Notepad o Wordpad.
2. Escribir archivo de modelo y guardar con extensión .mod

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 subject to.
Hay tantas restricciones como elementos
en el conjunto Restr, donde cada una es Si no se desea utilizar un archivo de datos, se pueden ingresar los datosa2b0ajo
una suma. del comando data.
 5. Ejemplo
1. Crear documento de texto en Notepad o Wordpad.
2. Escribir archivo de datos y guardar con extensión .dat

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.

22
5. Ejemplo
1. Crear documento de texto en Notepad o Wordpad.
2. Escribir archivo de datos y guardar con extensión .run
3. Se ejecuta en AMPL con el comando: include [Link]

23
5. Ejemplo

1. Extraer archivo [Link] a un directorio conocido.

2. Ejecutar [Link] en windows o abrir línea de comando en DOS.
3. El archivo de modelo y el archivo de datos deben estar en directorio AMPL.

Versión Windows con [Link] Versión línea de comando DOS

24
6. Ejercicio Barriles de Petróleo
Problema:
Petrolera debe determinar su producción de barriles de petróleo para los próximos 3
años.

Variables de decisión:
x = Producción en millones de barriles de petróleo para el periodo i.
i

Datos:
P = ( 28 – x ), Precio en dólares para barriles vendidos en periodo 1.
1 1

P = ( 30 – x ), Precio en dólares para barriles vendidos en periodo 2.

2 2

P = ( 32 – x ), Precio en dólares para barriles vendidos en periodo 3.

3 3

2
C = x , Costo de extracción en millones de dólares para periodo 1.
1 1
2
C = 1.5x , Costo de extracción en millones de dólares para periodo 2.
2 2

C = 2x 2, Costo de extracción en millones de dólares para periodo 3.

2 3

Tasa de descuento por periodo = 4%

25
6. Ejercicio Barriles de Petróleo
Problema:
Petrolera debe determinar su producción de barriles de petróleo para los próximos 3
años.

Objetivo:
Maximizar las utilidades totales (valor presente) para los 3 periodos:
Max P x - x 2+ (P x -1.5x 2)/1.04 +( P x -2 x2)/1.04 2
1 1 1 2 2 2 3 3 3

{x1,x2,x3} ≥ 0

Restricciones:
R : x + x + x ≤ 30, Cantidad máxima de extracción en 3 periodos.
1 1 2 3

R : C + C + C ≤ 350, Máximo gasto en extracción para los 3 periodos.

2 1 2 3

26
6. Ejercicio Barriles de Petróleo
Archivo de modelo: [Link]

Declara los parámetros del modelo

Declara las variables de decisión del modelo

Declara la función objetivo

Declara las restricciones del modelo

27
6. Ejercicio Barriles de Petróleo
Archivo de datos: [Link]

Define los valores de los parámetros

Archivo de instrucciones: [Link]

28
6. Ejercicio Barriles de Petróleo
Resultado en AMPL

Ejecuta archivo [Link] en

AMPL

Valor óptimo función

objetivo

Valor de las variables en el punto óptimo

Valor de los costos reducidos de las

variables

Valor y holgura de las

restricciones en punto óptimo

29
 7. Ejercicio Empresa de Computadores
Problema:
Empresa debe determinar sus cantidades óptimas de producción de dos tipos de
computadores, que llamaremos modelo A y modelo B.

Variables de decisión:
q = Cantidad de computadores modelo i a fabricar, con i={A, B}.
i

p = Precio de venta de computadores modelo i, con i={A, B}.

i

Datos:
Modelo A:
• Requiere de 3 horas de trabajo y de 2 chips como insumos.
• Función de demanda dada por: qA = 6.000 – 8pA + 2pB.
Modelo B:
• Requiere de 2 horas de trabajo y de 4 chips como insumos.
• Función de demanda dada por: qB = 5.000 + pA – 5pB.
Se dispone de 8.000 horas de trabajo y de un inventario de 7.000 chips.
30
7. Ejercicio Empresa de Computadores
Problema:
Empresa debe determinar sus cantidades óptimas de producción de dos tipos de
computadores, que llamaremos modelo A y modelo B.

Objetivo:
Maximizar las utilidades totales variando el precio y la cantidad producida:
Max pq +pq
A A B B

{p1,p2,q1,q2} ≥ 0

Restricciones:
R : qA = 6.000 – 8pA + 2pB , demanda modelo A.
1

R : qB = 5.000 + pA – 5pB,
2 demanda modelo B.
R : 3qA + 2qB ≤ 8.000, restricción de recurso horas de trabajo.
3

R : 2qA + 4qB ≤ 7.000, restricción de recurso chips.

4

31
 7. Ejercicio Empresa de Computadores
Archivo de modelo: [Link]

Declara los conjuntos del modelo

Declara los parámetros del modelo

En la Declara las variables de decisión del modelo

declaración de
parámetros y
variables se le
pueden dar
otras Declara la función objetivo
opciones,
como que sea
integer, binary,
>=0, default Declara las restricciones del modelo
10, etc.

3
1
 7. Ejercicio Empresa de Computadores
Archivo de datos: [Link]

Nótese la diferencia en el uso de : y := en la declaración de vectores y matrices

32
7. Ejercicio Empresa de Computadores
Archivo de instrucciones: [Link]

• ¿Cómo puedo cambiar interactivamente los valores?

• ¿Cómo puedo fijar el valor de una variable?
• ¿Cómo puedo guardar los resultados en un archivo?
• ¿Cómo puedo medir el tiempo de resolución? 33
 7. Ejercicio Empresa de Computadores
Archivo de instrucciones: [Link]

Ingreso de datos interactivo

Cambiar valores de datos

(condiciones iniciales o parámetros)

Muestra más cifras significativas de los

resultados
Muestra tiempos y memoria utilizada

34
 7. Ejercicio Empresa de Computadores
Archivo de instrucciones: [Link]
Ejecuta comando MS-DOS

Guarda datos en .txt

Fija el valor de una variable

Deshace la
fijación de
una variable

Nótese el uso de > para crear y guardar en un archivo .txt

nuevo y de >> para guardar en un archivo .txt ya existente 35
7. Ejercicio Empresa de Computadores
Archivo de resultados: [Link]
Parte 1 (todas las variables libres) Parte 2 (Producción de A fijo en 0)

Nótese el valor de las condiciones iniciales de las variables

37
 8. Ejercicio Empresa de Manufactura

Problema:
Empresa debe determinar nivel de producción y de inventario en cada periodo
para maximizar sus beneficios.

Variables de decisión:
Qjt = Cantidad de producto j a producir en periodo t.
Iit = Inventario de materia prima i en periodo t.

Datos:
• 3 productos: clavos, pernos y tornillos.
• 2 tipos de materia prima: níquel y fierro.
• T periodos a planificar.
• Máxima cantidad a producir por periodo.
• Unidades de materia prima para producir por producto.
• Inventarios iniciales de materia prima.
• Beneficio de cada producto por periodo.
• Costo de inventario y valor residual de materia prima.
38
 8. Ejercicio Empresa de Manufactura

Problema:
Empresa debe determinar nivel de producción y de inventario en cada periodo
para maximizar sus beneficios.

Objetivo:
Maximizar beneficio total estimado sobre todos los periodos,
menos los costos totales de almacenaje sobre todos los periodos,
más el valor de la materia prima restante después del último periodo

Restricciones:
• Cantidad producida total en cada periodo no debe exceder el máximo permitido
• Unidades de cada materia prima almacenada al comienzo del periodo 1 no puede
exceder el inventario inicial máximo
• Unidades de cada materia prima almacenada al comienzo de cualquier periodo t+1
debe ser igual a las unidades en almacenaje al comienzo del periodo t, menos las
unidades utilizadas para producción en el periodo t
• Debe cumplir cantidades mínimas de producción requeridas por el cliente 38
 8. Ejercicio Empresa de Manufactura
Archivo de modelo: [Link]

Parámetro
adicional
que me
obliga a
producir
una
cantidad
mínima de
cada
producto en
cada
periodo 3
9
 8. Ejercicio Empresa de Manufactura
Archivo de modelo: [Link]

Restricción
adicional de
producción
mínima, puede
ser por
requerimiento
de los clientes

4
0
 8. Ejercicio Empresa de Manufactura
Archivos de datos: [Link] y [Link]

• Puedo resolver distintos archivos de datos con el mismo archivo de modelo.

• Nótese que los archivos de datos pueden contener distintos conjuntos y n°de elementos.
42
 8. Ejercicio Empresa de Manufactura

Archivos de instrucciones: [Link]

¿Cómo puedo ingresar valor de producción mínima requerida interactivamente?

43
8. Ejercicio Empresa de Manufactura
Archivos de instrucciones: [Link]
Ingresando cantidades mínimas de producción interactivamente.

44
8. Ejercicio Empresa de Manufactura
Interfaz AMPL
Ingresando cantidades mínimas de producción interactivamente.

Resultados con y sin restricciones de cantidad mínima de producción difiere4n4

 8. Ejercicio Empresa de Manufactura
Archivos de Resultados: [Link]

Cantidades a producir e inventarios para cada

producto y para cada periodo de tiempo con
y sin restricciones de producción mínimas
4
5
 Parámetros y variables
Parámetros

D j  Demanda anual del mercado j

K i  Capacidad potencial de la instalacion i
fi  Costo fijo de apertura de la instalacion i
cij  Costo de transportar una unidad desde
la instalacion i al mercado j

Variables de Decisión

xij  Cantidad en unidades a transportar desde i hacia j

yi  1si la instalacion se abre, 0 de lo contrario
Formulación Algebraica
Minimizar Costo Total :
n n m
Min  f  y   C
i i ij  xij
i1 i1 j1

Sujeto A :
n

 x Dij j  j  1, 2, ...., m
i1
m
 x K y
ij i i  i  1, 2, ...., n
j1

xij  0
yi  0,1  i  1, 2, ...., n
 Modelo AMPL

Conjuntos
set INSTALACIONES;
# Conjunto de instalaciones candidatas
set MERCADOS;
# Conjunto de mercados
 Parámetros
param demanda{j in MERCADOS} >=0;
# Demanda Dj anual del mercado j
param cap{i in INSTALACIONES} >=0;
# Capacidad Ki de la instalacion i
param c_fijo{i in INSTALACIONES} >=0;
# Costo fi de apertura de la instalacion i
param c_tran{i in INSTALACIONES, j in MERCADOS} >=0;
# Costo de transportar una unidad desde la instalacion i hacia el mercado j
 Variables
var x{i in INSTALACIONES, j in MERCADOS} >= 0;
var y{i in INSTALACIONES} binary;

Función Objetivo
minimize costo_total:
sum{i in INSTALACIONES} (c_fijo[i]*y[i]) +
sum{i in INSTALACIONES, j in MERCADOS} (c_tran[i,j]*x[i,j]);
 Restricciones
subject to cump_dem{j in MERCADOS}:
sum{i in INSTALACIONES} (x[i,j]) = demanda[j];

subject to capacidad{i in INSTALACIONES}:

sum{j in MERCADOS} (x[i,j]) <= cap[i]*y[i];

# Los paréntesis no son necesarios en este caso, dan mayor claridad a

la expresión contenida dentro de la sumatoria
PROBLEMA DEL TRANSBORDO
k Dem k
Cap í
i j Y jk Cali: 1500
5000 A CALI
X ij Medellín : 2000

4000 B IBAGUE Bogotá: 4500

NEIVA Barranquilla: 2500

3500 C
Pasto: 1500
Xij: Cantidad de producto a enviar desde i a j
Yjk: Cantidad de producto a enviar desde j a k
Cij: Costo de enviar producto de i a j

Cjk: Costo de enviar producto de j a k

 DATOS
• Plantas: A, B, C
• Sitios de Transbordo: CALI, IBAGUE Y NEIVA
• Zonas de consumo: CAL, MED, BGTA, BLLA Y PTO

• Demanda Clientes: • Capacidades

– CAL: 1500 Ton/año plantas:
– MED: 2000 Ton/año – A: 5000 Ton/año
– BGTA: 4500 Ton/año – B: 4000 Ton/año
– BLLA: 2500 Ton/año – C: 3500 Ton/ año
– PTO: 1500 Ton/año
 DATOS
Costos de transporte de i a j ($/Ton)

DESTIN CALI IBAGUE NEIVA

O
ORIGEN
A 10000 20000 30000
B 20000 30000 10000
C 30000 50000 15000
 DATOS
Costos de transporte de j a k ($/Ton)

DESTIN B/QUILL
O ORIGEN CALI MEDELLIN BOGOTA PASTO
A
CALI 0 75908 83184 133706 69707
IBAGUE 57067 73630 45991 114487 109520
NEIVA 69604 84105 63116 135524 110175

Fuente. DECRETO 2663 / 21 JULIO 2008 CON BASE EN LA RESOLUCIÓN 3175 DE 2008
 MODELO MATEMATICO
Función Objetivo :
Min Costo Total :  Xij Cij   Yjk Cjk
iI jJ j k kK

S.A.
Yjk
jJ
 Demk  k K

 Xij  Capi
jJ
iI

 Xij  Yjk  j J
iI kK
ARCHIVO MODELO
# CONJUNTOS
set I; # Conjunto de plantas ubicados en la zona de consumo i
set J; # Conjunto de zonas de trasbordo ubicados en la zona de consumo j
set K; # Conjunto de clientes ubicados en la zona de consumo k

# PARAMETROS
param Cap_plantai{i in I} >= 0; # Capacidad de la planta ubicada en la localidad
i (Toneladas de producto/ año)
param Dem_clientesk{k in K} >= 0; # Demanda de producto de los clientes
ubicados en la zona de consumo k (Toneladas de producto/año)
param Cost_tteij{i in I, j in J}; # Costo de transporte de producto de la planta i
al sitio de transbordo j ($/Ton)
param Cost_ttejk{j in J, k in K}; # Costo de transporte de producto del sitio de
transbordo j a la zona de consumo k ($/Ton)
# VARIABLES DE DECISIÓN
var x{i in I, j in J}>= 0;
# Toneladas de producto a enviar de i a j por año (Ton/año) var
y{j in J, k in K}>= 0;
# Toneladas de producto a enviar de j a k por año (Ton/año)

# FUNCION OBJETIVO
minimize costo_total:
# ($/año)
sum{i in I, j in J} (x[i,j]*Cost_tteij[i,j])
# Costo anual de enviar producto de i a j
+ sum{j in J, k in K} (y[j,k]*Cost_ttejk[j,k]; #
Costo anual de enviar producto de j a k
# RESTRICCIONES
# Por capacidad de la planta i (Ton/año):
subject to Cap_pdni{i in I}:
sum {j in J} (x[i,j]) <= Cap_plantai[i];

# Por demanda de los clientes k (Ton/año):

subject to Dem_client{k in K}:
sum {j in J} (y[j,k]) <= Dem_clientesk [k];

# Por balance de flujos en zonas de transbordo j (Ton/año):

subject to Balance_CD{j in J}:
sum {i in I} (x[i,j]) = sum {k in K} (y[j,k]) ;
ARCHIVO DATOS
# CONJUNTO DE DATOS CORRESPONDIENTE AL PROBLEMA DEL TRANSBORDO
# CONJUNTOS PRINCIPALES
set I:= A B C;
set J:= CALI IBAGUE NEIVA;
set K:= CAL MED BGTA BLLA PTO;
# PARAMETROS
# Capacidad de las plantas ubicadas en la localidad i # (Ton/año)
param Cap_plantai:=
A 5000
B 4000
C 3500;
# Demanda de los clientes ubicados en la zona de consumo k # (Ton/año)
param Dem_clientesk:=
CAL 1500
MED 2000
BGTA 4500
BLLA 2500
PTO 1500;
# Costo de transportar producto de la planta i al sitio de transbordo j #
($/Ton)
param Cost_tteij:
CALI IBAGUE NEIVA:=
A 10000 20000 30000
B 20000 30000 10000
C 30000 50000 15000;
# Costo de transportar producto del sitio de transbordo j a la zona de
consumo k # ($/Ton)

param Cost_ttejk: CAL MED BGTA BLLA PTO :=

CALI 0 75908 83184 133706 69707
IBAGUE 57067 73630 45991 114487 109520
NEIVA 69604 84105 63116 135524 110175;
 Archivo Comandos
# COMANDOS DE INICIALIZACIÓN DE CONDICIONES:
option show_stats 1: Muestra las estadísticas del problema a resolver (No. de
variables, No. de restricciones, No. de variables binarias, etc.).
option solution_precision 0: Define la máxima precisión para llevar a cabo los
cálculos.
option omit_zero_rows 1: Omite de los resultados aquéllas filas (restricciones)
cuyo valor sea cero.
option omit_zero_cols 1: Omite de los resultados aquéllas columnas
(variables) cuyo valor sea cero (esto es muy útil para problemas con resultados
muy dispersos).
option display_precision 6: Define como seis los campos de precisión a
presentar de cada variable.
option display_round 1: Redondea a una cifra decimal lo que muestra en los
resultados.
option display_width 50: Este es un comando que controla el ancho de la fila
para motivos de impresión de resultados.
 Archivo Comandos
# COMANDOS DE SOLUCIÓN:
model nombre_archivo.txt;
data [Link];
option solver cplex;
solve;

# COMANDOS DE IMPRESIÓN DE RESULTADOS:

printf "\n\n**************************************\n" > nombre_ [Link];
printf "RESULTADOS DEL PROBLEMA\n" >> nombre_ [Link];
printf "*************************************\n\n" >> nombre_ [Link];
printf "\nCOSTO TOTAL = \t%12.1f", costo_total >> nombre_ [Link];
printf "\nFLUJO DESDE PROVEEDORES HACIA ZONAS
TRASBORDO=\n\n" >> nombre_ [Link] ;
display x >> nombre_ [Link];
 Archivo
Comandos
# COMANDOS DE IMPRESIÓN DE RESULTADOS:
display y >> nombre_ [Link];
printf "\nCAPACIDAD SOBRANTE DE PROVEEDORES =\n\n" >>
nombre_ [Link];
display Cap_plantai.slack >> nombre_ [Link];
printf "\nCOSTOS DE OPORTUNIDAD DE PROVEEDORES =\n\n" >>
nombre_ [Link];
display Dem_clientek >> nombre_ [Link] t;

SIGNIFICADO DE LOS COMANDOS DE IMPRESIÓN

• \n significa salto de línea;

•\t tabulador; %12.1f significa que se va a imprimir un número de punto
flotante (un número real) con 12 espacios, de los cuales uno es
decimal
Modelo de Bauxita
 Problema de una cadena de abastecimiento
Una compañía multinacional de aluminio tiene depósitos de bauxita (materia prima)
en tres lugares del mundo A, B y C. Tiene además cuatro plantas donde la bauxita
se convierte en alúmina (un producto intermedio), en lugares B, C, D y E. También
tiene plantas de esmaltado en los lugares D y E. El proceso de conversión de la
bauxita en alúmina es relativamente poco costoso. El esmaltado, sin embargo, es
costoso puesto que se requiere de un equipo electrónico especial. Una tonelada de
alúmina produce 0.4 toneladas de aluminio terminado. Los datos siguientes están
disponibles:
Problema de una cadena de abastecimiento
Problema de una cadena de abastecimiento

Las ventas anuales de aluminio terminado son de 1000 ton en la planta D y de

1200 ton en la planta E.
Problema de una cadena de abastecimiento
Los lingotes de producto terminado no se transportan entre D y E y viceversa.
Formule y resuelva un modelo de optimización para determinar la mejor
configuración y diseño de la cadena de abastecimiento presentada. Note que
existe el problema de determinar cuáles plantas de alúmina deben ser abiertas.
 El problema de la Bauxita

Variables de decisión

Xij = Ton/año de bauxita a transportar desde la mina i hacia la planta de

alúmina j;
i = A, B, C; j = B, C, D, E.

Yjk = Ton/año de alúmina a transportar desde la planta de alúmina j hacia la

planta de esmaltado k; j = B, C, D, E; k = D, E.

Wj = 1, si la planta de alúmina j se abre; 0, de lo contrario; j = B, C, D, E.

Función objetivo

– Minimizar costo total anual

 Función Objetivo Problema Bauxita
Costo anual de explotación de bauxita ($/año):

Costo anual de producción de alúmina ($/año):

 Función Objetivo Problema Bauxita

Costo anual de procesamiento de alúmina en las plantas de esmaltado ($/año):

Costo anual de transporte desde las minas de bauxita hacia las plantas de
alúmina ($/año):
 Función Objetivo Problema Bauxita
Costo anual de transporte desde las plantas de alúmina hacia las plantas de
esmaltado ($/año):

Costo fijo anual de plantas de alúmina ($/año):

 Restricciones Problema Bauxita
1) Por capacidad anual de explotación de bauxita en cada mina (Ton de bauxita/año):

2) Por capacidad anual de procesamiento de bauxita en cada planta de alúmina (Ton de

bauxita/año):
 Restricciones Problema Bauxita
3) Por capacidad anual de procesamiento de alúmina en cada planta de esmaltado (Ton
de alúmina/año):

4) Por ventas anuales de aluminio terminado en cada planta de esmaltado (Ton de aluminio
terminado/año):

5) Por balance de masa en cada una de las plantas de alúmina:

 Restricciones Problema Bauxita
6) Por límites en los valores de cada una de las variables:
CONJUNTOS PRINCIPALES

MINAS = Conjunto de minas de bauxita indexado por I

PLALU = Conjunto de plantas de alúmina indexado por j
PLESM = Conjunto de plantas de esmaltado indexado por k

PARÁMETROS

capal_es = Capacidad de procesamiento de alúmina en la planta de esmaltado k (Ton dealúmina/año)

capb_al = Capacidad de procesamiento de bauxita en la planta de alúmina j (Ton de bauxita/año)
capbaux = Capacidad de explotación de bauxita de la mina i (Tonde bauxita/año)
cexp = Costo de explotación de la mina i ($/Ton de bauxita)
cfijo = Costo fijo de la planta de alúmina j ($/año)
cpal = Costo de producción de alúmina en la planta de alúmina j ($/Ton dealúmina)
cpes = Costo de procesamiento de la alúmina para producir aluminio terminado en la planta de
esmaltado k ($/Ton de alúmina)
ctran_al = Costo de transporte de alúmina desde la planta de alúmina j hacia la planta de esmaltado k
($/Ton de alúmina)
ctran_b = Costo de transporte de bauxita desde la mina de bauxita i hacia la planta de alúmina j
($/Ton de bauxita)
demanda = Demanda de aluminio terminado en la planta de esmaltado k (Ton de aluminio
terminado/año)
rendal = Rendimiento de alúmina de la bauxita extraída de la mina i (Ton de alúmina/Ton de bauxita)
rendim = Rendimiento de alúmina para producir aluminio terminado (Ton de aluminio terminado/Ton de
alúmina)
 Variables de decisión

Variables de decisión

Xij = Ton/año de bauxita a transportar desde la mina i hacia la planta de alúmina j;

i = A, B, C; j = B, C, D, E.

Yjk = Ton/año de alúmina a transportar desde la planta de alúmina j hacia la planta de

esmaltado k; j = B, C, D, E; k = D, E.

Wj = 1, si la planta de alúmina j se abre; 0, de lo contrario; j = B, C, D, E.

Código AMPL

var x{i in MINAS, j in PLALU} >= 0;

var y{j in PLALU, k in PLESM} >= 0;

var w{j in PLALU} binary;

 Función Objetivo
Código AMPL
Minimizar costo_total: minimize costo_total:

cexp(i) x ij sum{i in MINAS, j in PLALU} (cexp[i]*x[i,j])

i. j

cpal(j) y jk + sum{j in PLALU, k in PLESM} (cpal[j]*y[j,k])

j. k

cpes(k) y jk + sum{j in PLALU, k in PLESM} (cpes[k]*y[j,k])

j k

ctran_b(i,j) x ij
+ sum{i in MINAS, j in PLALU} (ctran_b[i,j]*x[i,j])
i. j

ctran_al(j,k) y
j. k
+ sum{j in PLALU, k in PLESM} (ctran_al[j,k]*y[j,k])
jk

cfijo(j) w(j) + sum{j in PLALU} (cfijo[j]*w[j]);

j
 Restricciones
Código AMPL
subject to cap_exp{i in MINAS}:
sum{j in PLALU} (x[i,j]) <= capbaux[i];

subject to cap_prodal{j in PLALU}:

sum{i in MINAS} (x[i,j]) <= capb_al[j]*w[j];

subject to demand_es{k in PLESM}:

sum{j in PLALU } (rendim*y[j,k]) = demanda[k];

subject to balance{j in PLALU}:

sum{i in MINAS } (rendal[i]*x[i,j]) = sum{k in PLESM} (y[j,k]);
 *Datos de parámetros de tres y más
dimensiones (1)

• param pmformula {i in PM, hh in HRPM[i], r in RAWPM[i]} >= 0;

• # toneladas de cada materia prima por cada

tonelada de producto intermedio consumidas en
cada máquina de la 1a etapa [tons de mat. Prima /
ton de producto terminado]

* Tomado de Vidal, notas de clase curso Optimización Avanzada

 Datos de parámetros de tres y más
dimensiones (2)
param pmformula:=
[MAQ2, PROD_INTERM1, *]
[MAQ1, PROD_INTERM1, *]

MAT_PRIMA1 0.30 MAT_PRIMA1 0.25

MAT_PRIMA2 0.00 MAT_PRIMA2 0.05
MAT_PRIMA3 0.20
MAT_PRIMA4 0.05 MAT_PRIMA3 0.15
MAT_PRIMA5 0.40 MAT_PRIMA4 0.03
MAT_PRIMA6 0.10
MAT_PRIMA5 0.40
[MAQ1, PROD_INTERM2, *]
MAT_PRIMA6 0.20
MAT_PRIMA1 0.50
MAT_PRIMA2 0.30 [MAQ2, PROD_INTERM2, *]
MAT_PRIMA3 0.20
MAT_PRIMA4 0.00
MAT_PRIMA5 0.05 MAT_PRIMA1 0.45
MAT_PRIMA6 0.05
MAT_PRIMA2 0.30
MAT_PRIMA3 0.25
MAT_PRIMA4 0.05
MAT_PRIMA5 0.00
MAT_PRIMA6 0.07;
 Datos de parámetros de tres y más
dimensiones (3)

param
pmformula:=

[MAQ1, *, *]: MAT_PRIMA1 MAT_PRIMA2 MAT_PRIMA3 MAT_PRIMA4 MAT_PRIMA5 MAT_PRIMA6 :=

PROD_INTERM1 0.30 0.00 0.20 0.05 0.40 0.10

PROD_INTERM2 0.50 0.30 0.20 0.00 0.05 0.05

MAT_PRIMA MAT_PRIMA MAT_PRIMA MAT_PRIMA MAT_PRIMA MAT_PRIMA

[MAQ2, *, *]: 1 2 3 4 5 6 :=
PROD_INTERM1 0.25 0.05 0.15 0.03 0.40 0.20

PROD_INTERM2 0.45 0.30 0.25 0.05 0.00 0.07

;
 Datos de parámetros de tres y más
dimensiones (4)

param pmformula:=

[MAQ1, *, *] (tr): PROD_INTERM1 PROD_INTERM2 :=

MAT_PRIMA1 0.30 0.50
MAT_PRIMA2 0.00 0.30
MAT_PRIMA3 0.20 0.20
MAT_PRIMA4 0.05 0.00
MAT_PRIMA5 0.40 0.05
MAT_PRIMA6 0.10 0.05

[MAQ2, *, *] (tr): PROD_INTERM1 PROD_INTERM2 :=

MAT_PRIMA1 0.25 0.45
MAT_PRIMA2 0.05 0.30
MAT_PRIMA3 0.15 0.25
MAT_PRIMA4 0.03 0.05
MAT_PRIMA5 0.40 0.00
MAT_PRIMA6 0.20 0.07 ;
 Conjuntos y Subconjuntos - Definición

set FIGGEOMETRICAS; # Conjunto de figuras geometricas

set ESTRELLAS within FIGGEOMETRICAS;
set ESTRELLAS within FIGGEOMETRICAS;

set FIGGEOMETRICAS: EST_R EST_V EST_N DEC_R DEC_N …..CUBO_N

set ESTRELLAS: EST_R EST_V EST_N ;
 9. Modelo de Programación No Lineal

Queremos calcular el círculo de mayor área

inscrito en un polígono definido por 4 rectas.

Por lo tanto, sea:

R : Radio de la circunferencia.
(x0,y0) : Centro de la circunferencia.
 9. Modelo de Programación No Lineal

Problema:
Encontrar el círculo de
mayor área inscrito dentro
de las curvas.
9. Modelo de Programación No Lineal
P) Max R 2
s.a 3x0  4y 0  24
5x0  2y 0  30
El radio se debe encontrar
y0  4  0
al interior del polígono
- 3x0  5y 0  15
3x0  4y 0  24
R
5
5x0 - 2y 0  30
R
29 La distancia desde el centro
y0  4  R a cada una de las rectas no
puede ser mayor al radio
- 3x0  5y 0  15
R
34
R  0, x0, y0  
 9. Modelo de Programación No Lineal
En este caso sólo utilizaremos el .mod para correr el problema enAMPL

Definición de variables

Definición de π

Restricciones Lineales

Restricciones No Lineales
 9. Modelo de Programación No Lineal

Opciones de resolución

Estadísticas del Solver

Tiempos de resolución

Minos encuentra solución

Resultados con display

 9. Modelo de Programación No Lineal

Solución:

Área = 44.1188
Radio = 3.7474
Xo = 1.86285
Yo = -0.25254
Links de interés

[Link]

[Link]

[Link]/~calvo/ampl/[Link]

52