Programacin mixta-entera

Prof. Cesar de Prada

ISA UVA
[email protected]

Prof. Cesar de Prada ISA-UVA

Indice

Problemas hbridos
Tipos de problemas mixto-enteros
Algoritmo Branch and Bound
Ejemplos
Software

Prof. Cesar de Prada ISA-UVA

Problemas hbridos

Muchos problemas de decisin involucran no solo

variables que pueden representarse por valores reales,
sino decisiones de tipo discreto que estn
representadas de forma natural por variables enteras o
binarias.
Otras veces, el planteamiento del problema involucra,
junto a los modelos cuantitativos, reglas o condiciones
lgicas adicionales
Estos problemas de optimizacin hbridos con variables
reales y enteras se denominan de programacin mixta
entera
Si las decisiones son solo de tipo entero el problema se
denomina de programacin entera
Prof. Cesar de Prada ISA-UVA

Ejemplo: Banda de ladrones

Una banda de ladrones asalta un almacn donde hay N objetos distintos.
Cada objeto j tiene un peso pj y un valor vj. Disponen de una camioneta
que puede transportar como mximo un peso P. Qu objetos deben
seleccionar los ladrones para obtener el mximo beneficio de su accin?
Definiendo una variable binaria yj para indicar si un objeto ha sido o
no seleccionado:
N

max
y

y v
j 1

sujeto a

y
j 1

pj P

0 el objeto j no ha sido seleccionado

yj
1 el objeto j si ha sido seleccionado

Problema ILP
integer linear
programming

Prof. Cesar de Prada ISA-UVA

Ejemplo: El problema del viajante

Un viajante debe partir de su ciudad y recorrer N ciudades volviendo a
la ciudad de origen sin repetir ninguna. La distancia entre la ciudad i y
la j es cij. Cual es la ruta que debe seguir para recorrer una distancia
mnima?.
Podemos asociar una variable binaria yij a cada
par de ciudades i , j
N

min
y

i 1 j 1

y
i 1

j 1

ij

yij

cij
yij

0 el viajante no va de la ciudad i a la j
yij
1 el viajante va de la ciudad i a la j

yii 0

ij

j 1,..., N

debe llegar una vez y solo una de la ciudad j

ij

1 1,..., N

debe partir una vez y solo una de la ciudad i

Prof. Cesar de Prada ISA-UVA

Tipos de problemas mixto enteros

c' y
min
y

Ay b
y Z

ILP Integer
Linear
Programming

J (x, y )
min
x, y

h(x, y) 0

g(x, y) 0
x R n , y Z

c' x d' y
min
x, y

MILP Mix-Integer
Ax b

Linear
Programming
Ey e
0 x R n , y Z

MINLP Mix-Integer
Non-Linear
Programming

Pueden re-convertirse
igualdades y
desigualdades usando
variables de holgura, al
igual que problemas min
en max
Prof. Cesar de Prada ISA-UVA

Mtodos de solucin

La aproximacin de tratar las variables enteras como reales y

luego aproximarlas al entero mas prximo suele dar resultados
errneos, excepto quizs cuando el nmero de valores posibles
de una variable entera es alto. Rara vez con variables binarias
Pueden enumerarse todas las combinaciones de variables
enteras posibles y resolver para cada una el problema,
posiblemente NLP, de variables reales asociado, escogiendo
luego el de mejor J, ya que son un nmero finito. Pero el nmero
de combinaciones crece exponencialmente con el nmero de
variables enteras.
Examen inteligente de alternativas enteras: Branch and Bound
(B&B)
Ajuste de cotas inferior y superior: Outer Approximation (OA),
Generalised Benders decomposition (GBD)
Prof. Cesar de Prada ISA-UVA

Branch and Bound (B&B)

El mtodo proporciona una bsqueda inteligente del ptimo
combinando la comparacin de distintas alternativas funcin de
las variables enteras, con un procedimiento para eliminar
combinaciones que no pueden conducir al ptimo y para
determinar las condiciones de ptimo basndose en cotas del
mismo.
Est basado en tres ideas principales:
Relajacin, que proporciona cotas del problema
Ramificacin, que examina las distintas alternativas de
variables enteras en un punto dado del rbol de decisin.
Poda, que permite eliminar determinados grupos de
combinaciones de variables enteras simplificando la bsqueda

Prof. Cesar de Prada ISA-UVA

Relajacin
Una relajacin de un problema MILP o MINLP consiste en
suponer que las variables binarias yj pueden tomar valores
reales en el intervalo 0 yj 1. (De forma similar se trata el
caso de variables enteras) Por tanto en el problema relajado
todas las variables, x e y, son reales y resulta un problema de
tipo LP o NLP.
Dominio del problema original
Dominio del problema relajado

