Introducción a la programación lineal multiobjetivo

Facultad de Matemáticas Departamento de Estadística e Investigación Operativa Grado en Matemáticas INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL MULTIOBJETIVO Trabajo Fin de Grado Autora: Elvira Martínez Sánchez Supervisado por: Pedro Luis Luque Calvo Septiembre 2022 Índice general Prólogo ....................................... iii Resumen....................................... v Abstract....................................... vi ÍndicedeFiguras.................................. vii 1. Introducción. Programación Lineal Multiobjetivo 1 1.1. Contextohistórico .............................. 1 1.2. Conceptosprevios............................... 2 1.3. Definiciones básicas. Planteamiento del problema . . . . . . . . . . . . . 4 1.4. Optimalidad.................................. 6 1.5. Aplicaciones reales que usan Programación Lineal Multiobjetivo . . . . . 8 1.5.1. Diseño de tratamientos de radioterapia . . . . . . . . . . . . . . . 8 1.5.2. Compra de aviones de una compañía aérea . . . . . . . . . . . . . 9 2. Métodos de resolución 13 2.1. Introducción.................................. 13 2.2. Método Simplex Multiobjetivo . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.1. Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2. Comprobación de la eficiencia de una solución . . . . . . . . . . . 19 2.2.3. Algoritmo del Simplex Multiobjetivo . . . . . . . . . . . . . . . . 19 2.3. Método de las ponderaciones . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.1. Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.2. Generación del conjunto eficiente . . . . . . . . . . . . . . . . . . 26 2.3.3. Existencia de soluciones óptimas alternativas . . . . . . . . . . . . 27 2.4. Método de las ε-restricciones......................... 28 2.4.1. Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.2. Existencia de soluciones óptimas alternativas . . . . . . . . . . . . 29 2.4.3. Generación de soluciones eficientes . . . . . . . . . . . . . . . . . 29 2.5. Programación por metas . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.5.1. Descripción del método . . . . . . . . . . . . . . . . . . . . . . . . 31 3. Resolución con software 33 3.1. AMPL..................................... 33 3.2. R........................................ 36 3.2.1. PaqueteLpSolve ........................... 37 3.2.2. LibreríarAMPL............................ 38 3.2.3. PaqueterMOIP............................ 42 3.3. Conclusiones.................................. 44 i A. Apéndice: Comprobación de la eficiencia de una solución 45 Bibliografía 50 ii Prólogo Me gustaría agradecer a mi familia su apoyo incondicional y su confianza en mí a lo largo de todos estos años. Sin su sostén no habría conseguido llegar hasta aquí. Quisiera agradecer también a mi tutor, Pedro Luis Luque Calvo, por la dedicación que ha puesto en mi trabajo y el apoyo que ha supuesto para mí. iii Resumen Este trabajo pretende servir de introducción a la Programación Lineal Multiobjetivo, área de la Optimización Matemática que involucra múltiples criterios, frecuentemente conflictivos entre sí. Más concretamente, se ciñe a aquellos problemas en los que intervienen únicamente funciones de carácter lineal. Después de hacer una breve introducción histórica, se presenta el modelo general, así como las principales definiciones y resultados. Se exponen también diferentes métodos con los que resolver problemas de Programación Multiobjetivo, siendo este el contenido de mayor peso en el trabajo. A lo largo del mismo, un ejemplo en común servirá de hilo conductor para ilustrar el funcionamiento de cada uno de los métodos expuestos. Para finalizar, se muestra un método generalizado que resuelve problemas de Programación Lineal Multiobjetivo con ayuda de software disponible: AMPL y R. v Abstract This study is thought to be an introduction to Multiobjective Linear Programming, an area of the Mathematical Optimisation that involves multiple criteria, usually conflicting among them. More specifically, it focuses on those problems which only involve linear functions. After a brief historical background, the general model is introduced, as well as the main definitions and results. Different methods used to solve Multiobjective Programming problems are also presented, content which is considered to be the core one in this paper. Throughout the study, a common example is used as a guiding thread to illustrate the functioning of all of the displayed methods. Finally, a generalised method that solves Multiobjective Linear Programming problems with the help of an available software is shown: AMPL and R. vi Índice de figuras 2.1. Métodosderesolución ............................ 13 2.2. Región factible del espacio de decisiones . . . . . . . . . . . . . . . . . . 15 2.3. Región factible del espacio de objetivos . . . . . . . . . . . . . . . . . . . 15 2.4. Curvasdenivel ................................ 16 2.5. Conjunto eficiente. Método Simplex . . . . . . . . . . . . . . . . . . . . . 24 2.6. Solución eficiente. Método de las ponderaciones . . . . . . . . . . . . . . 26 2.7. Solución eficiente. Método de las ε−restricciones . . . . . . . . . . . . . 31 3.1. LogodeAMPL ................................ 33 3.2. PantallaAMPLide .............................. 36 3.3. LogodeRStudio ............................... 36 3.4. Pantalla Rstudio. Uso de lpSolve . . . . . . . . . . . . . . . . . . . . . . 38 3.5. Pantalla Rstudio. Uso de rAMPL . . . . . . . . . . . . . . . . . . . . . . 41 vii 1.4. OPTIMALIDAD Pk j=1(1 + MPi=jλi j)fj(x)≤Pk j=1(1 + MPi=jλi j)fj(x∗) ∀x∈X. ⇐⌟Se supone que ∃λ= (λ1, . . . , λk)∈Λtal que x∗es solución óptima del problema de un sólo objetivo (Pλ). Es trivial que x∗es eficiente para (MOLP). Se demuestra que es propiamente eficiente, con M= (k−1) ·m´axi,j{λj λi},k≥2 Por reducción al absurdo, se supone que x∗no es propiamente eficiente para (MOLP). Entonces, para algún objetivo fiy para algún x∈Xse tiene fi(x)−fi(x∗)> M ·(fj(x∗)−fj(x)),∀jtal que fj(x)< fj(x∗) Como consecuencia directa se tiene fi(x)−fi(x∗)>k−1 λiλj·(fj(x∗)−fj(x)),∀j=i Multiplicando por λi k−1y sumando en j se tiene λi(fi(x)−fi(x∗)) >Pj=iλj(fj(x∗)−fj(x)) Esto es absurdo, pues se ha supuesto que x∗es óptimo para (Pλ). ■ Este teorema, que puede ser consultado en [Geoffrion, 1968], tiene gran utilidad desde el punto de vista computacional, pues reduce a un problema de programación paramétrico encontrar soluciones propiamente eficientes. Teorema 1.4.2 El conjunto Xef de soluciones eficientes del problema (1.1) tiene las siguientes propiedades: (i) Si un punto interior de una cara del poliedro Xes eficiente, entonces todos los puntos de esa cara lo son. (ii) Si Xtiene un vértice y (1.1) tiene una solución eficiente, entonces tiene una solución eficiente en un vértice de X. (iii) Xef consiste en caras del poliedro Xy es cerrado y conexo por arco. Este teorema es de suma importancia pues implica que a la hora de buscar el conjunto eficiente basta con examinar los puntos de la frontera del poliedro X. Esto evita tener que considerar todo el conjunto de soluciones factibles, lo que supone un ahorro enorme de tiempo y esfuerzo. Teorema 1.4.3 Sea x∈Xun punto factible. Si x es solución óptima única para el problema uniobjetivo asociado a alguna de las funciones criterio del problema (1.1), entonces x es eficiente para (1.1). CAPÍTULO 1. INTRODUCCIÓN. PROGRAMACIÓN LINEAL MULTIOBJETIVO 7 1.5. APLICACIONES REALES QUE USAN PROGRAMACIÓN LINEAL MULTIOBJETIVO 1.5. Aplicaciones reales que usan Programación Lineal Multiobjetivo De acuerdo con [Ríos Insúa, 1996], los problemas de Programación Multiobjetivo surgen en los procesos de toma de decisiones en multitud de áreas de la actividad humana tales como la economía, la ingeniería, el transporte, la medicina, etc. En particular, la Programación Lineal Multiobjetivo tiene importantísimas aplicaciones en la vida real. En este apartado se recogen un par de ejemplos de ello. En primer lugar, se presenta una situación real que puede ser más o menos compleja y que se desea solventar. En el planteamiento del problema intervienen ciertos objetivos a los que se pretende aspirar con la aplicación de tal supuesta solución. Además, se imponen también una serie de requerimientos que deben cumplirse para que la solución sea satisfactoria. Todo este escenario que a priori puede parecer difícil de manejar, se consigue modelar en forma de variables, funciones objetivo y restricciones. De esta manera, haciendo uso de las distintas estrategias que ya existen para resolver estos problemas (algunas de ellas serán expuestas en el próximo capítulo) se obtendrán aquellas soluciones que encajen lo mejor posible con lo que se pretende conseguir en la situación real en concreto. En última instancia, serán los expertos de la materia en cuestión o los posibles interesados los que actúen como tomadores de decisiones. 1.5.1. Diseño de tratamientos de radioterapia De una manera simplificada se presenta un ejemplo de modelización para el diseño de un tratamiento de radioterapia para tratar casos de cáncer. Este ejemplo se menciona en [Ehrgott, 2005] y hace referencia a la investigación desarrollada en [Sonderman and Abrahamson, 1985]. La terapia de radiación se usa en medicina en el tratamiento de enfermedades tumorales. Mediante la aplicación de rayos de radiación de una forma determinada, se consigue dañar el ADN de las células cancerígenas y por consiguiente, frenar su avance en el organismo del paciente. Existe tecnología capaz de modular de manera independiente la dirección e intensidad de cada rayo del conjunto de rayos de radiación totales. Para concretar en qué zonas se va a aplicar el tratamiento, se discretiza el cuerpo del paciente en mpuntos de dosis. Cada punto de la discretización se supone clasificado en tres grupos según se localice en el tumor T, en tejido sano So en alguna de las l estructuras críticas {E1, . . . , El}. La dosis tumoral prescrita por el especialista viene dada por dT. El objetivo utópico sería diseñar un tratamiento que aplique exactamente la dosis necesaria dTuniformemente sobre el tumor a la vez que niguna dosis recae sobre regiones no afectadas. Pero en la práctica, esto no es factible, ya que las células tumorales se intercalan a nivel microscópico con células sanas. Es por ello que los especialistas dan por hecho que se va a aplicar o bien una dosis por defecto en la región tumoral (denotada zT), lo que permitirá sobrevivir a las células ma8CAPÍTULO 1. INTRODUCCIÓN. PROGRAMACIÓN LINEAL MULTIOBJETIVO 1.5. APLICACIONES REALES QUE USAN PROGRAMACIÓN LINEAL MULTIOBJETIVO lignas, o bien una dosis por exceso sobre tejido sano (denotada zS) o sobre las estructuras críticas (denotada zEk, para cada k= 1, . . . , l) , lo que puede agravar aún más la salud del paciente. Lo que se pretende conseguir entonces es minimizar todo lo posible estos errores a la hora de aplicar el tratamiento. El vector de variables de decisión será x∈Rn, que describe la intensidad determinada para cada rayo de radiación, donde nes el número total de rayos. La matriz A∈Rm×n, donde la entrada aij indentifica al rayo jen el punto de dosis i, según si estos puntos se situan sobre el tumor, sobre tejido sano o sobre estructuras críticas. Por tanto, Ax marcará el tratamiento aplicado en los puntos de dosis. Es necesario, además, fijar unas cotas superiores para evitar una dosis demasiado elevada que podría ocasionar efectos secundarios graves en el paciente. Se denotan estas por uT, uS, uEk, k = 1, . . . , l, según a qué regiones hagan referencia. Se asume que deben aplicarse a cada punto de la discretización. Con todo ello se puede modelizar el problema de la siguiente manera min (zT, zE1, . . . , zEl, zS) s.a ATx+zTe≥dT ATx≤uT AEkx−zEke≤uEk, k = 1, . . . , l ASx−zSe≤uS zEk≥ −uEk, k = 1, . . . , l zS≥0 x≥0 En este modelo, el objetivo es encontrar las soluciones eficientes (x, z)∈Rn+l+2 tales que minimizan simultáneamente la infradosificación en los tumores y la sobredosificación en las estructuras críticas y los tejidos sanos. 1.5.2. Compra de aviones de una compañía aérea A continuación se muestra otro ejemplo de aplicación práctica de la Programación Lineal Multiobjetivo. Este puede ser consultado en [Morales, 2014]. Se presenta el caso de una aerolínea que desea ampliar su flota para cubrir nuevas rutas de vuelo. Para ello pretende determinar el número óptimo de aeronaves que debe comprar. La compañía aérea baraja dos modelos diferentes de aviones, notados A y B, con diferentes características de capacidad, motor, alcance, autonomía y número de vuelos diarios máximos posibles, además de diferentes costes de adquisición, mantenimiento y consumo. Se consideran las variables aybcomo el número de aviones que se compran del modelo A y B, respectivamente. Como objetivos, la empresa se plantea, en primer lugar, maximizar el beneficio diario, medido en euros, resultante de los ingresos por actividad menos los gastos operativos. CAPÍTULO 1. INTRODUCCIÓN. PROGRAMACIÓN LINEAL MULTIOBJETIVO 9 1.5. APLICACIONES REALES QUE USAN PROGRAMACIÓN LINEAL MULTIOBJETIVO Por un lado, los ingresos proceden de los billetes diarios vendidos y dependen de la clase de esos pasajes; según sea turista (t) o business (s). Si se consideran los siguientes parámetros Pt,Ps: precio unitario de cada billete según la clase, tA,sA: número de pasajeros transportados por el modelo A según la clase, tB,sB: número de pasajeros transportados por el modelo B según la clase, se pueden modelar los ingresos como Ingresos =a[tAPt+sAPs] + b[tBPt+sBPs]. Por otro lado, los gastos corresponden a los costes diarios de poner en aire a los aviones. Considerando CA t,CA s: coste por pasajero en el modelo A según la clase, CB t,CB s: coste por pasajero en el modelo B según la clase, se tiene que Gastos =a[CA ttA+CA ssA] + b[CB ttB+CB ssB]. Por tanto, este criterio puede modelarse de la siguiente forma: Beneficio =Ingresos −Gastos = =a[tAPt+sAPs] + b[tBPt+sBPs]−a[CA ttA+CA ssA]−b[CB ttB+CB ssB] En segundo lugar, se quiere minimizar el consumo de combustible. Teniendo en cuenta que cA,cB: consumo por pasajero en el modelo A y B, respectivamente (expresado en litros por cada 100 kilómetros), se consigue modelar el consumo como Consumo =a[(tA+sA)cA] + b[(tB+sB)cB]. Además, como en toda situación real, se dan limitaciones en forma de restricciones. Existe un presupuesto disponible limitado en la empresa, procedente del beneficio y las amortizaciones acumuladas. Si se considera D: capital máximo disponible, GA,GB: precio de adquisición del modelo A y B respectivamente, esta restricción puede expresarse como GAa+GBb≤D. Es más, se puede aspirar a subvenciones si se cumplen ciertos requisitos. En este caso, se han de comprar un número mínimo, mA, de aviones del modelo A para poder aspirar a ellas: a≥mA. Tras un estudio de la demanda, se concluye que debe realizarse un número mínimo de viajes diario para poder cubrirla. Notando VA,VB: número de viajes al día que puede realizar el modelo A y B, respectivamente, U: número mínimo de viajes necesarios para satisfacer la demanda, se obtiene la siguiente restricción 10 CAPÍTULO 1. INTRODUCCIÓN. PROGRAMACIÓN LINEAL MULTIOBJETIVO 1.5. APLICACIONES REALES QUE USAN PROGRAMACIÓN LINEAL MULTIOBJETIVO VAa+VBb≥U. Por último cabe notar que, como es obvio, no puede comprarse un número negativo de aviones y, por tanto, se tiene la restricción de no negatividad a, b ≥0. Así pues, se ha conseguido establecer un modelo matemático de la situación real planteada, y queda como sigue: max a[tAPt+sAPs] + b[tBPt+sBPs]−a[CA ttA+CA ssA]−b[CB ttB+CB ssB] min a[(tA+sA)cA] + b[(tB+sB)cB] s.a. GAa+GBb≤D a≥mA VAa+VBb≥U a, b ≥0 CAPÍTULO 1. INTRODUCCIÓN. PROGRAMACIÓN LINEAL MULTIOBJETIVO 11 Capítulo 2 Métodos de resolución 2.1. Introducción En este capítulo se exponen algunos de los métodos más importantes utilizados tanto para generar el conjunto eficiente como para determinar la solución de mejor compromiso. El contenido completo de este capítulo ha sido desarrollado gracias a [Ríos Insúa, 1996] y [Ríos Insúa, 1997]. En primer lugar se describe el Método Simplex Multiobjetivo (Lee, 1972), que es una extensión del Método Simplex convencional para problemas lineales con un sólo objetivo. Seguidamente, se describen los métodos de las ponderaciones (Zadech, 1963) y de las ε-restricciones (Marglin, 1967), que tienen un amplio espectro de aplicaciones ya que también permiten ser usados en problemas de carácter no lineal. Interpretando estos métodos de forma adecuada se facilita la elección de la solución de mejor compromiso. Por último, se menciona la Programación por Metas (Charnes y Cooper, 1961), que está basada en el Método Simplex y tiene en cuenta el criterio del tomador de decisiones, lo que hace inmediato obtener la solución eficiente que más se adecúa a las preferencias del decisor. La diferencia entre el Método Simplex Multiobjetivo y el resto de métodos expuestos está en que el primero trabaja directamente con todas las funciones objetivo, mientras que los demás transforman el problema en uno unidimensional que puede ser resuelto convencionalmente. Figura 2.1: Métodos de resolución 13 2.1. INTRODUCCIÓN Existen casos particulares en los que el conjunto eficiente se puede obtener de manera sencilla haciendo uso de la representación gráfica sin necesidad de aplicar uno de los métodos anteriores. A continuación se presenta un ejemplo de ello para un problema biobjetivo. ■Ejemplo 2.1 Un cliente quiere proveer de luz cierto espacio y para ello dispone de dos tipos de producto de iluminación A y B, con características ecológicas y potenciales distintas. A su vez, desea considerar simultáneamente los objetivos (1): maximizar el ahorro energético (2): maximizar la luminosidad, que son, al menos, parcialmente contradictorios. Se toman las variables de decisión x1: decenas de unidades de producto A y x2: decenas de unidades de producto B, Se supone que el problema se modeliza con las funciones objetivo max f1(x) = −x1+x2(ahorro energético) max f2(x) = x1+ 2x2(luminosidad), las restricciones −x1+ 2x2≤8(control sujeto a normativa) x1+x2≤8(capacidad máxima total) x1≤6(capacidad máxima de producto A) y las condiciones de no negatividad x1, x2≥0. Se tiene, por tanto, el siguiente problema Multiobjetivo: max f(x) = (f1(x), f2(x)) = (−x1+x2, x1+ 2x2) s.a. −x1+2x2≤8 x1+x2≤8 x1≤6 x1, x2≥0 Equivalentemente, en forma matricial max f(x) = ((c1)Tx, (c2)Tx) s.a. Ax ≤b x≥0 En la Figura 2.2 se representa la región factible X del espacio de decisiones, que queda delimitada por las restricciones. Los puntos de X constituyen el conjunto de soluciones factibles. La región factible Ydel espacio de objetivos se calcula mediante f(X)=(f1(X), f2(X)) y queda representada en la Figura 2.3. Se observa que a cada punto extremo de X le corresponde uno y sólo un punto extremo de Y. 14 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.1. INTRODUCCIÓN Figura 2.2: Región factible del espacio de decisiones Figura 2.3: Región factible del espacio de objetivos Para identificar los puntos eficientes analizamos la información recogida en la siguiente tabla: Punto extremo de X (x1, x2)f(x1, x2)Punto extremo de Y O (0,0) (0,0) O’ A (0,4) (4,8) A’ B (8 3,16 3) (8 3,40 3) B’ C (6,2) (-4,10) C’ D (6,0) (-6,6) D’ Conviene recordar, como se vio en el Teorema 1.4.2, que para calcular el conjunto eficiente basta con examinar los puntos que están sobre la frontera de X. CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 15 2.1. INTRODUCCIÓN Se comienza considerando cada objetivo por separado y calculando su solución óptima. Para ello, se representan las curvas de nivel como aparecen en la Figura 2.4. Al ser dos funciones objetivo a maximizar, ambas tendrán sentido de movimiento ascendente. En el caso de la función objetivo f1(x) = −x1+x2, la curva de nivel que cumple con la solución óptima es la más alejada del origen (aparece en rojo con trazo continuo en la Figura 2.4) y el punto donde se consigue el valor objetivo máximo es el punto A, con f1(A) = 4. Análogamente ocurre con el objetivo f2(x) = x1+2x2, cuyas curvas de nivel (representadas en azul) alcanzan el valor objetivo máximo en el punto B y éste es f2(B) = 40 3≈13.33. Así, los puntos A y B son óptimos para uno de los objetivos y, de acuerdo con el Teorema 1.4.3, ambos son soluciones eficientes. Como los puntos A y B son adyacentes, se tiene que todos los puntos del segmento [A,B] son también eficientes, es decir, no existen otros puntos en el conjunto factible que mejoren el valor de una de las funciones objetivo sin causar una disminución en la otra. Ahora bien, se comprueba que no ocurre lo mismo con el resto de segmentos. Si consideramos, por ejemplo, el segmento [O′, A′]en la Figura 2.3, vemos que el punto A domina a todos los puntos restantes, esto es, mejora ambos objetivos simultáneamente, luego ninguno de los puntos restantes del segmento puede ser solución eficiente. De manera análoga puede verse en los demás segmentos. Así pues, se concluye que el conjunto eficiente Xef está formado todos los puntos del segmento [A, B]. Como observación, se puede ver en la Figura 2.4 que el punto que maximiza ambos objetivos (intersección entre las líneas continuas roja y azul) no está dentro de la región factible. Esto concuerda con la idea de que, en general, no existen soluciones óptimas para los problemas de Programación Multiobjetivo. Figura 2.4: Curvas de nivel ■ 16 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.2. MÉTODO SIMPLEX MULTIOBJETIVO Si x3entra en la base, entonces θ3=min{4 1/2}=4 1/2= 8, luego sale x2. Como θ1z1 1< θ3z1 3=⇒8/3·1/2=4/3<4=8·1/2 y θ1z1 1< θ3z1 3=⇒8/3·(−2) = −16/3<8=8·1 la columna a1es no dominada. Por tanto, introducir x1en la base proporciona una solución que domina a la solución que se obtiene al introducir x3en la base. PASO 16. Si a1entra en la base y x4sale se forma una base nueva no explorada anteriormente. PASO 17. h=h+ 1 = 2 + 1 = 3 B3={x2, x1, x5} Pivotar y construir la siguiente tabla del Simplex. c2→1 2 0 0 0 c1→-1 1 0 0 0 x20 1 1/3 1/3 0 16/3 x110 -1/3 2/3 0 8/3 x50 0 1/3 -2/3 1 10/3 z1→0 0 2/3 -1/3 0 8/3 z2→0 0 1/3 4/3 0 40/3 PASO 4. Solución básica factible asociada a B3: x3= x1 x2!= 8/3 16/3! PASO 5. La fila de costes reducidos z2tiene todas sus entradas no negativas, luego x3maximiza el objetivo f2. PASO 6. Además, todas las entradas de z2correspondientes a columnas no básicas (a3ya4) son estrictamente positivas luego x3maximiza el objetivo f2de forma única. Por tanto, x3es solución eficiente. PASO 9. Almacenar x3en el conjunto eficiente: Xef ={x2, x3}. g=g+ 1 = 1 + 1 = 2. PASO 10. Se busca una columna no básica (a3oa4) no dominada, al igual que hicimos anteriormente. Si x3entra en la base, entonces θ3=min{16/3 1/3,10/3 1/3}=10/3 1/3= 10, luego sale x5. Si x4entra en la base, entonces θ4=min{16/3 1/3,8/3 2/3}=8/3 2/3= 4, luego sale x1(esto daría una base ya explorada) CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 23 2.2. MÉTODO SIMPLEX MULTIOBJETIVO En este caso se tiene θ3z1 3> θ4z1 4=⇒10 ·2/3 = 20/3>−4/3 = 4 ·(−4/3) pero θ3z2 3< θ4z2 4=⇒10 ·1/3 = 10/3<16/3 = 4 ·4/3 luego ninguna columna domina sobre la otra. PASO 11. x3sí es eficiente. PASO 13. La columna no básica a4tiene sus entradas de costes reducidos positivos y negativos. PASO 14. No almacenamos la columna a4pues genera la base B2, que ya ha sido explorada. PASO 15. Se para el algoritmo. Se concluye, por tanto, que el conjunto eficiente está formado por los puntos extremos x2= 0 4!,x3= 8/3 16/3!, que corresponden a los puntos AyB, respectivamente, del Ejemplo 2.1, como era de esperar, y todos los puntos del segmento que los une: x=α·x2+ (1 −α)·x3,α∈(0,1). En la Figura 2.5 se aprecia el camino que recorre el algoritmo por la región factible hasta generar todo el conjunto eficiente. Figura 2.5: Conjunto eficiente. Método Simplex ■ 24 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.3. MÉTODO DE LAS PONDERACIONES 2.3. Método de las ponderaciones Se considera la siguiente notación para un problema lineal con k funciones objetivo: max f(x) = (f1(x), . . . , fk(x)) s.a. x∈X 2.3.1. Descripción del método Sea el vector λ= (λ1, . . . , λk), con λiel peso asociado al objetivo fi(x). Consideremos el siguiente problema, denotado P(λ): max p(x) = k X i=1 λifi(x) s.a. x∈X (2.2) El elemento λise interpreta como la relevancia o el peso relativo que el decisor da al objetivo i-ésimo fi(x)en relación a los demás. De esta manera, los objetivos tomarán importancia en el problema en orden de preferencia. El problema Multiobjetivo ha quedado transformado en un problema con un único objetivo p(x) a optimizar. Habiendo asignado los valores de λde manera razonable y una vez resuelto por alguno de los métodos convencionales, la solución óptima obtenida será directamente la de mejor compromiso para el decisor. El siguiente teorema da una condición suficiente para que la solución óptima de P(λ) sea eficiente. Teorema 2.3.1 Sea x∗solución óptima de P(λ). Si λi>0,∀i= 1, . . . , k, entonces x∗es eficiente para el problema Multiobjetivo original. El recíproco se verifica sólo bajo las hipótesis del siguiente teorema. Teorema 2.3.2 Sea X un poliedro convexo en Rn. Sean fi(x),∀i= 1, . . . , k las funciones objetivo. Sea x∗solución eficiente. Entonces existen valores λi>0,∀i= 1, . . . , k para los cuales x∗es solución óptima de P(λ). ■Ejemplo 2.3 Se retoma el Ejemplo 2.1, suponiendo que el decisor determina el vector de pesos λ= (λ1, λ2) = (1,2), esto es, da el doble de importancia al segundo objetivo respecto del primero. El problema uniobjetivo P(λ) queda como sigue: max p(x) = λ1f1(x) + λ2f2(x) = 1 ·(−x1+x2)+2·(x1+ 2x2) = x1+ 5x2 s.a. −x1+2x2≤8 x1+x2≤8 x1≤6 x1, x2≥0 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 25 2.3. MÉTODO DE LAS PONDERACIONES Resolviéndolo por el Método Simplex, se obtiene la solución óptima x∗= x∗ 1 x∗ 2!= 8/3 16/3!, que coincide con el punto extremo x3obtenido mediante el algoritmo del Simplex en el Ejemplo 2.2. Además, por el Teorema 2.3.1, queda asegurada su eficiencia pues el vector de pesos es estrictamente positivo. En la Figura 2.6 puede verse gráficamente que el punto x∗pertenece al conjunto eficiente. Figura 2.6: Solución eficiente. Método de las ponderaciones ■ 2.3.2. Generación del conjunto eficiente El método de las ponderaciones puede usarse para la generación del conjunto eficiente de la siguiente manera. Se comienza usualmente considerando los pesos λ= (1,0,...,0),(0,1,...,0),...,(0,0,...,1). De esta forma obtendremos kproblemas de optimización unidimensionales, uno para cada función objetivo. Seguidamente se hacen variar los valores de λconvenientemente. De esta manera se van generando puntos extremos del conjunto factible X. No es demasiado adecuado hacer uso del método de las ponderaciones para obtener el conjunto eficiente, pues en muchos casos se obtiene solo una aproximación de este. Surgen inconvenientes, por ejemplo, en el momento en que conjuntos de pesos distintos generan el mismo punto, o este es obtenido a partir de algún peso nulo, pues el Teorema 2.3.1 dice que no puede asegurarse su eficiencia. También puede darse el caso en que no se consigan generar todos los puntos extremos y por tanto se consideren como eficientes los puntos del segmento que une dos puntos no adyacentes. 26 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.3. MÉTODO DE LAS PONDERACIONES ■Ejemplo 2.4 Se considera ahora el problema genérico P(λ): max p(x) = λ1·(−x1+x2) + λ2·(x1+ 2x2) s.a. x∈X x≥0 Si se hace variar sistemáticamente el vector de pesos λ= (λ1, λ2)y se resuelven aquellos problemas unidimensionales que se van generando se consigue, al menos, una aproximación del conjunto eficiente. Conviene tomar valores de λestrictamente positivos para garantizar la eficiencia de las soluciones obtenidas. (λ1, λ2) (x∗ 1, x∗ 2) (1,1) (8 3,16 3) = B (2,1) (8 3,16 3) = B (1,3) (8 3,16 3) = B (3,2) (8 3,16 3) = B (4,1) (0,4) = A (5,1) (0,4) = A En base a los resultados se puede intuir que el conjunto eficiente lo forman los puntos del segmento que une A y B, ambos inclusive. ■ 2.3.3. Existencia de soluciones óptimas alternativas Se presenta una estrategia para evaluar la eficiencia de las soluciones óptimas alternativas, en el caso de que se hayan obtenido a partir de algún peso igual a cero. Se suponen nulos, sin pérdida de generalidad, todos los valores λia partir de un cierto p, esto es, λi(>0,si i= 1, . . . , p = 0,si i=p+ 1, . . . , k Resolviéndose el problema de optimización unidimensional (2.2) con la ponderación escogida, se obtiene una solución alternativa x∗= (x∗ 1, . . . , x∗ n)que verifica fi(x∗ 1, . . . , x∗ n) = z∗ i,i= 1, . . . , p. Tal solución alternativa se ha obtenido a partir de ciertos pesos nulos luego debe comprobarse su eficiencia. Para ello, se resuelve el siguiente problema de ponderaciones, denotado P0(λ), para un subconjunto de X. max p0(x) = p X i=1 λifi(x) s.a. x∈X fi(x1, . . . , xn) = z∗ i, i = 1, . . . , p CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 27 2.4. MÉTODO DE LAS ε-RESTRICCIONES Teorema 2.3.3 En las condiciones anteriores, si x∗= (x∗ 1, . . . , x∗ n)es solución óptima de P0(λ), entonces es eficiente. ■Ejemplo 2.5 Se supone ahora que el decisor da un vector de pesos λ= (2,0), en el que una de las componentes es nula. Resuelto por el método Simplex el problema del Ejemplo 2.4 para tales valores, se obtiene la solución óptima x∗= 0 4!, que verifica f1(x∗)=4. En este caso sabemos, por lo visto en los ejemplos anteriores, que se trata de un punto eficiente. De forma general, es necesario comprobar la eficiencia de la solución resolviendo el problema de ponderaciones P0(λ): max p0(x)=2·(−x1+x2)+0·(x1+ 2x2) = −2x1+ 2x2 s.a. x∈X f1(x) = −x1+x2= 4 Como cabe esperar, x∗es solución óptima luego es eficiente. ■ 2.4. Método de las ε-restricciones Se considera la siguiente notación para un problema lineal con k funciones objetivo: max f(x) = (f1(x), . . . , fk(x)) s.a. x∈X 2.4.1. Descripción del método Para aplicar este método, se requiere que una de las funciones objetivo tenga más relevancia para el decisor que el resto. Supongamos fr(x)tal objetivo. Se plantea el siguiente problema, denotado Pr(ε), en el que se busca optimizar el objetivo de mayor importancia y que añade una restricción en forma de cota inferior para cada uno de los demás: max fr(x) s.a. x∈X fi(x)≥εi, i = 1,...,r−1, r + 1, . . . , k donde εi,i= 1, . . . , r −1, r + 1, . . . , k son números reales que quedan a elección del decisor. De esta manera vuelve a obtenerse directamente la solución de mejor compromiso. En el caso en que Pr(ε)no tenga solución, habrá de reajustarse el problema relajando al menos una de las cotas inferiores impuestas. El siguiente teorema da una condición suficiente para que la solución óptima sea eficiente. Teorema 2.4.1 Si la solución óptima x∗de Pr(ε)es única, entonces x∗es eficiente. 28 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.4. MÉTODO DE LAS ε-RESTRICCIONES ■Ejemplo 2.6 Para resolver el problema considerado hasta ahora por el método de las ε− restricciones se supondrá que el objetivo más importante para el tomador de decisiones es el f2a la vez que se impone ε1= 5/2como cota inferior para el objetivo f2. Por lo visto previamente, se debe plantear y resolver el problema P2(ε): max f2(x) = x1+ 2x2 s.a. x∈X f1(x) = −x1+x2≥5/2 De nuevo, haciendo uso del Simplex, se obtiene el óptimo x∗= 8/3 16/3!que, por ser único, es eficiente (Teorema 2.4.1). Este punto es, de hecho, el punto B visto en el Ejemplo 2.1. ■ 2.4.2. Existencia de soluciones óptimas alternativas En el caso de que existan soluciones óptimas alternativas de Pr(ε)no puede asegurarse nada acerca de la eficiencia de éstas. Se presenta una estrategia para comprobar la eficiencia de una solución alternativa obtenida x∗= (x∗ 1, . . . , x∗ n). Se supone, sin pérdida de generalidad, que los objetivos f1, . . . , fpson aquellos que verifican las restricciones como igualdades en la solución óptima, es decir, fi(x∗) = εi,∀i= 1, . . . , p, incluido el objetivo escogido como el más importante (objetivo fr). Se resuelve el siguiente problema unidimensional, denotado P0(ε), que es análogo al presentado en el método de las ponderaciones, donde los objetivos f1, . . . , fppasan a ser restricciones: max fr(x) s.a. x∈X fi(x1, . . . , xn) = εi, i = 1, . . . , p Si x∗= (x∗ 1, . . . , x∗ n)es solución óptima de P0(ε), entonces queda comprobada su eficiencia. Si se escogen adecuadamente tanto la función objetivo fra optimizar como las cotas inferiores εi(i=r), el siguiente teorema asegura que toda solución eficiente es solución del problema Pr(ε). Teorema 2.4.2 Sea x∗solución eficiente. Entonces para todo valor de rexisten cotas inferiores εi(i=r)de manera que x∗sea solución óptima de Pr(ε). 2.4.3. Generación de soluciones eficientes El siguiente algoritmo conduce a soluciones eficientes. PASO 1. Tomar r= 1. Fijar cotas inferiores εi, i = 1, . . . , k, arbitrariamente. PASO 2. Obtener la solución óptima xrde Pr(ε). CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 29 2.4. MÉTODO DE LAS ε-RESTRICCIONES PASO 3. Si r=k, entonces se para el algoritmo. Si r < k, entonces si εr< fr(xr); cambiar εrpor fr(xr). Hacer r=r+ 1 e ir al PASO 2. ■Ejemplo 2.7 Un ejemplo de cómo aplicar el algortimo visto es el siguiente. PASO 1. r= 1. ε= (ε1, ε2) = (3,11) PASO 2. x1= 3/2 19/4!solución óptima única de P1(ε): max f1(x) = −x1+x2 s.a. x∈X f2(x) = x1+ 2x2≥11 PASO 3. r= 1 <2 = kyε1= 3 <13/4 = f1(x1)luego cambiar ε1por f1(x1). ε= (ε1, ε2) = (13/4,11) r=r+ 1 = 1 + 1 = 2 PASO 2. x2= 3/2 19/4!solución óptima única de P2(ε): max f2(x) = x1+ 2x2 s.a. x∈X f1(x) = −x1+x2≥13/4 PASO 3. r=2=kluego se para el algoritmo. El algoritmo ha conducido en dos iteraciones a la misma solución x1=x2, que como se observa en la Figura 2.7, pertenece al conjunto eficiente ya conocido. 30 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.5. PROGRAMACIÓN POR METAS Figura 2.7: Solución eficiente. Método de las ε−restricciones ■ 2.5. Programación por metas En este método, el tomador de decisiones fija un propósito a alcanzar en cada uno de los objetivos, de manera que se toma como solución óptima aquella que queda “lo más cerca posible” al mismo tiempo de todas las metas prefijadas. 2.5.1. Descripción del método Se considera el siguiente problema de programación uniobjetivo, denotado (P)M, donde ˜mies el nivel de aspiración que el decisor tiene para el objetivo fi: min d= k X i=1 |fi(x)−˜mi| s.a. x∈X Se pretende, por tanto, minimizar la suma de las diferencias entre los valores objetivo y sus metas, en valor absoluto. Hay que tener en cuenta que la función objetivo del problema (P)Mes de carácter no lineal. Alternativamente, puede transformarse en un problema lineal haciendo uso de las siguientes variables: d+ i=1 2(|fi(x)−˜mi|+ (fi(x)−˜mi) d− i=1 2(|fi(x)−˜mi| − (fi(x)−˜mi) que representan las ramas positiva (por exceso) y negativa (por defecto) de las diferencias entre cada valor objetivo y su meta propuesta. De esta manera, queda el siguiente problema equivalente, denotado (P′)M: CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 31 2.5. PROGRAMACIÓN POR METAS min d′= k X i=1 (d+ i+d− i) s.a. x∈X fi(x)−d+ i+d− i= ˜mi d+ i, d− i≥0,∀i= 1, . . . , k (2.3) La restricción fi(x)−d+ i+d− i= ˜mise conoce como restricción de meta. Ahora sí que puede aplicarse el método del Simplex para obtener una solución óptima de (P′)Mque, en general, no será eficiente para el (MOLP) original, por lo que habrá de comprobarse. ■Ejemplo 2.8 Por último, se resuelve de nuevo el Ejemplo 2.1, esta vez haciendo uso de la programación por metas. Se supone que el decisor fija las metas ˜m1= 3,˜m2= 15 para los objetivos f1yf2, respectivamente. El problema (P)Mpara estos datos concretos queda min d=| − x1+x2−3|+|x1+ 2x2−15| s.a. x∈X y haciendo uso de las variables auxiliares d+ 1=1 2(| − x1+x2−3|+ (−x1+x2−3)) d− 1=1 2(| − x1+x2−3| − (−x1+x2−3)) d+ 2=1 2(|x1+ 2x2−15|+ (x1+ 2x2−15)) d− 2=1 2(|x1+ 2x2−15| − (x1+ 2x2−15)) se transforma en (P′)M min d′= (d+ 1+d− 1) +(d+ 2+d− 2) s.a. −x1+2x2≤8 x1+x2≤8 x1≤6 −x1+x2−d+ 1+d− 1=3 x1+2x2−d+ 2+d− 2=15 x1, x2, d+ 1, d− 1, d+ 2, d− 2≥0 (2.4) Bastaría, por tanto, resolver este problema de Programación Lineal con un solo objetivo para obtener la solución de mejor compromiso. Esto queda pendiente para más adelante. ■ Este método será de utilidad para resolver cualquier problema de Programación Lineal Multiobjetivo mediante Software y se verá en el próximo Capítulo. 32 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 3.2. R set sVAR := 1..nvar; set sRES := 1..mres; set sOBJ := 1..nobj; param mc {sOBJ, sVAR}; param mA {sRES, sVAR}; param vb {sRES}; param vMetas {sOBJ}; var dmas {sOBJ} >= 0; var dmenos {sOBJ} >= 0; var x {sVAR} >= 0; minimize Obj_d: sum {k in sOBJ} (dmas[k] + dmenos[k]); s.t. rest_A {i in sRES}: sum {j in sVAR} mA[i,j] * x[j] <= vb[i]; s.t. rest_metas {k in sOBJ}: ( sum {j in sVAR} mc[k,j] * x[j] ) + ( - dmas[k] + dmenos[k] ) = vMetas[k]; " Análogamente para los datos que fueron definidos en el fichero .dat. data =" param nvar:= 2; param mres:= 3; param nobj:= 2; param mc : 1 2 := 1 -1 1 2 1 2; param mA : 1 2 := 1 -1 2 2 1 1 3 1 0; param vb:= 1 8 2 8 3 6; param vMetas:= 1 3 2 15; CAPÍTULO 3. RESOLUCIÓN CON SOFTWARE 39 3.2. R " Otra opción es guardar en una variable cada uno de los ficheros directamente. fic_ampl_modelo ="metas01.mod" fic_ampl_data ="metas01.dat" writeLines(modelo,fic_ampl_modelo) writeLines(data,fic_ampl_data) Por último, se ordena la resolución mediante los siguientes comandos: Se llama a la librería library(rAMPL) y se direcciona la ubicación de instalación. Debe ser la misma donde se instaló AMPL. dirinstall_ampl ="/home/rstudio/ampl.linux-intel64/" Mediante el comando new se crea el objeto, ampl =new(AMPL, new(Environment, dirinstall_ampl)) se interpretan las variables que contienen a los ficheros, ampl$reset() ampl$read(fic_ampl_modelo) ampl$readData(fic_ampl_data) se especifica el solver que se quiere utilizar, ampl$setOption("solver","cplex") y se ordena resolver. ampl$eval("option cplex_options 'sensitivity';") ampl$solve() ## CPLEX 20.1.0.0: sensitivity ## CPLEX 20.1.0.0: optimal solution; objective 2 ## 3 dual simplex iterations (0 in phase I) ## ## suffix up OUT; ## suffix down OUT; ## suffix current OUT; Se puede pedir también que imprima por pantalla la solución óptima obtenida ampl$eval("display x,dmas,dmenos;") ## : x dmas dmenos := ## 1 2.66667 0 0.333333 ## 2 5.33333 0 1.66667 ## ; y el enunciado del problema resuelto. 40 CAPÍTULO 3. RESOLUCIÓN CON SOFTWARE 3.2. R ampl$eval("expand;") ## minimize Obj_d: ## dmas[1] + dmas[2] + dmenos[1] + dmenos[2]; ## ## subject to rest_A[1]: ## -x[1] + 2*x[2] <= 8; ## ## subject to rest_A[2]: ## x[1] + x[2] <= 8; ## ## subject to rest_A[3]: ## x[1] <= 6; ## ## subject to rest_metas[1]: ## -dmas[1] + dmenos[1] - x[1] + x[2] = 3; ## ## subject to rest_metas[2]: ## -dmas[2] + dmenos[2] + x[1] + 2*x[2] = 15; Véase en la Figura 3.5 cómo se obtienen los mismos resultados haciendo uso de la librería rAMPL. Figura 3.5: Pantalla Rstudio. Uso de rAMPL ■ Para el desarrollo de esta sección y la comprensión de esta librería se ha consultado la información disponible en [rAM, b]. Cabe mencionar que para el uso de rAMPL es necesario tener instalado previamente el paquete “Rcpp”. CAPÍTULO 3. RESOLUCIÓN CON SOFTWARE 41 3.2. R 3.2.3. Paquete rMOIP Existe un paquete en R, llamado “gMOIP”, capaz de trabajar gráficamente (2D y 3D) con problemas lineales, ya sean continuos, enteros o mixtos, y permite hacer representaciones del espacio de decisiones y del espacio de objetivos de problemas bicriterio. Se presenta a continuación su funcionamiento recurriendo de nuevo al Ejemplo 2.1. ■Ejemplo 3.4 Representación del conjunto factible Se carga la librería library(gMOIP) Se definen los elementos del problema lineal biobjetivo con 2 variables #Matriz de restricciones A<- matrix(c(-1,2, 1,1, 1,0), ncol = 2,byrow = TRUE) #Vector lado derecho b<- c(8,8,6) #Matriz de objetivos obj <- matrix(c(-1,1,#primer objetivo 1,2), #segundo objetivo nrow = 2) Se define una nueva función para representarlo plotBiObj2D <- function(A, b, obj, type = rep("c", ncol(A)), #Variables continuas crit = "max",#Criterio de optimización faces = rep("c", ncol(A)), plotFaces = TRUE, plotFeasible = TRUE, plotOptimum = FALSE, labels = "numb", addTriangles = TRUE, addHull = TRUE) { p1 <- plotPolytope(A, b, type = type, crit = crit, faces = faces, plotFaces = plotFaces, plotFeasible = plotFeasible, plotOptimum = plotOptimum, labels = labels) + ggplot2::ggtitle("Espacio de decisiones") p2 <- plotCriterion2D(A, b, obj, type = type, crit = crit, addTriangles = addTriangles, addHull = addHull, plotFeasible = plotFeasible, labels = labels) + ggplot2::ggtitle("Espacio de objetivos") gridExtra::grid.arrange(p1, p2, nrow = 1) } 42 CAPÍTULO 3. RESOLUCIÓN CON SOFTWARE 3.2. R Se representa el conjunto factible del problema biobjetivo haciendo uso de la función previamente definida plotBiObj2D(A, b, obj, addTriangles = FALSE) 1 2 3 4 5 0 2 4 0246 x1 x2 Espacio de decisiones 1 2 3 4 5 0 5 10 −7.5 −5.0 −2.5 0.0 2.5 z1 z2 Espacio de objetivos Se observa que la función dibuja tanto la región factible del espacio de decisiones como la región factible del espacio de objetivos. La representación en dos dimensiones del espacio de objetivos permite identificar fácilmente los vértices eficientes y descartar los que no lo son. Así, en las gráficas obtenidas para este ejemplo, se aprecia que los puntos 1 y 3 en el espacio de objetivos son los objetivos asociados a las soluciones eficientes 1 y 3 (B y A respectivamente en la Figura 2.2) del espacio de decisiones. Esto concuerda con el hecho de que, si se pasa de 1 a 3 en el espacio de objetivos, mientras que el primer objetivo, considerado en el eje X, aumenta (mejora) su valor, el segundo objetivo, considerado en el eje Y, disminuye (empeora) su valor. Luego ambos son puntos no dominados, y sus respectivas soluciones en el espacio de decisiones, eficientes. Sin embargo, si se pasa de 5 a 3, o de 4 a 2, se ve que ambos objetivos aumentan (mejoran). Por tanto 3 domina a 5 y 2 domina a 4, por lo que ni 5 ni 4 serán soluciones eficientes. Generación de los puntos extremos del conjunto factible Otra gran utilidad a destacar del paquete gMOIP es la posibilidad de generar los puntos extremos del conjunto factible haciendo uso de la orden cornerPoints. cornerPoints(A, b, type = c("c","c")) ## x1 x2 ## [1,] 2.666667 5.333333 ## [2,] 6.000000 2.000000 ## [3,] 0.000000 4.000000 CAPÍTULO 3. RESOLUCIÓN CON SOFTWARE 43 3.3. CONCLUSIONES ## [4,] 6.000000 0.000000 ## [5,] 0.000000 0.000000 El vector type = c(“c”, “c”) indica que se tienen dos variables continuas. ■ Se ha consultado la documentación disponible en [Nielsen, 2021] y [rMO] referente al uso del paquete rMOIP. 3.3. Conclusiones El presente trabajo ha tratado de introducir al lector, de una forma gradual, en el ámbito de la Optimización Multiobjetivo; empezando por una primera parte eminentemente teórica, en la que se configura la estructura y sintaxis del modelo general; seguido de una parte central, en la que se exponen algunas de las distintas formas de abordar los problemas planteados en la parte precedente. Además, todo esto acompañado de ejemplos para favorecer la comprensión. Mediante el planteamiento de algunas situaciones reales que hacen uso de ella, se ha pretendido ilustrar la transversalidad que tiene la Programación Multiobjetivo en cualquier disciplina humana. Como bien es sabido, a día de hoy, la Programación Matemática no se entiende sin el soporte de un Software que facilite el manejo de grandes volúmenes de datos. Es por ello que, a modo de cierre de este trabajo, se han querido presentar algunas de las diversas herramientas de programación mediante Software disponibles, AMPL y R, para ejemplificar, de una manera tangible, lo que puede ser su uso a grandes escalas. El contenido de este trabajo abre las puertas al estudio de otras variantes de problemas Multiobjetivo, como pueden ser los de carácter no lineal, o aquellos que involucran variables enteras o mixtas. 44 CAPÍTULO 3. RESOLUCIÓN CON SOFTWARE Apéndice A Apéndice: Comprobación de la eficiencia de una solución A modo de Apéndice se ha querido implementar con Software el problema (2.1) para comprobar si una solución es eficiente o no para un problema Multiobjetivo, visto en el Método Simplex. Se recuerda su estructura max E= k X i=1 hi s.a. x∈X fi(x)−hi=fi(¯x), i = 1, . . . , k hi≥0, i = 1, . . . , k donde hison las variables de holgura consideradas. Como ya se vio, si E= 0, entonces la solución básica factible ¯xes eficiente para el problema multiobjetivo, y si E > 0, entonces no es posible asegurar la eficiencia de ¯x. Se procede con la definición de la función para unos datos con dimensiones y valores genéricos. En el desarrollo de esta, se recurre al paquete “lpSolve” visto en la sección 3.2.1. func_Comprobar_eficiencia_PLMult = function(mc, mA, vb, vdes, v_pto_c_Efi){ num_obj =nrow(mc) #Número objetivos num_filas_orig =nrow(mA) #Número restricciones criterio ="max" #Criterio de optimización mDmenos =- diag(num_obj) mA_amp_01 =cbind(mA,diag(0,nrow = num_filas_orig, ncol = num_obj)) mA_amp_02 =cbind(mc, mDmenos) mA_amp =rbind(mA_amp_01, mA_amp_02) #Nueva matriz restricciones vdes_amp =c(vdes,rep("=",num_obj)) #Nuevo vector desigualdades v_obj_x =as.numeric(mc %* % v_pto_c_Efi) 45 vb_amp =c(vb,v_obj_x) #Nuevo vector lado derecho vc_amp =c(rep(0,ncol(mc)), rep(1,num_obj)) #Nuevo vector objetivos #Resolución del problema uniobjetivo mediante el paquete lpSolve library(lpSolve) solucion =lp(direction = criterio, objective.in = vc_amp, const.mat = mA_amp, const.dir = vdes_amp, const.rhs = vb_amp) if (solucion$objval == 0) { mensaje ="AVISO: SÍ es una solución Eficiente!!"}#E = 0 else { mensaje ="AVISO: NO es una solución Eficiente!!"}#E > 0 print(mensaje) } ■Ejemplo A.1 Ahora se concretarán los datos para el Ejemplo que se ha usado a lo largo de todo el trabajo. En primer lugar, se definen los elementos del problema multiobjetivo original. mA =matrix(c(-1,2,#Matriz de restricciones 1,1, 1,0), nrow = 3,byrow = T) vb =c(8,8,6)#Vector lado derecho vdes =c("<=","<=","<=")#Vector de desigualdades mc =matrix(c(-1,1,#Matriz de objetivos 1,2), nrow = 2,byrow = T) Tal y como se vio, este par de puntos generados por el método del Simplex son eficientes, pues son óptimos para cada uno de los objetivos por separado. Esto se comprobó en el Ejemplo 2.2 viendo que la fila de costes reducidos asociada al objetivo en concreto tenía todas sus entradas no negativas. #Coincide con el punto x_2 y maximiza el objetivo f_1. pto_efi_01 =c(0,4) #Coincide con el punto x_3 y maximiza el objetivo f_2. pto_efi_02 =c(8/3,16/3) Haciendo uso de la función previamente definida, se ve que ambos son eficientes. func_Comprobar_eficiencia_PLMult(mc, mA, vb, vdes, v_pto_c_Efi = pto_efi_01) 46 APÉNDICE A. APÉNDICE: COMPROBACIÓN DE LA EFICIENCIA DE UNA SOLUCIÓN ## [1] "AVISO: SÍ es una solución Eficiente!!" func_Comprobar_eficiencia_PLMult(mc, mA, vb, vdes, v_pto_c_Efi = pto_efi_02) ## [1] "AVISO: SÍ es una solución Eficiente!!" A continuación se puede ver que, efectivamente, los puntos de la cara del poliedro que une los puntos anteriores son eficientes. Se comprueba dando valores al parámetro alfa. alfa =0.6 #0.2, 0.3, 0.4, 0.5, 0.9, 1 func_Comprobar_eficiencia_PLMult(mc, mA, vb, vdes, v_pto_c_Efi = alfa * pto_efi_01 + (1-alfa)*pto_efi_02) ## [1] "AVISO: SÍ es una solución Eficiente!!" Sin embargo, las filas de costes reducidos para el siguiente punto no tenían todas sus entradas estrictamente positivas luego es necesario comprobar su eficiencia. pto_01 =c(0,0)#Coincide con el punto x_1 Como puede verse, el punto no es eficiente para el problema multiobjetivo. func_Comprobar_eficiencia_PLMult(mc, mA, vb, vdes, v_pto_c_Efi = pto_01) ## [1] "AVISO: NO es una solución Eficiente!!" De igual modo puede comprobarse la eficiencia de los vértices restantes del conjunto factible. pto_02 =c(6,0) pto_03 =c(6,2) En este caso, tampoco se trata de soluciones eficientes. func_Comprobar_eficiencia_PLMult(mc, mA, vb, vdes, v_pto_c_Efi = pto_02) ## [1] "AVISO: NO es una solución Eficiente!!" func_Comprobar_eficiencia_PLMult(mc, mA, vb, vdes, v_pto_c_Efi = pto_03) ## [1] "AVISO: NO es una solución Eficiente!!" ■ APÉNDICE A. APÉNDICE: COMPROBACIÓN DE LA EFICIENCIA DE UNA SOLUCIÓN 47