OptimizationCourseOptimización de Procesos.pdf

Optimización de Procesos

1. Optimización de Procesos Optimización de Procesos
Vicente Rico Ramírez Vicente Rico Ramírez
Departamento de Departamento de
Ingeniería Química Ingeniería Química
Instituto Tecnológico de Instituto Tecnológico de
Celaya Celaya

2. Índice de Contenido Índice de Contenido
1 Introducci 1 Introduccióónn
1.1 La Ingenier 1.1 La Ingenieríía de Procesos a de Procesos
1.2 Modelaci 1.2 Modelacióón y Grados de Libertad n y Grados de Libertad
1.3 Representaci 1.3 Representacióón Matem n Matemáática Generalizada de un Problema de Optimizaci tica Generalizada de un Problema de Optimizacióónn
1.4 Tipos de Problemas de Optimizaci 1.4 Tipos de Problemas de Optimizacióónn
1.5 Regi 1.5 Regióón Factible n Factible
1.6 Convexidad 1.6 Convexidad
2. T 2. Téécnicas de Optimizaci cnicas de Optimizacióónn
2.1 Programaci 2.1 Programacióón Lineal: M n Lineal: Méétodo todo Simplex Simplex
2.2 Programaci 2.2 Programacióón No Lineal n No Lineal
2.2.1 Optimizaci 2.2.1 Optimizacióón sin restricciones n sin restricciones
2.2.2 Optimizaci 2.2.2 Optimizacióón con Restricciones de Igualdad n con Restricciones de Igualdad
2.2.3 Optimizaci 2.2.3 Optimizacióón con Restricciones de Desigualdad n con Restricciones de Desigualdad
2.3 La Programaci 2.3 La Programacióón Mixta n Mixta--Entera en el Dise Entera en el Diseñño de Procesos o de Procesos
2.4 Programaci 2.4 Programacióón Mixta Entera Lineal: M n Mixta Entera Lineal: Méétodo de todo de ““Branch and Bound Branch and Bound””
2.5 Programaci 2.5 Programacióón Mixta n Mixta--Entera No Lineal: M Entera No Lineal: Méétodo todo ““Outer Approximation Outer Approximation””
3. El Ambiente de Modelaci 3. El Ambiente de Modelacióón GAMS y sus Resolvedores n GAMS y sus Resolvedores

3. Índice de Contenido Índice de Contenido
4. Aplicaciones en Ingenier 4. Aplicaciones en Ingenieríía Qu a Quíímica mica
5. Introducci 5. Introduccióón a la Optimizaci n a la Optimizacióón Bajo Incertidumbre n Bajo Incertidumbre
5.1 Tipos de Problemas de Programaci 5.1 Tipos de Problemas de Programacióón Estoc n Estocáástica stica
5.2 El M 5.2 El Méétodo de Descomposici todo de Descomposicióón Estoc n Estocáástica stica
6. Introducci 6. Introduccióón a la Optimizaci n a la Optimizacióón n Multiobjetivo Multiobjetivo
6.1 M 6.1 Méétodos de Soluci todos de Solucióónn
7. Control 7. Control ÓÓptimo y Optimizaci ptimo y Optimizacióón Din n Dináámica mica
7.1 El Principio del M 7.1 El Principio del Mááximo ximo
7.2 Programaci 7.2 Programacióón Din n Dináámica mica
7.3 Programaci 7.3 Programacióón Din n Dináámica Estoc mica Estocáástica stica

4. 3 Etapas en la Ingeniería de Procesos 3 Etapas en la Ingeniería de Procesos
””Process Systems Engineering Process Systems Engineering””
••Síntesis (o Diseño) Síntesis (o Diseño)
••Simulación (o Análisis) Simulación (o Análisis)
••Optimización Optimización

5. Síntesis (o Diseño ) de Procesos Síntesis (o Diseño ) de Procesos
Materia
Prima
(condiciones
iniciales)
Productos
Bajo
Especificación
Determinación de la Estructura del Proceso Estructura del Proceso
para realizar la transformación deseada

6. Análisis (o Simulación ) de Procesos Análisis (o Simulación ) de Procesos
Dadas las condiciones de entrada y la estructura
del proceso, determinar las variables de salida variables de salida
Materia
Prima
(condiciones
iniciales)
Productos
Bajo
Especificación

7. Optimización de Procesos Optimización de Procesos
Definir una función objetivo función objetivoy determinar los
mejores valores de las mejores valores de lasvariables de diseño variables de diseño
D, Pureza
Alimentación
Minimizar Costo Minimizar Costo
N=?N=?
R=?R=?
P=?P=?

8. Interacción entre Etapas de la Ingeniería de Interacción entre Etapas de la Ingeniería de
Procesos Procesos
9La optimización optimizaciónrequiere de la solución de
problemas de simulación simulaciónen cada iteración
9La optimización optimizaciónes una herramienta
imprescindible en el diseño diseñode un proceso
Diseño Diseño
Simulación Simulación
Optimización Optimización

9. Introducción: Algunos Conceptos Introducción: Algunos Conceptos
en la Optimización de Procesos en la Optimización de Procesos

10. Representación Matemática de la Fisicoquímica Representación Matemática de la Fisicoquímica
del proceso: del proceso:
Previo a la Optimización: Previo a la Optimización: Modelación Modelación
z
Balances de Masa
z
Balances de Energía
z
Relaciones Termodinámicas
z
Ecuaciones de Diseño
z
Balances de Momentum
z
Restricciones Particulares
Sistema de Sistema de
Ecuaciones Ecuaciones
No Lineales No Lineales

11. Análisis de Grados de Libertad Análisis de Grados de Libertad
Para un sistema de M Ecuaciones M Ecuacionesy N Variables N Variables, el
número de grados de libertad, FF, está dado por:
F = N F = N --MM
Tres casos:
F = 0 El sistema tiene solución UNICA UNICA
F F > >
11El sistema puede OPTIMIZARSE OPTIMIZARSE
F < 0 El sistema está sobre especificado:
MODELO INCORRECTO MODELO INCORRECTO

12. Simulación u Optimización? Simulación u Optimización?
Grados de Libertad
F = Número de Variables – Número de Ecuaciones
F = N - M
Simulación ó Análisis
F=0
El sistema debe ser consistente
Optimización
F>1
Función Objetivo: Maximizar
utilidades, Minimizar costos, etc. Función Objetivo Función Objetivo:
obtención de diseños obtención de diseños
óptimos óptimos

13. Simulación u Optimización? Simulación u Optimización?
0 ,
3
2
2 1
2 1
2 1
≥
=
= +
xx
x x
x x
0 ,
2
2 1
2 1
≥
= +
xx
x x
022=−=F
112=−=F
2 1
minx x−
Solución única Solución única
Simulación Simulación
Soluciones posibles: Soluciones posibles:
Función
objetivo
M M
0
5.0
1
2
2
5.1
1
0
2 1
x x
5.0
5.1
2
1
=
=
x
x
Solución óptima Solución óptima
Optimización Optimización

14. M = 900 N = 1000 M = 900 N = 1000
¿ Como seleccionar 100 Variables de Diseño ?
Matriz de Incidencia
f
1
f
2
f
3
x
1
x
2
x
3
x
4
X
X X
X X X
Selección de Variables de Diseño Selección de Variables de Diseño
()
01
05 3
02) ln(
4 3
3
2 3
4 2 2
1 1
=− + − =
=− − =
=− =
x x x f
x x f
x f

15. Variable de Diseño: Cualquiera de x Variable de Diseño: Cualquiera de x
22
, x, x
33
y xy x
44
f
1
f
2
f
3
x
1
x
2
x
3
x
4
X
X X
X X X
Trayectorias de Trayectorias de Steward Steward

16. •
VariablesDiscretas DiscretasyContinuas Continuas
•
Restricciones (Ecuaciones, Desigualdades)
Lineales LinealesyNo Lineales No LinealesRepresentación Matemática del Representación Matemática del
Problema de Optimización Problema de Optimización
}1,0{ ,
0),(
0),( ..
),( min
∈ ∈
≤
=
y Rx
yxg
yxhts
yxf
n

17. }1,0{ ,
0),(
0),( ..
),( min
∈ ∈
≤
=
y Rx
yxg
yxhts
yxf
n
Minimizar Costos
Maximizar Utilidades
Balances de Materia, Energía,
Relaciones de Equilibrio, etc.
Decisiones discretas:
¿ Equipo Existe ?
Temperatura,
Presión, etc.
Límites:
0<
Comp<
1
El Modelo Matemático El Modelo Matemático

18. zz
¿ Restricción Lineal o No Lineal ? ¿ Restricción Lineal o No Lineal ?
zz
¿ Variable Continua o Discreta ? ¿ Variable Continua o Discreta ?
1 3 2= +y x
1 3= +y yx
()
1 ln
2
= +y x
200 K < Temperatura < 500 K
T = 253.75 K
T = 493.68 K
y
y=0
y=1
Equipo
No Existe
Equipo
Existe

19. Clasificación de Técnicas de Optimización Clasificación de Técnicas de Optimización
Tipos de Variables Tipos de Variables
Enteras ContinuasEnteras+Continuas
Tipos de Restricciones Tipos de Restricciones
Programación
Lineal Lineal
Programación
No Lineal No Lineal
Programación
Entera Entera
Tipos de Restricciones Tipos de Restricciones Programación
Mixta Entera Mixta Entera
Lineal Lineal
Programación
Mixta Entera Mixta Entera
No Lineal No Lineal

20. Tipos de Problemas de Optimización Tipos de Problemas de Optimización
(Determinística, Estado Estable) (Determinística, Estado Estable)
**
Programación Lineal ( Programación Lineal (LPLP))
**
Programación Mixta Entera Lineal ( Programación Mixta Entera Lineal (MILP MILP))
**
Programación No Lineal ( Programación No Lineal (NLPNLP))
**
Programación Mixta Entera No lineal ( Programación Mixta Entera No lineal (MINLP MINLP))

21. Región Factible y Convexidad Región Factible y Convexidad
n
Rx
xg
xhts
xf
∈
≤
=
0)(
0)( ..
)( min
NLPNLP

22. Función Convexa Función Convexa
f(x)es convexa si para toda x
1
y x
2
ε
R:
f(x)
x
1

x
2


f(x)
x
1

x
2

[]
)1,0( ), () 1()( ) 1 (
2 1 2 1
∈ ∀ − + ≤ −+α α α α αxf xf x xf
Función Convexa o No Convexa Función Convexa o No Convexa
Convexa ConvexaNo No
Convexa Convexa

23. Función Función
[]
)() 1()( ) 1 (
2 1 2 1
xf xf x xfα α α α− + ≤ −+
Función Convexa? Función Convexa?
No No
Convexa Convexa
)3,1( 6 11 6 )(
2 3
Intervalo x x x xf− + − =
)3()75.0()1( 25.0)5.2(f f f+ ≤
0 375.0≤ −
0)1( )(
1
= =f xf0)3( )(
2
= =f xf
25.0=α
)3()25.0()1( 75.0)5.1(f f f+ ≤
0 375.0≤
No se cumple No se cumple
75.0=α

24. Región Factible. Definición: Región Factible. Definición:
Convexa o No Convexa? Convexa o No Convexa?
Convexa si para toda x
1
y x
2
ε
FR:
() ()
{
}
n
Rx xg xhx FR∈ ≤ = =,0 ,0

x
2

x
1


x
2

x
1

)1,0( , ) 1(
2 1
∈ ∀ ∈ − + =α α αFR x x x
Región Factible y Convexa Región Factible y Convexa Convexa ConvexaNo No
Convexa Convexa

25. Técnicas de Optimización Técnicas de Optimización

26. Técnicas de Optimización Técnicas de Optimización
**
Métodos Simplex Métodos Simplexy Puntos Interiores ( y Puntos Interiores (LPLP))
**
““Branch and Bound Branch and Bound” (Ramificación y ” (Ramificación y
Acotamiento) ( Acotamiento) (MILP MILP))
**
Estrategia del Conjunto Activo Estrategia del Conjunto Activo, SQP , SQP
(Programación Cuadrática Sucesiva) ( (Programación Cuadrática Sucesiva) (NLPNLP))
**
““Outer Approximation Outer Approximation” y Descomposición de ” y Descomposición de
Benders ( Benders (MINLP MINLP))

27. Programación Lineal Programación Lineal

28. Forma General Forma General
n
T
Rx
x
bxAts
xc
∈
≥
≤
0
..
min
25
135 3 3
180 2 5
200 300
1
2 1
2 1
2 1
≤
≤ +
≤ +
+
x
x x
x x a sujeto
x x Maximize






=
200
300
c






=
2
1
x
x
x








=
0
3
1
3
25
A










=
25
135
180
b
Programación Lineal Programación Lineal

29. Método Simplex Método Simplex
El óptimo se encuentra siempre El óptimo se encuentra siempre
en un punto “esquina” en un punto “esquina”
g
2
=0
Si la función objetivo
disminuye en esta dirección
Región
de
búsqueda
g
1
=0
Este sería el punto óptimo

30. 1) Introducir variables “slack” para convertir desigualdades en
igualdades. El número de grados de libertad no cambia.
2) Utilizar x
=0como punto inicial
3) Construir Matriz de Coeficientes
4) Efectuar pasos de eliminación Gaussiana hasta no obtener
valores negativos en el renglón correspondiente a la función
objetivo
Método Simplex Método Simplex
25
135 3 3
180 2 5
1
2 1
2 1
≤
≤ +
≤ +
x
x x
x x
25
135 3 3
180 2 5
3 1
2 2 1
1 2 1
= +
= + +
= + +
s x
s x x
s x x

31. x
1
x
2
s
1
s
2
s
3
b
5
2
1
0
0
180
s
1
3
3
0
1
0
135
s
2
1
0
0
0
1
25
s
3
-300
-200
0
0
0
0
f
s
3
x
2
s
1
s
2
s
3
b
0
2
1
0
-5
55
s
1
0
3
0
1
-3
60
s
2
1
0
0
0
1
25
x
1
0
-200
0
0
300
7500
f
Método Simplex Método Simplex
Matriz de Matriz de
Coeficientes Coeficientes
Punto inicial Punto inicial
x
1
= 0
x
2
=0
s
1
= 180
s
2
=135
s
3
= 25
Eliminación Gaussiana

32. El pivote en los pasos de eliminación Gaussiana
se escoge de modo que:
• Columna: el coeficiente de la función
objetivo es el más negativo
• Renglón: la menor proporción entre b y el
coeficiente de la columna seleccionada
Pivoteo Pivoteoen el Método en el Método
Simplex Simplex

33. s
2
x
2
s
1
s
2
s
3
b
0
-3
1
-5/3
0
-45
s
1
1
1
0
1/3
0
45
x
1
0
-1
0
-1/3
1
-20
s
3
0
300
0
100
0
1350
f
Renglón Pivote Renglón Pivote
¿Qué ocurre si no se toma la menor proporción?

