Introducción a la Optimización matemática

Introducción a la Optimización matemática

Antonio H. Escobar Zuluaga

Universidad Tecnológica de Pereira - Colombia 2011

Que es Optimizar?

•

Es maximizar o minimizar recursos o procesos.

•

Es hacer más con los mismos recursos.

•

Es hacer lo mismo con menos recursos.

•

Es cambiar recursos ineficientes por recursos eficientes.

•

Es eliminar recursos existentes que afectan negativamente el sistema.

Justificación de la Optimización

El concepto de incertidumbre juega un rol importante en la investigación de los problemas de ingeniería

Porque Optimizar en las organizaciones? •

Porque existen recursos que no están siendo aprovechados adecuadamente.

•

Porque no se alcanzan los resultados deseados con los recursos disponibles.

•

Porque se tienen recursos ineficientes o que no se necesitan y que frenan el desarrollo.

•

Porque se requiere aumentar la competividad a costos eficientes de inversión, operación y mantenimiento. Porque existe una exigencia creciente de sistemas y procedimientos más eficientes.

•

La optimización está asociada a: •

Nivel de conocimiento científico acumulado en los grupos de desarrollo.

•

Nivel de tecnología que los miembros del grupo dominan.

•

Nivel y calidad de los desarrollos realizados.

•

Costos de producción obtenidos.

•

Variabilidad de los aspectos que se pueden resolver.

La optimización está asociada a: •

Desarrollo de la infraestructura tecnológica que se usa.

•

Adecuada valoración de resultados.

•

Flujo de ideas entre los miembros del grupo.

•

Calidad de los insumos.

•

Nivel de desperdicio.

•

Estrategias utilizadas.

La optimización requiere de:

La optimización genera nuevas exigencias:

Definición de optimización:

Se optimiza:

Se minimiza:

Se maximiza:

Áreas de aplicación:

Mínimos y máximos globales y locales, puntos de inflexión:

Componentes de un problema de optimización: •

Función Objetivo: Medida de la efectividad buscada expresada en función de las variables de decisión. Es lo que se minimiza o se maximiza.

•

Decisiones cuantificables sobre las que se ejerce control. Por ejemplo: calibre de un conductor eléctrico que se usará en un diseño.

•

Restricciones:

Factores que limitan los valores que pueden asumir las variables de decisión. Por ejemplo: corriente máxima del conductor.

•

Parámetros:

Variables de decisión:

Datos o recursos que asumen valores constantes y que forman los coeficientes de las variables. Por ejemplo: resistencia del conductor por unidad de longitud.

Que es el modelado?

•

Los procesos y sistemas en ingeniería son generalmente complicados y deben ser simplificados mediante idealizaciones y aproximaciones para poder resolver el problema planteado

•

El proceso de simplificación del problema, para que pueda ser representado en términos de un sistema de ecuaciones (para el análisis, diseño y optimización) es lo que se conoce como modelado

Modelo matemático:

•

Un modelo matemático es uno que representa el desempeño y comportamiento de un sistema dado en términos de ecuaciones matemáticas, ofreciendo resultados cuantitativos

•

Los modelos matemáticos pueden estar basados en el entendimiento físico de un sistema ó por construcción de modelos a partir de datos (e.g., ajuste de curvas a datos experimentales).

•

Las ecuaciones que gobiernan el sistema pueden ser algebraicas, ecuaciones diferenciales ordinarias y/o parciales, ecuaciones integrales ó combinación de varias de ellas

Mundo Real

Mundo Real

Mundo Real

Min Σt Σj Σh CTt(GTjth) Min Σt Σj Σh CTt(GTjth) sujeto a: sujeto a: GDzth - ΣuεTN(z) LDuzth = 0 GDzth - ΣuεTN(z) LDuzth = 0 GDzth + GHAzth + DEFzth = DEMzth GDzth + GHAzth + DEFzth = DEMzth ENuth - ΣjεL1(u) GTEjuth EN - ΣjεL1(u) GTEjuth - Σuth vεL2(u) LLvuth = 0 - ΣvεL2(u) LLvuth = 0

Mundo Real

Mundo Virtual

Min j Σh CTt(GTjth) Min ΣΣt Σ t Σj Σh CTt(GTjth) sujeto sujetoa:a: - ΣuεTN(z) LDuzth = 0 GD GDzth zth - ΣuεTN(z) LDuzth = 0 GD + GHAzth + DEFzth = DEMzth GDzth zth + GHAzth + DEFzth = DEMzth EN - ΣjεL1(u) GTEjuth ENuth uth - ΣjεL1(u) GTEjuth - -ΣΣvεL2(u) LL vuth ==00 LL vεL2(u)

