Problema de optimización mediante software

TRABAJO FIN DE GRADO Problema de optimización mediante software Alumno: D. Gonzalo Manuel Roa Muñoz Dirigido por: D. Antonio Beato Moreno Junio 2020 FACULTAD DE MATEMATICAS GRADO EN ESTADISTICA UNIVERSIDAD DE SEVILLA FACULTAD DE MATEMÁTICAS TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 2 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 3 Agradecimientos Con este proyecto cierro un ciclo de mi vida que me planteé como un desafío personal fuera de la edad óptima, pero que me ha servido para satisfacer la necesidad de completar unas carencias de formación que llevaba tiempo echando en falta en mi etapa profesional como docente. He disfrutado aprendiendo de todas las áreas de conocimiento que he estudiado, aunque me ha costado un esfuerzo que sólo mi familia más cercana conoce verdaderamente. Por eso quiero agradecerles haber sido mi principal soporte apoyándome y ayudándome en aquellos momentos que más lo he necesitado, dándome la fuerza necesaria para continuar luchando en lo que creo y nunca rendirme. Gracias, también, a todos mis amigos, a mis compañeros y al equipo directivo del colegio Altair, donde estoy como docente, por demostrarme su aprecio y permitirme que pudiera compaginar trabajo y estudio. Por último, y no menos importante, quiero agradecer el trabajo de revisión de este proyecto a D. Antonio Beato Moreno, por ayudarme a mejorarlo y darme las pautas necesarias para la culminación de dicho proyecto con éxito. Gonzalo Manuel Roa Muñoz TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 4 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 5 Resumen-abstract Resumen El estudio y el desarrollo en la Investigación Operativa han permitido un gran avance en el mundo empresarial, ya que su aplicación facilita la toma de decisiones, considerando la disponibilidad limitada de recursos. Este desarrollo ha tenido un gran auge gracias a los avances tecnológicos, ya que permite llevar a cabo su resolución más rápida y segura. Además de procesar una gran cantidad de datos, de forma que de otra manera no fuese posible, o fuese muy tedioso su desarrollo y la obtención de la solución. En este Trabajo Fin de Grado (TFG) pretendo analizar distintos problemas de optimización matemática con la utilización de distintos software aunque me centrare más en el paquete R. Abstract The study and development in Operations Research have allowed a great advance in the business world, since its application facilitates the decision making, considering the limited availability of resources. This development has had a great boom thanks to the technological advances, since it allows us to carry out its resolution faster and more secure. In addition, to process a large amount of data, otherwise it would not be possible, or it would be very tedious to get and obtain the solution. In this Final Degree Project (TFG) I intend to analyze different mathematical optimization problems with the use of different sodtware, although I will focus more on the R Package. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 6 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 7 Introducción El estudio de la optimización la programación matemática es muy interesante actualmente, debido a su gran versatilidad para la aplicación en el mundo empresarial. El estudio de esta rama ha sido posible a lo largo del grado, en diferentes asignaturas, si bien en algunas, con mayor profundidad. No obstante, si consideramos objetivamente, el mundo tecnológico actual en el que nos encontramos, el desarrollo de este ámbito se lleva en gran medida a través del uso de herramientas informáticas. El conocimiento teórico de esta disciplina permite tener los fundamentos básicos necesarios para un desarrollo e investigación de mayor profundidad. Esta investigación puede verse facilitada con el uso de software informáticos, además de poder avanzar a una gran velocidad en su desarrollo y aplicación. Además de contar con muchos tipos de programas informáticos desde hace años, el incesante aumento del volumen de software hasta la actualidad, nos abre la posibilidad de elegir entre una enorme variedad de herramientas informáticas, que nos ayudan a la puesta en práctica de Investigación Operativa. Muchas de ellas se desarrollan para un uso en concreto, de forma que sean específicos y abarquen dicho campo en su totalidad, mientras que otras se desenvuelven de forma genérica para poder englobar diferentes ámbitos. Considerando esta gran variedad de software, así como la incesante evolución de ambas clases de programas, el uso de un conjunto de las herramientas informáticas, nos puede llevar a la aplicación práctica completa de esta rama, sopesando las desventajas o errores que puedan esconderse en ellas, con el uso de otras, y así poder complementarse mutuamente. De forma más concreta, a lo largo de su estudio en la Universidad, se ha desarrollado su aplicación con el uso de hojas de cálculo Excel. Han sido de gran utilidad, además de permitir que profundicemos en el aprendizaje de este software, son muy usadas actualmente en el mundo laboral. Por todo ello, el mayor estudio e investigación de las herramientas actuales puede ser muy interesante, ya que con el conocimiento básico de algunas de ellas, podremos desarrollar muchos otros tipos de problemas. Este puede ser el caso del software informático R (The R Project for Statistical Computing), el cual es muy usado en la actualidad, no solo en esta materia, sino en una gran variedad ámbitos, estudios, investigaciones etc. que podremos comprender si estudiamos los cimientos de esta herramienta. Este proyecto se basará en el estudio e investigación del software informáticos, que permitan aplicar y facilitar la resolución de diferentes problemas de optimización. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 8 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 9 Contenido Agradecimientos 3 Resumen/Astract 5 Introducción 7 Capítulo 1: Fundamentos de optimización 12 1.1 Conceptos básicos 12 1.2 Definiciones 15 1.3 Convexidad 22 1.3.1 Conjuntos convexos 22 1.3.2 Funciones convexas 27 1.3.3 Optimización de funciones convexas 28 Capítulo 2: Tipos de problemas de Optimización 30 2.1 Programación no restringida 30 2.2 Programación restringida 31 2.2.1 Condiciones KKT 31 2.2.2 Programación lineal 33 2.2.3 Programación cuadrática 34 2.2.4 Programación cónica 35 2.2.5 Programación entera mixta 36 2.2.5.1 Problemas de redes 36 2.2.5.2 Problemas del viajante 37 2.2.5.3 Problemas de ruta de vehículos 37 2.2.6 Otros problemas de optimización 37 2.2.6.1 Problemas Multiobjetivos 37 2.2.6.2 Optimización FUZZY (difusa) 38 2.2.6.3 Optimización Global___________________39 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 16 Donde o en notación vectorial como: (PPNL) Donde ahora son funciones vectoriales. Las funciones implicadas en la definición del problema fundamental no tienen por qué tener ninguna propiedad en particular, pero en nuestro caso vamos a introducir hipótesis adicionales que ayudarán a simplificar el problema; por ejemplo, supondremos de forma general que las funciones son continuas y en la mayoría de los casos tendrán derivadas primeras y segundas también continuas. La resolución del problema de optimización PPNL consistirá en primer lugar, en buscar valores para las variables de decisión que cumplan las ecuaciones e inecuaciones que forman el sistema de las restricciones y en segundo lugar encontrar de entre estos valores aquel o aquellos que proporcionen el mayor (si el objetivo es maximizar) o menor (si el objetivo es minimizar) valor para la función real . Definición 1.2 Se definen algunos casos particulares del problema general de optimización 1.1. 1. Problemas sin restricciones: En este tipo de problemas no hay restricciones de ningún tipo, es decir m = p = 0. La expresión general para estos problemas es (PSR) (1.2) Las únicas limitaciones vienen dadas por el conjunto de donde esté definida la función . TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 17 2. Problemas de Lagrange o problemas sólo con restricciones de igualdad: Son problemas de optimización con restricciones donde solamente existen restricciones de igualdad, por tanto y . Son problemas de la forma: (PRI) No hay restricciones dadas por inecuaciones, sólo por ecuaciones. 3. Problemas unidimensionales o univariantes: Este es un caso particular de los problemas sin restricciones en los que solamente hay una variable, es decir para El problema se expresa como: (P1D) (1.4) donde es, en la mayoría de las ocasiones, un intervalo. De fi nición 1.3 ( Solución facti b le) Diremos que es una solución factible del problema PPNL (ecuación 1.1) si cumple todas sus restricciones, es decir: De fi nición 1.4 (Conjunto factible) se define región o conjunto factible del problema PPNL al conjunto de todas sus soluciones factibles. Observación 1.3 Con estas definiciones se puede decir que el objetivo al intentar resolver el problema de optimización PPNL es encontrar la “mejor” de todas las soluciones factibles. De fi nición 1.5 (Mínimo global) Diremos que es un TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 18 mínimo global del problema PPNL o que tiene un mínimo global sobre , el conjunto factible de PPNL, si El punto x será mínimo global estricto si la desigualdad es estricta Esta definición implica que no hay en Ω un punto en el que la función tome un valor menor que el que toma en x . Definición 1.6 (Máximo global) Diremos que es un máximo global del problema PPNL o que tiene un máximo global sobre , el conjunto factible de PPNL, si El punto x será máximo global estricto si la desigualdad es estricta Esta definición implica que no hay en Ω un punto en el que la función tome un valor mayor que el que toma en x . Observación 1.4 Los máximos y mínimos globales de un problema de optimización se denominan extremos globales. Definición 1.7 (Solución óptima) Diremos que x Ω es una solución óptima del problema PPNL o que tiene un óptimo en x sobre el conjunto factible Ω si ocurre alguna de estas dos situaciones 1. x es un mínimo global del problema PPNL y el objetivo del problema es minimizar. 2. x es un máximo global del problema PPNL y el objetivo del problema es maximizar. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 19 Definición 1.8 (Valor óptimo) Si es una solución óptima del problema PPNL, entonces se define el valor óptimo como el valor de la función objeto en la solución óptima, es decir, si es una solución óptima del problema PPNL, entonces es el valor óptimo. Resolver un problema de optimización es encontrar, si existe, sus soluciones óptimas, es decir, los extremos globales de la función objetivo sobre el conjunto factible. Desde el punto de vista práctico y computacional en algunas ocasiones bastará con obtener los llamados extremos locales que se definen a continuación. Definición 1.9 (Mínimo local) Consideremos el problema de optimización PPNL y sea su conjunto factible. Diremos que es un mínimo local o relativo de en si y sólo si El punto x será un mínimo local estricto de en Ω si la desigualdad es estricta Definición 1.10 (Máximo local) Consideremos el problema general de optimización PPNL y sea su conjunto factible. Diremos que es un máximo local o relativo de en si y sólo si El punto x será un máximo local estricto de en Ω si la desigualdad es estricta Observación 1.5 Los máximos y mínimos locales de los problemas de optimización también se denominan extremos locales o relativos. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 20 A diferencia de los extremos globales que afectan a todo el conjunto factible Ω, los extremos locales afectan a cierto entorno a su alrededor. La teoría inicial asociada a la optimización está orientada a la obtención de condiciones necesarias y suficientes para que un punto sea óptimo. Por otra parte, también es interesante conocer no sólo si un punto es o no óptimo desde el punto de vista teórico, sino también cómo encontrar esos óptimos desde el punto de vista práctico. Teniendo esto en cuenta, al considerar problemas de optimización se plantean dos cuestiones: 1. ¿Cómo podemos determinar si un punto x es o no la solución óptima de un problema de optimización? ¿Qué condiciones deberían cumplir las funciones para que un problema PPNL tenga solución? ¿Qué condiciones debe cumplir el punto x ? 2. Si no es punto óptimo, entonces ¿cómo podemos encontrar una solución óptima utilizando la información de la función en ? Mientras que con la primera cuestión se trata de determinar condiciones necesarias y/o suficientes para que un punto sea o no una solución óptima, en la segunda de las cuestiones se consideran los métodos numéricos adecuados para conseguir encontrar esas soluciones óptimas. Un resultado básico utilizado para conocer si un problema de optimización tiene solución es el teorema de Weierstrass, que recordamos a continuación dentro del contexto de la optimización matemática. Teorema 1.1 (Teorema de Weierstrass) Sea una función continua definida sobre un conjunto compacto (cerrado y acotado) . Entonces el problema de optimización Tiene al menos una solución para ambos objetivos de minimización y maximización, es decir TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 21 Este es un resultado importante a tener en cuenta en la resolución de problemas de optimización, sin embargo el Teorema no nos proporciona un métodos para la localización de las soluciones, solamente de su existencia en determinadas condiciones. Desde el punto de vista de las aplicaciones, lo interesante es caracterizar los puntos solución y diseñar un método efectivo para su cálculo. Finalmente, apuntar que un problema de optimización puede tener solución única como en el siguiente planteamiento No tener ninguna solución, como en el problema O tener más de una solución, como en el problema En el que hay incluso infinitas soluciones óptimas, tanto de mínimo como de máximo TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 22 1.3 Convexidad 1.3.1 Conjuntos convexos El concepto de convexidad es de gran importancia en el estudio de los problemas de optimización desde el punto de vista de la aplicación práctica, puesto que en algunos casos, bajo condiciones de convexidad, se puede garantizar que un extremo local de un problema es realmente un extremo global y por tanto la solución óptima del problema buscada. Se describen en esta sección algunos conceptos básicos de convexidad útiles para el desarrollo de la programación matemática y aunque es posible definirlos en el ámbito de cualquier espacio topológico, en lo sucesivo consideraremos el espacio vectorial . Definición 1.11 (Segmento lineal) Dados dos puntos el segmento lineal cerrado que une x con y es el conjunto definida por Del mismo modo, el segmento lineal abierto que une x con y es el conjunto definida por Definición 1.12 (Conjunto convexo) Sea Ω ⊂ entonces Esta definición se interpreta de forma que un conjunto será convexo si el segment lineal cerrado que une cualquier par de puntos del conjunto está contenido en dicho conjunto. La figura 1.2 representa algunos conjuntos convexos y otros no convexos de . TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 23 Figura 1.2: Convexidad en R2 Por convenio el conjunto vacío es un conjunto convexo. Uno de los tipos más importantes de conjunto convexo es el hiperplano, que definimos a continuación. Definición 1.13 (Hiperplano) Sea . Un hiperplano H en en un conjunto definido como El vector a es el llamado vector normal al hiperplano. La expresión es el producto escalar de ambos vectores Definición 1.14 (Semiespacios) Sea . Sea H un hiperplano construido a partir de a y b entonces definimos los semiespacios cerrados positivos y negativos asociados a H, respectivamente a los conjuntos Y semiespacios abiertos positives y negativos asociados a H a los conjuntos definidos como TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 24 El siguiente lema es una consecuencia inmediata de la definición de convexidad y establece que la intersección de dos conjuntos convexos es convexa y que la suma algebraica de dos conjuntos convexos también es convexa. Lema 1.1 Sean dos conjuntos convexos, entonces 1. Ω1 ∩ Ω2 es convexo. 2. Ω 1 + Ω 2 = es convexo. 3. Ω 1 − Ω 2 = es convexo. Ejemplo. El conjunto definido como siendo P el problema P= Es un conjunto convexo Solución: Para demostrar la convexidad de S utilizaremos la definición. Distinguimos tres casos: 1. Ca so I: El problema P no tiene solución, en este caso S es el conjunto vacío , que por definición es un conjunto convexo. 2. C a so II : El problema P tiene solución única: . En este caso el único segmento lineal que se puede construir es (en este caso incluso indep e ndien te men t e d e s i es tá en e l in terv alo [0, 1] o no ) . 3. Caso III: El problema P tiene más de una solución. En este caso S tiene más de un elemento y podemos suponer que existe que por ser soluciones del problema P serán puntos factibles y por tanto cumplirán las restricciones del problema. x 1 , x 2 ≥ 0 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 25 Como además son mínimos de P ; si llamamos al valor óptimo se tiene Ahora hay que comprobar que los elementos del segmento lineal que une con también están en S es decir son soluciones de P. para ello tomamos y consideramos el punto definido por Comprobamos su factibilidad operando directamente. Por una parte es factible ya que por una parte cumple el sistema de ecuaciones Y por otra parte, como De donde al ser se obtiene Ya que todos los sumandos son positivos. De forma es factible porque cumple las restricciones del problema. Si ahora evaluamos la función objetivo en TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 32 Tabla: Condiciones de optimalidad Restricciones Condiciones necesarias Condiciones suficientes No cóncava cóncava General Condiciones KKT cóncava y convexas Las condiciones suficientes es añadida a que se cumple la necesaria. El trabajo de Karush [32] y posteriormente Kuhn y Tucker [33] constituyeron el gran avance en el desarrollo de las condiciones de optimalidad. Teorema: - Condiciones necesarias Sean funciones diferenciables que satisfacen ciertas condiciones de regularidad. Entonces puede ser una solución óptima para el problema de PNL, solo si existen m números que satisfagan las siguientes condiciones de Karush-Kuhn-Tucker (KKT): 1. 2. 3. 4. 5. 6. - Condiciones suficientes Sea cóncava y convexas (es decir, se trata de un problema de programación convexa), donde todas estas funciones satisfacen las condiciones de regularidad y satisface las condiciones KKT. Entonces, es una solución óptima. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 33 2.2.2 Programación lineal La programación lineal es el campo de la programación matemática dedicado a maximizar o minimizar (optimizar) una función lineal, denominada función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones expresadas mediante un sistema de ecuaciones o inecuaciones también lineales. El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a Joseph Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificación diaria. Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantoróvich, un matemático de origen ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975. En 1979, otro matemático ruso, Leonid Khachiyan, diseñó el llamado Algoritmo del elipsoide, a través del cual demostró que el problema de la programación lineal es resoluble de manera eficiente, es decir, en tiempo polinomial. Más tarde, en 1984, Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal, lo que constituiría un enorme avance en los principios teóricos y prácticos en el área. El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa (factorial de 70, 70!) ; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el planteamiento del problema como una programación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones factibles que deben ser revisadas. Asi pues un problema de programación lineal se puede expresar de la siguiente forma: Donde es el vector de variables objetivas que debe optimizarse. Los coeficientes de la función objetivo está representada por es una matriz de coeficientes representando las restricciones del problema lineal. Ax ≤ b podría escribirse como TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 34 (donde se refiere a la i-ésima fila del coeficiente de la matriz ). Todos los problemas lineales son convexos y generalmente se resuelven mediante métodos de punto interior o simplex. . Para más información sobre el origen y las propiedades matemáticas de estos métodos remito al lector al libro de Nocedal y Wright (2006). 2.2.3 Programación cuadrática La programación cuadrática (QP) es el nombre que se le da a un procedimiento que minimiza una función cuadrática de n variables sujeta a m restricciones lineales de igualdad o desigualdad. Un programa cuadrático es la forma más simple de problema no lineal con restricciones de desigualdad. La importancia de la programación cuadrática es debida a que un gran número de problemas aparecen de forma natural como cuadráticos (optimización por mínimos cuadrados, con restricciones lineales), pero además es importante porque aparece como un subproblema frecuentemente para resolver problemas no lineales más complicados. Las técnicas propuestas para solucionar los problemas cuadráticos tienen mucha similitud con la programación lineal. Específicamente cada desigualdad debe ser satisfecha como igualdad. El problema se reduce entonces a una búsqueda de vértices exactamente igual que se hacía en programación lineal. Un problema cuadrático es una generalización del problema lineal estándar, dónde la función objetivo contiene una parte cuadrática además del término lineal. La parte cuadrática está representada por una matriz . Por lo tanto, los problemas cuadráticos se pueden expresar en el siguiente manera: Dado que las restricciones son lineales y presumiblemente independientes la cualificación de las restricciones se satisface siempre, así pues, las condiciones de Karush-KuhnTucker son también condiciones suficientes para obtener un extremo, que será además un mínimo global si Q es definida positiva. Si Q no es definida positiva el problema podría no estar acotado o llevar a mínimos locales. La Programación Cuadrática juega un papel muy relevante en la teoría de optimización lineal y no lineal pues guarda una relación muy estrecha con la Programación Lineal y es un paso intermedio esencial para resolver eficazmente problemas generales de Programación No Lineal. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 35 A diferencia de los problemas lineales, no todos los cuadráticos son convexos. Un problema cuadrático es convexo si y solo si es semidefinida positiva ( no nulo). 2.2.4 Programación cónica La programación cónica se refiere a una clase de problemas diseñados para modelar problemas de optimización convexos. Un problema de programación cónica se puede expresar genéricamente de la siguiente forma: También llamado problema primal de la programación cónica, donde es el vector de variables de decisión, son datos conocidos referentes al problema y ⊂ es un cono convexo, cerrado con un interior no vacío. Los conos más relevantes que satisfacen estas propiedades son: - Octante positivo. - Cono de Lorentz o de segundo orden. - Cono positivo semidefinido. La forma estándar de CP como se da en la ecuación minimiza un objetivo lineal sobre un convexo cono ( b - Ax = s K). Como Nemirovski (2006) señala que la representación de CP en este formulario tiene dos ventajas principales. Primero, esta formulación tiene fuertes habilidades unificadoras, lo que significa solo algunos conos permiten modelar muchos tipos diferentes de OP. Además, las no linealidades ya no están representados por objetivos generales no lineales y funciones de restricción sino vectores y matrices que permiten a los algoritmos utilizar la estructura presente en los OP convexos. En segundo lugar, la convexidad está incorporada en la definición de CP. Al mismo tiempo, teóricamente,cualquier OP convexo puede reformularse en la forma dada en la ecuación. Por lo tanto no lineal las funciones objetivas se expresan en forma de epígrafe (véase, por ejemplo, Boyd y Vandenberghe 2004): TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 36 Prácticamente el número de problemas cónicos que se pueden resolver está limitado por el número de conos soportado por un solver de optimización dado. Los solucionadores de última generación distinguen entre hasta ocho tipos diferentes de conos. Siguiendo las definiciones en Diamond y Boyd (2015) y O'Donoghue y col. (2016), un cono convexo K suele ser un producto cartesiano de simples conos convexos de los siguientes tipos. 2.2.5 Programación entera mixta Un modelo de programación entera es aquel que contiene restricciones y una función objetivo idénticas a la formuladas en programación lineal, la única diferencia en que una o mas variables de decisión deben tomar valor entero en la solución final. Existen tres tipos de modelos por programación entera: A) PURA: Son modelos similares a los de programación entera. B) BINARIA: Estos modelos lineales, las variables sólo toman valores 0 y 1, son usadas para uso probabilístico. Donde 0 se rechaza la opción y 1 se acepta la opción. C) MIXTA: En estos tipos de modelos, integra las variables puras y las mixtas. Los tipos de restricciones más usadas en la Programación Entera Mixta son: 1) Excluyentes: Solo sirve para elegir una alternativa de varias posibles. 2) Pre-requisito: Cuando necesitas realizar una acción antes de proceder con la siguiente. 3) Incluyente: Dicha restricción se da para cuando realizas una acción "A" entonces debes hacer la acción "B". 4) Costo Fijo: Cuando se nombra un costo fijo, es sinónimo de uso de variable mixta. 2.2.5.1 Problemas de redes Los problemas de redes surgen en una gran variedad de situaciones. Las redes de transporte, eléctricas y de comunicaciones predominan en la vida diaria. La representación de redes se utiliza ampliamente en áreas tan diversas como producción, distribución, planeación de proyectos, localización de instalaciones, administración de recursos y planeación financiera, para nombrar sólo unos ejemplos. De hecho, una representación de redes proporciona un panorama general tan poderoso y una ayuda conceptual para visualizar las relaciones entre los componentes del sistema, que se usa casi en todas las TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 37 áreas científicas, sociales y económicas. Uno de los mayores desarrollos recientes en investigación operativa (IO) ha sido el rápido avance tanto en la metodología como en la aplicación de los modelos de optimización de redes. La aparición de algunos algoritmos ha tenido un impacto importante, al igual que las ideas de ciencias de la computación acerca de estructuras de datos y la manipulación eficiente de los mismos. En consecuencia, ahora se dispone de algoritmos y paquetes de computadora y se usan en forma rutinaria para resolver problemas muy grandes que no se habrían podido manejar hace dos o tres décadas. 2.2.5.2 Problemas del viajante El problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? 2.2.5.3 Problemas de ruta de vehículos Los problemas de rutas de vehículos son una generalización de problema del viajero. El problema del viajero (TSP) es uno de los más famosos y estudiados. En este problema, un viajante de comercio tiene que visitar un conjunto de clientes o ciudades, y regresar después al punto de partida. Antes de salir, deberá decidir en qué orden recorrer dichas ciudades para minimizar la distancia total recorrida. Señalar que tiene que pasar una sola vez por cada ciudad. 2.2.6 Otros problemas de optimización 2.2.6.1 Problemas Multiobjetivos En la vida real, existen numerosas situaciones y problemas que son reconocidos como problemas multiobjetivo, es decir, no poseen un único criterio medible por el cual pueda declararse que una solución sea completamente satisfactoria. Dicho de otra forma, este tipo de problemas contiene múltiples criterios que han de satisfacerse o que han de ser tenidos en cuenta. A menudo dichos criterios entran en conflicto unos con otros y no existe una única solución que simultáneamente satisfaga a todos. Por tanto, la solución que se pretenda obtener debe estar en concordancia con las preferencias del decisor. Los problemas de optimización de rutas de vehículos (VRP) se modelan normalmente TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 38 como un problema de optimización con un único objetivo, que minimiza el coste de llevar alguna mercancía a unos destinos, al tiempo que se satisfacen ciertas restricciones. No obstante, en la vida real se pueden tener en cuenta otros factores, como son: la minimización de distancias, minimizar tiempos de espera, buscar un equilibrio en las cargas de trabajo (tiempo, distancia,…) En la optimización multiobjetivo, cada una de las funciones objetivo representa una aptitud o un costo a optimizar, las cuales dependen de n parámetros. Sin pérdida de generalidad. En particular, la r-ésima aptitud está dada por una función y la función evaluadora del problema a optimizar está compuesta por dichas funciones de aptitud. Suponiendo que se deben optimizar m aptitudes, la función a optimizar es de la forma y el problema general está dado por: donde y la i-ésima restricción está dada por la proposición . En la búsqueda de la solución óptima del problema general, se trabaja sobre un espacio de posibles soluciones en , donde todas satisfacen un criterio multiobjetivo de optimalidad. En otras palabras, el objetivo es optimizar de manera simultánea todas las funciones objetivo, puesto que en la mayoría de los problemas no es posible encontrar un solo valor óptimo para todas ellas, ya que el óptimo de una función no necesariamente lo es para las demás (Zitzler et al., 2003). Para ampliar los problemas multiobjetivos pueden dirigirse a apartado [27] de la Bibliografia. 2.2.6.2 Optimización FUZZY Desde que Zadeh [28] introdujo el concepto de número difuso y Chang y Zadeh [29] propusieron la noción de aplicación difusa, se realizan numerosos estudios en las condiciones de optimalidad para los problemas difusos, problemas de programación matemática en los que la función objetivo es difusa. El agrupamiento difuso (en inglés, fuzzy clustering) es una clase de algoritmos de agrupamiento donde cada elemento tiene un grado de pertenencia difuso a los grupos. Este tipo de algoritmos surge de la necesidad de resolver una deficiencia del agrupamiento exclusivo, que considera que cada elemento se puede agrupar inequívocamente con los elementos de su cluster y que, por lo tanto, no se asemeja al resto de los elementos. Tras la introducción de la lógica difusa por Zadeh en 1965 surgió una solución para este problema, caracterizando la similitud de cada elemento a cada uno de los grupos [30]. Esto se logra representando la similitud entre un elemento y un grupo por una función, llamada función de pertenencia, que toma valores entre cero y uno. Los valores cercanos a uno indican una mayor similitud, mientras que los cercanos a cero indican una menor similitud. Por lo tanto, el problema del agrupamiento difuso se reduce a encontrar una caracterización de este tipo que sea óptima. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 39 Los algoritmos de agrupamiento difuso se han aplicado ampliamente en diferentes áreas como el procesamiento de imágenes, sistemas de ingeniería, estimación de parámetros, entre otras [31]. 2.2.6.3 Optimización global Optimización Global es una rama de la matemática aplicada y el análisis numérico que se ocupa de la optimización de una función o un conjunto de funciones de acuerdo a diferentes criterios. Un modelo en su forma estándar es la minimización de una función real en el espacio de los parámetros , o en el subespacio definido por las restricciones . (El problema de maximizar la función es equivalente a minimizar una función ). En muchos problemas de optimización no lineal, la función objetivo tiene un gran número de mínimos y máximos locales, encontrar un óptimo local es una tarea sencilla, usando métodos clásicos de optimización local. En estos casos encontrar un mínimo o un máximo global es una tarea de mayor complejidad, pues los métodos analíticos no se pueden utilizar en la gran mayoría de los casos y las estrategias numéricas traen consigo un número grande de problemas. Algunos de los casos en los que se puede usar un enfoque de optimización global son: - Predicción de la estructura de las proteínas (minimizar la energía/función de energía libre). - Filogenética computacional (por ejemplo, minimizar el número de transformaciones de caracteres del árbol). - Problema del viajante y el diseños de circuitos eléctricos (minimizar la longitud del camino). - Ingeniería química (por ejemplo, analizar la energía libre de Gibbs). - Verificación de seguridad, ingeniería de seguridad (por ejemplo, de estructuras mecánicas, edificios). - Análisis del caso peor. - Problemas matemáticos (por ejemplo, la conjetura de Kepler). - El punto de partida de numerosas simulaciones dinámicas moleculares que consisten en una optimización inicial de la energía del sistema a ser simulado. - Calibración de los modelos de propagación de radio y otros modelos en la ciencias y en la ingeniería. - Ajustes de curvas como el análisis mínimo cuadrático y otras generalizaciones, como el ajuste de los datos de modelos experimentales, en la química, física, medicina, astronomía y otros. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 40 Capítulo 3 Software 3.1 Visión general En este capítulo se hace revisión de las herramientas más importantes de optimización convexa que podemos encontrar. Se estudian las caracteristicas de cada programa de forma que podemos conocer cual es más adecuado para el problema que necesitemos resolver, en función de diferentes propiedades como su complejidad o facilidad de uso, condiciones comerciales de distribución, y la variedad de problemas y formatos de datos que admita. Los principales apartados que encontraremos corresponden a los tipos de programas que existen, que pueden ser de modelado o de resolución. Veremos la diferencia entre ambos. También he reservado un espacio para herramientas de optimización global orientadas a problemas no necesariamente convexos. Al final del capítulo se incluye un ejemplo de problema cuadrático que nos permite comparar el procedimiento de utilización de varias herramientas, y que también sieve para visualizar de forma intuitiva la estructura de los problemas que estamos tratando. En estos momentos es posible para un usuario adquirir una gran variedad de aplicaciones que resuelven problemas de optimización, pero estos pueden ser de una naturaleza muy diversa, por lo que cada herramienta se centra en la resolución de un tipo o de un grupo más o menos amplio de problemas. Por ejemplo, si buscamos herramientas de optimización lineal, la cantidad de programas que encontramos en el mercado es innumerable; incluso en las hojas de cálculo de los paquetes de ofimática más populares se pueden resolver. Cuando los problemas son convexos, las técnicas disponibles de resolución permiten una altísima eficiencia en cuanto a tiempo de convergencia, dimensiones de las variables, y cantidad de funciones de restricción que podemos indicar. Podemos distinguir entre los programas específicos de resolución (solvers), que suelen estar especializados en algún tipo de problema (lineales, cuadráticos, cónicos, etc.); y por otro lado los sistemas de modelado, que se encargan de automatizar las transformaciones necesarias para convertir un problema en su formato estándar. Los solvers corresponden a un nivel bajo de programación, en el sentido de que son más complicados para el usuario, y están enfocados a aplicar un determinado algoritmo para un tipo de problema en concreto. Normalmente forman parte del “núcleo” de los TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 41 programas de modelado, que a su vez, pueden utilizar una gran cantidad de solvers para resolver en cada caso un conjunto variado de problemas. Los sistemas de modelado proporcionan un nivel alto de programación. No están especializados en un tipo de problema concreto, porque para eso cuentan con varios solvers una vez que han transformado el problema genérico para el que se utilizan. 3.2 Herramientas de resolución La cantidad de herramientas disponibles en el mercado para resolución de problemas de optimización es muy grande. En esta sección se analizan algunas de ellas agrupándolas por el tipo de problemas que resuelven. Veremos que la selección por el tipo de problemas abarcado no es un criterio exacto, porque muchos solvers pueden tratar más de un tipo de problemas. Por ejemplo, las herramientas de resolución cuadrática resuelven también problemas lineales, ya que estos se pueden ver como un caso particular de los anteriores. En definitiva, para asignar cada herramienta a un tipo de problema me he basado en la clasificación que de ellas hacen los programas de modelado que las incluyen. 3.2.1 Problemas Lineales Este grupo de programas es el más extenso. En este apartado presentamos o introducimos lp_solve, GLPK6, BPMPD y MINOS, aunque en el entorno académico puede resultar más accesible utilizar en Matlab el comando linprog del complemento Matlab Optimization Toolbox o incluso los solvers de Microsoft Excel y OpenOffice. 3.2.1.1 lp_solve Es un programa de resolución de problemas lineales que utiliza el método símplex y el de ramificar y acotar (Branch-and-Bound) para problemas de variables enteras y conjuntos especiales ordenados. La información sobre esta herramienta procede de [10]. El tamaño de modelo admitido no tiene límite, y la entrada de datos y especificaciones se hace básicamente de tres formas: • Por medio de las bibliotecas de interfaz de programación. • Con ficheros de entrada. • A través del entorno integrado de desarrollo. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 48 • Licencia de prueba para 30 días. • Licencia libre para uso académico, que está limitada a 90 días y contiene todas las características del producto. 3.2.3.2 SeDuMi Es un paquete que se utiliza para resolver problemas de optimización sobre conos simétricos. Esto incluye problemas lineales, cuadráticos, semidefinidos, cónicos, y cualquier combinación de los anteriores. La información sobre esta herramienta la he obtenido de [16], y según se indica en esta cita, está inspirado en una técnica conocida como empotrado auto-dual publicada en [26], que consiste en optimizar sobre conos homogéneos autoduales (cono cuyo dual es él mismo). Esto permite resolver algunos problemas en una sola fase, que lleva a la solución óptima o a una certificación de inviabilidad. Sus características más destacables son las siguientes: • Permite utilizar valores complejos. • Genera soluciones duales en problemas no viables. • Aprovecha las matrices dispersas para acelerar la ejecución. • Gestiona las columnas densas de forma separada, y con ello favorece la dispersión. • Puede importar problemas lineales en formato mps y problemas semidefinidos en formato sdpa. SeDuMi se distribuye de forma gratuita bajo los términos de código libre GPL. 3.2.3.3 SDPT3 Esta herramienta está diseñada para resolver problemas cónicos en los que el cono de las restricciones puede ser el producto de conos semidefinidos, conos de segundo orden, ortantes no negativos, o espacios euclídeos. La función objetivo es la suma de funciones lineales y términos de barrera logarítmica asociados con los conos de las restricciones. La información de esta herramienta procede del manual [17]. El código está escrito en Matlab, aunque también contiene rutinas escritas en C. Su funcionamiento se basa en un algoritmo de seguimiento de camino primal-dual no viable. Esto es una variante del algoritmo primaldual en el que se utilizan dos versiones del paso de Newton. Una de ellas está relacionada con este mismo sistema de ecuaciones, y se conoce como dirección NT (Nesterov-Todd), y la otra intenta linealizar una versión simétrica del mismo (llamada dirección HKM (Helmberg-Rendl-Vanderbei-Wolkowick (1996), Kojima-Shindoh-Hara (1997), Monteiro (1995))). Sus características más destacables son: TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 49 • Permite utilizar variables libres. • Se pueden resolver problemas de maximización de determinantes. • Puede resolver SDPs con datos complejos. • Se basa en un modelo de 3 parámetros con restricciones en conos homogéneos autoduales, de forma semejante a SeDuMi. SDPT3 se distribuye bajo los términos de licencia pública general de GNU GPL 2.0, por lo que no es compatible para aplicaciones comerciales, aunque en este último caso las empresas se pueden poner en contacto con los autores para personalizar alternativas. 3.2.3.4 PENSDP Es un programa para resolver problemas de tipo semidefinido, que tienen una función de objetivo lineal, y desigualdades matriciales lineales como restricciones. Está orientado a problemas SDP a gran escala con matrices densas o dispersas. Las principales características son: • Ahorro de utilización de memoria por liberación del hessiano. • Solución iterativa para el sistema de Newton. • Criterios de parada basados en la medida de error DIMACS (21Center for Discrete Mathematics and Theoretical Computer Science), que da como resultado unos cálculos más fiables. • Modo híbrido para la solución del sistema de Newton. • Orientado a problemas a gran escala. • Tratamiento eficiente de distintos patrones de dispersión en los datos del problema. • Detección de no viabilidad. Se puede utilizar como programa autónomo, con ficheros de entrada en formato de SDPA (SemiDefinite Programming Algorithm), y también se puede utilizar desde Matlab, como función desde las herramientas de modelado TOMLAB o YALIMP. Otra opción es utilizarlo como rutina que se puede llamar desde los lenguajes de programación C o Fortran. En este último caso los datos se comunican en forma de parámetros de dichas rutinas. PENOPT se distribuye bajo una licencia comercial, que se puede comprar en diferentes formatos, dependiendo de su utilización para una empresa, un departamento, o un usuario único. También hay otras modalidades para uso académico, a nivel de universidad, departamento o usuario único, con precios más reducidos. Por otro lado, también existe una licencia gratuita para desarrolladores, orientada a usuarios en entorno académico, y está limitada a tres meses, pudiendo renovarse cuando se necesite. Esta licencia se ofrece a investigadores que desarrollen y prueben software TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 50 de optimización y utilicen PENOPT para pruebas, o también si lo necesitan para desarrollar software en aplicaciones que requieran resolver problemas de optimización. Además, existe una licencia de evaluación para usuarios comerciales, que expira en un mes y no se puede renovar. Esta licencia no es gratuita, aunque su precio se descuenta si finalmente se compra una licencia definitiva antes de un plazo determinado. 3.2.4 Sistemas de Modelado Los sistemas de modelado proporcionan un lenguaje comprensible que permite al usuario expresar su problema centrando su esfuerzo en definirlo correctamente, dejando en manos del programa la conversión a otro formato compatible con las herramientas de resolución que forman parte del núcleo del sistema de modelado. Todas estas transformaciones del modelo descrito por el usuario producen otro problema o conjunto de problemas en un formato estándar y su mecanismo interno consiste básicamente en técnicas como pueden ser los cambios de variables, eliminar o añadir restricciones, utilizar variables de holgura, y otros recursos que podemos ampliar en [18]. Después de todas estas transformaciones, el sistema de modelado se encarga de elegir el solver más adecuado para el tipo de problema tratado. A partir de ahí, interpreta el resultado, indicando si es o no viable, y nos devuelve la solución óptima si es posible, adaptándola de nuevo al formato original. En esta sección se describen las cuatro herramientas sobre las que he encontrado mayor número de referencias en la bibliografía que he consultado sobre optimización convexa: CVX, AMPL, GAMS y YALIMP. Si bien este criterio de selección no es demasiado riguroso, ya que quedan sin tratar herramientas de gran calado en el mercado como AIMMS, TOMLAB, LINGO, etc., lo que persigue es presentar una muestra significativa de las características de este tipo de programas, aunque limitada para no extender excesivamente el tamaño de este TFG. 3.2.4.1 CVX CVX se utiliza integrada como complemento de Matlab. El trabajo con esta herramienta se basa en lo que llaman programación convexa disciplinada, que consiste en un conjunto de reglas que aseguran que expresamos nuestro problema de forma convexa. El programa aporta una biblioteca de funciones convexas que sirven de base para que el usuario construya las funciones y conjuntos del problema aplicando operaciones que conserven la convexidad. Las restricciones y funciones objetivo que se construyen con estas reglas se transforman automáticamente en forma canónica, y a partir de ahí se resuelve con los programas de resolución. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 51 También se pueden resolver problemas geométricos, ya que CVX los transforma a un formato convexo, y una vez resuelto se devuelve el resultado en su formato original. La información sobre CVX de este apartado procede del manual [19]. Los programas de resolución que utiliza son SDPT3 y SeDuMi. CVX se distribuye como software libre bajo los términos de GNU-GPL. Los derechos de copia están a nombre de Michael Grant y Stephen Boyd. 3.2.4.2 AMPL AMPL es un lenguaje de programación para modelado algebraico en problemas de optimización lineales y no lineales, con variables discretas y continuas, y fue desarrollado en los laboratorios Bell. Su utilización está orientada al desarrollo de prototipos y para trabajar en producción repetitiva. La información de esta herramienta procede de [20]. Soporta la definición de conjuntos y operaciones de conjuntos. También se caracteriza por un tipo de sintaxis muy general y natural para describir expresiones aritméticas, lógicas y condicionales, así como para sumatorios y otros operadores de iteración. Incluye características de programación no lineal como la posibilidad de especificar valores iniciales para los problemas primal y dual, funciones definidas por el usuario, diferenciación automática, y eliminación automática de variables definidas. Se puede utilizar para problemas de redes, para lo que incluye indicaciones específicas para declarar nodos y arcos, y una sintaxis especial para funciones lineales por tramos. Se opera por medio de un entorno de comandos interactivo con opciones para procesos en segundo plano. Hay comandos que permiten visualizar cualquier componente o expresión del modelo, a través de la pantalla o escribiéndolo en un fichero que utiliza un formato automático o según las preferencias del usuario. En AMPL los datos del problema están separados del modelo, por lo que éste contiene un sistema abstracto de variables, objetivos y restricciones que representa la forma general del problema a resolver, mientras que los datos se recopilan después de haber definido el modelo, creando un caso específico del problema. De esta forma, los modelos se mantienen de forma concisa incluso cuando los conjuntos y las tablas de datos aumentan. Los modelos pueden incorporar muchos tipos de condiciones para validar los datos, y se incluyen interfaces con las herramientas de resolución. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 52 El entorno de AMPL permite la conexión con una gran cantidad de herramientas de resolución, y en muchos casos este software de enlace no supone un coste adicional. • Para programación lineal - Variable continua: BPMPD, Mosek, y LOQO, entre otros. - Variable entera: MINTO, LAMPS, lp_solve, etc. - Redes: CPLEX, OSL • Para programación no lineal - Cuadrática: CPLEX, Mosek, OSL - Convexa: Mosek, SOPT - Continua: CONOPT, KNITRO, LANCELOT, etc. - Entera: MINLP AMPL está sujeto a una licencia comercial, que se puede comprar para máquinas individuales o en forma de licencias flotantes, y se ofrecen para una gran cantidad de plataformas. El modo flotante se puede utilizar cuando el número de usuarios es mayor que el de licencias, y se consigue con un servidor de autorizaciones en una red. Se puede descargar una versión de evaluación en la que podemos utilizar hasta 300 variables y 300 restricciones y objetivos. Nos podemos encontrar una versión académica cuyas características son:  Los tamaños de los problemas no están restringidos.  Se incluyen solucionadores comerciales de alta calidad y con todas las funciones.  AMPL y los solucionadores se proporcionan en un único archivo comprimido para cada plataforma, que puede distribuir libremente a los estudiantes que desean una instalación en sus propias computadoras.  Los archivos AMPL y solucionadores distribuidos se activan durante la duración del curso y dejan de funcionar una vez que finaliza el curso.  Solo se debe enviar un breve formulario de solicitud para cada oferta de cursos. Esta opción se usa tanto para enseñar la optimización como para incluir la optimización en la enseñanza de otras materias. Los temas de las clases de optimización que usaban AMPL para los cursos incluyen:  Programación lineal.  Optimización lineal y no lineal. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 53  Optimización combinatoria.  Investigación de operaciones deterministas.  Optimización de red.  Control óptimo. Una variedad de materias utilizó AMPL para introducir la optimización en la enseñanza. Los siguientes son una muestra representativa:  Sistemas de fabricación.  La investigación de operaciones.  Gestión de la cadena de suministro.  Operaciones de transporte público.  Econometría.  Finanzas.  Ingeniería Ambiental.  Ingeniería Química.  Redes de comunicaciones.  Planificación. También se incluye la posibilidad de comprar a la misma empresa algunas de las herramientas de resolución como Gurobi, CONOPT, KNITRO, SNOPT y MINOS. 3.2.4.3 GAMS Se trata de un sistema de modelado para programación matemática y optimización que consiste en un compilador de lenguaje y una serie de herramientas de resolución de alto rendimiento. La información de esta herramienta procede de [21]. Este sistema es especialmente útil cuando el problema a resolver es de grandes dimensiones, y que pueden requerir muchas revisiones para establecer un modelo adecuado. Se puede encontrar en versiones para ordenadores personales y para grandes servidores. GAMS facilita la descripción del problema haciendo que el modelado se haga de forma compacta y natural, permitiendo que el usuario pueda cambiar fácil y rápidamente la TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 54 formulación, o la selección de uno u otro solver, o incluso se puede pasar de un modelo lineal a no lineal sin mayor problema. El usuario se libera de tareas específicas del ordenador o servidor en que se instala, como por ejemplo calcular direcciones, asignaciones de almacenamiento, enlazado de subrutinas, o control de flujo. GAMS aumenta el tiempo disponible para conceptualizar y ejecutar el modelo, y analizar el resultado. Este sistema requiere especificaciones concisas y exactas sobre las entidades y sus relaciones. El lenguaje GAMS es formalmente similar a otros lenguajes de programación comunes, por lo que es familiar para cualquiera con experiencia en programación. Los datos se introducen en forma de lista y de tabla. Los modelos se describen con sentencias algebraicas concisas fáciles de leer tanto para los usuarios como para las máquinas. Se pueden describir conjuntos completos de restricciones relacionadas en una sola orden, para que después GAMS genere automáticamente cada ecuación de restricción, permitiendo que el usuario añada excepciones cuando la generalidad no sea aplicable. Las órdenes se pueden reutilizar sin tener que cambiar el álgebra en otros problemas semejantes. El usuario puede programar fácilmente un modelo para que se resuelva condiferentes valores en algún elemento, y a continuación generar un listado de soluciones para cada caso. Los modelos se desarrollan y documentan simultáneamente porque el usuario puede incluir textos explicativos como parte de la definición de cualquier símbolo o ecuación. GAMS incluye una gran cantidad de herramientas de resolución, como CPLEX, Gurobi, Mosek, entre otras. Estos solvers permiten resolver problemas de tipo LP, MIP, MIQCP (Mixed Integer Quadratically Constrained Program), NLP (Non-Linear Program), MINLP, CNS (Constrained Non-Linear System), MCP (Mixed Complementarity Problem) MPEC (Mathematical Program with Equilibrium Constraints). GAMS se compra con licencia comercial para empresas, y hay precios diferentes para uso académico. Se puede obtener para un solo usuario o para múltiples máquinas, y el precio depende de la arquitectura y de los solvers que se deseen. Las licencias de estos últimos se tienen que comprar con el paquete GAMS. Existe también una versión de demostración limitada a 300 restricciones y variables, con 2000 elementos distintos de cero, y con 50 variables discretas. En el caso de utilizar un solver de optimización global (no convexo) el número de variables y restricciones está limitado a 10. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 55 3.2.4.4 YALIMP YALIMP se utiliza como un complemento (toolbox) gratuito para Matlab, y sirve para modelar problemas de optimización convexos y no convexos. El lenguaje es consistente con la sintaxis de Matlab, por lo que es muy fácil de aprender para usuarios familiarizados con este entorno. Implementa una gran cantidad de recursos de modelado, permitiendo que el usuario se concentre en el modelo a alto nivel, mientras que YALIMP se ocupa del modelado a bajo nivel para obtener modelos eficientes y numéricamente satisfactorios. Soporta todos los tipos de problemas que hemos visto, lineales, cuadráticos, cónicos de orden 2, semidefinidos, geométricos, y otros más como por ejemplo los problemas cónicos con mezcla de variables enteras. Una de las ideas centrales de YALIMP es concentrarse en el lenguaje y en los algoritmos de alto nivel, dejando los verdaderos cálculos de optimización para los solvers externos. Sin embargo, también implementa algoritmos internos de optimización global no convexa, programación con mezcla de enteros, programación multiparamétrica, programación de suma de cuadrados y optimización robusta. Estos algoritmos se basan típicamente en el lenguaje de bajo nivel disponible en YALIMP, y resuelven subproblemas utilizando herramientas externas de resolución. • Para programación lineal: - Con licencia libre: CDD, GLPK, lp_solve, QSOPT - Con licencia comercial o libre en versiones académicas: BINTPROG, CPLEX, Gurobi, linprog (de Matlab Optimization Toolbox), Mosek • Para programación cuadrática: - Con licencia libre: BPMPD, CLP, OOQP, QPC - Con licencia comercial o libre en versiones académicas: CPLEX, Mosek, NAG, quadprog (de Matlab Optimization Toolbox), Xpress • Para programación cónica de segundo orden: - Con licencia libre: SDPT3, SeDuMi - Con licencia comercial o libre en versiones académicas: CPLEX, Mosek • Para programación semidefinida: - Con licencia libre: CSDP, DSDP, SDPA, SDPLR, SDPT3, SeDuMi - Con licencia comercial o libre en versiones académicas: LMILAB, PENBMI, PENSDP • Para programación no lineal en general y otros solvers: fmincon (de Matlab Optimization Toolbox), GPPOSY, IPOPT, KYPD, LMIRANK, MPT, PENNON, SNOPT, VSDP TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 56 La versión actual de YALIMP es libre de cargo y se distribuye de forma abierta. Esta disponibilidad implica que no cubre ningún servicio de garantía. 3.2.4.5 Entorno R R es un entorno y lenguaje de programación con un enfoque al análisis estadístico [22] y [23]. R nació como una reimplementación de software libre del lenguaje S, adicionado con soporte para alcance estático. Se trata de uno de los lenguajes de programación más utilizados en investigación científica, siendo además muy popular en los campos de aprendizaje automático (machine learning), minería de datos, investigación biomédica, bioinformática y matemáticas financieras. A esto contribuye la posibilidad de cargar diferentes bibliotecas o paquetes con funcionalidades de cálculo y representación gráfica. R es parte del sistema GNU y se distribuye bajo la licencia GNU GPL. Está disponible para los sistemas operativos Windows, Macintosh, Unix y GNU/Linux. 3.3 Algunos ejemplos de modelado 3.3.1 MPS MPS (Sistema de Programación Matemática) es un formato de archivo para la presentación y archivo de programación lineal (LP) y de programación entera mixta. El formato fue nombrado después de uno de los primeros IBM producto LP y se ha convertido en un estándar de facto ASCII medio entre la mayoría de los solucionadores comerciales del LP. Esencialmente todos los solucionadores comerciales del LP aceptan este formato, y también es aceptada por el código abierto COIN-O sistema. Sin embargo, con la aceptación de lenguajes de modelado algebraicas el uso de MPS ha disminuido. Por ejemplo, de acuerdo con las NEOS estadísticas del servidor en enero de 2011 a menos de 1% de las presentaciones eran en forma de MPS en comparación con 59,4% de AMPL y 29,7% de GAMS presentaciones. Aquí hay un pequeño modelo de ejemplo escritos en formato de MPS: NAME TESTPROB ROWS N COST TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 57 L LIM1 G LIM2 E MYEQN COLUMNS XONE COST 1 LIM1 1 XONE LIM2 1 YTWO COST 4 LIM1 1 YTWO MYEQN -1 ZTHREE COST 9 LIM2 1 ZTHREE MYEQN 1 RHS RHS1 LIM1 5 LIM2 10 RHS1 MYEQN 7 BOUNDS UP BND1 XONE 4 LO BND1 YTWO -1 UP BND1 YTWO 1 ENDATA A modo de comparación, aquí es el mismo modelo escrito en un formato orientado a ecuación: Optimize COST: XONE + 4*YTWO + 9*ZTHREE Subject To LIM1: XONE + YTWO <= 5 LIM2: XONE + ZTHREE >= 10 MYEQN: - YTWO + ZTHREE = 7 Bounds XONE <= 4 -1 <= YTWO <= 1 End El BOUNDS inferior de XONE es o bien 0 ó ( , dependiendo de la aplicación, ya que no se especifica. Curiosamente, no hay nada en formato MPS especifica la dirección de la optimización, y no hay una dirección estándar "por defecto"; algunos solucionadores LP maximizarán, si no se indica lo contrario, otros minimizarán, y otros darán más prioridad a la seguridad y no tienen ningún defecto y requieren una selección, en alguna parte, de un programa de control o mediante un parámetro. Si el modelo está formulado para la TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 64 **** SOLVER STATUS 1 NORMAL COMPLETION **** MODEL STATUS 1 OPTIMAL **** OBJECTIVE VALUE RESOURCE USAGE, LIMIT 0.401 1000.000 ITERATION COUNT, LIMIT 5 10000 GAMS/Cplex Mar 5, 2020 WIN.CP.CP. 19.3 016.014.038.WAT For Cplex 6.6 Cplex 6.6.1, GAMS Link 16, Using a GAMS/Cplex demo license installed at runtime. Optimal solution found. Objective : 93.500000 LOWER LEVEL UPPER MARGINAL ---- EQU COSTE 1.000 COSTE coste total de transporte [miles de euros] ---- EQU CAPACIDAD capacidad máxima de cada fábrica i [cajas] LOWER LEVEL UPPER MARGINAL VIGO -INF 350.000 350.000 -0.030 ALGECIRAS -INF 650.000 700.000 ---- EQU DEMANDA satisfacción demanda de cada mercado j [cajas] LOWER LEVEL UPPER MARGINAL MADRID 400.000 400.000 +INF 0.050 BARCELONA 450.000 450.000 +INF 0.150 VALENCIA 150.000 150.000 +INF 0.110 ---- VAR X cajas transportadas entre fábrica i y mercado j [cajas] LOWER LEVEL UPPER MARGINAL VIGO .MADRID . . +INF 0.040 VIGO .BARCELONA . 350.000 +INF . VIGO .VALENCIA . . +INF 0.010 ALGECIRAS .MADRID . 400.000 +INF . ALGECIRAS .BARCELONA . 100.000 +INF . ALGECIRAS .VALENCIA . 150.000 +INF . LOWER LEVEL UPPER MARGINAL ---- VAR CT -INF 03.500 +INF CT coste de transporte [miles de euros] **** REPORT SUMMARY : 0 NONOPT 0 INFEASIBLE 0 UNBOUNDED EXECUTION TIME = 0.030 SECONDS 0.7 Mb WIN-19-115 **** FILE SUMMARY INPUT D:\TR.GMS OUTPUT D:\TR.LST TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 65 Capítulo 4 Ejemplos de uso de software de optimización 4.1 Problemas de optimización lineal Veamos cómo se pueden resolver problemas de optimización lineal con R a través de algunos ejemplos sencillos. La mayor parte de las funciones necesarias pueden encontrarse en el paquete lp_solve [25] que a su vez esta basado en el proyecto de código abierto lp_Solve. Otro paquete alternativo que también se puede usar es linprog. 4.1.1 El paquete lpSolve Un problema en forma canónica Como ejemplo vamos a usar el siguiente problema: Un pastelero dispone de 150 kg de harina, 22 kg de azúcar y 27.5 kg de mantequilla para elaborar dos tipos de pasteles (A y B). Cada caja de pasteles de tipo A requiere 3 kg de harina, 1 kg de azúcar y 1 kg de mantequilla y su venta le reporta un beneficio de 20 euros. Cada caja de pasteles de tipo B requiere 6 kg de harina, 0.5 kg de azúcar y 1 kg de mantequilla y su venta le reporta un beneficio de 30 euros.¿Cuántas cajas de cada tipo debe elaborar el pastelero de manera que se maximicen sus ganancias? (Se supone en principio que también puede elaborar cajas incompletas, es decir, que no se trata de un problema de programación entera.) La forma canónica de un problema de optimización lineal es . La función canónica del problema que vamos a resolver como ejemplo es: TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 66 Para resolverlo basta llamar a la función lp y pasarle como argumentos de forma ordenada los parámetros que definen el problema. El orden de los parámetros es el siguiente: 1. “min” o “max” en función de si el problema es de minimización o maximización respectivamente. 2. El vector de coeficientes de la función objetivo. En el ejemplo . 3. La matriz de coeficientes de las variables en las ecuaciones quew definen las restricciones. En el ejemplo, 4. Un vector que determine la dirección de las restricciones . En el ejemplo las desigualdades son del tipo . 5. El vector con los términos independientes de las restricciones. En el ejemplo . Por defecto se supone que las variables de decisión no pueden ser negativas. El siguiente código define todos los parámetros del problema y se los pasa como argumentos a la función lp en el orden que hemos indicado: Library(lp_solve) #Parametros del problema coef <- c(20, 30) A <- matriz(c(3, 1, 1, 6, 0.5, 1), ncol=2) b <- c(150, 22, 27.5) dir <- rep(‘<=’, 3) # Solucion solucion <- lp(‘max’, coef, A, dir, b) el objeto solución que hemos generado al ejecutar la última línea es una lista con diversos elementos entre los cuales los más importantes son objval, el valor objetivo óptimo, y solution, las coordenadas de la solución factible óptimo del problema: TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 67 solución$objval ## [1] 775 Solución$solution ## [1] 5.0 22.5 Esto significa que la producción óptima del pastelero es de 5 cajas de A y 22.5 cajas de B, con lo que tendrá un beneficio máximo de 775 euros. Programación entera Supongamos ahora que el pastelero solo puede fabricar un número entero de cajas de cada tipo, es decir, que las variables solo pueden tomar valores enteros. La forma de indicar esta restricción adicional es añadiendo en la función lp el argument all.int=TRUE (también existe la posibilidad de restringir únicamente un subconjunto de las variables): solución <- lp(‘max’, coef, A, dir, b, all.int=TRUE) solución$objval ## [1] 770 solución$solution ## [1] 4 23 En este caso, la producción óptima del pastelero es de 4 cajas de A y 23 cajas de B con un beneficio de 770 euros. Problema de transporte El paquete lp_solve incluye también la función lp.transport para resolver el problema de transporte. Como ejemplo, vamos a resolver el problema de tramsporte definido por los siguientes datos: 3 4 6 8 9 30 2 2 4 5 5 80 2 2 2 3 3 10 3 3 2 4 2 60 10 50 20 80 20 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 68 Las filas corresponden a los lugares de origen y las columnas a los lugares de destino. Los valores de la matriz de costes de transporte desde cada origen a cada destino. El último elemento de cada fila es la oferta de producto en cada origen. El último elemento de cada columna es la demanda total en cada destino. A continuación definimos todos los parámetros del problema y los pasamos como argument de lp.transport en el orden adecuado: cost <- matrix(c(3, 2, 2, 3, 4, 2, 2, 3, 6, 4, 2, 2, 8, 5, 3, 4, 9, 5, 3, 2), ncol=5) direction <- ‘min’ row.signs <- rep(‘=’, 4) row.rhs <- c(30, 80, 10, 60) col.signs <- rep(‘=’, 5) col.rhs <- c(10, 50, 20, 80, 20) lp.transport(cost, direction, row.signs, row.rhs, col.signs, col.rhs) ## Success: the objective function is 610 lp.transport(cost, direction, row.sings, row.rhs, col.signs, col.rhs)$solution ## [,1] [,2] [,3] [,4] [,5] ## [1,] 10 20 0 0 0 ## [2,] 0 30 0 50 0 ## [3,] 0 0 0 10 0 ## [4,] 0 0 20 20 20 La solución óptima del problema es transporte 10 desde el origen 1 hasta el destino 1, 20 desde el origen 1 hasta el destino 2, 30 desde el origen 2 hasta el destino 2, etc. esta solución óptima conllevan un coste de 610. Problema de asignación Para resolver el problema de asignación el paquete lp_solve incluye la función lp.assign. como ejemplo, vamos a resolver el problema de asignación definido por la matriz: Las filas representan a los trabajadores y las columnas a las tareas. Cada elemento de la matriz corresponde el coste de asignar la tarea I al trabajador j. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 69 A continuación definimos la matriz de costes, que es el único argument de lp.assign: cost <- matriz(c(15, 9, 10, 10, 15, 12, 9, 10, 8), nrow=3) lp.assign(cost) ## Success: the objective function is 27 lp.assign(cost)$solution ## [,1] [,2] [,3] ## [1,] 0 1 0 ## [2,] 1 0 0 ## [3,] 0 0 1 La solución óptima es asignar la tarea 1 al trabajador 2, la tarea 2 al trabajador 1 y la tarea 3 al trabajador 3, todo con un coste de 27. 4.1.2 El paquete linprog Una alternativa a la función lp de lp_solve es la función solveLP del paquete linprog. Su funcionamiento es similar, aunque el rango de problemas que puede resolver es menor. Por ejemplo, no trata adecuadamente problemas en forma estándar con restricciones de igualdad. El orden por defecto en el que hay que pasar los argumentos es diferente al de lp: 1. Coeficientes de la función objetivo c. 2. Términos independientes de las restricciones b. 3. Matriz de coeficientes de las variables en las restricciones A. 4. Determinar si queremos maximizar o minimizar (maximum=TRUE o maximum=FALSE). 5. Vector que determina la dirección de las restricciones: . library(linprog) # Parametros del problema coef <- c(20, 30) A <- matrix(c(3, 1, 1, 6, 0.5, 1), ncol=2) b <- c(150, 22, 27.5) dir <- rep(‘<=’, 3) TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 70 # Solucion solución <- solveLP(coef, b, A, maximum=TRUE, dir) summary(solución) ## ## ## Result of Linear Programming / Linear Optimization ## ## Solution ## opt ## 1 5.0 ## 2 22.5 La función solveLP tiene la ventaja sobre lp de dar más información sobre los pasos intermedios del algoritmos simplex utilizado para resolver el problema. Para el máximo nivel de detalle se usa la opción verbose=4. solveLP(coef, b, A, maximum=TRUE, dir, verbose=4) ## [1] @initial Tableau” ## 1 2 S 1 S 2 S 3 P0 ## 1 3 6.0 1 0 0 150.0 ## 2 1 0.5 0 1 0 22.0 ## 3 1 1.0 0 0 1 27.5 ## Z-C -20 -30.0 0 0 0 0.0 ## ## Pivot Column: 2 ( 2 ) ## Pivot Row: 1 ( 1 ) ## ## 1 2 S 1 S 2 S 3 P0 ## 2 0.50 1 0.16667 0 0 25.0 ## 2 0.75 0 -0.08333 1 0 9.5 ## 3 0.50 0 -0.16667 0 1 2.5 ## Z-C -5.00 0 5.00000 0 0 750.0 ## ## Pivot Column: 1 ( 1 ) ## Pivot Row: 3 ( 3 ) ## ## 1 2 S 1 S 2 S 3 P0 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 71 ## 2 0 1 0.3333 0 -1.0 22.50 ## 2 0 0 0.1667 1 -1.5 5.75 ## 1 1 0 -0.3333 0 2.0 5.00 ## Z-C 0 0 3.3333 0 10.0 775.00 ## ## ## Result of Linear Programming / Linear Optimization ## ## Objective function (Maximum): 775 ## ## Iterations in phase 1: 0 ## Iterations in phase 2: 2 ## Solution ## opt ## 1 5.0 ## 2 22.5 ## ## Basic Variables ## opt ## 1 5.0 ## 2 22.5 ## S 2 5.75 ## ## Constraints ## actual dir bvec free dual dual.reg ## 1 150.0 <= 150.0 0.00 3.33333 34.50 ## 2 16.25 <= 22.0 5.75 0.00000 5.75 ## 3 27.50 <= 27.5 0.00 10.00000 2.50 ## ## All Variables (including slack variables) ## ## opt cvec min.c max.c marg marg.reg ## 1 5.00 20 15 30.00000 NA NA ## 2 22.50 30 20 40.00000 NA NA ## S 1 0.00 0 -Inf 3.33333 -3.33333 34.5 ## S 2 5.75 0 -20 6.66667 0.00000 NA ## S 3 0.00 0 -Inf 10.00000 -10.00000 2.5 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 72 4.2 Problemas de optimización cuadrática Tras una previa investigación teórica concluimos que una de las principales diferencias de la programación no lineal con respecto a la programación lineal, es que el punto óptimo no tiene por qué encontrarse en los puntos extremos de nuestra región factible, es más, puede encontrarse en el interior de nuestra región mientras que en el caso de la programación lineal nunca se encontrará en el interior. Resolución con R: Para su aplicación en R usaremos la función constrOptim para minimizar una función sujeta a restricciones de desigualdad. Función: constrOptim(theta, f, grad, ui, ci) Argumentos de la función constrOptim: Theta: valor de partida numérico (vector) (de longitud p): debe estar en la región factible. f: función para minimizar. grad: gradiente de f (una función también), o NULL. ui: matriz de restricción (k x p). ci: vector de restricción de longitud k. Salidas de la función constrOptim: $par: valor de las variables de decisión que optimiza la función objetivo. $value: valor que alcanza la función objetivo con el valor obtenido para las variables de decisión. Aplicación práctica Empezamos aplicándolo con el uso de R® mediante la resolución de un ejemplo, de forma que se pueda ver en la práctica. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 73 Para llevar a cabo la resolución de este problema en R®, comenzamos introduciendo los datos que nos ofrece el problema, es decir, vamos a definir la función que queremos minimizar, pero en este caso utilizando el comando function para definir el objeto, donde indicaremos el nombre de las variables, y , y a continuación entre corchetes debemos de introducir la función objetivo, , teniendo en cuenta la adecuada escritura en R. PNL<- function(x1,x2){(20000-440*x1-300*x2+20*x1^2+12*x2^2+x1*x2)} Para la introducción de las restricciones se usará una matriz y para las disponibilidades se define el objeto mediante un vector. matriz <- Matrix(c(1,1), nrow=1, byrow=TRUE) vectorb <- c(100) Una vez que introducimos los objetos podemos pasar a su resolución, en este caso, utilizaremos el paquete llamado constrOptim. En este paquete se pueden definir varios argumentos, nos centramos en aquellos de nuestro interés para la resolución del ejercicio. constroptim (c(100,100), function (x) {PNL (x[1], x[2])}, grad=NULL, ui=matriz, ci-vectorb} Directamente al ejecutar el comando mediante “run” o usando “ctrl+r” nos mostrará todos los resultados, si queremos en concreto el valor de nuestras variables podremos fijarnos en $par donde observamos que = 26’5537 y =73’4463. Para el valor que tomará la función objetivo se mostrará en $value que en este caso será de 1.029.060 unidades. $par $value [1] 26.55377 73.44623 [1] 1029060 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 80 - Almacenamiento y manipulación efectiva de datos. - Operadores para cálculo sobre variables indexadas (Arrays), en particular matrices. - Una amplia, coherente e integrada colección de herramientas para análisis de datos. - Posibilidades gráficas para análisis de datos, que funcionan directamente sobre pantalla o impresora. - Un lenguaje de programación bien desarrollado, simple y efectivo, que incluye condicionales, ciclos, funciones recursivas y posibilidad de entradas y salidas. (Debe destacarse que muchas de las funciones suministradas con el sistema están escritas en el lenguaje R). El término “entorno” lo caracteriza como un sistema completamente diseñado y coherente, antes que como una agregación incremental de herramientas muy específicas e inflexibles, como ocurre frecuentemente con otros programas de análisis de datos. R es en gran parte un vehículo para el desarrollo de nuevos métodos de análisis interactivo de datos. Como tal es muy dinámico y las diferentes versiones no siempre son totalmente compatibles con las anteriores. Algunos usuarios prefieren los cambios debido a los nuevos métodos y tecnología que los acompañan, a otros sin embargo les molesta ya que algún código anterior deja de funcionar. Aunque R puede entenderse como un lenguaje de programación, los programas escritos en R deben considerarse esencialmente efímeros. 5.2 Paquetes de optimización en R R tiene paquetes (unos cuantos miles en la actualidad) que extienden sus funciones básicas. Al abrir R se cargan automáticamente una serie de paquetes básicos. La lista completa de los paquetes oficiales puede consultarse en CRAN (https://cran.rproject.org/)((Comprehensive R Archve Network) es el repositorio oficial de paquetes de R, el lugar donde se publican las nuevas versiones del programa, etc. Contiene la lista completa de paquetes oficiales). Además de los oficiales, existen paquetes que pueden instalarse desde lugares como, por ejemplo, Github. No es sencillo encontrar el paquete que puede ser útil para un determinado fin. Las vistas de CRAN, descripciones de paquetes usados en un determinado ámbito y mantenidas por un experto en la materia, pueden ser un buen punto de partida. La instalación de paquetes puede realizarse o bien desde la consola: install.packages("nombre_paquete") o bien a través de los menús de RStudio (bajo Tools). Una vez instalados los paquetes es TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 81 necesario cargarlos para que las funciones que contienen estén disponibles en la sesión: library(nombre_paquete) 5.3 ROI El paquete R Optimization Infrastructure (ROI) proporciona una infraestructura extensible para modelar problemas de optimización lineal, cuadrática, cónica y no lineal general de manera consistente. library(ROI) Además, la infraestructura administra muchos solucionadores, reformulaciones, colecciones de problemas y funciones diferentes para leer y escribir problemas de optimización en varios formatos. El ROI proporciona las capacidades de modelado y administra los complementos, los complementos agregan los solucionadores al ROI. Sys.setenv(ROI_LOAD_PLUGINS = "FALSE") library(ROI) library(ROI.plugin.glpk) library(ROI.plugin.qpoases) library(ROI.plugin.ecos) library(ROI.plugin.scs) library(ROI.plugin.alabama) library(ROI.plugin.lpsolve) library(ROI.plugin.gurobi) Problema de optimización str(OP) ## function (objective, constraints, types, bounds, maximum = FALSE) Objetivo Objetivo lineal str(L_objective) ## function (L, names = NULL) TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 82 lo <- L_objective(c(1, 2, 3), c("x", "y", "z")) Objetivo cuadrático str(Q_objective) ## function (Q, L = NULL, names = NULL) qo <- Q_objective(diag(3), c(1, 2, 3), c("x_1", "x_2", "x_3")) Objetivo funcional str(F_objective) ## function (F, n, G = NULL, H = NULL, names = NULL) fo <- F_objective(F = function(x) sum(x^2), n = 2, G = function(x) 2*x, names = c("x_1", "x_2")) Restricciones Restricciones lineales str(L_constraint) ## function (L, dir, rhs, names = NULL) lc <- L_constraint(L = rbind(c(3, 4, 1), c(1, 0, 2), c(1, 1, 0)), dir = c("<=", ">=", "=="), rhs = c(90, 5, 2), names = c("x", "y", "z")) TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 83 Restricciones cuadráticas str(Q_constraint) ## function (Q, L, dir, rhs, names = NULL) qc1 <- Q_constraint(Q = diag(2), L = 1:2, dir = "<=", rhs = 3, names = c("x", "y")) qc2 <- Q_constraint(Q = list(diag(2, 2), NULL, matrix(c(3, 1, 1, 3), 2)), L = rbind(c(3, 1), c(1, 1), c(2, 5)), dir = c("<=", "<=", "<="), rhs = c(3, 4, 9), names = c("x", "y")) Restricciones funcionales str(F_constraint) ## function (F, dir, rhs, J = NULL, names = NULL) fc1 <- F_constraint(F = function(x) x^2, dir = c("<=", "<="), rhs = c(2, 4), J = function(x) diag(x = 2, nrow = 2) * x, names = c("x", "y")) o equivalente fc2 <- F_constraint(F = list(function(x) x[1]^2, function(x) x[2]^2), dir = c("<=", "<="), rhs = c(2, 4), J = list(function(x) rbind(c(2, 0) * x), function(x) rbind(c(0, 2) * x)), names = c("x", "y")) TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 84 Bounds Una variable Bounds es un tipo especial de restricción utilizada para restringir una variable objetivo entre un límite inferior y superior real. Por lo tanto, las variables Bounds a menudo también se denominan "box bounds" o "box contraints". Aunque las variables bounds podrían modelarse fácilmente como restricciones lineales, muchos GPS solo admiten variables bounds. Además, la mayoría de los solucionadores que admite cualquier tipo de restricción, permite especificar límites de variables directamente. Por lo tanto, es razonable. pero también es conveniente considerarlos por separado. Típicamente, las implementaciones de algoritmos de optimización diferencian entre cinco tipos de observación. límites de la variable objetivo: libre (−∞ , ∞), superior (−∞ , ub ], inferior [ lb, ∞), doble acotada [ lb, ub ], y límites fijos. En ROI, las variables bounds se representan como una lista con dos elementos: superior e inferior, donde solo los valores no predeterminados se almacenan en un formato simple y disperso. En esto solo los índices de formato disperso y los valores no predeterminados se almacenan. Para los bounds inferiores el valor predeterminado es cero y para los bounds superiores el valor predeterminado es infinito. Por lo tanto, para OPs donde se requieren todas las variables para tomar valores en el intervalo [0 , ∞) no tiene que haber bounds especificado. El bounds inferior y superior predeterminados se pueden cambiar con los argumentos ld y ud. Los bounds superior y/o inferior se especifican proporcionando el índice i de la variable correspondientes capaz (argumentos li, ui) y su límite inferior (lb) o superior (ub), respectivamente. Por lo tanto, se construyen restricciones de caja −∞ ≤ ≤ 4, 0 ≤ ≤100, 2 ≤ ≤ ∞ y 0 ≤ ≤ ∞ en ROI de la siguiente manera: R> V_bound (li = 1: 4, ui = 1: 4, lb = c (-Inf, 0, 2, 0), + ub = c (4, 100, Inf, Inf)) variables bounds de ROI: 2 bounds de variables no estándar inferiores y 2 superiores no estándar. Si se proporcionan todos los valores superiores e inferiores (no se omiten los valores predeterminados), los índices pueden ser excluido: R> V_bound (lb = c (-Inf, 0, 2, 0), ub = c (4, 100, Inf, Inf)) variables bounds de ROI: 2 bounds de variables no estándar inferiores y 2 superiores no estándar. Si se omiten los valores predeterminados, se debe proporcionar el número de variables objetivas. R> V_bound (li = c (1L, 3L), ui = c (1L, 2L), lb = c (-Inf, 2), ub = c (4, 100), + nobj = 4L) TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 85 variables bounds de ROI: 2 bounds de variables no estándar inferiores y 2 superiores no estándar. Tenga en cuenta que la caja restringe 0 ≤ ≤ 20 y −20 ≤ ≤ 20 para todo I ={1,2,4}. Este límite de variable se puede construir mediante el siguiente código de ROI. R> V_bound (li = 3, lb = 0, ld = -20, ud = 20, nobj = 4L) variables bounds de ROI: 3 variables bounds no estándar inferiores y 4 superiores no estándar. ROI distingue entre dos tipos diferentes de límites: 1) Sin límite (No_bound) 2) Limites variables V_bound Por defecto, los límites de las variables se establecen en para todo . str(V_bound) ## function (li, ui, lb, ub, nobj, ld = 0, ud = Inf, names = NULL) vb <- V_bound(li = 1:3, ui = 1:3, lb = c(-3, -Inf, -9), ub = c(3, 7, Inf)) La infraestructura de optimización R está estructurada en el ROI del paquete y su acompañamiento de extensiones (complementos y modelos). El ROI del paquete proporciona todas las clases y métodos necesarios y administra las extensiones (es decir, carga automáticamente los complementos y administra los metadatos sobre los complementos). Los paquetes de extensión agregan solucionadores de optimización, funciones de lectura/escritura y recursos adicionales (p. ej., colecciones de modelos). Las extensiones de plug-in juegan un papel especial, por lo tanto, todos los complementos se cargan automáticamente cuando se carga el ROI. Cuando se carga un complemento proporciona datos sobre sus capacidades. Estos datos se almacenan en una base de datos en memoria e incluye información sobre a qué problemas se aplica el complemento, qué formatos puede leer/escribir y los argumentos de control disponibles del solver y cómo el solver específico de los argumentos de control se relacionan con los argumentos comúnmente utilizados. Este mecanismo hace posible que ROI conozca todos los complementos instalados, sin necesidad de cambiar ROI cuando se agrega un nuevo complemento. Para hacer posible la carga automática los complementos deben seguir la convención de nombres TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 86 ROI.plugin. <nombre>, donde <nombre> es normalmente el nombre de un solver de optimización (por ejemplo, ROI.plugin.glpk (Theußl 2017)). Los prefijo ROI.models (por ejemplo, ROI.models.netlib (Schwendinger 2016)) se utiliza para paquetes de datos con OPs predefinidos. Después de formular un OP se puede resolver llamando a la función ROI_solve (x, solucionador, control, ...). Esta función toma un objeto R de la clase 'OP' que contiene la formulación del OP, el nombre del solucionador que se utilizará y una lista para resolver parámetros específicos del solver como argumentos. El solver y los argumentos de control son opcionales, si no se proporciona un argumento de solución, el ROI elegirá una solución de resolución automáticamente. Alternativamente, los parámetros específicos del solver se pueden especificar a través de argumentos de puntos El problema indicado se puede resolver con el siguiente código de ROI: R> (lp_sol <- ROI_solve (lp, solver = "glpk")) Los status code del solver se utilizan para informar al usuario sobre el estado de salida del solver. A pesar de el uso común de los status code en los solver de optimización no existe un estándar ampliamente utilizado. Sin embargo, creemos que es deseable proporcionar status code unificados. Los status code utilizados en ROI_solve son simples y consistentes con la práctica común, devuelve 0 en caso de éxito (si se encontró una "solución" que cumple los requisitos específicos del solver) 1 de lo contrario. Para la optimización de solvers especializados en resolver LPs convexos, QPs y CPs se puede suponer que se encontró una solución, si el código de estado es 0. Desafortunadamente, lo mismo no es cierto para los no convexos QPs y GPS, aquí los códigos de estado son menos informativos. Algunos paquetes como optimx y Alabama verifique las condiciones de Karush-Kuhn-Tucker (KKT) para verificar que la solución encontrada cumpla con los requisitos criterios de un mínimo local. La función principal de un paquete de infraestructura de optimización general debe tomar al menos tres argumentos: problema que representa un objeto que contiene la descripción del problema de optimización (OP) correspondiente, solucionador especificando el solucionador que se utilizará (por ejemplo, "glpk", "nlminb", "scs"), control que contiene una lista de argumentos de control adicionales para el solucionador correspondiente. El solucionador de argumentos y el control se entienden fácilmente, ya que desde el solucionador disponible espectro solo tenemos que elegir aquellos que sean capaces de manejar el OP correspondiente y (opcionalmente) proporcione los parámetros de control apropiados. Sin embargo, al construir el objeto del problema, de manera general e intuitiva, es una tarea desafiante que lleva a varios problemas de diseño. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 87 Parece natural instanciar OP basados en una función objetivo, una o varias restricciones, tipos y límites de las variables objetivas, así como la dirección de optimización (si se busca un mínimo o un máximo). R> biblioteca ("ROI") la función objetivo depende principalmente de su forma funcional. Si la función objetivo es lineal (L) entonces es una práctica común suministrar solo un vector de coeficientes . Para funciones objetivos cuadraticas (Q) de la forma la mayoría de los solvers toman un vector y una matriz como entrada. Las funciones objetivos no lineales se representan como una función R que toma el vector de variables objetivas como argumento y devuelve el valor objetivo. Los tipos de funciones objetivos y los constructores correspondientes implementados en ROI son: F, Q, L. F La forma más general de una función objetivo se crea con el F_objetivo (F, n, G, H, nombres) constructor simplemente suministrando F, una función R que representa , y n la longitud de x. Opcionalmente, la información sobre el gradiente y el hessiano puede ser proporcionado a través de los argumentos G y H. Si no se proporciona un gradiente, se calculará numéricamente si es necesario. El argumento de nombres opcionales se propaga a la solución objeto para que la solución sea más legible. Q Las funciones objetivas que representan una forma cuadrática como se describe anteriormente se pueden crear fácilmente con el constructor Q_objetivo (Q, L, nombres) tomando Q, la parte cuadrática , y opcionalmente L, la parte lineal , como argumentos. El argumento de los nombres es nuevamente opcional. L Si el objetivo a optimizar es una función lineal, entonces uno debe usar el L_objetivo (L, nombres) constructor que suministra L (los coeficientes de las variables objetivas) como un vector numérico. El argumento de los nombres es nuevamente opcional. Los tres constructores devuelven un objeto heredado de la clase 'objetivo'. Para modelar las clases de problemas nos bastaría con cuatro tipos de restricciones. Por lo tanto, los argumentos con el mismo nombre tienen la misma funcionalidad independientemente del tipo de restricción. ROI distingue entre 5 tipos diferentes de restricciones: F, C, Q, L, Sin restricciones. F La forma más general de restricciones puede expresar cualquier restricción representable por una función R. Se crean a través de F_constraint (F, dir, rhs, J, nombres). Aquí F es ya sea una función o una lista de funciones, dir es un vector de caracteres que da la dirección de la restricción y rhs es un vector numérico que da el lado derecho de la restricción. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 88 Los argumentos opcionales J y nombres se pueden usar para proporcionar el jacobiano y la variable nombres de las restricciones. C Las restricciones cónicas se construyen mediante la función C_constraint (L, conos, rhs, nombres), donde L puede ser un vector numérico de longitud n o una matriz de dimension m × n. Una restricción cónica puede estar compuesta por varios conos, donde cada tipo de cono puede ocurrir varias veces. Actualmente el ROI implementa constructors para los conos K_zero, K_lin, K_soc, K_psd, K_expp, K_expd, K_powp y K_powd. A combinar diferentes conos se puede utilizar la combinación genérica . Q Las restricciones cuadráticas definidas en la ecuación 5 se pueden crear fácilmente con el constructor Q_constraint (Q, L, dir, rhs, nombres). Las restricciones cuadráticas Q se dan como un lista de longitud m donde las entradas son de n × n matrices o NULL. L Las restricciones lineales se construyen mediante la función L_constraint (L, dir, rhs, names). Todos los constructores devuelven un objeto que hereda de la clase 'restricción'. Ya que en muchas situaciones es deseable optimizar una función objetivo dada sujeta a restricciones compuestas de diferentes tipos, el ROI puede combinar multiples restricciones en una sola restricción usando el generic funciones c ( ) o rbind ( ). Dado que las matrices L y Q pueden volverse enormes pero típicamente son escasas usamos el formato de matriz de triplete simple del slam (Hornik, Meyer y Buchta 2016) paquete para almacenarlos internamente. En el formato de matriz de triplete simple (a veces referido como formato de lista de coordenadas) solo los índices de fila, los índices de columna y los valores de los elementos distintos de cero se almacenan en una lista. Elegimos el paquete slam no solo por eficiencia razones, sino también debido al hecho de que muchas API de solucionador exigen dicho formato. Como es una práctica común en los solucionadores de enteros mixtos distingue entre tipos de variables continuo, entero y binario.Codificamos la opción variable con los siguientes caracteres: "C" para continuo, "I" para entero y "B" para binario. Por defecto se asumen todas las variables de tipo continuo. La infraestructura de optimización R está estructurada en el ROI del paquete y su acompañamiento extensiones (plug-ins y models). El paquete ROI proporciona todas las clases y métodos necesarios y administra las extensiones (es decir, carga automáticamente los complementos y administra los metadatos sobre los complementos). Los paquetes de extensión agregan solucionadores de optimización, funciones de lectura / escritura y recursos adicionales (p. ej., colecciones de modelos). Las extensiones de plug-in juegan un papel especial, por lo tanto, todos los complementos se cargan automáticamente cuando se carga el ROI. Cuando se carga un complemento TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 89 proporciona datos sobre sus capacidades. Estos datos se almacenan en una base de datos en memoria y incluye información sobre a qué problemas se aplica el complemento, qué formatos puede lectura / escritura y los argumentos de control disponibles del solucionador y cómo el solucionador específico Los argumentos de control se relacionan con los argumentos comúnmente utilizados. Este mecanismo hace posible que el ROI conozca todos los complementos instalados, sin necesidad de cambiar el ROI cuando se agrega un nuevo complemento. Para hacer posible la carga automática los complementos deben seguir la convención de nombres ROI.plugin. <nombre>, donde <nombre> es normalmente el nombre de un solucionador de optimización (por ejemplo, ROI.plugin.glpk (Theußl 2017)). Los prefijo ROI.models (por ejemplo, ROI.models.netlib (Schwendinger 2016)) se utiliza para paquetes de datos con OP predefinidos. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 96 Gráficamente quedaría como se indica a continuación: Ahora que tenemos los 4 clusters vamos a buscar la ruta más corta dentro de cada clusters. Para el cluster 1 (C1) que esta formado por las paradas A, B, C, D, I, J y PC: x=c(4,8,2,6,4,7,6.99375) > y=c(0,0,1,1,3,3,4.15625) > paradas=c("A","B","C","D","I","J","PC") > xy.data=data.frame(x,y,row.names=paradas) > print(xy.data) TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 97 x y A 4.00000 0.00000 B 8.00000 0.0000x0 C 2.00000 1.00000 D 6.00000 1.00000 I 4.00000 3.00000 J 7.00000 3.00000 PC 6.99375 4.15625 > plot(xy.data) > text(xy.data,labels=paradas,pos=4) > xy.m1=dist(xy.data,"euclidean",TRUE,TRUE) > print(xy.m1) A B C D I J PC A 0.000000 4.000000 2.236068 2.236068 3.000000 4.242641 5.122202 B 4.000000 0.000000 6.082763 2.236068 5.000000 3.162278 4.276325 C 2.236068 6.082763 0.000000 4.000000 2.828427 5.385165 5.907576 D 2.236068 2.236068 4.000000 0.000000 2.828427 2.236068 3.308996 I 3.000000 5.000000 2.828427 2.828427 0.000000 3.000000 3.209276 J 4.242641 3.162278 5.385165 2.236068 3.000000 0.000000 1.156267 PC 5.122202 4.276325 5.907576 3.308996 3.209276 1.156267 0.000000 Vamos a representar por la variable como la arista que va de i a j. dicha variable tomara el valor 1 si pertenece a la ruta óptima, 0 en otro caso. Así la función a minimizar es: Y esta sujeta a las restricciones que dividiremos en tres grupos: restricciones de llegada, restricciones de salida y ruptura de subcircuitos. Restricciones de llegada: TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 98 Restricciones de salida: Restricciones de ruptura de subcircuitos: Como solo hay 7 paradas nos valdria con escribir rupturas de tamaño 2. Por ello obtenemos sólo 21 ecuaciones (6+5+4+3+2+1=21): Para implementar el modelo en R y ejecutar las funciones de optimización, debemos representar los datos del modelo mediante matrices y vectores. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 99 La función lp de lpSolver necesita una matriz formada por los coeficientes de las variables en las restricciones que Llamaremos const.coef y los vectores para los coeficientes de la función objetivo (obj.coef), las direcciones de las restricciones, strings, y los valores , b.coef. Estos mismos elementos los utilizaremos para la función solveLP de linprog. Comenzamos el trabajo en R cargando los paquetes que vamos a emplear > library(lpSolve) > library(linprog) y a continuación iremos creando los conjunto de valores. En primer lugar tenemos el vector de , denominado obj.coef, > obj.coef<- c (4, 2.236068, 2.236068, 3, 4.242641, 5.122202, 4, 6.082763, 2.236068, 5, 3.162278, 4.276325, 2.236068, 6.082763, 4, 2.828427, 5.385163, 5.907576, 2.236068, 2.236068, 4, 2.828427, 2.236068, 3.308996, 3, 5, 2.828427, 2.828427, 3, 3.209276, 4.242641, 3.162278, 5.385165, 2.236068, 3, 1.156267, 5.122202, 4.276325, 5.907576, 3.308996, 3.209276, 1.156267) Seguido de la matriz const.coef con los coeficientes de las restricciones, con tantas filas como número de restricciones y columnas como número de variables del modelo. > a<- c(0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0, 0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0, 0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0, 0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0, 0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0, 0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0, 0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0, 1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1, 1,1,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 100 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0, 0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1) > const.coef<-matrix(a,nrow=35,byrow=T) Y por último el vector strings para las desigualdades de las restricciones y b.coef para los valores b de las mismas > strings<- c("=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=", "<=") > b.coef<- c(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) Para poder ejecurar lp y así poder ver si el modelo resulta válido o no. > lpSolve1<- lp(direction="min", obj.coef, const.coef, strings, b.coef) > lpSolve1$solution [1] 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 [41] 1 0 Con lo que me está diciendo que los caminos a coger son: TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 101 Para el cluster 2 (C2) que esta formado por las paradas E, F, G, PC, K, L y R: > x=c(11,9,13,6.99375,10,12,12) > y=c(1,2,2,4.15625,4,4,6) > paradas=c("E","F","G","PC","K","L","R") > xy.data=data.frame(x,y,row.names=paradas) > print(xy.data) x y E 11.00000 1.00000 F 9.00000 2.00000 G 13.00000 2.00000 PC 6.99375 4.15625 K 10.00000 4.00000 L 12.00000 4.00000 R 12.00000 6.00000 > plot(xy.data) > text(xy.data,labels=paradas,pos=4) > xy.m1=dist(xy.data,"euclidean",TRUE,TRUE) > print(xy.m1) E F G PC K L R E 0.000000 2.236068 2.236068 5.100191 3.162278 3.162278 5.099020 F 2.236068 0.000000 4.000000 2.945242 2.236068 3.605551 5.000000 G 2.236068 4.000000 0.000000 6.381571 3.605551 2.236068 4.123106 PC 5.100191 2.945242 6.381571 0.000000 3.010308 5.008688 5.334975 K 3.162278 2.236068 3.605551 3.010308 0.000000 2.000000 2.828427 L 3.162278 3.605551 2.236068 5.008688 2.000000 0.000000 2.000000 R 5.099020 5.000000 4.123106 5.334975 2.828427 2.000000 0.000000 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 102 La función a minimizar seria: Restricciones de llegada: Restricciones de salida: TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 103 Restricciones de ruptura: > library(lpSolve) > library(linprog) > obj.coef<-c(2.236068,2.236068,5.100191,3.162278,3.162278, 5.099020,2.236068,4,2.945242,2.236068,3.605551,5,2.236068,4, 6.381571,3.605551,2.236068,4.123106,5.100191,2.945242,6.381571, 3.010308,5.008688,5.334975,3.162278,2.236068,3.605551,3.010308, 2,2.828427,3.162278,3.605551,2.236068,5.008688,2,2,5.099020,5, 4.123106,5.334975,2.828427,2) > a<-c(0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0 ,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0, 0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0 ,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0, 0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0 ,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0, 0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,1 ,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1 ,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1 ,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 104 ,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0, 0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0 ,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0 ,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1 ,0,0,0,0,0,1) > const.coef<-matrix(a,nrow=35,byrow=T) > strings<-c("=","=","=","=","=","=","=","=","=","=","=","=", "=","=","<=","<=","<=","<=","<=","<=","<=","<=","<=","<=","<=", "<=","<=","<=","<=","<=","<=","<=","<=","<=","<=") > b.coef<- c(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1) > lpSolve1<- lp(direction="min",obj.coef,const.coef,strings, b.coef) > lpSolve1$solution [1] 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 [41] 1 0 Con lo que me está diciendo que los caminos a coger son: TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 105 Para el cluster 3 (C3) que esta formado por las paradas PC, P, Q, U y V: > x=c(6.99365,7,9,6,10) > y=c(4.15625,6,6,8,8) > paradas=c("PC","P","Q","U","V") > xy.data=data.frame(x,y,row.names=paradas) > print(xy.data) x y PC 6.99365 4.15625 P 7.00000 6.00000 Q 9.00000 6.00000 U 6.00000 8.00000 V 10.00000 8.00000 > plot(xy.data) > text(xy.data,labels=paradas,pos=4) > xy.m1=dist(xy.data,"euclidean",TRUE,TRUE) > print(xy.m1) PC P Q U V PC 0.000000 1.843761 2.724859 3.970108 4.879811 P 1.843761 0.000000 2.000000 2.236068 3.605551 Q 2.724859 2.000000 0.000000 3.605551 2.236068 U 3.970108 2.236068 3.605551 0.000000 4.000000 V 4.879811 3.605551 2.236068 4.000000 0.000000 TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 112 Bibliografía [1] Miguel A. Goberna. Medio siglo de Programación Lineal. En: Jornadas de Educación Matemática de la Comunidad Valenciana 2000. [2] Eugene Schenkman. The Weierstrass approximation theorem. American Mathematical Mobthly, pages 65-66. 1972 [3] Goberna, M.A., Jornet, V., Puente, R. Optimización lineal. Teoría, métodos y modelos. Addison Wesley, 2004. [4] Luenberger, D. Programación Lineal y no Lineal. Addison Wesley, 1973. [5] Stefan TheuBI, Florian Schwendinger, Kurt Hornik. ROI: An Extensible R Optimization Infrastructure. 2019. [6] Enrique Castillo, Antonio J. Conejo, Pablo Pedregal, Ricardo García y Natalia Alguacil. Formulación y Resolución de Modelos de Programación Matemática en Ingeniería y Ciencia. 2002. [7] Enrique Baquela y Andrés Redchuk. Optimización Matemática con R. Volumen I: Introducción al modelado y resolución de problemas. 2013 [8] H. Calvete and P. Mateo. Programación lineal, entera y meta. Colección Textos Docentes. Prensa Universitaria de Zaragoza, 1994. [9] J. Dennis and R. Schnable, Numerical methods for unconstrained optimization ans nonlinear equations. Prentice-Hall, Inc., New Jersey, 1983. [10] M. Berkelaar, J. Dirks, K. Eikland, P. Notebaert, y J. Ebert, lp_solve Reference Guide, Eindhoven University of Technology, 2011, Web, http://lpsolve.sourceforge.net/5.0/. [11] A. Makhorin, GLPK (GNU Linear Programming Kit), Department for Applied Informatics, Moscow Aviation Institute, 2011, Web, http://www.gnu.org/software/glpk/. [12] C. Mészáros, The BPMPD interior point solver for convex quadratic problems, Tech. Report WP-98-8, Laboratory of Operations Research and Decision Systems, Budapest, Hungría, 1998, http://www.sztaki.hu/~meszaros/bpmpd/. [13] B. A. Murtagh y M. A. Saunders, MINOS 5.5 User Guide, Tech. Report SOL 83-20R, Systems Optimization Laboratory, Dep. of Operations Research, Stanford University, dic 1983, http://www.sbsi-sol-optimize.com/manuals/Minos%20Manual.pdf. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 113 [14] IBM Corporation, Software Group, IBM ILOG CPLEX Optimizer, High Performance Mathematical Optimization Engines, 2010, Web, http://public.dhe.ibm.com/common/ssi/ecm/en/wsd14044usen/WSD14044USEN.PDF. [15] MOSEK ApS, The MOSEK optimization toolbox for MATLAB manual. Version 6.0 (Revision 114), 2011, Web, http://www.mosek.com/fileadmin/products/6_0/tools/doc/ html/toolbox/index.html. [16] J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Advances Optimization Lab, Mc-Master University, 1998, incluido en la descarga del software. [17] K. C. Toh, C. R. H. Tütüncü, y M. J. Todd, On the Implementation and Usage of SDPT3 - a Matlab Software Package for Semidefinite-Quadratic-Linear Programming, version 4.0, jul 2006. [18] S. Boyd y L. Vandenberghe, Convex Optimization, Cambridge University Press, mar 2004. [19] M. Grant y S. Boyd, CVX, Matlab Software for Disciplined Convex Programming, version 1.21, feb 2011, disponible online, http://cvxr.com/cvx. [20] AMPL Optimization LLC, Key AMPL Features, 2011, Web, http://www.ampl.com/key.html. [21] GAMS Development Corporation, An Introduction to GAMS, 2011, Web, http://www.gams.com/docs/intro.html. [22] Becker, R.A., Chambers, J.M. y Wilks, A.R. (1988). The new S language: A programming environment for data analysis and graphics. Pacific Grove, CA: Wadsworth. [23] Chambers, J.M. (1998). Programming with data: a guide to the Language (2007). Software for data analysis: Programming with R. New York: Springer. [24] Venables, W. N., Smith, D. M. y the RDevelopment Core Team (2007). An Introduction to R. Vienna, Austria: R Foundation for Statistical Computing. [25] Berkelaar, M. et al (2014) lpSolve: Interface to Lpsolve v. 5.5 to solve linearinteger programs. R package version 5.6.10. [26] Y. Ye, M. J. Todd, y S. Mizuno, An O( )-iteration homogeneous and selfdual linear programming algorithm, Mathematics of Operations Research 19 (1994), 53– 67. TFG: Problema de optimización mediante software 2019/2020 Gonzalo Manuel Roa Muñoz Página 114 [27] Zitzler, E., Laummans, M. & Thiele, L. (May, 2001). SPEA2: Improving the Strength Pareto Evolutionary Algorithm. En Computer Engineering and Networks Laboratory (TIK) Report. [28] L.A. Zadeh. Fuzzy Sets, Inform. Control 8 (1965) 338-353 [29] S.S.L. Chang, L.A. Zadeh. On fuzzy mappings and control, IEEE Transactions on Systems, Man and Cybernetics 2 (1) (1972) 30-34. [30] Bezdek, James C.; Ehrlich, Robert; Full, William (1984). FCM: The Fuzzy c- Means Clustering Algorithm. Computers & Geosciences 10 (2-3): 191-203. [31] Yang, M. S. (1993). A Survey of Fuzzy Clustering. Mathl. Comput. Modelling 18 (11): 1-16. Archivado desde el original el 15 de diciembre de 2013. Consultado el 8 de marzo de 2020. [32] W. Karush (1939). Minima of Functions of Several Variables with Inequalities as Side Constraints. M.Sc. Dissertation. Dept. of Mathematics, Univ. Of Chicago, Chicago, Illinois. [33] H. W. Kuhn, Tucker, A. W., Proceedings of 2nd Berkeley Symposium, Nonlinear Programming, University of California Press, 1951, Berkeley [34] Christos H. Papadimitriou y Kenneth Steiglitz. “Combinatorial Optimization: Algorithms and Complexity”. General Publishing Company (1998).