Optimizacion

Problemas de optimización

Los metodos para hallar valores extremos que hemos aprendido tienen aplicaciones practicas en muchas areas de nuestra vida. Una persona de negocios quiere minimizar los costos y maximizar las utilidaddes. El principio de Fermat, en optica, afirma que la luz sigue la trayectoria que recorre en el menor tiempo. Lo que en algunos casos se conoce como la linea recta. En esta sección trataremos de resolver problemas como lo de maximizar áreas, volúmenes y utilidades, minimizar distancias, tiempos y costos.

En la solucion de problemas practicos, el desafio mas grande suele ser convertir el problema en palabras en una problema matematico de optimazion, establecer la funcion que debe maximizarse o minimizarse. Reucerdo los principios de soluciòn de problemas.

#Comprenda el problema.

#Analogía : Intente casos especiales.

#Dibuje Diagramas.

Max/Min Función Objetivo

Sujeto a,

Restricción

Clasificación de Problemas de Optimización

• Optimización continua:

El espacio de búsqueda corresponde a ¬n

• Optimización discreta (combinatoria):

El espacio de búsqueda corresponde a un conjunto finito o posiblemente contable infinito.

Ejemplo: enteros, conjuntos, permutación,grafo, etc.

Optimización Continua

• No restringida:

– Una variable

– Varias variables

• Restringida:

– Programación lineal

– Programación no lineal

– Programación cuadrática

– Programación convexa

Optimización discreta

• Programación entera

• Optimización en grafos:

– Minimal spanning tree

– Camino más corto

– Problema del agente viajero

– Matching

– Flujo máximo

• Programación dinámica

• Scheduling

Función convexa

Función convexa en un intervalo [x,y].

En matemática, una función real f definida en un intervalo (o en cualquier subconjunto convexo de algún espacio vectorial) se llama función convexa o cóncava hacia arriba, si está definida sobre un conjunto convexo y para cualesquiera dos puntos cualquiera x e y de su dominio es su dominio C y cualquier t en [0,1], se cumple

En otras palabras, una función es convexa sí y sólo si su epigrafo (el conjunto de puntos situados en o sobre el grafo) es un conjunto convexo.

Una función estrictamente convexa es aquella en que

para cualquier t en (0,1) y

Una función es cóncava si la función es convexa.

Definición concava

Formalmente, una función real f definida en un intervalo (o en cualquier conjunto convexo C de algún espacio vectorial) se dice que es cóncava, si para dos puntos x e y cualesquiera definidas en su dominio C, y para cualquier t en [0,1], se cumple

Además, f(x) es cóncavo en [a, b] si y sólo si la función −f(x) es convexa en [a, b].

Una función que es cóncava es a menudo también llamada cóncava hacia abajo, mientras que una función convexa es llamada cóncava hacia arriba.

Una función es estrictamente cóncava si

para cualquier t en (0,1) y x ≠ y.

Una función continua en C es cóncava si y sólo si

.

para cualquier x e y en C.

Una función diferenciable f es cóncava en un intervalo si su derivada f ′ es monótonamente decreciente en ese intervalo: una función cóncava posee una pendiente negativa o decreciente. (entendiendo por "decreciente" aquí a que es "no-creciente", en lugar de "estrictamente decreciente"; es decir, se permite la pendiente cero).

...