Algoritmos de optimización en ingeniería E-Book

Erik Valdemar Cuevas

• Herausgeber: Marcombo
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Spanisch
• Veröffentlichungsjahr: 2024

Seitenzahl: 217

Beschreibung

La eficiencia y la optimización se erigen como principios clave de la ingeniería y la gestión. Poseer las herramientas y técnicas de optimización correctas se ha vuelto indispensable. La revolución tecnológica y el auge del análisis de datos han resaltado el inmenso valor de los algoritmos de optimización, capaces de descubrir las mejores soluciones en una amplia gama de escenarios, desde la optimización de recursos en proyectos de ingeniería hasta la estrategia de toma de decisiones en la gestión empresarial. Sin embargo, adentrarse en el aprendizaje de la optimización numérica representa un reto significativo, que demanda una sólida comprensión de las matemáticas y la programación informática. La abrumadora cantidad de nueva información y la jerga especializada pueden ser particularmente intimidantes sin la guía de un experto. Este libro se presenta como la solución a este desafío: ofrece una introducción al fascinante mundo de la optimización numérica con un estilo claro y ameno, proporcionando simultáneamente las herramientas esenciales de matemáticas y programación de manera secuencial y accesible, sin necesidad de conocimientos previos especializados. Se distingue de otras publicaciones especializadas por su enfoque eminentemente práctico. Incluye ejemplos en MATLAB, que sirven como herramienta práctica para reducir la distancia entre la teoría y su aplicación en el mundo real. La inclusión de ejemplos de código ya preparados y su explicación línea por línea no solo hace que la materia resulte más atractiva, sino que también anima a experimentar, modificar y mejorar el código con sus propias ideas. Si se acerca a la optimización numérica por primera vez como estudiante, este libro será un recurso de gran valor para sus estudios, y le brindará un entendimiento profundo de los algoritmos de optimización y su aplicación práctica. Si es un profesional que busca adentrarse en el campo de la optimización sin ser un especialista, encontrará en este libro un excelente punto de partida.

Leseprobe

Algoritmos de optimización en ingeniería

© 2024 Avelina Alejo-Reyes, Erik Valdemar Cuevas,Paulina González-Ayala y Julio C. Rosas-Caro

Primera edición, 2024

© 2024 MARCOMBO, S. L.

www.marcombo.com

Ilustración de cubierta: Jotaká

Maquetación: Reverté-Aguilar, S. L.

Corrección: Cristina Pazos

Directora de producción: M.a Rosa Castillo

Cualquier forma de reproducción, distribución, comunicación pública o transformación de esta obra solo puede ser realizada con la autorización de sus titulares, salvo excepción prevista por la ley. Diríjase a CEDRO (Centro Español de Derechos Reprográficos, www.cedro.org) si necesita fotocopiar o escanear algún fragmento de esta obra.

ISBN del libro en papel: 978-84-267-3811-0

ISBN del libro electrónico: 978-84-267-3849-3

Producción del ePub: booqlab

A nuestras familias, amigos y mentores, que han sido nuestros pilares en este viaje.

A nuestros estudiantes y colegas, por compartirnos una parte de su vida, lo que ha profundizado nuestra pasión por la educación y la investigación.Que las páginas siguientes no solo sirvan como una guía para adquirir conocimientos, sino también como una invitación a imaginar y crear.

A todos ustedes, nuestro más sincero agradecimiento y la esperanza de que este trabajo inspire tanto como nosotros hemos sido inspirados en su creación.

Antes de comenzar a leer este libro

En este libro se utiliza la tipografía Courier en los casos en los que se hace referencia a código o acciones por realizar en el ordenador, ya sea en un ejemplo o cuando se refiere a alguna función mencionada en el texto. También se usa para indicar menús de programas, teclas, URL, grupos de noticias o direcciones de correos electrónicos.

Los términos y definiciones que se utilizan mayormente en lengua inglesa se mantienen en este libro en dicho idioma y en cursiva.

El código fuente de los ejemplos, así como todos los recursos didácticos y de programación que se utilizan en este libro, podrán descargarse a medida que se avanza en la lectura.

Estos recursos están disponibles en www.marcombo.info con el código ALGORITMOS24.

Contenido

Prólogo

CAPÍTULO 1Introducción a la optimización