34. s
3
s
2
s
1
s
2
s
3
b
0
0
1
-2/3
-3
15
s
1
0
1
0
1/3
-1
20
x
2
1
0
0
0
1
25
x
1
0
0
0
200/3
100
11500
f
Método Simplex Método Simplex
Eliminación Gaussiana

35. 1. En cada punto esquina, un número de
variables igual al número de grados de
libertad del problema valen cero
2. Las variables cuyo valor es cero se
denominan no básicas no básicas
3. Cada punto de la trayectoria se dice que es
una solución básica solución básica
4. El algoritmo concluye cuando ya no hay
coeficientes negativos en el renglón de la
función objetivo
Notas en el Método Simplex Notas en el Método Simplex

36. Método Simplex Método Simplex
25
135 3 3
180 2 5
200 300
1
2 1
2 1
2 1
≤
≤ +
≤ +
+
x
x x
x x a sujeto
x x Maximize
x
1
x
2
()
90,0
()
45,0
()
0,0
()
5.27,25
()
20,25
()
0,25
El óptimo en el punto (25,20) El óptimo en el punto (25,20)

37. Programación No Lineal Programación No Lineal

38. Optimización Sin Restricciones Optimización Sin Restricciones
Condición necesaria necesaria: es un punto crítico de f(x
)
si se cumple que
(
)
n
Rx
xf
∈
min
x
()
0
1
=












∂
∂
∂
∂
= ∇
n
x
f
x
f
xfM
Condiciones de Optimalidad Condiciones de Optimalidad
Se obtiene un sistema Se obtiene un sistema
de de nnEcuaciones con Ecuaciones con nn
Variables Variables xx

39. Optimización Sin Restricciones Optimización Sin Restricciones
(
)
n
Rx
xf
∈
min
()
0
1
=












∂
∂
∂
∂
= ∇
n
x
f
x
f
xfM
Condiciones de Optimalidad Condiciones de Optimalidad

40. Condición suficiente suficiente: La Matriz Matriz Hessiana Hessianade la
función objetivo es definida positiva










∂
∂
∂∂
∂
∂∂
∂
∂
∂
=
2
1
2
1 2
2
2 1
2
2
1
2
x
f
xx
f
xx
f
x
f
H
()
()
()
x Hx x xf xf x xf
T T
∆ ∆ +∆ ∇+ = ∆+
2
1
0
2
1≥∆ ∆x Hx
T
Hessianapara el
caso de 2 variables 2 variables

41. Optimización Sin Restricciones Optimización Sin Restricciones
()
2
2
2 1
2
1
2 6 )( minx x x x− + −
1
3
2
1
=
=
x
x
H es positiva definida H es positiva definida
Optimo Global Optimo Global
()
0
2 2
6 2
2
1
=






−
−
= ∇
x
x
xf






=
20
02
H

42. Optimización Con m Restricciones de Igualdad Optimización Con m Restricciones de Igualdad
Función de Lagrange (función escalar): Función de Lagrange (función escalar):
Condiciones de Optimalidad Condiciones de Optimalidad
()
n
Rx
xhts
xf
∈
=0)( ..
min
()
()
()
()
∑
+ = + =
m
j
j j
T
xh xf xh xf xLλ λ λ)( ,
λλ
se denominan multiplicadores de se denominan multiplicadores de
Lagrange y constituyen Lagrange y constituyen mmvariables variables
adicionales en el problema adicionales en el problema

43. Condición necesaria: Condición necesaria:Obtener un punto crítico
(estacionario) para la función de Lagrange función de Lagrange
Condición suficiente: La Matriz Matriz Hessiana Hessianade la
función de Lagrange función de Lagrangees definida positiva
()
()
0)(
,
= ∇ + ∇=
∂
∂
∑
j
j j
xh xf
x
xL
λ
λ
()
()
0
,
= =
∂
∂
xh
xL
λ
λ
Se obtiene un sistema Se obtiene un sistema
de de n+mn+mEcuaciones Ecuaciones
con con n+mn+mVariables Variables x x
y y
λλ

44. Optimización con Optimización con
Restricciones de Igualdad Restricciones de Igualdad
()
02 ..
2 6 )( min
2 1
2
2
2 1
2
1
=− −
− + −
x xts
x x x x
()
0
1
1
2 2
6 2
)(
1
2
1
=






−
+






−
−
= ∇ + ∇
∑
λ λ
x
x
xh xf
j
j j
()
02
2 1
=− − =x x xh
02
0 2 2
0 6 2
2 1
1 2
1 1
=− −
= −−
= +−
x x
x
x
λ
λ

45. Optimización Con m Restricciones de Igualdad y r de Optimización Con m Restricciones de Igualdad y r de
Desigualdad Desigualdad
Función de Lagrange Aumentada (función escalar): Función de Lagrange Aumentada (función escalar):
Condiciones de Optimalidad Condiciones de Optimalidad
()
()
()
()
()
∑ ∑
= =
+ + = + + =
r
k
k k
m
j
j j
T T
xg xh xf xg xh xf xL
1 1
)( )( ,,µ λ µ λ µλ
µµ
se denominan multiplicadores de se denominan multiplicadores de Karush Karush--
Kuhn Kuhn--Tucker Tuckery constituyen y constituyen rrvariables variables
adicionales en el problema adicionales en el problema
n
Rx
xg
xhts
xf
∈
≤
=
0)(
0)( ..
)( min

46. Condición necesaria: Condición necesaria:Obtener un punto crítico
(estacionario) mediante el Teorema de Karush Teorema de Karush--
Kuhn Kuhn--Tucker Tucker
Condición suficiente: La Matriz Matriz Hessiana Hessianade la
función de Lagrange Aumentada función de Lagrange Aumentadaes definida
positiva
Se obtiene un sistema Se obtiene un sistema
de de n+m+r n+m+r Ecuaciones Ecuaciones
con con n+m+r n+m+rVariables Variables
x, x,
µµ
y y
λλ
()
()
0)( )(
,,
= ∇ + ∇ + ∇=
∂
∂
∑ ∑
k
k k
j
j j
xg xh xf
x
xL
µ λ
µλ
(
)
()
0
,,
= =
∂
∂
xh
xL
λ
µλ
()
()
0= ⋅xgx
k k
µ
()
0≤xg
k
()
0≥x
k
µ

47. Condición necesaria: Condición necesaria: ()
()
0)( )(
,,
= ∇ + ∇ + ∇=
∂
∂
∑ ∑
k
k k
j
j j
xg xh xf
x
xL
µ λ
µλ
(
)
()
0
,,
= =
∂
∂
xh
xL
λ
µλ
()
()
0= ⋅xgx
k k
µ
()
0≤xg
k
()
0≥x
k
µ

48. Optimización con Optimización con
Restricciones de Restricciones de
Desigualdad Desigualdad
()
0
21
1
1
1
1
3
)(
2 1
2
1
=






−
+





−
+






−
−
= ∇ + ∇
∑
µ µ µ
x
x
xh xf
k
k k
()
()
02
2
1
0 ..
3
2
1
min
2 1 2
2 1 1
2 1
2
2
2
1
≤− − =
≤ + −=
− − + =
x x g
x x gts
x x x x xf
Note: Note:
()
()
0 2
2
1
0
1
2
1
3
2 1 2
2 1 1
2 1 2
2 1 1
= − −
= + −
= − +
= + −
x x
x x
x
x
µ
µ
µ µ
µ µ

49. Solución al Conjunto de Ecuaciones KKT
()
0)( )(= ∇ + ∇ + ∇
∑ ∑
k
k k
j
j j
xg xh xfµ λ
()
0=xh
()
()
0= ⋅xgx
k k
µ
()
0≤xg
k
()
0≥x
k
µ
()
0=xg
k
()
0<xg
k
Programación No Lineal Programación No Lineal
Estrategia del Conjunto Activo ( Estrategia del Conjunto Activo ( Active Active SetSetStrategy Strategy))
Desigualdades Desigualdades
Activa ActivaInactiva Inactiva

50. {}
0
1
= =
k
gk J
0 0
1
= > ⇒∅=
k k
g Jµ
()
0)( )(
1
= ∇ + ∇ + ∇
∑ ∑
∈Jk
k k
j
j j
xg xh xfµ λ
()
0=xh
()
1
0J k xg
k
∈ =
Programación No Lineal Programación No Lineal
Estrategia del Conjunto Activo Estrategia del Conjunto Activo
1) Definir conjunto activo. Inicialmente:
2) Formular ecuaciones KKT

51. a) Eliminar de J
1
la restricción con el µ
i
más negativo
b) Añadir a J
1
todas las restricciones violadas
para hacerlas activas
c) Regresar a 2)
0 0)(≥ ≤
k k
y xgµ
0 / 0)(< >
k k
oy xgµ
0)(>xg
k
Programación No Lineal Programación No Lineal
Estrategia del Conjunto Activo Estrategia del Conjunto Activo
3) Si para toda kOK
OK. Se ha obtenido la solución
Si cualquier

52. Condiciones de Karush Condiciones de Karush--Kuhn Kuhn--Tucker (Iteración 1): Tucker (Iteración 1):
Estrategia del Conjunto Activo: Ejemplo Estrategia del Conjunto Activo: Ejemplo
Programación No Lineal Programación No Lineal
()
()
0
02
2
1
0 ..
3
2
1
min
2 3
2 1 2
2 1 1
2 1
2
2
2
1
≤ −=
≤− − =
≤ + −=
− − + =
x g
x x g
x x gts
x x x x xf
{}
0
1
= =
k
gk J
()
0)( )(
1
= ∇ + ∇ + ∇
∑ ∑
∈Jk
k k
j
j j
xg xh xfµ λ
0 0
1
= > ⇒∅=
k k
g Jµ
()
0
1
3
)(
2
1
=






−
−
= ∇ + ∇
∑
x
x
xh xf
k
k k
µ
0
0
0
1
3
3
2
1
2
1
=
=
=
=
=
µ
µ
µ
x
x
Verificando restricciones y µ´s:
0
0
0
01
!!!02/1
02
3
2
1
3
2
1
=
=
=
<−=
> =
<−=
µ
µ
µ
g
g
g
Activar g
2
{}
2
2
=J

53. n
Rx
xg
xhts
xf min
∈
≤
=
0)(
0)( ..
)(
Condiciones de optimalidad
(Karush-Khun-Tucker)
Iteración de Newton
Programa cuádratico
Sistema de Ecuaciones
No Lineales
Programación Cuadrática Sucesiva (SQP) Programación Cuadrática Sucesiva (SQP)
Programación No Lineal Programación No Lineal

54. Programación Mixta Programación Mixta--Entera Entera

55. z
2
z
1
x
2
x
1
x
0
10 kmol/hr B
A
I II



=
selected not isI reactor if
selected isI reactor if
y
0
1
1



=
selected not isII reactor if
selected isII reactor if
y
0
1
2
1,0 , 0 ,
0 20 0 20
10 67.0 8.0
0.6 5.5 4.6 5.7 min
2 1 2 1
2 2 1 1
2 1
2 2 1 1
= ≥
≤ − ≤ −
= +
+ + + =
yy xx
y x y x
x x a sujeto
x y x y C
Representación de Procesos en Representación de Procesos en
Términos de Variables Binarias Términos de Variables Binarias

56. 1) NOT 1) NOT
2) OR (exclusivo) 2) OR (exclusivo)
3) OR (inclusivo) 3) OR (inclusivo)
4) AND 4) AND
5) 5) IfIf--Then Then
6) 6) IffIff--Then Then
7) Teorema de 7) Teorema de Morgan Morgan
8) Distribución de 8) Distribución de
ANDAND
j
j
y
p
−
¬
1
1= +
∨
j i
j i
y y
pp
Relaciones Lógicas Relaciones Lógicas
1≥ +
∨
j i
j i
y y
p p
j i j i
j i j i
y y y y
p p p p
≤ ≥ + −
∨ ¬ →
1 1
()
()
B A B A
B A B A
¬∨¬⇔ ∧ ¬
¬∧¬⇔ ∨ ¬
1 ,1≥ ≥
∧
i j
j i
y y
p p
() ()()
C B CA C B A∨ ∧ ∨ ⇔ ∨ ∧
j i
j i
y y
p p
=
↔

57. Representando Alternativas Representando Alternativas














≥
≥
= ∨














≥
≤
=
0 ,
1
5
0 ,
1
2
2 1
1
2 1
2
2 1
1
2 1
1
xx
x
x x
y
xx
x
x x
y
()
()
()
1
1 1
1 2
1 2
2 1
1 1
1 2 1
1 2 1
= +
− ≤−
− −≥ −
− ≤ −
y y
y M x
y M x x
y M x x
Big Big --MMConvex ConvexHull Hull
()
()
() 0 ,
1 1
1 5
1 5
2 1
2 1
2 2 1
2 2 1
≥
− −≥−
− −≥ −
− ≤ −
xx
y M x
y M x x
y M x x
2 22
1 21
2 12
1 11
2 22 21
1 12 11
My x
My x
My x
My x
x x x
x x x
≤
≤
≤
≤
= +
= +
0 , ,,
1
0 5
0 2
22 21 12 11
2 1
2 12
1 11
22 12
21 11
≥
= +
≥
≤
= −
= −
x xxx
y y
y x
y x
x x
x x

58. Procedimiento: Procedimiento: 1)1)Resolver el problema como si todas las variables fueran
continuas (problema LP). Es decir, relajar las variables binarias.
A este nivel se le conoce como “Root Node” (Nodo raíz)
• El valor de la función objetivo en el nodo raíz es un límite
inferior a su valor en la solución
• Si la solución del nodo raíz es entera, tal solución es la
solución del problema
2)2)Realizar una búsqueda de ramificación ordenada mediante la
adición de restricciones enteras
Programación Mixta Programación Mixta--
Entera Lineal Entera Lineal
Método de “ Método de “Branch and Bound” (Ramificación y Acotamiento) ” (Ramificación y Acotamiento)

59. 0<
y
2
<
1
0<
y
3
<
1
0<
y
1
<
1
0<
y
2
<
1
0<
y
3
<
1
Relajado
y
1
=1
y
1
=0
y
2
=1
y
2
=0
y
3
=1
y
3
=0
Para mvariables binarias, el número de posibles nodos es 2
m+1
-1
Método de “ Método de “Branch and Bound” (Ramificación y Acotamiento) ” (Ramificación y Acotamiento)

60. 1)1)La función objetivo en ies un límite inferior a la función
objetivo en k.
2)2)Si algún nodo resulta en una solución entera, el valor de la
función objetivo en tal nodo es un límite superior de la solución
3)3)Si ies infactible o ilimitado, entonces ktambién lo es

k
i
3 Reglas en el Método de “ 3 Reglas en el Método de “Branch and Bound”:”:

