ESCUELA SUPERIOR DE INGENIERA QUMICA E INDUSTRIAS EXTRACTIVAS

INSTITUTO POLITCNICO NACIONAL

Apuntes de Optimizacin y Simulacin de Procesos

Gabriel E. Santana Rodrguez

Julio 2007

Contenido
Optimizacin _________________________________________________________ 1
Porqu optimizar? ________________________________________________________ 1

Clasificacin de modelos ________________________________________________ 1 Funcin objetivo ______________________________________________________ 1

Caractersticas esenciales de los problemas de optimizacin_______________________ 1 Pasos para la solucin de problemas de optimizacin ____________________________ 1 Ejemplo 1 ________________________________________________________________ 1 Ejemplo 2 ________________________________________________________________ 1

Mtodos analticos _____________________________________________________ 1

Derivacin Univariable _____________________________________________________ 1
Primera derivada ________________________________________________________________1 Segunda derivada________________________________________________________________1 Ejemplo 1______________________________________________________________________1 Ejemplo 2______________________________________________________________________1

Derivacin Multivariable ___________________________________________________ 1

Gradiente ______________________________________________________________________1 Hessiano_______________________________________________________________________1 Ejemplo 1______________________________________________________________________1 Ejemplo 2______________________________________________________________________1 Ejemplo 3______________________________________________________________________1

Multiplicadores de Lagrange ________________________________________________ 1

Ejemplo 1______________________________________________________________________1 Ejemplo 2______________________________________________________________________1

Mtodos numricos ____________________________________________________ 1

Fibonacci_________________________________________________________________ 1
Ejemplo _______________________________________________________________________1

Seccin dorada ____________________________________________________________ 1

Ejemplo _______________________________________________________________________1

Simplex __________________________________________________________________ 1
Ejemplo 1______________________________________________________________________1 Ejemplo 2______________________________________________________________________1

Nelder-Mead______________________________________________________________ 1
Ejemplo 1______________________________________________________________________1 Ejemplo 2______________________________________________________________________1

Mxima Pendiente _________________________________________________________ 1

Ejemplo 1______________________________________________________________________1 Ejemplo 2______________________________________________________________________1

Programacin lineal ___________________________________________________ 1

Mtodo grfico. ___________________________________________________________ 1
Ejemplo _______________________________________________________________________1

Mtodo Simplex ___________________________________________________________ 1

Ejemplo _______________________________________________________________________1

Programacin geomtrica _______________________________________________ 1

Ejemplo de polinomios con trminos positivos __________________________________ 1 Ejemplo de polinomios con trminos positivos y negativos ________________________ 1

Programacin dinmica ________________________________________________ 1

Ejemplo 1 ________________________________________________________________ 1 Ejemplo 2 ________________________________________________________________ 1

Bibliografa __________________________________________________________ 1

ii

GESR

Optimizacin [1]
La optimizacin es el uso de mtodos especficos para determinar la solucin ms rentable y ms eficiente a un problema o a un diseo para un proceso. Esta tcnica es una de las herramientas cuantitativas principales en la toma de decisin industrial. Una amplia variedad de problemas en el diseo, la construccin, la operacin, y el anlisis de plantas qumicas (as como muchos otros procesos industriales) se puede resolver por la optimizacin. El objetivo de la optimizacin es encontrar los valores de las variables en el proceso que produzcan el mejor valor del criterio establecido tal como el costo mnimo. Normalmente existe una compensacin entre los costos de capital y de operacin.

Porqu optimizar?
Por qu los ingenieros estn interesados en la optimizacin? Qu beneficios resultan de usar este mtodo en vez de tomar decisiones intuitivamente? Los ingenieros trabajan para mejorar el diseo inicial del equipo y se esfuerzan para mejorar la operacin de ese equipo una vez que est instalado de tal modo que realice la mayor produccin, el mximo beneficio, el costo mnimo, el menor uso de energa y as sucesivamente. El valor monetario proporciona una medida conveniente de objetivos diversos, pero no todos los problemas tienen que ser considerados en un marco monetario (costo contra rdito). En operaciones de planta, las ventajas surgen del funcionamiento mejorado de la planta, tal como mejores producciones de productos valiosos (o producciones reducidas de contaminantes), del consumo de energa reducido, de velocidades de procesamiento mayores y de tiempos ms largos entre paros. La optimizacin puede tambin conducir a costos de mantenimiento reducidos, a menos desgaste del equipo y a una utilizacin mejor del personal. Adems, las ventajas intangibles surgen de las interacciones entre operadores de planta, ingenieros y la gerencia. Es extremadamente provechoso identificar sistemticamente el objetivo, las restricciones y los grados de libertad en un proceso o una planta, conduciendo a beneficios tales como calidad mejorada del diseo, una localizacin de averas ms rpidamente y ms confiables, y una toma de decisin ms rpida. Los beneficios pronosticados se deben hacer con cuidado. Las variables de operacin y diseo en la mayora de las plantas se relacionan siempre de cierta manera. Si la cuenta del combustible para una columna de la destilacin es $3000 por da, un ahorro del 5 por ciento puede justificar un proyecto sobre conservacin de energa. Sin embargo, en una operacin unitaria tal como destilacin, es incorrecto simplemente sumar los servicios del intercambiador de calor y hacer una reduccin en el calor total requerido. Una reduccin en el servicio de calentamiento del rehervidor puede influenciar en la pureza del producto, que se puede traducir en un cambio en las ganancias y en los requerimientos de enfriamiento en el condensador. Por lo tanto, puede ser engaoso no hacer caso de los efectos indirectos y de relacin que tienen las variables del proceso en los costos.

GESR

Qu hay acerca de la discusin, de que el uso formal de la optimizacin realmente no est garantizado debido a la incertidumbre que existe en la representacin matemtica del proceso o de los datos utilizados en el modelo del proceso? Tal discusin tiene ciertamente cierto mrito. Los ingenieros tienen que usar un juicio en la aplicacin de tcnicas de optimizacin a los problemas que tienen una incertidumbre considerable asociada a ellos, desde el punto de vista de la exactitud y del hecho de que los parmetros de operacin de la planta y los alrededores no son siempre estticos. En algunos casos puede ser posible realizar un anlisis va optimizacin determinista y despus agregar caractersticas estocsticas al anlisis para producir predicciones cuantitativas del grado de incertidumbre. Siempre que el modelo de un proceso se idealice y los datos de la entrada y los parmetros se conozcan aproximadamente, los resultados de la optimizacin se deben tratar juiciosamente. Pueden proporcionar lmites superiores a las expectativas. Otra manera de evaluar la influencia de parmetros inciertos en el diseo ptimo es realizar un anlisis de sensibilidad. Es posible que el valor ptimo de una variable de proceso no es afectado por ciertos parmetros (sensibilidad baja); por lo tanto, tener valores exactos para estos parmetros no ser crucial para encontrar el ptimo verdadero.

Clasificacin de modelos
Basados en la teora fsica Basados en descripciones estrictamente empricas Provienen de la experiencia como de reglas heursticas a consecuencia de falta de tiempo o de recursos.

Involucra balances de masa y energa, termodinmica, cintica de la reaccin qumica, etc.

Linear

No linear

f ( x)

f ( x)

Estado estacionario (esttico)

Estado no estacionario (dinmico) 0 t Si hay variacin respecto al tiempo.

=0 t No hay variacin respecto al tiempo.

GESR

Parmetro agrupado

Parmetro distribuido

=0 V Las variaciones espaciales se ignoran y las propiedades del sistema son iguales en todo el volumen

0 V Existen variaciones espaciales y las propiedades del sistema son diferentes en todo el volumen

Variable discreta

Variable continua

La variable tiene un nmero finito de valores, por ejemplo, el nmero de compresores.

La variable tiene un nmero infinito de valores, por ejemplo, los diferentes valores de presin y temperatura en cada etapa de compresin.

Determinsticos

Estocsticos

Son sistemas que exhiben el mismo comportamiento bajo las mismas condiciones y no suceden al azar. Por ejemplo, un lquido hervir bajo ciertas condiciones.

Son sistemas que funcionan por azar en funcin de probabilidades. Por ejemplo, la forma que toma el vapor es aleatoria.
3

GESR

Funcin objetivo [1]

Formular el problema es quizs el paso ms crucial de la optimizacin. La formulacin del problema requiere identificar los elementos esenciales de una declaracin conceptual o verbal de una aplicacin dada y organizarlos en una forma matemtica prescrita, a saber, 1. La funcin objetivo (criterio econmico) 2. El modelo de proceso (restricciones) La funcin objetivo representa los factores tales como beneficio, costo, energa, y produccin en trminos de las variables claves del proceso que es analizado. El modelo del proceso y las restricciones describen las correlaciones de las variables clave.

Caractersticas esenciales de los problemas de optimizacin

Debido a que la solucin de los problemas de optimizacin implica varias caractersticas de las matemticas, la formulacin de un problema de optimizacin debe utilizar expresiones matemticas. Tales expresiones no necesitan necesariamente ser muy complejas. No todos los problemas se pueden indicar o analizar cuantitativamente, pero restringiremos nuestra cobertura a los mtodos cuantitativos. Desde un punto de vista prctico, es importante relacionar correctamente la declaracin del problema con una tcnica de solucin anticipada. Una variedad amplia de problemas de optimizacin tiene estructuras asombrosamente similares. De hecho, es esta semejanza la que ha permitido el progreso reciente en las tcnicas de optimizacin. Los ingenieros qumicos, ingenieros petroleros, fsicos, qumicos e ingenieros de trfico, entre otros, tienen un inters comn en la misma estructura matemtica del problema, cada uno con un diverso uso en el del mundo real. Podemos hacer uso esta semejanza estructural para desarrollar un marco o una metodologa dentro de la cual puede ser estudiado cualquier problema. Cada problema de optimizacin contiene tres categoras esenciales: 1. Por lo menos una funcin objetivo que se optimizar (funcin beneficio, funcin costo, etc.) 2. Restricciones de igualdad (ecuaciones) 3. Restricciones de desigualdad (desigualdades) Las categoras 2 y 3 constituyen el modelo del proceso o del equipo; la categora 1 a veces se llama el modelo econmico. Por solucin factible del problema de optimizacin se quiere decir que se trata de un conjunto de variables que satisfacen las categoras 2 y 3 al grado deseado de precisin.

GESR

Pasos para la solucin de problemas de optimizacin

1. Analizar el proceso para definir las variables de proceso y las caractersticas especficas del inters; es decir, hacer una lista de todas las variables. Puede incluir un diagrama o esquema. 2. Determinar el criterio de optimizacin (minimizar o maximizar), especificar la funcin objetivo en trminos de las variables definidas en el paso 1 junto con los coeficientes. Este paso proporciona el modelo de optimizacin (a veces llamado modelo econmico cuando sea apropiado). 3. Con expresiones matemticas, desarrolle un modelo vlido del proceso o del equipo que relacione las variables de entrada-salida del proceso y los coeficientes asociados. Incluir las restricciones de igualdad y desigualdad. Utilizar principios fsicos bien conocidos (balances de masa, balances de energa), relaciones empricas, conceptos implcitos y restricciones externas. Identificar las variables independientes y dependientes para obtener el nmero de grados de libertad. 4. Si la formulacin del problema es demasiado grande en alcance: (a) Divida el problema en partes manejables o, (b) simplifique la funcin objetivo y el modelo. 5. Aplique una tcnica de optimizacin adecuada a la declaracin matemtica del problema. 6. Compruebe las respuestas y examine la sensibilidad del resultado a los cambios en los coeficientes del problema y las suposiciones.

Ejemplo 1
Se desea enfriar un gas [Cp=0.3 Btu/(lb F)] de 195 a 90 F, usando agua de enfriamiento a 80 F. Los costos del agua son $0.20/1000 pies3 y los cargos fijos anuales para el intercambiador son $0.50/pie2 de superficie interna, con un dimetro de 0.0875 pies. El coeficiente de transferencia de calor es U=8 Btu/(h pie2 F) para un gasto msico de gas de 3000 lb/h. Grafique los costos anuales del agua de enfriamiento y los cargos fijos del intercambiador como una funcin de la temperatura del agua de salida. Cul es el costo total mnimo? Solucin: Paso 1.
Suposicin: Intercambiador de calor de un solo paso por tubos y un solo paso por coraza en contracorriente y sin cambio de fase.

El perfil de temperatura es:

GESR

195F

T0 90F 80F

0.20 $ 1000 pies 3 $ C fijos = 0.50 pie 2 ao lb m gas = 300 h Btu Cp gas = 0.3 lb F Btu U =8 h pie 2 F C agua =

Paso 2. Minimizar Costos totales como una funcin de la temperatura del agua de salida.

Costostotales = f (T0 ) =
Paso 3.

$ ao

Sumar todos los costos y dejarlos en $/ao. Para eso se necesita las ecuaciones que describen el proceso:
Suposiciones: Prdidas de calor despreciables Se laboran 365 das al ao, 24 horas al da. lb Btu , agua = 62.4 Cp agua = 1 pie 3 lb F

Q = magua cpagua (T0 80) Q = m gas cp gas (195 90) Q = UATml Tml = (195 T0 ) (90 80) (195 T0 ) ln (90 80)

GESR

Los costos son:

C agua = C fijos
3 0.20 $ $ lb (24)(365)h 1 pie = magua 3 1000 pies agua lb h ao ao $ $ = 0.50 ( A pies 2 ) = 2 pie ao ao

Donde:
magua = m gas cp gas (195 90) (3000)(0.3)(195 90) lb Q = = = cpagua (T0 80) cpagua (T0 80) h (1)(T0 80)
(3000)(0.3)(195 90) = pies 2 (195 T0 ) (90 80) (8) (195 T0 ) ln (90 80)

A=

Q = UTml

Paso 4. No hay nada que simplificar Paso 5. Una tcnica de solucin, es derivar la funcin objetivo en trminos de la variable T0. Igualar a cero y encontrar la solucin.
dCtotal = dT0

T0 = 120.5 F

Ctotal = 249.40
Paso 6.

$ ao

Para comprobar la solucin, se puede graficar.

GESR

Ejemplo 2
Un compuesto orgnico se produce en un proceso por lotes donde no se obtiene ningn producto hasta que se termine el procesamiento del lote. Cada ciclo consiste de un tiempo de operacin necesario para completar la reaccin ms un tiempo adicional de 1.4 h requeridas para descarga y carga. El tiempo de operacin por ciclo es igual a 1.5P0.25, donde P son los kilogramos de producto producido por lote. Los costos de operacin durante el periodo de operacin son $20 por hora, mientras que los costos durante el periodo de descarga-carga son $15 por hora. Los costos fijos anuales (Cf) del equipo, varan con el tamao del lote de la siguiente forma:
$ C f = 340 P 0.8 ao

Los cargos por almacenamiento e inventario se pueden despreciar. De ser necesario asuma que la planta puede operar 24h/da por 300 das/ao. La produccin anual es 106 kg de producto. A esta capacidad, los costos de las materias primas y miscelneas, diferentes a los ya mencionados, son de $260 000 por ao. Determine el tiempo del ciclo para obtener el mnimo costo anual total.

Paso 1.
h 1.4 muerto ciclo hoperacin 1.5P0.25 ciclo Kg producto P ciclo

tiempo para descarga y carga. tiempo de operacin por ciclo (se asume en horas) kilogramos de producto producido por lote (1 lote por cada ciclo)

GESR

$ 20 hoperacin

Costo durante el periodo de operacin Costo durante el periodo de descarga-carga Costos fijos anuales

$ 15 hmuerto
$ C f = 340 P 0.8 ao

Kg producto 106 ao
$ 260 000 ao

Produccin anual

Costos de las materias primas y miscelneas

De ser necesario asuma que la planta puede operar 24h/da por 300 das/ao. Paso 2. Minimizar los costos totales anuales en funcin de la nica variable P.

Costostotales = f ( P) =
Paso 3.

$ ao

Convertir todos los costos a $/ao y despus sumarlos. Costo durante el periodo de operacin,
h 1 ciclo 6 Kg $ 20 $ 1.5P 0.25 operacin 10 ao = ao h ciclo operacin P Kg

Costo durante el periodo de descarga-carga,

$ hmuerto 1 ciclo 6 Kg $ 15 10 ao = ao h 1.4 ciclo P Kg muerto

El costo total es,

Paso 4. No hay nada que simplificar

GESR

Paso 5. Una tcnica de solucin, es derivar la funcin objetivo en trminos de la variable P. Igualar a cero y encontrar la solucin.

dCtotal = dP P = 1625.840
Ctotal =

Kg ciclo $ ao

El tiempo de cada ciclo es,

1.4 + 1.5P 0.25 = 1.4 + 1.5(1625.84) 0.25 = 10.9

El tiempo total al ao es,

h ciclo

h 1 ciclo 6 Kg 10.9 10 6 h = 6704.2 10 = 10.9 ciclo P Kg ao ao 1625.84

El tiempo total disponible es de (24)(300)=7200 h/ao, es decir, a condiciones ptimas no se requerir todo el tiempo disponible de operacin. Paso 6. Para comprobar la solucin, se puede graficar.

10

GESR

Mtodos analticos [2]

Derivacin Univariable
Primera derivada. Es la pendiente de una recta y se define como:
f ' ( x) = lim
h0

f ( x + h) f ( x ) h

Para una funcin dada f ( x) , la pendiente en un punto estacionario (punto mnimo, mximo o de inflexin) es cero.

f ( x)
Mximo

f ' ( x) = 0

f ' ( x) = 0 f ' ( x) = 0
( x)
Mnimo

Inflexin

Segunda derivada. Sigue siendo una pendiente, pero su significado es diferente.

La serie de Taylor, es una serie infinita que puede representar una funcin como:

f ( x) = f ( x 0 ) + f ' ( x0 )( x x0 ) + f ' ' ( x0 )

Donde: x0 es un punto estacionario x es un punto alrededor de x0

( x x0 ) 2 ( x x0 ) n + L + f ( n) ( x0 ) 2! n!

Si la serie se trunca hasta el tercer trmino, 0 (en un punto estacionario) ( x x0 ) 2 f ( x) = f ( x 0 ) + f ' ( x0 )( x x0 ) + f ' ' ( x0 ) 2! ( x x0 ) 2 f ( x) = f ( x 0 ) + f ' ' ( x 0 ) 2!

11

GESR

Se despeja f ' ' ( x0 ) ,

f ' ' ( x0 ) = 2!( f ( x ) f ( x0 ) ) ( x x0 ) 2