1.1 Definición y conceptos fundamentales

1.2 El problema EOQ, “el problema de Juan”

1.3 Introducción a los métodos de solución. “El gradiente descendiente”

1.3.1 Solución del problema con el método de gradiente descendiente utilizando MATLAB

1.3.2 Explicación del código 1.1

1.4 El método de la derivada igual a cero

1.5 Calcular el gradiente cuando no está definido

1.5.1 Estrategia de paro

1.5.2 Representando la función y la solución actual

1.5.3 Representando los costes parciales y el total

1.6 Ejercicio: maximizar el área de un terreno

1.7 Ejercicio: maximizar la fuerza electroestática entre dos partículas con cargas

1.8 Cuando NO funciona el método del gradiente

1.9 El problema de Juan (EOQ) con óptimos locales ocasionados por descuentos por volumen

1.9.1 El método de la búsqueda aleatoria o Random Search

Referencias

CAPÍTULO 2Gradiente descendiente

2.1 Introducción

2.1.1 Modalidad y dimensionalidad

2.2 El método del gradiente descendiente

2.2.1 Encontrar la cima del cerro en 3D

2.2.2 Dibujando el cerro en 3D

2.2.3 Maximizando la función

2.3 El problema del ajuste de curva

2.3.1 La minimización del error cuadrático

2.3.2 Interpolación cuadrática

2.3.3 Interpolación polinómica

2.4 Maximizando la función Peaks

2.5 Minimizando la función de Bohachevsky

Referencias

CAPÍTULO 3Breve historia de los métodos de optimización metaheurísticos

3.1 Introducción

3.2 Clasificación de las técnicas de optimización

3.3 Exploración y explotación

3.4 Técnicas básicas de selección

Referencias

CAPÍTULO 4EOQ con múltiples proveedores, descuentos por volumen, restricciones de capacidad y de calidad

4.1 Introducción al problema de inventarios

4.1.1 Ejemplo 1. Dos proveedores sin restricción de capacidad

4.1.2 Combinación de proveedores

4.1.3 Restricciones de capacidad

4.1.4 Introduciendo descuentos por volumen

4.1.5 Tratamiento de la calidad imperfecta de las unidades

Referencias

CAPÍTULO 5Distribuciones de probabilidad y el método de Random Search

5.1 Introducción

5.2 Las distribuciones de probabilidad

5.3 El método de la búsqueda aleatoria local o Random Local Search

5.4 El método de la búsqueda aleatoria adaptiva o Adaptive Random Search

5.5 Maximizar el área de un terreno

5.6 Maximizando la función Peaks

5.7 Minimizando la función de Bohachevsky

Referencias

CAPÍTULO 6Método de recocido simulado (Simulated Annealing)

6.1 Introducción

6.2 Descripción del método de recocido simulado

6.3 Ejemplo del método de recocido simulado

Referencias

CAPÍTULO 7Optimización por enjambre de partículas (Particle Swarm Optimization - PSO)

7.1 Introducción

7.2 Descripción del método de PSO

7.3 Funciones útiles en MATLAB

7.4 Maximizar la función Peaks

7.5 Minimizar la función de Bohachevsky

Referencias

Prólogo

En una época donde la eficiencia y la optimización se han convertido en el mantra de la ingeniería y la administración es vital tener a nuestra disposición las herramientas y técnicas de optimización adecuadas. El creciente auge de la tecnología y el análisis de datos ha puesto de manifiesto el valor incuestionable de los algoritmos de optimización. Estos algoritmos nos permiten encontrar las mejores soluciones posibles en una variedad de contextos, desde la planificación de recursos en la ingeniería hasta la toma de decisiones estratégicas en la administración.

Aprender optimización numérica puede ser un reto, ya que es necesario tener conocimientos de matemáticas y programación informática. Además, la cantidad de información que se ha generado recientemente y el uso de términos especializados puede resultar abrumadora, sobre todo para las personas que no cuentan con un profesor experto que los guíe en este tema.

Este libro aborda el siguiente desafío: introducir al lector, con una lectura ligera y amena, al mundo de la optimización numérica y brindar simultáneamente las herramientas de matemáticas y programación, de una forma secuencial que no requiera conocimientos previos especializados ni la ayuda de un instructor experto.