Lgicamente, al ampliar el espacio de bsqueda, la solucin del

problema relajado es una cota inferior (o superior en el caso de
maximizacin) al problema original MILP o MINLP. El clculo de esta
cota es el objetivo que se busca al resolver el problema relajado.
Prof. Cesar de Prada ISA-UVA

Algoritmo Branch and Bound (B&B)

Ejemplo ILP (Himmelblau)
Max J = 86 y1 + 4 y2 + 40 y3

1
Relajacin
1

0 y1 1
0 y2 1
0 y3 1
y*=(1, 0.776, 1)
Jr*=129.1

Sujeto a
774 y1 + 76 y2 + 42 y3 875
67 y1 + 27 y2 + 53 y3 875
y1, y2, y3 0,1

10

El problema relajado es LP y
su resolucin proporciona
una cota superior Jr* de J*:
J* 129.1

y2= 0

2
Ramificacin

LP

y2= 1

A continuacin se examinan
las dos alternativas posibles
para y2, nica variable real de
la solucin relajada
Prof. Cesar de Prada ISA-UVA

Algoritmo Branch and Bound (B&B)

Max J = 86 y1 + 4 y2 + 40 y3
Sujeto a
774 y1 + 76 y2 + 42 y3 875

Nodo
n
LP

67 y1 + 27 y2 + 53 y3 875
y1, y2, y3 0,1
3 Relajacin
LP
Mejor solucin
factible hasta el
momento
(incumbente):
Cota inferior de J*

11

0 y1 1
y2 = 0
0 y3 1
y*=(1, 0, 1)
Jr*=126.0
4 Poda

y2= 0

0 y1 1
0 y2 1
0 y3 1
y*=(1, 0.776, 1)
Jr*=129.1
2
Ramificacin

1
Relajacin

y2= 1

No se puede seguir ramificando en

el nodo 2. El BB termina si la
diferencia de cotas superior e
inferior es menor que una
tolerancia Cota cota
sup

1 cota inf

inf

tol

Prof. Cesar de Prada ISA-UVA

1
1
Relajacin

B&B

LP

y2= 0
129.1
J*
126.0

12

Candidato
No hay mas
ramificacin
en este
nodo
El valor del
candidato es
una cota
inferior para
todo el
problema

0 y1 1
y2 = 0
0 y3 1
y*=(1, 0, 1)
Jr*=126.0

Poda

0 y1 1
0 y2 1
0 y3 1
y*=(1, 0.776, 1)
Jr*=129.1
2
Ramificacin
3

129.1
J*
-

y2= 1

0 y1 1
y2 = 1
Relajaciones
0 y3 1
y*=(0.978,1, 1)
Jr*=128.11
y1= 0
Ramificacin y1= 1

Si el hueco, o diferencia de cotas

superior e inferior, en el nodo 3 es
superior a la tolerancia, debe
seguirse ramificando. En caso
contrario el BB termina y el
candidato actual es el ptimo.

Cota
superior
en esta
rama:
128.11
J*
126.0

Prof. Cesar de Prada ISA-UVA

1
1
Relajacin

B&B

LP

y2= 0
129.1
J*
126.0
Candidato
No hay mas
ramificacin
en este
nodo

0 y1 1
y2 = 0
0 y3 1
y*=(1, 0, 1)
Jr*=126.0

Poda

0 y1 1
0 y2 1
0 y3 1
y*=(1, 0.776, 1)
Jr*=129.1
2
Ramificacin
3

y2= 1

0 y1 1
y2 = 1
Relajaciones
0 y3 1
y*=(0.978,1, 1)
Jr*=128.11
y1= 0
Ramificacin y1= 1

Cada solucin factible proporciona

una cota inferior para cualquier rama

13

129.1
J*
-

Pueden usarse los valores de

las cotas para podar ramas
sin calcular sus valores

Cota
superior
en esta
rama:
128.11
J*
126.0

Cada ramificacin
proporciona cotas
superiores menores
en esa rama
Prof. Cesar de Prada ISA-UVA

1
1
Relajacin

B&B

LP
y2= 0

129.1
J*
126.0
Candidato

14

Nueva
solucin
factible, pero
inferior a la
del candidato
actual por lo
que este no
cambia

0 y1 1
y2 = 0
0 y3 1
y*=(1, 0, 1)
Jr*=126.0

0 y1 1
0 y2 1
0 y3 1
y*=(1, 0.776, 1)
Jr*=129.1

y2= 1

2
Ramificacin
3

