Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización

Equation Chapter 1 Section 1 Trabajo Final de Grado Ingeniería de las Tecnologías Industriales Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Autora: Julia Caballero Galiano Tutora: Alicia Robles Velasco Dpto. de Organización Industrial y Gestión de Empresas II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2023 iii Trabajo Final de Grado Ingeniería de las Tecnologías Industriales Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Autora: Julia Caballero Galiano Tutora: Alicia Robles Velasco Profesor Sustituto Interino Dpto. de Organización Industrial y Gestión de Empresas II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2023 v Trabajo Final de Grado: Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Autora: Julia Caballero Galiano Tutora: Alicia Robles Velasco El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2023 El Secretario del Tribunal vii A mi familia A mis profesores ix Agradecimientos Este trabajo marca el punto final de cuatro años de carrera, cuatro años de aprendizaje tanto académico como personal. Y no puedo olvidarme de todos aquéllos que han estado conmigo durante esta etapa tan importante en mi vida. Primero agradecer a mi familia el apoyo constante y empujarme siempre a seguir y dar la mejor versión de mi misma cuando ni yo creía que fuera posible. Suena a cliché, pero de verdad que no podría haber hecho esto sin ellos. Por supuesto, gracias también a mis amigos. Estos años hemos compartido mucho y hemos ido aprendiendo los unos de los otros, apoyándonos en todo momento y haciendo los momentos duros un poco más amenos. Aunque acabe esta etapa, sé que las amistades que he hecho en esta carrera me acompañarán siempre. Finalmente, quisiera acordarme también de todos mis profesores, pero especialmente de Alicia Robles. He aprendido muchísimo con el trabajo que me has propuesto, pero sobre todo me ha servido para apreciar lo importante y bonita que puede ser esta carrera. Gracias por tu implicación constante y las facilidades que me has puesto en todo momento. Julia Caballero Galiano Sevilla, 2023 ÍNDICE DE ILUSTRACIONES Ilustración 1. Hitos de la ingeniería industria 4 Ilustración 2. Representación estadística del número de egresados en IOI de 2º ciclo, Grado y Máster 8 Ilustración 3. Poliedro que representa la solución factible 26 Ilustración 4. Ejemplo generación matriz método simplex 27 Ilustración 5. Variable de entrada método Simplex 28 Ilustración 6. Variable de salida método Simplex 28 Ilustración 7. Actualización matriz método simplex 29 Ilustración 8. Planteamiento problema de la dieta en Excel 30 Ilustración 9. Programación del problema en Solver 30 Ilustración 10. Método resolución Solver 30 Ilustración 11. Línea del código para la creación del modelo 31 Ilustración 12. Líneas del código para la creación de variables 31 Ilustración 13. Línea del código para establecer la función objetivo 32 Ilustración 14. Líneas del código para establecer las restricciones 32 Ilustración 15. Líneas del código para resolver el modelo 32 Ilustración 16. Cruce en un punto 34 Ilustración 17. Cruce en dos puntos 35 Ilustración 18. Cruce aleatorio 35 Ilustración 19. Mutación 35 Ilustración 20. Esquema con los pasos del algoritmo genético 37 Ilustración 21. Ejemplo de mutación aplicado al TSP 43 Ilustración 22. Mapa ruta aleatoria 45 Ilustración 23. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 3158 km 46 Ilustración 24. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 3179 km 47 Ilustración 25. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 3086 km 48 Ilustración 26. Mapa con la mejor ruta. TSP 10 ciudades 48 Ilustración 27. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 5911 km 49 Ilustración 28. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 5836 km 50 Ilustración 29. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 5931 km 50 Ilustración 30. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 5814 51 Ilustración 31. Mapa con la mejor ruta. TSP 30 ciudades 52 Ilustración 32. Productos incluidos en la mochila. Aptitud 13 55 Ilustración 33. Productos incluidos en el camión. Beneficio 9880 € 56 Ilustración 34. Productos incluidos en el camión. Beneficio 10030 € 57 Ilustración 35. Productos incluidos en el camión. Beneficio 10100 € 57 xvii Ilustración 36. Productos incluidos en el camión. Beneficio 10180 58 1 1 INTRODUCCIÓN a relevancia de la ingeniería industrial y de la ingeniería de organización es indudable; sin embargo, hoy en día sigue existiendo confusión acerca de lo que realmente tratan y para qué sirven. Ambas son disciplinas muy versátiles que se complementan entre sí y se centran en mejorar la eficiencia y productividad de procesos de todo tipo. Relacionada con ambas ramas está la investigación de operaciones, que consiste en la aplicación de técnicas matemáticas, estadísticas y de programación para la optimización de procesos productivos y ayudar en la toma de decisiones. Con ese fin, se plantean modelos matemáticos en los que la función objetivo suele ser maximizar beneficios o minimizar costes o distancias y se busca la solución óptima, cumpliendo siempre una serie de restricciones. Algunas de las muchas aplicaciones de la investigación operativa son el problema de la dieta, el problema del viajante y el problema de la mochila. Son problemas aplicables a todo tipo de ámbitos en los que hay que tomar decisiones, desde empresas hasta situaciones cotidianas. En conclusión, estas disciplinas tienen en común la búsqueda de la optimización y la resolución de problemas complejos, fomentando la innovación y la calidad. Para continuar su desarrollo es clave concienciar a la sociedad de su importancia e incentivar su estudio. El objetivo de este trabajo es ayudar a la difusión de la investigación operativa. Para ello, se desarrollan y resuelven los tres problemas mencionados. En concreto, se propone una versión sencilla de cada problema y una versión más realista y, por tanto, compleja. Asimismo, en el trabajo se explican las ténicas de resolución más utilizadas en esta rama de la ingeniería que se han utilizado para resolver los problemas. El trabajo esta dividido en seis secciones. En esta primera sección se ha realizado una breve introducción al mismo. A continuación, en la sección 2 se realiza un análisis de la historia e hitos más importantes de la ingeniería e investigación operativa. En la siguiente sección se explicarán los tres tipos de problemas que se van a resolver y sus diferentes escenarios. En la sección 4 se verán las metodologías usadas para la resolución de los problemas y en la 5 se mostrarán los resultados obtenidos al aplicar estas metodologías a los escenarios propuestos. Finalmente, en la sección 6, se resumen los aspectos más relevantes del trabajo y se comentarán áreas de investigación y desarrollo futuras. L 3 2 HISTORIA 2.1. La ingeniería industrial La RAE define la ingeniería como “conjunto de conocimientos orientados a la invención y utilización de técnicas para el aprovechamiento de los recursos naturales o para la actividad industrial” [1]. La ingeniería forma parte de nuestras vidas desde la prehistoria, aunque no se estableció el conocimiento de esta disciplina hasta la Revolución Industrial (1760 - 1840). La primera escuela de ingeniería fue fundada en Francia, en 1795, durante el gobierno de Napoleón y desde entonces han surgido múltiples ramas enfocadas a las distintas necesidades del ser humano. Quizás una de las más generalistas sea la ingeniería industrial. Según el Instituto de Ingeniería Industrial (IIE), la ingeniería industrial es “lo concerniente con el diseño, mejoramiento e instalación de los sistemas integrados de personas, materiales, información, equipo y energía, soportado por el conocimiento especializado y la habilidad en las matemáticas, la física y las ciencias sociales que, junto con los principios y métodos de análisis de la ingeniería y el diseño, especifican, predicen y evalúan los resultados que serán obtenidos de cada uno de los sistemas de la industria” [2]. La práctica de la ingeniería industrial se ha caracterizado desde el principio por su adaptación, diversificación y formación multidisciplinar. Abarca numerosos campos de aplicación y tiene un papel importante en varios ámbitos. Las principales áreas de conocimiento de un ingeniero industrial son las de manufactura y producción, administrativa y financiera, de logística y distribución, de automatización y robótica, eléctrica, energética y análisis, desarrollo y gestión de proyectos. La historia de la ingeniería industrial está marcada por una serie de acontecimientos que impulsaron el avance y mejora de la sociedad. En la Ilustración 1 y en el resto de la sección se tratan algunos de los hitos más relevantes. Estos hitos han influido directamente en el desarrollo de la sociedad, impulsando el crecimiento económico y el avance tecnológico en numerosos ámbitos. Historia 4 Ilustración 1. Hitos de la ingeniería industria Fuente: Elaboración propia Aunque esta ingeniería ´oficialmente´ surgiera a raíz de la Primera Revolución Industrial, el verdadero origen de muchas de sus técnicas se remonta a la Revolución Agrícola, que tuvo lugar en el mismo período de tiempo que la Industrial. Ante la necesidad de optimizar la productividad de las actividades económicas rurales, se perfeccionaron los procedimientos de abonado y se reorganizó la explotación. Estas mejoras permitieron que se produjera al auge de la ingeniería en la Revolución Industrial, momento en el que se implementó el uso de máquinas, aumentando así la producción mecanizada y, por lo tanto, la productividad. Esto supuso un antes y un después en la sociedad y la economía. Después las aportaciones de la Ingeniería industrial no hicieron más que crecer, con inventos como el ferrocarril o la máquina de vapor [3]. No se puede hablar de la historia de la ingeniería industrial sin mencionar a sus principales precursores: Uno de los primeros fue Richard Arkwright, que inventó la versión mecánica del torno de hilar y fue el primero en establecer el método de control administrativo. En 1760, el arquitecto francés Jean Perronet estudió los tiempos para la fabricación de elementos para la construcción, que resultó clave para el desarrollo conceptual de lo que ahora conocemos como ingeniería industrial. La máquina de vapor (1774), uno de los inventos más significativos, se atribuye a James Watt y Matthew Boulton, y originó el gran cambio mencionado anteriormente. 1774: James Watt presentó la máquina de vapor 1883: Frederick Taylor empezó a estudiar el diseño del trabajo y la medición de actividades 1913: Henry Ford creó la primera línea de ensamblaje de coches de producción en masa 1917: Se constituyó la Sociedad de Ingenieros Industriales en EEUU 1950: Taiichi Ohno diseñó el sistema de producción de Toyota 5 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Más tarde, a finales del siglo XIX, llegó Frederick W. Taylor, considerado por muchos como el padre de la Dirección Científica y de la Ingeniería Industrial. Entre las contribuciones de Taylor a la ingeniería destacan el desarrollo del análisis del trabajo, el estudio de tiempos y movimientos y la estandarización de herramientas. En la misma época que Taylor, realizó también avances Henry Lawrence Gantt, que creó una gráfica para el control de actividades a través del tiempo. El diagrama de Gantt sigue siendo hoy en día una herramienta muy usada para la organización y gestión de proyectos. También cabe destacar al matrimonio formado por Frank y Lillian Gilbreth, que a principios del siglo XX contribuyeron al desarrollo del Estudio de Movimientos, logrando la optimización de numerosos procesos en ámbitos tanto industriales como del hogar [4]. A Henry Ford, fundador de la Ford Motor Company, le debemos la implementación del sistema de producción en línea, también conocido como fordismo. La idea era disminuir el tiempo de producción y el volumen de materia prima en transformación y aumentar la capacidad de producción a través de la especialización y la línea de montaje. Consiguió así la producción en masa y a precio asequible de automóviles y se convirtió en pocos años en líder de la industria automovilística. Gracias a estos avances la gente empezó a interesarse en los métodos de producción y se constituyó en 1917 la Sociedad de Ingenieros Industriales. [5] Una vez introducida la historia de la ingeniería industrial a nivel mundial, es interesante poner el foco en cómo avanzó esta disciplina en España. El 4 de septiembre de 1850 surge en España por un Real Decreto la carrera de ingeniero industrial. A finales de ese año se creó en Madrid el Real Instituto Industrial y Escuelas de Ampliación en Barcelona, Sevilla y Vergara. Sin embargo, debido a la situación socioeconómica de España durante esos años, hasta el siglo XX no empezó la expansión de esta ingeniería en nuestro país. Tras la contribución de los ingenieros industriales en el proceso de modernización de aquella época, se publicó el Decreto de 1935 de Alcalá Zamora que reconocía y regulaba las competencias profesionales del ingeniero industrial [6]. Desde la creación de la carrera han ido surgiendo nuevas especialidades y titulaciones, como, por ejemplo, la Titulación de Ingeniería de Organización. Ésta se origina en la especialidad en Organización Industrial de la carrera de Ingeniería Industrial, en el plan de estudios de 1964. Inicialmente la titulación era de segundo ciclo, lo que implicaba que solo se pudiera acceder a ella si se realizaba desde los primeros ciclos de las Ingenierías Superiores, Técnicas o Arquitectura. Sin embargo, debido al éxito que tuvo la especialidad, se decidió otorgarle una identidad, Historia 6 consiguiendo una mayor especialización. Hoy en día se accede mediante el grado especialista en Ingeniería en Organización Industrial [7]. Una de las escuelas en la que se imparte esta carrera es la Escuela Técnica Superior de Ingeniería (ETSi), creada en 1963 e inagurada oficialmente en abril de 1967. La primera promoción de ingenieros industriales contaba solo con las especialidades de Eléctrica, Mecánica y Química, pero a lo largo de los años éstas se fueron ampliando. El grado de Ingeniería en Organización Industrial se empezó a imparitr en 1994. [8] 2.2. La ingeniería de organización La ingeniería de organización industrial (IOI) se define como una rama de la ingeniería que se dedica a estudiar la conexión entre la tecnología, las personas y la organización en búsqueda de una mayor productividad [9]. Para hablar bien de la IOI hay que remontarse al siglo XVIII, cuando surgen los primeros pensadores que resaltaron la importancia de la división del trabajo y la especialización. Destacaron Adam Smith, Charles Babbage, David Ricardo o Matthew Boulton, entre otros. Adam Smith, famoso economista y filosofo británico, indicaba en su obra “La Riqueza de las Naciones” (1776) la importancia de una adecuada división del trabajo y especialización. Lo explicaba mediante el ejemplo de la fabricación de alfileres, mostrando cómo la división del trabajo era crucial para incrementar la productividad. En el siglo XIX David Ricardo, economista inglés, siguió estudiando las teorías de Smith y trató el tema de la especialización productiva en el comercio internacional entre países. También desarrolló el concepto de ventaja competitiva en el comercio, aunque, al igual que las observaciones de Adam Smith, estaban limitadas por falta de medios. [10] Pero el nacimiento de la disciplina se produjo a raíz de la Segunda Revolución Industrial (1870- 1914). Uno de los momentos clave de la ingeniería de organización lo marcó la publicación en 1903 del artículo Shop Management, de Frederick W. Taylor, ya mencionado entre los pioneros de la Ingeniería Industrial y considerado padre de la IOI. En esta publicación Taylor se centró en el estudio de tiempos y movimientos para medir el rendimiento y la productividad de los obreros. Se trataban también temas como el estudio de incentivos, estandarización de herramientas, métodos de estimación de costes, estudios de planificación, etc. En 1911 publica Principios de Administración Científica, donde se tratan aspectos tan importantes como la racionalización del trabajo, la formación rápida de operarios, el desgaste de éstos o la fabricación en serie. 7 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización En 1915, año en el que falleció Taylor, se creó la primera agrupación profesional en el campo de la Organización Industrial se empezaron a conocer sus ideas y las de sus seguidores como “Scientific Management”. A las aportaciones de Taylor se le sumó el sistema de producción en línea de Ford comentado anteriormente, que consistía en fabricar en series enormes el mismo modelo de coche (Ford T). Tuvo mucho éxito, pero después de un tiempo la demanda de este modelo cayó y General Motors, presidida por Alfred Sloan, pasó a ser el primer grupo empresarial del mundo en el sector del automóvil. Alfred Sloan también tiene un importante papel en la historia de la ingeniería de organización. Introdujo técnicas innovadoras de gestión (modelo de gestión descentralizada) y contabilidad (sistema de contabilidad). Por esto y otras importantes aportaciones, lleva su nombre la facultad de gestión empresarial del Instituto de Tecnología de Massachusetts (MIT), MIT Sloan School of Management de Boston [11]. Otros nombres relevantes son Charles Bedaux, Henry Gantt. Frank y Lillian Gilbreth, T.C. Fry y Walter Shewhart. A los dos últimos les debemos la introducción de la estadística como herramienta en el control de la calidad. La Segunda Guerra Mundial y la Posguerra también influyeron en el desarrollo de la IOI y la Investigación Operativa, de la que se hablará más adelante. Se empezaron a usar y ver la importancia de técnicas de logística, coordinación, planificación y optimización. Además, después de la Guerra, se dio un crecimiento económico y el mercado se volvió más competitivo, lo que propulsó el desarrollo de nuevas técnicas y metodologías para mejorar la logística y estrategias. [12] Más tarde, en 1950, nace en Japón gracias al ingeniero Taiichi Ohno el sistema de producción de Toyota, la filosofía del Lean Manufacturing, y aunque no tuviera demasiado éxito en aquel momento, acabó resultando clave para la mejora de sistemas de producción y otras industrias. Hoy en día sigue estando presente en numerosas e importantes empresas como Toyota, Nike o Intel [13]. A raíz de la popularidad de la rama, surgieron en todo el mundo titulaciones relacionadas con la ingeniería de organización. Como se mencionó anteriormente, en España existe la titulación de Ingeniería de Organización Industrial desde 1964 [12], pero en otros países, como Estados Unidos, se creó antes. Recibe un nombre distinto en cada país (Industrial Engineering en Estados Unidos, Managment Engenieering en Reino Unido, Ingenieur de Génie Industriel en Francia, etc… [14]) pero el objetivo es siempre el mismo: combinar la gestión y la organización con una formación técnica. Casos de estudio 14 3.1.1 Modelo matemático A continuación, se presenta el modelo matemático asociado al problema de la dieta. !!!!!!!𝑀𝑖𝑛. & 𝑐!𝑥! " !#$ !!!!!!!!𝑠.𝑎.!𝑏%&!"'≤! & 𝑎!%𝑥!!≤!𝑏%&()!;!!𝑗 = 1,…,𝑚! " !#$ !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!𝑥!' ≥0 Donde: - 𝑥! : cantidad del alimento i - 𝑐! : coste del alimento i - n: número de alimentos - m: número de nutrientes - aij: cantidad del nutriente j en el alimento i - bjmin: cantidad mínima del nutriente j - bjmax: cantidad máxima del nutriente j La función objetivo del modelo busca minimizar el coste total de la dieta, siendo el sumatorio de la multiplicación del coste unitario de cada alimento ( 𝑐𝑖 ) por la variable 𝑥𝑖 que representa la cantidad de dicho alimento que debe contener la dieta óptima. Este sumatorio tendrá n términos, uno correspondiente a cada alimento. A continuación, se establecen restricciones nutricionales para garantizar que la dieta cumpla con los requisitos establecidos. El modelo suele tener 2·m restricciones, es decir, m restricciones para asegurar que la dieta tiene al menos 𝑏𝑗𝑚𝑖𝑛 nutrientes, y otro conjunto de m restricciones para asegurar que no se supera la máxima cantidad permitida para cada nutriente. Estas restricciones se establecen mediante ecuaciones lineales en las que se multiplica cada variable 𝑥𝑖 por la cantidad del nutriente j en dicho alimento ( 𝑎𝑖𝑗 ) y se fuerza esta multiplicación a ser mayor o menor, dependiendo del caso, que un determinado valor nutricional. Aunque no sea el caso en este trabajo, también se pueden añadir restricciones adicionales, como preferencias dietéticas o limitaciones económicas. Por último, las variables del modelo son continuas y mayores que 0, representando la cantidad de cada alimento que debe contener la dieta. Es importante tener en cuenta que la formulación del modelo puede depender de los requisitos y datos de cada problema en particular. 15 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización 3.1.2 Particularización del modelo: escenario 1 En este escenario, se presenta un problema nutricional de bebés. El objetivo es demostrar la utilidad de la modelización matemática y de las técnicas propuestas para su resolución. Cabe destacar que los datos incluidos en el enunciado son datos reales, obtenidos a partir de la web de Hero Baby [27], marca de alimentos para bebés y niños pequeños. Es decir, tanto los costes como los nutrientes de cada alimento son valores reales. Para la obtención de estos datos se ha llevado a cabo una búsqueda minuciosa y comparación de información en varias fuentes. Enunciado: Unos padres están preparando la compra de potitos de bebés para su hijo de ocho meses. Después de un pequeño estudio de mercado han seleccionado tres tipos diferentes: de pollo y arroz (potito A), de frutas variadas (potito B) y de verdura y pescado (potito C). Los expertos recomiendan los siguientes valores nutricionales para bebés de 6-12 meses: 60-100 g/día de hidratos de carbono, 10-30 g/día de proteína (30 máximo), 5 g/día de fibra y 40-50 mg/día de vitamina C. El potito A cuesta 8,49 €/kg y contiene por cada 100 gramos 9,5 g de hidratos de carbono, 2,7 g de proteínas y 1 g de fibra. El potito B cuesta 6,36 €/kg y contiene por cada 100 gramos 15,5 g de hidratos de carbono, 1,1 g de proteínas, 1,4 g de fibra y 25 mg de vitamina C. El potito C cuesta 18,37 €/kg y contiene por cada 100 gramos 8,5 g de hidratos de carbono, 3 g de proteínas y 1 g de fibra. Determinar en kilos qué cantidad de cada potito al día (xA, xB y xc) deben darle al bebé para cumplir con los requisitos nutricionales al menor coste posible. En la tabla siguiente se encuentran los tres tipos de potitos con sus respectivos precios y valores nutricionales. Tabla 1. Resumen de los datos del problema de la dieta escenario 1 Precio (€/kg) Hidratos de carbono (g) Proteínas (g) Fibra (g) Vitamina C (mg) Potito A 8,49 9,5 2,7 1 0 Potito B 6,36 15,5 1,1 1,4 25 Potito C 18,37 8,5 3 1 0 Formulación matemática del problema: !!!!!!!!!!!!!𝑀𝑖𝑛.!!8,49𝑥.+6,36𝑥/+18,37𝑥0 !!!!!!!!!!!!!!!𝑠.𝑎.!!0,06 ≤0,095𝑥.+0,155𝑥/+0,085𝑥0≤0,1 !!!!!!!!!!!!!!!!!!!!!!!!!!0,01!≤0,027𝑥.+0,011𝑥/+0,03𝑥0≤0,03 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!0,05≤0,01𝑥.+0,014𝑥/+0,01𝑥0≤0,006 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!0,00004!≤0,00025𝑥/≤0,00005 Casos de estudio 16 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!𝑥.,𝑥/,𝑥0≥0 3.1.3 Particularización del modelo: escenario 2 Debido a la importancia e impacto que tuvo el problema original de la dieta de Stigler explicado al comienzo de esta sección, en este escenario se ha decidido emplear los mismos datos usados inicialmente por Stigler y poder comparar resultados. El problema de la dieta Stigler consiste en encontrar la combinación más económica de alimentos que cumpla los requerimientos nutricionales de una persona. Los datos utilizados son los usados en 1939 e incluyen la lista con los 77 alimentos, las cantidades de los distintos nutrientes de cada alimento, así como su precio y los requisitos nutricionales mínimos diarios. Al igual que para el escenario anterior, los datos utilizados en este escenario son datos reales tomados del artículo científico original donde se presentaba el problema. Restricciones del modelo: - Calorías (kcal) ≥ 3 - Proteína (g) ≥ 70 - Calcio (g) ≥ 0.8 - Hierro (mg) ≥ 12 - Vitamina A (KIU) ≥ 5 - Vitamina B1 (Tiamina) (mg) ≥ 1.8 - Vitamina B2 (Riboflavina) (mg) ≥ 2.7 - Vitamina B3 (Niacina) (mg) ≥ 18 - Vitamina C (Ácido ascórbico) (mg) ≥ 75 Cada alimento viene expresado en su respectiva unidad y el precio en centavos. Sin embargo, las cantidades de cada nutriente (calcio, proteínas, hierro…) vienen expresadas en gramos por dólar, por lo que habrá que realizar una conversión para que estén en la misma unidad que cada alimento. Es decir, si la unidad del ‘alimento 1’ son 10 libras, habrá que dividir el precio entre 10 para saber cuánto cuesta una libra y posteriormente habrá que relacionar este precio con los gramos por 1 $ para obtener las cantidades de cada nutriente por libra de alimento. A continuación, se muestra en la Tabla 2 parte de los datos [28]. No obstante, los datos completos se encuentran en la Tabla 17 del Anexo 1. 17 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Tabla 2. Datos del problema de la dieta escenario 2 Formulación matemática del problema: !!!!!!!!!!!!!!!!!!!!𝑀𝑖𝑛.!!3,6𝑥$+14,1𝑥1+0,86𝑥2+⋯+0,57𝑥34!+!0,756𝑥35 +20,5𝑥33 𝑠.𝑎.1,6𝑥$+1,636𝑥1+0,1𝑥2+⋯+0,08𝑥34!+!0,07𝑥35 +1,31𝑥33 ≥3 !!!!!50,8𝑥$+58,94𝑥1+3,26𝑥2+⋯+0𝑥34!+!0𝑥35 +2,25𝑥33 ≥70 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!0,072𝑥$+0,097𝑥1+0,124𝑥2+⋯+0,003𝑥34!+!0,078𝑥35 +0,082𝑥33 ≥ 0,8 !!!!!!!!!!!!!!!!13,14𝑥$+7,61𝑥1+1,51𝑥2+⋯+0,42𝑥34!+!1,84𝑥35 +1,43𝑥33 ≥12 0𝑥$+0𝑥1+0𝑥2+⋯+0𝑥34!+!0𝑥35 +0,041𝑥33 ≥ 5 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1,99𝑥$+0,45𝑥1+0,12𝑥2+⋯+0𝑥34!+!0,014𝑥35 +0,041𝑥33 ≥ 1,8 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1,2𝑥$+0,27𝑥1+0,076𝑥2+⋯+0𝑥34!+!0,057𝑥35 +0,082𝑥33 ≥ 2,7 !!!!!!!!!!!!!!!!15,88𝑥$+9,59𝑥1+0,99𝑥2+⋯+0,029𝑥34!+!1,1𝑥35 +0,61𝑥33 ≥18 0𝑥$+0𝑥1+0𝑥2+⋯+0𝑥34!+!0𝑥35 +0𝑥33 ≥ 75 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!𝑥$,𝑥1,𝑥2,…,𝑥34,𝑥35,𝑥33 ≥0 3.2 Problema del viajante El problema del viajante – TSP (Travelling Salesman Problem) está presente en nuestra sociedad desde el siglo XIX gracias al matemático irlandés William Rowan Hamilton y al británico Thomas Kirkman. Sin embargo, no fue hasta los años 1930s que Karl Menger y, más tarde, Hassler Whitney y Merrill Flood lo formularon matemáticamente y comenzaron a estudiarlo en profundidad. A partir de entonces, y debido a la complejidad del problema, el interés por él no hizo más que crecer. [29] Es considerado como NP-complejo y existen varias heurísticas y algoritmos que buscan encontrar la solución óptima de este problema. Puede ser considerado como un problema de grafos ponderados no dirigido, donde las ciudades son los vértices y los caminos con sus respectivos pesos son las aristas y la distancia o coste entre vértices. El problema consiste en, dado un número de nodos y los respectivos costes para ir de uno a otro, encontrar el camino más barato o corto para visitar todos los nodos y volver al de inicio. [30] Casos de estudio 18 Las principales aplicaciones del problema actualmente son planificación y logística, aunque también se ha utilizado en otro tipo de ámbitos como la cristalografía de rayos-X, la secuenciación de ADN o el taladro de placas de circuitos. [31] 3.2.1 Modelo matemático A continuación, se presenta el modelo matemático asociado al problema del viajante [32]. ! !!!!!!!𝑀𝑖𝑛.!! & & 𝑐!%𝑥!% " %#$ " !#$ ! !!!!!!!!𝑠.𝑎.!! & 𝑥!% =1!;!!𝑗 = 1,…,𝑛 " !#$'!6% ! !!!!!!!!!!!!!!!!!! & 𝑥!% =1!;!!𝑖 = 1,…,𝑛 " %#$'!6% !!!!!!!!!!!!!!!!!! & & 𝑥!% ≤! | 𝑆 | −1,!!!!!!!!!∀𝑆 =1,2,…,𝑛 %∈8,%6!!∈8 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!𝑥!%'∈{0,1} Donde: - xij: nodo que va del arco i al j Variable binaria, toma valor 1 si la arista está en la solución y 0 si no - cij: coste o distancia al ir del nodo i al j - n: número de nodos - S: subconjunto de {1, 2, …, n} Mediante la función objetivo del modelo matemático del TSP se quiere minimizar el coste o la distancia de ir de un nodo a otro. Se calcula sumando la multiplicación de las distancias o costes entre los nodos visitados ( 𝑐!% ) por las variables que indican si se va del nodo i al j ( 𝑥!% ). Los sumatorios tendrán tantos términos como nodos. Las dos primeras restricciones indican que hay que visitar y partir de cada nodo exactamente una vez. Además, es necesario añadir la tercera restricción para que no se formen ciclos más pequeños dentro del recorrido y garantizar que la solución es un ciclo hamiltoniano, es decir, una ruta cerrada que visita cada nodo una vez y regresa al inicial. Por último, las variables del modelo son binarias: solo pueden tomar el valor 0 o el 1. Este tipo de varibles se utiliza para problemas de toma de decisiones en los que las dos posibles opciones son mutuamnete excluyentes. En este problema 𝑥!% toma valor 1 si la ruta incluye el camino del nodo i al j, y 0 en caso contrario. 19 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización 3.2.2 Particularización del modelo: escenario 1 En el primer escenario se pretende desarrollar un ejemplo sencillo de la aplicación de este problema. En concreto se presenta el problema de diseño de una gira para un cantante que tiene que pasar por 10 ciudades. Para ello se implementará un algoritmo genético en Python, cuyo funcionamiento se explicará más adelante. El objetivo es comprender el problema del viajante y analizar la eficiencia de los modelos de investigación operativa y el algoritmo genético para resolver este tipo de problemas. Enunciado: Un cantante está planeando una pequeña gira por la Península Ibérica. Su idea es dar conciertos en 10 de las principales ciudades del país recorriendo la menor distancia posible. Sabiendo que tiene que empezar y acabar en la misma ciudad, ¿cuál sería la mejor ruta? En la Tabla 3 se muestran las distancias medidas en kilómetros (km) entre las 10 ciudades en cuestión. Estas distancias corresponden a los costes del modelo. Por simplicidad se han medido en línea recta, aunque en la realidad debería haberse tenido en cuenta la distancia real por carretera que existe entre las mismas. Los datos se han obtenido mediante la herramienta de Google Maps que permite medir la distancia entre dos puntos. Para rellenar la matriz de distancias se ha medido la distancia de cada ciudad respecto a todas las demás. Tabla 3. Matriz de distancias (km) 10 ciduades Cij Barcelona Bilbao La Coruña Lisboa Madrid Murcia Salamanca Sevilla Valencia Zaragoza Barcelona 0 470 895 1005 506 470 655 822 298 256 Bilbao 470 0 425 720 321 606 334 702 470 248 La Coruña 895 425 0 517 506 856 347 694 793 645 Lisboa 1005 720 517 0 499 702 373 308 760 770 Madrid 506 321 506 499 0 352 175 392 305 274 Murcia 470 606 856 702 352 0 509 436 180 405 Salamanca 655 334 347 373 175 509 0 399 478 405 Sevilla 822 702 694 308 392 436 399 0 545 647 Valencia 298 470 793 760 305 180 478 545 0 243 Zaragoza 256 248 645 770 274 405 405 647 243 0 3.2.3 Particularización del modelo: escenario 2 En este escenario se amplia la lista de ciudades a visitar con respecto al escenario anterior, el cantante pasará de recorrer 10 ciudades a visitar 30. El objetivo es, una vez comprendido el escenario 1, aumentar la complejidad del modelo y hacerlo más realista. La metodología empleada Casos de estudio 20 para resolver este escenario es la misma que en el escenario anterior, el algoritmo genético. Al ser el problema más complejo, se valorará más la utilidad del algoritmo y las ventajas que proporciona, como la precisión y velocidad de resolución. Enunciado: Viendo el éxito de su álbum, el cantante ha decidido ampliar la gira y pasar por varias ciudades más de la Península y Francia, sumando un total de 30 ciudades. Su objetivo sigue siendo empezar y acabar en la misma ciudad minimizando la distancia recorrida. ¿Qué ruta debe seguir en este caso? En la Tabla 4 se muestran las distancias entre algunas de las 30 ciudades. Por falta de espacio, la tabla completa se encuentra en las distintas tablas del Anexo 2 . Al igual que en el escenario anterior, las distancias entre ciudades son en línea recta, para que el problema fuese aún más realista deberían obtenerse las distancias realeas por carretera. En este escenario las distancias también se han obtenido mediante la herramienta de Google Maps que permite medir la distancia entre dos puntos. Tabla 4. Parte de la matriz de distancias (km) 30 ciudades Cij Barcelona Bilbao Cáceres Ciudad Real Coímbra Córdoba Évora Faro La Coruña … Barcelona 0 470 752 580 892 710 914 995 895 Bilbao 470 0 506 485 562 617 668 813 425 Cáceres 752 506 0 222 185 225 166 304 454 Ciudad Real 580 485 222 0 400 702 373 308 760 Coímbra 892 562 185 400 0 400 185 355 352 Córdoba 710 617 225 702 400 0 284 295 681 Évora 914 668 166 373 185 284 0 172 535 Faro 995 813 304 308 355 295 172 0 706 La Coruña 895 425 454 760 352 681 535 706 0 3.3 Problema de la mochila El Problema de la Mochila - KP (Knapsack Problem) es un problema de Optimización Combinatoria y pertenece a la lista de los 21 problemas NP-completos que publicó Richard Karp en 1972. Consiste en simular llenar una mochila de una determinada capacidad con objetos de distinto valor y peso. Este problema puede aplicarse a varios procesos de toma de decisiones reales, como, por ejemplo, asignación de espacio (ej. carga del avión), generación de claves, selección de proyectos o inversiones, etc. 21 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Aunque aparentemente pueda parecer un problema sencillo, realmente es bastante complejo a la hora de resolverlo. Uno de los métodos más utilizados para resolver problemas de gran tamaño son las metaheurísticas y, en concreto, el algoritmo genético, el cual se explicará en la sección 4. 3.3.1 Modelo matemático A continuación, se presenta el modelo matemático asociado al problema de la mochila [33]. 𝑀𝑎𝑥. ∑ 𝑏!𝑥! " !#$ !!!!!!!!!𝑠.𝑎. ∑ 𝑤!𝑥! " !#$ !≤𝑐 !!!!!!!!!!!!!!!!!!!!!!!!!!𝑥!' ∈{0,1} Donde: - xi: variable de decisión que toma el valor de 1 si se decide meter el elemento i en la mochila, y 0 e.c.c - 𝑏! : valor del elemento i - n: número de elementos - 𝑤! : peso del elemento i - c: capacidad de la mochila La función objetivo del modelo matemático del problema de la mochila busca maximizar el valor de los elementos que se meten en la mochila. Se calcula sumando la multiplicación del valor de cada elemento ( 𝑏𝑖 ) por la variable 𝑥𝑖 que representa si ese elemento se incluye o no en la mochila. Este sumatorio tendrá n términos, uno correspondiente a cada elemento. La primera restricción indica que el peso total de los elementos incluidos en la mochila no puede superar la capacidad de ésta. Esto se expresa mediante el sumatorio de la multiplicación del peso de cada elemento ( 𝑤𝑖 ) por la variable 𝑥𝑖 . Al igual que en la función objetivo, el sumatorio tendrá tantos términos como elementos. En cuanto a las variables de decisión, el tipo depende del problema que se vaya a tratar. En este trabajo serán binarias, ya que en los casos propuestos solo habrá dos opciones: meter el elemento entero en la mochila, en cuyo caso la variable de decisión 𝑥𝑖 valdrá 1; o no meterlo, tomando 𝑥𝑖 el valor 0. 3.3.2 Particularización del modelo: escenario 1 En este escenario se presenta un sencillo ejemplo del problema de la mochila, en el que un repartidor tiene que decidir qué elementos incluir primero para repartirlos. Es un caso con pocos Casos de estudio 22 elementos que podría intentar resolverse sin técnicas avanzadas; sin embargo, al igual que en el caso del problema del viajante, se implementará un algoritmo genético en Python para su resolución. La aplicación del algoritmo servirá para encontrar rápida y eficientemente la solución óptima y así comparar esta solución con la obtenida mediante procedimientos tradicionales. El objetivo principal de este escenario es entender bien en qué consiste el problema y cuáles son los objetivos para luego poder abordar casos de mayor envergadura. Por ello se ha elegido este ejemplo, ya que es uno de los más típicos del problema de la mochila y sirve como introducción al tema. Enunciado: Un repartidor de comidas caseras a domicilio dispone de una mochila de 30 litros de capacidad para hacer la entrega de pedidos. Cada vez que sale de la tienda debe decidir, en función del tamaño y la hora de entrega al cliente, qué pedidos meter en la mochila. Los pedidos que tengan que ser entregados en los próximos 30 minutos tendrán una urgencia de 5, los que tengan que estar en 1 hora tendrán una urgencia de 4, en 2 horas urgencia 3, en 3 horas tendrán urgencia 2 y los que puedan entregarse a lo largo del día, urgencia 1. Al realizar el primer viaje, ¿qué pedidos debe meter primero en la mochila para asegurarse que cumple con los plazos establecidos? La lista de pedidos es la siguiente: Tabla 5. Resumen de los datos del escenario 1 del KP Urgencia Volumen (litros) Producto A 5 15 Producto B 2 12 Producto C 2 5 Producto D 5 2 Producto E 1 7 Formulación matemática: 𝑀𝑎𝑥.!!5𝑥.+2𝑥/+2𝑥0+5𝑥:+𝑥; !!!!!!!!!!𝑠.𝑎.15𝑥.+12𝑥/+5𝑥0+2𝑥:+7𝑥;≤30 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!𝑥.,𝑥/,𝑥0,𝑥:,𝑥;' ∈{0,1} 3.3.3 Particularización del modelo: escenario 2 En este escenario se presenta un caso similar al anterior pero más complejo y realista. Consiste en decidir qué productos de un almacén entregar primero para maximizar beneficios sin superar la capacidad del camión en el que se transportan. Aunque por claridad no se vaya a realizar en este 23 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización caso, una forma de hacer este problema más realista y útil en el ámbito de la logísitca sería penalizar retrasos en la entrega de los productos mediante nuevas restricciones y añadiendo costes en la función objetivo. Nuevamente se resolverá implementando el algoritmo genético en Python. Al haber muchos más productos que en el escenario anterior, los cálculos manuales se complican significativamente, por lo que se verá aún más la importancia de usar técnicas avanzadas que faciliten la búsqueda de la solución óptima. Los datos han sido obtenidos en función de los precios y pesos medios de los distintos productos. Enunciado: El gerente de una pequeña empresa de logística, que cuenta con un camión con una capacidad máxima de 1500 kg, debe decir qué productos del almacén transportar para maximizar el valor total sin superar la capacidad. El almacén está lleno de electrodomésticos y muebles, cada uno con su respectivo peso y precio. El precio indica el beneficio que se obtiene por cada producto que se entrega. Aunque eventualmente se vayan a transportar todos los productos del almacén, dado que la empresa está empezando y necesita generar ingresos para cubrir gastos operativos y poder invertir en más recursos, ¿qué productos debe meter en el camión para maximizar las ganancias y asegurar que el transporte sea eficiente y rentable? Los distintos productos con sus respectivos datos se encuentran en la siguiente tabla: Tabla 6. Resumen de los datos del escenario 2 del KP Valor (€) Peso (kg) Nombre Producto A 800 150 Lavadora Producto B 1500 300 Frigorífico Producto C 150 30 Microondas Producto D 1000 200 Secadora Producto E 100 10 Aspiradora Producto F 900 180 Aire acondicionado Producto G 1000 200 Televisor Producto H 1000 400 Sofá Producto I 1200 250 Mesa de comedor Producto J 500 120 Estantería Producto K 400 180 Escritorio Producto L 150 40 Sillón Producto M 800 120 Cortadora de césped Producto N 700 80 Equipo de sonido Metodología 30 30 Ilustración 8. Planteamiento problema de la dieta en Excel Fuente: Elaboración propia Programamos el problema: se establece la celda objetivo y se señala si se quiere maximizar o minimizar. También se ponen las celdas que contienen las variables que vamos a ajustar y otras restricciones necesarias: Ilustración 9. Programación del problema en Solver Fuente: Elaboración propia Se pueden agregar tantas restricciones como hagan falta, pero el número máximo de celdas de variables es 200. El Solver permite usar otros métodos además del simplex; por ello, es importante elegir el método de resolución, en este caso Simplex LP. Fuente: Elaboración propia Ilustración 10. Método resolución Solver 31 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Finalmente se pulsa ‘Resolver’ y, en caso de haberla, Solver nos proporcionará la solución óptima con el valor de cada variable y la función objetivo. La información de esta sección se basa en el contenido de la web del Soporte técnico de Microsoft 365 [36]. 4.2.2 Librería Gurobi La librería Gurobi es un software de optimización matemática que, al igual que Solver, sirve para resolver diversos problemas de programación. Una de las principales diferencias entre ambas herramientas es que Gurobi es mucho rápida y eficiente, pudiendo resolver problemas muy complejos en muy poco tiempo. Por ello, usaremos esta librería para resolver el segundo escenario del problema de la dieta, ya que, al tener tantas variables, el Solver de Excel es menos eficiente debido a sus limitaciones. Gurobi incluye implementaciones de alto rendimiento del método simplex y el dual simplex, y un solucionador de barrera paralela [37]. Para el caso de estudio del problema de la dieta de Stigler se usará la librería Gurobi en el leguaje de programación de Python. Para ello, una vez instalado Gurobi, habrá que importar la interfaz Gurobipy, que nos permitirá resolver complejos problemas de optimización. Lo siguiente será definir los parámetros y datos del problema, en este caso, lista de alimentos con sus respectivos precios y valores nutricionales, y los requisitos de nutrientes mínimos. Después se crea el modelo mediante m=gp.model (Ilustración 11). Cuando se tenga el modelo creado se añaden variables (m.addVar) y, para mayor claridad de los resultados, se les asignan los nombres de los alimentos a los índices correspondientes de las variables de decisión (Ilustración 12). Ilustración 11. Línea del código para la creación del modelo Ilustración 12. Líneas del código para la creación de variables La parte clave del código es el establecimiento de la función objetivo y de las restricciones. Como se ve en la Ilustración 13, la función objetivo se establece así: m.setObjective( objetivo, Metodología 32 32 gp.GRB.MINIMIZE). En m.setObjective por ‘objetivo’ se entiende la suma de todos los alimentos multiplicados por sus precios. Ilustración 13. Línea del código para establecer la función objetivo Para las restricciones se usa m.addConstr y se establece que la suma de todos los alimentos multiplicados por los distintos valores nutricionales sea mayor que los mínimos fijados antes (Ilustración 14). Ilustración 14. Líneas del código para establecer las restricciones Finalmente se resuelve el modelo mediante m.optimize y se imprime la solución. Ilustración 15. Líneas del código para resolver el modelo La información de esta sección se basa en el contenido de la web GUROBI OPTIMIZATION [38]. 4.3 Metaheurísticas El término ‘metaheurística’ fue introducido por primera vez en el artículo semanal sobre búsqueda tabú de Fred Glover en 1986 y se obtiene de combinar el prefijo ‘meta’, que significa ‘a un nivel superior’, y la palabra griega ‘heurística’, encontrar. En investigación operativa, un método heurístico es aquél que, aunque no garantice la optimalidad, proporciona una solución de alta calidad con un coste computacional razonable. Por lo tanto, las metaheurísticas se pueden definir como métodos aproximados diseñados para mejorar problemas de optimización combinatoria en los que los métodos heurísticos no son efectivos. El objetivo es encontrar el óptimo de un problema complejo en el menor tiempo posible, lo que supone un gran avance. [39] 33 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Es una combinación de varias áreas distintas: las matemáticas aplicadas, la ingeniería informática, ingeniería industrial y las disciplinas empresariales, lo que supone una gran ayuda para la toma de decisiones. Por ello, es una disciplina que se ha convertido en vital para las grandes empresas y otros tipos de sectores como la medicina. [40] A lo largo de los años, se han desarrollado muchas metaheurísticas según el tipo de problema a resolver. En este caso, para el problema del viajante y el de la mochila, se ha decidido utilizar algoritmos genéticos. Como hemos dicho, no se garantiza siempre la solución óptima, algunos de los motivos son los siguientes: - Convergencia hacia un óptimo local - Configuración inicial inadecuada: la efectividad y rendimiento del algoritmo dependen de la configuración inicial de parámetros y población - Limitaciones computacionales 4.3.1 Algoritmo Genético Los principios básicos de los algoritmos genéticos fueron desarrollados por John H. Holland en 1975 y están fundamentados en las Leyes de la Vida Natural descritas por Charles Darwin [41]. El algoritmo genético es un método para resolver problemas de búsqueda y optimización basados en la mecánica de la selección natural, la evolución y la genética. El método elige las mejores soluciones a medida que se desarrolla la población y las combina para producir nuevas soluciones que se evalúan y compiten con la población inicial. Aunque el algoritmo cambia según la aplicación, hay una estructura común para todos: 1. Crear una población inicial de x individuos. En el algoritmo genético, individuo hace referencia a una posible solución y la población es un conjunto de individuos, es decir, un conjunto de posibles soluciones. Esta población irá evolucionando mediante distintos procesos de selección para intentar encontrar la solución óptima. Se establece una población inicial y a partir de ésta ir realizando cambios y mejoras. Esta población inicial suele generarse aleatoriamente; sin embargo, en algunas ocasiones puede ser conveniente generarla siguiendo algún criterio específico. 2. Calcular la aptitud (fitness) de cada individuo. La función aptitud es la que evalúa la idoneidad de una solución y es la encargada de guiar el proceso de selección en función de los resultados que se vayan obteniendo. Está estrechamente Metodología 34 34 relacionada con la función objetivo por lo que la aptitud será muy diferente en función del tipo de problema y lo que se quiera optimizar en cada caso. 3. Se seleccionan los mejores individuos Para empezar a buscar la solución óptima se seleccionan unos primeros individuos (padres) siguiendo distintos métodos de selección, como, por ejemplo, la selección por ruleta, por torneo, por ranking o elitista. Todas estas técnicas evalúan y comparan individuos de la población inicial para identificar a los mejores y ordenar según la aptitud para empezar el proceso de cruce, mutación, etc. 4. Se cruzan los individuos seleccionados (fase de reproducción) El cruce es una función cuya finalidad es combinar genes de los padres para que los descendientes hereden las características beneficiosas de los dos padres, es decir, combinar dos soluciones distintas y crear una nueva a partir de éstas. Hay distintos tipos de cruce: cruce en un punto, cruce en dos puntos, aleatorio, etc. Una vez más, la selección de un tipo u otro depende del caso en concreto. Cruce en un punto: En la Ilustración 16 se presenta un ejemplo de cruce en un punto. Este tipo de cruce consiste en seleccionar un punto, normalmente al azar, y a partir de ahí hacer el intercambio de genes. Como puede observarse, a partir de dos soluciones iniciales llamadas de padres (parte izquierda de la ilustración), se generan dos soluciones nuevas como combinación de las anteriores, también llamadas de hijos (parte derecha de la ilustración). Ilustración 16. Cruce en un punto Fuente: Elaboración propia Cruce en dos puntos: Este caso es similar al anterior, pero en lugar de realizarse el cruce en un punto se realiza en dos, normalmente aleatorios. Como se puede observar en la Ilustración 17, se seleccionan dos puntos, y se realiza el intercambio de genes en los dos, obteniendo nuevamente dos soluciones nuevas (hijos) como combinación de las anteriores (padres). 1 1 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 35 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Ilustración 17. Cruce en dos puntos 1 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 Fuente: Elaboración propia Cruce aleatorio: El proceso de intercamabio de genes vuelve a ser muy parecido a los casos anteriores. En este caso la diferencia es que no hay un número determinado de puntos de cruces, sino que es aleatorio. Sin embargo, como se ve en la Ilustración 18, el resultado es el mismo: dos hijos (parte derecha de la ilustración) a partir de unos padres (parte izquierda de la ilustración) que han intercambiado sus genes. Ilustración 18. Cruce aleatorio 1 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 Fuente: Elaboración propia 5. Se introducen pequeñas mutaciones en algunos individuos aleatoriamente. Mediante la mutación, que se realiza en función a una determinada tasa, se introducen cambios aleatorios en los individuos para evitar que el algoritmo quede atrapado en óptimos locales y poder explorar un rango más amplio y variado de soluciones. Consiste en seleccionar aleatoriamente puntos de un individuo, generalmente dos puntos, e intercambiar los genes de posición. En el caso de la Ilustración 19 se observa cómo el gen de la posición 3, que vale 0, pasa a la posición 6, y viceversa. Por lo que en la solución nueva (parte inferior de la ilustración) el gen de la posición 3 valdrá 1 y el de la posición 6 será 0. Ilustración 19. Mutación 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 Fuente: Elaboración propia La información de esta sección se basa en el contenido de la web cienciadedatos.net [42]. 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 Metodología 36 36 En este algoritmo también son muy importantes los parámetros y el criterio de selección de éstos. Los más comunes y los que se han utilizado en este trabajo son el tamaño de la población, el número de generaciones y tasa de mutación. El tamaño de población es el tamaño de individuos en cada generación de la población y es de los parámetros más importantes, ya que tiene un gran impacto en la diversidad y tiempo computacional. Un tamaño de la pobación grande implica una exploración más exhaustiva del espacio de posibles soluciones, pero a costa de un mayor tiempo de ejecución. Mientras que una población pequeña proporciona soluciones menos diversas pero mayor eficiencia computacional. El número de generaciones es el número de veces que se ejecuta el algoritmo hasta parar. Al igual que ocurre con el tamaño de población, con un número grande de generaciones se consigue mayor convergencia hacia soluciones óptimas, pero también mayor tiempo de ejecución, por lo que hay que encontrar el equilibrio, en función de la complejidad del problema, entre calidad de soluciones y coste computacional. Respecto a la tasa de mutación, determina la probabilidad de que se mute algún gen de un individuo. Suele ser bastante pequeña, ya que esto suele ser suficiente para garantizar la diversidad genética adecuada, aunque depende del tipo de problema que se esté tratando. La tasa de mutación es muy útil para evitar que el algritmo se quede atrapado en un óptimo local, que es una solución mejor que sus vecinas, pero no necesariamente la mejor. Cabe destacar que la elección de estos parámetros puede llegar a ser algo subjetiva y depende de muchos factores, por lo que es conveniente dar distintos valores que ayuden a evaluar y comparar distintas regiones del espacio de búsqueda para determinar cuáles funcionan mejor en cada situación. En este trabajo se realizarán varias ejecuciones con distintas combinaciones de los parámetros para encontrar los valores que ayuden a encontrar la solución óptima. En resumen, es una técnica de programación que imita a la evolución biológica para resolver problemas de optimización. Se parte de una población inicial consituida por posibles soluciones. Éstas se evalúan por la función de aptitud. Las mejores soluciones se reproducen y se las hace evolucionar por procesos similares a los que han ido experimentando los seres vivos a lo largo de la historia: selección, cruce y mutación. Tras realizar un determinado número de iteraciones, se selecciona la mejor solución encontrada a lo largo de la ejecución del algoritmo. En la Ilustración 20 se presenta un esquema general con los distintos pasos del algoritmo comentados en esta sección. 37 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Ilustración 20. Esquema con los pasos del algoritmo genético Fuente: Elaboración propia 38 5 RESULTADOS n este apartado se expondrán los resultados obtenidos de los problemas planteados en el punto 3 y se verá si se han cumplido los objetivos deseados. Como se explicó en la metodología, cada problema ha sido resuelto de una forma distinta y utilizando diferentes softwares. 5.1 Problema de la dieta 5.1.1 Escenario 1 Como se ha explicado en el apartado de la metodología, el primer escenario del problema de la dieta se ha resuelto con Solver de Excel ya que, al tener pocas variables y restricciones, Solver garantiza que se encontrará la solución óptima. Cada restricción se ha dividido en dos, una para establecer el mínimo y otra para establecer el máximo de cada nutriente. A continuación, se muestra la tabla de Excel con las restricciones y los valores de las variables y función objetivo generada por Solver: Tabla 7. Resultados del escenario 1 del problema de la dieta x1 x2 x3 0,305 0,2 0 Valor Signo R1 0,095 0,155 0,085 0,06 ≥ 0,06 R2 0,095 0,155 0,085 0,06 ≤ 0,1 R3 0,027 0,011 0,03 0,01044 ≥ 0,01 R4 0,027 0,011 0,03 0,01044 ≤ 0,03 R5 0,01 0,014 0,01 0,005852 ≥ 0,005 R6 0,01 0,014 0,01 0,00585 ≤ 0,006 R7 0 0,00025 0 0,00005 ≥ 0,00004 R8 0 0,00025 0 0,00005 ≤ 0,00005 Z 8,49 6,36 18,37 3,86368 La solución óptima proporcionada nos dice que se le deberá dar al bebé diariamente 0,31kg del potito A y 0,2kg del potito B. No será necesario darle nada del potito C, ya que con los dos primeros se cumplen los requisitos nutricionales a menor precio. Si interpretáramos el resultado en un horizonte temporal mayor, por ejemplo, de una semana, la solución óptima se corresponde a darle al bebé algo más de 2 potitos A y algo más de 1 potito B. E 39 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización En la última fila de la tabla se ve la suma de estas variables multiplicada cada una por su respectivo precio, lo que da como resultado el valor de la función objetivo, que es lo que habrá que gastarse al día para comprar la cantidad necesaria de potitos. Este coste mínimo es de 3,86 € al día. Lo que supondría un coste de 27 € semanales. También se puede comprobar en la solución que se cumplen las restricciones. Las únicas restricciones que se cumplen con signo de igualdad son la primera (correspondiente al mínimo de hidratos de carbono) y la última (correspondiente al máximo de vitamina C), mientras que en el resto de las restricciones aparecen holguras. Volviendo a las ocho restricciones originales tenemos: Hidratos de carbono: 0,06!≤0,06!≤ 0,1 Proteínas: 0,01!≤0,01044211!≤ 0,03 Fibra: 0,005!≤0,00585263 ≤0,006 Vitamina C: 0,00004!≤0,00005!≤ 0,00005 5.1.2 Escenario 2 Mediante la aplicación del método simplex, esta vez con la librería Gurobi, se han identificado las cantidades necesarias de cada alimento que cumplan con los requisitos y a un coste mínimo. La selección de alimentos que proporciona la dieta óptima a menor precio es la siguiente: harina de trigo (x1), hígado (x30), col (x46), espinacas (x52) y alubias blancas (x69). En la siguiente tabla se muestran los resultados obtenidos, donde se ven las cantidades diarias requeridas de cada alimento seleccionado y el precio total diario en centavos. Además, a la derecha de la tabla se puede comprobar el cumplimiento de los distintos requerimientos nutricionales. Para mejor visualización se han omitido de la tabla los alimentos no elegidos. Tabla 8. Resultados del escenario 2 del problema de la dieta, valores diarios x1 x30 x46 x52 x69 0,81997 0,00706 0,30309 0,06182 1,03438 Valor Signo Calorías 1,6092 0,5896 0,0962 0,0891 1,5871 3 ≥ 3 Proteína 50,796 89,244 4,625 8,586 99,769 147,4135 ≥ 70 Calcio 0,072 0,0536 0,148 0 0,6726 0,8 ≥ 0,8 Hierro 13,14 37,252 1,332 11,178 46,728 60,4669 ≥ 12 Vitamina A 0 45,3456 0,2664 74,3904 0 5 ≥ 5 Vitamina B1 1,9944 1,7152 0,333 0,4617 2,2656 4,1204 ≥ 1,8 Vitamina B2 1,1988 13,6144 0,1665 1,1178 1,4514 2,7 ≥ 2,7 Vitamina B3 15,876 84,688 0,962 2,673 12,803 27,316 ≥ 18 Vitamina C 0 140,7 198,653 223,155 0 75 ≥ 75 Resultados 46 46 Ilustración 23. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 3158 km La mejor ruta encontrada es: ['Madrid', 'Murcia', 'Valencia', 'Barcelona', 'Zaragoza', 'Bilbao', 'La Coruña', 'Lisboa', 'Sevilla', 'Salamanca', 'Madrid'] Con una distancia de: 3158 km Esta solución se obtiene después de 500 iteraciones del algoritmo. En la Ilustración 23 se observa cómo la función objetivo va mejorando a medida que avanzan las iteraciones hasta estabilizarse alrededor de la iteración 120. Para asegurarnos del correcto funcionamiento del algoritmo, este se ha implementado varias veces. Por ejemplo, en la Ilustración 24 se muestra la evolución de la mejor solución encontrada tras 500 iteraciones. En este caso la función objetivo se estabiliza aproximadamente en la iteración 370. Aquí se ve la importancia de establecer un número de generaciones alto, ya que, aunque la mayoría de las veces la solución se estabiliza pronto, habrá ejecuciones, como esta, en las que tarde más la función objetivo en estabilizarse. Además, puede comprobarse que en este caso se obtiene una solución final peor que la anterior. Esto es un problema común cuando utilizamos metaheurísticas, ya que, como se comentó antes, estos métodos no aseguran alcanzar el óptimo global del problema y por ello es importante realizar varias ejecuciones. 47 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Ilustración 24. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 3179 km La mejor ruta encontrada es: ['Murcia', 'Valencia', 'Barcelona', 'Zaragoza', 'Bilbao', 'La Coruña', 'Salamanca', 'Lisboa', 'Sevilla', 'Madrid', 'Murcia'] Con una distancia de: 3179 km Tras implementar el algoritmo diez veces, la mejor solución encontrada es la que corresponde a una ruta de 3086 km. En la Tabla 13 se observa la media de la mejor solución encontrada en estas diez ejecuciones, así como la desviación y el mejor y peor resultado. Los valores mostrados en esta tabla demuestran que el algoritmo proporciona siempre soluciones relativamente cercanas a la óptima. En la Ilustración 25 se ve la evolución de la solución hasta llegar a la mejor solución encontrada en las 500 generaciones. Tabla 13. Resultado de las 10 ejecuciones del escenario 1 del TSP Media Desviación Mejor resultado Peor resultado 3148,7 46,68 3086 3218 Resultados 48 48 Ilustración 25. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 3086 km La mejor ruta encontrada es: ['Sevilla', 'Lisboa', 'La Coruña', 'Salamanca', 'Madrid', 'Bilbao', 'Zaragoza', 'Barcelona', 'Valencia', 'Murcia', 'Sevilla'] Con una distancia de: 3086 km A la vista de los resultados proporcionados por el código en Python, el cantante recorrerá un total de 3086 km durante su gira. Empezará y acabará en Sevilla y la ruta que debe seguir es la siguiente: Sevilla – Lisboa – La Coruña – Salamanca – Madrid – Bilbao – Zaragoza – Barcelona – Valencia – Murcia – Sevilla. Vista en el mapa, la ruta queda así: Ilustración 26. Mapa con la mejor ruta. TSP 10 ciudades I L - A I A - V - I 49 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Se puede observar que no importa en qué ciudad se empiece mientras se siga el orden del resto de la ruta establecida, por ejemplo: Madrid – Bilbao – Zaragoza – Barcelona – Valencia – Murcia – Sevilla – Lisboa – La Coruña – Salamanca – Madrid. La distancia total es la suma de ir de una ciudad a otra siguiendo la ruta establecida en la solución. En este caso la mejor solución da como resultado una distancia de 3086 km, que son casi 2000 km menos que la ruta aleatoria mostrada al principio. Esta mejora se consigue en menos de 5 segundos, tiempo que tarda en proporcionar la solución el código. 5.2.3 Escenario 2 Para 30 ciudades, el número de posibles soluciones es aproximadamente 2,6525286!𝑥!1021 . Esto hace que sea extremadamente difícil llegar a la mejor solución. Es aquí donde cobra especial importancia el uso de alguna técnica, como el algoritmo genético, que proporcione soluciones óptimas en un tiempo razonable. Aunque se tarde algo más en ejecutar el código en este escenario que en el anterior, en menos de un minuto se obtiene la solución. Los parámetros en este escenario son tamaño de población = 1000, número de generaciones = 500 y tasa de mutación = 0,5. Se observa que al haber más ciudades sea necesario explorar un mayor número de soluciones, lo que se puede conseguir aumentando el tamaño de la población. Nuevamente, será necesario ejecutar varias veces para analizar el mayor rango de soluciones posibles. Algunas de las soluciones obtenidas son las siguientes: Ilustración 27. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 5911 km Resultados 50 50 La mejor ruta encontrada es: ['Paris', 'Nantes', 'San Sebastián', 'Bilbao', 'Vitoria', 'León', 'Oviedo', 'La Coruña', 'Santiago', 'Oporto', 'Coimbra', 'Lisboa', 'Évora', 'Mérida', 'Cáceres', 'Salamanca', 'Segovia', 'Madrid', 'Ciudad Real', 'Faro', 'Sevilla', 'Málaga', 'Córdoba', 'Murcia', 'Valencia', 'Zaragoza', 'Barcelona', 'Toulouse', 'Marsella', 'Lyon', 'Paris'] Con una distancia de: 5911 km Ilustración 28. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 5836 km La mejor ruta encontrada es: ['Paris', 'Nantes', 'San Sebastián', 'Bilbao', 'Vitoria', 'León', 'Oviedo', 'La Coruña', 'Santiago', 'Oporto', 'Coimbra', 'Lisboa', 'Évora', 'Mérida', 'Cáceres', 'Salamanca', 'Segovia', 'Madrid', 'Ciudad Real', 'Córdoba', 'Faro', 'Sevilla', 'Málaga', 'Murcia', 'Valencia', 'Zaragoza', 'Barcelona', 'Toulouse', 'Marsella', 'Lyon', 'Paris'] Con una distancia de: 5836 km Como se vió en el escenario 1 y se observa en la Ilustración 29, es posible que la solución empeore en las distintas veces que se implemente el código. Ilustración 29. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 5931 km 51 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización La mejor ruta encontrada es: ['Paris', 'Nantes', 'San Sebastián', 'Bilbao', 'Vitoria', 'León', 'Oviedo', 'La Coruña', 'Santiago', 'Oporto', 'Coimbra', 'Lisboa', 'Évora', 'Mérida', 'Cáceres', 'Salamanca', 'Segovia', 'Madrid', 'Ciudad Real', 'Córdoba', 'Málaga', 'Sevilla', 'Faro', 'Murcia', 'Valencia', 'Zaragoza', 'Barcelona', 'Toulouse', 'Marsella', 'Lyon', 'Paris'] Con una distancia de: 5931 km Tras realizar 10 ejecuciones, la mejor solución encontrada es la que corresponde a una ruta de 5814 km. Como se comprueba en la Tabla 14, las soluciones obtenidas en las distintas ejecuciones no varían mucho, lo que muestra la estabilidad del código. Tabla 14. Resultado de las 10 ejecuciones del escenario 2 del TSP Media Desviación Mejor resultado Peor resultado 5880,2 57,49 5814 5931 Ilustración 30. Evolución de la mejor solución encontrada por el algoritmo. Ruta de 5814 La mejor ruta encontrada es: ['Málaga', 'Faro', 'Sevilla', 'Córdoba', 'Ciudad Real', 'Madrid', 'Segovia', 'Salamanca', 'Cáceres', 'Mérida', 'Évora', 'Lisboa', 'Coimbra', 'Oporto', 'Santiago', 'La Coruña', 'Oviedo', 'León', 'Vitoria', 'Bilbao', 'San Sebastián', 'Nantes', 'Paris', 'Lyon', 'Marsella', 'Toulouse', 'Barcelona', 'Zaragoza', 'Valencia', 'Murcia', 'Málaga'] Con una distancia de: 5814 km En la Ilustración 30 se observa como evolucionan las soluciones en las 500 iteraciones. La solución se estabiliza alrededor de la generación 250 y la menor distancia encontrada es 5814 km. En conclusión, al ampliar la gira, la distancia mínima que tendrá que recorrer el cantante es 5814 km, un poco menos que el doble que antes. La ruta vista en el mapa quedaría así: Resultados 52 52 Ilustración 31. Mapa con la mejor ruta. TSP 30 ciudades Al haber creado la población inicial según la cercanía de unas ciudades a otras, se consigue reducir bastante el tiempo de ejecución y garantizar una buena solución. Al igual que en el escenario 1, los resultados de las distintas ejecuciones no varían mucho entre sí, lo que indica que el algoritmo es estable. En este caso, para los parámetros elegidos, el peor resultado obtenido es 5931 km y el mejor es 5814 km, diferencia relativamente pequeña para la cantidad de ciudades. 5.3 Problema de la mochila Al igual que para el problema del viajante, se comenzará esta sección explicando el funcionamiento del algoritmo genético aplicado a este problema y luego se mostrarán los resultados. 5.3.1 Algoritmo genético aplicado al problema de la mochila (KP) En los escenarios del problema de la mochila propuestos en este trabajo, los datos son la capacidad máxima de la mochila y un vector pedidos donde en cada componente se encuentra el nombre del pedido, su valor y su peso o volumen. El valor no representa lo mismo en todos los problemas, D A A I - I 1 D - A ↓ D 1 I A T D ↓ D - I - & d I - - - I & 53 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización pero lo que se busca siempre es maximizar la suma del valor de los pedidos. Es decir, el objetivo de este tipo de problemas es buscar la combinación de objetos/pedidos que meter en la mochila sin superar la capacidad máxima y maximizando el valor total. En este trabajo se resolverán dos escenarios. En uno el valor será la urgencia o prioridad de entrega de un pedido, es decir, se querrá maximizar la urgencia, y en el otro se tiene como dato el precio al que se vende cada producto, por lo tanto, el objetivo será que el precio total de los productos seleccionados sea lo mayor posible para maximizar el beneficio. De ahora en adelante se utilizará el término valor para hablar de los dos escenarios, en el primero representará la urgencia y en el segundo el beneficio. Por tanto, la función ‘calculo_fitness’ es sumar el valor de cada pedido a una variable que guarde el valor total, a la vez que se suma su respectivo peso a la variable peso_total y se va comprobando que éste no supere la capacidad. Si se supera la capacidad se utiliza un sistema de penalización en el que se le otorga a la función objetivo un valor de 0. La función ‘calculo_fitness’ devuleve el valor total. Cada gen es un pedido, el individuo o solución será un vector cuyas variables tomarán valor 1 si el pedido se incluye en la mochila y 0 en caso contrario, y la aptitud será la suma de los valores de las variables que están incluidas. Parámetros Al igual que en el problema del viajante, los parámetros se determinarán a través del mismo proceso empírico. Finalmente, los parámetros elegidos para el primer escenario son: Tabla 15. Pruebas combinación de parámetros KP escenario 1 Tamaño de población = 100 Número de generaciones = 25 Tasa de mutación = 0,1 En este caso se observa cómo, para estos parámetros, se garantiza siempre la misma solución. Mientras que los valores de los parámetros del segundo escenario, al haber más pedidos, serán mayores: Media Desviación Mejor resultado Peor resultado TM 0,1 12,8 0,42163702 13 12 TM 0,3 12,6 0,51639778 13 12 TM 0,5 12,2 1,22927259 13 10 TM 0,1 12,7 0,48304589 13 12 TM 0,3 12,8 0,42163702 13 12 TM 0,5 12,9 0,31622777 13 12 TM 0,1 13 013 13 TM 0,3 12,8 0,42163702 13 12 TM 0,5 12,9 0,31622777 13 12 TP 100 TP 25 TP 50 Resultados 54 54 Tabla 16. Pruebas combinación de parámetros KP escenario 2 Tamaño de población = 1000 Número de generaciones = 500 Tasa de mutación = 0,5 Procedimiento Para un mismo número de datos, por ejemplo, 20 ciudades y 20 productos, el KP tiende a tener menos posibles soluciones; por lo tanto, en este caso sí que se partirá de una población completamente aleatoria. La función ‘crear_individuo’ generará un vector con tantos componentes como productos y asignará valores binarios aleatorios. El 0 representará que el producto no se incluye en la solución y el 1 lo contrario. Igual que para el TSP, cuando se tiene la población inicial y la función ‘calculo_fitness’, se crean unas variables para almacenar los mejores resultados. La única diferencia es que, como en este caso estamos maximizando, el valor inicial de la variable ‘mejor_fitness’ será 0. Después de esto se ejecuta el bucle principal hasta igualar el número de generaciones. Los pasos dentro del bucle son los mismos que el problema del viajante, la diferencia radica en cómo funcionan algunas de las funciones a las que se llama. La función ‘padres’ es igual, sin embargo, las funciones ‘cruce’ y ‘mutación’ varían. En el cruce se selecciona un punto aleatorio y se crea un vector hijo combinando genes del padre1 hasta el punto de corte y los del padre2 después. En la mutación se selecciona un índice al azar del padre1 y se cambia el gen correspondiente a dicho índice, es decir, si antes valía 1 después valdrá 0, y viceversa. En este caso, como solo se genera un hijo en cada generación, se eliminará únicamente el último elemento del vector ‘población_ordenada’ y se sustituirá por el hijo. Se vuelve a calcular la aptitud de cada individuo y se ordena la población. Con base en esta nueva población se obtiene el mejor individuo de la generación y su aptitud y se comparara con el mejor individuo hasta el momento. En caso de ser mejor, se actualizará el mejor individuo y su fitness. Media Desviación Mejor resultado Peor resultado TM 0,1 9419 224,373201 9780 8980 TM 0,3 9594 335,797558 10080 9030 TM 0,5 9397 507,39093 10080 8500 TM 0,1 9694 305,657761 10080 9150 TM 0,3 9718 273,284548 10180 9150 TM 0,5 9924 135,170674 10180 9780 TM 0,1 9820 182,878223 10180 9550 TM 0,3 9802 137,663035 10030 9530 TM 0,5 10009 126,002645 10180 9800 TP 1000 TP 100 TP 500 55 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Tras la explicación del algoritmo genético aplicado a este problema, se muestran los resultados de ambos escenarios. Para mayor claridad, el código implementado en Python imprimirá por pantalla dos ilustraciones junto con el resultado. En la ilustración de la izquierda se puede observar la evolución de la aptitud durante toda la ejecución del algoritmo, es decir, el valor de la mejor solución en cada generación. Mientras que en la gráfica de la derecha se muestra la solución óptima, donde las barras que aparecen representan los pedidos incluidos: la barra azul indica el valor o urgencia y la naranja el peso o volumen de cada producto seleccionado. 5.3.2 Escenario 1 Al tener el escenario 1 solo 5 pedidos, haciendo algunas operaciones y cálculos a mano puede comprobarse cuál es la solución óptima: (1, 0, 1, 1, 1) con aptitud 13 y un volumen total de 29 litros. Este mismo resultado se obtiene en segundos gracias al algoritmo genético. Se ejecuta el código 10 veces para comprobarlo y, efectivamente, con los parámetros seleccionados en la Tabla 15 (tamaño de población = 100, número de generaciones = 25 y tasa de mutación = 0,1) el resultado es siempre el esperado. En la Tabla 17 se observan la media y desviación de las soluciones encontradas en las 10 ejecuciones realizadas y el mejor y peor resultado, que como se ha comentado, en este escenario es el mismo. Tabla 17. Resultado de las 10 ejecuciones del escenario 1 del KP Media Desviación Mejor resultado Peor resultado 13 0 13 13 La mejor solución es la siguiente: Ilustración 32. Productos incluidos en la mochila. Aptitud 13 62 REFERENCIAS [1] R. A. Española, «Ingeniería». Fecha de acceso: marzo 2023: https://dle.rae.es/ingenier%C3%ADa [2] A. E. Varela, «La ingeniería industrial como herramienta para la internacionalización» 2010. Fecha de acceso: febrero 2023. https://www.laccei.org/LACCEI2010- Peru/Papers/Papers_pdf/IGE089_Espinal.pdf [3] «Historia de la Ingeniería Industrial». Fecha de acceso: abril 2023. https://www.ingenieriaindustrialonline.com/conceptos-generales/historia-de- la-ingenieria-industrial/ [4] «Precursores de la ingeniería industrial». Fecha de acceso: febrero 2023. https://predictiva21.com/precursores-ingenieria-industrial-2/ [5] «Historia de la ingeniería Industrial». Fecha de acceso: marzo 2023. https://ingenierosconingenio.com/blog/historia-de-la- ingenieria-industrial/ [6] «¿Qué es la ingeniería industrial?». Fecha de acceso: abril 2023. https://portal.coiim.es/colegio/que-es-la-ingenieria-industrial/ [7] AingOI, «La ingeniería de OI». Fecha de acceso: abril 2023. https://www.aingoi.com/la-ingenieria-de-oi/ [8] E. Sevilla, «Historia de la ETSi». Fecha de acceso: marzo 2023. https://www.etsi.us.es/etsi/nuestra-escuela/historia-de-la-etsi [9] G. Carman, «Ingeniería de organización industrial,» 2017. Fecha de acceso: abril 2023. https://grupocarman.com/blog/2017/03/18/ingenieria-de- organizacion-industrial/ [10] U. d. Carlemany, «Los orígenes e historia de la ingeniería en organización industrial,» 2021. Fecha de acceso: marzo 2023. https://www.universitatcarlemany.com/actualidad/blog/losorigenes-e-historia-de-la-ingenieria-en-organizacion- industrial/#:~:text=La%20aparici%C3%B3n%20de%20la%20Ingenier%C3%ADa,de%20F rederick%20Taylor%20en%201903. [11] L. Castaño, «La historia de la Organización Industrial,» 2011. Fecha de acceso: marzo 2023. https://tuotrodiario.es/consejos/historia-organizacion- industrial [12] AingOI, «Historia de la IOI». Fecha de acceso: abril 2023. https://www.aingoi.com/la-ingenieria-de-oi/historia/ [13] «Lean Manufacturing: qué es, principios, herramientas y ejemplos». 63 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Fecha de acceso: abril 2023. https://www.cursosaula21.com/que-es-lean-manufacturing/ [14] «Ingeniería de organización industrial». Fecha de acceso: abril 2023. https://es.wikipedia.org/wiki/Ingenier%C3%ADa_de_organizaci%C3%B3n_industrial [15] ADINGOR, «Asociación para el Desarrollo de la Ingeniería de Organización». Fecha de acceso. marzo 2023. https://adingor.net/quienes-somos/# [16] «Ingeniería de organización industrial». Fecha de acceso: abril 2023. https://es.wikipedia.org/wiki/Ingenier%C3%ADa_de_organizaci%C3%B3n_industrial#Aso ciaci%C3%B3n_Profesional_de_Ingenieros_de_Organizaci%C3%B3n_Industrial_de_Espa %C3%B1a_(AingOI) [17] T. O. Society, «About OR-The Operational Research Society». Fecha de acceso: abril 2023. https://www.theorsociety.com/about-or/ [18] «Historia de la Investigación de Operaciones,» 2015. Fecha de acceso: https://www.scielo.br/j/bolema/a/Vbm7ZdpKvyyshsWHwHNqksS/?lang=es&format=pdf#: ~:text=La%20investigación%20operacional%20tuvo%20sus,determinar%20cuáles%20tácti cas%20militares%20funcionaban. [19] «Perspectivas históricas de la Investigación Operacional,» 2018. Fecha de acceso: abril 2023. https://www.gestiondeoperaciones.net/programacion_lineal/historia-de-la-investigacion-de- operaciones/ [20] IFORS, «IFORS History». Fecha de acceso: marzo 2023. https://www.ifors.org/history/ [21] IFORS, «Regional Groupings». Fecha de acceso: marzo 2023. https://www.ifors.org/regional-groupings/ [22] T. O. Society, «History of The OR Society». Fecha de acceso: febrero 2023. https://www.theorsociety.com/about-us/history-of-the-or- society/ [23] «Institute for Operations Research and the Management Sciences». Fecha de acceso: marzo 2023. https://en.wikipedia.org/wiki/Institute_for_Operations_Research_and_the_Management_Sc iences [24] «informs». Fecha de acceso: abril 2023. https://www.informs.org/ [25] Seio, «Breve historia». Fecha de acceso: marzo 2023. https://www.seio.es/breve-historia/ [26] «¿Qué son los Problemas de Dieta?» 2019. Referencias 64 64 Fecha de acceso: marzo 2023. https://knuth.uca.es/moodle/mod/page/view.php?id=4498 [27] «La Tienda Hero». Fecha de acceso: mayo 2023. https://www.latiendahero.es [28] G. J. Stigler, «The Cost of Subsistence,» Journal of Farm Economics, Vol. 27, No. 2, May 1945. [29] «Problema del viajante». Fecha de acceso: marzo 2023. https://es.wikipedia.org/wiki/Problema_del_viajante#Historia [30] N. Cummings, «A brief History of the Travelling Salesman Problem». Fecha de acceso: marzo 2023. https://www.theorsociety.com/about-or/ormethods/heuristics/a-brief-history-of-the-travelling-salesman-problem/ [31] «Problema del Viajante de Comercio» 2017. Fecha de acceso: abril 2023. https://knuth.uca.es/moodle/mod/page/view.php?id=4131&lang=en [32] « Tres métodos diferentes para resolver el problema del viajante» 2020. Fecha de acceso: mayo 2023. https://baobabsoluciones.es/blog/2020/10/01/problema-del- viajante/ [33] «Problema de la mochila ». Fecha de aaceso: abril 2023. https://www.uaeh.edu.mx/scige/boletin/tlahuelilpan/n6/e2.html [34] « El tutorial de Python ». Fecha de acceso: junio 2023. https://docs.python.org/es/3/tutorial/ [35] «Teoría del método Simplex». Fecha de acceso: mayo 2023. http://www.phpsimplex.com/teoria_metodo_simplex.htm [36] M. 365, «Definir y resolver un problema con Solver». Fecha de acceso: abril 2023. https://support.microsoft.com/es-es/office/definir-y-resolver- un-problema-con-solver-5d1a388f-079d-43ac-a7eb-f63e45925040 [37] «Gurobi Optimization» 2011. Fecha de acceso: abril 2023. http://investigaciondeoperacion2es.blogspot.com/2011/10/gurobi-optimization.html [38] M. Karbstein, «Introduction to Modeling with Python,» 2022. Fecha de acceso: mayo 2023. https://www.gurobi.com/wpcontent/uploads/IntroModeling.pdf?x58432 [39] «Metaheurísticas» 2021. Fecha de acceso: abril 2023. http://www.cs.us.es/~fsancho/?e=207 [40] «Metaheurística: la disciplina desconocida que se ha vuelto imprescindible en las grandes empresas,» 2017. Fecha de acceso: abril 2023. https://www.expansion.com/empresas/2017/07/08/59609d2b268e3ecb7a8b45aa.html 65 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización [41] J. C. López, «Introducción a los algoritmos genéticos,» 2010. Fecha de acceso: mayo 2023. https://www.adictosaltrabajo.com/2010/10/07/jgap/#:~:text=Los%20principios%20b%C3% A1sicos%20de%20los,existen%20en%20una%20determinada%20poblaci%C3%B3n. [42] J. A. Rodrigo, «Optimización con algoritmo genético y Nelder-Mead,» 2019. Fecha de acceso: mayo 2023. https://www.cienciadedatos.net/documentos/48_optimizacion_con_algoritmo_genetico 66 ANEXO Anexo 1 En este anexo se muestran la tabla completa con los datos del escenario 2 del problema de la dieta. Éstos han sido obtenidos del artículo ‘The Cost of Subsistence’ escrito por George Stigler en 1945. Tabla 19. Datos del escenario 2 del problema de la dieta 67 Anexo 2 En el anexo 2 se presentan los datos del escenario 2 del problema del viajante. En la Tabla 20 se observa la matriz completa con las 30 ciudades y las respectivas distancias. Tabla 20. Matriz distancias (km) 30 ciudades 68 Para mayor claridad en las siguientes tablas se muestra esta matriz con las 30 ciudades dividida por grupos: Tabla 21. Matriz distancias (km) Barcelona - Córdoba 69 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Tabla 22. Matriz distancias (km) Évora - Lisboa Anexo 70 70 Tabla 23. Matriz distancias (km) Madrid - Nantes 71 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización Tabla 24. Matriz distancias (km) Oporto - San Sebastián Anexo 78 78 Anexo 4 Algoritmo genético El código es el mismo para ambos escenarios, lo único que cambian son los datos. Por ello, se presentará el código del escenario 1. - TSP o Escenario 1 import random import matplotlib.pyplot as plt #Crear individuo aleatorio def crear_individuo(): return random.sample(ciudades, len(ciudades)) #Cálculo de la aptitud def calculo_fitness(route): distancia = 0 distancia_total= distancias[ciudades.index(route[0])][ciudades.index(route[-1])] for i in range(len(route)-1): distancia+= distancias[ciudades.index(route[i])][ciudades.index(route[i+1])] distancia_total += distancia return distancia_total #Selección de los padres def padres(poblacion_ordenada): padre1 = poblacion_ordenada[0] padre2 = poblacion_ordenada[1] return padre1, padre2 #Cruce de los padres def cruce(padre1, padre2): punto_cruce = random.randint(1, len(padre1)-1) hijo1 = padre1[:punto_cruce] + [x for x in padre2 if x not in padre1[:punto_cruce]] hijo2 = padre2[:punto_cruce] + [x for x in padre1 if x not in 79 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización padre2[:punto_cruce]] return hijo1, hijo2 #Mutación def mutacion(hijo): index1 = random.randint(0, len(hijo)-1) index2 = random.randint(0, len(hijo)-1) hijo[index1], hijo[index2] = hijo[index2], hijo[index1] return hijo #Datos del problema ciudades = ["Barcelona", "Bilbao", "La Coruña", "Lisboa", "Madrid", "Murcia", "Salamanca", "Sevilla", "Valencia", "Zaragoza"] distancias = [ [0,470,895,1005,506,470,655,822,298,256], [470,0,425,720,321,606,334,702,470,248], [895,425,0,517,506,856,347,694,793,645], [1005,720,517,0,499,702,373,308,760,770], [506,321,506,499,0,352,175,392,305,274], [470,606,856,702,352,0,509,436,180,405], [655,334,347,373,175,509,0,399,478,405], [822,702,694,308,392,436,399,0,545,647], [298,470,793,760,305,180,478,545,0,243], [256, 248,645,770,274,405,405,647,243,0] ] #Parámetros del algoritmo tam_poblacion = 300 num_generaciones = 500 tasa_mutacion = 0.5 mejores_distancias = [] mejor_individuo = None mejor_fitness = float('inf') Anexo 80 80 #Se crea población inicial aleatoria poblacion = [crear_individuo() for i in range(tam_poblacion)] #Bucle principal del algoritmo for generacion in range(num_generaciones): fitness = [calculo_fitness(individuo) for individuo in poblacion] poblacion_ordenada = [x for _, x in sorted(zip(fitness, poblacion), reverse=False)] padre1, padre2 = padres(poblacion_ordenada) if random.random() > tasa_mutacion: hijo1, hijo2 = cruce(padre1, padre2) else: hijo1 = mutacion(padre1) hijo2 = mutacion(padre2) #Se actualiza la población poblacion_ordenada.pop() poblacion_ordenada.pop() poblacion_ordenada.append(hijo1) poblacion_ordenada.append(hijo2) poblacion = poblacion_ordenada #Se actualiza el fitness y ordenar nuevamente la población fitness = [calculo_fitness(individuo) for individuo in poblacion] poblacion_ordenada = [x for _, x in sorted(zip(fitness, poblacion), reverse=False)] poblacion = poblacion_ordenada.copy() #Obtener el mejor individuo de esta generación mejor_actual = poblacion[0] fitness_mejor_actual = fitness[0] 81 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización #Comprobar si el mejor individuo de esta generación es mejor que el mejor encontrado hasta ahora if fitness_mejor_actual < mejor_fitness: mejor_individuo = mejor_actual.copy() mejor_fitness = fitness_mejor_actual #Almacenar la distancia del mejor individuo de esta generación mejores_distancias.append(mejor_fitness) #Gráfica de la evolución de la distancia total plt.plot(mejores_distancias) plt.xlabel("Generación") plt.ylabel("Distancia (km)") plt.title("Menor distancia encontrada en cada generación") plt.show() mejor_individuo.append(mejor_individuo[0]) print("La mejor ruta encontrada es:", mejor_individuo) print("Con una distancia de:", mejor_fitness, "km") o Escenario 2 import random import matplotlib.pyplot as plt #Se crean individuos para la poblaciñon inicial. No es completamente aleatoria def crear_individuo(): ciudad_inicial = random.choice(ciudades) individuo = [ciudad_inicial] for _ in range(len(ciudades)-1): Anexo 82 82 ciudades_restantes = [ciudad for ciudad in ciudades if ciudad not in individuo] distancia_minima = float('inf') ciudad_mas_cercana = None for ciudad in ciudades_restantes: distancia = distancias[ciudades.index(individuo[- 1])][ciudades.index(ciudad)] if distancia < distancia_minima: distancia_minima = distancia ciudad_mas_cercana = ciudad individuo.append(ciudad_mas_cercana) return individuo #Cálculo de la aptitud, distancia total def calculo_fitness(route): distancia = 0 distancia_total= distancias[ciudades.index(route[0])][ciudades.index(route[-1])] for i in range(len(route)-1): distancia+= distancias[ciudades.index(route[i])][ciudades.index(route[i+1])] distancia_total += distancia return distancia_total #Selección de los padres def padres(poblacion_ordenada): padre1 = poblacion_ordenada[0] padre2 = poblacion_ordenada[1] return padre1, padre2 #Cruce def cruce(padre1, padre2): punto_cruce = random.randint(1, len(padre1)-1) 83 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización hijo1 = padre1[:punto_cruce] + [x for x in padre2 if x not in padre1[:punto_cruce]] hijo2 = padre2[:punto_cruce] + [x for x in padre1 if x not in padre2[:punto_cruce]] return hijo1, hijo2 #Mutación def mutacion(hijo): index1 = random.randint(0, len(hijo)-1) index2 = random.randint(0, len(hijo)-1) hijo[index1], hijo[index2] = hijo[index2], hijo[index1] return hijo #Datos ciudades = ["Barcelona", "Bilbao", "Cáceres", "Ciudad Real", "Coimbra", "Córdoba", "Évora", "Faro", "La Coruña", "León", "Lyon", "Lisboa", "Madrid", "Málaga", "Marsella", "Mérida", "Murcia", "Nantes", "Oporto", "Oviedo", "Paris", "Salamanca", "Santiago", "San Sebastián", "Segovia", "Sevilla", "Toulouse", "Valencia", "Vitoria", "Zaragoza"] distancias = [ [0, 470, 752, 580, 892, 710, 914, 995, 895, 685, 532, 1005, 506, 770, 338, 772, 470, 712, 900, 694, 831, 655, 897, 403, 528, 822, 261, 298, 430, 256], [470, 0, 506, 485, 562, 617, 668, 813, 425, 256, 676, 720, 321, 738, 672, 560, 606, 455, 522, 236, 743, 334, 457, 77, 275, 702, 360, 470, 50, 248], [752, 506, 0, 222, 185, 225, 166, 304, 454, 353, 1150, 261, 245, 350, 1070, 61, 454, 945, 264, 435, 1253, 167, 421, 564, 253, 240, 795, 514, 488, 522], [580, 485, 222, 0, 400, 143, 350, 413, 610, 445, 1041, 455, 163, 255, 914, 208, 263, 936, 470, 513, 1206, 270, 581, 509, 218, 253, 681, 307, 443, 393], [892, 562, 185, 400, 0, 400, 185, 355, 352, 352, 1233, 176, 396, 513, 1188, 222, 640, 952, 110, 408, 1279, 241, 300, 630, 365, 373, 892, 685, 555, 645], [710, 617, 225, 143, 400, 0, 284, 295, 681, 530, 1180, 392, 300, 134, 1050, 178, 289, 1071, 490, 615, 1347, 351, 640, 648, 344, 120, 823, 422, 580, 534], [914, 668, 166, 350, 185, 284, 0, 172, 535, 490, 1316, 108, 419, Anexo 84 84 367, 1234, 143, 565, 1093, 295, 561, 1408, 329, 483, 726, 420, 215, 963, 660, 650, 688], [995, 813, 304, 413, 355, 295, 172, 0, 706, 652, 1436, 220, 530, 310, 1328, 253, 579, 1250, 464, 727, 1556, 480, 654, 863, 545, 177, 1079, 714, 788, 794], [895, 425, 454, 610, 352, 681, 535, 706, 0, 220, 1082, 517, 506, 813, 1113, 523, 856, 687, 235, 207, 1029, 347, 54, 520, 445, 694, 801, 793, 469, 645], [685, 256, 353, 445, 352, 530, 490, 652, 220, 0, 900, 510, 310, 662, 896, 414, 659, 605, 274, 88, 928, 187, 244, 304, 221, 584, 611, 586, 239, 434], [532, 676, 1150, 1041, 1233, 1180, 1316, 1436, 1082, 900, 0, 1388, 913, 1267, 278, 1188, 995, 517, 1199, 887, 392, 1001, 1109, 605, 899, 1293, 360, 816, 678, 649], [1005, 720, 261, 455, 176, 392, 108, 220, 517, 510, 1388, 0, 499, 471, 1317, 244, 702, 1126, 279, 585, 1453, 373, 463, 788, 495, 308,1036, 760, 710, 770], [506, 321, 245, 163, 396, 300, 419, 530, 506, 310, 913, 499, 0, 416, 816, 283, 352, 774, 423, 373, 1053, 175, 488, 353, 68, 392, 561, 305, 282, 274], [770, 738, 350, 255, 513, 134, 367, 310, 813, 662, 1267, 471, 416, 0, 1108, 296, 323, 737, 613, 748, 1457, 484, 770, 762, 470, 157, 913, 472, 700, 627], [338, 672, 1070, 914, 1188, 1050, 1234, 1328, 1113, 896, 278, 1317, 816, 1108, 0, 1095, 805, 1158, 1175, 907, 660, 945, 1132, 595, 824, 1163, 319, 642, 656, 545], [772, 560, 61, 208, 222, 178, 143, 253, 523, 414, 1188, 244, 283, 296, 1095, 0, 434, 1001, 316, 495, 1304, 235, 478, 610, 294, 174, 832, 518, 535, 552], [470, 606, 454, 263, 640, 289, 565, 579, 856, 659, 995, 702, 352, 323, 805, 434, 0, 1026, 736, 717, 1240, 509, 806, 597, 416, 436, 673, 180, 549, 405], [712, 455, 945, 936, 952, 1071, 1093, 1250, 687, 605, 517, 1126, 774, 737, 1158, 1001, 1026, 0, 878, 545, 342, 769, 731, 436, 728, 1153, 466, 869, 494, 623], [900, 522, 264, 470, 110, 490, 295, 464, 235, 274, 1199, 279, 423, 613, 1175, 316, 736, 878, 0, 335, 1213, 253, 192, 597, 380, 478, 869, 726, 525, 647], [694, 236, 435, 513, 408, 615, 561, 727, 207, 88, 887, 585, 373, 748, 907, 495, 717, 545, 335, 0, 878, 266, 225, 312, 305, 664, 589, 630, 264, 449], [831, 743, 1253, 1206, 1279, 1347, 1408, 1556, 1029, 928, 392, 1453, 1053, 1457, 660, 1304, 1240, 342, 1213, 878, 0, 1079, 1071, 85 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización 700, 1015, 1441, 588, 1066, 772, 840], [655, 334, 167, 270, 241, 351, 329, 480, 347, 187, 1001, 373, 175, 484, 945, 235, 509, 769, 253, 266, 1079, 0, 319, 400, 131, 399, 653, 478, 324, 405], [897, 457, 421, 581, 300, 640, 483, 654, 54, 244, 1109, 463, 488, 770, 1132, 478, 806, 731, 192, 225, 1071, 319, 0, 535, 425, 649, 812, 782, 478, 644], [403, 77, 564, 509, 630, 648, 726, 863, 520, 304, 605, 788, 353, 762, 595, 610, 597, 436, 597, 312, 700, 400, 535, 0, 317, 741, 278, 449, 77, 206], [528, 275, 253, 218, 365, 344, 420, 545, 445, 221, 899, 495, 68, 470, 824, 294, 416, 728, 380, 305, 1015, 131, 425, 317, 0, 427, 544, 358, 244, 280], [822, 702, 240, 253, 373, 120, 215, 177, 694, 584, 1293, 308, 392, 157, 1163, 174, 436, 1153, 478, 664, 1441, 399, 649, 741, 427, 0, 1260, 545, 670, 647], [261, 360, 795, 681, 892, 823, 963, 1079, 801, 611, 360, 1036, 561, 913, 319, 832, 673, 466, 869, 589, 588, 653, 812, 278, 544, 1260, 0, 485, 344, 288], [298, 470, 514, 307, 685, 422, 660, 714, 793, 586, 816, 760, 305, 472, 642, 518, 180, 869, 726, 630, 1066, 478, 782, 449, 358, 545, 485, 0, 424, 243], [430, 50, 488, 443, 555, 580, 650, 788, 469, 239, 678, 710, 282, 700, 656, 535, 549, 494, 525, 264, 772, 324, 478, 77, 244, 670, 344, 424, 0, 294], [256, 248, 522, 393, 645, 534, 688, 794, 645, 434, 649, 770, 274, 627, 545, 552, 405, 623, 647, 449, 840, 405, 644, 206, 280, 647, 288, 243, 294, 0] ] #Parámetros tam_poblacion = 1000 num_generaciones = 500 tasa_mutacion = 0.3 mejores_distancias = [] mejor_individuo = None mejor_fitness = float('inf') poblacion = [crear_individuo() for i in range(tam_poblacion)] Anexo 86 86 #Bucle principal del algoritmo for generacion in range(num_generaciones): fitness = [calculo_fitness(individuo) for individuo in poblacion] poblacion_ordenada = [x for _, x in sorted(zip(fitness, poblacion), reverse=False)] padre1, padre2 = padres(poblacion_ordenada) if random.random() > tasa_mutacion: hijo1, hijo2 = cruce(padre1, padre2) else: hijo1 = mutacion(padre1) hijo2 = mutacion(padre2) #Se actualiza la población poblacion_ordenada.pop() poblacion_ordenada.pop() poblacion_ordenada.append(hijo1) poblacion_ordenada.append(hijo2) poblacion = poblacion_ordenada # Se actualiza el fitness y ordenar nuevamente la población fitness = [calculo_fitness(individuo) for individuo in poblacion] poblacion_ordenada = [x for _, x in sorted(zip(fitness, poblacion), reverse=False)] poblacion = poblacion_ordenada.copy() # Obtener el mejor individuo de esta generación mejor_actual = poblacion[0] fitness_mejor_actual = fitness[0] # Comprobar si el mejor individuo de esta generación es mejor que el mejor encontrado hasta ahora if fitness_mejor_actual < mejor_fitness: 87 Desarrollo y resolución de modelos de investigación operativa para la divulgación de la ingeniería de organización mejor_individuo = mejor_actual.copy() mejor_fitness = fitness_mejor_actual #Almacenar la distancia del mejor individuo de esta generación mejores_distancias.append(mejor_fitness) #Gráfica de la evolución de la distancia total plt.plot(mejores_distancias) plt.xlabel("Generación") plt.ylabel("Distancia (km)") plt.title("Menor distancia encontrada en cada generación") plt.show() mejor_individuo.append(mejor_individuo[0]) print("La mejor ruta encontrada es:", mejor_individuo) print("Con una distancia de:", mejor_fitness, "km") En el problema de la mochila el código es el mismo para ambos escenarios, lo único que cambian son los datos y valores de los parámetros. Por ello, se presentará el código de un único escenario, el 1. - KP import random import matplotlib.pyplot as plt #Datos pedidos = [('pedido A', 5, 15), ('pedido B', 2, 12), ('pedido C', 2, 5), ('pedido D', 5, 2), ('pedido E', 1, 7)] capacidad = 30 #Parámetros del algoritmo genético tam_poblacion = 100 num_generaciones = 25 tasa_mutacion = 0.1