La lectura ligera diferencia a este libro de otros libros especializados en optimización numérica, en los que la densidad del contenido teórico, matemático y de programación hace que comprender unas cuantas páginas nos lleve una buena cantidad de tiempo. Esto supondrá una diferencia considerable para lectores que se inician por primera vez en el tema y que no disponen de un tutor experto que pueda guiarles. Las ecuaciones y temas matemáticos se introducen de forma gradual para una mejor comprensión. El principal reto es que el lector no necesite realizar cursos por separado o leer previamente libros de matemáticas, optimización y programación para iniciarse en el mundo de la optimización y que, una vez ahí, a partir de los conocimientos provistos por este libro, pueda decidirse por rutas de mayor especialización.

Una característica distintiva de este libro es su amplio uso de implementaciones de MATLAB, que sirve como herramienta práctica para reducir la distancia entre la teoría y la aplicación en el mundo real. El libro está estructurado teniendo en cuenta que el aprendizaje se acelera cuando los conceptos teóricos se complementan con ejemplos prácticos de resolución de problemas basados en programación. Este enfoque es particularmente beneficioso para los estudiantes que puedan tener una formación más débil en matemáticas, ya que demuestra el sentido práctico y la eficacia de la optimización de una manera más accesible. La inclusión de ejemplos de código ya preparados no solo hace que la materia resulte más atractiva para los estudiantes, sino que también los anima a experimentar, modificar y mejorar el código con sus propias ideas. Este método de aprendizaje está diseñado para que resulte menos desalentador y más estimulante, sobre todo para aquellos que podrían sentirse abrumados ante la perspectiva de desarrollar programas complejos desde cero. El enfoque del libro pretende desmitificar las complejidades de la optimización en ingeniería industrial, haciéndola más accesible e interesante tanto para estudiantes como para profesionales.

Si eres un estudiante que se aproxima por primera vez a la optimización numérica, encontrarás este libro de gran ayuda para tus estudios, proporcionándote una comprensión sólida de los algoritmos de optimización y de cómo se utilizan en la práctica. Si eres un profesional no especializado en la optimización pero con la necesidad de adentrarse en este campo, este libro te servirá como un excelente punto de partida.

El camino hacia la eficiencia y la optimización puede ser complicado, pero con las herramientas y técnicas adecuadas, se vuelve mucho más manejable. Esperamos que este libro sea un compañero útil en ese viaje.

Avelina Alejo-Reyes,Erik Cuevas,Paulina González-Ayala,Julio César Rosas-Caro.

CAPÍTULO 1

INTRODUCCIÓN A LA OPTIMIZACIÓN

1.1 Definición y conceptos fundamentales

La optimización es un acto natural para el ser humano, tan natural que lo hacemos todo el tiempo, a veces sin percatarnos de ello. Siguiendo a [1.1] y [1.2], podemos definir la optimización de la siguiente manera: “Optimizar es tomar las decisiones para obtener el mejor resultado posible con los recursos y restricciones que tenemos”.

Las personas adquieren viviendas, ordenadores, coches, ropa, comida, una profesión, una pareja, una ciudad de residencia. En todas las elecciones las personas preferimos las mejores opciones a las peores, sin embargo, solemos ser conscientes de nuestras limitaciones y de nuestras restricciones y, debido a ello, no siempre optamos por las mejores opciones en todo, sino por las que consideramos las mejores considerando nuestras prioridades, nuestros recursos y nuestras restricciones. Todos coincidimos en que una casa grande bonita y bien ubicada es la mejor opción, pero, a veces, debido a nuestras restricciones, sacrificamos el tamaño por una buena ubicación, o viceversa. No escogemos las mejores opciones, escogemos las opciones óptimas, que desde cierto punto de vista sí son las mejores, considerando las opciones, prioridades y restricciones. A esta tarea que llevamos a cabo la denominamos optimización.

Las limitaciones y restricciones mejor entendidas son las relacionadas con la economía; las entendemos bien porque las vivimos todo el tiempo, por eso es por lo que este libro abordará en su mayoría ejemplos de la economía simple (sin abordar temas financieros complejos).