61. Método de “ Método de “Branch and Bound”: Ejemplo ”: Ejemplo
{}
1,0 ,, ,0
9 3 8 5
0 2 3 ..
2 3 min
3 2 1
3 2 1
3 2 1
3 2 1
∈ ≥
−≤ − − −
≤ + + +−
+ + +=
yyy x
y y y
y y y x ts
y y yxz
y
3
=0y
3
=1
y
2
=0y
2
=1
y
2
=0
y
2
=1
y
1
=0y
1
=1
[]
6
333.0,1,0
=z[]
5.6
0,5.0,1
=z
[]
9
0,1,1
=z
[]
8.5
0,1,2.0
=z
[]
75.6
1,075.0,0
=z
[]
8
1,1,0
=z
infactible infactible
infactible infactible
infactible infactible
15 1 2
3
1
=−
=
+m
m

62. Algoritmo Algoritmo
General General

NO
SI
Nueva y
Z
L

Z
U

Seleccionar un valor inicial para y
Resolver el NLP resultante S(y
k
)
Resolver el Problema Maestro MILP
Z
L
<Z
U
?
Solución
Programación Mixta Programación Mixta--
Entera No Lineal Entera No Lineal

63. Problema Maestro Problema Maestro
() ()( )
() ()( )
{}
Tk
R
Rx y
a Ay
By xx xg xg
xx xf xf yc a sujeto
Z
n m
k
T
k k
k
T
k k T
∈∀









∈
∈ ∈
≤
≤ + − ∇+
− ∇+ + ≥
=
α
α
α
1,0
0
min
()





∀
=
k
k k
yde valores posibles los
ySde óptima solución la es xk
T
Programación Mixta Programación Mixta--
Entera No Lineal Entera No Lineal
Algoritmo “ Algoritmo “Outer Approximation” (DICOPT+++) ” (DICOPT+++)
{}
n m
T
Rx y
ayA
yB xg
xf yc
∈ ∈
≤
≤ +
+
1,0
0 )(
)( min
x
f(x)

64. Optimización Optimización Semi Semi--Infinita: Problema Relajado Infinita: Problema Relajado
() ()( )
() ()( )
{}
K k
R
Rx y
a Ay
By xx xg xg
xx xf xf yc a sujeto
Z
n m
k
T
k k
k
T
k k T
K1
1,0
0
min
=









∈
∈ ∈
≤
≤ + − ∇+
− ∇+ + ≥
=
α
α
α
(
)
K k que tal y por definidos
x NLP as subproblem Kde solución la Dada
k
k
K1=
Algoritmo “ Algoritmo “Outer Approximation””

65. 1)1)“Outer Approximation”: Ejemplo 1 “Outer Approximation”: Ejemplo 1
Programación Mixta Programación Mixta--
Entera No Lineal Entera No Lineal
()
()
0 14
0 2
0 2 ..
5.0 5.1 min
2 2 1
1 1
2
2
1
2
2
2
1 3 2 1
≤ − − −
≥ −
≤ − −
+ + + + =
y x x
y x
x x ts
x x y y y z
5 0 2
2 1
= = =
U
z x x
2)2)
3)3)
()
3 2 1
2 2
1 1
3
0
0 1
y x x
y x
y x
≥ +
≥ −
≥ −−
4 0
4 0
1
2
1
3 2 1
≤ ≤
≤ ≤
≥ + +
x
x
y y y
{}
1,0 ,
2 1
∈yy
NLPNLP
MILP MILP
1 1 1
3 2 1
= = =y y y
1 0 2 0 0 1
2 1 3 2 1
= = = = = =
L
z x x y y y
11 2 2
2 1
= = =
U
z x x
NLPNLP
MILP MILP
0 0 1
3 2 1
= = =y y y
5.1 0 1 0 1 0
2 1 3 2 1
= = = = = =
L
z x x y y y
5.3 1 1
2 1
= = =
U
z x x
NLPNLP
MILP MILP
0 1 0
3 2 1
= = =y y y
5.4 1 2 1 0 0
2 1 3 2 1
= = = = = =
L
z x x y y y

66. 1)1)Comenzar con y=1y resolver NLP:“Outer Approximation”: Ejemplo 2, Iteración 1 “Outer Approximation”: Ejemplo 2, Iteración 1
Programación Mixta Programación Mixta--
Entera No Lineal Entera No Lineal
()
()
{}
1,0 2 0
01.1 57.0 ln
0 1ln ..
7.2 min
2
1
2
∈ ≤ ≤
≤ −+ − −=
≤ + + −=
+ −=
y x
y x g
y x gts
xy z
0 347.9 7183 .1 2525 .0
2 1
= = = =µ µ x z
2)2)Linealizar el problema MINLP en x= 1.7183para obtener el problema maestro MILP:
{}
1,0 0
2581 .0 87085 .0
36788 .0 36787 .0
9525 .2 4366 .3 7.2 ..
min
∈ ≤
−≤ + −
≤ + −
− + −≥
=
y x
yx
yx
x y ts
z
OA
OA OA
α
α
939.1
0
−=
=
OA
z
y
)(
U
z
)(
L
z
U L
z z<
Volver a paso 1
con nuevo valor
y=0

67. El Entorno de Modelación El Entorno de Modelación
GAMS GAMSy sus Resolvedores y sus Resolvedores

68. Formas de Atacar el Problema de Formas de Atacar el Problema de
Modelación Modelación
zz
Corriente Modular Secuencial Corriente Modular Secuencial
*
Cada unidad de proceso (módulo) (módulo)calcula su salida
dadas las entradas
⇓⇓
En cada unidad se resuelve un sistema de ecuaciones no
lineales (subrutina que “convi erte” valores de entradas
en valores de salida)
*
Las variables de lascorrientes de reciclose suponen
inicialmente y constituyen la guía para proceso iterativo

69. Corriente
de
Reciclo
Compresor
Divisor de Corriente
Intercambiador Separador Flash
Reactor
Mezclador
Alimentación
*
Se requieren algoritmos de orden de precedencia orden de precedenciay
determinación de las corrientes de reciclo determinación de las corrientes de reciclo a ser supuestas.

70. *
Cada unidad del sistema es representado por un
sistema de ecuaciones ( lenguaje declarativo lenguaje declarativo: no
restricciones en cuanto a especificación de variables)
*
Las ecuaciones son generalmente almacenadas en
librerías
*
Para definir el problema, se colectan las ecuaciones
que representan a cada unidad y a las conexiones
entre ellas
zz
Corriente de Orientación a las Ecuaciones Corriente de Orientación a las Ecuaciones

71. *
El sistema resultante se resuelve simultáneamente simultáneamente
(probablemente un problema de miles de ecuaciones)
Sistema R
esultante

72. 9
Corriente Modular Secuencial: Simuladores de
Procesos
ASPEN ASPEN, PRO/II, HySys
¾
Modelado por configuración configuración
9
Corriente de Orientación a las Ecuaciones: Sistemas
de Modelación
gPROMS, SpeedUp, ABACO,
ASCEND
99
GAMS GAMS
¾¾
NLPNLP:
CONOPT, MINOS, LACELOT, SRQP, LINGO
¾¾
MINLP MINLP:
DICOPT
¾¾
MILP, LP MILP, LP:
CPLEX, OSL, LINDO, SCICONIC, XA
Simuladores y Optimizadores Simuladores y Optimizadores
Comerciales Comerciales

73. GAMS la Interfase GAMS la Interfase

74. Resolvedores en GAMS Resolvedores en GAMS
Tipos de Problemas Tipos de Problemas
Algoritmos Algoritmos
de Solución de Solución

75. GAMS: Ejemplo 1 GAMS: Ejemplo 1
W
1

y
1

W
1

y
0
= 0
Q=1000 lb/hr x
F
= 0.2
Q=1000 lb/hr
x
1

Etapa de Extracción
()
1 1
1
1
1
+ −
=
x H
Hx
y
1 1
Wy Qx Qx
F
+ =
()
1 1
W x xQ Max
F
λ− −
05.0=λ
2.1=H

76. GAMS: Ejemplo 2 GAMS: Ejemplo 2
z
A
= 0.6
z
B
= 0.3
z
C
= 0.1
F = 1000 Kmol/hr
x
D
A
= 0.8
q
z
N
jj
j j
− =
−
∑
=
1
1
θ α
α
min
1
1R
x
N
jj
D
j j
+=
−
∑
=
θ α
α
∑
=
=
N
j
D
j
x
1
1
0.1=
CC
α
0.1=q
3.2=
AC
α
3.1=
BC
α

77. Algunas Aplicaciones en Algunas Aplicaciones en
Ingeniería Química Ingeniería Química

78. D, Pureza
Alimentación
¿ Cómo separar una mezcla ABC ? ¿ Cómo separar una mezcla ABC ? ABC
A
BC
B
C
ABC
C
AB
A
B
Optimización de Columnas
y
Optimización de Columnas y
Secuencias de Destilación Secuencias de Destilación
Diseño Óptimo de Diseño Óptimo de
Columnas Columnas
1)1)
2)2)
Minimizar Costo Minimizar Costo
N=? R=? P=? N=? R=? P=?

79. 9Supone separaciones del 100% (Sharp Sharpsplits splits)
9Supone que las cargas térmicas y costos de inversión son
funciones lineales funciones linealesde la alimentación
9Supone que las cargas de los cambiadores son del mismo
orden de magnitud
Modelo MILP para Modelo MILP para
Secuencias de Separación Secuencias de Separación

k
top
k
Cl∈
k
Cl∈
bot
k
Cl∈
F
i
x
∑
∑ ∈
∈
=
k
top
k
Cl
F
l
Cl
F
l
top
k
x
x
ξ
∑
∑ ∈
∈
=
k
bot
k
Cl
F
l
Cl
F
l
bot
k
x
x
ξ

80. Datos de Caso de Estudio Datos de Caso de Estudio
Sistema
Fijo
α
k

(10
3
$/año)
Variable
β
k

(10
3
$ hr / Kgmol año)
Carga térmica
K
k
(10
6
KJ / Kgmol)
A/BCD 145 0.42 0.028 AB/CD 52
0.12
0.042
ABC/D 76 0.25 0.054
A/BC 125 0.78 0.024
AB/C 44 0.11 0.039
B/CD 38 0.14 0.040
BC/D 66 0.21 0.047
A/B 112 0.39 0.022
B/C 37 0.08 0.036
C/D 58 0.19 0.044
Costos de utilidades: Costos de utilidades:
Agua de enfriamiento: CW = 1.3 (103$ hr/ 106 KJ año)
Vapor: CH = 34 (103$ hr/ 106 KJ año)
Mezcla Cuaternaria ABCD Mezcla Cuaternaria ABCD
F=1000 Kmol/hr: 15% A, 30% B, 35% C, 20% D

81. Superestructura con Superestructura con
4 Componentes 4 Componentes
y
10

y
9

y
8

y
7

y
6

y
5

y
4

y
3

y
2

y
1

F
10

F
9

F
8

F
7

F
6

F
5

F
4

F
2

F
3

F
1

F
TOT

AB/CD
AB/C A/BC
B/CD BC/D
ABCD
A/BCD ABC/D
C/D B/C A/B
Superestructura Superestructura

82. Modelo Modelo
Factores de separación
ξ
1
A
=0.15
ξ
6
A

=0.188
ξ
1
BCD

=0.85 ξ
6
BC

=0.812
ξ
2
AB

=0.45 ξ
7
AB

=0.5625
ξ
2
CD

=0.55 ξ
7
C

=0.437
ξ
3
ABC

=0.8 ξ
8
C

=0.636
ξ
3
D

=0.2 ξ
8
D

=0.364
ξ
4
B

=0.353 ξ
9
B

=0.462
ξ
4
CD

=0.647 ξ
9
C

=0.538
ξ
5
BC

=0.765 ξ
10
A

=0.333
ξ
5
D

=0.235
ξ
10
B
=0.667

3 2 1
1000F F F F
TOT
+ + = = 0 85.0
1 5 4
= − +F F F
0 8.0
3 7 6
= − +F F F
0 563.0 45.0
7 2 10
= − −F F F
0 812.0 765.0
6 5 9
= − −F F F
0 647.0 55.0
4 2 8
= − −F F F
10 ,..., 1 1,0 0 0 1000= = ≥ ≤ −k y F y F
k k k k
10 ,..., 1= =k FK Q
k k k
()
()
∑ ∑
= =
+ + + =
10
1
10
1
3.1 34 min
k
k
k
k k k k
Q F y Cβ α
Balance Global Balance Global
Mezclas Intermedias Mezclas Intermedias
BCDBCD
ABCABC
ABAB
BCBC
CDCD
Flujos ( Flujos (BigBig--M)M)
Cargas Térmicas Cargas Térmicas
Función Objetivo Función Objetivo

83. h1 h2
c1 c2
500 °K
418 °K
375 °K
310 °K
305 °K
298 °K
?
Síntesis de Redes de Síntesis de Redes de
Intercambio de Calor Intercambio de Calor

84. Estrategia de Optimización Simultánea Estrategia de Optimización Simultánea

Stage 2
Stage 1
H2-C2
H2-C2 H2-C1
H2-C1
H1-C2
H1-C2
H1-C1
H1-C1
C2 C1
H2 H1
Modelo MINLP Modelo MINLP
(SYNHEAT) (SYNHEAT)