0 y1 1
y2 = 1
Relajaciones
0 y3 1
y*=(0.978,1, 1)
Jr*=128.11
y1= 0
Ramificacin

y1 =0
y2 = 1
0 y3 1
y*=(0,1, 1)
Jr*=44.0
Poda

129.1
J*
-

128.11
J*
126.0

y1= 1

Relajacin
No se puede seguir
ramificando este nodo
Prof. Cesar de Prada ISA-UVA

1
1
Relajacin

B&B

LP

y2= 0
129.1
J*
126.0
Candidato

15

0 y1 1
y2 = 0
0 y3 1
y*=(1, 0, 1)
Jr*=126.0

y1 =0
y2 = 1
0 y3 1
y*=(0,1, 1)
Jr*=44.0
Poda

129.1
J*
-

0 y1 1
0 y2 1
0 y3 1
y*=(1, 0.776, 1)
Jr*=129.1

y2= 1

2
Ramificacin
3

0 y1 1
y2 = 1
Relajaciones
0 y3 1
y*=(0.978,1, 1)
Jr*=128.11
y1= 0
Ramificacin y1= 1

El valor de J*r es
inferior a la cota
inferior del candidato,
cualquier
ramificacin dara un
valor menor, puede
podarse el nodo

128.11
J*
126.0

y1 = 1
Relajacin
y2 = 1
0 y3 1
y*=(1, 1, 0.595)
Jr*=113.81
Poda
Prof. Cesar de Prada ISA-UVA

1
1
Relajacin

B&B

LP

y2= 0
129.1
J*
126.0
Candidato

16

0 y1 1
y2 = 0
0 y3 1
y*=(1, 0, 1)
Jr*=126.0

y1 =0
y2 = 1
0 y3 1
y*=(0,1, 1)
Jr*=44.0
Poda

0 y1 1
0 y2 1
0 y3 1
y*=(1, 0.776, 1)
Jr*=129.1
2
Ramificacin
3

y1= 0

129.1
J*
-

y2= 1

0 y1 1
y2 = 1
0 y3 1
y*=(0.978,1, 1)
Jr*=128.11

128.11
J*
126.0

Ramificacin y1= 1
5
y1 = 1
El candidato
y2 = 1
actual, nodo 2, es
0 y3 1
el ptimo al
y*=(1, 1, 0.595)
haberse podado
Jr*=113.81
Poda
ya todas las
ramas
Prof. Cesar de Prada ISA-UVA

Ejemplo: Fbrica de pinturas

Una fbrica de pinturas tiene tres unidades de produccin de un
cierto tipo de pintura con capacidades que se indican en la tabla
adjunta. Igualmente se muestran en la misma los costos de puesta
en marcha de cada unidad y los costes por Kg de pintura
producido. Si una unidad se pone en funcionamiento, debe
producir en un periodo toda su capacidad

17

Unidad

Costes de
puesta en
marcha

Costes por Kg
de pintura
producida

Capacidad, Kg

2800

1900

2000

1700

1900

2900
Prof. Cesar de Prada ISA-UVA

Fbricas de pinturas
Las unidades pueden ponerse en marcha al principio de la
maana o al principio de la tarde. Lgicamente, si una unidad se
puso en marcha por la maana y sigue operando por la tarde solo
genera costos de puesta en marcha por la maana. Todas las
unidades se apagan por la noche y las decisiones de puesta en
marcha para el da se toman por la maana cada da de acuerdo a
los pedidos existentes.
Si un determinado da deben servirse 2500 kg de pintura por la
maana y 3500 kg por la tarde, Qu unidades deben ponerse en
funcionamiento y cuando para incurrir en los menores costos
posibles?

18

Cmo varia la solucin si la demanda de la tarde se incrementa

en 100 Kg?
Prof. Cesar de Prada ISA-UVA

Fbrica de pinturas
Variables:
1

i nmero del proceso (1, 2, 3)

j nmero del periodo de trabajo: 1 maana 2 tarde

yij variable binaria: vale 1 si el proceso i funciona

en el periodo j
ci costes de puesta en marcha de la unidad i
pi costes de produccin de un Kg en el proceso i

wi capacidad de produccin de la unidad i por

periodo
Dj demanda de pintura en el periodo j

19

zi variable binaria auxiliar , vale 1 si yi1 o yi2 es 1

Prof. Cesar de Prada ISA-UVA

Fbrica de pinturas
3

min ci z i pi wi ( yi1 yi 2 )
y ij , z i

i 1

w y
2

i 1

ij

z i yij

Dj

i 1,2,3

j 1,2

Excel

