Optimización con Restricciones

Vista previa del material en texto

Optimización con Restricciones 
Cristián García-Campo 
Universidad de los Andes 
Optimización 
2° semestre 2018 
Optimización–Prof. Cristian García-Campo 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Contexto 
Para construir un Modelo de PM generalmente se siguen los siguientes pasos: 
 
1) Entender el Problema. 
 
2) Definir las Variables. 
 
3) Definir la Función Objetivo. 
 
4) Definir las Restricciones. 
 
5) Buscar la Soluciones. 
 
6) Interpretar los resultados. 
 
Optimización sin Restricciones 
Contexto 
Optimización–Prof. Cristian García-Campo 
Para todo punto crítico P = a,b de z=f(x,y) tal que : 
 
𝜕𝑧
𝜕𝑥
=
𝜕𝑧
𝜕𝑦
= 0 
 
Se tiene que: 
D(a,b) < 0 P es punto silla o de inflexión 
D(a,b) = 0 El test no entrega información sobre P 
D (a,b) >0 P es un mínimo o máximo local 
 
𝜕2𝑧
𝜕𝑥2
 > 0 P es un mínimo local 
 
 
𝜕2𝑧
𝜕𝑥2
 < 0 P es un máximo local 
 
𝐷 = 
𝜕2𝑧
𝜕𝑥2
 * 
𝜕2𝑧
𝜕𝑦2
 - 
𝜕2𝑧
𝜕𝑥𝜕𝑦
2
 
Optimización sin Restricciones 
Contexto 
Optimización–Prof. Cristian García-Campo 
Más Formalmente, se dice que un punto (𝑥1, 𝑥2, 𝑥3 … 𝑥𝑛) perteneciente al 
dominio D de la función f(𝑥1, 𝑥2, 𝑥3 … 𝑥𝑛) es crítico si el gradiente 
 𝛁f(𝑥1, 𝑥2, 𝑥3 … 𝑥𝑛)=0 
 
 
 
 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Contexto 
Si la función f(𝑥1, 𝑥2, 𝑥3 … 𝑥𝑛) es continua en y dos veces diferenciable en D 
su Matriz Hessiana «H» será: 
 
 
 
 
 
 
Adicionalmente se definen los determinantes de las matrices menores de H 
( ∆1, ∆2, ∆3 … . ∆𝑛) como sigue: 
 
 
 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Contexto 
Si todos los determinantes de las matrices menores son estrictamente 
positivos la matriz H se dirá definida positiva. Esto quiere decir que su 
convexidad es estrictamente positiva y por lo tanto acepta un mínimo local 
estricto. 
 
Así mismo Si los determinantes de las matrices menores impares son 
estrictamente negativos y los de las matrices menores pares estrictamente 
positivos la matriz H se dirá definida negativa. Esto quiere decir que su 
convexidad es estrictamente negativa ( ramas hacia abajo ) y por lo tanto 
acepta un máximo local estricto. 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Contexto 
Es importante destacar que estas condiciones sólo sirven para describir un punto 
mínimo o máximo local. Para determinar la optimalidad global del problema es 
necesario comparar la función objetivo evaluada en cada uno de los puntos óptimos 
locales y adicionalmente verificar que se cumplan las condiciones de existencia de 
solución óptima para el problema. 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Pregunta 
Para los siguientes problemas encuentre los puntos críticos y clasifíquelos en mínimos 
máximos o sillas. 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Pregunta 
Para los siguientes problemas encuentre los puntos críticos y clasifíquelos en mínimos 
máximos o sillas. 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Pregunta 
Para los siguientes problemas encuentre los puntos críticos y clasifíquelos en mínimos 
máximos o sillas. 
 
𝑓 𝑥, 𝑦 = 14𝑥2 − 2𝑥3 + 2𝑦2 + 4𝑥𝑦 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Solución 
Derivando e igualando a 0 para encontrar los puntos Críticos : 
 
𝜕𝑓(𝑥,𝑦)
𝜕𝑥
= 28𝑥 − 6𝑥2 + 4𝑦 = 0 
 
𝜕𝑓(𝑥,𝑦)
𝜕𝑦
= 4𝑦 + 4𝑥 = 0 
 
Reemplazando (2) en (1) y resolviendo el sistema de ecuaciones: 
28𝑥 − 6𝑥2 − 4𝑥 = 0 
24𝑥 − 6𝑥2 = 0 
4𝑥 − 𝑥2 = 0 
𝑥(4 − 𝑥) = 0 
 
Y por lo tanto x= 0 ó x=4 además por (2) y=-x por lo tanto los puntos críticos son 
entonces ( 0,0 ) y ( 4,-4) 
 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Solución 
Construyendo la matriz Hessiana: 
 
𝐻 𝑥, 𝑦 =
28 − 12𝑥 4
4 4
 
 
 
Reemplazamos los puntos críticos y calculamos el Determinante: 
 
𝐷 𝐻 0,0 =
28 4
4 4
= 112 − 16 = 96 > 0 
 
 = 28 > 0 
 
La matriz es positiva definida en ( 0,0 ) y por lo tanto es un Mínimo Local 
 
 
 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Solución 
Construyendo la matriz Hessiana: 
 
𝐻 𝑥, 𝑦 =
28 − 12𝑥 4
4 4
 
 
 
Reemplazamos los puntos críticos y calculamos el Determinante: 
 
𝐷 𝐻 4, −4 =
−20 4
4 4
= −80 − 16 = −96 < 0 
 
 = −20 < 0 
 
La matriz no es positiva ni negativa definida en ( 4,-4 ) y por lo tanto es un punto de 
silla o puntos de inflexión. 
 
 
 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Pregunta 
