380531571-funcion-objetivo.pptx

r

1. Instituto tecnológico de Tuxtla Gutiérrez Ingeniería bioquímica I ngeniería de procesos B8a Santiz Gómez José Alfredo equipo # 5 García Marroquín Roberto Carrascosa Molina Mónica Guadalupe. Rodríguez Galdámez Rodrigo del Carmen Martínez Silvestre Karina Elizabeth TUXTLA GUTIERREZ, CHIAPAS. MAYO 2018

2. 4.1.3 función objetivo

3. La función objetivo es la ecuación que será optimizada dadas las limitaciones o restricciones determinadas y con variables que necesitan ser minimizadas o maximizadas usando técnicas de programación lineal o no lineal . Una función objetivo puede ser el resultado de un intento de expresar un objetivo de negocio en términos matemáticos para su uso en el análisis de toma de decisiones, operaciones, estudios de investigación o de optimización.

4. Formulación de un modelo de programación lineal Determinación de las variables de decisión Representan los elementos del sistema decisión . sistema a modelar que son controlables por el decisor. En los modelos lineales continuos estas variables toman como valores números reales y se representan por letras con subíndices como se acostumbra a hacer con las variables matemáticas, o literales alusivos a su significado : peso , valor, etc. En el primer caso también se utiliza la representación como vector de un conjunto indexado de variable :  

5. Determinación de las restricciones . Representan las limitaciones prácticas de determinados recursos o imposiciones físicas de la realidad. Se expresan como ecuaciones e inecuaciones lineales de las variables de decisión . Formulación de la función objetivo . Se trata de la función que mide la calidad de la solución y que hay que optimizar (maximizar un beneficio o minimizar un coste) También es una función lineal de todas o parte de las variables de decisión.  

6. EJEMPLO

7. Problema 1: asignación de recursos En una fábrica de cerveza se producen tres tipos distintos: rubia, negra y de baja graduación, y para ello se utilizan dos materias primas : malta y levadura. En la siguiente tabla se especifican: a ) la cantidad de materias primas consumidas para producir una unidad de cada tipo de cerveza; b) las cantidades disponibles de cada materia prima; y c) el precio unitario de venta de cada tipo de cerveza. Se trata de conocer la cantidad a fabricar de cada tipo de cerveza de manera que el beneficio sea máximo.

8. SOLUCIÓN Variables de decisión Del enunciado del problema se desprende que las variables de decisión son las producciones a fabricar de cada tipo de cerveza : = producción de cerveza rubia = producción de cerveza negra = producción de cerveza de baja graduación   Restricciones Las restricciones en este caso imponen que las materias primas utilizadas en la fabricación de los tres tipos de cerveza no deben sobrepasar las cantidades disponibles :  

9. Función objetivo En este caso el objetivo es maximizar el beneficio, que viene dado por la suma de los precios de venta de la producción :   El modelo matemático de programación lineal para el problema de asignación de recursos queda formulado de la siguiente manera:

10. Nos vamos a ocupar de modelar problemas de programación lineal y resolver los modelos utilizando los lenguajes de modelado disponibles comercialmente. L a expresión del problema se realiza en dos modernos lenguajes de modelado (OPL y OML) sería la siguiente:

11. Es evidente que estos lenguajes disponen de una sintaxis muy próxima a la pura expresión matemática El texto en verde corresponde matemática . a comentarios, y el azul a palabras reservadas de cada lenguaje. La solución que nos dan los respectivos sistemas son la siguientes :

12. ¿QUE ES LA OPTIMIZACIÓN? La optimización es el proceso de hallar el máximo o mínimo relativo de una función generalmente sin ayuda de gráficos. Un problema de optimización consiste en minimizar o maximizar el valor de una variable. En otras palabras se trata de calcular o determinar el valor mínimo o el máximo de una o varias variables.

13. ¿ que es la optimización sin restricciones? Es el problema de minimizar una función sin la existencia de restricciones, esta función puede ser de una o de mas variables. La no presencia de las restricciones puede ser vista en un comienzo como una grave limitación , sin embargo, existe una metodología que permite tratar problemas de optimización no lineales con restricciones como problema de optimización no lineales sin restricciones.

14. Optimización sin restricciones En optimización sin restricciones se minimiza una función objetivo que depende de variables reales sin restricciones sobre los valores de esas variables. La formulación matemática es: donde f es una función suficientemente regular.

15. Ejemplo Se intenta encontrar una curva que ajuste algunos datos experimentales, por ejemplo medidas y1,..., ym de una señal tomadas en los tiempos t1,..., tm . Desde los datos y el conocimiento de la aplicación, se deduce que la se ñ al tiene un comportamiento exponencial y oscilatorio, y se elige modelarlo por la funcion : Φ(t, x) = x1 + x2e−(x3−t)2/x4 + x5 cos (x6t)

16. Los números reales xi, i = 1,..., 6 son los parámetros del modelo. Se desea seleccionarlos de manera que los valores del modelo Φ( tj , x) ajusten los datos observados yj tanto como sea posible. Para establecer el objetivo como un problema de optimización, se agrupan los parámetros xi en un vector de incógnitas (x1,...,x6)t y se definen los residuos rj (x) = yj − Φ( tj , x), j = 1,...,m que miden la discrepancia entre el modelo y los datos observados