La variable zi vale 1 si se ha arrancado la unidad i por la

maana o por la tarde

Si por la maana no puede haber mas de

una unidad funcionando simultneamente:

20

j 1,2

y
i 1

i1

Prof. Cesar de Prada ISA-UVA

Formulacin en GAMS
sets i unidades / u1, u2, u3 /
j periodos / m, t /
parameters costea(i) coste de arrancar una unidad
/ u1=2800, u2=2000, u3=1900 /
costeKg(i) coste por kg por periodo / u1=5 , u2=3, u3=8 /
capacidad(i) capacidad /u1=1900, u2=1700, u3=2900/
demanda(j) demanda por periodo / m= 2500, t = 3500/;
variables

y(i,j) funciona o no la unidad I en el periodo j

z(i)
arranca la unidad i ese dia
coste coste total de la produccion del dia
binary variables y, z;

21

Prof. Cesar de Prada ISA-UVA

Formulacin en GAMS
equations produccion(j) produccion en cada periodo
restriccion(i,j) limites en z
costetotal calculo del coste;
produccion(j).. sum(i, y(i,j)*capacidad(i)) =g= demanda(j);
restriccion(i,j).. z(i) =g= y(i,j);
costetotal.. coste =e= sum(i,
costea(i)*z(i)+costeKg(i)*capacidad(i)*sum(j,y(i,j)));

model pinturas planificacion de la produccion / all /;

solve pinturas minimizing coste using mip;
display coste.l

22

Prof. Cesar de Prada ISA-UVA

Mezcla con lotes discretos

Unidad

Capacidad
kg/dia

8000

Kg de materias A
primas
necesarias

10000

Para hacer p1

0.4

0.6

0.16

Para hacer p2

0.3

0.7

0.2

Cada unidad trabaja

con lotes de 2000Kg

Disponibilidad
A

Beneficio
/ Kg

p1
1

p2

23

6000

B
C

Qu cantidad de p1 y
p2 deben producirse
para maximizar el
beneficio?
Prof. Cesar de Prada ISA-UVA

Mezcla con lotes discretos

Variables:

max 0.16 x1 0.2 x2

x1 cantidad producida por da de p1

0.6 x1 0.3x2 6000

x2 cantidad producida por da de p2

xi 2000 yi

i 1, 2

0 y1 4

0 y2 5

yi
A

p1
1

B
p2
C

24

entera
xi tiene que tomar
valores mltiplos de
2000 Kg, el tamao
del lote

2
Prof. Cesar de Prada ISA-UVA

Algoritmo Branch and Bound (B&B)

max 0.16 x1 0.2 x2
0.6 x1 0.3 x2 6000
xi 2000 yi

i 1, 2

0 y1 4

0 y1 5

yi

1
Relajacin
0 y1 4
0 y2 5
y*=(2.5, 5)
Jr*=2800

entera
y1 2

El problema relajado es LP y
su resolucin proporciona
una cota superior Jr* de J*:
J* 2800

25

2
Ramificacin

LP

y1 3

A continuacin se examinan
las dos alternativas posibles
para y1, nica variable real de
la solucin relajada
Prof. Cesar de Prada ISA-UVA

Algoritmo Branch and Bound (B&B)

max 0.16 x1 0.2 x2

Nodo
n

0.6 x1 0.3 x2 6000

xi 2000 yi

i 1, 2

0 y1 4

0 y1 5

yi

y1 2

entera
3 Relajacin
LP

Mejor solucin
factible hasta el
momento
(incumbente):
Cota inferior de J*

26

LP

0 y1 2
0 y2 5
y*=(2,5)
Jr*=2640
4 Poda

0 y1 4
0 y2 5
y*=(2.5, 5)
Jr*=2800

2
Ramificacin

1
Relajacin

y1 3

No se puede seguir ramificando en

el nodo 2. El BB terminara si la
diferencia de cotas superior e
inferior fuera menor que la
tolerancia
Prof. Cesar de Prada ISA-UVA

1
1
Relajacin

B&B

LP
y1 2

2800
J*
2640
Candidato
No hay mas
ramificacin
en este
nodo al dar
una
solucin
entera

27

0 y1 2
0 y2 5
y*=(2, 5)
Jr*=2640

2800
J*
-

0 y1 4
0 y2 5
y*=(2.5, 5)
Jr*=2800

2
Ramificacin
3
Relajaciones

Poda

y1 3
3 y1 4
0 y2 5
y*=(3,4)
Jr*=2560

Poda

Tambien da
solucin
entera, pero
es inferior al
nodo 2

Por tanto la solucin es: y*=(2, 5), x*=(4000, 10000)