vuth

Mundo Virtual Inflación = 10%

Costo de transporte

Min j Σh CTt(GTjth) Min ΣΣt Σ t Σj Σh CTt(GTjth) sujeto sujetoa:a:

PIB 5.2% Costo de combustibles

GD - ΣuεTN(z) LDuzth = 0 GDzth zth - ΣuεTN(z) LDuzth = 0 GD + GHAzth + DEFzth = DEMzth GDzth zth + GHAzth + DEFzth = DEMzth EN - - ΣΣjεL1(u) GTE ENuth GTEjuth juth - -uth ΣΣvεL2(u) jεL1(u) LL vuth ==00 LL vεL2(u)

vuth

Devaluación 12%

Costo de oportunidad Hidrología

Modelamiento matemático:

Representación matemática de un problema de optimización:

Modelamiento matemático: Ejemplo: Una empresa fabrica transformadores y motores eléctricos, para lo cual requiere de tres tipos de materia prima: fleje de hierro, alambre aislado de cobre y alambre aislado de aluminio, en la proporción que se muestra en la siguiente tabla: Materia prima

Kilos de materia prima necesarias para construir una unidad de:

transformador

Cantidad mensual máxima de materia prima disponible (Kg):

motor

hierro

2

1

1500

cobre

1

1

1200

aluminio

1

0

500

Lucro líquido por unidad fabricada

$ 15

$ 10

Cual debe ser la producción de transformadores y motores para maximizar el lucro?

Variables de decisión: x1 Materia prima

x2

Kilos de materia prima necesarias para construir una unidad de:

transformador

Cantidad mensual máxima de materia prima disponible (Kg):

motor

hierro

2

1

1500

cobre

1

1

1200

aluminio

1

0

500

Lucro líquido por unidad fabricada

$ 15

$ 10

X 1 : cantidad de transformadores producidos X 2 : cantidad de motores producidos

Modelamiento matemático: 2. Función Objetivo

Como existen muchas soluciones, debe Definirse un objetivo, que se denomina La función objetivo del problema.

Lucro = $15 x1 + $10 x2 Lucro ($) = 15 x1 + 10 x2

Modelamiento matemático: 3. Los recursos tienen restricciones Materia prima

Cantidad mensual máxima de materia prima disponible (Kg):

hierro

1500

cobre

1200

aluminio

500

Las restricciones de los recursos se relacionan con las variables de decisión a través de ecuaciones matemáticas algebráicas de igualdad o desigualdad.

Modelamiento matemático: Forma matemática de las restricciones: transformador

motor

hierro

2

1

Cantidad máxima disponible 1500

cobre

1

1

1200

aluminio

1

0

500

La cantidad de recurso es positiva:

Modelamiento matemático:

Modelo matemático resultante

Dificultades de la optimización:

Dificultades de la optimización: Técnicas de modelamiento Problema de la Vida real

Modelo Matemático de la parte que deseo controlar

Técnicas de solución Solución Realimentación o ajustes para la implementación

Matemática

Enfoques respecto a las metodologías de solución: Respecto a los objetivos

Multiobjetivo

Mono-objetivo

Respecto a la complejidad Exacta Sin incertidumbre

Respecto a los datos

Con incertidumbre

Metaheurística

Metodologías de solución: •

Optimización exacta • Programación Lineal. • Programación No Lineal • Programación No lineal enteramixta • Programación binaria

•

Procesos Estocásticos • Probabilidad • Estadística Clásica • Estadística Bayesiana • Series de Tiempo • Estimación de Estado • Econometría • Teoría de Colas

• Inteligencia Artificial • Redes Neuronales • Búsqueda Tabú • Algoritmos Genéticos • GRASP • Simulated Annealing • Colonia de hormigas • Scatter Search • Lógica Difusa • Sistemas Expertos • Recocido simulado • Teoría de juegos • Técnicas Multiobjetivo

Solución del modelo matemático:

Modelo matemático resultante

Representación gráfica del modelo matemático resultante Solución óptima:

Función Objetivo

Efecto del cambio de la función objetivo

Nueva solución óptima

Nueva Función Objetivo

Dualidad en optimización: max 15*x1 + 10*x2 ; s.a. 2*x1 + x2 5 x1 + x2 5 x1 0

Variables duales (las entrega el PL)

X1 = X2 =

300.0 900.0

Dualidad en optimización: max 15*x1 + 10*x2 ;

X1 = X2 =

301.0 899.0

s.a. 2*x1 + x2 5 x1 + x2