Resumen paper Optimización

De Departamento de Informatica
Saltar a: navegación, buscar

Contenido

¿Para qué optimizar?

La optimización se puede utilizar para extraer información detallada de un sistema para producir nuevas oportunidades de negocio. Puede afinar operaciones para crear nuevas mejoras en la eficiencia del proceso. Los sistemas basados en herramientas de optimizacion pueden promover la flexibilidad para que los sistemas sigan siendo eficientes en muchos escenarios. La existencia de procesos repetitivos en muchas operaciones, en un solo proceso, puede conducir a una mejora sustancial para el funcionamiento global. Cuando la magnitud de la operacion es grande la ganancia total puede ser muy grande. Los sistemas que se adaptan rapidamente a los cambios en un proceso son de mayor valor que aquellos que no lo hacen.

¿Cuando optimizar?

Cuando el conjunto de alternativas es muy grande la optimizacion selecciona la mejor. Hay situaciones en empresas para que la optimizacion no es apropiada. Cada vez que hay mecanismos mas simples, se den aplicar primero, sin embargo muchos de los problemas aparentemente simples son enormemente complejos.

La optimizacion se debe utilizar cuando no hay una solución fácil y directa.

Esto suele ocurrir cuando la estructura del problema es complejo y hay millones de posibles soluciones. En tales casos, puede haber un enfoque eficiente, solución directa, por lo que las técnicas de optimizacion pueden buscar la mejor solución. En otro casos, cuando no se puede encontrar la solución el problema esta relajado ( algunas restricciones sobre alternativas se relajan) y la optimizacion se utiliza para encontrar la mejor solución para el problema relajado. La solución relajada puede servir de base para resolver con precision el problema original.

¿Qué metodos utiliza la Optimización?

Existen numerosos modelos de optimizacion. El enfoque depende del problema. Sistemas basados en reglas son comunmente utilizadas para aplicaciones de control y reglas predeterminadas para generar soluciones. y modeladas por programación lineal y/o programación lineal entera

Optimización

La optimización es el proceso de encontrar la mejor solucion a partir de un conjunto de soluciones

Se divide en 2 clases: globales y locales:

  1. Optimizacion Global = Se encuentra la mejor solucion desde el conjunto de todas las soluciones. Siempre encontrará la misma solución sin importar el punto de inicio, pero por lo general se requieren más potencia computacional. En algunas aplicaciones es imposible de encontrar. De hecho encontrar el optimo global puede no ser necesario.
  2. Optimización Local = Se encuentra la mejor solucion de un conjunto de soluciones que se acercan el uno al otro. La solución encontrada depende del punto de partida para la optimización. Encontrar una buena solucion de forma rápida puede ser mas deseable que encontrar la mejor solucione lentamente.

El tipo de optimizacion depende de la estructura del problema. Si todas las variables de decision son reales y la F.O y las restriccciones son funciones lineales, la programacion lineal generalmente es el mejor enfoque.

Programacion lineal--> formula simplista.

La capacidad de los enfoques para manejar dichas complicaciones es el principal factor a considerar al momento de decidir entre los enfoques.

Formulación del problema

Es clave para optimizar:

  • Variables de decision.
  • Funcion objetivo.
  • Funciones de restricción.

la estrucutra de estas variables y funciones determina el mejor enfoque para resolver.

  • Variables de decision: usadas para representar decisiones que necesitan ser tomadas. La decision es representada por variables discretas con poosibles valores en {A,B,C}. Hay muchos tipos de variables:
Variables Reales, tienen un limite inferior y superior y puede tomar cualquier valor en el rango.
Variables enteras tienen limite inferior y superior puede tomar cualquier valor entero en el intervalo
Variables Logicas: Verdaderas o falsas --> 0 ,1.-
Variables Choice(?) (de elección): Conjunto de valores posibles son representadas por valores enteras con limite inferior de 1 y un limite superior del numero de valores posibles. Estos valores corresponden a diferentes opciones.
Variables Set: tienen diferentes conjuntos como valores posibles. Estas variables pueden ser representadas como variables de eleccion, pero sus interacciones son mas complejas.
  • Función Objetivo: Describe el objetivo, económico o una elección especifica de variables de decisión. Se clasifican en 2 tipos:
F.O lineales: combinación lineal de las variables de decisión.
F.O no lineales: Permitir que para cualquier función de las variables de decisión que cubre una amplia gama de interacciones y compensaciones que pueden ocurrir en situaciones del mundo real.
  • Funciones de restricción: Describe condiciones lógicas o físicas que las variables de decisión tienen que obedecer. Pueden ser lineales o no lineales.
Ademas por ejemplo si A entonces no B --> pueden ser representados utilizando variables lógicas o de forma directa.
La formulación a menudo es alterada por el enfoque deseado. sin embargo, la elección de un método antes de formular un problema no suele ser la mejor manera de proceder.
problemas tienen formulaciones adecuadas para un determinado enfoque, pero el enfoque puede ser muy ineficiente para un determinado problema.

Enfoques de Solución

Heuristicas

Algoritmo que no intenta ser optimo. Se utiliza porque son computacionalmente eficientes y/o fácil de implementar. No son muy precisos ni predecibles, además en ocasiones se desmoronan debido a problemas de escalabilidad y/o supuestos poco realistas. Si el problema se vuelve repetitivo y los parametros cambian con frecuencia, la heuristica tiende a desmoronarse. El rendimiento heuristico puede mejorarse mediante algoritmos de optimización. La optimización es la única manera de garantizar la mejor solucion para todos los parametros del problema.

Técnicas de optimización

  • Sistemas basados en Reglas: Son utilizados en sistemas de control, heuristica y sistemas adaptativos.