Y el beneficio ptimo 2640

Prof. Cesar de Prada ISA-UVA

Variables enteras y binarias

Hay formas sencillas de hacer que una variable z
tome valores enteros entre 0 y n, usando solo
variables binarias, esto es, variables que solo toman
valores 0, 1
z = y1 + 2 y2 + 3 y3 + . + n yn
1 y1 + y2 + y3 + . + yn
y = {0 , 1}

28

Prof. Cesar de Prada ISA-UVA

Modelado con variables binarias

Seleccionar una alternativa y solo una
N

i 1

y1
y2

Seleccionar no mas de una alternativa

N

i 1

y3

Seleccionar al menos una alternativa

N

i 1

Seleccionar la alternativa j solo si se ha seleccionado la i

29

y j yi 0

Prof. Cesar de Prada ISA-UVA

Activacin de variables continuas

Para eliminar activar la variable continua x
usando la variable binaria y
q
L
U

variable continua , p.e. flujo

limite inferior
limite superior
Li yi q i Ui yi
si y i 0 0 q i 0 q i 0
si y i 1 L i q i U i

30

Prof. Cesar de Prada ISA-UVA

Modelado con variables continuas

y 0-1
Activacin y desactivacin de restricciones asociadas a una
corriente o unidad
restricciones h ( x ) 0 g ( x ) 0
var iables de ho lg ura s, v
h( x) s v 0
s v U 1 (1 y )
U , limite amplio
g ( x ) U 2 (1 y ) 0
s 0, v 0
si y 0 h ( x ) y g ( x ) no estan limitadas
si y 1 s 0, v 0, h ( x ) 0, g ( x ) 0

31

Prof. Cesar de Prada ISA-UVA

Modelado con variables continuas

y 0-1
m corrientes dirigidas al mismo nodo i
m

Uy i 0

qj

j 1

q j 0 j 1,2 , . . . , m
si y 0, q j 0

U lmite superior al flujo total

32

Prof. Cesar de Prada ISA-UVA

Modelado de expresiones lgicas

P1 P2 P3

y1 y 2 y 3 1

P1 P2 P3

y 1 1, y 2 1 y 3 1

P1 P2

1 y 1 y 2 1 o y 1 y 2 0

P1 si y solo si P2

y1 y 2

uno entre P1 , P2 , P3

y1 y 2 y 3 1

P1 P2 P3

y1 y 3 0 y 2 y 3 0

Usando estas equivalencias, puede convertirse cualquier

expresin lgica a expresiones en y, si la expresin lgica
se escribe en su forma conjuntiva normal

33

Prof. Cesar de Prada ISA-UVA

Forma normal conjuntiva

Q 1 Q 2 Q n

Donde las Q son expresiones de P escritas como disyunciones

Procedimiento de obtencin:
1 Reemplazar la implicacin por su expresin equivalente
P1 P2 P1 P2

2 Aplicar las leyes de Morgan para desplazar dentro las negaciones

( P1 P2 ) P1 P2

( P1 P2 ) P1 P2

3 Utilizar la propiedad distributiva para dar la forma normal

( P1 P2 ) P3 ( P1 P3 ) ( P2 P3 )

34

Prof. Cesar de Prada ISA-UVA

Ejemplo (1)
( P1 P2 ) P3 ( P4 P5 )

Paso 1

( P1 P2 ) P3 ( P4 P5 )
Paso 2

(P P ) P (P
1

P5 )

Paso 3

( P P ) ( P P ) P ( P P )
P P P P P P P
1

35

Prof. Cesar de Prada ISA-UVA

Ejemplo (2)

P P
1

P4 P5 P3 P4 P5

Q1 Q 2
Q 1 P1 P2 P4 P5
Q 2 P3 P4 P5
luego Q 1 Q 2

1 y 1 1 y 2 y 4 y 5 1

1 y 3 y 4 y 5 1
resulta ser

y1 y2 y4 y5 1

( P1 P2 ) P3 ( P4 P5 )

y 3 y 4 y5 0

36

Prof. Cesar de Prada ISA-UVA

Ejemplo de la produccin de acetona

(Raman y Grossmann, CACHE)
Se necesita producir acetona. La materia prima disponible es el
alcohol etlico (CH3CH2OH) y el metano (CH4). A continuacin se
muestran las posibles reacciones. Suponemos que el catalizador
que se requiere para todas las reacciones y los compuestos
inorgnicos estn disponibles excepto para CrO3 y O3. Determinar
la factibilidad para la produccin de acetona a partir de estos
productos. Si es factible, especificar un camino de reaccin.
NaOC 2 H 5 / C 2 H 5 OH
CH 3CO2 C 2 H 5

