FUNCIONES
• Continuas, discontinuas.
• Continuamente diferenciables, no continuamente
diferenciables (de orden n)
• Unimodales, multimodales.
• Cóncavas, convexas.
• Puntos estacionarios.
• Región convexa.
• Funciones y formas cuadráticas.
• Condiciones necesarias y suficientes de
– Máximos y mínimos.
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
1
FUNCIONES
• Funciones cóncavas y convexas
f[x  (1 -  )x ]  f(x )  (1 -  )f(x ), 0    1
1
2
1
2
Función cóncava f[x  (1 -  )x ]  f(x )  (1 -  )f(x ), 0    1
1
2
1
2
Las funciones estrictame nte convexas o cóncavas son aquélas en las
que el signo  o  es sustituído por  o  .
Función convexa
• Puntos estacionarios (Puntos singulares).
Son aquéllos que verifican f(x)  0
• Región convexa
Una región R es convexa si
x , x en R el punto x dado por la combinació n lineal de los anteriores
1 2
x  x  (1 -  )x está tambi én en R, 0    1
1
2
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
2
FUNCIONES
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
3
FUNCIONES
• Formas cuadráticas
H es definida positiva si y solo si x T Hx  0 , x  0
H es definida negativa si y solo si x T Hx  0 , x  0
H es semidefini da positiva si y solo si x T Hx  0 , x  0
H es semidefini da negativa si y solo si x T Hx  0 , x  0
H es indefinida si x T Hx  0 para algún x y  0 para otros x.
f(x)
H(x)
Valores propios de H
Menores de H
Estrictamente
convexa
Definida positiva
>0
1  0,  2  0,...
Convexa
Semidefinida positiva
0
  0,   0,...
1
2
Cóncava
Semidefinida negativa
0
Estrictamente
cóncava
Definida negativa
<0
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
  0,   0,   0,...
1
2
3
  0,   0,   0,...
1
2
3
4
Extremos de f(x)
• 1
• 2
• 3
•
•
f (x) es doblementediferenciable en x *
f (x*)  0 o sae quex * sea un puntoestacionario
H ( x*) sea definida positiva paraun mínimoy definidanegativaparaun máximo
Las condiciones 1 y 2 son necesarias y la 3 suficiente para garantizar que x*
sea un extremo.
Un máximo o mínimo puede existir aunque no se cumplan las tres
condiciones.P. ej. Si f(x)=x4, x*=0 es un mínimo pero H(0) no está definida en
x*=0 y la condición 3 no se satisface.
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
5
REGIÓN FACTIBLE
Min f  ( x1  3) 2  ( x2  4) 2
sujeto a las restricciones
x1  0
x2  0
5  x1  x2  0
 2.5  x1  x2  0
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
6
REGIÓN FACTIBLE
Min f  ( x1  2) 2  ( x2  2) 2
sujeto a las restricciones
x1  0
x2  0
5  x1  x2  0
 2.5  x1  x2  0
Si la función f y las restricciones son
convexas, lo que implica que la región
factible es convexa, el problema de
programación no lineal general se
transforma en un problema de
programación convexa y se verifica
que:
El mínimo local de f(x) es también un
mínimo global.
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
7
FUNCIONES CONVEXAS
CONJUNTOS CONVEXOS
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
8
FUNCIONES CONVEXAS
CONJUNTOS CONVEXOS
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
9
OPTIMIZACION SIN
RESTRICCIONES.BUSQUEDA
UNIDIMENSIONAL
• A. Métodos directos. No requieren el cálculo de la
derivada.
• B. Métodos indirectos. Requieren el cálculo de la
derivada.
– Selección del estimado inicial.
– Procedimientos de búsqueda y partición del intervalo.
– Convergencia.
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
10
Métodos directos
• Métodos de eliminación de regiones.
– Búsqueda de dos puntos por intervalos iguales.
– Búsqueda dicotómica.
– Búsqueda de Fibonacci.
– Búsqueda por razón aúrea.
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
11
Métodos directos
Búsqueda de Fibonacci.
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
12
Métodos indirectos.
• Método de Newton.
• Método de Quasi-Newton.
• Método de la secante.
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
13
OPTIMIZACION SIN
RESTRICCIONES. BUSQUEDA
MULTIVARIABLE.
•
1.
2.
3.
Métodos directos.
Búsqueda aleatoria
Búsqueda por rejilla
Método simplex
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
14
OPTIMIZACION SIN RESTRICCIONES.
BUSQUEDA MULTIVARIABLE.
• Método simplex
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
15
MÉTODOS INDIRECTOS
PRIMER ORDEN (A)
SEGUNDO ORDEN (B)
• A.-Método del gradiente
•
Método del Gradiente conjugado
(Fletcher-Powell)
• B.- Método de Newton
•
Método de la secante
•
Método de Davidon-Fletcher-Powell
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
16
MÉTODO DEL GRADIENTE
• Ecuación básica para búsqueda de un mínimo/máximo de f(x).El
gradiente es un vector que da la máxima variación de f(x)
• Steepest ascent (descent)
x k 1  x k  Hg x x
 constante,H  I es el más simple
  k tamañovariabledel paso.