85. () ()
∑∑
∑∑
∈∈
∈∈
∈ + = −
∈ + = −
ST kHPi
j ijk j j j
ST kCPj
i ijk i i i
CP j qhu q F TIN TOUT
HP i qcu q F TOUT TIN
,
,
() ()
∑
∑ ∈
+
∈
+
∈ ∈ = −
∈ ∈ = −
HP i
ijk j kj jk
CP j
ijk i ki ik
CP j ST k q F t t
HP i ST k q F t t
, ,
, ,
1 ,
1 ,
CP j TIN t
HP i TIN t
j NOK j
i i
∈ =
∈ =
+1 ,
1,
,
CP j t TOUT
HP i t TOUT
CP j ST k t t
HP i ST k t t
j j
NOK i i
kj jk
ki ik
∈ ≥
∈ ≤
∈ ∈ ≥
∈ ∈ ≥
+
+
+
,
,
, ,
, ,
1,
1 ,
1 ,
1 ,
(
)
()
CP j qhu Ft TOUT
HP i qcu F TOUT t
j j j j
i i i NOK i
∈ = −
∈ = −
+
,
,
1,
1 ,
1,0 , ,
,0
,0
, , ,0
=
∈ ≤ Ω−
∈ ≤ Ω−
∈ ∈ ∈ ≤ Ω−
j i ijk
j j
i i
ijk ijk
zhu zcu z
CP j zhu qhu
HP i zcu qcu
ST kCP j HP i z q
CP j zhu t TOUT dthu
HP i zcu TOUT t dtcu
CP j HP iST k z t t dt
CP j HP iST k z t t dt
j j hu j
i cu NOK i i
ijk kj ki kij
ijk jk ik ijk
∈ −Γ+ − ≤
∈ −Γ+ − ≤
∈ ∈ ∈ −Γ+ − ≤
∈ ∈ ∈ −Γ+ − ≤
+
+ + +
), 1(
), 1(
, , ), 1(
, , ), 1(
1,
1 ,
1, 1, 1,
MODELO MODELO
Balance de calor total para cada corriente:
Balance de calor para cada etapa:
Asignación de las temperaturas de entrada a la
superestructura:
Factibilidad de temperaturas:
Carga de servicios de enfriamiento y
calentamiento:
Restricciones lógicas:
Cálculo de las diferencias de
temperaturas:

86. H
T
3

T
2

T
1

d
4

d
3

d
2

d
1

Demand
T
4

La Producción del Petróleo es un Problema La Producción del Petróleo es un Problema
Multiperiódico Multiperiódico




























































































































































































































































































































3200
3100
3000
2900
2800
2700
2600
2500
JanMar MayJu lSep Nov Jan
Month
Thousands of barrels/day































Planeación de la Planeación de la
Producción Producción

87. well bore storage
well head
reservoir
well bore
oil
flow

oil flow
Geological Properties:
permeability
thickness
porosity
etc.

La extracción produce una disminución de la presión del La extracción produce una disminución de la presión del
pozo con el tiempo pozo con el tiempo
p
up
p
lowp
w
t
s
t t
q
t
s
p
flow
p
shut

88. El tiempo de operaci El tiempo de operacióón H es dividido en NP periodos n H es dividido en NP periodos
de tiempo. Dadas las demandas de producci de tiempo. Dadas las demandas de produccióón del n del
petr petróóleo en cada periodo de tiempo y las constantes de leo en cada periodo de tiempo y las constantes de
caracterizaci caracterizacióón de los pozos, determinar: n de los pozos, determinar: ••Los perfiles de producci Los perfiles de produccióón yn y
••Los tiempos operaci Los tiempos operacióón de cada pozo n de cada pozo en cada periodo de tiempo. en cada periodo de tiempo.
Modelos de Modelos de
Programación Mixta Programación Mixta--
Entera Entera

89. Modelo MILP Modelo MILP
(
)Ty Ty Tq Minimize
ij ij ij
ij ij ij ij ij ij∑∑ ∑∑ ∑∑
− + +1α δ γ
∑
∈∀ ≥
i
j ij
Pj d Tq
()
[]
{}
() []
{}
()
PjWi y c T cq I
PjWi c T cq D
PjWi
p I p
p p
W
p I p
I p p
W
Y
D p p
Y
ij
s
i ij
ij ij
up
i ij
in
ij
up
i
f
ij
ij
up
i ij
in
ij
ij
in
ij
f
ij
ij
ij
ij
in
ij
f
ij
ij
∈ ∈∀ − + =
∈ ∈∀ + =
∈ ∈∀
























> +
= ∨










≤ +
+ =
¬
∨





− =
, 1 ln
, ln
,
2 1
2 1
2 1
()
[]
{}
(
)
PjWi q q
PjWi p p c T c q
ij ij
low
i
in
ij ij
∈ ∈∀ ≤
∈ ∈∀ − = +
,
, ln
max
2 1
max
(
)
PjWi q q
PjWi y q yq q
low
ij
ij
low
ij
up
i ij
∈ ∈∀ ≥
∈ ∈∀ − + ≤
,
, 1
PjWi p p
f
ij
in
ij
∈ ∈∀ =
−
,
1

90. Gráficas de Gráficas de Gant Gant

Centrífuga Reactor 2 Reactor 1 Mezclador
4
4
4
4
20
20
20
20
8
8
8
8
Producto A
¾¾
Determinar el Tamaño y número de unidades paralelas Determinar el Tamaño y número de unidades paralelas
¾¾
Determinar la Secuenciación de las unidades Determinar la Secuenciación de las unidades
Calendarización de Calendarización de
Procesos por Lotes Procesos por Lotes

91. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 1
CCóóddiiggoo GGAAMMSS

El código de GAMS se puede escribir con cualquier procesador de texto o a
través de la interfase de GAMS. Si se utilizan procesadores especializados como
Word, FrameMaker, PageMaker, etc., asegúrese de guardar el archivo sin
formato (como texto, código ASCII).
Los archivos de GAMS deberán tener la extensión *
.gms
Luego de la solución de algún modelo, GAMS crea un archivo de resultados
también en formato de texto y con el mismo nombre que el archivo del código,
pero con extensión *
.lst

Como regla general, un modelo de GAMS debe contener las siguientes partes
(se muestra un caso ilustrativo):
1) Título
$TITLE MULTIPRODUCTO

2) Declaración de Conjuntos
SETS
J COMPONENTES /1*3/

3) Declaración de Parámetros
PARAMETERS SA, SB, SC;

4) Declaración de Variables (positivas y generales)
VARIABLES P;
POSITIVE VARIABLES X7, X8, X9, X10, X11, X12;

5) Declaración de Ecuaciones
EQUATIONS RES1, RES2, RES3, INE1, INE2, INE3,OBJ;

6) Ecuaciones del Sistema
RES1.. X11 =E= 0.667*X8 + 0.667 *X9 + 0.5*X10;

92. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 2
Note que el identificador de la ecuación va precedido de dos puntos. En las
ecuaciones el símbolo =E= significa igual, =G= significa mayor que y =L=
significa menor que.

7) Definición de una función objetivo (“Dummy” o verdadera)
OBJ.. P =E= 0.025*X8 + 0.028*X9 + 0.028*X10 - 0.015*X11 -
0.02*X12 - 0.025*X7;

8) Establecimiento de las ecuaciones que componen un modelo en
particular
MODEL PLANTAS /ALL/;

9) Valores de parámetros, estimados iniciales, límites de las variables
SA = 40000;
TETA.L('1')= 1.05;

10) Llamado a la técnica de solución de acuerdo al tipo de problema
SOLVE PLANTAS USING MIP MAXIMIZING P;

93. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 3
EEjjeemmppllooss IIlluussttrraattiivvooss ddeell UUssoo ddee GGAAMMSS

1. Resolver el problema de programación lineal de la planta multiproducto que
se desarrolló en clase. Recodar que las ecuaciones son:
25000
30000
40000
333.0
167.0333
.0333.0
5.0667.0667.0
7
12
11
107
109812
109811
≤
≤
≤
=
++=
++=
x
x
x
xx
x
xxx
xxxx


Mientras que la función objetivo está dada por:
712111098
025.002.0015.0028.0028.0025.0 xxxxxxP −−−++=

94. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 4
CCóóddiiggoo GGAAMMSS ddeell EEjjeemmpplloo 11
$TITLE MULTIPRODUCTO
*
*DEFINICION DE VARIABLES, PARAMETROS Y ECUACIONES
*

VARIABLES P;

POSITIVE VARIABLES X7, X8, X9, X10, X11, X12;
*
* DATOS CONOCIDOS
*
PARAMETERS SA, SB, SC;
*
*ECUACIONES
*
EQUATIONS RES1, RES2, RES3, INE1, INE2, INE3,OBJ;

*
* DEFINICION DE LAS ECUACIONES QUE FORMAN PARTE DEL MODELO
*
RES1.. X11 =E= 0.667*X8 + 0.667 *X9 + 0.5*X10;
RES2.. X12 =E= 0.333*X8 + 0.333*X9 + 0.167 *X10;
RES3.. X7 =E= 0.333*X10;
INE1.. X11 =L= SA;
INE2.. X12 =L= SB;
INE3.. X7 =L= SC;
OBJ.. P =E= 0.025*X8 + 0.028*X9 + 0.028*X10 - 0.015*X11 -
0.02*X12 - 0.025*X7;

MODEL PLANTAS /ALL/;

*
* ASIGNACION DE VALORES A LOS PARAMETROS
*
SA = 40000;
SB = 30000;
SC = 25000;

OPTION LIMROW=0;
OPTION LIMCOL=0;
*
* LLAMADO A LA TECNICA DE SOLUCION
*
SOLVE PLANTAS USING MIP MAXIMIZING P;

95. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 5
RReessuullttaaddooss GGAAMMSS ddeell EEjjeemmpplloo 11
4 *DEFINICION DE VARIABLES, PARAMETROS Y ECUACIONES
5 *
6
7 VARIABLES P;
8
9 POSITIVE VARIABLES X7, X8, X9, X10, X11, X12;
10 *
11 * DATOS CONOCIDOS
12 *
13 PARAMETERS SA, SB, SC;
14
15 *
16 *ECUACIONES
17 *
18 EQUATIONS RES1, RES2, RES3, INE1, INE2, INE3,OBJ;
19
20
21 *
22 * DEFINICION DE LAS ECUACIONES QUE FORMAN PARTE DEL MODELO
23 *
24 RES1.. X11 =E= 0.667*X8 + 0.667 *X9 + 0.5*X10;
25 RES2.. X12 =E= 0.333*X8 + 0.333*X9 + 0.167 *X10;
26 RES3.. X7 =E= 0.333*X10;
27 INE1.. X11 =L= SA;
28 INE2.. X12 =L= SB;
29 INE3.. X7 =L= SC;
30 OBJ.. P =E= 0.025*X8 + 0.028*X9 + 0.028*X10 - 0.015*X11 -
0.02*X12 - 0.025*X7;
31
32 MODEL PLANTAS /ALL/;
33
34 *
35 * ASIGNACION DE VALORES A LOS PARAMETROS
36 *
37 SA = 40000;
38 SB = 30000;
39 SC = 25000;
40
41 OPTION LIMROW=0;
42 OPTION LIMCOL=0;
43
44 *
45 * LLAMADO A LA TECNICA DE SOLUCION
46 *
47 SOLVE PLANTAS USING MIP MAXIMIZING P;

MODEL STATISTICS

BLOCKS OF EQUATIONS 7 SINGLE EQUATIONS 7

96. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 6
BLOCKS OF VARIABLES 7 SINGLE VARIABLES 7
NON ZERO ELEMENTS 20

GENERATION TIME = 0.000 SECONDS 1.4 Mb WIN200- 121

EXECUTION TIME = 0 .000 SECONDS 1.4 Mb WIN200- 121

S O L V E S U M M A R Y

MODEL PLANTAS OBJECTIVE P
TYPE MIP DIRECTION MAXIMIZE
SOLVER OSL2 FROM LINE 47

**** SOLVER STATUS 1 NORMAL COMPLETION
**** MODEL STATUS 1 OPTIMAL
**** OBJECTIVE VALUE 705.1354

RESOURCE USAGE, LIMIT 0.070 1000.000
ITERATION COUNT, LIMIT 3 10000

OSL Version 2 Mar 21, 2001 WIN.O2.O2 20.0 007.043.039.WAT (Jan )

Work space allocated -- 0.09 Mb

LOWER LEVEL UPPER MARGINAL

---- EQU RES1 . . . - 0.032
---- EQU RES2 . . . - 0.020
---- EQU RES3 . . . - 0.026
---- EQU INE1 - INF 40000.000 40000.000 0.017
---- EQU INE2 - INF 13766.923 30000.000 .
---- EQU INE3 - INF 25000.000 25000.000 0.001
---- EQU OBJ . . . 1.000

LOWER LEVEL UPPER MARGINAL

---- VAR P - INF 705.135 +INF .
---- VAR X7 . 25000.000 +INF .
---- VAR X8 . . +INF - 0.003
---- VAR X9 . 3691.848 +INF .
---- VAR X10 . 75075.075 +INF .
---- VAR X11 . 40000.000 +INF .
---- VAR X12 . 13766.923 +INF .


**** REPORT SUMMARY : 0 NONOPT
0 INFEASIBLE
0 UNBOUNDED

97. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 7
2. Para el sistema de extracción mostrado en la Figura, utilice el sistema de
modelación GAMS para determinar los valores de las variables W
1 y x1 que
maximizan la función:

donde
λ = 0.05. Considere que la relación de equilibrio entre y 1 y x 1 está
dada por la expresión:
Use un valor de H = 1.2. Note también que el balance de masa en el
sistema resulta en la ecuación:

11
WyQxQx
F
+=




Figura


W1
y1
W1
y0 = 0
Q=1000 lb/hr
xF = 0.2
Q=1000 lb/hr
x1
Etapa de
Extracción
( )
11
WxxQ
F
λ−−
( )11
1
1
1
+−
=
xH
Hx
y

98. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 8
CCóóddiiggoo GGAAMMSS ddeell EEjjeemmpplloo 22
$TITLE EXTRACCION
$OFFSYMXREF
$OFFSYMLIST
*
*DEFINICION DE VARIABLES, PARAMETROS Y ECUACIONES
*
VARIABLES F;

POSITIVE VARIABLES X1, Y1, W1;

PARAMETERS Q, XF, LAMBDA, H;

EQUATIONS MASBAL, EQUILIBRIO, OBJ;

*
*ECUACIONES
*
MASBAL.. Q * XF =E= Q * X1 + W1 * Y1;
EQUILIBRIO.. Y1 =E= (H * X1)/(((H - 1.0) * X1) + 1.0);
OBJ.. F =E= Q * ( XF - X1) - LAMBDA * W1;

*
* DEFINICION DE LAS ECUACIONES QUE FORMAN PARTE DEL MODELO
*
MODEL EXTRACTOR /ALL/;
*
* ASIGNACION DE VALORES A LOS PARAMETROS
*

Q = 1000;
XF = 0.2;
LAMBDA = 0.05;
H = 1.2;
*
* LIMITES Y VALORES INICIALES
*

Y1.L = 0.1;
Y1.UP = 1.0;
X1.L = 0.1;
X1.UP = 0.2;
W1.L = 500;
OPTION LIMROW=0;
OPTION LIMCOL=0;
*
* LLAMADO A LA TECNICA DE SOLUCION
*
SOLVE EXTRACTOR USING NLP MAXIMIZING F;

99. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 9
RReessuullttaaddooss GGAAMMSS ddeell EEjjeemmpplloo 22
COMPILATION TIME = 0.000 SECONDS 0.7 Mb WIN194-
116
Model Statistics SOLVE EXTRACTOR USING NLP FROM LINE 55




MODEL STATISTICS

BLOCKS OF EQUATIONS 3 SINGLE EQUATIONS 3
BLOCKS OF VARIABLES 4 SINGLE VARIABLES 4
NON ZERO ELEMENTS 8 NON LINEAR N- Z 3
DERIVATIVE POOL 5 CONSTANT POOL 10
CODE LENGTH 40


GENERATION TIME = 0.110 SECONDS 1.9 Mb WIN194-
116


EXECUTION TIME = 0.110 SECONDS 1.9 Mb WIN194-
116


S O L V E S U M M A R Y

MODEL EXTRACTOR OBJECTIVE F
TYPE NLP DIRECTION MAXIMIZE
SOLVER CONOPT FROM LINE 55

**** SOLVER STATUS 1 NORMAL COMPLETION
**** MODEL STATUS 2 LOCALLY OPTIMAL
**** OBJECTIVE VALUE 58.1881

RESOURCE USAGE, LIMIT 0.391 1000.000
ITERATION COUNT, LIMIT 15 10000
EVALUATION ERRORS 0 0


C O N O P T Wintel version 2.043C- 005-039
Copyright (C) ARKI Consulting and Development A/S
Bagsvaerdvej 246 A
DK- 2880 Bagsvaerd, Denmark