17. La estimación de x se obtendrá resolviendo el problema: Este es un problema de mínimos cuadrados no lineales, que es un caso especial de optimización sin restricciones. Si el numero de medidas es grande (por ejemplo 105), la evaluación de f o sus derivadas para un valor concreto del vector de parámetros x es bastante caro desde el punto de vista computacional.

18. Que es un mínimo y su importancia. Mínimos de una Función.   En un punto en el que la derivada se anule y antes sea negativa y después del punto positiva, se dice que la función tiene un mínimo relativo. Es decir, que F'( x o ) = 0 y en ese punto, la función, pase de decreciente a creciente. En x =  b  la función tiene un mínimo relativo y se observa que su derivada se anula en ese punto, pasando de negativa a positiva. Mín en ( b ,f ( b ).   Para que una función tenga máximo o mínimo no es suficiente con que su derivada se anule (debe, además, cambiar de signo ). La importancia de conocer un mínimo es poder determinar la condición inferior de una función o de un proceso en si.

19. Caracterización de un mínimo ¿Que es una solución? Un punto x∗ es un MINIMO GLOBAL si f(x∗) ≤ f(x) para todo x ∈ Rn. Sin embargo el mínimo global puede ser difícil de encontrar pues nuestro conocimiento de f es usualmente local. La mayoría de los algoritmos calculan mínimos locales que son puntos en los que sea alcanza el menor valor de f en su entorno. Formalmente: Un punto x∗ es un MINIMO LOCAL si existe un entorno N de x∗ tal que f(x∗) ≤ f(x) para todo x ∈ N. Hay funciones con muchos mínimos locales. Es generalmente difícil encontrar el mínimo global para tales funciones. Un ejemplo con millones de mínimos locales aparece en la determinación de la conformación de una molécula con energía potencial mínima.

20. ¿Como reconocer un mínimo local? Si la función f es suficientemente regular existen modos eficientes y prácticos de identificar mínimos locales. En particular si f es dos veces diferenciable puede decirse si x∗ es un mínimo local examinando su gradiente ∇f(x∗) y su hessiano ∇2f(x∗). En concreto: • CONDICION NECESARIA DE PRIMER ORDEN: Si x∗ es un mínimo local y f es continuamente diferenciable en un entorno abierto de x∗, entonces ∇f(x∗)=0. (x∗ punto estacionario) • CONDICIONES NECESARIAS DE SEGUNDO ORDEN: Si x∗ es un mínimo local y ∇2f es continua en un entorno abierto de x∗, entonces ∇f(x∗)=0 y ∇2f(x∗) es semidefinida positiva. • CONDICIONES SUFICIENTES DE SEGUNDO ORDEN: Si ∇2f es continua en un entorno abierto de x∗, ∇f(x∗)=0 y ∇2f(x∗) es definida positiva, entonces x∗ es un mínimo local estricto de f.

21. Las condiciones suficientes no son necesarias. Un ejemplo simple esta dado por la función f(x) = x4 para la que el punto x∗ = 0 es un mínimo local estricto y sin embargo su hessiano es nulo (y por tanto no definido positivo). Cuando la función objetivo es convexa, los mínimos locales y globales son fáciles de caracterizar: Cuando f es convexa, cualquier mínimo local x∗ es un mínimo global de f. Si además f es diferenciable, entonces cualquier punto estacionario x∗ es un mínimo global de f.

22. Problemas no regulares Existen muchos problemas interesantes en los que las funciones involucradas pueden ser no diferenciables e incluso discontinuas. • Si la función está formada por unos pocos trozos regulares con discontinuidades entre los trozos, puede ser posible encontrar el mínimo analizando cada trozo por separado. • Si la función es continua en todo punto pero es no diferenciable en ciertos puntos, puede identificarse la solución analizando los subgradientes, o los gradientes generalizados que son una generalización del concepto de gradiente al caso no regular.

23. Una visión de conjunto de los algoritmos • Se considera solo el caso regular. • Todos los algoritmos para minimización sin restricciones necesitan que el usuario suministre un punto inicial, que se denotara por x0. • Comenzando en x0, los algoritmos de optimización generan una sucesión { xk } que terminan cuando el algoritmo no puede progresar más o cuando parece que un punto solución se ha aproximado con precisión suficiente. • Para decidir como pasar de un iterante xk al siguiente los algoritmos utilizan información sobre f y sus derivadas en el iterante xk o incluso de todos los i terantes anteriores x0, x1,...,xk−1, xk . Existen dos estrategias fundamentales para pasar de un iterante a otro. La mayoría de los algoritmos siguen alguna de estas estrategias.

24. Dos estrategias: Búsqueda de línea y Región de confianza • Búsqueda de línea: – el algoritmo elige una dirección dk – busca a lo largo de esa dirección desde el iterante actual a un nuevo iterante con un menor valor de la función objetivo – la distancia que debe moverse el iterante puede encontrarse resolviendo de manera aproximada el siguiente problema de minimización unidimensional que consiste en encontrar un paso t tal que: (Resolviendo exactamente este problema se obtendría el mayor beneficio, pero hacerlo es caro e innecesario pues el objetivo final es la optimización de f y no la de f( xk + tdk ).) – en cada nuevo punto se calcula una nueva dirección de búsqueda y un nuevo paso y se repite el proceso.