k
λ es la longitud del paso
H es una matriz nxn
g es el gradiente def(x); f(x)
opt
k , optimizael tamañodel paso.
• Optimizar
– la longitud del paso
x k 1  x k  sk
1
f ( x )  f (x k )  T f (x k )sk  (sk )T H (x k )(sk )
2
Derivandocon respectoa  e igualendo a cero resulta :
opt
k  
Tema IV.3
Introducción
T f (x k )sk
(sk )T H (x k )(sk )
Simulación y Optimización de
Procesos Químicos
17
MÉTODO DEL GRADIENTE
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
18
MÉTODO DEL GRADIENTE
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
19
MÉTODO DEL GRADIENTE.EJEMPLO.
Compresor de tres estados
 k 1
kNRT  p2  k  p3 
 
  
k  1  p1 
 p2 

Datos NRT  1, p1  1, p4  10.
 k 1
W
k
p 
  4 
 p3 
 k 1
k

 3


La figura da las isolíneasdeW .
Se buscael m ínim odeW conel m étododel gradiente.
Estimadoinicial p2  4, p3  7.
Tema IV.3
Introducción
La direcciónde búsquedaes proporcional a los cam biosdeW con p y p
2
3
Así en (4,7)
W
W
 0.079
 0.009
p
p
2
3
p
2  0.079  8.8
p
0.009
3
Tom andoincrem entos de p igualesa 0.05,
3
los increm entos de p serán 0.05 8.8  0.44.
2
Así el prim erdescensovienedadoen la tabla
Simulación y Optimización de
Procesos Químicos
20
MÉTODO DEL GRADIENTE.EJEMPLO.
Tema IV.3
Introducción
p2
p3
W
4.00
7.00
2.681
3.56
6.95
2.653
3.12
6.90
2.629
2.68
6.85
2.615
2.24
6.80
2.622
Simulación y Optimización de
Procesos Químicos
Punto
mínimo
21
MÉTODO DEL
GRADIENTE.EJEMPLO.
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
22
Direcciones conjugadas
Gradiente conjugado
•
Es un método útil en mejorar la convergencia del método del
gradiente.
s y s son direcciones conjugadasentresí si
i
j
si  Q s j   0
T
•
•
•
•
La matriz Q es el hessiano de la función. objeto.
La dirección de búsqueda es una combinación lineal del gradiente
actual con la dirección anterior.
Pequeña información necesaria para realizar el algoritmo.
Paso 1.
En x calcular f (x ).
0
0
s0  f (x 0 ).
•
•
Paso 2.Guardar
..........
Tema IV.3
Introducción
f (x 0 ).
Simulación y Optimización de
Procesos Químicos
23
PROGRAMACION NO LINEAL CON
RESTRICCIONES
•
•
•
•
Método de los multiplicadores de Lagrange
Condiciones necesarias y suficientes para un extremo local
Método del gradiente generalizado
Programación cuadrática
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
24
PROGRAMACION NO LINEAL CON
RESTRICCIONES DE IGUALDAD
Método de los multiplicadores de Lagrange
• PROBLEMA
min f (x)
sujeto a g j (x)  0, j  1,2,...,m
• CONDICIONES NECESARIAS. A partir de la función de Lagrange,L
L( x1 , x 2 , ,.., x n , 1 , 2 ,...,m )  f (x)  1 g1 (x)  2 g 2 (x)  ....  m g m (x)
L
 0 i  1,2,...,n
xi
L
 g j (x)  0 j  1,2,...,m