Using default control program.


** Optimal solution. Reduced gradient less than tolerance.

100. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 10

CONOPT time Total 0.219 seconds
of which: Function evaluations 0.051 = 23.2%
Derivative evaluations 0.000 = 0.0%

Work length = 0.05 Mbytes
Estimate = 0.05 Mbytes
Max used = 0.04 Mbytes

LOWER LEVEL UPPER MARGINAL

---- EQU MASBAL - 200.000 - 200.000 - 200.000 0.463
---- EQU EQUILIBRIO . . . 464.178
---- EQU OBJ 200.000 200.000 200.000 1.000

LOWER LEVEL UPPER MARGINAL

---- VAR F - INF 58.188 +INF .
---- VAR X1 . 0.092 0.200 - 2.233E- 6
---- VAR Y1 . 0.108 1.000 .
---- VAR W1 . 1002.840 +INF .


**** REPORT SUMMARY : 0 NONOPT
0 INFEASIBLE
0 UNBOUNDED
0 ERRORS


EXECUTION TIME = 0.060 SECONDS 0.7 Mb WIN194-
116

101. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 11
q
z
N
j j
jj
−=
−∑
=
1
1θα
α
min
1
1R
x
N
j j
D
jj
+=
−∑
=θα
α
∑
=
=
N
j
D
j
x
1
1
3. Considere la separación de la mezcla ternaria que se muestra en la figura.
En tal sistema, A es el componente clave ligero (
αA,C = 2.3), C es el
componente clave pesado (
αC,C = 1.0) y B es el componente intermedio
(
αB,C=1.3). Las siguientes ecuaciones permiten la determinación del valor
mínimo de la razón de reflujo y de las composiciones en el destilado de los
componentes B y C a reflujo mínimo.


(1)

Ec. De
Underwood
(2)

(3)


Utilice el sistema de modelación GAMS para determinar las dos raíces para
θ
en la Ecuación (1), el valor mínimo de la relación de reflujo y los valores de
x
D
B
y x
D
C
. Suponga que q = 1.0.




zA = 0.6
zB = 0.3
z
C = 0.1
F = 1000 Kmol/hr
x
D
A = 0.8

102. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 12

CCóóddiiggoo GGAAMMSS ddeell EEjjeemmpplloo 33
$TITLE UNDERWOOD

$OFFSYMXREF
$OFFSYMLIST

*
*DEFINICION DE VARIABLES, PARAMETROS Y ECUACIONES
*

SETS
J COMPONENTS /1*3/,
I ROOTS /1*2/;
VARIABLES C;

POSITIVE VARIABLES TETA(I), XD(J), RMIN;

PARAMETERS ALFA(J), Z(J), Q;


*
*ECUACIONES
*

EQ1(I).. SUM(J,((ALFA(J)*Z(J))/(ALFA(J)- TETA(I))))=E= 1.0 - Q;
EQ2(I).. SUM(J,((ALFA(J)*XD(J))/(ALFA(J)- TETA(I))))=E= RMIN + 1.0;
EQ3.. SUM(J,XD(J))=E= 1.0;
OBJ.. C =E= 1.0;

*
* DEFINICION DE LAS ECUACIONES QUE FORMAN PARTE DEL MODELO
*

MODEL UNDEQN /ALL/;

*
* ASIGNACION DE VALORES A LOS PARAMETROS
*

ALFA('1')=2.3;
ALFA('2')=1.3;
ALFA('3')=1.0;

Z('1')=0.6;
Z('2')=0.3;
Z('3')=0.1;

Q = 1.0;

103. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 13

*
* VALORES INICIALES Y LIMITES INFERIOR Y SUPERIOR
*

TETA.L('1')= 1.05;
TETA.UP('1')= 1.299;
TETA.LO('1')= 1.001;
TETA.L('2')= 2.1;
TETA.UP('2')= 2.299;
TETA.LO('2')= 1.301;
XD.L('2')=0.1;
XD.UP('2')=1.0;
XD.L('3')=0.01;
XD.UP('3')=1.0;
XD.FX('1')=0.8;

OPTION LIMROW=0;
OPTION LIMCOL=0;
*
* LLAMADO A LA TECNICA DE SOLUCION
*

RReessuullttaaddooss GGAAMMSS ddeell EEjjeemmpplloo 33

COMPILATION TIME = 0.050 SECONDS 0.7 Mb WIN200-
121
Model Statistics SOLVE UNDEQN USING NLP FROM LINE 72




MODEL STATISTICS

BLOCKS OF EQUATIONS 4 SINGLE EQUATIONS 6
BLOCKS OF VARIABLES 4 SINGLE VARIABLES 7
NON ZERO ELEMENTS 16 NON LINEAR N- Z 10
DERIVATIVE POOL 8 CONSTANT POOL 12
CODE LENGTH 207


GENERATION TIME = 0.050 SECONDS 1.9 Mb WIN200-
121


EXECUTION TIME = 0.110 SECONDS 1.9 Mb WIN200-
121

S O L V E S U M M A R Y

104. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 14

MODEL UNDEQN OBJECTIVE C
TYPE NLP DIRECTION MINIMIZE
SOLVER CONOPT FROM LINE 72

**** SOLVER STATUS 1 NORMAL COMPLETION
**** MODEL STATUS 2 LOCALLY OPTIMAL
**** OBJECTIVE VALUE 1.0000

RESOURCE USAGE, LIMIT 0.488 1000.000
ITERATION COUNT, LIMIT 2 10000
EVALUATION ERRORS 0 0


C O N O P T Windows NT/95/98 version 2.043F- 008-043
Copyright (C) ARKI Consulting and Development A/S
Bagsvaerdvej 246 A
DK- 2880 Bagsvaerd, Denmark

Using default control program.


** Optimal solution. There are no superbasic variables.


CONOPT time Total 0.160 seconds
of which: Function evaluations 0.000 = 0.0%
Derivative evaluations 0.000 = 0.0%

Work length = 0.05 Mbytes
Estimate = 0.05 Mbytes
Max used = 0.04 Mbytes


---- EQU EQ1

LOWER LEVEL UPPER MARGINAL

1 . . . EPS
2 . . . EPS


---- EQU EQ2

LOWER LEVEL UPPER MARGINAL

1 1.000 1.000 1.000 EPS
2 1.000 1.000 1.000 EPS

105. GAMS Instituto Tecnológico de Celaya

Departamento de Ingeniería Química 15
LOWER LEVEL UPPER MARGINAL

---- EQU EQ3 1.000 1.000 1.000 EPS
---- EQU OBJ 1.000 1.000 1.000 1.000

LOWER LEVEL UPPER MARGINAL

---- VAR C - INF 1.000 +INF .


---- VAR TETA

LOWER LEVEL UPPER MARGINAL

1 1.001 1.039 1.299 .
2 1.301 1.539 2.299 .


---- VAR XD

LOWER LEVEL UPPER MARGINAL

1 0.800 0.800 0.800 EPS
2 . 0.167 1.000 .
3 . 0.033 1.000 .

LOWER LEVEL UPPER MARGINAL

---- VAR RMIN . 0.450 +INF .


**** REPORT SUMMARY : 0 NONOPT
0 INFEASIBLE
0 UNBOUNDED
0 ERRORS


EXECUTION TIME = 0.000 SECONDS 0.7 Mb

106. Introducción a la Optimización Introducción a la Optimización
Bajo Incertidumbre Bajo Incertidumbre

107. Reflexión Reflexión
¾
Compañía petrolera: ¿cuál será el precio y la
demanda del petróleo en 6 meses?
¾
En un proceso continuo
9
Existirá variación en las demandas del producto
9
Calidad de Servicios?
9
Cadena de Suministro de Materias Primas?
El futuro no puede pronosticarse con exactitud El futuro no puede pronosticarse con exactitud
Necesario considerar incertidumbre en Necesario considerar incertidumbre en algun algunos os
procesos: procesos:Procesos Estocásticos Procesos Estocásticos

108. Tipos de Problemas de Optimización Tipos de Problemas de Optimización
Estocástica Estocástica
**
Programación Lineal Estocástica ( Programación Lineal Estocástica (SLPSLP))
**
Programación Mixta Entera Lineal Estocástica Programación Mixta Entera Lineal Estocástica
((SMILP SMILP))
**
Programación No Lineal Estocástica ( Programación No Lineal Estocástica (SNLP SNLP))
**
Programación Mixta Entera No lineal Estocástica Programación Mixta Entera No lineal Estocástica
((SMINLP SMINLP))

109. Otra Clasificación: Tipos de Otra Clasificación: Tipos de
Problemas Bajo Incertidumbre Problemas Bajo Incertidumbre
¾
“Wait and see Wait and see” : Esperar ocurrencia de un
eventoincierto y entonces optimizar
¾
“Here and now” Optimización inmediata
en base a alguna medida de probabilidad
La mayoría de los algoritmos de La mayoría de los algoritmos de
solución utilizan ambas estrategias solución utilizan ambas estrategias

110. Problemas Estocásticos de 2 Etapas Problemas Estocásticos de 2 Etapas
¾
Idea fundamental: Recurso Recurso
¾
Recurso en 2 Etapas
Primera Etapa Primera Etapa
Seleccione la variable de decisión
x
Segunda Etapa Segunda Etapa
Ocurrencia de un evento incierto
Tomar una acción correctiva (recurso)
y

111. Un Ejemplo Un Ejemplo
El problema del vendedor de El problema del vendedor de
periódicos periódicos
¾
El vendedor compra xperiódicos a un precio c
¾
Entonces vende tantos periódicos como puede a un precio q,
el exceso representa una pérdida
¾
La demanda del periódico cambia día a día (incertidumbre)
¾
Cuando la demanda se conoce, se calculan las ganancias Cuántos periódicos debe comprar el vendedor para maximizar
sus ganancias ?

112. El Problema del Vendedor El Problema del Vendedor
de Periódicos de Periódicos
Primera Etapa Primera Etapa
Seleccionar el número de
periódicos a comprar x
Segunda Etapa Segunda Etapa
Ocurrencia de un evento incierto(demanda)
Las ganancias se calculan
Se toma una acción correctiva (recurso)

113. Programación Estocástica Lineal Programación Estocástica Lineal
con Recurso con Recurso

114. Representación Matemática Estándar Representación Matemática Estándar
para Problemas Lineales ( para Problemas Lineales (SLPwR SLPwR))
()
xQxc
T
+ min
b xA ts= ..
0≥x
() ()
y q xQ
T
ω ωmin ,=
() () ()
x T h y Wtsω ω ω− = ..
0≥y
Primera
Etapa
Segunda
Etapa
Función de
Recurso
Matriz de
Recurso
Evento
incierto
() ( )
[]
ω
ω
,xQE xQ=
dondey

115. Clases ClasesEspeciales de Problemas Especiales de Problemas Recurso
Completo
Recurso
Simple
()
W W=ω
0 ,≥ ∀ =y z z yW
()
II W− =,
() ()
x T h y yω ω− = −
− +
Recurso
Fijo

116. ()
xQ xc
T
+ min
θ+xc
T
min
()
θ≤xQ ts..
() ( )
[]
ω
ω
,xQE xQ=
Reformulación Reformulación
donde
Primera
Etapa
bxA ts= ..
0≥xbxA=
0≥x
() ()
y q xQ
T
ω ωmin ,=
xTh yWts− = ..
0≥y

117. Dos Tipos de Cortes en Dos Tipos de Cortes en
Algoritmos SLP Algoritmos SLP
Corte de Optimalidad Corte de Optimalidad
Corte de Factibilidad Corte de Factibilidad
•Asegura que los valores de
x
(obtenidos en la primera
etapa) no propician infactibilidades en la segunda etapa
•Aproximación Lineal de Q(x)
•Basado en el problema dual: proporciona límite inferior
a Q(x)

118. Teorema de la Dualidad (LP) Teorema de la Dualidad (LP)
Primo Dual
yc
T
min
b yA ts= ..
0≥y
b
T
π max
c A ts
T
≤ π..
Multiplicadores
de Lagrange
•Si el dual no es acotado no es acotado, el primo es infactible infactible
• Si el dual es infactible, el primo no es acotado
• El valor de la función objetivo del problema dual dualprovee
una cota inferior cota inferiorpara la función objetivo del problema
primo primo. En problemas convexos sus valores son iguales.

119. Problema de la Segunda Etapa Problema de la Segunda Etapa
Primo Dual
yq
T
min
xTh yWts− = ..
0≥y
()
xTh
T
− π max
q W ts
T
≤ π..
Multiplicadores
de Lagrange

120. Ejemplo Ilustrativo Ejemplo Ilustrativo
()
[]
ω
ω
, 75.0 minxQE x+ −
5 ..≤x ts
0≥x
()
4 3 2 1
3 min ,y y y y xQ+ + + − =ω
x y y y y ts21 ..
4 3 2 1
+ = + − + −ω
x y y y y41 1
4 3 2 1
+ += − + + −ω
0 ,,,
4 3 2 1
≥yyyy

121. Ejemplo Ilustrativo Ejemplo Ilustrativo
[]
75.0−=c
[]5=b
[]1=A











−
=
1
1
3
1
q












=
4
3
2
1
y
y
y
y
y






− −
− −
=
1 111
11 11
W
()






+
=
ω
ω
ω
1
h








−
−
=
4
1
2
1
T
Recurso Recurso
Fijo Fijo
≤→α
=→α
[]
x x=

122. Dual del Problema de la Segunda Dual del Problema de la Segunda
Etapa Etapa Multiplicadores
de Lagrange
()
()
()
x x xQ41 1 21 max ,
2 1
+ + + + =ω π ωπ ω
1 ..
2 1
−≤ − −π π ts 3
2 1
≤ +π π
1
2 1
≤ + −π π
1
2 1
≤ −π π

123. Corte de Optimalidad: Corte de Optimalidad:
Aproximación Aproximación Lineal a Lineal a Q(x) Q(x)
Soporte SoporteLineal Lineal

0 1 2 3 4 5
10

8

6

4

2

0

0 1 2 3 4 5
10

8

6

4

2

0

0 1 2 3 4 5
10

8

6

4

2

0

0 1 2 3 4 5
10

8

6

4

2

0

124. Corte de Optimalidad Corte de Optimalidad
(teorema de la dualidad)
•El valor de la función objetivo del problema de la
segunda etapa en cada iteración ν(tomando x
ν
de la
primera etapa) y para el k-ésimovalor de las variables
inciertas,
ω
k
, es:
Debido a la convexidad
(dual es Límite inferior)
()()( )
ν ν ν
π ωxT h xQ
k k
T
k
k
− = ,
()()
()
xT h xQ
k k
T
k
k
− ≥
ν
π ω,
•Para una función de probabilidad discreta, teniendo el
valor
ω
k
una probabilidad p
k
, el valor esperado de la
función objetivo:
() ()( )
[]
()( )
[]
ν ν ν ν ν
π πxT h p xTh E xQ
k k
T
k
K
k
k
T
− = − =
∑
=1