Optimizar también se puede traducir, en cierta forma, como decidir qué coste estamos dispuestos a pagar, o qué sacrificios estamos dispuestos a hacer, con tal de obtener los beneficios correspondientes. En los problemas físicos o en los matemáticos sucede algo similar, suele haber un coste para cada resultado, una variable que se puede explicar como el coste de otra. El coste no es necesariamente algo malo, simplemente es lo que necesitamos invertir para obtener el resultado esperado.

Pongamos un ejemplo. En la industria automotriz los diseñadores de coches ofrecen, entre otros, distintas opciones de coches deportivos, con una considerable capacidad de aceleración. Estos suelen contar con un motor de gran potencia y suelen ser coches pequeños con un peso considerablemente menor al de los coches familiares. Podríamos decir que, si queremos maximizar la aceleración, necesitamos maximizar la potencia del motor y minimizar el peso del vehículo. Por eso, los coches deportivos suelen ser pequeños, pero tienen un motor muy potente. Por otra parte, los conductores de coches deportivos no esperan que su vehículo tenga un bajo consumo de combustible, o que el mantenimiento sea económico. Los coches de bajo consumo también suelen ser pequeños, pero por lo general su motor es de poca potencia. Por su parte, los coches familiares suelen tener un tamaño considerablemente grande y un motor potente. Sin embargo, el motor, en relación con el peso del vehículo, no suele estar diseñado para ofrecer una alta aceleración, sino para guardar un equilibrio entre aceleración y consumo de combustible mientras se cumple con la posibilidad de llevar a muchos pasajeros, en ocasiones hasta tres filas de asientos. Por último, los camiones también suelen contar con muchos caballos de potencia, pero, debido a su tamaño, en la práctica acaban siendo los vehículos con menor aceleración.

Podemos identificar en los diseñadores de coches señales claras de toma de decisiones basadas en directrices, recursos y restricciones.

¿Sería posible diseñar un camión o un tráiler con alta aceleración? Sí, es posible fabricar un motor muy grande. Probablemente no lo hacen porque los fabricantes calculan que el coste sería muy alto, y que no tendría un alto volumen de ventas, que sus compradores preferirían el tipo de camiones que se venden actualmente. Podríamos repasar muchos ejemplos y detectar la optimización detrás de casi cualquier actividad humana.

La optimización no solo está en los fabricantes de coches, también en las personas o en los consumidores. Hay personas que prefieren no invertir demasiados recursos en un coche para tener esos recursos disponibles o para destinarlos a otros gastos que consideran más importantes, y en esos gastos es donde dichas personas tratan de optimizar sus recursos.

Las situaciones físicas se pueden representar en términos matemáticos, a lo que comúnmente llamamos modelar[1.3], y una vez que se encuentran modeladas matemáticamente es posible optimizarlas utilizando las técnicas que describiremos en este libro. En términos matemáticos optimizar implica encontrar los valores mínimos o máximos de una función objetivo bajo ciertas restricciones matemáticas (si las hay). La función objetivo es una variable que depende de otras variables de entrada. El objetivo de los algoritmos de optimización no es solo encontrar el mínimo o máximo de la función objetivo, sino los valores de las variables independientes que dan como resultado dicho valor mínimo o máximo [1.4].

Retomando la definición que enunciamos sobre la optimización: “tomar las decisiones para obtener el mejor resultado posible con los recursos y restricciones que tenemos”; el obtener los mejores resultados puede referirse a muchas cosas, por ejemplo, maximizar las ganancias en un proyecto o minimizar el coste de un producto.

Tal como se ha mencionado, la optimización se utiliza en un amplio espectro de aplicaciones, no solo en las relacionadas con la economía, pero las opciones relacionadas con la economía tienen un atractivo didáctico sobresaliente, por lo que serán utilizadas para diversas explicaciones en este libro.

La función objetivo es una representación matemática de la variable (por ejemplo, el coste) que se desea optimizar [1.5]. En un problema de optimización se busca encontrar el valor mínimo o máximo de esta función. Las restricciones, por otro lado, son las limitaciones o condiciones bajo las cuales se debe resolver el problema.