CH 3COCH 2 CO2 C 2 H 5
H 3O

CH 3COCH 2 CO2 C 2 H 5 CH 3COCH 3 C 2 H 5OH CO2

Et 2 O
H 2 O / HCl
CH 3CN CH 3 MgI
CH 3C NMgI CH 3
CH 3COCH 3

37

Prof. Cesar de Prada ISA-UVA

Ejemplo de la produccin de acetona

(Raman y Grossmann, CACHE)

Et 2 O / H 3O
CH 3CHO CH 3 MgI

CH 3CHOHCH 3
/ H 2 SO4
CH 3CHOHCH 3 CrO
3

CH 3COCH 3
3 / H 2 O / H 2 O2
CH 2 C CH 3 2 O
CH 3COCH 3 HCO2 H

CO2 CH 3
Mg / Er2 O
CH 3 I
CH 3 MgI CH
3

CH 3 3 COH

CH 3 3 COH CH 2 C CH 3 2

CH 4 I 2 CH 3 I HI
CH 4 Cl 2 CH 3Cl HCl
3 / Cu
CH 3CH 2 OH O2 Cr
2O
CH 3CHO

H 2O
CH 3Cl NaCN
NaCl CH 3CN

CH 3COOH C 2 H 5OH CH 3CO2 C 2 H 5

38

CH 3CHO O2 CH 3COOH
Prof. Cesar de Prada ISA-UVA

Ejemplo de la produccin de acetona

(Raman y Grossmann, CACHE)
Formulacin
De todas las reacciones qumicas posibles, se tiene que verificar dnde se
puede sintetizar la acetona a partir de la materia prima y catalizadores dados.
Para llegar a la conclusin final utilizando programacin matemtica, lo
primero que debemos hacer es expresar todas las reacciones en la forma de
lgica proposicional, utilizando los principales operadores:

(OR), (and), (implicacin), y (negacin)

I.

A B
M

39

A B C D

A B C D
se puede expresar como

A M B

Prof. Cesar de Prada ISA-UVA

Ejemplo de la produccin de acetona

(Raman y Grossmann, CACHE)
II. Expresar estas proposiciones lgicas en su forma conjuntiva
normal, utilizando los pasos sgtes:
1. Eliminar la implicacin

A B esto es equivalente A B
2. Mover la negacin al interior

A B A B

A B A B

Ejemplo

A B C D
A B C D
A B C D
A B C A B D

3. Distribuir el OR sobre el AND de forma recursiva

A B C A C B C

40

( ) clusula

Prof. Cesar de Prada ISA-UVA

Ejemplo de la produccin de acetona

(Raman y Grossmann, CACHE)
III. Convertir cada clusula por separado en desigualdades lineales. Para
ello, se asigna a cada variable una variable entera (binaria) y. Cada
negacin se sustituye por 1-y, donde y es la variable correspondiente.

A B C A B D
1 y A 1 y B yC 1
1 y A 1 yB yD 1
y A y B yC 1
y A yB yD 1

41

Prof. Cesar de Prada ISA-UVA

Ejemplo de la produccin de acetona

(Raman y Grossmann, CACHE)
CH 3CHO O2 CH 3COOH

CH 3CHO O2 CH 3COOH

y1 CH 3CHO

CH 3CHO O2 CH 3COOH

y 2 O2

(CH 3CHO O2 ) CH 3COOH

(CH 3CHO CH 3COOH ) (O2 CH 3COOH )

1 y1 y3 1
1 y 2 y3 1

42

y3 CH 3COOH

y1 y3 0
y 2 y3 0

Prof. Cesar de Prada ISA-UVA

Ejemplo de la produccin de acetona

(Raman y Grossmann, CACHE)

min yu
s.a.
Ay a
yr 0,1 , r 1,..., R
n

yu: variables binarias asignadas a los productos que se desean obtener

Yr : variables binarias asignadas a la materia prima y los catalizadores
disponibles
Si yu =1, significa que el producto se puede sintetizar y que se
dispone de materia prima

43

Prof. Cesar de Prada ISA-UVA

Ejemplo 1: Planteamiento
(Grossmann)
Representacin de alternativas para producir producto C a partir de los
productos A y B, a travs de los Procesos I, II, III. El producto C puede
ser producido slo a travs del proceso I; los procesos I y III, y los
procesos I y II. Los procesos II y III no pueden realizarse
simultneamente.
B
c

A2

Proceso II

B2

A1

Proceso I

B1
A3

44

Proceso III

B3

Prof. Cesar de Prada ISA-UVA

