OPTIMIZACION DINAMICA PDF

Preview

Summary

RESUMEN SOBRE QUE ES OPTIMIZACION DINAMICA...

Description

Teor í aBási cadeOpt i mi z aci ón

1

Dpt o.Economí a-UNALM

OPTIMIZACION I. INTRODUCCION La optimización o programación matemática es un instrumento fundamental en la economía. Es empleada para modelizar la asignación de recursos escasos entre fines alternativos, y resolver problemas de distribución económica desarrollados en la teoría del consumidor, teoría de la producción, economía del bienestar, equilibrio general, etc. 1.1.

MODELOS DE OPTIMIZACION

Se distinguen diferentes modelos de optimización. La característica es la existencia de un único decisor. Si existe mas de un decisor se tiene la optimización multicriterio y la teoría de juegos.

1.2.

CLASIFICACION DE LOS MODELOS Los mas frecuentes son:

a) Según la naturaleza de los datos: - Modelos Deterministas.- Problemas donde se conocen con exactitud los datos que intervienen en el modelo - Modelos Estocásticos.- Problemas donde algunos o todos los datos dependen de fenómenos aleatorios b) Según la variable tiempo: - Modelos Estáticos.- La variable tiempo no se toma en consideración. Se tienen: Optimización o programación estática, Programación Clásica, Programación No Lineal, Programación Lineal y Teoría de Juegos. - Modelos Dinámicos .- Cuando se considera la variable tiempo de forma explícita en el modelo. Se tienen : Optimización o programación dinámica, El principio del máximo, Juegos diferenciales, etc. c) Según los objetivos del problema: - Modelos de un único objetivo - Modelos Multiobjetivos d) Según existan restricciones : - Modelos libres - Modelos con restricciones e) Según linealidad : - Modelos Lineales .- Todas las funciones que intervienen son lineales

1

Teor í aBási cadeOpt i mi z aci ón

Dpt o.Economí a-UNALM

2

- Modelos No Lineales.- Cuando al menos una de las funciones que interviene es no lineal. f) Según tipo de variables: - Modelos Continuos.- Todas las variables son contínuas - Modelos Discretos.- Al menos una de las variables unicamente puede tomar valores enteros.

II. PLANTEAMIENTO DEL MODELO El planteamiento general de un problema de programación matemática : * Optimizar Sujeta a

