Optimizacion

Optimización

Julian Castro Espinel 20162578016, Juan Sebastián Rivera 20162578127

Resumen: El presente abarcara el tema acerca de los métodos de optimización más conocidos actualmente. En principio se tratara la optimización no restringida y el método más conocido respecto a esta, el cual es el método de búsqueda de sección dorada; este método es de tipo unimodal y su función es hallar el extremo máximo o mínimo de una función. Posteriormente se tratara la optimización restringida la cual está relacionada con la programación lineal y a su vez con el método conocido como Simplex y Dual; este es utilizado para optimizar funciones que estén sujetas a una serie de restricciones.

Palabras clave—Optimización, optimización no restringida, búsqueda de sección dorada, optimización restringida, programación lineal, simplex y dual, método, función.

I. INTRODUCCION

La optimización puede definirse como aquella ciencia encargada de determinar las mejores soluciones a problemas matemáticos que a menudo tratan un caso o aspecto de la vida real. Los problemas que incumben o requieren de optimización se  pueden encontrar principalmente en campos de ingeniería, economía, geofísica y prácticamente en todos los campos de las ciencias exactas e inexactas.

Los métodos de búsqueda dorada y de programación lineal (Simplex y Dual) son métodos que surgen a partir de la optimización en la matemática; por medio de estos se pueden resolver casos o  situaciones de la vida real en las cuales se busca identificar y resolver dificultades con el fin de aumentar la productividad en diferentes campos aumentando así los beneficios de distintas actividades.

Su objetivo principal es optimizar, al maximizar o minimizar funciones lineales; puede ser con una o con diferentes variables lineales. Dependiendo del método se presentan ciertas restricciones lineales, optimizando una función objetiva también lineal. Los resultados de dicho algoritmo se convierten en un respaldo cuantitativo (numérico) de las decisiones frente a las distintas situaciones planteadas.

1. HISTORIA

A. Búsqueda de sección dorada

Este método toma su nombre debido a que su algoritmo mantiene los valores de dicha función en grupos de tres puntos de los cuales las distancias forman una proporción dorada. Tanto esta búsqueda como la búsqueda de Fibonacci fueron introducidas por Jack Kiefer en 1953 gracias a sus estudios en el diseño y optimización de experimentos en el campo de la geofísica.

B. Programación lineal

El concepto de programación lineal ha sido complementado por diferentes actores a lo largo de la historia.

En 1826 Joseph Fourier anticipo la programación lineal gracias a la creación de su método Fourier-Motzkin el cual se creó con el fin de solucionar sistemas de inecuaciones. Luego este término se amplió con el inicio de la segunda guerra mundial; pues este se utilizó para planificar los gastos e ingresos destinados y provenientes de la guerra, con el fin de reducir los costos al ejército y aumentar las pérdidas del enemigo.

Este concepto se mantuvo oculto hasta la época de la posguerra en 1947 en la cual muchas de las nuevas industrias lo utilizaron para su planificación. Posteriormente, George Dantzig desarrollo el algoritmo simplex basándose en la optimización utilizada en la programación lineal; y a su vez, John Von Neumann desarrollo la teoría de la dualidad la cual se terminaría utilizando en conjunto con el algoritmo Simplex.

A partir de la creación del método simplex muchos matemáticos o afines han contribuido al crecimiento de la programación lineal; su aporte se ha visto reflejado en el desarrollo sus teorías matemáticas, el diseño de códigos computacionales y en la creación de nuevas aplicaciones. La programación lineal también ha sido utilizada para resolver:  

• programas enteros,  
• programas discretos,  
• programas no lineales,  
• problemas combinatorios,  
• problemas de programación estocástica  
• problemas de control óptimo

1. DEMOSTRACION

A. Búsqueda de sección dorada

La búsqueda de sección dorada es una técnica o método de búsqueda para una sola variable, es por ello que es un método unimodal. Este es muy similar al método de bisección, utilizado para hallar raíces.

En este método se busca aproximar hacia un punto medio; para ello se utilizan tres puntos iniciales. Los dos primeros se conciben como los extremos del intervalo y el tercero será punto entre los otros dos. Posteriormente, lo que se busca es hallar un extremo ya sea el máximo o el mínimo de una función unimodal. Para ello se realizan reducciones sucesivas entre los dos extremos que son los dos puntos en los que se sabe que se encuentra el extremo.

La ventaja de utilizar este método es que no se deben recalcular todos los valores de la función en la siguiente iteración, puesto que estos se han escogido mediante razón aurea.  

La clave para hacer que este método sea muy eficiente es optar por una buena o la mejor elección de los puntos intermedios. Esto se puede lograr si se satisfacen las siguientes condiciones.

                           [pic 1] 

Se especifica que la suma de las sublongitudes debe ser igual a la longitud original y que el cociente entre dichas longitudes debe ser igual. Reemplazando 𝑙0 por la sumatoria de las sublongitudes se obtiene la siguiente ecuación.

                      [pic 2] 

Y utilizando el recíproco y 𝑅 = 𝑙2/𝑙1 se obtiene

                       [pic 3] 

Al realizar el despeje de R se llega a la raíz positiva

      [pic 4] 

La cual da un valor de 0.61803 el cual se conoce como la razón dorada o aurea. Este es el elemento clave del método.

Para comenzar a trabajar este método se utilizan las siguientes formulas:

                    [pic 5] 

Donde 𝑥𝑢 y 𝑥𝑙 son los dos valores iniciales que contienen cada extremo de la función y 𝑥1 𝑥2 son los dos puntos intermedios.

...