Ejemplo 1: Datos
Conversiones:
Proceso I:

Capacidad mxima

C = 0.9B

Proceso II: B = ln(1 + A)

Proceso III: B = 1.2ln(1 + A)

Precios

2 ton/h de C

Proceso II:

5 ton/h de B

Proceso III:

4 ton/h de B

Coste de Inversin

A: 1.800 $/ton

45

Proceso I:

Fijo (103 $/h)

Variable (103 $/ton)

B: 7.000 $/ton

Proceso I:

3.5

C: 13.000 $/ton

Proceso II:

Proceso III:

1.5

1.2

Demanda de C:

1 ton/h mximo

Prof. Cesar de Prada ISA-UVA

Ejemplo 1: Formulacin
B1

A2

Proceso II

B2 y 2

A1
A3

B1
Proceso III

Proceso I

C y1

B3 y 3

max PR = 13C-1.8A2 - 1.8 A3 -7B1 - 3.5y1 - 2C - 1.0y2 - 1B2 - 1.5y3 - 1.2B3

s .a.
PI: C-0.9(B1+B2+B3) = 0

Balances PII: B2-ln(1+A2) = 0

PIII: B3-1.2ln(1+A3) = 0
B1 = B2 + B3 +Bc

46

B2 5y2

B3 4 y3
c 2 y1

C, A2, A3, B1, B2, B3 >= 0

y1, y2, y3 = 0,1
y2 + y3 1

Lmites
Prof. Cesar de Prada ISA-UVA

GAMS
Positive Variables
a2 materia prima para el proceso 2
a3 materia prima para el proceso 3
b2 produccion de producto B en el proceso 2
b3 produccion de producto B en el proceso 3
bc cantidad de producto B que se puede adquirir en el mercado
b1 cantidad de producto B que se consume en el proceso 1
c1 capacidad de produccion del producto c en el proceso 1 ;
Binary Variables
y1 existencia del proceso 1
y2 existencia del proceso 2
y3 existencia del proceso 3 ;
Variable
pr beneficio total en millones de $ por ano ;

47

Prof. Cesar de Prada ISA-UVA

GAMS
las restricciones inout2 e inout3 se han convexificado
inout1.. c1 =e= 0.9*b1 ;
inout2.. exp(b2) - 1 =e= a2 ;
inout3.. exp(b3/1.2) - 1 =e= a3 ;
mbalb.. b1 =e= b2 + b3 + bp ;
log1.. c1 =l= 2*y1 ;
log2.. b2 =l= 4*y2 ;
log3.. b3 =l= 5*y3 ;

48

Prof. Cesar de Prada ISA-UVA

GAMS
y1.L = 1.000 existencia del proceso 1
y2.L = 0.000 existencia del proceso 2
y3.L = 1.000 existencia del proceso 3
c1.L = 1.000 capacidad de produccion del producto c en
el proceso 1
b1.L = 1.111 cantidad de producto B que se consume en el
proceso 1
b2.L = 0.000 produccion de producto B en el proceso 2
b3.L = 1.111 produccion de producto B en el proceso 3
bc.L = 0.000 cantidad de producto B que se puede adquirir en el
mercado
a2.L = 0.000 materia prima para el proceso 2
a3.L = 1.524 materia prima para el proceso 3

Proceso I

A3

49

Proceso III

B3 y 3

C
y1

Prof. Cesar de Prada ISA-UVA

Representacin de Alternativas:
Superestructuras, Floudas 1995
En una superestructura, se engloban todas las posibles
estructuras alternativas, que adems, son candidatas a la
solucin factible u ptima del proceso
Unidad
2

Entrada
1

Unidad
1
Unidad
3

50

Salida
1

Salida
2

Prof. Cesar de Prada ISA-UVA

Ejemplo de produccin de
amonaco, Biegler et all, 1997.
Recuperacin de
Hidrgeno

N2
H2

51

Compresor

Reactor

Separacin

Purga

NH 3

Prof. Cesar de Prada ISA-UVA

Ejemplo de produccin de
amonaco (rbol de alternativas)
reactor
tubular

condensacin
por flash

separacin por
membrana
no se recupera H2

destilacin
absorcin

separacin por
membrana
no se recupera H2

condensacin
por flash
reactor
multilecho

52

destilacin
absorcin
no se recupera H2

separacin por
membrana
no se recupera H2
separacin por
membrana

Prof. Cesar de Prada ISA-UVA

Ejemplo de produccin de
amonaco (superestructura)
purga
agua
absorbedor
NH3
reactor
tubular
N2

flash

H2
reactor
multilecho

53