Los problemas de optimización pueden ser lineales o no lineales [1.6], dependiendo de si la función objetivo y las restricciones son representadas por una ecuación lineal o no. Su función objetivo puede tener forma convexa o no convexa. También pueden ser de variable única o de múltiples variables, dependiendo de la cantidad de variables de decisión involucradas. Estos términos, que pueden sonar extraños en este momento, serán abordados en los siguientes capítulos, pero comenzaremos con ejemplos simples que nos ayuden a desenvolvernos es estos temas poco a poco antes de incrementar gradualmente la dificultad de los mismos.

1.2 El problema EOQ, “el problema de Juan”

Comenzaremos analizando lo que vamos a denominar “el problema de Juan”. Juan vive en una comunidad remota y es el distribuidor local de agua purificada, la cual vende en envases de 5 litros. Juan compra estos envases a 1 euro cada uno, pero para ir a comprarlos debe ir al pueblo más cercano, lo cual le cuesta 10 euros, teniendo en cuenta los gastos en combustible y el mantenimiento de su vehículo. Asimismo, su coche puede transportar un máximo de 200 envases.

Juan vende 5 envases de agua por día. Los guarda en el almacén local de la comunidad, en donde ha de pagar 5 céntimos en concepto de almacenaje por cada envase y por cada día.

De forma rutinaria, cuando se le acaba el inventario (los envases disponibles para vender), viaja al pueblo de nuevo y compra otros 200 envases de agua (los que le caben en su coche), que le duran unos 40 días. Ese día Juan gasta 210 euros, 200 por los envases y 10 por el viaje.

Juan es una persona curiosa que disfruta de los retos mentales. Además, le gusta tomar decisiones sabias, por lo que a veces Juan se pregunta si su método de trabajo es el mejor o si habría una forma de administrar mejor sus recursos.

Así que vamos a analizar el problema de Juan y a tratar de optimizarlo. Concretamente vamos a tratar de minimizar el coste de mantenimiento de su inventario. Nótese que no mencionamos el precio al que Juan vende sus envases de agua. De hecho, no es necesario saber esto para minimizar el coste de administración de inventario, pero, si el lector lo desea, puede imaginar cierto precio de venta, por ejemplo, 4 euros por envase. Nótese también que hemos definido que venderá 5 envases diarios, esto es, suponer que la demanda es constante, lo cual podemos hacer como primera aproximación. En la vida real es difícil dar con un ejemplo de demanda constante, pero sí que podemos obtener un promedio de ventas por día y utilizar ese parámetro para el modelo matemático. Esta es una práctica común en diversos sectores industriales. Además, existen algoritmos que nos pueden ayudar a predecir variables como esta. En cualquier caso, nos vamos a centrar en los gastos de Juan, que es lo que deseamos minimizar, con los datos que nos son proporcionados.

El primer paso para resolver este problema es modelarlo matemáticamente, esto es, expresar matemáticamente el coste promedio que Juan paga por mantener su inventario.

TC es para nosotros el periodo del ciclo de orden. Todas las empresas compran sus productos y planifican las compras de forma cíclica, el periodo puede durar quince días o un mes, incluso habrá empresas cuyo ciclo de orden para algún producto dure varios meses.

Después de saber cada cuánto va al pueblo (cada TC), podemos asegurar que el coste promedio de transportar sus envases de agua del pueblo a su comunidad se puede expresar como (1.2).

Si lo multiplicamos por h (el coste de almacenamiento por cada envase) y lo dividimos entre TC obtendremos el coste promedio. Este coste promedio de almacenamiento de productos del inventario se puede calcular como (1.4).

Figura 1.1 Comportamiento del inventario.

De (1.4) es posible observar que el coste promedio de almacenamiento aumenta cuando aumenta la cantidad (Q) de envases que Juan compra.

El coste promedio P de las piezas es fijo (1 euro por envase). Si conocemos la demanda diaria, podemos calcular cuánto gasta Juan en promedio por día en pagar los envases de agua, y podemos calcularlo como (1.5).

El coste de los envases no depende de la cantidad (Q) de envases que él compra cada vez que va al pueblo, solo depende de la demanda, que en nuestro ejemplo es constante.

La ecuación del gasto promedio de Juan se puede obtener sumando los tres tipos de costes descritos en (1.2), (1.4) y (1.5), y se puede expresar como (1.6).