En est ltima ecuacin, el trmino f ( x) f ( x0 ) vara de signo, los otros trminos son siempre positivos.

Para un mnimo

f ( x)

f ( x)
Como f ( x) > f ( x0 ) :

f ( x)
f ( x) f ( x0 ) siempre es positivo f ( x0 )
x

f ' ' ( x0 ) > 0 es un mnimo

x0

( x)

Para un mximo

f ( x)

f ( x0 ) f ( x) f ( x)

Como f ( x) < f ( x0 ) :
f ( x) f ( x0 ) siempre es negativo
f ' ' ( x0 ) < 0 es un mximo
x

x0

( x)

12

GESR

El resultado anterior se puede generalizar. Si el orden de la derivada es un nmero par (n): Si f(n)(xopt)>0 se trata de un mnimo Si f(n)(xopt)<0 se trata de un mximo Si f(n)(xopt)=0 se necesita de una derivada de orden mayor para definirlo Si el orden de la derivada es un nmero impar (m): Si f(m)(xopt)>0 se trata de un punto de inflexin Si f(m)(xopt)<0 se trata de un punto de inflexin Si f(m)(xopt)=0 se necesita de una derivada de orden mayor para definirlo

Ejemplo 1
x4 x2 . Decir de qu tipo se trata. Encontrar el punto estacionario de la funcin f ( x) = 2 2 Solucin:
La primera derivada de la funcin es,

f ' ( x) = 2 x 3 x = 0
La solucin de la ecuacin anterior es,

x=0 x=+ 12 x= 12 Hasta el momento se sabe que existen 3 puntos estacionarios, pero no se puede decir si se trata de un punto mnimo, mximo o de inflexin. La segunda derivada de la funcin es,

f ' ' ( x) = 6 x 2 1
Se evala cada punto estacionario y se obtiene,

f ' ' ( x = 0) = 1
f ''(x = + 1 2) = 2 f ''(x = 1 2) = 2

f ' ' ( x0 ) < 0 Se trata de un mximo

f ' ' ( x0 ) > 0 Se trata de un mnimo f ' ' ( x0 ) > 0 Se trata de un mnimo

En la siguiente grafica se pueden ver los puntos estacionarios de la funcin.

13

GESR

Ejemplo 2
Encontrar el punto estacionario de la funcin f(x)=x5. Decir de qu tipo se trata. Solucin: La primera derivada es, f(x)=5x4=0 La solucin de la ecuacin anterior es x=0. La segunda derivada de la funcin es, f(x)=20x3 f(x=0)=0 Se necesita de una derivada de orden mayor La tercera derivada de la funcin es, f(3)(x)=60x2 f(3)(x=0)=0 Se necesita de una derivada de orden mayor La cuarta derivada de la funcin es, f(4)(x)=120x f(4)(x=0)=0 Se necesita de una derivada de orden mayor La quinta derivada de la funcin es, f(5)(x)=120 f(5)(x=0)=120 como el orden de la derivada es impar (m=5), se trata de un punto de inflexin.

14

GESR

La grfica de la funcin es:

x=0 Punto de inflexin

15

GESR

Derivacin Multivariable
Gradiente
El gradiente es la derivada parcial de una funcin respecto a cada una de las variables independientes: f x 1 f f ( x1 , x2 ,L, xn ) = x2 M f xn Para una funcin dada f ( x1 , x2 ,L, xn ) , su gradiente en un punto estacionario (mnimo, mximo u otro) es cero. Por ejemplo, para la funcin:

f ( x, y ) = ( x 2) 2 + ( y 1) 2
f f ( x , y ) = x f T = [2( x 2) 2( y 1)] y
T

Su gradiente es:

Su gradiente representa la pendiente de un plano. En el punto mnimo de la funcin, la pendiente de este plano respecto al eje x y y es cero

f(x, y)
f ( x, y )

x plano

Hessiano
La serie de Taylor se puede usar para desarrollar el criterio de un mnimo o un mximo de una funcin de dos variables, ( x x0 ) 2 f ( x, y ) = f ( x0 , y0 ) + f x ( x0 , y0 )( x x0 ) + f y ( x0 , y0 )( x x0 ) + f xx ( x0 , y0 ) + 2! ( x x0 )( y y0 ) ( y y0 ) 2 + f xy ( x0 , y0 ) + f yy ( x0 , y0 ) +L 2! 2!

16

GESR

Donde los subndices x,y indican diferenciacin parcial respecto a aquellas variables. Si truncamos la serie de Taylor hasta los trminos de segundo orden y puesto que las primeras derivadas evaluadas en el punto estacionario (x0, y0) son cero: 0 0 ( x x0 ) 2 f ( x, y ) = f ( x0 , y0 ) + f x ( x0 , y0 )( x x0 ) + f y ( x0 , y0 )( x x0 ) + f xx ( x0 , y0 ) + 2! ( x x0 )( y y0 ) ( y y0 ) 2 + f xy ( x0 , y0 ) + f yy ( x0 , y0 ) 2! 2!

f ( x, y ) = f ( x0 , y0 ) + f xx ( x0 , y0 )
En forma matricial,

( x x0 ) 2 ( x x0 )( y y0 ) ( y y0 ) 2 + f xy ( x0 , y0 ) + f yy ( x0 , y0 ) 2! 2! 2!
f 1 [( x x0 ) ( y y0 )] xx 2 f yx f xy ( x x0 ) f yy ( y y 0 )

f ( x, y ) = f ( x0 , y 0 ) +

Donde: f xx f xy es la matriz de segundas derivadas parciales evaluada en el f yx f yy punto estacionario (x0, y0), a esta matriz se le llama matriz Hessiana. Para una funcin de n variables, la matriz Hessiana se puede escribir como,
2 f x12 2 f x x 2 1 H = 2 f x3x1 M 2 f xn x1 2 f x1x2 2 f 2 x2 2 f x3 x2 M 2 f xn x2 2 f x1x3 2 f x2 x3 2 f 2 x3 M 2 f xn x3 2 f x1xn 2 f L x2 xn 2 f L x3 xn M M 2 f L 2 xn L

r f ( x0 ) es un mnimo si:
H0 tiene determinantes Di > 0 donde i = 1, 2, , n (H0 se denomina positiva definida)

r f ( x0 ) es un mximo si:
H0 tiene determinantes Di < 0 para i = 1, 3, , impares y H0 tiene determinantes Di > 0 para i = 2, 4, , pares (H0 se denomina negativa definida) Donde: i, representa el tamao de la matriz H0 (filas y columnas)

17

GESR

Si el resultado es cero para cualquier valor de Di, se dice que la matriz es semi-definida positiva o semi-definida negativa, no se puede definir si se trata de un mnimo o un mximo y por lo tanto se requiere de una derivada de orden mayor para definirlo.

Ejemplo 1
Para una funcin de dos variables: f ( x, y ) = ( x 2) 2 + ( y 1) 2 . Encontrar los puntos estacionarios y decir si se trata de un mnimo, un mximo o que no se pueda definir como tal. Su gradiente es:
f x f x 2( x 2) f ( x, y ) = f = = f y 2( y 1) y

En el punto estacionario, el gradiente es cero:

f x = 2( x 2) = 0 f y = 2( y 1) = 0
La solucin del sistema de ecuaciones anterior es:

x0 = 2 y0 = 1
Las derivadas parciales del gradiente, se vuelven a derivar para formar la matriz Hessiana, es decir:
f x x H= f y x f x (2( x 2)) y x = f y ( 2 ( y 1)) x y (2( x 2)) 2 0 y = (2( y 1)) 0 2 y

Evaluada en el punto estacionario x0 = 2, y0 = 1

2 2 H0 = 2 2
La matriz Hessiana es de tamao i=2, se calcula la determinante de la matriz H0 de tamao (1 x 1) y de (2 x 2), como:

18

GESR

D1 = 2 D2 = 2 0 0 2 =2

Como D1 >0 y D2 >0, la matriz H0 es positiva definida, por lo tanto se trata de un mnimo. f ( x0 = 2, y0 = 1) = 0 La grfica de la funcin es:

Ejemplo 2
Para la siguiente funcin: . Encontrar los puntos estacionarios y decir si se trata de un mnimo, un mximo o que no se pueda definir como tal. Su gradiente es:
f x f ( x, y ) = f = y

En el punto estacionario, el gradiente es cero:

0 = 0

19

GESR

La solucin del sistema de ecuaciones anterior es:

Las derivadas parciales del gradiente, se vuelven a derivar para formar la matriz Hessiana:

En el punto 1:

H0 =
D1 = D1 = D2 = D2 =

Como D1 =0 y D2 <0, no se trata ni de un mnimo, ni de un mximo, se necesitan de derivadas de orden mayor para definirlo.

f ( x0 = 0, y0 = 0) = 3
En el punto 2:

H0 =
D1 = D1 = D2 = D2 =

Como D1 >0 y D2 >0, se trata de un mnimo.

f ( x0 = 0.6541, y0 = 0.91618) = 2.3611

La grfica de la funcin es:

20

GESR

Ejemplo 3
. Encontrar los puntos estacionarios y decir si se trata de un mnimo, un mximo o que no se pueda definir como tal. Su gradiente es:
f x f ( x, y ) = f y = f z

Para la siguiente funcin:

En el punto estacionario, el gradiente es cero:

0 = 0 0

La solucin del sistema de ecuaciones anterior es:

Las derivadas parciales del gradiente, se vuelven a derivar para formar la matriz Hessiana:

21

GESR

En el punto estacionario:

H0 =
D1 = D1 = D2 = D2 =

D3 = D3 =
Como D1 >0, D2 <0 y D3 <0 no se trata ni de un mnimo, ni de un mximo, se necesitan de derivadas de orden mayor para definirlo.

22

GESR

Multiplicadores de Lagrange
Se aplica a problemas de optimizacin multivariable con restricciones de igualdad y desigualdad

Ejemplo 1
Optimizar: Sujeto a:
f ( x1 , x2 ) = x1 + x2
2 h( x1 , x2 ) = x12 + x2 1 = 0

En tercera dimensin, el problema se ve como:

El plano inclinado es la funcin objetivo a optimizar que corta al cilindro que es la restriccin.

Si se ve desde arriba, obtendremos una grfica que se llama de contornos

f = 1.4142 f = 0.7000 f = 0.0000 f = -0.7000 f = -1.4142

Cada recta representa un valor constante de f ( x1 , x2 ) y el valor ptimo debe estar sobre el crculo (porque es una restriccin de igualdad).

De la grfica anterior se puede ver que el problema tiene dos valores ptimos, un mnimo en f ( x1 = 0.7071, x2 = 0.7071) =-1.4142 y un mximo en f ( x1 = 0.7071, x2 = 0.7071) = 1.4142.

23

GESR

Slo en un punto estacionario, los vectores h y f vectorialmente, en este caso:

se pueden relacionar

f f
h
f = h

El valor y signo de la variable (llamada multiplicador de Lagrange) no tiene ningn significado cualitativo, solo relaciona el gradiente de la funcin objetivo con el gradiente de las restricciones de igualdad. Resolviendo el problema por multiplicadores de Lagrange. La restriccin se iguala acero y la funcin L es:

Se calcula el gradiente de L y cada una de las ecuaciones se iguala a cero:

Resolviendo el sistema de ecuaciones anterior, la solucin es:

Solucin 1 Solucin 2

24

GESR

Cuando existen restricciones de desigualdad que llegan a formar parte de la solucin, es decir, desigualdades que se convierten en igualdades, los multiplicadores de Lagrange se conoce como condiciones de Kuhn-Tucker o Karush- Kuhn-Tucker. Hasta el momento no se puede definir si se trata de un mnimo o un mximo. Para eso se tendran que calcular las condiciones de segundo orden.

Ejemplo 2
Optimizar: f = x + 2y2 + z2 Sujeta a: x + y + z =1 x y = -2 Las restricciones se igualan acero y la funcin L es:

Se calcula el gradiente de L y cada una de las ecuaciones se iguala a cero:

Resolviendo el sistema de ecuaciones, la solucin es:

25

GESR

Mtodos numricos [2]

Fibonacci
El mtodo de Fibonacci es considerado como uno de los mejores mtodos para optimizacin univariable. A partir de un intervalo de solucin dado (a, b), el mtodo de Fibonacci reduce ste intervalo calculando dos puntos intermedios simtricos (x1, x2), la funcin objetivo f(x) se evala en estos dos puntos; Para minimizar se elimina el punto con el mayor valor de f(x) y para maximizar se elimina el punto con el menor valor de f(x)); el proceso de eliminacin se repite hasta un nmero determinado de intervalos.

f(x2) x1 Para la siguiente iteracin este intervalo se elimina x2 b

f(x1) a

En la grfica de abajo se muestra un ejemplo del mtodo de Fibonacci. Se realizan 4 iteraciones con 5 intervalos calculados. Se supone que el punto b no cambia.

26

GESR

|
Iteracin 1

1 3 2

1 = 2 + 3 a x1 x2 2
Iteracin 2

2 = 3 + 4

x1

x2

x3 3

Iteracin 3

3 = 4 + 5 x2 x3 x4 b

Iteracin 4

4 5

5 = 4 + 2 2

x3 x4 x5 b En la ltima iteracin 4, si es muy pequeo 0 .

5 =

4 2

Despejando 4 y sustituyendo de la iteracin 4 hasta la iteracin 1,

4 = 2 5 3 = 4 + 5 = 2 5 + 5 = 3 5 2 = 3 + 4 = 3 5 + 2 5 = 5 5

27

GESR

1 = 2 + 3 = 5 5 + 3 5 = 8 5
Igualando el intervalo 5 de la iteracin 1 y la iteracin 2, 5 = 1 = 2 8 5 En la iteracin 1,
1 = (b a ) 2 = (b x1 )

2 = ( x2 a )

(b a) (b x1 ) = 8 5 x1 = b 5(b a) 8

(b a) ( x2 a) = 8 5 x2 = a + 5(b a) 8

Si se realizarn n iteraciones,
x1 = b x2 = a +

Donde:
=

fm f m +1

(b a )

m fm

0 0

1 1

2 1

3 2

4 3

5 5

6 8

7 13

8 21

9 34

10 55

m f m = f m1 + f m2

m: es el nmero de intervalos calculados, m=n+1 n: es el nmero de iteraciones

Ejemplo
Maximizar: Intervalo inicial: Iteraciones: Solucin: Con m= 5 intervalos, f 5 = 5 y f 6 = 8

y = 3 + 6x 4x 2 a=0, b=1 n = 4 (m=n+1=5 intervalos)

28

GESR

5 = (1 0) = 0.625 8
Iteracin 1
a=0
x1 = b = 1.0 0.625 = 0.375 f 1 = f ( x1 = 0.375) = 4.6875 x2 = a + = 0.0 + 0.625 = 0.625 f 2 = f ( x 2 = 0.625) = 5.1875

b=1

f1 < f 2 Se elimina el punto a=0

El nuevo intervalo es: a=0.375 < x < b=1.0 = (1.0 0.625) = 0.375 Iteracin 2
a=0.375
x1 = 0.625 f1 = 5.1875 x 2 = a + = 0.375 + 0.375 = 0.750 f 2 = f ( x 2 = 0.750) = 5.2500 f1 < f 2 Se elimina el punto a=0.375

b=1

El nuevo intervalo es: a=0.625 < x < b=1.0 = (1.0 0.750) = 0.250 Iteracin 3
a=0.625
x1 = 0.750 f1 = 5.2500 x 2 = a + = 0.625 + 0.250 = 0.875 f 2 = f ( x 2 = 0.875) = 5.1875 f1 > f 2 Se elimina el punto b=1.0

b=1.0

El nuevo intervalo es: a=0.625 < x < b=0.875 = (0.750 0.625) = 0.125 Iteracin 4
a=0.625
x1 = b = 0.875 0.125 = 0.750 f1 = f ( x1 = 0.750) = 5.2500 f1 = f 2 x2 = 0.750 f 2 = 5.2500

b=0.875

La solucin es x= 0.750

29

GESR

Seccin dorada
El mtodo de seccin dorada es similar al mtodo de Fibonacci.

Iteracin 1

1 3 2

1 = 2 + 3
1 2 = +1 3 3

x1

x2 2 4 3

Iteracin 2

2 = 3 + 4 2 3 = +1 4 4

x1

x2

x3

3
Iteracin 3

3 = 4 + 5
3 4 = +1 5 5 x2 x3 x4
b

Iteracin 4

4 6 5

4 = 5 + 6 4 5 = +1 6 6

x3 x4 x5 b

De la grfica anterior, se puede obtener lo siguiente:

30

GESR

2 3 4 5 = = = = 3 4 5 6 En la iteracin 2 tenemos, 2 3 = +1 4 4

( es una constante)

Si dividimos y multiplicamos el lado izquierdo por 3 ,

2 3 3 = +1 3 4 4

= + 1
2 1 = 0

En la iteracin 1,
2 = 3

1 = (b a ) 2 = (b x1 )
(b a ) = (b x1 )

2 = ( x2 a )
(b a ) = ( x2 a )

x1 = b

(b a )

x2 = a +

(b a)

Ejemplo
Minimizar En el intervalo: Iteraciones: Tolerancia

f ( x) = 0.5 x exp( x 2 ) a=0, b=2 n=4 t=0.1

31

GESR

=
Iteracin 1
a=0

(b a)

(2 0) = 1.2361 1.618

x1 = b = 2 1.2361 = 0.7639 x1 = a + = 0 + 1.2361 = 1.2361 f1 = f ( x1 = 0.7639) = 0.0738 f 2 = f ( x2 = 1.2361) = 0.2318 f1 < f 2 Se elimina el punto b=2

b=2

El nuevo intervalo es:

a=0 < x < b=1.2361 error = 1.2361 0 = 1.2361

= (0.7639 0) = 0.7639
Iteracin 2
a=0
x1 = b = 1.2361 0.7639 = 0.4721 x1 = 0.7639

b=1.2361

f1 = f ( x1 = 0.4721) = 0.1222 f 2 = 0.0738 f1 > f 2 Se elimina el punto a=0

El nuevo intervalo es:

a=0.4721 < x < b=1.2361 error = 1.2361 0.4721 = 0.7640

= (1.2361 0.7639) = 0.4722

Iteracin 3
a=0.4721
x1 = 0.7639 f1 = 0.0738 x1 = a + = 0.4721 + 0.4722 = 0.9443 f 2 = f ( x2 = 0.9443) = 0.1129 f1 < f 2 Se elimina el punto b=1.2361

b=1.2361