f (X1 , X2 , ...... , Xn) g 1 ((X1 , X2 , ...... , Xn) < b1 g 2 (X1 , X2 , ...... , Xn) < b2 ............................. g m (X1 , X2 , ...... , Xn) < bm

* Forma abreviada : Opt. f ( x ) s. a. g( x ) < b Donde :

f :R

n

g:R

n

xεR

R, m

R ,

n

bεR

,

m

f : Función objetivo. Es la función definida de un dominio de Rn sobre R Representa una descripción matemática y cuantificada del objetivo que se pretende alcanzar. x : Vector de variables instrumentales o variables de decisión De los valores posibles de las variables, se elige aquel o aquellos que proporcionen el valor óptimo de la función f. Conjunto de Oportunidades (S) : Llamado conjunto factible, es el conjunto de puntos X ε R n que cumplen todas y cada una de las restricciones y al mismo tiempo pertenecen al dominio de f. X = { xε R n / x ε S, g(x) < b } Cada vector de X se llama solución factible. Luego, el problema de programación matemática consiste en elegir aquel o aquellos valores de las variables instrumentales pertenecientes al conjunto S, es decir x ε S, que proporcionen el mayor o menor valor de la función objetivo (f).

2

Teor í aBási cadeOpt i mi z aci ón

Representación, en general :

3

Dpt o.Economí a-UNALM

Max f (x) s. a. g (x) < b

En forma análoga se establece el planteamiento de los problemas de minimización, ya que: Mín f (x) = - Max [ - f (x) ]

III. PROGRAMACION ESTATICA 3.1. CLASIFICACION DE LA OPTIMIZACION ESTATICA Se pueden clasificar de diversas formas, pero el mas comunmente utilizado es según el tipo de funciones que intervienen y según las condiciones sobre las variables. Se clasifican en: 3.1.1. Programación Clásica Todos aquellos problemas en los que independientemente de cual sea la función objetivo, las restricciones son todas igualdades y las variables pueden tomar cualquier valor real. Planteamiento : Max f (X 1 , X2 , ...... , Xn) s. a.

h 1 ((X1 , X2 , ...... , Xn) = b1 h 2 (X1 , X2 , ...... , Xn) = b2 ............................. h m (X1 , X2 , ...... , Xn) = bm - La función y las restricciones pueden ser de cualquier tipo - Si tanto la función como las restricciones fueran todas lineales, se tiene un problema de programación lineal. - Se debe cumplir m < n, osea número de restricciones < número de variables - Si m > n, el conjunto de oportunidades (S) podría estar formado por un único punto o ser el conjunto vacío y el problema de optimización carecería de significado. - Si m = 0, es el caso de programación clásica sin restricciones, cuyo planteamiento es : Max f (X 1, X2, ...., Xn)

3.1.2. Programación No Lineal Es el caso mas general de la programación matemática. La función puede ser de cualquier tipo y las restricciones pueden ser tanto igualdades como desigualdades. Planteamiento : Max f( X 1, X2, ... , Xn)

3

Teor í aBási cadeOpt i mi z aci ón

4

Dpt o.Economí a-UNALM

s.a. g 1 ((X 1 , X2 , ...... , Xn) < b1 g 2 (X1 , X2 , ...... , Xn) < b2 ............................. g m (X1 , X2 , ...... , Xn) < bm En este tipo de problemas, además se puede añadir restricciones sobre el signo de las variables. 3.1.3. Programación Lineal Aquellos modelos en que tanto la función objetivo como las restricciones son lineales, y las restricciones pueden ser igualdades o desigualdades. Planteamiento : Max Z (x) = C1 X1 + C2 X2 + .... + Cn Xn s.a.

a11 X1 + a12 X2 + ... a1n Xn < b1 a 21 X1 + a22 X2 + ... a2n Xn < b2 .............................................. a m1 X1 + am2 X2 + ...amn Xn < bm X 1, X2 ...., Xn > 0

Forma matricial :

Max Z = ct x s. a. A < x b x>0

Siendo c, x ε Rn ; b ε Rm ; A ε M m x n Observación : Tanto la programación clásica como la programación lineal son casos particulares de la programación No Lineal.

3.2.

DEFINICIONES PREVIAS

3.2.1. OPTIMO Sea la función Z = f(x, y), definida en un cierto intervalo S, S  R2. Se supone que la función Z: i) Es continua en todo su dominio ii) Posee 1a. y 2da. derivadas finitas.

4

Teor í aBási cadeOpt i mi z aci ón

Dpt o.Economí a-UNALM

5

Definición de Optimo libre : Se dice que f(X,Y) posee un óptimo libre (o extremo) en un punto Po(a,b)  S, si en dicho punto posee un máximo o mínimo. Definición de máximo : f alcanza un máximo en Po , si : f(Po)  f(p),  P  V(Po) V(Po) = Entorno cualquiera de Po. Definición de mínimo : Análogamente, se dice que f alcanza un mínimo en Po si : f(Po) < f(P),  P  V(Po) Clases de Optimo Los óptimos son locales o relativos cuando lo sean en el entorno de un punto Po y son globales o absolutos cuando lo sean con respecto a todo el dominio (el entorno de Po coincide con el dominio de f(P)) Gráficamente : Máx. Global

f(X) Máx. Relativo Mín Relativo Mínimo Global

X

Observaciónes : 

El máximo o mínimo relativo será ¨estricto ¨si se cumple la desigualdad estricta : Para máximo: f(Po) > f(P) Para mínimo: f(Po) < f(P)



Las técnicas clásicas de búsqueda de óptimos, usando diferenciabilidad, proporcionan solamente óptimos locales o relativos; en cambio el análisis de convexidad nos proporciona óptimos globales o absolutos.

3.2.2. CONJUNTOS CONVEXOS En la teoría de optimización, el concepto de convexidad es importante, ya que interesa que las funciones y conjuntos que intervienen en la programación matemática verifiquen un conjunto de propiedades respecto a la convexidad. Como se señaló en una observación anterior, es a través del análisis de convexidad que se analizan los óptimos globales, lo cual es una ventaja frente a las técnicas clásicas de búsqueda de óptimos según diferenciabilidad , que proporcionan solamente óptimos locales.

5

Teor í aBási cadeOpt i mi z aci ón

Dpt o.Economí a-UNALM

6

Definición : Un subconjunto S  Rn es un conjunto convexo si el segmento que une cualquier par de puntos de S está contenido en dicho conjunto. Es decir, el conjunto S es convexo cuando  x, y  S se verifica que :  x + (1- ) y  S,

0 ≤  ≤ 1.

siendo

Donde: x, y  Rn ,   R

Graficos :

S1

S2

S3

S1, S2 y S 3 son conjuntos convexos

S5 S6 S4 S 4, S5 y S6 no convexos. 3.2.3. CONDICIONES NECESARIAS Y SUFICIENTES En el análisis de optimización es frecuente usar los conceptos de “condición necesaria” y “condición suficiente”. i) Una condición necesaria es como un prerequisito. Supongamos que un enunciado p es verdadero sólo si otro enunciado q es verdadero; entonces q constituye una condición necesaria de p. Simbólicamente se representa : p  q. Por ejemplo: Si p es el enunciado : “una persona es un padre” y q es “una persona es varón”, entonces p  q. Osea el ser varón(q) es una condición necesaria para la paternidad(p). El recíproco no es cierto. ii) Una condición suficiente es una situación en la que un enunciado p es verdadero si q es verdadero, pero p también puede ser verdadero cuando q no es verdadero. Osea q es una condición suficiente para p, y se representa : p  q. Entonces la veracidad de q basta para establecer la veracidad de p. Por ejemplo: El enunciado de p, “Es día no laborable”, y de q es “Es 1º. De mayo”. Entonces p  q, puesto que un dia no laborable puede ser un domingo o cualquier otro dia feriado , el hecho de que sea 1º. de mayo(q) no es prerequisito para que sea dia no laborable(p). iii) Si la situación es que q es necesario y suficiente para p, entonces se representa como : p  q, osea “p si y sólo si q”.

