Introducción a la programación lineal multiobjetivo

Facul ad de Ma emá icas Depa amen o de Es adís ica e In es igación Ope a i a G ado en Ma emá icas INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL MULTIOBJETIVO T abajo Fin de G ado Au o a: El i a Ma ínez Sánchez Supe isado po : Ped o Luis Luque Cal o Sep iemb e 2022 Índice gene al P ólogo ....................................... iii Resumen....................................... Abs ac ....................................... i ÍndicedeFigu as.................................. ii 1. In oducción. P og amación Lineal Mul iobje i o 1 1.1. Con ex ohis ó ico .............................. 1 1.2. Concep osp e ios............................... 2 1.3. De iniciones básicas. Plan eamien o del p oblema . . . . . . . . . . . . . 4 1.4. Op imalidad.................................. 6 1.5. Aplicaciones eales que usan P og amación Lineal Mul iobje i o . . . . . 8 1.5.1. Diseño de a amien os de adio e apia . . . . . . . . . . . . . . . 8 1.5.2. Comp a de a iones de una compañía aé ea . . . . . . . . . . . . . 9 2. Mé odos de esolución 13 2.1. In oducción.................................. 13 2.2. Mé odo Simplex Mul iobje i o . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.1. Desc ipción del mé odo . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2. Comp obación de la e iciencia de una solución . . . . . . . . . . . 19 2.2.3. Algo i mo del Simplex Mul iobje i o . . . . . . . . . . . . . . . . 19 2.3. Mé odo de las ponde aciones . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.1. Desc ipción del mé odo . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.2. Gene ación del conjun o e icien e . . . . . . . . . . . . . . . . . . 26 2.3.3. Exis encia de soluciones óp imas al e na i as . . . . . . . . . . . . 27 2.4. Mé odo de las ε- es icciones......................... 28 2.4.1. Desc ipción del mé odo . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.2. Exis encia de soluciones óp imas al e na i as . . . . . . . . . . . . 29 2.4.3. Gene ación de soluciones e icien es . . . . . . . . . . . . . . . . . 29 2.5. P og amación po me as . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.5.1. Desc ipción del mé odo . . . . . . . . . . . . . . . . . . . . . . . . 31 3. Resolución con so wa e 33 3.1. AMPL..................................... 33 3.2. R........................................ 36 3.2.1. Paque eLpSol e ........................... 37 3.2.2. Lib e ía AMPL............................ 38 3.2.3. Paque e MOIP............................ 42 3.3. Conclusiones.................................. 44 i A. Apéndice: Comp obación de la e iciencia de una solución 45 Bibliog a ía 50 ii P ólogo Me gus a ía ag adece a mi amilia su apoyo incondicional y su con ianza en mí a lo la go de odos es os años. Sin su sos én no hab ía conseguido llega has a aquí. Quisie a ag adece ambién a mi u o , Ped o Luis Luque Cal o, po la dedicación que ha pues o en mi abajo y el apoyo que ha supues o pa a mí. iii Resumen Es e abajo p e ende se i de in oducción a la P og amación Lineal Mul iobje i o, á ea de la Op imización Ma emá ica que in oluc a múl iples c i e ios, ecuen emen e con lic i os en e sí. Más conc e amen e, se ciñe a aquellos p oblemas en los que in e ie- nen únicamen e unciones de ca ác e lineal. Después de hace una b e e in oducción his ó ica, se p esen a el modelo gene al, así como las p incipales de iniciones y esul ados. Se exponen ambién di e en es mé odos con los que esol e p oblemas de P og amación Mul iobje i o, siendo es e el con enido de mayo peso en el abajo. A lo la go del mismo, un ejemplo en común se i á de hilo conduc o pa a ilus a el uncionamien o de cada uno de los mé odos expues os. Pa a inaliza , se mues a un mé odo gene alizado que esuel e p oblemas de P og a- mación Lineal Mul iobje i o con ayuda de so wa e disponible: AMPL y R. Abs ac This s udy is hough o be an in oduc ion o Mul iobjec i e Linea P og amming, an a ea o he Ma hema ical Op imisa ion ha in ol es mul iple c i e ia, usually con lic ing among hem. Mo e speci ically, i ocuses on hose p oblems which only in ol e linea unc ions. A e a b ie his o ical backg ound, he gene al model is in oduced, as well as he main de ini ions and esul s. Di e en me hods used o sol e Mul iobjec i e P og amming p oblems a e also p esen ed, con en which is conside ed o be he co e one in his pape . Th oughou he s udy, a common example is used as a guiding h ead o illus a e he unc ioning o all o he displayed me hods. Finally, a gene alised me hod ha sol es Mul iobjec i e Linea P og amming p oblems wi h he help o an a ailable so wa e is shown: AMPL and R. i Índice de igu as 2.1. Mé odosde esolución ............................ 13 2.2. Región ac ible del espacio de decisiones . . . . . . . . . . . . . . . . . . 15 2.3. Región ac ible del espacio de obje i os . . . . . . . . . . . . . . . . . . . 15 2.4. Cu asdeni el ................................ 16 2.5. Conjun o e icien e. Mé odo Simplex . . . . . . . . . . . . . . . . . . . . . 24 2.6. Solución e icien e. Mé odo de las ponde aciones . . . . . . . . . . . . . . 26 2.7. Solución e icien e. Mé odo de las ε− es icciones . . . . . . . . . . . . . 31 3.1. LogodeAMPL ................................ 33 3.2. Pan allaAMPLide .............................. 36 3.3. LogodeRS udio ............................... 36 3.4. Pan alla Rs udio. Uso de lpSol e . . . . . . . . . . . . . . . . . . . . . . 38 3.5. Pan alla Rs udio. Uso de AMPL . . . . . . . . . . . . . . . . . . . . . . 41 ii 1.4. OPTIMALIDAD Pk j=1(1 + MPi=jλi j) j(x)≤Pk j=1(1 + MPi=jλi j) j(x∗) ∀x∈X. ⇐⌟Se supone que ∃λ= (λ1, . . . , λk)∈Λ al que x∗es solución óp ima del p oblema de un sólo obje i o (Pλ). Es i ial que x∗es e icien e pa a (MOLP). Se demues a que es p opiamen e e icien e, con M= (k−1) ·m´axi,j{λj λi},k≥2 Po educción al absu do, se supone que x∗no es p opiamen e e icien e pa a (MOLP). En onces, pa a algún obje i o iy pa a algún x∈Xse iene i(x)− i(x∗)> M ·( j(x∗)− j(x)),∀j al que j(x)< j(x∗) Como consecuencia di ec a se iene i(x)− i(x∗)>k−1 λiλj·( j(x∗)− j(x)),∀j=i Mul iplicando po λi k−1y sumando en j se iene λi( i(x)− i(x∗)) >Pj=iλj( j(x∗)− j(x)) Es o es absu do, pues se ha supues o que x∗es óp imo pa a (Pλ). ■ Es e eo ema, que puede se consul ado en [Geo ion, 1968], iene g an u ilidad desde el pun o de is a compu acional, pues educe a un p oblema de p og amación pa amé ico encon a soluciones p opiamen e e icien es. Teo ema 1.4.2 El conjun o Xe de soluciones e icien es del p oblema (1.1) iene las siguien es p opiedades: (i) Si un pun o in e io de una ca a del polied o Xes e icien e, en onces odos los pun os de esa ca a lo son. (ii) Si X iene un é ice y (1.1) iene una solución e icien e, en onces iene una solución e icien e en un é ice de X. (iii) Xe consis e en ca as del polied o Xy es ce ado y conexo po a co. Es e eo ema es de suma impo ancia pues implica que a la ho a de busca el conjun o e icien e bas a con examina los pun os de la on e a del polied o X. Es o e i a ene que conside a odo el conjun o de soluciones ac ibles, lo que supone un aho o eno me de iempo y es ue zo. Teo ema 1.4.3 Sea x∈Xun pun o ac ible. Si x es solución óp ima única pa a el p oblema uniobje i o asociado a alguna de las unciones c i e io del p oblema (1.1), en onces x es e icien e pa a (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 eales que usan P og amación Li- neal Mul iobje i o De acue do con [Ríos Insúa, 1996], los p oblemas de P og amación Mul iobje i o su gen en los p ocesos de oma de decisiones en mul i ud de á eas de la ac i idad humana ales como la economía, la ingenie ía, el anspo e, la medicina, e c. En pa icula , la P og amación Lineal Mul iobje i o iene impo an ísimas aplicaciones en la ida eal. En es e apa ado se ecogen un pa de ejemplos de ello. En p ime luga , se p esen a una si uación eal que puede se más o menos compleja y que se desea sol en a . En el plan eamien o del p oblema in e ienen cie os obje i os a los que se p e ende aspi a con la aplicación de al supues a solución. Además, se imponen ambién una se ie de eque imien os que deben cumpli se pa a que la solución sea sa is ac o ia. Todo es e escena io que a p io i puede pa ece di ícil de maneja , se consigue modela en o ma de a iables, unciones obje i o y es icciones. De es a mane a, haciendo uso de las dis in as es a egias que ya exis en pa a esol e es os p oblemas (algunas de ellas se án expues as en el p óximo capí ulo) se ob end án aquellas soluciones que encajen lo mejo posible con lo que se p e ende consegui en la si uación eal en conc e o. En úl ima ins ancia, se án los expe os de la ma e ia en cues ión o los posibles in e e- sados los que ac úen como omado es de decisiones. 1.5.1. Diseño de a amien os de adio e apia De una mane a simpli icada se p esen a un ejemplo de modelización pa a el diseño de un a amien o de adio e apia pa a a a casos de cánce . Es e ejemplo se menciona en [Eh go , 2005] y hace e e encia a la in es igación desa ollada en [Sonde man and Ab ahamson, 1985]. La e apia de adiación se usa en medicina en el a amien o de en e medades umo ales. Median e la aplicación de ayos de adiación de una o ma de e minada, se consigue daña el ADN de las células cance ígenas y po consiguien e, ena su a ance en el o ganismo del pacien e. Exis e ecnología capaz de modula de mane a independien e la di ección e in ensidad de cada ayo del conjun o de ayos de adiación o ales. Pa a conc e a en qué zonas se a a aplica el a amien o, se disc e iza el cue po del pacien e en mpun os de dosis. Cada pun o de la disc e ización se supone clasi icado en es g upos según se localice en el umo T, en ejido sano So en alguna de las l es uc u as c í icas {E1, . . . , El}. La dosis umo al p esc i a po el especialis a iene dada po dT. El obje i o u ópico se ía diseña un a amien o que aplique exac amen e la dosis necesa ia dTuni o memen e sob e el umo a la ez que niguna dosis ecae sob e egiones no a ec adas. Pe o en la p ác ica, es o no es ac ible, ya que las células umo ales se in e calan a ni el mic oscópico con células sanas. Es po ello que los especialis as dan po hecho que se a a aplica o bien una dosis po de ec o en la egión umo al (deno ada zT), lo que pe mi i á sob e i i a las células ma- 8CAPÍTULO 1. INTRODUCCIÓN. PROGRAMACIÓN LINEAL MULTIOBJETIVO 1.5. APLICACIONES REALES QUE USAN PROGRAMACIÓN LINEAL MULTIOBJETIVO lignas, o bien una dosis po exceso sob e ejido sano (deno ada zS) o sob e las es uc u as c í icas (deno ada zEk, pa a cada k= 1, . . . , l) , lo que puede ag a a aún más la salud del pacien e. Lo que se p e ende consegui en onces es minimiza odo lo posible es os e o es a la ho a de aplica el a amien o. El ec o de a iables de decisión se á x∈Rn, que desc ibe la in ensidad de e minada pa a cada ayo de adiación, donde nes el núme o o al de ayos. La ma iz A∈Rm×n, donde la en ada aij inden i ica al ayo jen el pun o de dosis i, según si es os pun os se si uan sob e el umo , sob e ejido sano o sob e es uc u as c í icas. Po an o, Ax ma ca á el a amien o aplicado en los pun os de dosis. Es necesa io, además, ija unas co as supe io es pa a e i a una dosis demasiado ele- ada que pod ía ocasiona e ec os secunda ios g a es en el pacien e. Se deno an es as po uT, uS, uEk, k = 1, . . . , l, según a qué egiones hagan e e encia. Se asume que deben aplica se a cada pun o de la disc e ización. Con odo ello se puede modeliza el p oblema de la siguien e mane a 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 es e modelo, el obje i o es encon a las soluciones e icien es (x, z)∈Rn+l+2 ales que minimizan simul áneamen e la in adosi icación en los umo es y la sob edosi icación en las es uc u as c í icas y los ejidos sanos. 1.5.2. Comp a de a iones de una compañía aé ea A con inuación se mues a o o ejemplo de aplicación p ác ica de la P og amación Lineal Mul iobje i o. Es e puede se consul ado en [Mo ales, 2014]. Se p esen a el caso de una ae olínea que desea amplia su lo a pa a cub i nue as u as de uelo. Pa a ello p e ende de e mina el núme o óp imo de ae ona es que debe comp a . La compañía aé ea ba aja dos modelos di e en es de a iones, no ados A y B, con di e en es ca ac e ís icas de capacidad, mo o , alcance, au onomía y núme o de uelos dia ios máximos posibles, además de di e en es cos es de adquisición, man enimien o y consumo. Se conside an las a iables aybcomo el núme o de a iones que se comp an del modelo A y B, espec i amen e. Como obje i os, la emp esa se plan ea, en p ime luga , maximiza el bene icio dia io, medido en eu os, esul an e de los ing esos po ac i idad menos los gas os ope a i os. CAPÍTULO 1. INTRODUCCIÓN. PROGRAMACIÓN LINEAL MULTIOBJETIVO 9 1.5. APLICACIONES REALES QUE USAN PROGRAMACIÓN LINEAL MULTIOBJETIVO Po un lado, los ing esos p oceden de los bille es dia ios endidos y dependen de la clase de esos pasajes; según sea u is a ( ) o business (s). Si se conside an los siguien es pa áme os P ,Ps: p ecio uni a io de cada bille e según la clase, A,sA: núme o de pasaje os anspo ados po el modelo A según la clase, B,sB: núme o de pasaje os anspo ados po el modelo B según la clase, se pueden modela los ing esos como Ing esos =a[ AP +sAPs] + b[ BP +sBPs]. Po o o lado, los gas os co esponden a los cos es dia ios de pone en ai e a los a iones. Conside ando CA ,CA s: cos e po pasaje o en el modelo A según la clase, CB ,CB s: cos e po pasaje o en el modelo B según la clase, se iene que Gas os =a[CA A+CA ssA] + b[CB B+CB ssB]. Po an o, es e c i e io puede modela se de la siguien e o ma: Bene icio =Ing esos −Gas os = =a[ AP +sAPs] + b[ BP +sBPs]−a[CA A+CA ssA]−b[CB B+CB ssB] En segundo luga , se quie e minimiza el consumo de combus ible. Teniendo en cuen a que cA,cB: consumo po pasaje o en el modelo A y B, espec i amen e (exp esado en li os po cada 100 kilóme os), se consigue modela el consumo como Consumo =a[( A+sA)cA] + b[( B+sB)cB]. Además, como en oda si uación eal, se dan limi aciones en o ma de es icciones. Exis e un p esupues o disponible limi ado en la emp esa, p oceden e del bene icio y las amo izaciones acumuladas. Si se conside a D: capi al máximo disponible, GA,GB: p ecio de adquisición del modelo A y B espec i amen e, es a es icción puede exp esa se como GAa+GBb≤D. Es más, se puede aspi a a sub enciones si se cumplen cie os equisi os. En es e caso, se han de comp a un núme o mínimo, mA, de a iones del modelo A pa a pode aspi a a ellas: a≥mA. T as un es udio de la demanda, se concluye que debe ealiza se un núme o mínimo de iajes dia io pa a pode cub i la. No ando VA,VB: núme o de iajes al día que puede ealiza el modelo A y B, espec i amen e, U: núme o mínimo de iajes necesa ios pa a sa is ace la demanda, se ob iene la siguien e es icción 10 CAPÍTULO 1. INTRODUCCIÓN. PROGRAMACIÓN LINEAL MULTIOBJETIVO 1.5. APLICACIONES REALES QUE USAN PROGRAMACIÓN LINEAL MULTIOBJETIVO VAa+VBb≥U. Po úl imo cabe no a que, como es ob io, no puede comp a se un núme o nega i o de a iones y, po an o, se iene la es icción de no nega i idad a, b ≥0. Así pues, se ha conseguido es ablece un modelo ma emá ico de la si uación eal plan- eada, y queda como sigue: max a[ AP +sAPs] + b[ BP +sBPs]−a[CA A+CA ssA]−b[CB B+CB ssB] min a[( A+sA)cA] + b[( B+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í ulo 2 Mé odos de esolución 2.1. In oducción En es e capí ulo se exponen algunos de los mé odos más impo an es u ilizados an o pa a gene a el conjun o e icien e como pa a de e mina la solución de mejo comp omiso. El con enido comple o de es e capí ulo ha sido desa ollado g acias a [Ríos Insúa, 1996] y [Ríos Insúa, 1997]. En p ime luga se desc ibe el Mé odo Simplex Mul iobje i o (Lee, 1972), que es una ex ensión del Mé odo Simplex con encional pa a p oblemas lineales con un sólo obje i o. Seguidamen e, se desc iben los mé odos de las ponde aciones (Zadech, 1963) y de las ε- es icciones (Ma glin, 1967), que ienen un amplio espec o de aplicaciones ya que ambién pe mi en se usados en p oblemas de ca ác e no lineal. In e p e ando es os mé odos de o ma adecuada se acili a la elección de la solución de mejo comp omiso. Po úl imo, se menciona la P og amación po Me as (Cha nes y Coope , 1961), que es á basada en el Mé odo Simplex y iene en cuen a el c i e io del omado de decisiones, lo que hace inmedia o ob ene la solución e icien e que más se adecúa a las p e e encias del deciso . La di e encia en e el Mé odo Simplex Mul iobje i o y el es o de mé odos expues os es á en que el p ime o abaja di ec amen e con odas las unciones obje i o, mien as que los demás ans o man el p oblema en uno unidimensional que puede se esuel o con encionalmen e. Figu a 2.1: Mé odos de esolución 13 2.1. INTRODUCCIÓN Exis en casos pa icula es en los que el conjun o e icien e se puede ob ene de mane a sencilla haciendo uso de la ep esen ación g á ica sin necesidad de aplica uno de los mé odos an e io es. A con inuación se p esen a un ejemplo de ello pa a un p oblema biobje i o. ■Ejemplo 2.1 Un clien e quie e p o ee de luz cie o espacio y pa a ello dispone de dos ipos de p oduc o de iluminación A y B, con ca ac e ís icas ecológicas y po enciales dis in as. A su ez, desea conside a simul áneamen e los obje i os (1): maximiza el aho o ene gé ico (2): maximiza la luminosidad, que son, al menos, pa cialmen e con adic o ios. Se oman las a iables de decisión x1: decenas de unidades de p oduc o A y x2: decenas de unidades de p oduc o B, Se supone que el p oblema se modeliza con las unciones obje i o max 1(x) = −x1+x2(aho o ene gé ico) max 2(x) = x1+ 2x2(luminosidad), las es icciones −x1+ 2x2≤8(con ol suje o a no ma i a) x1+x2≤8(capacidad máxima o al) x1≤6(capacidad máxima de p oduc o A) y las condiciones de no nega i idad x1, x2≥0. Se iene, po an o, el siguien e p oblema Mul iobje i o: max (x) = ( 1(x), 2(x)) = (−x1+x2, x1+ 2x2) s.a. −x1+2x2≤8 x1+x2≤8 x1≤6 x1, x2≥0 Equi alen emen e, en o ma ma icial max (x) = ((c1)Tx, (c2)Tx) s.a. Ax ≤b x≥0 En la Figu a 2.2 se ep esen a la egión ac ible X del espacio de decisiones, que queda delimi ada po las es icciones. Los pun os de X cons i uyen el conjun o de soluciones ac ibles. La egión ac ible Ydel espacio de obje i os se calcula median e (X)=( 1(X), 2(X)) y queda ep esen ada en la Figu a 2.3. Se obse a que a cada pun o ex emo de X le co esponde uno y sólo un pun o ex emo de Y. 14 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.1. INTRODUCCIÓN Figu a 2.2: Región ac ible del espacio de decisiones Figu a 2.3: Región ac ible del espacio de obje i os Pa a iden i ica los pun os e icien es analizamos la in o mación ecogida en la siguien e abla: Pun o ex emo de X (x1, x2) (x1, x2)Pun o ex emo 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’ Con iene eco da , como se io en el Teo ema 1.4.2, que pa a calcula el conjun o e icien e bas a con examina los pun os que es án sob e la on e a de X. CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 15 2.1. INTRODUCCIÓN Se comienza conside ando cada obje i o po sepa ado y calculando su solución óp ima. Pa a ello, se ep esen an las cu as de ni el como apa ecen en la Figu a 2.4. Al se dos unciones obje i o a maximiza , ambas end án sen ido de mo imien o ascenden e. En el caso de la unción obje i o 1(x) = −x1+x2, la cu a de ni el que cumple con la solución óp ima es la más alejada del o igen (apa ece en ojo con azo con inuo en la Figu a 2.4) y el pun o donde se consigue el alo obje i o máximo es el pun o A, con 1(A) = 4. Análogamen e ocu e con el obje i o 2(x) = x1+2x2, cuyas cu as de ni el ( ep esen a- das en azul) alcanzan el alo obje i o máximo en el pun o B y és e es 2(B) = 40 3≈13.33. Así, los pun os A y B son óp imos pa a uno de los obje i os y, de acue do con el Teo ema 1.4.3, ambos son soluciones e icien es. Como los pun os A y B son adyacen es, se iene que odos los pun os del segmen o [A,B] son ambién e icien es, es deci , no exis en o os pun os en el conjun o ac ible que mejo en el alo de una de las unciones obje i o sin causa una disminución en la o a. Aho a bien, se comp ueba que no ocu e lo mismo con el es o de segmen os. Si consi- de amos, po ejemplo, el segmen o [O′, A′]en la Figu a 2.3, emos que el pun o A domina a odos los pun os es an es, es o es, mejo a ambos obje i os simul áneamen e, luego nin- guno de los pun os es an es del segmen o puede se solución e icien e. De mane a análoga puede e se en los demás segmen os. Así pues, se concluye que el conjun o e icien e Xe es á o mado odos los pun os del segmen o [A, B]. Como obse ación, se puede e en la Figu a 2.4 que el pun o que maximiza ambos obje i os (in e sección en e las líneas con inuas oja y azul) no es á den o de la egión ac ible. Es o concue da con la idea de que, en gene al, no exis en soluciones óp imas pa a los p oblemas de P og amación Mul iobje i o. Figu a 2.4: Cu as de ni el ■ 16 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.2. MÉTODO SIMPLEX MULTIOBJETIVO Si x3en a en la base, en onces θ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. Po an o, in oduci x1en la base p opo ciona una solución que domina a la solución que se ob iene al in oduci x3en la base. PASO 16. Si a1en a en la base y x4sale se o ma una base nue a no explo ada an e io men e. PASO 17. h=h+ 1 = 2 + 1 = 3 B3={x2, x1, x5} Pi o a y cons ui la siguien e abla 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 ac ible asociada a B3: x3= x1 x2!= 8/3 16/3! PASO 5. La ila de cos es educidos z2 iene odas sus en adas no nega i as, luego x3maximiza el obje i o 2. PASO 6. Además, odas las en adas de z2co espondien es a columnas no básicas (a3ya4) son es ic amen e posi i as luego x3maximiza el obje i o 2de o ma única. Po an o, x3es solución e icien e. PASO 9. Almacena x3en el conjun o e icien e: Xe ={x2, x3}. g=g+ 1 = 1 + 1 = 2. PASO 10. Se busca una columna no básica (a3oa4) no dominada, al igual que hicimos an e io - men e. Si x3en a en la base, en onces θ3=min{16/3 1/3,10/3 1/3}=10/3 1/3= 10, luego sale x5. Si x4en a en la base, en onces θ4=min{16/3 1/3,8/3 2/3}=8/3 2/3= 4, luego sale x1(es o da ía una base ya explo ada) CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 23 2.2. MÉTODO SIMPLEX MULTIOBJETIVO En es e caso se iene θ3z1 3> θ4z1 4=⇒10 ·2/3 = 20/3>−4/3 = 4 ·(−4/3) pe o θ3z2 3< θ4z2 4=⇒10 ·1/3 = 10/3<16/3 = 4 ·4/3 luego ninguna columna domina sob e la o a. PASO 11. x3sí es e icien e. PASO 13. La columna no básica a4 iene sus en adas de cos es educidos posi i os y nega i os. PASO 14. No almacenamos la columna a4pues gene a la base B2, que ya ha sido explo ada. PASO 15. Se pa a el algo i mo. Se concluye, po an o, que el conjun o e icien e es á o mado po los pun os ex emos x2= 0 4!,x3= 8/3 16/3!, que co esponden a los pun os AyB, espec i amen e, del Ejemplo 2.1, como e a de espe a , y odos los pun os del segmen o que los une: x=α·x2+ (1 −α)·x3,α∈(0,1). En la Figu a 2.5 se ap ecia el camino que eco e el algo i mo po la egión ac ible has a gene a odo el conjun o e icien e. Figu a 2.5: Conjun o e icien e. Mé odo Simplex ■ 24 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.3. MÉTODO DE LAS PONDERACIONES 2.3. Mé odo de las ponde aciones Se conside a la siguien e no ación pa a un p oblema lineal con k unciones obje i o: max (x) = ( 1(x), . . . , k(x)) s.a. x∈X 2.3.1. Desc ipción del mé odo Sea el ec o λ= (λ1, . . . , λk), con λiel peso asociado al obje i o i(x). Conside emos el siguien e p oblema, deno ado P(λ): max p(x) = k X i=1 λi i(x) s.a. x∈X (2.2) El elemen o λise in e p e a como la ele ancia o el peso ela i o que el deciso da al obje i o i-ésimo i(x)en elación a los demás. De es a mane a, los obje i os oma án impo ancia en el p oblema en o den de p e e encia. El p oblema Mul iobje i o ha quedado ans o mado en un p oblema con un único obje i o p(x) a op imiza . Habiendo asignado los alo es de λde mane a azonable y una ez esuel o po alguno de los mé odos con encionales, la solución óp ima ob enida se á di ec amen e la de mejo comp omiso pa a el deciso . El siguien e eo ema da una condición su icien e pa a que la solución óp ima de P(λ) sea e icien e. Teo ema 2.3.1 Sea x∗solución óp ima de P(λ). Si λi>0,∀i= 1, . . . , k, en onces x∗es e icien e pa a el p oblema Mul iobje i o o iginal. El ecíp oco se e i ica sólo bajo las hipó esis del siguien e eo ema. Teo ema 2.3.2 Sea X un polied o con exo en Rn. Sean i(x),∀i= 1, . . . , k las unciones obje i o. Sea x∗solución e icien e. En onces exis en alo es λi>0,∀i= 1, . . . , k pa a los cuales x∗es solución óp ima de P(λ). ■Ejemplo 2.3 Se e oma el Ejemplo 2.1, suponiendo que el deciso de e mina el ec o de pesos λ= (λ1, λ2) = (1,2), es o es, da el doble de impo ancia al segundo obje i o espec o del p ime o. El p oblema uniobje i o P(λ) queda como sigue: max p(x) = λ1 1(x) + λ2 2(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 Resol iéndolo po el Mé odo Simplex, se ob iene la solución óp ima x∗= x∗ 1 x∗ 2!= 8/3 16/3!, que coincide con el pun o ex emo x3ob enido median e el algo i mo del Simplex en el Ejemplo 2.2. Además, po el Teo ema 2.3.1, queda asegu ada su e iciencia pues el ec o de pesos es es ic amen e posi i o. En la Figu a 2.6 puede e se g á icamen e que el pun o x∗pe enece al conjun o e i- cien e. Figu a 2.6: Solución e icien e. Mé odo de las ponde aciones ■ 2.3.2. Gene ación del conjun o e icien e El mé odo de las ponde aciones puede usa se pa a la gene ación del conjun o e icien e de la siguien e mane a. Se comienza usualmen e conside ando los pesos λ= (1,0,...,0),(0,1,...,0),...,(0,0,...,1). De es a o ma ob end emos kp oblemas de op imización unidimensionales, uno pa a cada unción obje i o. Seguidamen e se hacen a ia los alo es de λcon enien emen e. De es a mane a se an gene ando pun os ex emos del conjun o ac ible X. No es demasiado adecuado hace uso del mé odo de las ponde aciones pa a ob ene el conjun o e icien e, pues en muchos casos se ob iene solo una ap oximación de es e. Su gen incon enien es, po ejemplo, en el momen o en que conjun os de pesos dis in os gene an el mismo pun o, o es e es ob enido a pa i de algún peso nulo, pues el Teo ema 2.3.1 dice que no puede asegu a se su e iciencia. También puede da se el caso en que no se consigan gene a odos los pun os ex emos y po an o se conside en como e icien es los pun os del segmen o que une dos pun os no adyacen es. 26 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.3. MÉTODO DE LAS PONDERACIONES ■Ejemplo 2.4 Se conside a aho a el p oblema gené ico P(λ): max p(x) = λ1·(−x1+x2) + λ2·(x1+ 2x2) s.a. x∈X x≥0 Si se hace a ia sis emá icamen e el ec o de pesos λ= (λ1, λ2)y se esuel en aquellos p oblemas unidimensionales que se an gene ando se consigue, al menos, una ap oxima- ción del conjun o e icien e. Con iene oma alo es de λes ic amen e posi i os pa a ga an iza la e iciencia de las soluciones ob enidas. (λ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 esul ados se puede in ui que el conjun o e icien e lo o man los pun os del segmen o que une A y B, ambos inclusi e. ■ 2.3.3. Exis encia de soluciones óp imas al e na i as Se p esen a una es a egia pa a e alua la e iciencia de las soluciones óp imas al e na- i as, en el caso de que se hayan ob enido a pa i de algún peso igual a ce o. Se suponen nulos, sin pé dida de gene alidad, odos los alo es λia pa i de un cie o p, es o es, λi(>0,si i= 1, . . . , p = 0,si i=p+ 1, . . . , k Resol iéndose el p oblema de op imización unidimensional (2.2) con la ponde ación escogida, se ob iene una solución al e na i a x∗= (x∗ 1, . . . , x∗ n)que e i ica i(x∗ 1, . . . , x∗ n) = z∗ i,i= 1, . . . , p. Tal solución al e na i a se ha ob enido a pa i de cie os pesos nulos luego debe com- p oba se su e iciencia. Pa a ello, se esuel e el siguien e p oblema de ponde aciones, de- no ado P0(λ), pa a un subconjun o de X. max p0(x) = p X i=1 λi i(x) s.a. x∈X i(x1, . . . , xn) = z∗ i, i = 1, . . . , p CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 27 2.4. MÉTODO DE LAS ε-RESTRICCIONES Teo ema 2.3.3 En las condiciones an e io es, si x∗= (x∗ 1, . . . , x∗ n)es solución óp ima de P0(λ), en onces es e icien e. ■Ejemplo 2.5 Se supone aho a que el deciso da un ec o de pesos λ= (2,0), en el que una de las componen es es nula. Resuel o po el mé odo Simplex el p oblema del Ejemplo 2.4 pa a ales alo es, se ob iene la solución óp ima x∗= 0 4!, que e i ica 1(x∗)=4. En es e caso sabemos, po lo is o en los ejemplos an e io es, que se a a de un pun o e icien e. De o ma gene al, es necesa io comp oba la e iciencia de la solución esol iendo el p oblema de ponde aciones P0(λ): max p0(x)=2·(−x1+x2)+0·(x1+ 2x2) = −2x1+ 2x2 s.a. x∈X 1(x) = −x1+x2= 4 Como cabe espe a , x∗es solución óp ima luego es e icien e. ■ 2.4. Mé odo de las ε- es icciones Se conside a la siguien e no ación pa a un p oblema lineal con k unciones obje i o: max (x) = ( 1(x), . . . , k(x)) s.a. x∈X 2.4.1. Desc ipción del mé odo Pa a aplica es e mé odo, se equie e que una de las unciones obje i o enga más ele ancia pa a el deciso que el es o. Supongamos (x) al obje i o. Se plan ea el siguien e p oblema, deno ado P (ε), en el que se busca op imiza el obje i o de mayo impo ancia y que añade una es icción en o ma de co a in e io pa a cada uno de los demás: max (x) s.a. x∈X i(x)≥εi, i = 1,..., −1, + 1, . . . , k donde εi,i= 1, . . . , −1, + 1, . . . , k son núme os eales que quedan a elección del deciso . De es a mane a uel e a ob ene se di ec amen e la solución de mejo comp omiso. En el caso en que P (ε)no enga solución, hab á de eajus a se el p oblema elajando al menos una de las co as in e io es impues as. El siguien e eo ema da una condición su icien e pa a que la solución óp ima sea e i- cien e. Teo ema 2.4.1 Si la solución óp ima x∗de P (ε)es única, en onces x∗es e icien e. 28 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.4. MÉTODO DE LAS ε-RESTRICCIONES ■Ejemplo 2.6 Pa a esol e el p oblema conside ado has a aho a po el mé odo de las ε− es icciones se supond á que el obje i o más impo an e pa a el omado de decisiones es el 2a la ez que se impone ε1= 5/2como co a in e io pa a el obje i o 2. Po lo is o p e iamen e, se debe plan ea y esol e el p oblema P2(ε): max 2(x) = x1+ 2x2 s.a. x∈X 1(x) = −x1+x2≥5/2 De nue o, haciendo uso del Simplex, se ob iene el óp imo x∗= 8/3 16/3!que, po se único, es e icien e (Teo ema 2.4.1). Es e pun o es, de hecho, el pun o B is o en el Ejemplo 2.1. ■ 2.4.2. Exis encia de soluciones óp imas al e na i as En el caso de que exis an soluciones óp imas al e na i as de P (ε)no puede asegu a se nada ace ca de la e iciencia de és as. Se p esen a una es a egia pa a comp oba la e iciencia de una solución al e na i a ob enida x∗= (x∗ 1, . . . , x∗ n). Se supone, sin pé dida de gene alidad, que los obje i os 1, . . . , pson aquellos que e i ican las es icciones como igualdades en la solución óp ima, es deci , i(x∗) = εi,∀i= 1, . . . , p, incluido el obje i o escogido como el más impo an e (obje i o ). Se esuel e el siguien e p oblema unidimensional, deno ado P0(ε), que es análogo al p esen ado en el mé odo de las ponde aciones, donde los obje i os 1, . . . , ppasan a se es icciones: max (x) s.a. x∈X i(x1, . . . , xn) = εi, i = 1, . . . , p Si x∗= (x∗ 1, . . . , x∗ n)es solución óp ima de P0(ε), en onces queda comp obada su e i- ciencia. Si se escogen adecuadamen e an o la unción obje i o a op imiza como las co as in e io es εi(i= ), el siguien e eo ema asegu a que oda solución e icien e es solución del p oblema P (ε). Teo ema 2.4.2 Sea x∗solución e icien e. En onces pa a odo alo de exis en co as in e io es εi(i= )de mane a que x∗sea solución óp ima de P (ε). 2.4.3. Gene ación de soluciones e icien es El siguien e algo i mo conduce a soluciones e icien es. PASO 1. Toma = 1. Fija co as in e io es εi, i = 1, . . . , k, a bi a iamen e. PASO 2. Ob ene la solución óp ima x de P (ε). CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 29 2.4. MÉTODO DE LAS ε-RESTRICCIONES PASO 3. Si =k, en onces se pa a el algo i mo. Si < k, en onces si ε < (x ); cambia ε po (x ). Hace = + 1 e i al PASO 2. ■Ejemplo 2.7 Un ejemplo de cómo aplica el algo imo is o es el siguien e. PASO 1. = 1. ε= (ε1, ε2) = (3,11) PASO 2. x1= 3/2 19/4!solución óp ima única de P1(ε): max 1(x) = −x1+x2 s.a. x∈X 2(x) = x1+ 2x2≥11 PASO 3. = 1 <2 = kyε1= 3 <13/4 = 1(x1)luego cambia ε1po 1(x1). ε= (ε1, ε2) = (13/4,11) = + 1 = 1 + 1 = 2 PASO 2. x2= 3/2 19/4!solución óp ima única de P2(ε): max 2(x) = x1+ 2x2 s.a. x∈X 1(x) = −x1+x2≥13/4 PASO 3. =2=kluego se pa a el algo i mo. El algo i mo ha conducido en dos i e aciones a la misma solución x1=x2, que como se obse a en la Figu a 2.7, pe enece al conjun o e icien e ya conocido. 30 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 2.5. PROGRAMACIÓN POR METAS Figu a 2.7: Solución e icien e. Mé odo de las ε− es icciones ■ 2.5. P og amación po me as En es e mé odo, el omado de decisiones ija un p opósi o a alcanza en cada uno de los obje i os, de mane a que se oma como solución óp ima aquella que queda “lo más ce ca posible” al mismo iempo de odas las me as p e ijadas. 2.5.1. Desc ipción del mé odo Se conside a el siguien e p oblema de p og amación uniobje i o, deno ado (P)M, donde ˜mies el ni el de aspi ación que el deciso iene pa a el obje i o i: min d= k X i=1 | i(x)−˜mi| s.a. x∈X Se p e ende, po an o, minimiza la suma de las di e encias en e los alo es obje i o y sus me as, en alo absolu o. Hay que ene en cuen a que la unción obje i o del p oblema (P)Mes de ca ác e no lineal. Al e na i amen e, puede ans o ma se en un p oblema lineal haciendo uso de las siguien es a iables: d+ i=1 2(| i(x)−˜mi|+ ( i(x)−˜mi) d− i=1 2(| i(x)−˜mi| − ( i(x)−˜mi) que ep esen an las amas posi i a (po exceso) y nega i a (po de ec o) de las di e en- cias en e cada alo obje i o y su me a p opues a. De es a mane a, queda el siguien e p oblema equi alen e, deno ado (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 i(x)−d+ i+d− i= ˜mi d+ i, d− i≥0,∀i= 1, . . . , k (2.3) La es icción i(x)−d+ i+d− i= ˜mise conoce como es icción de me a. Aho a sí que puede aplica se el mé odo del Simplex pa a ob ene una solución óp ima de (P′)Mque, en gene al, no se á e icien e pa a el (MOLP) o iginal, po lo que hab á de comp oba se. ■Ejemplo 2.8 Po úl imo, se esuel e de nue o el Ejemplo 2.1, es a ez haciendo uso de la p og amación po me as. Se supone que el deciso ija las me as ˜m1= 3,˜m2= 15 pa a los obje i os 1y 2, espec i amen e. El p oblema (P)Mpa a es os da os conc e os queda min d=| − x1+x2−3|+|x1+ 2x2−15| s.a. x∈X y haciendo uso de las a iables auxilia es 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 ans o ma 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) Bas a ía, po an o, esol e es e p oblema de P og amación Lineal con un solo obje i o pa a ob ene la solución de mejo comp omiso. Es o queda pendien e pa a más adelan e. ■ Es e mé odo se á de u ilidad pa a esol e cualquie p oblema de P og amación Lineal Mul iobje i o median e So wa e y se e á en el p óximo Capí ulo. 32 CAPÍTULO 2. MÉTODOS DE RESOLUCIÓN 3.2. R se sVAR := 1..n a ; se sRES := 1..m es; se sOBJ := 1..nobj; pa am mc {sOBJ, sVAR}; pa am mA {sRES, sVAR}; pa am b {sRES}; pa am Me as {sOBJ}; a dmas {sOBJ} >= 0; a dmenos {sOBJ} >= 0; a x {sVAR} >= 0; minimize Obj_d: sum {k in sOBJ} (dmas[k] + dmenos[k]); s. . es _A {i in sRES}: sum {j in sVAR} mA[i,j] * x[j] <= b[i]; s. . es _me as {k in sOBJ}: ( sum {j in sVAR} mc[k,j] * x[j] ) + ( - dmas[k] + dmenos[k] ) = Me as[k]; " Análogamen e pa a los da os que ue on de inidos en el iche o .da . da a =" pa am n a := 2; pa am m es:= 3; pa am nobj:= 2; pa am mc : 1 2 := 1 -1 1 2 1 2; pa am mA : 1 2 := 1 -1 2 2 1 1 3 1 0; pa am b:= 1 8 2 8 3 6; pa am Me as:= 1 3 2 15; CAPÍTULO 3. RESOLUCIÓN CON SOFTWARE 39 3.2. R " O a opción es gua da en una a iable cada uno de los iche os di ec amen e. ic_ampl_modelo ="me as01.mod" ic_ampl_da a ="me as01.da " w i eLines(modelo, ic_ampl_modelo) w i eLines(da a, ic_ampl_da a) Po úl imo, se o dena la esolución median e los siguien es comandos: Se llama a la lib e ía lib a y( AMPL) y se di ecciona la ubicación de ins alación. Debe se la misma donde se ins aló AMPL. di ins all_ampl ="/home/ s udio/ampl.linux-in el64/" Median e el comando new se c ea el obje o, ampl =new(AMPL, new(En i onmen , di ins all_ampl)) se in e p e an las a iables que con ienen a los iche os, ampl$ ese () ampl$ ead( ic_ampl_modelo) ampl$ eadDa a( ic_ampl_da a) se especi ica el sol e que se quie e u iliza , ampl$se Op ion("sol e ","cplex") y se o dena esol e . ampl$e al("op ion cplex_op ions 'sensi i i y';") ampl$sol e() ## CPLEX 20.1.0.0: sensi i i y ## CPLEX 20.1.0.0: op imal solu ion; objec i e 2 ## 3 dual simplex i e a ions (0 in phase I) ## ## su ix up OUT; ## su ix down OUT; ## su ix cu en OUT; Se puede pedi ambién que imp ima po pan alla la solución óp ima ob enida ampl$e al("display x,dmas,dmenos;") ## : x dmas dmenos := ## 1 2.66667 0 0.333333 ## 2 5.33333 0 1.66667 ## ; y el enunciado del p oblema esuel o. 40 CAPÍTULO 3. RESOLUCIÓN CON SOFTWARE 3.2. R ampl$e al("expand;") ## minimize Obj_d: ## dmas[1] + dmas[2] + dmenos[1] + dmenos[2]; ## ## subjec o es _A[1]: ## -x[1] + 2*x[2] <= 8; ## ## subjec o es _A[2]: ## x[1] + x[2] <= 8; ## ## subjec o es _A[3]: ## x[1] <= 6; ## ## subjec o es _me as[1]: ## -dmas[1] + dmenos[1] - x[1] + x[2] = 3; ## ## subjec o es _me as[2]: ## -dmas[2] + dmenos[2] + x[1] + 2*x[2] = 15; Véase en la Figu a 3.5 cómo se ob ienen los mismos esul ados haciendo uso de la lib e ía AMPL. Figu a 3.5: Pan alla Rs udio. Uso de AMPL ■ Pa a el desa ollo de es a sección y la comp ensión de es a lib e ía se ha consul ado la in o mación disponible en [ AM, b]. Cabe menciona que pa a el uso de AMPL es necesa io ene ins alado p e iamen e el paque e “Rcpp”. CAPÍTULO 3. RESOLUCIÓN CON SOFTWARE 41 3.2. R 3.2.3. Paque e MOIP Exis e un paque e en R, llamado “gMOIP”, capaz de abaja g á icamen e (2D y 3D) con p oblemas lineales, ya sean con inuos, en e os o mix os, y pe mi e hace ep esen- aciones del espacio de decisiones y del espacio de obje i os de p oblemas bic i e io. Se p esen a a con inuación su uncionamien o ecu iendo de nue o al Ejemplo 2.1. ■Ejemplo 3.4 Rep esen ación del conjun o ac ible Se ca ga la lib e ía lib a y(gMOIP) Se de inen los elemen os del p oblema lineal biobje i o con 2 a iables #Ma iz de es icciones A<- ma ix(c(-1,2, 1,1, 1,0), ncol = 2,by ow = TRUE) #Vec o lado de echo b<- c(8,8,6) #Ma iz de obje i os obj <- ma ix(c(-1,1,#p ime obje i o 1,2), #segundo obje i o n ow = 2) Se de ine una nue a unción pa a ep esen a lo plo BiObj2D <- unc ion(A, b, obj, ype = ep("c", ncol(A)), #Va iables con inuas c i = "max",#C i e io de op imización aces = ep("c", ncol(A)), plo Faces = TRUE, plo Feasible = TRUE, plo Op imum = FALSE, labels = "numb", addT iangles = TRUE, addHull = TRUE) { p1 <- plo Poly ope(A, b, ype = ype, c i = c i , aces = aces, plo Faces = plo Faces, plo Feasible = plo Feasible, plo Op imum = plo Op imum, labels = labels) + ggplo 2::gg i le("Espacio de decisiones") p2 <- plo C i e ion2D(A, b, obj, ype = ype, c i = c i , addT iangles = addT iangles, addHull = addHull, plo Feasible = plo Feasible, labels = labels) + ggplo 2::gg i le("Espacio de obje i os") g idEx a::g id.a ange(p1, p2, n ow = 1) } 42 CAPÍTULO 3. RESOLUCIÓN CON SOFTWARE 3.2. R Se ep esen a el conjun o ac ible del p oblema biobje i o haciendo uso de la unción p e iamen e de inida plo BiObj2D(A, b, obj, addT iangles = 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 obje i os Se obse a que la unción dibuja an o la egión ac ible del espacio de decisiones como la egión ac ible del espacio de obje i os. La ep esen ación en dos dimensiones del espacio de obje i os pe mi e iden i ica ácil- men e los é ices e icien es y desca a los que no lo son. Así, en las g á icas ob enidas pa a es e ejemplo, se ap ecia que los pun os 1 y 3 en el espacio de obje i os son los obje- i os asociados a las soluciones e icien es 1 y 3 (B y A espec i amen e en la Figu a 2.2) del espacio de decisiones. Es o concue da con el hecho de que, si se pasa de 1 a 3 en el espacio de obje i os, mien as que el p ime obje i o, conside ado en el eje X, aumen a (mejo a) su alo , el segundo obje i o, conside ado en el eje Y, disminuye (empeo a) su alo . Luego ambos son pun os no dominados, y sus espec i as soluciones en el espacio de decisiones, e icien es. Sin emba go, si se pasa de 5 a 3, o de 4 a 2, se e que ambos obje i os aumen an (mejo an). Po an o 3 domina a 5 y 2 domina a 4, po lo que ni 5 ni 4 se án soluciones e icien es. Gene ación de los pun os ex emos del conjun o ac ible O a g an u ilidad a des aca del paque e gMOIP es la posibilidad de gene a los pun os ex emos del conjun o ac ible haciendo uso de la o den co ne Poin s. co ne Poin s(A, b, ype = 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 ec o ype = c(“c”, “c”) indica que se ienen dos a iables con inuas. ■ Se ha consul ado la documen ación disponible en [Nielsen, 2021] y [ MO] e e en e al uso del paque e MOIP. 3.3. Conclusiones El p esen e abajo ha a ado de in oduci al lec o , de una o ma g adual, en el ám- bi o de la Op imización Mul iobje i o; empezando po una p ime a pa e eminen emen e eó ica, en la que se con igu a la es uc u a y sin axis del modelo gene al; seguido de una pa e cen al, en la que se exponen algunas de las dis in as o mas de abo da los p oblemas plan eados en la pa e p eceden e. Además, odo es o acompañado de ejemplos pa a a o ece la comp ensión. Median e el plan eamien o de algunas si uaciones eales que hacen uso de ella, se ha p e endido ilus a la ans e salidad que iene la P og amación Mul iobje i o en cual- quie disciplina humana. Como bien es sabido, a día de hoy, la P og amación Ma emá ica no se en iende sin el sopo e de un So wa e que acili e el manejo de g andes olúmenes de da os. Es po ello que, a modo de cie e de es e abajo, se han que ido p esen a algunas de las di e sas he amien as de p og amación median e So wa e disponibles, AMPL y R, pa a ejempli ica , de una mane a angible, lo que puede se su uso a g andes escalas. El con enido de es e abajo ab e las pue as al es udio de o as a ian es de p oble- mas Mul iobje i o, como pueden se los de ca ác e no lineal, o aquellos que in oluc an a iables en e as o mix as. 44 CAPÍTULO 3. RESOLUCIÓN CON SOFTWARE Apéndice A Apéndice: Comp obación de la e iciencia de una solución A modo de Apéndice se ha que ido implemen a con So wa e el p oblema (2.1) pa a comp oba si una solución es e icien e o no pa a un p oblema Mul iobje i o, is o en el Mé odo Simplex. Se ecue da su es uc u a max E= k X i=1 hi s.a. x∈X i(x)−hi= i(¯x), i = 1, . . . , k hi≥0, i = 1, . . . , k donde hison las a iables de holgu a conside adas. Como ya se io, si E= 0, en onces la solución básica ac ible ¯xes e icien e pa a el p oblema mul iobje i o, y si E > 0, en onces no es posible asegu a la e iciencia de ¯x. Se p ocede con la de inición de la unción pa a unos da os con dimensiones y alo es gené icos. En el desa ollo de es a, se ecu e al paque e “lpSol e” is o en la sección 3.2.1. unc_Comp oba _e iciencia_PLMul = unc ion(mc, mA, b, des, _p o_c_E i){ num_obj =n ow(mc) #Núme o obje i os num_ ilas_o ig =n ow(mA) #Núme o es icciones c i e io ="max" #C i e io de op imización mDmenos =- diag(num_obj) mA_amp_01 =cbind(mA,diag(0,n ow = num_ ilas_o ig, ncol = num_obj)) mA_amp_02 =cbind(mc, mDmenos) mA_amp = bind(mA_amp_01, mA_amp_02) #Nue a ma iz es icciones des_amp =c( des, ep("=",num_obj)) #Nue o ec o desigualdades _obj_x =as.nume ic(mc %* % _p o_c_E i) 45 b_amp =c( b, _obj_x) #Nue o ec o lado de echo c_amp =c( ep(0,ncol(mc)), ep(1,num_obj)) #Nue o ec o obje i os #Resolución del p oblema uniobje i o median e el paque e lpSol e lib a y(lpSol e) solucion =lp(di ec ion = c i e io, objec i e.in = c_amp, cons .ma = mA_amp, cons .di = des_amp, cons . hs = b_amp) i (solucion$obj al == 0) { mensaje ="AVISO: SÍ es una solución E icien e!!"}#E = 0 else { mensaje ="AVISO: NO es una solución E icien e!!"}#E > 0 p in (mensaje) } ■Ejemplo A.1 Aho a se conc e a án los da os pa a el Ejemplo que se ha usado a lo la go de odo el abajo. En p ime luga , se de inen los elemen os del p oblema mul iobje i o o iginal. mA =ma ix(c(-1,2,#Ma iz de es icciones 1,1, 1,0), n ow = 3,by ow = T) b =c(8,8,6)#Vec o lado de echo des =c("<=","<=","<=")#Vec o de desigualdades mc =ma ix(c(-1,1,#Ma iz de obje i os 1,2), n ow = 2,by ow = T) Tal y como se io, es e pa de pun os gene ados po el mé odo del Simplex son e icien es, pues son óp imos pa a cada uno de los obje i os po sepa ado. Es o se comp obó en el Ejemplo 2.2 iendo que la ila de cos es educidos asociada al obje i o en conc e o enía odas sus en adas no nega i as. #Coincide con el pun o x_2 y maximiza el obje i o _1. p o_e i_01 =c(0,4) #Coincide con el pun o x_3 y maximiza el obje i o _2. p o_e i_02 =c(8/3,16/3) Haciendo uso de la unción p e iamen e de inida, se e que ambos son e icien es. unc_Comp oba _e iciencia_PLMul (mc, mA, b, des, _p o_c_E i = p o_e i_01) 46 APÉNDICE A. APÉNDICE: COMPROBACIÓN DE LA EFICIENCIA DE UNA SOLUCIÓN ## [1] "AVISO: SÍ es una solución E icien e!!" unc_Comp oba _e iciencia_PLMul (mc, mA, b, des, _p o_c_E i = p o_e i_02) ## [1] "AVISO: SÍ es una solución E icien e!!" A con inuación se puede e que, e ec i amen e, los pun os de la ca a del polied o que une los pun os an e io es son e icien es. Se comp ueba dando alo es al pa áme o al a. al a =0.6 #0.2, 0.3, 0.4, 0.5, 0.9, 1 unc_Comp oba _e iciencia_PLMul (mc, mA, b, des, _p o_c_E i = al a * p o_e i_01 + (1-al a)*p o_e i_02) ## [1] "AVISO: SÍ es una solución E icien e!!" Sin emba go, las ilas de cos es educidos pa a el siguien e pun o no enían odas sus en adas es ic amen e posi i as luego es necesa io comp oba su e iciencia. p o_01 =c(0,0)#Coincide con el pun o x_1 Como puede e se, el pun o no es e icien e pa a el p oblema mul iobje i o. unc_Comp oba _e iciencia_PLMul (mc, mA, b, des, _p o_c_E i = p o_01) ## [1] "AVISO: NO es una solución E icien e!!" De igual modo puede comp oba se la e iciencia de los é ices es an es del conjun o ac ible. p o_02 =c(6,0) p o_03 =c(6,2) En es e caso, ampoco se a a de soluciones e icien es. unc_Comp oba _e iciencia_PLMul (mc, mA, b, des, _p o_c_E i = p o_02) ## [1] "AVISO: NO es una solución E icien e!!" unc_Comp oba _e iciencia_PLMul (mc, mA, b, des, _p o_c_E i = p o_03) ## [1] "AVISO: NO es una solución E icien e!!" ■ APÉNDICE A. APÉNDICE: COMPROBACIÓN DE LA EFICIENCIA DE UNA SOLUCIÓN 47