Apunte_de_Problemas Chile.pdf

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
 8
 
  Universidad de Chile Departamento de Ingeniería Matemática Problemas de Optimización para Estudiantes de Ingeniería Capítulo 1: Matemáticas para la Optimización Capítulo 2: Condiciones de Optimalidad Capítulo 3: Programación Lineal Capítulo 4: Dualidad en Programación Lineal Capítulo 5: Modelos y Algoritmos de flujos en redes Autores: Jorge A MAYA A. Cristopher H ERMOSILLA J.
Related documents
Share
Transcript
  Universidad de ChileDepartamento de Ingeniería Matemática Problemas de Optimización para Estudiantes deIngeniería Capítulo 1: Matemáticas para la OptimizaciónCapítulo 2: Condiciones de OptimalidadCapítulo 3: Programación LinealCapítulo 4: Dualidad en Programación LinealCapítulo 5: Modelos y Algoritmos de flujos en redes  Autores: Jorge A MAYA  A.Cristopher H ERMOSILLA  J.Nicolás H ERNÁNDEZ  S.14 de junio de 2009  Índice general 1. Matemáticas para la Optimización 2 1.1. Conjuntos Convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2. Funciones Convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2. Caracterización de Optimalidad 16 2.1. Optimización con Restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3. Programación Lineal 23 3.1. Algoritmo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4. Dualidad en Programación Lineal 32 4.1. Dualidad y Análisis de Sensibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5. Modelos y alg. para flujos en redes 42 5.1. Problemas de transporte y de flujo a costo mínimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 1  Capítulo 1 Matemáticas para la Optimización 1.1. Conjuntos Convexos 1.1.1. Problemas Resueltos P1.  Considere la norma euclideana en las siguientes definiciones:Dados  v ∈ R 3 \{ 0 } y  ε  >  0, se llama  Cono de Bishop-Phelps  al conjunto  K  ( v , ε )  definido por: K  ( v , ε ) = {  x ∈ R 3 :  ε  v   x ≤ v ,  x }  (1.1.1)Dados  a , b ∈ R 2 y  γ  ∈ [ 0 , 1 ] , se llama  Pétalo de Penot  al conjunto  P γ  ( a , b )  definido por: P γ  ( a , b ) = {  x ∈ R 2 :  γ   a −  x  +   x − b ≤ b − a }  (1.1.2)Dados C  ⊆ R 2 y  x 0  ∈ R 2 , se llama  Gota de Danes  al conjunto  [ C  ,  x 0 ]  definido por: [ C  ,  x 0 ] = Co ( {  x 0 }∪ C  )  (1.1.3) a ) Pruebe que  K  ( v , ε )  es convexo para cualquier  v ∈ R 3 \{ 0 } y  ε  >  0 b ) Pruebe que  P γ  ( a , b )  es convexo para cualquier  a , b ∈ R 2 y  γ  ∈ [ 0 , 1 ] c ) Pruebe que  [ C  ,  x 0 ] = {  x 0  + t  ( c −  x 0 )  :  t   ∈ [ 0 , 1 ] , c ∈ C  }∀ C  ⊆ R 2 convexo y  x 0  ∈ R 2 d  ) Pruebe que dados  a , b ∈ R 2 y  γ  ∈ ( 0 , 1 )  entonces  B ( b , r  ) ⊆ P γ  ( a , b ) , donde r   =  a − b  1 − γ  1 + γ  . Concluya que  [ c ,  B ( b , r  )] ⊆ P γ  ( a , b ) ∀ c ∈ P γ  ( a , b ) Solución: a ) Sean  v ∈ R 3 \{ 0 } y  ε  >  0 fijos, consideremos  x ,  y ∈ K  ( v , ε )  y  t   ∈ [ 0 , 1 ] .Sea  z  = tx +( 1 − t  )  y , veamos que  z ∈ K  ( v , ε ) : ε  v   z  =  ε  v  tx +( 1 − t  )  y ≤ t  ε  v   x  +( 1 − t  ) ε  v   y   ( propiedades de normas ) ≤ t   v ,  x  +( 1 − t  )  v ,  x   (  x ,  y ∈ K  ( v , ε ))=  v ,  x  Luego  z ∈ K  ( v , ε ) , y como  x ,  y , t   son arbitrario se concluye que  K  ( v , ε )  es convexo.2  b ) Sean  a , b ∈ R 2 y  γ  ∈ [ 0 , 1 ]  fijos, consideremos  x ,  y ∈ P γ  ( a , b )  y  t   ∈ [ 0 , 1 ] .Sea  z  = tx +( 1 − t  )  y , veamos que  z ∈ P γ  ( a , b ) : γ   a −  z  +   z − b  =  γ   a − tx − ( 1 − t  )  y  +  tx +( 1 − t  )  y − b  =  γ   ta +( 1 − t  ) a − tx − ( 1 − t  )  y  +  tx +( 1 − t  )  y − tb − ( 1 − t  ) b  =  γ   t  ( a −  x )+( 1 − t  )( a −  y )  +  t  (  x − b )+( 1 − t  )(  y − b ) ≤ t  γ   a −  x  +( 1 − t  ) γ   a −  y  + t    x − b  +( 1 − t  )   y − b  = t  [ γ   a −  x  +   x − b  ]+( 1 − t  )[ γ   a −  y  +   y − b  ] ≤ t   b − a  +( 1 − t  )  b − a  =  b − a  Luego  z ∈ P γ  ( a , b ) , y como  x ,  y , t   son arbitrario se concluye que  P γ  ( a , b )  es convexo. c ) Esto es directo de la definición de Co ( {  x 0 }∪ C  ) d  ) Sean  a , b ∈ R 2 ,  γ  ∈ ( 0 , 1 )  y  r   como en el enunciado. Sea  x ∈  B ( b , r  ) , luego:   x − b ≤ a − b  1 − γ  1 + γ  ⇒ a − b ≥  x − b  + γ    x − b  + γ   a − b ≥  x − b  + γ    x − a  Luego  B ( b , r  ) ⊆ P γ  ( a , b ) . Más aún como  P γ  ( a , b )  es convexo y contiene a  B ( b , r  )  se concluyeque [ c ,  B ( b , r  )] ⊆ P γ  ( a , b )  ∀ c ∈ P γ  ( a , b ) P2.  Demuestre que la proyección en  R n , de un punto    a , sobre la bola cerrada  B (   c , 1 )  (suponiendo que   a  / ∈  B (   c , 1 ) ), está dada por    p (   a ) =   c +    a −   c    a −   c  Solución: Como  B (   c , 1 )  es un convexo cerrado no vacío entonces la proyección de    a  sobre la bola es única,bastará entonces ver que     p (   a ) =   c +    a −   c    a −   c   minimiza la distancia de   a  a la bola. d  (    p (   a ) ,  a ) =     p (   a ) −   a  =    c +    a −   c    a −   c −   a  =  (   c −   a )  1 −  1    a −   c    =    c −   a   1 −  1    a −   c   =    a −   c − 1por otro lado claramente     p (   a ) ∈  B (   c , 1 ) , pues  d  (    p (   a ) ,  c ) =  1.3
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks