Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Optimización en Ingenieŕıa
Dr. Carlos A. Coello Coello
Departamento de Computación
CINVESTAV-IPN
Av. IPN No. 2508
Col. San Pedro Zacatenco
México, D.F. 07300
email: [email protected]
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Introducción
Llamamos optimización al acto de obtener el mejor resultadoposible dadas ciertas circunstancias. No existe ningún método deoptimización que pueda resolver eficientemente todo tipo deproblemas y de ah́ı que se hayan desarrollado diversos métodos a lolargo de los años.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Introducción
La optimización tiene enorme aplicabilidad en muchas ramas delconocimiento, aunque el énfasis de este curso serán las aplicacionesen ingenieŕıa. Nótese que este curso dará prioridad a los aspectosalgoŕıtmicos y de implementación sobre los aspectos teóricos. Por lotanto, se requieren buenos conocimientos de programación,aśı como conocimientos básicos de cálculo y de trigonometŕıa.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Introducción
A los métodos de optimización se les conoce también comotécnicas de programación matemática y se les suele estudiaren investigación de operaciones.
La investigación de operaciones es una rama de lasmatemáticas que se ocupa de métodos y técnicas aplicables aproblemas de toma de decisiones, aśı como del establecimiento delas mejores soluciones posibles (o sea, las óptimas).
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Introducción
La tabla del acetato siguiente muestra una clasificación de métodosde optimización:
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Técnicas de Programación Técnicas Métodos
Matemática Estocásticas Estad́ısticos
Métodos de cálculo Teoŕıa de decisión Análisis de regresión
Cálculo de variaciones estad́ıstica Análisis de clusters,
Programación no lineal Procesos de Markov reconocimiento de patrones
Programación geométrica Teoŕıa de colas Diseño de experimentos
Programación cuadrática Teoŕıa de renovación Análisis discriminatorio
Programación lineal Métodos de simulación (análisis de factores)
Programación dinámica Teoŕıa de confiabilidad
Programación entera
Programación estocástica
Programación separable
Programación multiobjetivo
Métodos de redes: CPM y PERT
Teoŕıa de juegos
Recocido simulado
Algoritmos genéticos
Redes Neuronales
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Introducción
Nótese que en este curso nos concentraremos en las técnicas deprogramación matemática y no cubriremos ni métodos estocásticosni métodos estad́ısticos.
Dentro de las técnicas de programación matemática, nosconcentraremos fundamentalmente en los métodos paraoptimización no lineal sobre una y varias variables, en la ausenciade restricciones. Veremos también (si el tiempo lo permite) un pocosobre métodos de optimización en espacios restringidos.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Introducción
Las técnicas de programación matemática son útiles paraencontrar el mı́nimo de una función de varias variables sujeta a unconjunto de restricciones. Las técnicas estocásticas puedenusarse para analizar problemas descritos por un conjunto devariables aleatorias con una distribución de probabilidad conocida.
Los métodos estad́ısticos nos permiten analizar datosexperimentales y construir modelos emṕıricos para obtener larepresentación más precisa posible del problema real.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
Los primeros métodos de optimización se remontan a la época deIsaac Newton (1643-1727), Joseph-Louis Lagrange (1736-1813) yAugustin-Louis Cauchy (1789-1857).
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
El desarrollo de métodos de cálculo diferencial para optimizar fueposible gracias a las contribuciones de Isaac Newton y GottfriedWilhelm von Leibniz (1646-1716).
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
Los fundamentos de cálculo de variaciones, que lidia con laminimización de funciones, fueron sentados por Johann Bernoulli(1667-1748), Leonhard Euler (1707-1783), Joseph-Louis Lagrange yKarl Weierstrass (1815-1897).
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
El método de optimización para problemas con restricciones, elcual involucra la adición de multiplicadores desconocidos, se conocecomo hoy en d́ıa con el nombre de su inventor: Lagrange.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
Cauchy desarrolló la primera aplicación del método de descensoempinado para resolver problemas de minimización sinrestricciones.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
A pesar de estas primeras aplicaciones, se logró muy poco progresohasta mediados del siglo XX, cuando el advenimiento de lascomputadoras digitales hizo posible la implementación de losalgoritmos de optimización existentes y estimuló el desarrollo denuevos métodos.
Esto marcó el inicio de una época incréıblemente productiva en lacual surgió un volumen muy considerable de publicaciones sobreoptimización. Esto produjo también el surgimiento de varias áreasbien definidas en teoŕıa de la optimización.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
Es interesante hacer notar que los principales desarrollos en el áreade métodos numéricos para optimización sin restricciones sellevaron a cabo en el Reino Unido en los 1960s. El método simplexfue desarrollado por George Dantzig (1914- ) en 1947 y el principiode optimalidad para problemas de programación dinámica fueanunciado en 1957 por Richard Bellman (1921-1984).
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
Esto sentó las bases para el desarrollo de métodos de optimizaciónen espacios restringidos. Sin embargo fue el trabajo de Harold W.Kuhn y Albert W. Tucker en 1951 en torno a las condicionesnecesarias y suficientes para la solución a un problema deoptimización lo que estableció los fundamentos para una enormecantidad de investigación posterior en optimización no lineal.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
Igualmente significativas fueron las contribuciones de G. Zoutendijky J. Ben Rosen durante principios de los 1960s (amboscontribuyeron a la optimización no lineal).
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
Aunque no se ha encontrado ninguna técnica de optimización cuyaaplicabilidad a programación no lineal sea universal, el trabajo deC.W. Carroll y el de Anthony V. Fiacco & Garth P. McCormick,permitió resolver una amplia gama de problemas con restriccionesusando funciones de penalización.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
La programación geométrica fue desarrollada en los 1960s por R.J.Duffin, C. Zener y E.L. Peterson.
Ralph E. Gomory realizó trabajo pionero en programación entera,que ha sido una de las áreas de mayor crecimiento en optimización(esto se debe a que muchos problemas del mundo real caen dentrode este tipo de clasificación).
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
George Dantzig y Abraham Charnes & William Wager Cooperdesarrollaron técnicas de programación estocástica para resolverproblemas en los cuales se presupone que los parámetros de diseñoson independientes y siguen una distribución normal.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
El deseo de optimizar simultáneamente dos o más funcionesobjetivo, motivó el desarrollo de la optimización multiobjetivo.
Uno de los primeros métodos multiobjetivo que aún sigue en usofue la programación por metas (goal programming), propuesta porCharnes y Cooper en 1961 para problemas lineales.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
Los fundamentos de teoŕıa de juegos fueron desarrollados por Johnvon Neumann en 1928, y desde entonces se ha aplicado esta técnicaa varios problemas, sobre todo en economı́a. La aplicación de teoŕıade juegos a la solución de problema de ingenieŕıa es relativamentereciente.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
La segunda mitad del siglo XX se caracterizó por el advenimientode las heuŕısticas tales como el recocido simulado, los algoritmosgenéticos y las redes neuronales.
El recocido simulado imita el proceso de enfriamiento de los sólidos.Los algoritmos genéticos son técnicas de búsqueda y optimizaciónbasadas en la selección natural y la genética.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Antecedentes Históricos
Las redes neuronales son técnicas de clasificación basadas en el usode modelos de celdas simples (llamadas “neuronas”)interconectadas entre śı.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Algunas Aplicaciones de
la Optimización en Ingenieŕıa
En el sentido más amplio del término, la optimización puedeaplicarse para resolver cualquier problema de ingenieŕıa. Algunosejemplos de aplicaciones son los siguientes:
Diseño de estructuras para aviación y el espacio con un pesomı́nimo.
Determinación de trayectorias óptimas de veh́ıculos espaciales.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Algunas Aplicaciones de
la Optimización en Ingenieŕıa
Diseño de estructuras civiles tales como marcos, cimentaciones,puentes, torres, chimeneas, y presas, con un costo mı́nimo.
Diseño śısmico de estructuras (con cargas aleatorias).
Diseño de sistemas de agua potable y alcantarillado.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Algunas Aplicaciones de
la Optimización en Ingenieŕıa
Diseño de herramientas y demás componentes mecánicos.
Diseño de turbinas, bombas y equipo para transferencia decalor.
Diseño de equipo eléctrico (motores, generadores ytransformadores).
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Algunas Aplicaciones de
la Optimización en Ingenieŕıa
Diseño de redes eléctricas.
Planeación de producción.
Diseño de redes hidráulicas.
Clase No. 1 2007
Optimización en Ingenieŕıa Dr. Carlos A. Coello Coello
Algunas Aplicaciones de
la Optimización en Ingenieŕıa
Optimización de horarios.
Diseño óptimo de procesos qúımicos.
Control de inventarios.
Diseño de sistemas de control.
Clase No. 1 2007