6

Teor í aBási cadeOpt i mi z aci ón

Dpt o.Economí a-UNALM

7

Por ejemplo: Si p es el enunciado “una figura tiene 4 lados” y q establece “es un triangulo”. Se trata de una implicancia recíproca, un “si y sólo si”. iv) La metodología para resolver problemas de optimización consiste en usar, primero las condiciones necesarias(casi siempre condiciones de primer orden) y luego las condiciones suficientes (casi siempre condiciones de segundo orden). Una condición de primer orden nos permite encontrar los puntos estacionarios o críticos, que vienen a ser los “candidatos” a ser puntos máximos, mínimos o ninguno de ellos. Lo cual se verifica o se concluye según la condición de segundo orden. 3.2.4. FUNCIONES CONVEXAS Y CONCAVAS En la práctica se hace necesario buscar condiciones necesarias y suficientes para caracterizar a las funciones convexas en general, y a las funciones convexas diferenciables. Estas últimas se obtienen usando la condición de Primer Orden, con el gradiente de la función, o con la condición de Segundo orden con el Hessiano. Definición . Dado un conjunto convexo S de Rn, se dice que una función real f, definida f : S  Rn R, es convexa , si  x1,x2  S, y   [ 0,1 ], se verifica : f ( x1 + (1-) x2 )

≤  f(x1) + (1-) f(x2)

La función f será estrictamente convexa si  x1, x2  S, x1  x2 y   (0,1), se verifica : f ( x1 + (1-) x2 )   f(x1) + (1-) f(x2) Gráficamente :

X X

Función convexa

Función estrictamente

convexa Sea x punto cualquiera entre x1 y x2

f(X)

f(x2)

x = x1 + (1-) x2 fcualquier valor de f(x) entre f(x1) y f(x2) :

f f(x)

f=  f(x1) + (1-) f(x2)

f(x1)

Si cumple : f(x)  f , es estrictamente

x1

x

convexa.  x  x1,x2  x2 Si f(x) ≤ f , la función f es convexa

-

 x  x1,x2  7

Teor í aBási cadeOpt i mi z aci ón

Dpt o.Economí a-UNALM

8