25. Región de confianza: – se construye una función modelo mk (x) cuyo comportamiento cerca del iterante actual xk es similar al de la función objetivo f. – como el modelo mk puede no ser una buena aproximación de f cuando x está lejos de xk , restringimos la búsqueda de un optimo de mk en alguna región en torno a xk . Es decir encontramos el candidato dk resolviendo de manera aproximada el siguiente subproblema: – Si la solución candidata no produce un decrecimiento suficiente en f se concluye que la región de confianza es demasiado grande y debe reducirse para después resolver el nuevo subproblema asociado.

26. Una buena técnica de optimización de funciones de una única variable es fundamental por al menos tres razones: 1 .- En muchos problemas las restricciones se pueden incluir dentro de la función objetivo, por lo que la dimensionalidad del problema se reduce a una variable. 2 .- Algunos problemas sin restricciones, inherentemente incluyen una única variable. 3 .- Las técnicas de optimización con y sin restricciones, generalmente incluyen pasos de búsqueda unidireccional en sus algoritmos . Antes de la aparición de los ordenadores de alta velocidad, los métodos de optimización estaban prácticamente limitados a los métodos indirectos en los cuales el cálculo estaba restringido al uso de derivadas y la condiciones necesaria de optimalidad . Los modernos ordenadores han hecho posible los métodos directos, esto es la búsqueda de un óptimo por comparación sucesiva de los valores de la función f(x) en una secuencia de puntos x1, x2, x3... sin la necesidad de hacer intervenir derivadas analíticas. 4.2.1 Métodos numéricos para la optimización de funciones

27. Han sido desarrollados, básicamente tres métodos para llevar a cabo la búsqueda directa unidireccional, basados en las condiciones de optimalidad . Estos son: 1 .- Método de Newton 2 .- Aproximaciones finitas al método de Newton (Métodos cuasi-Newton) 3 .- Métodos de secante.

28. Método de Newton. El objetivo de este método para estimar la solución de una ecuación f(x)=0, es producir una sucesión de aproximaciones que se acerquen a la solución. Escogemos el primer número X0 de la secuencia y luego en circunstancias favorables el método hace el resto moviéndose paso a paso a la raíz. Al tener un comportamiento grafico de la función y = f(x), hay que proponer una primera solución. Use la primer aproximación para obtener la segunda y asi sucesivamente hasta encontrar la raíz. Mediante la formula.  

29. Proponer un punto de evaluación. Calcular el gradiente (ecuación objetivo) Calcular el hessiano y la inversa. Multiplicar el gradiente por la hessiana inversa. Restar el punto propuesto al punto obtenido.

30. Método de newton en diferencias finitas. Los métodos en diferencias finitas tipo Newton, se utilizan si la derivada de la función objetivo es difícil de calcular, o ésta viene dada de forma numérica. Se basan en sustituir las derivadas por aproximaciones en diferencias finitas . En este método es necesario tener las f’’(x) o el hessiano como aproximación.

31. Métodos de secante Los métodos de secante toman dos puntos, x p y x q y resuelve una ecuación similar a la dada en el método de Newton: donde m es la pendiente de la línea que conecta x p y x q . dada por: El método de la secante aproxima la segunda derivada por una línea recta. Cuando xq→x p el valor de m se aproximará al valor de la segunda derivada. En este sentido el método de la secante se podría considerar también un método cuasi Newton. El método de la secante parece bastante “crudo” pero funciona bastante bien en la práctica.  

32. 4.3 OPTIMIZACION DE FUNCIONES MULTIVARIABLES Optimización Disponibilidad de ordenadores Desarrollo y mejoría de los modelos económicos Desarrollo del software

33. Los métodos pueden ser clasificados en tres categorías, basándonos en la información que debe ser suministrada por el usuario: Métodos de búsqueda directa: los cuales utilizan solo valores de la función objetivo. Métodos de gradiente: aquellos que requieren valores exactos de la primera derivada de la función objetivo. Métodos de segundo orden: utilizan la segunda derivada de la función objetivo. MÉTODOS DE OPTIMIZACION

34. Para la aplicación de estos métodos solamente es necesario conocer el valor de la función objetivo en cualquier punto del espacio y no necesitamos ninguna hipótesis adicional acerca de la diferenciabilidad de la función. Podemos emplear estos métodos, bien cuando el gradiente de la función, ∇f (x), no exista, no sea conocido o simplemente porque su expresión es demasiado compleja para poder manejarlo con eficacia. MÉTODOS DE BÚSQUEDA DIRECTA

35. MÉTODOS INDIRECTOS Los métodos indirectos hacen uso de derivadas en la determinación de las direcciones de búsqueda. Una buena dirección de búsqueda debería reducir la función objetivo, entonces si x0 es el punto inicial y x1 es el nuevo punto: f(x1)<f(x0).