El nuevo intervalo es:

a=0.4721 < x < b=0.9443 error = 0.9443 0.4721 = 0.4722

= (0.7639 0.4721) = 0.2918

Iteracin 4
a=0.4721
x1 = b = 0.9443 0.2918 = 0.6525 x1 = 0.7639 f1 = f ( x1 = 0.6525) = 0.0737 f 2 = 0.0738 f1 < f 2 Se elimina el punto b=0.9443

b=0.9443

El nuevo intervalo es:

a=0.4721 < x < b=0.7639 error = 0.7639 0.4721 = 0.2918

32

GESR

Se cumplen las 4 iteraciones, pero no se cumple la tolerancia. El mejor punto obtenido es x1=0.6525 Simplex [3] El mtodo de mxima pendiente se aplica a problemas multivariables sin restricciones. En geometra, un simplex o n-simplex es el anlogo en n dimensiones de un tringulo. Por ejemplo, un 0-simplex es un punto; un 1-simplex un segmento de una lnea; un 2simplex un tringulo; un 3-simplex es un tetraedro; y un 4-simplex es un pentcoron. En la optimizacin problemas multivariables, para resolver un problema de 2 variables independientes necesitaremos un tringulo, para 3 variables un tetraedro, para 4 variables un pentcoron y as sucesivamente. Por ejemplo, un simplex regular para 2 variables independientes es,

x2

centroide
3

x1 La funcin f ( x1 , x2 ) se evala en los puntos 1, 2 y 3, para minimizar se elimina el punto que produzca el menor valor de f ( x1 , x2 ) (para maximizar se elimina el punto que produzca el mayor valor de f ( x1 , x2 ) ). Si se elimina el punto 1, este punto se proyecta al lado contrario para encontrar un nuevo punto 4. El proceso se repite hasta que ya no sea posible minimizar ms la funcin. De los textos de geometra analtica se puede demostrar que las coordenadas de los vrtices de un simplex regular se pueden obtener de la siguiente tabla:

33

GESR

m puntos

1 2 3 4 M m=n+1 Donde:
d1 = t n 2 t d2 = n 2

1 x1 d1 + x1 d2 + x1 d2 + x1 M d2 + x1

n variables 2 3 x2 x3 d2 + x2 d2 + x3 d1 + x2 d2 + x3 d2 + x2 d1 + x3 M M d2 + x2 d2 + x3

... M

n xn d2 + xn d2 + xn d2 + xn M d1 + xn