Definición. Una función real f, definida en un conjunto S  Rn, es cóncava (estrictamente cóncava) si la función (-f) es convexa (estrictamente convexa). Siendo (-f) la función definida por (-f) (x) = - f(x)

Función concava

Función estrictamente cóncava

El estudio de la convexidad o concavidad de una función a través de las definiciones puede ser algo difícil porque implica el uso de desigualdades. Los dos primeros teoremas siguientes pueden ser mas prácticos para el análisis de convexidad o concavidad. 3.2.4. TEOREMAS Teorema .- Sea f una función de clase dos en un conjunto abierto y convexo S; (f  C2). Entonces f es convexa si y sólo si el Hessiano de f(x), en cualquier punto de S, corresponde a una forma cuadrática definida o semidefinida positiva. Si el Hessiano es definido positivo solamente, entonces f(x) es estrictamente convexa. Teorema .- Sea f una función de clase dos en un conjunto abierto y convexo S; (f  C2). La condición necesaria y suficiente para que f sea cóncava es que su hessiano tenga asociada una forma cuadrática definida o semidefinida negativa en S. Si el Hessiano es definido negativo solamente, entonces f(x) es estrictamente cóncavo. Observación : Las condiciones de estrictamente cóncavo y convexo, no son necesarios y suficientes. Ejemplos : 1) Sea f(X,Y) = 2X –Y – X 2 + 2XY – Y2. Analizar según teorema, si la función es ¿cóncava o convexa.? Formando el Hessiano :

f1 = 2- 2X +2Y , f 2 = -1 +2X – 2Y,

8

f11 = -2 , f22 = -2 ,

f12 = 2 f21 = 2

Teor í aBási cadeOpt i mi z aci ón

Luego : H =

-2 2

Dpt o.Economí a-UNALM

9

2 -2



H1 = -2 < 0 ;

H2  = 0

El signo de los menores principales o hessianos indican que la función es semidefinida negativa. Entonces la función será cóncava. 2) f(X,Y,Z) = X2 + Y –Z2 . La función es ¿cóncava o convexa.? f 1 = 2X , f2 = 1 , f3 = -2Z,

f 11 = 2, f22 = 0, f33 = -2

f12 = 0 , f23 = 0 ,

2 0 0 El hessiano es : H = 0 0 0 0 0 -2

f13 = 0

 H1 = 2 > 0; H2  = 0 y H3 = 0.

La forma cuadrática es indefinida, osea la función no es ni cóncava ni convexa ni aún del tipo estricto. En este caso puede existir punto silla S(según 4.2.2). Observe que cuando un menor principal es cero, la forma cuadrática no está definida y entonces o puede ser semidefinida o simplemente indefinida. En el caso de ser semidefinida positiva se asegura que no hay un máximo; y si es semidefinida negativa se asegura que no es un mínimo. El análisis de ser indefinida se vale algunas veces del uso de derivadas terceras, que es teoricamente posible, pero en la práctica resulta complejo, o también de un riguroso tratamiento del punto crítico en cuestión; a través de un estudio local o de vecindades del punto. (Guerrero, F., ob.cit. pg. 64) Puede ser práctico considerar indefinida, si mas de un menor principal es cero. 3) Estudiar la convexidad o concavidad de la función: f(X 1,X2) = 2X1X2 – 3X12 – 5X22 Calculando las derivadas parciales, según Hessiano: f1 = 2X2 – 6X1 , f 2 = 2X1 – 10X2, El hessiano es :

f11 = -6, f22 = -10, H =

f 12 = 2 f21 = 2

-6 2 2 -10



H1 = -6 < 0 ;

H2  = 56 > 0.

El signo de los menores principales o hessianos indican que se trata de una forma cuadrática definida negativa. Entonces la función será estrictamente cóncava. 4) En la función f(X,Y) = - 6X 2 + (2a + 4) XY – Y 2 + 4aY. Determine el valor de “a” para que la función sea cóncava. f1 = -12X + (2a + 4)Y ;

f 11 = -12 ;

f2 = (2a + 4)X – 2Y + 4a ;

f21 = (2a + 4) ;

9

f12 = (2a + 4) f 22 = -2

Teor í aBási cadeOpt i mi z aci ón

El Hessiano es :

10

H  =

-12 (2a + 4)

Dpt o.Economí a-UNALM

(2a + 4) -2