125. Corte de Optimalidad Corte de Optimalidad
Por lo tanto, debido
a la convexidad
Definiendo
()
()
()
[]
() ()
∑ ∑ ∑
= = =
− = − ≥
K
k
k
T
k k
K
k
k
T
k k k k
T
k
K
k
k
xT p h p xT h p xQ
1 1 1
ν ν ν
π π π
()
∑
=
=
K
k
k
T
k k
h p e
1
ν
π
()
∑
=
=
K
k
k
T
k k
T p E
1
ν
π
()
Ex e xQ−≥
()
xQ≥θ
e Ex≥ +θ
y
Se tiene
y dado que
entonces
Ex e−≥θ

126. Corte de Factibilidad Corte de Factibilidad
se satisfacen. Note: si yes finito, entones q
T
yes
finito y por lo tanto
•La decisión tomada en la primera etapa xν
resulta en un
problema factible en la segunda etapa si existe un vector
finito ytal que las restricciones:
ν
xT h yW− =
0≥y
()
∞<xQ

127. Corte de Factibilidad Corte de Factibilidad
•Para verificar
factibilidad, resolver el
problema:
(
)
− +
+ =y ye z
T
min
ν
xT h y y yW ts− = − +
− +
..
0 ,0 ,0≥ ≥ ≥
− +
y y y
(
)
ν
σxTh
T
− max
0 ..≤ W ts
T
σ
e≤ σ
•Cuyo problema dual
es:
•Note que z>
0. si z=0entonces la segunda etapa es factible
Multiplicadores
de Lagrange

128. Corte de Factibilidad Corte de Factibilidad
•Sin embargo, si z>0 entonces el problema primo:
yq
T
min
ν
xT h yW ts− = ..
0≥y
esinfactible
•Por el teorema de la dualidad: Si el dual no está acotado,
entonces el primo es infactible. Por lo tanto, el dual
:
(
)
ν
πxTh
T
− max
q W ts
T
≤ π ..
no estaríaacotado
no está acotado debido a que
(
)
ν
πxTh
T
− max
()
()
0≥ −xTh
T
ν
σ
Note:

129. Corte de Factibilidad Corte de Factibilidad
•Por lo tanto, para asegurar la factibilidad del primo, la restricción:
debe añadirse
()
()
0≤ −xTh
T
ν
σ
Feasibility Cut
•Si para algún valor k(evento discreto) el primo es infactible,
entonces se define:
()
k
T
T D
ν
σ=
()
k
T
h d
ν
σ=
d xD≥
•Y se incorpora el corte de factibilidad:

130. Algoritmos para Recurso Algoritmos para Recurso
Fijo Fijo
Método Método““
LL--
Shaped Shaped
””
Descomposición Descomposición
Estocástica Estocástica
(SD) (SD)
• Usa función de probabilidad
discreta para ω
• Cálculo exacto del límite
inferior de Q(x) (Corte de Corte de
Optimalidad Optimalidad)
• Muestreo de una función de
probabilidad continua para ω
• Estimación del límite inferior
de Q(x) basado en esperanza
matemática (Corte de Corte de
Optimalidad Optimalidad)

131. Método “L Método “L--Shaped” Shaped”
•Supone una función de probabilidad discreta para
ω
k
•Note la estructura del problema determinístico equivalente:
k
T
k
K
k
k
T
yqp xc
∑
=
+
1
min
b xA ts= ..
xT h yW
k k k
− =
0 ,0≥ ≥
k
y x
K kK1=

A
T
1
W
T
2
W
.
.
.
T
k
… W

A
T
T
1
T
T
2
T
… T
k
T

W
T

W
T

.
.
.
W
T

Estructura del primo
Estructura del Dual

132. Algoritmo “ Algoritmo “LL--Shaped Shaped””
•Paso 0 Haga r = s =
ν
= 0
•Paso 1 Haga
ν
=
ν
+1 y resuelva el problema (Current Problem CP)
θ+ =xc z
T
min
b xA ts= ..
l l
d xD≥
l l
e xE≥ +θ
r lK1= s lK1=
x
ν
y
θ
ν
conforman la solución óptima. Si no hay cortes (iteración
1), haga
θ
ν
=-∞y no la considere en el problema
Corte de Optimalidad
Corte de Factibilidad

133. Algoritmo “ Algoritmo “LL--Shaped Shaped””
Paso 2 Para k=1…K(número de realizaciones de un
evento incierto) resuelva el problema:
Si para algúnkel valor óptimo es z>0 añada uncorte de
factibilidad:
− +
+ =
k
T
k
T
ye ye zmin
ν
xT h y y yW ts
k k k k k
− = − +
− +
..
0 ,0 ,0≥ ≥ ≥
− +
k k k
y y y
()
k
T
k r
T D
ν
σ=
+1
()
k
T
k r
h d
ν
σ=
+1
1 1+ +
≥
r r
d x D
Haga r=r+1 y regrese al Paso 1. De otro modo, vaya al
paso 3.
Multiplicadores
de Lagrange del
problema
anterior

134. Algoritmo “ Algoritmo “LL--Shaped Shaped””
•Paso 3 Para k=1…Kresuelva el problema
Y defina:
Si no haga s=s+1 , añada el corte de optimalidad
k
T
k
yq min
ν
xT h yW
k k k
− =
0≥
k
y
()
∑
=
+
=
K
k
k
T
k k s
h p e
1
1
ν
π
()
∑
=
+
=
K
k
k
T
k k s
T p E
1
1
ν
π
ν ν
ηx E e
s s1 1+ +
− =
si
ν ν
η θ≥
Y regrese el paso 1
x E e
s s1 1+ +
− =θ
Multiplicadores
de Lagrange del
problema
anterior
Pare, x
ν
es la solución óptima

135. Descomposición DescomposiciónEstocástica Estocástica
•Se muestra en cada iteración a partir de una distribución de
probabilidad continua
ω
k
•Cálculo de límite inferior de Q(x) es aproximado
L-Shaped DescomposiciónEstocástica
()
∑
=
+
=
K
k
k
T
k k s
h p e
1
1
ν
π
()
∑
=
+
=
K
k
k
T
k k s
T p E
1
1
ν
π
()
∑
=
=
ν
ν
ν
π
ν
1
1
k
k
T
k
h e
()
∑
=
=
ν
ν
ν
π
ν
1
1
k
k
T
k
T E
1
1
−
−
=
ν ν
ν
ν
k k
e e
1
1
−
−
=
ν ν
ν
ν
k k
E E
k=1…
ν
-1
Actualización:

136. Algoritmo de Descomposición Algoritmo de Descomposición
Estocástica Estocástica
(Higle y Sen) (Higle y Sen)
Recurso completo Recurso completo
•Paso 0 Haga
ν
= 0
,
θ
ν
=-∞Suponer x
1
•Paso 1 Haga
ν
=
ν+1
y genere una observación de las
variables estocásticas mediante muestreo muestreo

137. Algoritmo SD Algoritmo SD
•Paso 2 Determine
θ
ν
(x)(
v
-ésimaaproximación lineal a Q(x) )
a) Resuelva el problema de optimización lineal (dual de segunda
etapa):
(
)
ν
ν ν
πxT h
T
− max
q W ts
T
≤ π ..
ν
π
k
(
)
ν
πxT h
k k
T
− max
q W ts
T
≤ π ..
1 1− =νK k
ν
ν
π
Para obtener(
v
-ésimamuestra y al
v
-ésimovalor del vector
x
)
Similarmente resuelva el problema
v-1
veces:
Para obtener (
k
-ésimamuestra y al
v
-ésimovalor de
x
)

138. Algoritmo SD Algoritmo SD
b) Calcule los coeficientes del
corte de optimalidad corte de optimalidad
()
∑
=
=
ν
ν ν
ν
π
ν
1
1
k
k
T
k
h e
()
∑
=
=
ν
ν ν
ν
π
ν
1
1
k
k
T
k
T E
()
()
∑
=
− = −
ν
ν
π
ν
1
1
k
k k
T
k
v
v
v
v
xT h xE e
c) Actualizar los coeficientes de previos cortes
1
1
−
−
=
ν ν
ν
ν
k k
e e
1
1
−
−
=
ν ν
ν
ν
k k
E E
1 1− =νK k

139. Algoritmo SD Algoritmo SD
Para obtener x
ν
+1
. Vaya al paso 1
•Paso 3 Resuelva el problema de la primera etapa con los cortes
de optimalidad:
ν
θ+xc
T
min
b xA ts= ..
xE e
k k
ν ν
ν
θ−≥
ν ν
ν
θ
k k
exE≥ +
νK1=k
•El algoritmo se detiene si el cambio en la función objetivo es pequeño
()
xQ

140. Un Caso Un Caso
z
Suponga que se tiene un SLPwR con 50 restricciones 50 restriccionesy que
se toman N = 200 N = 200muestras muestrasdel valor de
ω
¾
Es necesario resolver 200 problemas 200 problemasde optimización
correspondientes a la primera etapa. El primero posee 5050
restricciones, el segundo 5151… el último 250 restricciones 250 restricciones
¾
Es necesario resolver el problema de la segunda etapa un
número de veces igual a
20100 20100
¾
El número de restricciones en la segunda etapa no cambia.
=
∑
=
N
i
i
1

141. Implementación del Algoritmo Implementación del Algoritmo
SD: Técnica de Muestreo HSS SD: Técnica de Muestreo HSS
•Monte Carlo Monte Carlopuede presentar valores grandes de
varianza
•HSSHSSpresenta mejores propiedades de uniformidad
HSS Monte Carlo HSS Monte Carlo
0
0.5
1
00.51
X
Y
0
0.5
1
00.51
X
Y

142. Implementación Computacional Implementación Computacional
•Integración del entorno de modelación GAMS, el
código de la técnica de muestreo HSS (FORTRAN) y
un programa en C++ como programa maestro

Sampling
(FORTRAN)
GAMS - OSL GAMS - OSL
C++ Code
1) Generation of an
approximation to Q(x):
sampling and multiple
generation and
solution of LP´s
2) Addition of
optimality cut and
solution to the 1st
stage problem

143. Aplicaciones a Ingeniería Química Aplicaciones a Ingeniería Química

Purchased
power
Fuel
Boiler
P
1

(power)
P
2

(power)
Turbine 1
Condensate
Turbine 2
Pressure
reducing
valve
Pressure
reducing
valve
635 psig stream
195 psig stream
62 psig stream
power
Sistema Turbogenerador Sistema Turbogenerador

144. P
RIMERA
E
TAPA
Segunda Etapa
Caso de Estudio
Renglones Columnas Renglones Columnas
Variables
Estocásticas
Sistema Turbogenerador 1 2 21 28 4
Planeación de una Refinería 4 5 12 13 8
Planeación de una Planta
Petroquímica
1 2 11 15 11

N (M
ISMO
E
RROR
P
ROMEDIO
)
Caso de Estudio
HSS MC
Sistema Turbogenerador 60 140
Planeación de una Refinería 190 275
Planeación de una Planta Petroquímica 175 160

Aplicaciones a Ingeniería Química Aplicaciones a Ingeniería Química

145. Resultados Resultados
0
1
2
3
4
5
6
7
8
020406080100
Iteration
% Error
HSS
MC
1140
1160
1180
1200
1220
1240
1260
1280
0 20406080100
Iteration
Objective
MC
HSSSistema Turbo Generador Sistema Turbo Generador

146. ¿Cómo evaluar si el esfuerzo vale la ¿Cómo evaluar si el esfuerzo vale la
pena? pena? zz
Valor de la Solución Estocástica (VSS) Valor de la Solución Estocástica (VSS):
Diferencia entre el valor obtenido para la función
objetivo respecto del valor obtenido si se usan
valores promedio para incertidumbres
zz
Valor de la Información Perfecta (VPI) Valor de la Información Perfecta (VPI)
Diferencia del resultado con el valor verdadero
luego de la ocurrencia real del evento

147. Caso de Estudio VSS (%) Sistema Turbogenerador 0.48 Planeación de una Refinería 6.85 Planeación de una Planta Petroquímica 2.22
Resultados Resultados

148. Discusión Discusión
zz
A pesar de la limitación acerca de la linealidad de A pesar de la limitación acerca de la linealidad de
las restricciones, existen aplicaciones importantes las restricciones, existen aplicaciones importantes
en planeación y calendarización de procesos en planeación y calendarización de procesos
zz
Extensión a casos entero y no lineal Extensión a casos entero y no lineal
¾¾
BONUS (No lineal) BONUS (No lineal)
¾¾
Desarrollo actual para casos de programación Desarrollo actual para casos de programación
entera entera

149. Programación Estocástica Mixta Programación Estocástica Mixta
Entera Lineal Entera Lineal

150. Surgen Más Clasificaciones Surgen Más Clasificaciones
para Problemas Multi para Problemas Multi--Etapa Etapa
¾¾
Variables Enteras en la Primera Etapa Variables Enteras en la Primera Etapa:
Se utilizan los mismos algoritmos que en
programación lineal estocástica
¾¾
Variables Enteras en la Segunda Etapa: Variables Enteras en la Segunda Etapa:
Se utilizan variaciones en el método de
“branch and bound” para permitir la
adición iterativa de los cortes de
optimalidad y factibilidad

151. Problemas Enteros en la Primera Problemas Enteros en la Primera
Etapa: Aplicaciones a Otras Áreas Etapa: Aplicaciones a Otras Áreas
zz
Seguridad en Redes de Agua Municipales Seguridad en Redes de Agua Municipales
ƒ
Colocación óptima de sensores para disminuir el
porcentaje de la población en riesgo tras un ataque
químico a la red
zz
Localización de Estaciones de Desinfección Localización de Estaciones de Desinfección
ƒ
Colocación óptima de estaciones para conservar
niveles de cloro bajo especificaciones para aguas
municipales

152. Seguridad en Redes de Agua Seguridad en Redes de Agua
Municipales Municipales
()
[]
ω
δ
β
ω
, min
11
xQE x
n
i
n
j
ij
ij
ij
+
∑∑
==
ji n i x x ts
ji ij
≤ − =∀ =,1 1 ..K
{}
Eji x
ij
∈ ∀ ∈, 1,0
() ()
∑∑∑
===
=
n
i
P
p
n
j
ipj ipj
y q xQ
111
min ,ω ω
()
∑
≤ ∈
≤
jiEjjiij
x x
, ,,max
P p n i y ts
ipi
K K1 , 1 1 ..= =∀ =
jp ip ipj
qδω=
()
1 .. ,= ∈ ∀ ≤ −
kjp kj ipj ipk
fts E jk x y y