(
(

n + 1 + n 1
n + 1 1

t , es la distancia entre dos puntos del simplex (o bien, es la tolerancia)

Ejemplo 1
f ( x1 , x2 ) = ( x1 3) 2 + ( x2 4) 2 Minimizar: Punto inicial: x1=0.5, x2=1.0 Tolerancia: t=0.1
Solucin: El problema es de 2 variables independientes x1 y x2, se necesitan m=2+1=3 puntos.
d1 = d2 = t n t n 2

( 2

n + 1 + n 1 =

0.1 2 + 1 + 2 1 = 0.0966 2 2 0.1 n + 1 1 = 2 + 1 1 = 0.02589 2 2

Punto 1 2 3

x1 0 .5 0.0966 + 0.5 0.0259 + 0.5

x2 1 .0 0.0259 + 1.0 0.0966 + 1.0

f(x1, x2) 15.2500 14.6218 14.5510

Tringulo

1, 2, 3

Para minimizar, se elimina el punto con el mayor valor de f ( x1 , x2 ) , en este caso es el punto 1.
Punto 1 2 x1 0.5 0.5966 x2 1.0 1.0259 f(x1, x2) 15.2500 14.6218 Tringulo

34

GESR

3 Centroide:

0.5259

1.0966

14.5510

1, 2, 3

x1C =

1 n

[( x ) x ]
1
e 1

C x2 =

1 n

[( x ) x ]
2
e 2

Donde el superndice c es para centroide y e es para eliminado

x1C =
C x2 =

1 [(0.5 + 0.5966 + 0.5259) 0.5] = 0.56125 2 1 [(1.0 + 1.0259 + 1.0966) 1.0] = 1.06125 2

Punto reflejado:

x1 = 2 x1C x1e
x1 = 2(0.56125) 0.5 = 0.6225

C e x2 = 2 x2 x2

x2 = 2(1.06125) 1.0 = 1.1225

Como el valor de la funcin en el punto 4, es menor que el punto eliminado 1, el proceso se repite de lo contrario se detiene. Para minimizar, se elimina el punto con el mayor valor de f ( x1 , x2 ) , en este caso es el punto 2.
Punto 1 2 3 4 x1 0.5 0.5966 0.5259 0.6225 x2 1.0 1.0259 1.0966 1.1225 f(x1, x2) 15.2500 14.6218 14.5510 13.9328 Tringulo

1, 2, 3 2, 3, 4

Centroide:

x1C =
C x2 =

1 [(0.5966 + 0.5259 + 0.6225) 0.5966] = 0.5742 2 1 [(1.0259 + 1.0966 + 1.1225) 1.0259] = 1.10955 2

Punto reflejado:
x1 = 2(0.5742) 0.5966 = 0.5518 x2 = 2(1.10955) 1.0259 = 1.1932

35

GESR

Como el valor de la funcin en el punto 5, es menor que el punto eliminado 2, el proceso se repite de lo contrario se detiene. Se elimina el punto con el mayor valor de f ( x1 , x2 ) , en este caso es el punto 3.
Punto 1 2 3 4 5 x1 0.5 0.5966 0.5259 0.6225 0.5518 x2 1.0 1.0259 1.0966 1.1225 1.1932 f(x1, x2) 15.2500 14.6218 14.5510 13.9328 13.8721 Tringulo

1, 2, 3 2, 3, 4 3, 4, 5

La tabla completa de resultados es,

Punto 1 2 3 4 5 6 7 8 9 10 M 81 82 83 84 85 86 87 88 89 90 x1 0.5000 0.5966 0.5259 0.6225 0.5518 0.6484 0.5776 0.6742 0.6035 0.7001 M 2.7374 2.7632 2.6925 2.7891 2.8598 2.8857 2.8150 2.9116 2.9823 3.0082 x2 1.0000 1.0259 1.0966 1.1225 1.1932 1.2191 1.2898 1.3157 1.3864 1.4123 M 3.6616 3.7582 3.8289 3.8548 3.7841 3.8807 3.9514 3.9773 3.9066 4.0032 f(x1,x2) 15.2500 14.6218 14.5510 13.9328 13.8721 13.2638 13.2131 12.6149 12.5741 11.9859 M 0.1835 0.1145 0.1238 0.0655 0.0663 0.0273 0.0366 0.0083 0.0090 0.0001 Tringulo

1 4 4 4 7 7 7 10 M 81 81 83 83 85 85 87 87 89 89

2 2 5 5 5 8 8 8 M 80 80 80 84 84 84 84 88 88 88

3 3 3 6 6 6 9 9 M 78 82 82 82 82 86 86 86 86 90

En el punto 90, se obtiene el resultado final de:

x1 = 3.0082 x2 = 4.0032 f ( x1 = 3.0082, x2 = 4.0032) = 0.0001

36

GESR

Ejemplo 2
Minimizar: f ( x1 , x 2 ) = ( x1 3) 2 + ( x2 4) 2 + ( x3 5) 2 Punto inicial: x1=0.0, x2=0.0, x3=0.0 Tolerancia: t=0.1 Solucin:
Punto 1 2 3 4 5 6 7 8 9 10 M 230 231 232 233 234 235 236 237 238 239 x1 0.0000 0.0943 0.0236 0.0236 0.0943 0.0000 0.0550 0.0759 0.1502 0.0931 M 2.9066 2.9671 2.9335 3.0006 3.0275 3.0073 2.9782 2.9185 3.0026 3.0736 x2 0.0000 0.0236 0.0943 0.0236 0.0943 0.1179 0.0629 0.1598 0.0934 0.1164 M 3.8418 3.8929 3.9353 3.8614 3.9513 3.9390 4.0224 3.9799 4.0256 4.0115 x3 0.0000 0.0236 0.0236 0.0943 0.0943 0.1179 0.1807 0.1676 0.1772 0.2561 M 4.8971 4.8361 4.9202 4.9249 4.8903 4.9875 4.9405 5.0085 5.0374 4.9685 f(x1,x2,x3) 50.0000 49.0201 48.8786 48.7372 47.7639 47.9065 47.3998 46.6496 46.6424 46.0372 M 0.0443 0.0394 0.0150 0.0249 0.0152 0.0039 0.0045 0.0071 0.0021 0.0065 Tetraedro 2 3 2 3 2 3 2 3 2 3 6 3 6 7 6 7 9 7 9 7 M M 230 228 230 231 230 231 230 231 234 231 234 235 234 235 237 235 237 235 239 235

1 1 1 1 5 5 5 5 5 10 M 229 229 229 233 233 233 236 236 236 236

4 4 4 4 4 4 4 8 8 8 M 227 227 232 232 232 232 232 232 238 238

En el punto 239, se obtiene el resultado final de:

x1 = 3.0736 x2 = 4.0115 x2 = 4.9685 f ( x1 = 3.0736, x2 = 4.0115, x3 = 4.9685) = 0.0065

37

GESR

Nelder-Mead [4]
El mtodo de Nelder-Mead es una versin ms eficiente del mtodo simplex que permite que las figuras geomtricas se reflejen agregando un coeficiente , se contraigan con un coeficiente o se expandan con un coeficiente . El mtodo es muy robusto para hacerlo manualmente, pero se implementa fcilmente en un cdigo de computadora. Los valores de los coeficientes , y recomendados por los autores del mtodo son: =1 = 0.5 =2

Ejemplo 1
f ( x1 , x2 ) = ( x1 3) 2 + ( x2 4) 2 Minimizar: Punto inicial: x1=0.5, x2=1.0 Tolerancia: t=0.1
Solucin:
Punto 1 2 3 4 5 6 7 8 9 x1 0.5259 0.7449 0.7519 1.4160 2.1010 2.1010 2.1010 2.1790 2.1790 x2 1.0970 1.2450 1.6050 2.4110 4.2980 4.2980 4.2980 4.1280 4.1280 f(x) 14.5500 12.6800 10.7900 5.0340 0.8971 0.8971 0.8971 0.6909 0.6909 error 0.3142 0.9012 1.5360 3.2500 4.0560 1.8680 0.1990 0.2410 0.0889

En el punto 9, se obtiene el resultado final de:

x1 = 2.1790 x2 = 4.1280 f ( x1 = 2.1790, x2 = 4.1280) = 0.6909

38

GESR

Ejemplo 2
Minimizar: f ( x1 , x 2 ) = ( x1 3) 2 + ( x2 4) 2 + ( x3 5) 2 Punto inicial: x1=0.0, x2=0.0, x3=0.0 Tolerancia: t=0.1 Solucin:
iteracin 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 x1 0.0236 0.1886 0.1886 0.2959 0.6591 0.6591 1.6400 1.6400 3.2390 3.2390 3.2390 3.2390 3.2390 3.2390 3.2390 3.2390 3.2370 3.2370 3.2370 x2 0.0236 0.1886 0.1886 0.2409 0.7429 0.7429 1.5470 1.5470 3.5000 3.5000 3.5000 3.5000 3.5000 3.5000 3.5000 3.5000 3.6360 3.6360 3.6360 x3 0.0943 0.1886 0.1886 0.5474 0.9393 0.9393 2.6650 2.6650 5.3030 5.3030 5.3030 5.3030 5.3030 5.3030 5.3030 5.3030 5.4530 5.4530 5.4530 f(x) 48.7400 45.5800 45.5800 41.2700 32.5800 32.5800 13.3200 13.3200 0.3992 0.3992 0.3992 0.3992 0.3992 0.3992 0.3992 0.3992 0.3938 0.3938 0.3938 error 0.4958 1.4310 1.4320 2.7050 5.4930 5.4530 10.2900 9.8120 11.4800 6.1800 5.0450 1.4960 0.6770 0.5322 0.4255 0.1239 0.1386 0.1132 0.0095

En el punto 239, se obtiene el resultado final de:

x1 = 3.2370 x2 = 3.6360 x2 = 5.4530 f ( x1 = 3.2370, x2 = 3.6360, x3 = 5.4530) = 0.3938

39

GESR

Mxima Pendiente [1]

El mtodo de mxima pendiente se aplica a problemas multivariables sin restricciones. r r Para una funcin objetivo de la forma: f = f ( x ) donde x es un vector. El procedimiento de clculo es el siguiente:
r1 Paso 1. Estimar un punto inicial [x ] r Paso 2. Calcular el gradiente de la funcin f ( x ) = [f x1 f x2 L f xn ] r1 r n +1 rn r n Paso 3. Sustituir el punto inicial [x ] en: [x ] = [x ] [f ( x )] Donde n = 1, 2 , , nmero mximo de iteraciones r n +1 rn r n Paso 4. Sustituir [x ] en la funcin objetivo: f = f ([x ] [f ( x )] ) = f ( ) Paso 5. Minimizar la funcin f ( ) y sustituir Paso 6. Repetir pasos 3 a 5 hasta cumplir la tolerancia o un nmero mximo de iteraciones.

Ejemplo 1
Minimizar: Punto inicial Nmero mximo de iteraciones: Tolerancia:

f = f ( x, y ) = ( x 2) 2 + ( y 6) 2 x=0.5, y=0.8 5 0.01

Solucin: Se calcula el gradiente de la funcin objetivo:

f = 2( x 2) x f = 2( y 6) x

Calcular un nuevo punto (x, y):

x = x f = x (2( x 2)) x f y = y = y (2( y 6)) y

Iteracin 1

Se hace la sustitucin del punto inicial en el sistema de ecuaciones,

40

GESR

Se sustituye en la funcin objetivo, se deriva respecto a y se obtiene el valor de ,

Se sustituye y se obtiene un nuevo punto inicial,

El error es,

Iteracin 2

Se hace la sustitucin del punto inicial,

Como ya no aparece la variable , se termina y el valor final es,

El error es,

Los resultados se resumen en la siguiente tabla,

error=mxxn+1-xn 5.2 0

Iteracin 0 1 2

x 0.5 2.0 2.0

y 0.8 6.0 6.0

f(x, y) 29.29 0 0

41

GESR

Ejemplo 2
Minimizar: Punto inicial Nmero mximo de iteraciones: Tolerancia:

f = f ( x, y , z ) = 2 x 2 + y 2 + 3 z 2 x=2, y= -2, z= 1 5 0.5

Se calcula el gradiente de la funcin objetivo:

f = 4x x f = 2y x f = 6z z Calcular un nuevo punto (x, y, z):

f = x (4 x) x f y = y = y (2 y ) y f z = z = z (6 z ) z x = x Iteracin 1

Se hace la sustitucin del punto inicial,

Se sustituye en la funcin objetivo, se deriva respecto a y se obtiene el valor de ,

Se sustituye y se obtiene un nuevo punto inicial,

42

GESR

El error es,

Iteracin 2

Se hace la sustitucin del punto inicial,

Se sustituye en la funcin objetivo, se deriva respecto a y se obtiene el valor de ,

Se sustituye y se obtiene un nuevo punto inicial,

El error es,

43

GESR

Iteracin 3

Se hace la sustitucin del punto inicial,

Se sustituye en la funcin objetivo, se deriva respecto a y se obtiene el valor de ,

Se sustituye y se obtiene un nuevo punto inicial,

El error es,

Los resultados se resumen en la siguiente tabla,

Iteracin 0 1 2 3 x 2 0.15873 0.00424 -0.00011 y -2 -1.07937 -0.55409 -0.26956 z 1 -0.38095 0.17522 -0.09471 f(x, y) error=mxxn+1-xn 15 1.65079 1.8412 0.39916 0.55617 0.09957 0.28453

44

GESR

Programacin lineal [1,2]

En este mtodo, la palabra programacin significa optimizacin y no a la generacin de un cdigo de computadora. Un problema de programacin lineal involucra la optimizacin de una funcin objetivo lineal sujeta a restricciones de igualdad y desigualdad, que tambin son lineales. Los mtodos utilizados para resolver un problema de programacin lineal son: Grfico, solo aplicable a problemas de 2 variables independientes. Simplex, aplicable a problemas de 2 o ms variables independientes. Punto interior, aplicable a problemas de 2 o ms variables independientes.

Mtodo grfico.
Ejemplo
Maximizar: Sujeto a:
f = x1 + 3 x2 x1 + x2 1 x1 + x2 2 x1 + x2 1 x1 0, x2 0

(1) (2) (3)

Solucin: Graficar Se grafican las restricciones que son rectas (para graficar una recta se necesitan dos puntos): Para la restriccin 1: x1 + x2 1 , se toma como igualdad, x1 + x2 = 1 Si x1=0, entonces x2=-1, punto 1 (x1,x2)=(0,1) Si x2=0, entonces x1=1, punto 2 (x1,x2)=(-1,0) Para la restriccin 2: x1 + x2 2 , se toma como igualdad, x1 + x2 = 2 Si x1=0, entonces x2=2, punto 1 (x1,x2)=(0,2) Si x2=0, entonces x1=2, punto 2 (x1,x2)=(2,0) Para la restriccin 3: x1 + x2 1 , se toma como igualdad, x1 + x2 = 1 Si x1=0, entonces x2=2, punto 1 (x1,x2)=(0,1) Si x2=0, entonces x1=2, punto 2 (x1,x2)=(1,0)

45

GESR

x1 + x2 2
2

x2

x1 + x2 1

x1 + x2 1
1

-1 Regin factible

x1

Se toma un punto de referencia, por ejemplo el origen que tiene coordenadas (x1,x2)=(0,0). Se sustituye en cada una de las restricciones:
x1 + x2 1 : 0 + 0 1 , 0 1 Verdadero x1 + x2 2 : 0 + 0 2 , 0 2 Verdadero x1 + x2 1 : 0 + 0 1 , 0 1 Falso x1 0 , x2 0 indican el primer cuadrante

La regin factible de cada recta apunta hacia el punto de referencia, en este caso, si el resultado es verdadero hacia el origen, si es falso hacia el lado opuesto del origen.

x1 + x2 2
2

x2

x1 + x2 1

x1 + x2 1
1

-1

x1 46

GESR

Se seala la regin factible que satisface a todas las restricciones. Es la regin, cuyos lados sealan todos hacia adentro. x2 2

x1 + x2 2

x1 + x2 1

x1 + x2 1
1

-1 Punto ptimo

x1

Se evalan las coordenadas de c/u de las esquinas de la regin factible x2 2

x1 + x2 2

x1 + x2 1

x1 + x2 1
1

-1

x1

Punto A B C D

x1 0.5000 0.000 2.000 1.000

x2 1.500 1.000 0.000 0.000

f(x1,x2) 5.000 3.000 2.000 1.000

El punto con el mayor valor de f(x1, x2) es el punto A.

47

GESR

Mtodo Simplex
Ejemplo
Maximizar: Sujeto a:
f = x1 + 3 x2 x1 + x2 1 x1 + x2 2 x1 + x2 1 x1 0, x2 0

(1) (2) (3)

Las variables de la funcin objetivo y las restricciones se pasan al lado izquierdo, dejando las constantes del lado derecho.
f x1 3 x 2 = 0 x1 + x 2 1 x1 + x2 2 x1 + x2 1 x1 0, x2 0

Las desigualdades se convierten a igualdades, agregando una variable de holgura positiva por cada restriccin. Por ejemplo, si tuviramos la desigualdad 3 5 , tenemos dos opciones para convertirla a igualdad agregando el nmero positivo 2. Opcin 1: Opcin 2: sumar del lado menor restar del lado mayor
3+ 2 = 5 3= 52

Para nuestro problema,

f x1 3 x 2 = 0 x1 + x2 + x3 = 1 x1 + x 2 + x 4 = 2 x1 + x2 x5 = 1

x1 0, x2 0, x3 0, x4 0, x5 0
Se hace una tabla con los coeficientes de la funcin objetivo y las restricciones,
Tabla 1

f
E1 E2 E3 E4

x1

x2

x3
0 1 0 0

x4

x5
0 0 0 -1

1 0 0 0

-1 -1 1 1

-3 1 1 1

0 0 1 0

0 1 2 1

48

GESR

Solucin parcial Variables bsicas. Una variable es bsica si tiene solamente un coeficiente diferente de cero y su valor es la divisin de la constante b entre el coeficiente. Variables no bsicas. Una variable es no bsica si tiene ms de un coeficiente diferente de cero y su valor es cero.

1 2 1 = 1 Bsicas: x3 = = 1 , x4 = = 2 , x5 = 1 1 1 No bsicas: x1 = 0 , x 2 = 0
El valor de la funcin objetivo es f ( x1 = 0, x 2 = 0) = 0 (valor en la esquina superior derecha de la tabla) Pivote Columna pivote. En el primer rengln (funcin objetivo), se elige el menor nmero negativo. Si no hay negativos, se detiene el proceso iterativo. Rengln pivote. Se divide la constante b entre su respectivo coeficiente de la columna pivote. Se elige el menor nmero positivo diferente de cero. El pivote es la interseccin de la columna pivote y el rengln pivote.

f
1 0 0 0 Eliminacin

x1

x2

x3
0 1 0 0

x4

x5
0 0 0 -1

-1 -1 1 1

-3 1 1 1

0 0 1 0

0 1 2 1

1/1= 1 2/1= 2 1/1= 1

Se hacen ceros los coeficientes arriba y abajo del pivote. El modo de eliminacin es: Ecuacin = Ecuacin (nmero a eliminar/ pivote) Ecuacin pivote

f
E1=E1-(1/-3)E2 E2=E2 E3=E3-(1/1)E2 E4=E4-(1/1)E2
1-(-3/1)0

x1
-1-(-3/1)-1

x2
-3-(-3/1)1

x3
0-(-3/1)1

x4
0-(-3/1)0

x5
0-(-3/1)0

b
0-(-3/1)1

0
0-(1/1)0 0-(1/1)0

-1
1-(1/1)-1 1-(1/1)1

1
1-(1/1)1 1-(1/1)1

1
0-(1/1)1 0-(1/1)0

0
1-(1/1)0 0-(1/1)1

0
0-(1/1)0 -1-(1/1)0

1
2-(1/1)1 1-(1/1)2

49

GESR

Tabla 2

f
E1 E2 E3 E4

x1

x2

x3
3 1 -1 -1

x4

x5
0 0 0 -1

1 0 0 0

-4 -1 2 2

0 1 0 0

0 0 1 0

3 1 1 0

Solucin parcial Bsicas: No bsicas: El valor de la funcin objetivo es: Pivote

1 1 0 x 2 = = 1 , x 4 = = 1 , x5 = =0 1 1 1 x1 = 0 , x3 = 0 f ( x1 = 0, x 2 = 1) = 3

f
1 0 0 0 Eliminacin

x1

x2

x3
3 1 -1 -1

x4

x5
0 0 0 -1

-4 -1 2 2

0 1 0 0

0 0 1 0

3 1 1 0

1/-1= -1 1/2= 0.5 0/2= 0

f
E1=E1-(-4/2)E3 E2=E2-(-1/2)E3 E3 E4=E4-(2/2)E3
1-(4/2)0 0-(-1/2)0

x1
-4-(4/2)2 -1-(-1/2)2

x2
0-(4/2)0 1-(-1/2)0

x3
3-(4/2)-1 1-(-1/2)-1

x4
0-(4/2)1 0-(-1/2)1

x5
0-(4/2)0 0-(-1/2)0

b
3-(4/2)1 1-(-1/2)1

0
0-(2/2)0

2
2-(2/2)2

0
0-(2/2)0

-1
-1-(2/2)-1

1
0-(2/2)1

0
-1-(2/2)0

1
0-(2/2)1

Tabla 3

f
1 0 0 0

x1

x2

x3
1 0.5 -1 0

x4

x5
0 0 0 -1

0 0 2 0

0 1 0 0

2 0.5 1 -1

5 1.5 1 -1

Solucin final (porque ya no hay nmeros negativos en el primer rengln) 1 1.5 1 x1 = = 0.5 , x2 = = 1.5 , x5 = =1 Bsicas: 2 1 1 x3 = 0 , x 4 = 0 No bsicas: f ( x1 = 0.5, x2 = 1.5) = 5 El valor de la funcin objetivo es:

50

GESR

Programacin geomtrica [2]

La programacin geomtrica se aplica a polinomios.

Ejemplo de polinomios con trminos positivos

Minimizar: P W = 2 100
0.286

P3 + P 2

0.286

1000 + P 3

0.286

Es recomendable que las variables y constantes que estn dividiendo, pasen del denominador al numerador.
W = 100 0.286 P2
0.286

+ P2

0.286

P3

0.286

+ 1000 0.286 P3

0.286

A cada sumando se le divide por una variable wi y esta divisin se eleva a la misma wi, con i =1,2, , # total de sumandos. Para formar una multiplicatoria:
100 0.286 P2 0.286 W = w 1
w1

P2 0.286 P30.286 w 2

w2

1000 0.286 P3 0.286 w 3

w3

Se separan las constantes de las variables: 100 0.286 1 W = w1 w2

w1 w2

10000.286 0.286 w10.286 w 2 0.286 w 20.286 w3 P3 w3 P2

w3

El exponente de cada variable se iguala a cero: 0.286 w1 0.286 w2 = 0 0.286 w2 0.286 w3 = 0 Y se agrega una ecuacin que es la sumatoria de todas las wi igual a 1. w1 + w2 + w3 = 1 Se resuelve el sistema de ecuaciones: 0.286 w1 0.286 w2 = 0 0.286 w2 0.286 w3 = 0 w1 + w2 + w3 = 1 La solucin del sistema de ecuaciones es: w1=1/3 w2=1/3 w3=1/3

51

GESR

Se sustituyen los valores de wi: W mnimo 100 0.286 = 1/ 3 1 1/ 3

1/ 3 1/ 3

1000 0.286 1/ 3

1/ 3 0

1 1

P2 P3 = 3.73
0

Cada sumando se divide entre su wi y se iguala al valor ptimo de la funcin objetivo,

W
mnimo

100 0.286 P2 = w1
=
P2
0.286

0.286

100 0.286 P2 3.73 = 1/ 3 3.73 =

P2
0.286

0.286

mnimo

P3 w2

0.286

P3 1/ 3

0.286

mnimo

1000 0.286 P3 = w3

0.286

1000 0.286 P3 3.73 = 1/ 3

0.286

De las ecuaciones anteriores, se obtiene el valor de las variables independientes: P2=215.44 P3=464.16

Ejemplo de polinomios con trminos positivos y negativos

Minimizar:
1 .1 0 .6 y = 3 x10.25 3 x1 x2

115 2 x3 x 2 x3

Es recomendable que las variables y constantes que estn dividiendo, pasen del denominador al numerador.
1 .1 0 .6 1 1 y = 3 x10.25 3 x1 x 2 115 x 2 x3 2 x3

A cada trmino se le divide por un peso wi y esta divisin se eleva a la misma wi. con i=1,2, , # total de trminos. Se hace la divisin de la multiplicatoria de los trminos positivos entre la multiplicatoria de los trminos negativos.

y=

3 x10.25 w1
1.1 0.6 3 x1 x2 w2 w2

w1

Trminos positivos
w2 w3

1 1 115 x 2 x3 2 x 3 w3 w4

Trminos negativos

52

GESR

Se separan las constantes de las variables:

3 w1 0.6 w 2+ w3 w3 w 4 y= x10.25w11.1w2 x2 x3 w4 w2 w3 3 115 2 x3 w2 w3 w4

w1

El exponente de cada variable se iguala a cero: 0.25w1 1.1w2 = 0 0.6w2 + w3 = 0 w3 w4 = 0 Y se agrega una ecuacin que es la sumatoria de todas las wi de los trminos positivos menos la suma de todas las wi de los trminos negativos igual a 1.
w1 w2 w3 w4 = 1

Se resuelve el sistema de ecuaciones: 0.25w1 1.1w2 = 0 0.6 w2 + w3 = 0 w3 w4 = 0 w1 w2 w3 w4 = 1 La solucin del sistema de ecuaciones es: w1=2 w2=5/11 w3=3/11 w4=3/11 Se sustituyen los valores de wi:

mnimo

3 2 = 3 / 11 5 / 11 3 / 11 3 115 2 x3 5 / 11 3 / 11 3 / 11

1 1 1 0 0 = 0.1067 x x2 x3
0 1

Cada trmino se divide entre su wi y se iguala al valor ptimo de la funcin objetivo, y mnimo = 3x10.25 w1 0.1067 = 3x10.25 2

53

GESR

y mnimo =

1.1 0.6 3 x1 x2 w2

0.1067 =

1.1 0.6 3x1 x2 5 / 11

y mnimo =

1 1 x3 115 x2 w3

0.1067 =

1 1 115 x 2 x3 3 / 11

y mnimo =

2 x3 w4

0.1067 =

2 x3 3 / 11

De las ecuaciones anteriores, se obtiene el valor de las variables independientes: x1 = 2.560 10-5, x2 = 2.716 105, x3 = 1.455 10-2

54

GESR

Programacin dinmica [2]

La programacin dinmica resuelve un problema de optimizacin por etapas y obtiene el ptimo con un nmero de combinaciones menor a todas las combinaciones posibles. Cada etapa tiene 4 variables: Ri (Resultado)

Si (Estado)

Etapa i

~ (Transicin) S i

Di (Decisin) Para mltiples etapas:

F3=F2+R3 R3

F2=F1+R2 R2

F1=R1 R1

Etapa 3 S3 d3

~ S S 2 3

Etapa 2

~ S 2 S1

Etapa 1

~ S1

d2

d1

El problema se comienza a resolver, a partir de la etapa final (etapa 1), debido a que cualquier decisin que se tome en esta etapa (d1) no tendr efecto en etapas subsecuentes, el flujo de informacin es de izquierda a derecha. El diagrama de etapas puede tener ramificaciones que no se contemplan aqu.

55

GESR

Ejemplo 1
Un carro tanque transporta un producto fabricado en San Francisco que debe ser entregado a cualquier puerto importante en la costa este para su envo a Europa. El costo de envo a travs del Atlntico es esencialmente igual en todos los puertos principales de la costa del este. Se desea para seleccionar la ruta ptima (el kilometraje de camino ms bajo) de San Francisco a la costa este. Las distancias relativas entre las ciudades a lo largo de las rutas posibles se muestran en el siguiente diagrama:

N0

C4

C0

S0

Diagrama por etapas. Para este problema, las etapas son el traslado de un nodo a otro: F4=F3+R4 R4 F3=F2+R3 R3 F2=F1+R2 R2 F1=R1 R1

Etapa 4 S4 d4

~ S 4 S3

Etapa 3

~ S S 2 3

Etapa 2

~ S 2 S1

Etapa 1

~ S1

d3

d2

d1

~ Identificar las variables de cada etapa (Si, di, Ri, S i )

Variable de estado (Si): El nodo de salida Variable de decisin (di): Seleccionar una ruta Variable de resultado (Ri): El kilometraje acumulado ~ Variable de transicin ( S i ): El nodo de llegada

56

GESR

Definir todos los estados posibles para todas las etapas Los estados de cada etapa son todos los nodos de salida. S4 C4 d4 F4
~ S 4

S3 N3 C3 S3

d3

F3

~ S 3

S2 N2 C2 S2

d2

F2

~ S 2

S1 N1 C1 S1

d1 1 3 7

F1 1 3 7

~ S 1 N0 N0 C0

Combinaciones Combinaciones de la etapa 2 S2 R2 N2 8 N2 7 C2 C2 C2 S2 S2 6 5 4 3 2 F2 8 7 6 5 4 3 2

~ S F2=F1+R2 2 N1 9 menor C1 10

N1 C1 S1 C1 S1

7 8 11 6 9

menor

menor

Combinaciones de la etapa 3 S3 R3 N3 1 N3 3 C3 C3 C3 S3 S3 5 6 7 8 9 F3 1 3 5 6 7 8 9

~ S F3=F2+R3 3 N2 10 menor C2 10 menor

N2 C2 S2 C2 S2 14 13 13 15 15 menor menor menor menor

Combinaciones de la etapa 4 S4 R4 C4 6 C4 5 C4 4 F4 6 5 4
~ S F4=F3+R4 4 N3 16 menor C3 18 S3 19

Se eligen las mejores combinaciones (los que tiene el menor kilometraje) y se obtiene la siguiente tabla:

57

GESR

S4 C4

d4 6

~ ~ S F4 S 4 S3 d3 F3 S2 3 16 N3 N3 1,3 10 N2,C2 N2 C3 6,7 13 C2,S2 C2 S3 8,9 15 C2,S2 S2

d2 8 6 3

F2 9 7 6

~ S S1 2 N1 N1 N1 C1 C1 S1

d1 1 3 7

F1 1 3 7

~ S 1 N0 N0 C0

Ejemplo 2
Un flujo msico de 700 lb/h se debe de distribuir entre tres reactores qumicos que operan en paralelo:

R3 = 0.08F3 - 3(N3/100)2 R2 = 0.08F2 - 2(N2/100)2 R1 = 0.08F1 - (N1/100)2 Reactor 3 N3 700 Reactor 2 N2 Reactor 1 N1

Cada reactor tiene un catalizador diferente y condiciones de operacin diferentes. El beneficio que se obtiene en cada reactor se determina por el flujo msico que se alimenta a cada reactor y es B1, B2 y B3 para N1, N2 y N3 respectivamente. Maximizar el beneficio. Diagrama por etapas Para este problema las etapas son cada reactor: F3=F2+R3 R3 F2=F1+R2 R2 F1=R1 R1

Etapa 3 d3 S3 ~ S 3 S2

Etapa 2 d2
~ S 2 S1

Etapa 1 d1
~ S1

~ Identificar las variables de cada etapa (Si, di, Ri, S i )

58

GESR

Definir todos los estados posibles para todas las etapas Es el flujo disponible antes de pasar por un reactor y lo dividiremos en incrementos de 100 (entre menor el incremento, ms exacta la solucin pero ms combinaciones y viceversa)

S3 700

d3

F3

~ S 3

S2 0 100 200 300 400 500 600 700

d2

F2

~ S 2

S1 0 100 200 300 400 500 600 700

d1 0 100 200 300 400 500 600 700

F1 0 7 12 15 16 15 12 7

~ S 1 -

Combinaciones Combinaciones de la etapa 2 S2 700 700 700 700 700 700 700 700 600 600 600 600 600 600 600 500 500 500 500 500 500 400 400 400 d2 700 600 500 400 300 200 100 0 600 500 400 300 200 100 0 500 400 300 200 100 0 400 300 200 R2 -42 -24 -10 0 6 8 6 0 -24 -10 0 6 8 6 0 -10 0 6 8 6 0 0 6 8
~ S 2 0 100 200 300 400 500 600 700

F2=F1+R2 -42 -17 2 15 22 23 mayor 18 7 -24 -3 12 21 24 21 12 -10 7 18 23 22 15 0 13 20

0 100 200 300 400 500 600 0 100 200 300 400 500 0 100 200

mayor

mayor

59

GESR

400 400 300 300 300 300 200 200 200 100 100 0

100 0 300 200 100 0 200 100 0 100 0 0

6 0 6 8 6 0 8 6 0 6 0 0

300 400 0 100 200 300 0 100 200 0 100 0

21 16 6 15 18 15 8 13 12 6 7 0

mayor

mayor

mayor

mayor mayor

Combinaciones de la etapa 3 S3 700 700 700 700 700 700 700 700 d3 700 600 500 400 300 200 100 0 R3 -91 -60 -35 -16 -3 4 5 0

~ S 3 0 100 200 300 400 500 600 700

F3=F2+R3 -91 -53 -22 2 18 27 29 mayor 23

Se eligen las mejores combinaciones (los que tiene el mayor beneficio, F) y se obtiene la siguiente tabla: S3 700 d3 100 F3 29

~ S 3 600

S2 0 100 200 300 400 500 600 700

d2 0 0 100 100 100 200 200 200

F2 0 7 13 18 21 23 24 23

~ S 2 0 100 100 200 300 300 400 500

S1 0 100 200 300 400 500 600 700

d1 0 100 200 300 400 500 600 700

F1 0 7 12 15 16 15 12 7

~ S 1 -

60

GESR

Bibliografa
[1] T.F. Edgar, D.M. Himmelblau and L.S. Lasdon, Optimization of Chemical Processes. McGraw-Hill, 2nd ed. 2001 [2] R.W. Pike, Optimization for Engineering Systems, http://www.mpri.lsu.edu/bookindex.html, 2001 [3] D.M. Himmelblau, Applied nonlinear programming, McGraw-Hill, 1972 [4] J.A. Nelder and R. Mead, A simplex method for function minimization, Computer Journal, vol 7, p 308-313, 1965

61