H1 = -12 < 0 . Nunca será convexa Para que la función sea cóncava(estrictamente cóncava), el H2 deberá ser mayor o igual que cero : H2  = 24 – (2a + 4) 2 > 0 -4a 2 –16a + 8 > 0 Se concluye que los valores de “a” son: a < -2 + 6 y a > -2 - 6 Teorema Local - Global Sea el problema general de programación matemática : Max f(x) s.a. x  X Si X es un conjunto convexo y f es una función cóncava en X, todo máximo local de f es un máximo global. Mín f(x) s.a. x  X Si X es un conjunto convexo y f es una función convexa en X, todo mínimo local de f es un mínimo global. Teorema de Weierstrass Si X es un subconjunto compacto (cerrado y acotado) de Rn y f una función real contínua en X, entonces f posee un máximo y un mínimo globales.

IV. OPTIMIZACION DE FUNCIONES SIN RESTRICCIONES (Programación Clásica sin restricciones) Se trata de hallar los valores de las variables x  Rn que maximizan o minimizan una función f : Rn R diferenciable. Max f(x) o Min f(x) 4.1. Condiciones Necesarias de Optimo Local 4.1.1. Condición Necesaria de 1er. Orden. : Si f : Rn R es una función de clase uno, la condición necesaria para que x* sea un óptimo local es que  f(x *) = 0 Si Z = f(x, y)

10

Teor í aBási cadeOpt i mi z aci ón

Z=

Dpt o.Economí a-UNALM

11

f/x

0 =

f/y

0

Los valores de x obtenidos en f(x*) son llamados puntos críticos o estacionarios. En la práctica, esta condición implica el desarrollo de ecuaciones con el fin de determinar los puntos críticos. Osea resolver :  f /  x = 0 f/y = 0 4.1.2. Condición Necesaria de 2do. Orden. Sea f  C2 (Rn) y x* un punto crítico de f en el cual la matriz hessiana no es la nula. Si x* es un máximo local ( mínimo local) de f, entonces la forma cuadrática asociada a Hf(x*) es semidefinida negativa (semidefinida positiva). Observar que Hf(x*) es el determinante hessiano H , correspondiente. La condición necesaria debe satisfacerse para que exista óptimo (o si existe óptimo forzosamente ha de verificarse). Su no cumplimiento demostraría la inexistencia del óptimo en ese punto, y su cumplimiento no garantiza la existencia de aquel, sino su posibilidad. 4.2. Condiciones Suficientes de Optimo Local 4.2.1. Sea f  C2 (Rn) y x* un punto crítico de f en el cual la matriz hessiana no es la nula. Si la matriz hessiana en x* corresponde a una forma cuadrática definida negativa (definida positiva), entonces x* es un máximo local estricto (mínimo local estricto) 4.2.2. Sea f  C2 (Rn) y x* un punto crítico de f en el cual la matriz hessiana no es la nula. Si la matriz hessiana en x* corresponde a una forma indefinida, entonces x* es un punto de silla. Ejemplo : Sea la función, f( X,Y ) = X 2 – Y2 1º) Según la condición de 1er. Orden, encontramos el punto crítico al resolver : f 1 = 2X = 0  f 2 = -2Y = 0 

X=0 Y=0

El punto crítico es (0,0) 2º) Según la condición de 2do. Orden, formamos el hessiano con las derivadas parciales faltantes y analizamos el punto (0,0) : Las derivadas parciales faltantes son :

11

f11 = 2 ; f 21 = 0 ;

f 12 = 0 f 22 = -2

Teor í aBási cadeOpt i mi z aci ón

Dpt o.Economí a-UNALM

12

El Hessiano es : H =

2 0

0 -2

H1 = 2 > 0, H2 = -4 < 0 Según los signos obtenidos, pareciera que se tratase de una forma definida; pero no es así. Sería definida negativa si los signos de los menores principales empezara con menor y luego mayor. Por lo tanto el punto crítico (0,0) es un punto silla. Se trata de una forma indefinida (según 4.2.2). 4.3. Condiciones Suficientes de Optimo Global 4.3.1. Si f  C1(Rn) es una función cóncava y x* un punto crítico suyo, entonces x* es un máximo global o absoluto de f. Si f es estrictament...