Para los siguientes problemas encuentre los puntos críticos y clasifíquelos en mínimos 
máximos o sillas. 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Solución 
Optimización–Prof. Cristian García-Campo 
Optimización sin Restricciones 
Extra Opcional 
Algunas funciones son difíciles de optimizar por la vía de encontrar puntos de 
gradiente nulo (incluso cuando éstas son convexas). En estos casos, es necesario buscar 
métodos alternativos para identificar sus puntos extremos como los que se describen 
en la próxima sección. 
 
 
Método de Newton 
 
Método del Gradiente 
Optimización sin Restricciones 
Cristián García-Campo 
Universidad de los Andes 
Optimización 
2° semestre 2018 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones 
Cristián García-Campo 
Universidad de los Andes 
Optimización 
2° semestre 2018 
Optimización–Prof. Cristian García-Campo 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Contexto 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Contexto 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Contexto 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Contexto 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Contexto 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Contexto 
Con todo, las condiciones necesarias de optimalidad de primer orden para problemas 
con restricciones de no negatividad son: 
 
 
𝒙𝒊 ∗
𝝏𝒇 𝒙
𝝏𝒙𝒊
= 𝟎 ∀𝒊 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Contexto 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones NN 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Contexto 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Contexto 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Contexto 
Así, las condiciones de optimalidad de Primer orden para un problema con 
restricciones de igualdad y su problema equivalente con lagrangeano L son:Las condiciones de segundo orden pueden encontrarse utilizando el Hessianno del 
Lagrangeano pero por lo general, como el dominio es restringido a las restricciones, los 
puntos óptimos tienen poco que ver con la convexidad de la función objetivo por lo 
que generalmente se debe analizar el punto de manera similar a como si fuera un 
punto de borde. 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Contexto 
Curvas de nivel de f(x) decrecientes 
Mínimo 
Dominio = h (x1,x2) 
Paraboloide o 
Elipsoide 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Contexto 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejemplo 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejemplo 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejemplo 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejemplo 
Condiciones de 
Optimalizad de 
LaGrange. 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejemplo 
Un espejo rectangular de 100x70 cm. Se ha roto por 
uno de sus vértices. La forma del pedazo es un 
triángulo rectángulo de 40x40 cm. Calcule cómo 
debe cortarse el espejo para que siga siendo 
rectangular y tenga área máxima. 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejemplo 
Variables 
x :Coordenada x del punto de Corte 
y:Coordenada y del punto de Corte 
 
Función Objetivo 
𝑀𝑎𝑥 𝐴 𝑥, 𝑦 = 100 − 𝑦 70 − 𝑥 
 
Sujeto a: 
𝑦 = 40 − 𝑥 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejemplo 
Construimos el LaGrangeano 
 
𝑀𝑎𝑥 𝐿 𝑥, 𝑦, λ = 100 − 𝑦 70 − 𝑥 + λ 40 − x − y 
 
Derivamos e igualamos a cero: 
 
𝜕𝐿
𝜕𝑥
= −100 + 𝑦 − λ=0 
 
𝜕𝐿
𝜕𝑦
= −70 + 𝑥 − λ = 0 
 
𝜕𝐿
𝜕λ
= 40 − 𝑥 − 𝑦 = 0 
 
 
 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejemplo 
Despejamos y de 1) y x de 2) y remplazamos en 3): 
 
40 − (70 + λ) − (100 + λ) = 0 
 
130 = −2λ 
 
 −𝟔𝟓 = 𝝀  𝐱 = 𝟓 ; 𝒚 = 𝟑𝟓 
 
A= 4225 cm2 
 
 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Note que no 
incluimos las 
restricciones de NN 
¿Qué pasaría si las 
incluimos? 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
¿ Que representa el valor 
de Lambda? 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Contexto 
Interpretación de los multiplicadores de Lagrange 
 
Pensemos en un problema de optimización de dos variables y una restricción como el que vimos 
recién. El multiplicador de Lagrange (λ) representa la sensibilidad de la función objetivo ante 
pequeñas variaciones del parámetro V de la restricción. Es decir, si aumentamos el parámetro V en 
∆𝑉, obtendremos que el nuevo valor de la función objetivo se puede aproximar por: 
 𝒇 𝒓∗, 𝒉∗ = 𝒇 𝒓∗, 𝒉∗ + λ ∗ ∆𝑽 
 
Para el caso general de más variables y restricciones, los multiplicadores λi representan lo mismo 
que para el caso de 2 variables y una restricción. Por lo tanto, ante una variación en ∆𝑎𝑖 del 
parámetro 𝑎𝑖 ( parámetro de la restricción de igualdad i / 𝑔𝑖 𝑥𝑖 = 𝑎𝑖 ), tenemos que la variación 
de la función objetivo se puede aproximar por: 
𝒇 𝒙𝒊 ∗ = 𝒇 𝒙𝒊 ∗ + λ𝒊 ∗ ∆𝒂𝒊 
 
 
Esto se puede interpretar también como 
𝝏𝒇(𝒙𝒊∗)
𝝏𝒂𝒊
= 𝝀𝒊 
 
 
….La demostración de esta afirmación se entregará como material opcional 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
U( x1,x2)= -7.2 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Problema 
Optimización con Restricciones 
Cristián García-Campo 
Universidad de los Andes 
Optimización 
2° semestre 2018 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones 
Cristián García-Campo 
Universidad de los Andes 
Optimización 
2° semestre 2018 
Optimización–Prof. Cristian García-Campo 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejercicios Resueltos 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejercicios Resueltos 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejercicios Resueltos 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejercicios Resueltos 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejercicios Resueltos 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejercicios Resueltos 
Máximo 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejercicios Resueltos 
Mínimo 
Optimización–Prof. Cristian García-Campo 
Optimización con Restricciones de Igualdad 
Ejercicios Resueltos