Esta es la formula más importante de nuestro problema, la que nos da el resultado que queremos minimizar. La llamaremos función objetivo f(Q) y, dado que queremos hacerla lo más pequeña posible, estamos frente a un problema de minimización. La tabla 1.1 muestra un resumen de los parámetros en (1.6).

Tabla 1.1 Parámetros de (1.6)

Es interesante ver que una decisión que pareciera intrascendente puede mejorar el resultado. Sería más interesante saber cómo hacer esto.

La diferencia entre los costes descritos podría parecer pequeña para algunos lectores cuando hablamos de cantidades pequeñas como en este ejemplo, pero hay empresas cuyo coste de inventario se mide en millones de euros, y un ahorro de un pequeño porcentaje podría significar mucho dinero. Además, en un mundo competitivo, cualquier ventaja cuenta.

Lo más importante es que lo único que tiene que hacer Juan para ahorrar dinero es tomar una decisión: decidir cuántos envases debe comprar cada vez que va al pueblo. Pero ¿cómo podría Juan saberlo? ¿Cómo encontrar el valor óptimo? ¿Se puede hacer con MATLAB? ¿Se puede optimizar todo? O ¿qué cosas sí podemos optimizar? Estas son las preguntas que abordaremos en este libro.

La optimización tiene un papel central en muchos campos, pero es especialmente relevante en la ingeniería y la administración. En la ingeniería, los problemas de optimización surgen con frecuencia en áreas como la planificación y control de procesos, el diseño de sistemas, la distribución de recursos y la toma de decisiones estratégicas. Los ingenieros a menudo necesitan encontrar la solución más eficiente o rentable a un problema, dadas ciertas limitaciones. Esto puede implicar, por ejemplo, minimizar el coste de producción de cierto producto, manteniendo al mismo tiempo un nivel de calidad específico.

En la administración, los problemas de optimización también son muy comunes. Por ejemplo, una empresa puede querer maximizar sus beneficios sujetos a restricciones de presupuesto, o puede querer encontrar la forma más eficiente de asignar a sus empleados a diferentes tareas. La optimización también puede ser útil en la planificación estratégica, ayudando a los administradores a tomar decisiones informadas y eficientes.

En los capítulos subsecuentes exploraremos en detalle diferentes tipos de problemas de optimización y cómo se pueden resolver utilizando algoritmos y técnicas específicas. También veremos cómo estos conceptos se pueden aplicar en la ingeniería y la administración, y cómo se pueden implementar en el lenguaje de programación de MATLAB.

MATLAB es una potente plataforma de cálculo numérico que, además, es un programa de uso común para los estudiantes de ingeniería. Al final de este libro, el lector tendrá un punto de inicio claro en los fundamentos de la optimización y será capaz de aplicar estos conceptos en su propio trabajo.

Por otra parte, el lector podrá implementar los conceptos descritos en este libro en otros paquetes computacionales, tales como Excel o Python.

1.3 Introducción a los métodos de solución. “El gradiente descendiente”

Existen diversos métodos de optimización numérica ([1.7] y [1.8]), algunos de los cuales serán abordados en este libro. Sin embargo, podemos comenzar con uno de los más utilizados y simples: el método del gradiente, también llamado método del gradiente descendiente.

Para introducir el significado de estos métodos podemos imaginar que estamos en un enorme cerro al que subimos caminando. Sin embargo, llegada la tarde, la cima del cerro se cubre de una densa niebla y no podemos ver a distancia, solo alcanzamos a visibilizar algunos metros delante de nosotros. Queremos bajar el cerro, al menos lo suficiente como para evitar la niebla, así que debemos definir una estrategia; podemos seguir esta simple regla, ir siempre hacia abajo, podemos dar un paso en cada dirección, sentir cuál de esos pasos nos lleva cuesta abajo más rápidamente y seguir esa dirección. Esto, en esencia, es el método del gradiente descendiente.

Figura 1.2 Cómo bajar un cerro si ha sido cubierto con una densa niebla.

El ejemplo descrito trata sobre un problema de minimización. Queremos llegar abajo o minimizar la altura a la que estamos. Aunque no conozcamos el camino, intuitivamente sabemos que, si avanzamos siempre hacia abajo, seguramente llegaremos al pie del cerro. La contraparte de minimización sería llegar a la cima, esto sería un problema de maximización y la estrategia análoga sería avanzar siempre hacia arriba.