agua

condensacin
por flash
NH

3
Prof. Cesar de Prada ISA-UVA

Alternativa del reactor multilecho

Alternativa 1: reactor multilecho / condensacin
por flash / separacin por membrana

purga

flash

N2
H2
reactor
multilecho

condensacin
por flash
NH3

54

Prof. Cesar de Prada ISA-UVA

Alternativa para el reactor tubular

purga

agua

absorbedor
NH3

flash

N2

agua

H2
reactor
tubular

condensacin
por flash

NH3
Alternativa 2: reactor tubular / condensacin por flash y
destilacin por absorcin / separacin por membrana Prof. Cesar de Prada ISA-UVA
55

Superestructuras
L5
L9
L6

L1

Representacin de todas
las alternativas posibles.
Cul es la mejor?

U-2

L2

B (98% C1)

L3
L10

(C1, C2, C3)

L4

L7

Variables 0-1 indican si

una corriente o una
unidad existen o no

U-3

U-1

C (97% C2)

L11
L8

56

D (99% C3)
Prof. Cesar de Prada ISA-UVA

Asignacin de tareas
En un taller trabajan n personas capaces de realizar diversas tareas.
Debido a sus diferentes habilidades y experiencia cada una tarda un
tiempo diferente en hacer cada una de las tareas, el cual es
conocido. Se deben realizar n de esas tareas para completar un
determinado trabajo. Cmo debe asignarse el personal para realizar
el tiempo total empleado?
Variables
i personas
j tareas
tij tiempo que la persona i tarda en hacer la tarea j

57

yij variable binaria, vale 1 si a la persona i se le asigna la

tarea j
Prof. Cesar de Prada ISA-UVA

Asignacin de tareas
n

min t ij y ij
x

i 1 j1

Tiempo total empleado

sujeto a
n

y
i 1

ij

y
j1

ij

1
1

j 1,..., n

Cada persona tiene que tener

asignada una tarea y una sola

i 1,..., n

Cada tarea debe haber sido

asignada a una persona y a una
sola

yij binaria

58

Prof. Cesar de Prada ISA-UVA

Oleoducto
P1

P1

P2
P2

Centro C1

P1

P3

P3

Centro C2

En que orden debo enviar los productos para minimizar costos,

satisfacer restricciones (dos tipos determinados de productos no deben
ir juntos) y satisfacer las demandas en tiempo?

59

Prof. Cesar de Prada ISA-UVA

Reactor batch
A

Un reactor opera en forma batch en

periodos de trabajo de una hora. Se
alimenta de un producto A que da lugar a
dos reacciones paralelas A B y A C
pero solo el producto B tiene valor
comercial. Las velocidades de reaccin
son:
k B 10 6 exp(10000 / RT )

k C 5 *1011 exp(20000 / RT )
Encontrar el perfil de temperatura que maximiza la
produccin final de B, sabiendo que esta debe ser inferior
en todo momento a 139 C

60

Prof. Cesar de Prada ISA-UVA

Optimizacin dinmica
A

xB

tiempo

B
T

max
T (t )

61

x B (1)

dx A
(k B k C ) x A x A (0) A0
dt
dx B
1h
6
x B ( 0) 0
kB xA
k B 10 exp(10000 / RT )
dt
11
k

5
*
10
exp(20000 / RT )
T (t ) 139
C

tiempo

Prof. Cesar de Prada ISA-UVA

Parametrizacin de las variables

de decisin
A

xB

tiempo

B
T

max
Ti

62

x B (1)

T1, T2, T3,.TN

dx A
(k B k C ) x A x A (0) A0
dt
dx B
1h
6
kB xA
x B ( 0) 0
k B 10 exp(10000 / RT )
dt
11
k

5
*
10
exp(20000 / RT )
Ti 139
C

tiempo

Prof. Cesar de Prada ISA-UVA

Resolucin con simulacin

max
Ti

x B (1)

dx A
(k B k C ) x A x A (0) A0
dt
dx B
kB xA
x B ( 0) 0
dt
Ti 139

u(t)
Optimizador
Ti

y(t)
Proceso

xB(1), Ti -139

Simulacin desde 0 a 1
para calcular J(u,x(t))

63

Prof. Cesar de Prada ISA-UVA

Optimizacin dinmica secuencial

minJ( x, u)
u
x(t ) f ( x(t ), u(t ))
y(t) g(x(t),u(t)
y y(t ) y
u u(t ) u

u(t)
Optimizador
u

64

y(t)
Proceso

Simulacin desde 0 a 1
para calcular J(u,x(t))
Prof. Cesar de Prada ISA-UVA