153. Localización de Estaciones de Desinfección Localización de Estaciones de Desinfección
()
[]
ω
ω
, min
1
xQE xW
b
n
i
ii
+
∑
= ∑
=
≤
b
n
i
b i
n x ts
1
max
..
{}
1,0∈
i
x
()
()
k
i
b
n
i
i
n
k
k
i
i
y q
T
xQ
∑∑
==
∆
=
11
1
min ,ω ω
∑∑
==
≤
b
n
i
i
n
k
j
k
i
km
ij
u y ts
11
..α
k
i
k
i
qω=
∑∑
==
−≤ −
b
n
i
i
n
k
j
k
i
km
ij
y
11
l α
0≤ −
i
k
i
k
i
xY y
0≥
k
i
y
b
n iK1=
i
n kK1=
m
n jK1=
1− + =
α
n M M mK

154. If θ <
Q(x
ν
)
Generate optimality cut
Return to current node
Else
Go to pendant node


Branch
Check integrality
Root
Node

Check feasibility
Add Cut
Check integrality
Check feasibility
A
dd Cut
z=
θ=


Compute Q(x
ν
)
Update z
∞
∞−
Programación Estocástica Mixta Programación Estocástica Mixta--
Entera Lineal (Variables Enteras en Entera Lineal (Variables Enteras en
la Segunda Etapa) la Segunda Etapa)

155. Otro Tipo de Problemas Otro Tipo de Problemas
Estocásticos Estocásticos

156. Chance Constrained Chance ConstrainedProgramming Programming
z
Hay algunas restricciones para las que sólo existe cierta
probabilidad de que se tengan que satisfacer
z
Tales restricciones deben incluir las variables inciertas
dentro de términos lineales
2 1
4x x Z Minimize− =
()
0 ,
4
7
3
8 2
2 1
2 1
2
2 1
≥
≤ −
≤ ≤
≤ +
xx
x x
u xP
x x
Sujeto a: Sujeto a:
2 1
4x x Z Minimize− =
0 ,
4
6
8 2
2 1
2 1
2
2 1
≥
≤ −
≤
≤ +
xx
x x
x
x x
Sujeto a: Sujeto a:

157. Chance Constrained Chance ConstrainedProgramming Programming

158. Introducción a la Optimización Introducción a la Optimización
Multiobjetivo Multiobjetivo