Consisten en un proceso controlado por un conjunto fijo de cientos o incluso miles de reglas. En la práctica las reglas y sus interacciones son muy complejas. Si las reglas no cambian como los cambios del sistemas, la optimalidad no está garantizada.
Estos sistemas cambian las reglas dependiendo del estado actual del proceso o el valor de la decision anterior, lo que permite a las reglas adaptarse con el proceso. Aunque es una mejora sobre los sistemas basados en reglas estáticas, la forma en que se adaptan es un estático.
Es un tipo de optimizacion ya que las reglas todavia proporcionan buenas soluciones para una amplia gama de soluciones, sin embargo, aun es un metodo heuristico.
Una forma en que los sitemas basados en reglas proporcionan siempre el optimo: si se ha demostrado que las reglas se usan siempre ofrecen una solucion optima para cualquier estado del proceso, pero suelen se un problema más complejo que generar las reglas primero.
El mayor problema es que nadie sabe las reglas a aplicar.
Sistemas basados en reglas --> Neuron Data, Haly enterprise y ILOG.
  • Programacion Lineal y entera: Es el metodo mas conocido y el mas utilizado.
Utilizado para tomar decisiones de gestión sobre la asignación de recursos escasos a los productos. Los costos de los recursos y los beneficios de los productos se utilizan para determinar la mejor solución.
Los modelos de Programación Lineal, fueron resueltos inicialmente mediante el método Simplex, más recientemente, los métodos de punto interior han pasado al primer plano, que puede resolver problemas con 10.000 restricciones y 100.000 variables.
El problema surge cuando el objetivo o las restricciones no son funciones lineales. En ciertos casos, las funciones no lineales se pueden acercar a lineales por trozos, pero, es una representación ineficiente del problema, además solo un numero limitado de funciones puede ser representado de esa manera.
La Programación Lineal entera utiliza programación lineal para resolver problemas con algunas variables del tipo entero. Las variables enteras son representadas como variables reales y el PL se resuelve, luego en un proceso repetitivo, una variable entera es acotada por arriba o por abajo, en un intento de forzar a un valor entero mediante la adicion de restricciones y el modelo de programacion lineal modicado. Este método (Branch and Bound) termina cando todas las variables enteras toman valores enteros.
Si se tienen muchas variables enteras, la resolucion es muy demorosa. Algunos problemas requieren de millones de iteraciones que hay que resolver.
Vendedores--> ILOG, CPLEX División y OSL.
  • Reducción de Dominio y propagación de restricciones
La reducción de dominio y propagación de restricciones es un enfoque adecuado para problemas con variables y restricciones diferentes, tales como variables enteras, lógicas y/o restricciones lineales y lógicas.
La combinación de la reducción de dominio y propagación de restricciones con programación lineal puede ser muy eficaz cuando se resuelven problemas con ambas variables reales y enteras, y restricciones lineales.
Estas técnicas comienzan con la premisa de que puede ser mas eficiente para identificar donde la solución "no es" (identificar que valor no es) antes de tratar de cuantificar lo que "es".
Cada decisión tiene un dominio de posibles valores, una variable real puede tomar cualquier valor en el Rango [L,U] una variable lógica puede tomar valores 0 o 1.
La Reducción de dominio elimina sistemáticamente valores que no son posibles a partir del dominio de cada variable.
Si hay restricciones suficientes, el dominio puede ser dramáticamente reducido.
Cuando una variable tienen un dominio vacío, el problema se vuelve inviable, es decir, no hay valor posible para esa variable, por lo que el problema no tiene solución.
La Propagación de restricciones trabaja de forma sistemática la reducción de todos los dominios de variables. Cada variable tiene asociada al menos una restricción, de lo contrario es una variable, no restringida.
Cuando el dominio de la variable es alterado, el conjunto asociado a esa variable para cada una de las restricciones se ve afectada. El cambio a sus dominios a la vez afecta a otras variables a través de todas las variables de decisión. La eficacia de este enfoque aumenta a medida que la red de restricciones se expande.
La reducción de dominio y propagación de restricciones permite una representación compacta de soluciones factibles que satisfacen todas las restricciones. Este enfoque permite a todos los tipos de variables y restricciones estar representados en una manera intuitiva. Como las variables están relacionadas entre sí a través de restricciones, la región factible (representado por un dominio de cada variable) es refinada usando propagación de restricciones.
Cuando el valor de una variable se establece, el efecto en todas las otras se conoce instantáneamente.
Si al establecer una variable en un valor determinado hace que otra variable sea inviable, la propagación de restricciones lo revela al instante. Por lo tanto, la región factible es siempre representada, aun cuando en alguna de las variables se hayan establecido valores. Si la región factible llega a estar vacía, los valores establecidos no son factibles y necesitan ser cambiados.
Para encontrar un optimo global, es necesario una búsqueda de todas las soluciones factibles.
Esta búsqueda define el orden en el cual las variables deberían ser establecidas y una manera de elegir un valor desde el dominio de la variable. El algoritmo de búsqueda interno es fundamental para la optimización eficiente. Cuando el único requisito es una solución viable, la primera solución encontrada por el algoritmo de búsqueda es suficiente, pero si una función objetivo esta siendo optimizada, el algoritmo de búsqueda tiene que encontrar el valor de la función objetivo entre todas las soluciones factibles. Si el algoritmo de búsqueda es ineficiente, este proceso puede tomar mucho tiempo para uso practico.
Los vendedores de la reducción de dominio y propagación de restricciones incluye ILOG y COSYTECH


  • Algoritmos Genéticos
Encuentran la solución a problemas mediante el uso de la evolución de una solución aceptable a una mejor. En contraste a los enfoques anteriores, los algoritmos genéticos se centran en la optimización local sin embargo, la evolución es controlada en un intento de buscar en el espacio de la solución entera, que puede formar la optimización global.
Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas