Optimización de Procesos
2
Tier I: Métodos Matemáticos de optimización
Daniel Grooms
Sección 1:
Introducción
3
Propósito de este Módulo
• Este módulo provee una introducción del área de optimización y muestra como se relaciona la optimización a la ingeniería química en general y a la integración de procesos en particular
• Esta es una introducción así que hay muchos aspectos interesantes que no serán cubiertos aqui
Para una discusión más detallada, vea las referencias listadas al final del módulo
4
Introducción a la Optimización
• ¿Qué es optimización?– Un proceso matemático de obtención del valor
mínimo (o máximo) de una función sujeto a algunas restricciones determinadas
• La optimización es usada todos los días – Ejemplos:– Al elegir la ruta que llevará a un destino– Al asignar el tiempo de estudio para varias clases– El orden de cocción de varios artículos en una
comida– Qué tan frecuentemente se debe cambiar el filtro
de aire de un carro
5
Aplicaciones de la Optimización
• Ejemplos de optimización en una planta química:– ¿A qué temperatura operar un reactor? – ¿Cuándo regenerar/cambiar el catalizador del reactor? – ¿Qué razón de reflujo de destilación usar para la
pureza deseada?– ¿Qué diámetro de tubería para una red de tuberías?
• La optimización puede ser usada para determinar las mejores respuestas para cada una de estas preguntas
6
Beneficios de la Optimización
• Capaz de determinar sistemáticamente la mejor solución
• Un modelo creado por optimización puede ser usado para otras aplicaciones
• Los conocimientos ganados durante el proceso de optimización pueden identificar cambios que pueden hacerse para mejorar el desempeño
7
Requisitos para la Optimización
• Un claro entendimiento de que se necesita optimizar. – Ej.: ¿minimizar el costo o maximizar la calidad
del producto?
• Comprensión de las restricciones en la optimización.– Ej: asuntos de seguridad, requisitos del
cliente, límites de presupuesto, etc.
• Una manera de representar esto matemáticamente (i.e. un modelo)
8
Definiciones
• Función objetivo: Una representación de lo que quieres minimizar o maximizar - como: costo, tiempo, producción, ganancia, etc.
• Variables: Elementos que pueden ser cambiados para influenciar el valor de la función objetivo
• Restricciones: Igualdades o desigualdades que limitan la cantidad de variables que pueden ser cambiadas
9
Más Definiciones
• Mínimo: Un punto donde la función objetivo no disminuye cuando la(s) variable(s) es cambiada en cierta cantidad.
• Máximo: Un punto donde la función objetivo no se incremente cuando la(s) variable(s) es cambiada en cierta cantidad.
Mínimo: Mínimo Estricto:
10
Ejemplo 1 de Modelamiento
Una planta química hace urea y nitrato de amonio. Las utilidades netas son $1000 y $1500/ton producida respectivamente. Ambos químicos son fabricados en dos pasos - reacción y secado. El número de horas necesarias para cada producto es proporcionado abajo:
Paso/Químico Urea Nitrato de Amonio
Reacción 4 2
Secado 2 5
11
Ejemplo 1 de Modelamiento
La etapa de reacción opera un total de 80 horas por semana y la de secado está disponible por 60 horas por semana. Hay 75 toneladas de materia prima disponible. Cada tonelada producida de cualquier producto requiere 4 toneladas de materia prima.
¿Cuál es la velocidad de producción de cada químico que maximizará las utilidades netas de la planta?
12
Ejemplo 1 de Modelamiento
• Función Objetivo:Queremos maximizar la utilidad neta. Utilidad
Neta = Ingresos - Costo. Consideremos x1 = toneladas de urea producidas por semana y x2 = toneladas de nitrato de amonio producidas por semana. Ingresos = 1000x1 + 1500x2. No existen datos para los costos, así que asumiremos Costo = 0.
Entonces, la función objetivo es:
Maximizar 1000x1 + 1500x2
13
Ejemplo 1 de Modelamiento• Restricciones:Sabemos que la fase de reacción opera
durante 80 hrs/semana. Así, los tiempos combinados de reacción requeridos para cada producto no pueden exceder esta cantidad.
La tabla indica que cada tonelada de urea producida requiere 4 horas de reacción y cada ton de nitrato de amonio producido requiere 2 horas de reacción. Esto resulta en la siguiente restricción:
4x1 + 2x2 ≤ 80
14
Ejemplo 1 de Modelamiento
También sabemos que la fase de secado opera 60 hrs/semana. La tabla indica que la urea requiere 2 hrs/ton producida y el nitrato de amonio 5 hrs/ton producida. Así, obtenemos la siguiente restricción:
2x1 + 5x2 ≤ 60
15
Recordemos que el suministro de materia prima es 75 tons/semana y cada ton de urea o nitrato de amonio producido requiere 4 toneladas de materia prima. Esto nos da la restricción final:
4x1 + 4x2 ≤ 75
Ejemplo 1 de Modelamiento
16
Finalmente, para asegurar un resultado realista, siempre es prudente incluir restricciones no-negativas para las variables donde sea aplicable.
Aquí, no debemos tener velocidades de producción negativas, así que incluimos las dos restricciones
x1 ≥ 0 & x2 ≥ 0
Ejemplo 1 de Modelamiento
17
Así, tenemos el siguiente problema:
Maximizar 1000x1 + 1500x2
Sujeta a: 4x1 + 2x2 ≤ 80
2x1 + 5x2 ≤ 60
4x1 + 4x2 ≤ 75
x1, x2 ≥ 0
Una vez resuelto, esto tiene una respuesta óptima de x1 = 11.25 tons/semana y x2 = 7.5 tons/semana
Restricción 1
Restricción 2
Restricción 3
Ejemplo 1 de Modelamiento
18
Gráfica de Ejemplo 1
El área gris es llamada región factible y se puede observar que el punto óptimo se encuentra en la intersección de las restricciones.
Ya que estamos maximizando, analizamos en la dirección del vector ganancia
x2
x1
Restricción 1
Restricción 2
Restricción 3
Punto Óptimo Vector ganancia
19
Ejemplo 2 de Modelamiento
Una compañía tiene tres plantas que producen etanol y cuatro clientes a los que debe proveer etanol.
La siguiente tabla muestra los costos de entrega por tonelada de etanol de las plantas a los clientes.
(Un guión en la tabla indica que cierta planta no puede entregar a cierto cliente)
Planta/Cliente C1 C2 C3 C4
P1 132 - 97 103
P2 84 91 - -
P3 106 89 100 98
20
Las tres plantas P1, P2, & P3 producen 135, 56, y 93 tons/año, respectivamente. Los cuatro clientes, C1, C2, C3, & C4 requieren 62, 83, 39, y 91 tons/año, respectivamente.
Determine el esquema de transportación que resultará en el costo más bajo.
Ejemplo 2 de Modelamiento
21
• Función Objetivo:Queremos obtener el menor costo, así que
debemos minimizar el costo. El costo será los costos dados en la tabla por la cantidad transferida de cada planta a cada cliente. Muchas de las cantidades serán cero, pero debemos incluirlas todas porque no sabemos cuales usaremos.
Ejemplo 2 de Modelamiento
22
Consideremos a xij como la cantidad (tons/año) de etanol transferida de la planta Pi al cliente Cj. Así, x21 es la cantidad de etanol enviada de la planta P2 al cliente C1. Dejaremos fuera las combinaciones que la tabla indica muestra imposibles (como x12). Entonces, la función objetivo es:
Minimizar 132 x11 + 97 x13 + 103 x14 + 84 x21 + 91 x22 + 106 x31 + 89 x32 + 100 x33 + 98 x34.
Ejemplo 2 de Modelamiento
23
• Restricciones:
Las plantas de etanol no pueden producir más etanol debido a sus limitaciones de capacidad. El etanol que cada planta produce es la suma del etanol que envía a los clientes. Así, par la planta P1, el límite es de 135 tons/año y la restricción es:
x11 + x13 + x14 ≤ 135
Puesto que la planta puede enviar etanol a los clientes C1, C2, y C4.
Ejemplo 2 de Modelamiento
24
Para las plantas P2 y P3, los límites son 56 y 93 tons/año, así que sus restricciones son:
x21 + x22 ≤ 56
x31 + x32 + x33 + x34 ≤ 93
El signo ≤ es usado porque las plantas pueden producir menos o hasta sus límites, pero no pueden producir más del límite.
Ejemplo 2 de Modelamiento
25
También, cada uno de los clientes tiene requerimientos de etanol que deben cumplirse. Por ejemplo, el cliente C1 debe recibir al menos 62 tons/año de cualquiera de las plantas P1, P2, P3, o una combinación de las tres. Así, la restricción del cliente es:
x11 + x21 + x31 ≥ 62
Ya que puede recibir etanol de las plantas P1, P2, & P3.
Ejemplo 2 de Modelamiento
26
Los requisitos de los clientes C2, C3, y C4 son 83, 39, y 91 tons/año así que las restricciones son:
x22 + x32 ≥ 83
x13 + x33 ≥ 39
x14 + x34 ≥ 91El signo ≥ es usado porque está bien si los
clientes reciben etanol extra, pero deben cumplir al menos los requerimientos mínimos.
Ejemplo 2 de Modelamiento
27
• Si los clientes tuvieran que recibir exactamente la cantidad especificada de etanol, usaríamos restricciones de igualdad
• Sin embargo, no se ha indicado para este problema, así que las dejaremos como restricciones de desigualdad
Ejemplo 2 de Modelamiento
28
Como en el ejemplo anterior, las restricciones no-negativas son requeridas porque no podemos tener una cantidad negativa de etanol trasferido.
x11, x13, x14, x21, x22, x31, x32, x33, x34 ≥ 0
Ejemplo 2 de Modelamiento
29
El problema es:
Minimizar 132 x11 + 97 x13 + 103 x14 + 84 x21 + 91 x22 + 106 x31 + 89 x32 + 100 x33 + 98 x34
Sujeta a: x11 + x13 + x14 ≤ 135
x21 + x22 ≤ 56
x31 + x32 + x33 + x34 ≤ 93
Ejemplo 2 de Modelamiento
30
x11 + x21 + x31 ≥ 62 x22 + x32 ≥ 83x13 + x33 ≥ 39x14 + x34 ≥ 91
Y: x11, x13, x14, x21, x22, x31, x32, x33, x34 ≥ 0
El resultado óptimo es:x11 x13 x14 x21 x22 x31 x32 x33 x34
0 39 87 56 0 6 83 0 4
Ejemplo 2 de Modelamiento
31
• A diferencia del ejemplo previo, no podemos encontrar el punto óptimo gráficamente porque tenemos más de dos variables
• Esto ilustra el poder de la optimización matemática
Ejemplo 2 de Modelamiento
32
• Maximizar una función es equivalente a minimizar lo negativo de la función:
Maximizando y Minimizando
)(min)(max xfxf
x* x*
f(x) f(x)
x x
33
Extremos Locales y Globales
• Ejemplo: Al tratar de minimizar una función objetivo f(x) que tiene una variable única, x.
• Existen dos mínimos locales• Hay un mínimo global
f(x)
x
34
• 1a Derivada: Velocidad de cambio de la función. También, línea tangente.
• 2a Derivada: Velocidad de cambio de la 1a derivada
Repaso de Cálculo
En esta región, la 2a derivada es positiva porque la pendiente de la 1a derivada va en aumento
En esta región, la 2a derivada es negativa porque la pendiente de la 1a derivada va en aumento
f(x)
x
1a's Derivadas
35
Repaso de Cálculocontinuación
• Podemos observar que la pendiente de la 1a derivada es cero (horizontal) en máximos y mínimos
• También, la 2a derivada es < 0 (negativa) en los máximos y es > 0 (positiva) en los mínimos
f(x)
x
36
Optimización no restringidaEjemplo
Supón que estás decidiendo que tanto aislamiento debes poner en tu casa. Asume que la pérdida de calor de la casa puede ser modelada por la ecuación:
donde x es el espesor del aislamiento en centímetros.
101
x
Q kJ/h
37
También, supón que la generación de 1 kJ de calor cuesta $0.50 para tu caldera y el aislamiento costará $1/año por cada centímetro de grosor a lo largo de su periodo de vida. Queremos minimizar el costo del calor perdido y de el aislamiento.
Optimización no restringidaEjemplo
38
De este modo, mientras más aislante instalemos, menos calor perderemos, el aislamiento puede hacer muy buen trabajo, pero cuesta dinero también, así que necesitamos encontrar el equilibrio óptimo. Aquí está una gráfica de los dos costos:
Costo del calor
Costo de aislamientoCosto Anual
Espesor del aislamiento
Optimización no restringidaEjemplo
39
No tenemos ninguna restricción de presupuesto o de suministro de aislamiento, así que solo minimizaremos el costo total.
El costo total anualizado de la pérdida de calor es dado por:
kJañodia
diah
hkJ
xCostHeat
50.0$36524101
añox$800,43
380,4
Optimización no restringidaEjemplo
40
Cada centímetro de aislamiento cuesta $1/año, entonces el costo total anualizado de aislamiento es 1x $/año. El costo total es simplemente la suma de los dos costos:
añoxx
CostTotal$800,43
380,4
Optimización no restringidaEjemplo
41
Podemos encontrar el mínimo usando los elementos de cálculo que observamos antes. Primero, encontramos donde la primera derivada es cero (horizontal). Entonces nos aseguramos de que la segunda derivada sea positiva, puesto que estamos buscando un mínimo.
Optimización no restringidaEjemplo
42
Encuentra la derivada del costo total:
Resuelve para la derivada igual a cero:
x
xdx
dCost
dx
dTotal 800,43
380,4
10380,4
2
x
0380,4
12
x
380,42 x
Optimización no restringidaEjemplo
43
El resultado es: x = 66.18
x es el grosor del aislamiento y obviamente no podemos tener valores negativos. Así, nuestro resultado es x = +66.18 cm
A propósito, ya que solo hay una solución positiva, sólo tenemos un mínimo. Así sabemos que éste es el mínimo global.
Optimización no restringidaEjemplo
44
Verifica la 2a derivada:
A x= 66.18,
Puesto que la 2a derivada es positiva, este punto es un mínimo.
3322
2 760,8380,4)2(0
380,41
xxxdx
dCost
dx
dTotal
04.13218.66
760,832
2
TotalCostdx
d
Optimización no restringidaEjemplo
45
Así, el mejor equilibrio entre costo por pérdida de calor y costo de aislamiento se alcanza si instalamos cerca de 66 cm de aislamiento.
x* = 66 cm
Costo Total
Espesor del aislamiento
Resultados del Ejemplo de Optimización no restringida
46
La Región Factible
• La región factible es el grupo de soluciones que satisfacen las restricciones de un problema de optimización
• Un problema de optimización de 2 variables con 4 restricciones de desigualdad:
x2
x1
Región Factible
47
Restricciones de Igualdad
• Ahora, la región factible es la sección de la línea de la restricción de igualdad que se encuentra dentro del área formada por las restricciones de desigualdad
x2
x1
Restricciones de Desigualdad
Restricción de
Igualdad
48
Más de la Región Factible
• El punto óptimo se encuentra en la región factible
• Si la región factible es solo un punto, no existen grados de libertad para optimizar. Las restricciones son simplemente un sistema de ecuaciones
• Si la región factible no existe, las restricciones están en conflicto:
x2
x1
49
Conjuntos Convexos
• Un conjunto es convexo si una combinación convexa de cualesquiera dos puntos en el conjunto se encuentra también en el conjunto
• Una combinación convexa:
– Una combinación convexa de puntos x1 y x2 es: donde
• Gráficamente, una combinación convexa de dos puntos es una línea que conecta ambos puntos.
21 )1( xx 10
x1x2
=1 =0
50
• Un conjunto es convexo si, para cualesquiera dos puntos en el conjunto, la longitud total de la línea conectora está también en el conjunto
• Prueba estos:
Visualización Gráfica
La totalidad de la línea está en el grupo, así que el grupo es convexo
Esta área no se encuentra en el grupo, así que el grupo es no-convexo
ConvexoConvexoNo-convexo No-convexo
51
Funciones Convexas
• f(x) es una función convexa si:
f(x1+(1-).x2) ≤ f(x1) + (1-).f(x2)
donde 0 ≤ ≤ 1
x1 x2
f(x1)
f(x2)
f(x1)+(1-)f(x2)
f(x1+(1-)x2)
52
Funciones Convexas
• En términos geométricos, una función es convexa si la línea que conecta dos puntos cualesquiera de la función nunca es menor que los valores de la función entre los dos puntos.
53
Funciones Cóncavas
• La definición de una función cóncava es exactamente opuesta a la de la función convexa
• Si f(x) es una función convexa, -f(x) es una función cóncava
54
Resultados de Convexidad
Para el problema de optimización
minimizar: f(x)sujeta a: gi(x) ≤ 0 i = 1, …, m
donde x es un vector de n variables.
• Si f(x) es una función convexa y las restricciones gi(x) forman un conjunto convexo, entonces solo hay un mínimo de f(x): el mínimo global
55
Implicaciones
• Esto es importante porque usualmente es posible encontrar un óptimo local, pero es muy difícil determinar si el óptimo local es el óptimo global.
Así luce el proceso de optimización:
Empieza aquí
¡Encontramos el mínimo
global!
¡Oops! – tal vez no
56
Conclusiones de Convexidad
• Tener un problema convexo (función objetivo convexa y un grupo convexo de restricciones) es la única manera de garantizar una solución óptima global
• Desafortunadamente, la mayoría de los problemas reales son no_convexos
• Sin embargo, los problemas convexos proporcionan algunos elementos y tienen propiedades que podemos usar parcialmente para problemas no-convexos