159. Optimización Multiobjetivo (MOP) Optimización Multiobjetivo (MOP)
¾
Prácticamente en cualquier área y en una variedad de
contextos se presentan problemas con múltiples objetivos
que se contraponen entre sí
¾
A este tema se le conoce también como Optimización Optimización
Vectorial Vectorialy se clasifica en términos del tipo de variables y
restricciones ( MOLP MOLP, MONLP MONLP, etc.)
) , , ,(
3 2 1k
Z Z ZZ Z MaximizarK =
0)(=xh
Sujeto a:
0)(≤xg

160. Un Ejemplo Un Ejemplo
Un estudiante desea seleccionar la mejor escuela de ingeniería c Un estudiante desea seleccionar la mejor escuela de ingeniería c on base a on base a
varios criterios: varios criterios:
Escuelas consideradas Escuelas consideradas
Criterios de Selección Criterios de Selección
Rangos proporcionados por US News Rangos proporcionados por US News

161. Selección de Universidad Selección de Universidad
Valores normalizados Valores normalizados
Análisis de Resultados Análisis de Resultados

162. Conjunto Pareto Conjunto Pareto
¾
MIT es mejor que Georgia Tech y que la Universidad de Michigan
en todos los criterios considerad os. Sin embargo, Stanford, Cal
Tech, Cornell y Carnegie Mellon son mejores o no que MIT
dependiendo del criterio.
¾
La solución a una problema MOP no es un solo valor, sino un
conjunto de alternativas denominado Conjunto Pareto Conjunto Pareto, Conjunto
Preferido o Conjunto No Dominado
¾
Un grupo de 5 escuelas 5 escuelasconforman el Conjunto Pareto en el
ejemplo
¾¾
Conjunto Pareto: Conjunto Pareto:Conjunto de alternativas que proporcionan
soluciones potenciales y representan un compromiso entre los
diferentes objetivos

163. Otro Ejemplo: Fabricación Otro Ejemplo: Fabricación
de Químicos de Químicos
2 1 2
2 1 1
05
4
x x Z Minimize
x x Z Minimize
+ −=
− =
0 ,
4
5
8 2
1
2 1
2 1
2
2 1
1
≥
≤ −
≤
≤ +
≥
xx
x x
x
x x
x
Sujeto a: Sujeto a:
Durabilidad Durabilidad
Almacenamiento Almacenamiento
Disponibilidad Disponibilidad
Seguridad Seguridad
Costo Costo
Emisiones Emisiones
Región Factible en Región Factible en
espacio de Decisión espacio de Decisión

164. Otro Ejemplo: Fabricación Otro Ejemplo: Fabricación
de Químicos de Químicos
Región Factible en Región Factible en
espacio de Objetivos espacio de Objetivos
Valores en Puntos Valores en Puntos
Extremos Extremos
Frontera BAD constituye el Frontera BAD constituye el
Conjunto Pareto Conjunto Pareto

165. Métodos de Solución para Métodos de Solución para
MOPMOP
¾
“Métodos Basados en la Preferencia Métodos Basados en la Preferencia” :
Determinan la solución que mejor satisface la
preferencia de quien toma las decisiones.
Reduce el tiempo y el número de alternativas
pero sufren de subjetividad y falta de información
¾
“Métodos Generadores Métodos Generadores” Determinan el conjunto
Pareto de manera formal
La mejor estrategia es utilizar un método generador La mejor estrategia es utilizar un método generador
para determinar el Conjunto Pareto y entonces usar para determinar el Conjunto Pareto y entonces usar
un método basado en la preferencia para seleccionar un método basado en la preferencia para seleccionar
la solución óptima final. la solución óptima final.

166. Método Generador: Método de los Método Generador: Método de los
Coeficientes de Peso Coeficientes de Peso
¾
La idea es asociar cada función objetivo con un
coeficiente de peso coeficiente de pesoy minimizar la suma “pesada” de los
objetivos
¾
El problema se convierte en una serie de problemas serie de problemasde
optimización de una sola función objetivo una sola función objetivo
∑
=
=
k
i
i i mult
Zw Z Optimizar
1
0)(=xh
Sujeto a:
0)(≤xg

167. Sujeto a:
Método de los Coeficientes de Método de los Coeficientes de
Peso: Procedimiento Peso: Procedimiento
¾
Escoja valores no negativos de los pesos y resuelva el
problema:
∑
=
=
k
i
i i mult
Zw Z Optimizar
1 0)(=xh0)(≤xg
¾
Analice el espacio de la función objetivo y repita
con nuevos pesos de forma que se mueva hacia
la región del conjunto Pareto que se desea
explorar
¾
Encuentre los óptimos individuales para cada objetivo.
Tales puntos representan los extremos del Conjunto No
Dominado.
k
Z Optimizar
Z Optimizar
Z Optimizar
M
2
1

168. Ejemplo Ilustrativo Ejemplo Ilustrativo
2 2 1 1
Zw Zw Z Minimize
mult
+ =
0 ,
4
5
8 2
1
2 1
2 1
2
2 1
1
≥
≤ −
≤
≤ +
≥
xx
x x
x
x x
x
Sujeto a: Sujeto a:
Función objetivo “pesada” Función objetivo “pesada”
mult
Z
w
Z
w
w
Z
2
1
2
1
2
1
+ −=

169. Método Generador: Método de Método Generador: Método de
Restricciones (Constraint Restricciones (ConstraintMethod) Method)
¾
La idea otra vez es transformar el problema multiobjetivo
a una serie de problemas de un solo objetivo
¾
Se selecciona una función objetivo que se conserva se conserva
como tal y el resto se incluye como restricciones de restricciones de
desigualdad desigualdad
) , , ,(
3 2 1k
Z Z ZZ Z MinimizeK =
0)(=xh
Sujeto a:
0)(≤xg
i mult
Z Z Minimize=
ij Z
j j
≠∀ ≤∈

170. Método de Restricciones Método de Restricciones
2 1 2
2 1 1
05
4
x x Z Minimize
x x Z Minimize
+ −=
− =
0 ,
4
5
8 2
1
2 1
2 1
2
2 1
1
≥
≤ −
≤
≤ +
≥
xx
x x
x
x x
x
Sujeto a: Sujeto a:
0 ,
4
5
8 2
1
2 1
2 1
2
2 1
1
≥
≤ −
≤
≤ +
≥
xx
x x
x
x x
x
Sujeto a: Sujeto a:
2 1 1
4x x Z Minimize− =
2 2 1 2
5.0≤∈ − −=x x Z

171. Método de Restricciones Método de Restricciones
1
2
=∈

172. Método Basado en la Preferencia: Método Basado en la Preferencia:
Optimización Mediante Metas (Goal Optimización Mediante Metas (Goal
Programming) Programming)
¾
Se define un valor como meta para cada función meta para cada función
objetivo objetivo
¾
Se crea una sola función objetivo que minimiza las minimiza las
desviaciones desviacionesrespecto de las metas definidas
) , , ,(
3 2 1k
Z Z ZZ Z MinimizeK =
0)(=xh
Sujeto a:
0)(≤xg
(
)
∑
− +
+ =
i
i i goal
Z Minimizeδ δ
i G Z
i i i i
∀ − = −
− +
δ δ
Se establece una meta GG
ii
para cada objetivo ZZ
ii
0 ,≥
− +
i i
δδ

173. Goal GoalProgramming Programming
2 1 2
2 1 1
05
4
x x Z Minimize
x x Z Minimize
+ −=
− =
0 ,
4
5
8 2
1
2 1
2 1
2
2 1
1
≥
≤ −
≤
≤ +
≥
xx
x x
x
x x
x
Sujeto a: Sujeto a:
0 ,
4
5
8 2
1
2 1
2 1
2
2 1
1
≥
≤ −
≤
≤ +
≥
xx
x x
x
x x
x
Sujeto a: Sujeto a:
()
∑
=
− +
+ =
2
1i
i i goal
Z Minimizeδ δ
0 ,≥
− +
i i
δδ
5
2 1
−= =G G
− +
− +
− =+ + −
− =+ −
2 2 2 1
1 1 2 1
5 05
5 4
δ δ
δ δ
x x
x x
Solución:
4 1
2 1
= −=Z Z

174. Control Óptimo y Optimización Control Óptimo y Optimización
Dinámica Dinámica

175. Problemas de Control Óptimo Problemas de Control Óptimo

Proceso de solución consiste en encontrar los
perfiles perfilesde la variable de control vstiempo de
modo que se optimice un índice particular de
medida de desempeño del sistema
()
)( ,
0
TS dt xk L
Maximizar
T
+ =
∫
θ
θ
()
θ,xf
dt
dx
=
Sujeto a:

Métodos de Solución Convencionales
•El Principio del Máximo
•Programación Dinámica
•Cálculo de Variación
0
)0(x x=

176. 
La reina Didoplanteó el problema problema isoperimétrico isoperimétrico: Encuentre el
área mayor que puede ser cubierta con un cordel de longitud fija
(L)
∫
=
X
o
dxxy A)(
∫
=
T
o
dttx A Maximize)(
1
()()
∫∫∫






+ = + = =dx
dx
dy
dx dy ds L
X
0
2
2 2
1
Problemas Históricos Problemas Históricos
dt u L
T∫
+ =
0
2
1
t x
x y
→
→
1
u
dt
dx
=
1
0)0(
1
= x
2 2
1u
dt
dx
+ =0)0(
2
= xLTx=)(
2
0)(
1
=Tx

177. Problemas Problemas Isoperimétrico Isoperimétrico
∫
=
T
o
dttx A Maximize)(
1
u
dt
dx
=
1
0)0(
1
= x
2 2
1u
dt
dx
+ =0)0(
2
= xLTx=)(
2
0)(
1
=Tx

178. Brachistochrone Brachistochrone(Tiempo Mas Corto) (Tiempo Mas Corto)
Bernoulli Galileo

179. Ingeniería Química: Problema de Ingeniería Química: Problema de
Destilado Máximo Destilado Máximo
dt
R
V
dt
dt
dD
L
R
Maximizar
T
t
T
t
∫ ∫
+
= =
0 0
1
∫
∫
+
+
=
T
t
T
t
D
D
dt
R
V
dt
R
V
x
x
0
0
)1(
*
1
1
F Bo x
R
V
dt
dx
t
t
= =
+
−=
1
0
1
1
)1( 2
0 1
)1( 2 2
) (
1
F
t
D t
t
t
x x
x
x x
R
V
dt
dx
=
−
+
=
Sujeto a: Sujeto a:
Pureza Pureza
promedio promedio

180. El Principio del Máximo El Principio del Máximo
¾
La función objetivo se reformula en la forma lineal de forma lineal de
Mayer Mayer
¾
Requiere la incorporación de ecuaciones diferenciales
ordinarias adicionales (ecuaciones adjuntas ecuaciones adjuntas) que
representan la dinámica de las variables adjuntas
(también agregadas al problema)
¾
Se define una función Hamiltoniana Hamiltoniana(invariante en el
tiempo)
¾
El perfil óptimo se obtiene derivando la función
Hamiltonianacon respecto a la variable de control variable de control
¾
El sistema resultante es un problema de valores en la problema de valores en la
frontera frontera

181. ()
dt xk L
Maximizar
T
θ
θ
,
0∫
=
∑
=
= =
n
i
i i
T
f f H
1
µ µ
0
)0(x xf
dt
dx
= =
c T
x
f
f
dt
d
n
ji
j
j x
T
=
∂
∂
−= −=
∑
=
)(
1
µ µ µ
µ
∑
=
= =
n
i
i i
T
Txc Txc J
Maximizar
1
)( )(
θ
0
)0(x xf
dt
dx
= =
0
)0(x x f
dt
dx
= =
El Principio del Máximo El Principio del Máximo
Hamiltoniano Hamiltoniano
Ecuaciones y Ecuaciones y
Variables Adjuntas Variables Adjuntas
Forma Lineal Forma Lineal

182. Problema de Destilado Problema de Destilado
Máximo: Principio del Máximo: Principio del
Máximo Máximo
F Bo x
R
V
dt
dx
t
t
= =
+
−=
1
0
1
1
)1( 2
0 1
)1( 2 2
) (
1
F
t
D t
t
t
x x
x
x x
R
V
dt
dx
=
−
+
=
Sujeto a: Sujeto a:
Función objetivo es Función objetivo es
rere--escrita en forma escrita en forma
Lagrangiana Lagrangiana
()
[]
dt x x
R
V
L
R
Maximizar
D D
t
T
t
)1( *
0
1
1
− −
+
=
∫
λ

183. Problema de Destilado Problema de Destilado
Máximo: Principio del Máximo: Principio del
Máximo Máximo
F Bo x
R
V
dt
dx
t
t
= =
+
−=
1
0
1
1
)1( 2
0 1
)1( 2 2
) (
1
F
t
D t
t
t
x x
x
x x
R
V
dt
dx
=
−
+
=
Sujeto a: Sujeto a:
Para obtener forma Para obtener forma
lineal de lineal de Mayer Mayer
()
[]
∫
− −
+
=
t
D D
t
t
dt x x
R
V
x
0
)1( *
3
1
1
λ
T
t
x
R
Maximize
3
()
[]
)1( *
3
1
1
D D
t
t
x x
R
V
dt
dx
− −
+
=λ

184. Problema de Destilado Problema de Destilado
Máximo: Principio del Máximo: Principio del
Máximo Máximo
Hamiltoniano Hamiltoniano
()
()
()
[]
)1( * 3
1
)1( 2
2 1
1
1 1 1
D D
t
t
t t
D t
t
t
t t
x x
R
V
x R
x xV
R
V
H− −
+
+
+
−
+
+
−=λµ µ µ
Ecuaciones y Ecuaciones y
Variables Adjuntas Variables Adjuntas
()
()
()
0 ,
1
1
2
1
)1( 2
2
1
=
+
−
=
T
t t
D t
t
t
x R
x xV
dt
d
µ µ
µ
()
()
0 ,
1 1
1
2
2
)1(
3
1
2
)1(
2
2
=








∂
∂
+
−
+








∂
∂
−
−=
T
t
D
t
t
t t
t
D
t
t
x
x
R
V
x R
x
x
V
dt
d
µ λµ µ
µ
1 ,0
3
3
= =
T
t
dt
d
µ
µ
0=
∂
∂
t
R
H
()()
1
1
1
2 )1(
)1( * 1 )1( 2
1
2
−








−
∂
∂






+ − − − −
=
t
t
t
D
D D t D t
t
t
t
x R
x
x x x x
x
R
µ
λ
λ µ
µ
Perfil óptimo Perfil óptimo

185. Programación Dinámica Programación Dinámica

Condición de Condición de Optimalidad Optimalidad: Aplicación del Principio
de Optimalidadde Bellmanda como resultado una
ecuación diferencial parcial conocida como Ecuación
Hamilton-Jacobi-Bellman(HJB)






∂
∂
+ +
∂
∂
=
∑
i
i
t
i
t
t t
t
dt
dx
x
L
xk
t
L Maximize
),( 0θ
θ






∂
∂
+ +
∂
∂
=
∑
i
i i
t
t
t
t
f
x
L
xk
t
L Maximize
),( 0θ
θ
[]
fL k L
Maximize
x t
t
+ + =
θ
0

186. Problema de Destilado Problema de Destilado
Máximo: Programación Máximo: Programación
Dinámica Dinámica
Ecuación HJB Ecuación HJB Perfil óptimo Perfil óptimo
()
[]















−
+ ∂
∂
+





+
−
∂
∂
+ − −
+
+
∂
∂
=
1
)1( 2
2 1
)1( *
) (
1 1
1
1
0
t
D t
t t t t
D D
t t
x
x x
R
V
x
L
R
V
x
L
x x
R
V
R
Maximize
t
L
λ






∂
∂
∂
∂
−
∂
∂






+
+






+
−












−
∂
∂
+
∂
∂
− − − =
t
D
t t t
D
t t t
D t
t t
D D
R
x
xx
L
R
x
R
V
R
V
x
x x
x
L
x
L
x x
)1(
1 2
)1(
2 1
)1( 2
2 1
)1( *
1
1 )1 (
) ( 1 0λ λ
()
1
1
1
2 )1(
)1( *
1 1
)1( 2
2
−










∂
∂
−
∂
∂
+ − −
∂
∂
−







−
∂
∂
=
t
t
t
D
D D
t t
D t
t
t
x
x
L
R
x
x x
x
L
x
x x
x
L
R
λ
λ

Mismo perfil que en el principio Mismo perfil que en el principio
del máximo si las del máximo si las variables variables
adjuntas adjuntasson iguales a las son iguales a las
derivadas de la función objetivo derivadas de la función objetivo
(L) con respecto (L) con respectoa las variables a las variables
de estado (x) de estado (x)

187. Problemas Estocásticos Problemas Estocásticos
de Control Óptimo de Control Óptimo
¾
No es posible despreciar incertidumbres en algunas
aplicaciones prácticas de problemas de control óptimo:
9
En parámetros del modelo
9
En condiciones iniciales
¾
El problema estocástico de control óptimo resultante
puede ser analizado utilizando “Teoría de Opción Teoría de Opción
Real Real”:
9
Caracterizando incertidumbres dependientes del tiempo como
Procesos de Ito
9
Usando el Lema de Lema de ItoIto
9
Usando las condiciones de optimalidad de Programación Programación
Dinámica Estocástica Dinámica Estocástica

188. 
Las variables estocásticas cambian con el tiempo en una forma
incierta

El denominado proceso proceso Wiener Wienerse utiliza como base para modelar
una amplia gama de procesos estocásticos más complicados.
Posee 3 propiedades:
9
Satisface la propiedad de Markov Markov
9
Presenta incrementos independientes
9
Sus cambios en el tiempo se distribuyen normalmente

Un proceso de proceso de ItoItorepresenta el incremento de una variable
estocástica en el tiempo de acuerdo con:
() ()
dztxbdttxa dx, ,+ =
ay bson funciones conocidas y dzes el incremento de un
proceso Wiener. Note que E[dz]=0y E[dz
2
]=dt
Procesos de Procesos de ItoIto

189. Procesos de Procesos de ItoIto

MovimientoBrowniano

MovimientoGeométricoBrowniano

“Mean reverting process”
dz dt dxσ α+=
(
)
dz dtx x dx
avg
σ η+− =
dzx dtx dxσ α+=
Algunos parámetros ingenierilespueden representarse como
procesos de Ito:

190. Lema Lemade Ito de Ito

Teorema Fundamental Teorema Fundamentaldel Cálculo Estocástico

Permite derivar e integrar funciones de variables estocásticas que
se comportan como procesos de Ito
() ()
dztxbdttxa dx, ,+ =
()
()
dz
x
F
txb dt
x
F
txb
x
F
txa
t
F
dF
∂
∂
+






∂
∂
+
∂
∂
+
∂
∂
=),( ,
2
1
,
2
2
2
()
2
2
2
2
1
dx
x
F
dx
x
F
dt
t
F
dF
∂
∂
+
∂
∂
+
∂
∂
=

No se desprecian algunas contribuciones de segundo orden dado
que E[dz
2
]=dt

191. Programación Dinámica Estocástica Programación Dinámica Estocástica

Se ha desarrollado una extensiona las condiciones de
optimalidadde programación dinámica para el caso
estocástico:
()
dt xk L
Maximize
t t
T
t
θ
θ
,
0∫
=
Sujeto a: Sujeto a:
Condiciones de Condiciones de
Optimalidad Optimalidad:
(
)
dz dt xf dx
i t
t
i
i
t
σ θ+ =,






+ =)(
1
),( 0dLE
dt
xk
Maximize
t
t
t
θ
θ
∑ ∑ ∑ ≠



∂∂
∂
+
∂
∂



+
∂
∂
+ +
∂
∂
=
ji
j
t
i
t
j i
i
i
t
i
i
t i i
t
t
t
xx
L
x
L
txf
x
L
txk
t
L Maximize
2
2
2 2
) (2
),( ),( 0σσ
σ
θProcesos de Procesos de ItoIto

192. Principio del Máximo para Problemas Principio del Máximo para Problemas
Estocásticos Estocásticos
¾¾
Con base en las condiciones de Con base en las condiciones de optimalidad optimalidadpara programación para programación
dinámica, se pudieron derivar las expresiones correspondientes a dinámica, se pudieron derivar las expresiones correspondientes al l
método del principio del máximo método del principio del máximo
¾¾
Las variables adjuntas Las variables adjuntas((
µµ
) en el principio del máximo son equivalentes ) en el principio del máximo son equivalentes
a las a lasderivadas parciales de la función objetivo con respecto a las derivadas parciales de la función objetivo con respecto a las
variables de estado variables de estado ((LL
xx
) de programación dinámica ) de programación dinámica
¾¾
El principal resultado del análisis es la derivación de las El principal resultado del análisis es la derivación de las ecuaciones ecuaciones
adjuntas adjuntas
¾¾
Las derivadas de segundo orden Las derivadas de segundo ordende la función objetivo con especto de la función objetivo con especto
a las variables de estado a las variables de estado ((LL
xxxx
) en programación dinámica ) en programación dinámica
estocástica tiene que ser también incluidas y se incorporan en l estocástica tiene que ser también incluidas y se incorporan en l a a
formulación a través de las formulación a través de las variables adjuntas variables adjuntas adicionales,,
ωω

193. f Hµ=
ω
σ
µ
2
2
+ =f H
0
)0(x xf
dt
dx
= =
0
)0(x x dz dtf dx= + =σ
c T f
dt
d
x
= −=)(µ µ
µ
Determin Determinístico ísticoEstocástico EstocásticoPrincipio del Máximo para Problemas Principio del Máximo para Problemas
Estocásticos Estocásticos

Se utiliza representación escalar aunque el análisis es válido para
el caso vectorial
()
c T f
dt
d
x x
= − −=)(
2
1
2
µ ω σ µ
µ
()
0 )(
2
1
2
2
= − − −=T f f
dt
d
xx xx x
ω ω σ µ ω
ω

194. Versión Estocástica del Problema Versión Estocástica del Problema
de Destilado Máximo de Destilado Máximo
dt
R
V
dt
dt
dD
L
R
Maximize
T
t
T
t
∫ ∫
+
= =
0 0
1
*
0
0
)1(
1
1
D
T
t
T
t
D
Dave
x
dt
R
V
dt
R
V
x
x=
+
+
=
∫
∫
F Bo x
R
V
dt
dx
t
t
= =
+
−=
1
0
1
1
Sujeto a:
)1( 2
0 2 2
2
1
)1( 2
2
) (
1
F t
t
D t
t
t
x x dz x dt
x
x x
R
V
dx= +
−
+
=σ
Proceso Proceso ItoIto
Restricción externa usada Restricción externa usada
como criterio de como criterio de
convergencia convergencia

195. 2.75
2.8
2.85
2.9
2.95
3
3.05
3.1
3.15
3.2
0123
Time (H rs )
Relative Volatility
Rigorous
Simulation
P a th 1 P a th 2 P a th 3
Volatilidad Relativa como un Volatilidad Relativa como un
Proceso de Proceso de ItoIto
Ocasiona un comportamiento incierto en las Ocasiona un comportamiento incierto en las
variables de estado variables de estado

196. Principio del Máximo Principio del Máximo
()
()
()
()
ω σ µ µ
µ
2 2
2 1
2
)1(
2
1
)1( 2
2
1
1
1
t
t t
t
D
t t
D t
x
x R
x
x
V
x R
x xV
dt
d
−
+








∂
∂
−
−
+
−
−=
()
()
()
()
()
()
2
1
)1( 2
2
2 1
2
2
)1(2
1
2
)1(
1 1 1
1
2
t t
D t
t t
t
D
t t
t
D
x R
x xV
x R
x
x
V
x R
x
x
V
dt
d
+
−
− −
+
∂
∂
+
+








∂
∂
−
−=ωµωσ µ ω
ω
()
()
1
)1 (
)1(
2
2
2 2
2
1
)1(
)1( 2 1
−
∂
∂





+






∂
∂
+
∂
∂
− −
=
µ
ω
σ
σ
µ
µ
t
D
t
t
t
t
t
D
D t t
t
R
x
V
R
x
R
x
R
x
x x x
R
Ecuaciones Ecuaciones
Adjuntas Adjuntas
Perfil Perfil
óptimo óptimo

197. Perfil Óptimo de la Razón de Reflujo Perfil Óptimo de la Razón de Reflujo
¾
Se requieren valores de refl ujo más grandes debido a la
disminución en el valor de la volatilidad relativa con el tiempo
¾
La desviación respecto al caso determinísticotambién cambia
con el tiempo debido al efecto de las incertidumbres

198. Determin Determinístico ístico
Nuevamente el Problema Nuevamente el Problema Isoperimétrico Isoperimétrico

Considere ahora la versión estocástica versión estocásticadel problema
isoperimétrico
)(
3
Tx
u
Maximize
0)0(
)( 0)0( 1
0)( 0)0(
3 1
3
2 2
2 2
1 1
1
= =
= = + =
= = =
x x
dt
dx
L Tx x u
dt
dx
Tx x u
dt
dx
0)( 0)0(
1 1 1
= = + =Tx x dz dtu dxσ
5.0=σ
16=L
Movimiento Browniano Movimiento Browniano
Estocástico Estocástico
Suposición meramente Suposición meramente
académica académica

199. Soluciones al Problema Soluciones al Problema Isoperimétrico Isoperimétrico
0
1
0
1
2
2
1
3
2 2
1 1
=
+
+
=
=
=
+−=
µ µ
ω
µ
µ
µ
u
u
c
ct

200. Bibliografía Bibliografía
1. Teor 1. Teoríía de optimizaci a de optimizacióón (n (determin determiníística stica) y ) y
Aplicaciones en Ingenier Aplicaciones en Ingenieríía Qu a Quíímica mica a) Practical Methods of Optimization; R. Fletcher, 2nd. Ed., Wi a) Practical Methods of Optimization; R. Fletcher, 2nd. Ed., Wi leyley
b) Optimization of Chemical Processes; Edgar, b) Optimization of Chemical Processes; Edgar, Himmelblau Himmelblauand Larson, and Larson,
2nd. Ed., McGraw 2nd. Ed., McGraw--Hill Hill
c) Nonlinear Programming, Theory and Algorithms; c) Nonlinear Programming, Theory and Algorithms; Bazaraa Bazaraa, , Sherali Sheraliand and
Shetty Shetty, Wiley , Wiley
d) Systematic Methods for Chemical Process Design; d) Systematic Methods for Chemical Process Design; Biegler Biegler, Grossmann , Grossmann
and Westerberg, Prentice Hall and Westerberg, Prentice Hall
e) Linear Programming; e) Linear Programming; Chvatal ChvatalVasek Vasek, Ed. W. H. Freeman and Co. , Ed. W. H. Freeman and Co.
2. Programaci 2. Programacióón n MultiObjetivo MultiObjetivo
a) a) Introduction to Applied Optimization, Introduction to Applied Optimization, Diwekar Diwekar, , Kluwer KluwerAcademic Academic
Publishers Publishers

201. Bibliografía Bibliografía
3. Programaci 3. Programacióón Estoc n Estocáástica stica
a) Stochastic Programming, a) Stochastic Programming, Kall Kalland Wallace, Wiley and Wallace, Wiley
4. Control 4. Control óóptimo ptimo
a) Batch Distillation, Simulation, Optimal Design and Control; a) Batch Distillation, Simulation, Optimal Design and Control; Diwekar Diwekar, Ed. , Ed.
Taylor and Francis Taylor and Francis
b) Optimal Control Theory; b) Optimal Control Theory; Sethi Sethiand Thompson, and Thompson, Kluwer KluwerAcademic Academic
Publishers Publishers
c) Investment Under Uncertainty; c) Investment Under Uncertainty; Dixit Dixitand and Pindyck Pindyck, Princeton University , Princeton University
Press Press