j
• CONDICIONES SUFICIENTES
n
2L
dxi dx j
j 1 xi x j
m
Q  
i 1
La form a cuadráticaQ evaluadaen x * debe ser definida positiva
para todos los valores de d x que satisfaganlas restricciones
Teorem ade Hancock.
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
25
PROGRAMACION NO LINEAL CON
RESTRICCIONES DE IGUALDAD
• Matriz de Hancock. Condiciones suficientes con restricciones.
• La forma cuadrática Q es definida positiva o negativa si las
raíces  de la ecuación siguiente son positivas o negativas.
L11   L12 ........
L21
L1n
g11 g 21
g m1
L22   ..... L2 n
g12 g 22
gm2
.
.
Ln1
Ln 2
Lnn  
g11
g12
g1n g 2 n
g mn
g1n
0 0
0
g mn
0 0
0
0
.
.
g m1
gm2
• Ejemplo. Encontrar las dimensiones de un depósito cilíndrico
cerrado hecho de acero que maximice su volumen si el área
del mismo es de 24p.
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
26
CONTROL ÓPTIMO ESTACIONARIO
• Dinámica
Min x ,u J(x,u)
sujeto a x  f(x,u, v)
Min x ,u J(x,u)
• Estacionario
sujeto a f(x,u, v)  0
• Método de los multiplicadores de Lagrange
Minx,u J(x,u)  Minx,u J(x,u)  Tf(x,u, v)
• Sistema lineal o linealizado en torno a un punto
1
1
estacionario
J ( x, u )  x Qx  u Pu
T
T
2
2
sujeto a Ax  Bu  Cv  0
• Solución
u*  Mv


1
M   I  P 1BT AT QA1B P 1BT AT QA1C
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
27
CONTROL ÓPTIMO ESTACIONARIO
• Condiciones necesarias
J 
0
x
J 
0
u
J 
0

• Condiciones suficientes
– Definida positiva lo cual implica que
– Q (nxn) sea simétrica y def. positiva
– P (rxr) sea simétrica y def. positiva
 2 J Q O

xu O P 
v
v
u
Tema IV.3
Introducción
M
x
u
Simulación y Optimización de
Procesos Químicos
28
x
PROGRAMACION NO LINEAL CON
RESTRICCIONES DE DESIGUALDAD
• PROBLEMA
min f (x)
min f (x)
sujeto a g j (x)  0, j  1,2,...,m
sujeto a g j (x)  y j  0, j  1,2,...,m
2
• SOLUCIÓN. Método de los multiplicadores de Lagrange
m
min L(x, y, λ )  f ( x )    j G j ( x, y )
j 1
G j (x, y )  g j (x )  y j  0, j  1,2,...,m
2
y  ( y1 , y 2 ,..y m )´ vectorde variablesslack
λ  ( 1 , 2 ,...,m )´ vectorde multiplicadores de Lagrange
• CONDICIONES NECESARIAS
• Las derivadas parciales de L con respecto a x,y,,igualadas a cero.
• Dan n+2m ecuaciones para calcular n+2m incógnitas
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
29
PROGRAMACION NO LINEAL CON
RESTRICCIONES DE DESIGUALDAD
• En programación convexa las condiciones anteriores se convierten en
condiciones necesarias y suficientes para un mínimo local. Se llaman
condiciones de Kuhn-Tucker y se establecen como:
m
g j
f
 j
 0 i  1,2,...,n
xi i 1
xi
jg j  0
j  1,2,....,m
gj  0
j  1,2, ......,m
j  0
j  1,2,.......,m
• Si el problema es de maximizar o si las restricciones son del tipo
• tienen que ser no positivos.Si el problema es de maximizar y las
restricciones de la forma  los  tienen que ser no negativos.

los
j
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
30
j
PROGRAMACION ENTERA-MIXTA (MIP)
• La función objetivo depende de dos conjuntos de variables
– x vector de variables continuas
– y vector de variables enteras
• Ejemplos:
– Problema del viajante.
– Problema de la localización de plantas
En general son problemas de PL o PNL conocidos como MILP o
MINLP
Soluciones.- Algoritmo Branch and Bound.
Son variantes de Programación lineal y no lineal.
Utilizado en EXCEL SOLVER
Tema IV.3
Introducción
Simulación y Optimización de
Procesos Químicos
31
Descargar

Tema 3