Soluciones utilitarias de compromiso en problemas multi-objetivo con información parcial

Rect@ Vol 10 Diciembre 2009. Pp 179 - 195 Recibido 30/10/2009 Revisado 23/11/2009 Aceptado 4/12/2009 Soluciones utilitarias de compromiso en problemas multi-objetivo con información parcial Hinojosa, M. A. (*) Mármol A. M. (**) (*)Universidad Pablo de Olavide. Sevilla (**)Universidad de Sevilla. RESUMEN En este trabajo se analizan problemas de optimización multi-objetivo en situaciones en que las preferencias del agente decisor pueden representarse por funciones aditivas y solo se dispone de información parcial sobre los pesos de importancia de los objetivos. Este análisis puede interpretarse también en términos de decisión en grupo, cuando distintos agentes proporcionan pesos distintos para los objetivos, y a partir de ahí hay que llegar a un consenso sobre la solución a elegir. En este contexto de información parcial se introduce una clase de soluciones que pueden considerarse un compromiso entre las soluciones del tipo maximin y las soluciones utilitarias. También se analizan algunas de sus principales propiedades Palabras claves: Problemas multi-objetivo, pesos de importancia, información parcial, conceptos de solución. ABSTRACT We analyze multiple objective optimization problems in situations in which the preferences of the decision maker can be represented by additive functions and only partial information about the importance of the objectives is available. This analysis can also be interpreted in terms of group decision-making when different agents provide different weights for the objectives, and a consensus about the solution to choose has to be reached. In this context of partial information we introduce a class of solutions that can be considered as a compromise between the solutions based on a maxmin criterion and the utilitarian solutions. We also analyze some of their main properties. Keywords: Multi-objective problems, importance weights, partial information, solution concepts Hinojosa M.A., M´armol, A.M. 1.- Introducci´on Con objeto de motivar el an´alisis del problema multi-objetivo y las soluciones que se presentan a continuaci´on, comenzamos este trabajo con un ejemplo ilustrativo. Ejemplo 1: Un modelo de producci´on con incertidumbre sobre los precios. Consideremos una empresa que fabrica dos productos, Z1yZ2, de acuerdo a una tecnolog´ıa que le permite producir en un conjunto de producci´on posible (CPP) como el representado en la Figura 1. Figura 1: CPP en un ejemplo con dos productos. Z1 Z2 CPP Supondremos que el CPP es compacto (las producciones est´an acotadas y adem´as las combinaciones de productos en la frontera del CPP son producibles en la tecnolog´ıa considerada), comprehensivo (si la combinaci´on de productos z=(z1,z 2) se puede producir, tambi´en se puede producir cualquier combinaci´on z=(z 1,z 2), con z 1≤z1yz 2≤z2)yconvexo (cualquier combinaci´on convexa de dos posibles puntos en el CPP pertenece tambi´en al CPP). Estos supuestos son habituales en distintos modelos de negociaci´on y de producci´on existentes en la literatura. El problema que se plantea es elegir, de entre las alternativas en el CPP, la producci´on que maximice una determinada funci´on de utilidad que est´a basada en los precios. Si se conocieran los m´aximos precios, λ1yλ2, que el mercado es capaz de absorber para los productos Z1yZ2respectivamente, la producci´on ´optima estar´ıa autom´aticamente determinada al maximizar la funci´on de utilidad f(z)=λ1z1+λ2z2. Esta soluci´on es conocida en la literatura como la soluci´on utilitaria. La denotamos por Suy la representamos en la Figura 2. Figura 2: Soluci´on utilitaria. Z1 Z2 CPP Su=z∗=(z∗ 1,z∗ 2) λ=(λ 1 ,λ 2 ) λ1z1+λ2z2=K Rect@181 Vol.10 (2009) Soluciones utilitarias de compromiso ... Normalmente es dif´ıcil predecir los precios que el mercado absorber´a, pero, en muchos casos s´ı se puede asumir cierta informaci´on imprecisa sobre dichos precios. En este ejemplo supondremos que se sabe que el producto Z1es m´as caro o a lo sumo tiene el mismo precio que el producto Z2y que, por otro lado, el precio del producto Z1alom´as duplica el precio del producto Z2.1 En este trabajo, con la informaci´on imprecisa facilitada, definiremos una nueva soluci´on que llamaremos soluci´on utilitaria de compromiso (SUC) y denoretamos por Suc. Est´a basada en un principio conservador seg´un el cual, se asigna a cada combinaci´on de productos factible la peor de las valoraciones posibles, teniendo en cuenta todos los precios admisibles incluidos en el conjunto de informaci´on, y se elige entonces, la producci´on que maximiza estas peores valoraciones.2 Gr´aficamente, la SUC en este ejemplo, considerando la informaci´on mencionada, se representa en la Figura 3. Figura 3: CPP con informaci´on imprecisa sobre los precios. Z1 Z2 CPP Suc =z∗=(z∗ 1,z∗ 2) El nombre de soluci´on utilitaria de compromiso se justifica porque puede ser considerada un compromiso entre la soluci´on utilitaria, Su, de la Figura 2 y la soluci´on maximin basada en un principio igualitario (Rawls, 1971), que aconseja producir la misma cantidad de cada producto. Si los precios que el mercado es capaz de absorber son conocidos, la SUC coincide con la soluci´on utilitaria; en cambio, si no hay ninguna informaci´on sobre dichos precios hay que considerar como poliedro de informaci´on todo el simplex y la SUC coincide con la soluci´on maximin, que denotamos por Sm. En la Figura 4 se representan, para el ejemplo considerado, las tres soluciones: La soluci´on maximin, la SUC y la soluci´on utilitaria. 1Si los precios los suponemos normalizados para pertenecer al simplex ∆1={λ=(λ1,λ 2)|λ1≥ 0,λ 2≥0,λ 1+λ2=1}, la informaci´on imprecisa disponible en este caso puede representarse mediante el poliedro Λ = {λ∈∆1|λ1≥λ2,λ 1≤2λ2}, que llamaremos poliedro de informaci´on. Los puntos extremos de este poliedro de informaci´on son λ1=(1/2,1/2) y λ2=(2/3,1/3). 2Un punto z=(z1,z 2) del CPP es preferido a otro z=(z 1,z 2), con respecto al poliedro de informaci´on Λ, si minλ∈Λλ1z1+λ2z2≥minλ∈Λλ1z 1+λ2z 2. Esto es equivalente a imponer la desigualdad para los puntos extremos de Λ, es decir, 1/2z1+1/2z2≥1/2z 1+1/2z 2y2/3z1+1/3z2≥ 2/3z 1+1/3z 2. Rect@182 Vol.10 (2009) Hinojosa M.A., M´armol, A.M. Figura 4: SUC, soluci´on utilitaria y soluci´on maximin. Z1 Z2 CPP Suc Sm Su Obs´ervese que a medida que se incorpora informaci´on sobre los precios la SUC se adapta mejor a la tecnolog´ıa de cada problema, es decir, toma en consideraci´on la forma que tiene el CPP. En los dos ejemplos que se representan en la Figura 5, la soluci´on maximin no tiene en cuenta la capacidad que tiene la empresa de producir de un producto m´as que del otro. Sin embargo, con la informaci´on sobre los precios facilitada, la SUC tiene en cuenta que en estos problemas es posible una peque˜na disminuci´on en la fabricaci´on de un producto a cambio de un incremento mayor en la producci´on del otro. Figura 5: SUC en dos CPP correspondientes a tecnolog´ıas diferentes. Z1 Z2 CPP Suc CPP Z2 Z1 Suc En este Ejemplo 1, con el que hemos decidido comenzar la redacci´on del trabajo, estamos ignorando el an´alisis econ´omico del problema, centr´andonos en en problema matem´atico de maximizaci´on de ambas producciones (objetivos) dentro de un conjunto factible y utilizando los precios como pesos de importancia de los dos objetivos considerados que se agregan en una funci´on de utilidad lineal a trozos. Este es el marco en el que se desarrolla el trabajo: problemas de decisi´on multiobjetivo en situaciones en las que las preferencias del agente decisor pueden representarse por funciones aditivas, y donde se permite imprecisi´on en los pesos de los objetivos; m´as concretamente, se dispone de informaci´on parcial sobre los pesos de los objetivos que se formaliza por medio de restricciones lineales. El an´alisis que se presenta en este trabajo puede interpretarse tambi´en en t´erminos de decisi´on en grupo, cuando un grupo de agentes decisores tiene que resolver un Rect@183 Vol.10 (2009) Soluciones utilitarias de compromiso ... problema multi-objetivo y cada uno de ellos proporciona un vector de pesos diferente, la falta de consenso en estas situaciones puede interpretarse como informaci´on parcial sobre la importancia de los objetivos. Los trabajos previos sobre el tratamiento de problemas multi-objetivo con informaci´on parcial tratan principalmente de la reducci´on del conjunto de soluciones Pareto-´optimas, de acuerdo con la informaci´on disponible (v´ease, por ejemplo, Weber (1987), Carrizosa et al. (1995), M´armol et al. (2002)). Hay tambi´en bastante literatura sobre problemas lineales multi-objetivo en los que los coeficientes de la funci´on objetivo no est´an perfectamente determinados, sino que vienen dados por intervalos o por medio de relaciones lineales ( por ejemplo, M´armol y Puerto (1997), Hansen y otros (1989) y Wendell (1985, 2004)). La mayor´ıa de estos trabajos se centran en analizar la sensibilidad de una soluci´on dada ante cambios factibles en los par´ametros. En un sentido diferente Hinojosa y M´armol (2009) investigan las soluciones que surgen para problemas de decisi´on multi-objetivo con informaci´on parcial cuando las preferencias del agente decisor se representan por funciones utilitarias o igualitarias y estudian los principios de racionalidad que los sustentan. En el presente trabajo se supone que las preferencias del agente decisor pueden representarse mediante una funci´on aditiva y desde un punto de vista conservador, se proponen la soluciones utilitarias de compromiso (SUC) para problemas multiobjetivo con informaci´on parcial. En nuestro modelo, la informaci´on parcial se representa mediante un conjunto de informaci´on poli´edrico formado por los pesos de los objetivos que se pueden considerar en la funci´on utilitaria. Presentamos tambi´en la caracterizaci´on de la SUC para problemas lineales multiobjetivo mediante la resoluci´on de un problema escalar lineal. El resto del trabajo se estructura como sigue: En la Secci´on 2 se formaliza el modelo lineal continuo de optimizaci´on multi-objectivo y se definen formalmente las soluciones SUC. En la Secci´on 3 se estudian algunas propiedades que cumple dicha soluci´on. Finalizamos el trabajo con unos comentarios a modo de conclusiones. 2.- Soluciones utilitarias de compromiso en problemas multi-objetivo con informacion parcial Consideremos un problema de optimizaci´on con sobjetivos que reflejan los prop´ositos diferentes del agente decisor. Este problema lo representamos en su forma general como sigue: max z =f(x)=[f1(x),... ,f r(x),... ,f s(x)] s.t :x∈Ω donde Ω es el conjunto factible en el espacio de decisi´on, Ω ⊆IR n, que consideramos compacto, comprehensivo y convexo, y fes una funci´on, f:IR n→IR s, donde fr, r=1,2,... ,s, son funciones objetivo continuamente diferenciables. Asumimos, sin p´erdida de generalidad, que todos los objetivos son de maximizaci´on. Si consideramos problemas lineales multi-objetivo, entonces fr,r=1,2,... ,s, son funciones lineales de xyΩyf(Ω) = {z∈IR s|z=f(x),x∈Ω}son conjuntos poli´edricos. Rect@184 Vol.10 (2009) Hinojosa M.A., M´armol, A.M. Un problema multi-objetivo (PMO) lo denotamos por un par (Ω,f). Un punto x∈Ω se denomina una soluci´on factible del problema. Se trata de seleccionar un subconjunto de soluciones factibles (preferiblemente una ´unica) que sea considerada deseable por el agente decisor o por el grupo de agentes decisores. El requisito de Pareto-optimalidad es b´asico para las soluciones en los problemas multi-objetivo. Una soluci´on factible es Pareto-´optima si los valores de los objetivos no pueden mejorarse componente a componente.3 Definici´on 2.1. Una soluci´on factible x∗∈Ω es Pareto-´optima o eficiente si no existe otra, x∈Ω, tal que fr(x)>f r(x∗) para todo r=1,... ,s. Una soluci´on factible x∗∈Ω es fuertemente Pareto-´optima o fuertemente eficiente si no existe ninguna otra soluci´on factible , x∈Ω, tal que fr(x)≥fr(x∗) para todo r=1,... ,s, con al menos una desigualdad estricta. Para cada PMO (Ω,f), el conjunto de soluciones Pareto-´optimas (fuertemente Pareto-´optimas) lo denotamos por PO(Ω,f)(FPO(Ω,f)). En la literatura hay distintos procedimientos para generar soluciones eficientes (ver, por ejemplo, Chankong y Haimes(1983) y Yano y Sakawa(1989)). La escalarizaci´on mediante una suma ponderada es uno de los mas extendidos. No obstante, en la pr´actica, el conjunto de soluciones eficientes de un PMO suele contener demasidas alternativas para permitir al agente decisor realizar la elecci´on de la m´as preferida. En nuestro contexto, asumiremos inicialmente que las preferencias del agente decisor (o agentes decisores) se pueden representar por una funci´on aditiva4,λ·f(x)=s r=1 λrfr(x), y por lo tanto, es posible seleccionar soluciones eficientes maximizando una funci´on lineal de las funciones objetivo. En este caso, los par´ametros, λr, se pueden interpretar como pesos de importancia de los objetivos y el conjunto completo de soluciones Pareto-optimas puede generarse considerando todos los pesos en el IRs-simplex ∆s−1=λ∈IR s +|s r=1 λr=1 . Cuando se puede determinar un ´unico vector de pesos, λ∈∆s−1,elPMO es un problema con informaci´on completa y se representa por la terna (Ω,f,λ). Resolviendo el problema ponderado correspondiente se obtiene un subconjunto de puntos eficientes (en muchos casos un ´unico punto). La soluci´on obtenida, que se define formalmente a continuaci´on, se denomina soluci´on utilitaria. Definici´on 2.2. La soluci´on utilitaria, Su, selecciona para cada problema (Ω,f,λ) el conjunto Su(Ω,f,λ) = arg max x∈Ωλ·f(x). Ejemplo 2: Consideremos dos problemas bi-objetivo con informaci´on completa, (Ω,f,λ 1)y(Ω,f,λ 2). En el primero, el primer objetivo se considera el doble de importante que el segundo, es decir, λ1=(2/3,1/3)t, y en el segundo se da la misma importacia a ambos objetivos, es decir, λ2=(1/2,1/2)t. Entonces 3Usaremos el t´ermino Pareto-´optimo y tambi´en el t´ermino eficiente para referirnos a las soluciones en el espacio de decisi´on, Ω. Cuando no haya lugar a confusi´on, usaremos tambi´en el t´ermino eficiente para referirnos a los correspondientes valores en el espacio de objetivos. 4Dados z1,z 2∈IR s, denotamos por z1·z2al producto escalar de z1yz2, es decir, z1·z2= s r=1 z1 rz2 r. Rect@185 Vol.10 (2009) Soluciones utilitarias de compromiso ... Su(Ω,f,λ 1) = arg max x∈Ω{(2/3)f1(x)+(1/3)f2(x)}, Su(Ω,f,λ 2) = arg max x∈Ω{(1/2)f1(x)+(1/2)f2(x)}. En la Figura 6 se representan las soluciones a dichos problemas en el espacio de objetivos. 2f1(x)+f2(x)=K f1(x) f(Ω) Su(Ω,f,(2/3,1/3)) Su(Ω,f,(1/2,1/2)) f1+f2=T Figura 6: Soluci´on utiltaria. f2(x) Sin embargo, el problema de la determinaci´on de los pesos dista bastante de ser trivial. De ahora en adelante vamos a considerar situaciones en las que la importancia de los objetivos no esta establecida de manera precisa, pero el agente decisor es capaz de proporcionar un conjunto de informaci´on en el que deben estar los pesos de los objetivos. Sea Λ un poliedro de pesos que representa la informaci´on disponible sobre la importancia de los objetivos, Λ ⊆∆s−1.Unproblema multi-objetivo con informaci´on parcial es una terna (Ω,f,Λ). En este tipo de problemas con informaci´on parcial, vamos a extender la noci´on de soluci´on utilitaria definiendo una soluci´on de compromiso, que est´a basada en la siguiente relaci´on de dominancia en el espacio de objetivos. Definici´on 2.3. Dados z1,z2∈IR s,z1domina a z2con respecto a la relaci´on de dominancia Λ,z1Λz2,simin λ∈Λλ·z1>minλ∈Λλ·z2. Definici´on 2.4. El punto z∗∈f(Ω) es no dominado respecto a Λsi no existe otro, z∈f(Ω), que lo domine con respecto a dicha relaci´on. Definici´on 2.5. La soluci´on utilitaria de compromiso, Suc, selecciona para cada problema (Ω,f,Λ) los puntos factibles correspondientes a las soluciones no dominadas respecto de Λ, es decir, Suc(Ω,f,Λ) = arg max x∈ΩmΛ(x), donde mΛ(x) = minλ∈Λλ·f(x). Sean λ1,λ 2, ... ,λ k,los puntos extremos del poliedro Λ. En el siguiente resultado se prueba que la relaci´on de dominancia Λpuede establecerse en funci´on de los puntos extremos del poliedro Λ. Proposici´on 2.6. z1Λz2si, y solo si, minh=1,... ,k{λh·z1}>minh=1,... ,k{λh·z2}. Rect@186 Vol.10 (2009) Hinojosa M.A., M´armol, A.M. Demostraci´on: Vamos a probar que minh=1,... ,k{λh·z}= minλ∈Λλ·z. En primer lugar, es f´acil ver que minh=1,... ,k{λh·z}≥minλ∈Λλ·z. Sea ahora λ∗∈Λ, tal que λ∗·z= minλ∈Λλ·z. Se cumple λ∗=k i=1 αiλi, con 0 ≤αi≤1y k i=1 αi= 1. Por tanto, λ∗·z=k  i=1 αiλi·z= k  i=1 αiλi·z≥ k  i=1 αimin h=1,... ,k{λh·z}= min h=1,... ,k{λh·z}. De donde se sigue la igualdad. ✷ Como consecuencia, se obtiene una representaci´on alternativa de la funci´on mΛ, como mΛ(x) = min{λ1·f(x),λ 2·f(x),... ,λ k·f(x)}. Como se coment´o en el Ejemplo 1, en el caso de m´axima informaci´on sobre los pesos de importancia de los objetivos, cuando el conjunto de informaci´on consiste en un ´unico vector de pesos, la SUC coincide con la soluci´on utilitaria. En el caso en que no hay ninguna informaci´on sobre dichos pesos de importancia, el conjunto de informaci´on consiste en todos los pesos posibles en el simplex s-dimensional, ya que la ausencia de informaci´on no permite descartar ninguno. En este caso la SUC coincide con la soluci´on maxim´ın del problema multiobjetivo. En este sentido la SUC se considera un compromiso entre la soluci´on utilitaria y la noci´on igualitaria que subyace en la soluci´on maximin. Obs´ervese que dicho compromiso pueder forzarse para que sea un compromiso entre la soluci´on maximin ponderada por el vector py la soluci´on utilitaria. Este vector prepresenta la direcci´on que dirige la soluci´on maximin ponderada con la que coincide la SUC en ausencia de informaci´on. Puede considerarse como una ponderaci´on a priori que determina el rayo en el que confluyen las curvas de nivel lineales a trozos que dirigen la SUC. Dado un vector de componentes estrictamente positivas, p, que llamaremos de ponderaci´on a priori, el concepto de soluci´on utilitaria de compromiso puede generalizarse de la siguiente forma: Definici´on 2.7. La soluci´on utilitaria de compromiso con ponderaci´on a priori p, que denotamos por Sp uc(Ω,f,Λ), es para cada problema (Ω,f,Λ) Sp uc(Ω,f,Λ) = arg max x∈Ωmp Λ(x), donde mp Λ(x) = min λ1·f(x) λ1·p,λ2·f(x) λ2·p,... ,λk·f(x) λk·p. Ejemplo 1 (Continuaci´on): Supongase que en el modelo de producci´on con incertudumbre sobre los precios del Ejemplo 1, el agente decisor quiere que la producci´on se mantenga en el ratio que se viene haciendo en campa˜nas anteriores, dos unidades del producto 1 por cada unidad producida del producto 2, a no ser que la informaci´on imprecisa sobre los precios de mercado aconseje otra cosa. Por tanto, la ratio p=(2,1) se considera una ponderaci´on a priori, que debe respetarse en ausencia de informaci´on. En la Figura 7 se observa c´omo con el mismo conjunto de informaci´on propuesto en el Ejemplo 1, que representa los posibles precios que el mercado puede absorber, la utilizaci´on de la SUC no aconseja modificar, en este ejemplo, el ratio de producci´on p=(2,1). Rect@187 Vol.10 (2009) Soluciones utilitarias de compromiso ... factibles poli´edricos y funciones objetivo lineales, la SUC se obtiene simplemente mediante la resoluci´on de un problema lineal uni-objetivo. En particular, la utilizaci´on de estas soluciones apuntan ventajas en los modelos de An´alisis Envolvente de Datos (DEA) de cara a establecer puntos de referencia mas realistas que tengan en cuenta las preferencias parcialmente especificadas por un decisor o por los miembros de un grupo de decisores. Entre los inconvenientes de la SUC, vamos a destacar que esta soluci´on, al igual que el resto de las soluciones basadas en nociones utilitarias, no cumple una propiedad deseable en determinadas situaciones, la Monoton´ıa. Esta propiedad requiere que si se ampl´ıa el conjunto factible en un PMO, en la soluci´on del problema con regi´on factible mayor deber´ıan poderse encontrar soluciones factibles con todos los objetivos mejores o iguales. La Figura 8 ilustra el hecho de que la SUC no satisface la propiedad de monoton´ıa. Obs´ervese que cuando el conjunto factible se ampl´ıa, el segundo objetivo alcanza valores mas bajos en todos los puntos que proporciona la SUC. Sp uc(Ω,f,Λ) Figura 14: Sp uc no es mon´otona f1(x) Sp uc(Ω,f,Λ) p f(Ω) f2(x) Agradecimientos: Esta investigaci´on ha sido parcialmente financiada por el proyecto SEJ2007-62711 del Ministerio de Ciencia y Tecnolog´ıa y por el proyecto de la Consejer´ıa de Innovaci´on de la Junta de Andaluc´ıa P06-SEJ-01801. 5.- Referencias •Carrizosa E., Conde E., Fern´andez F.R., Puerto J.(1995). Multi-criteria analysis with partial information about the weighting coefficients. European Journal of Operational Research Vol. 81, n.22, pp. 291-301. •Chankong V., Haimes Y.Y. (1983). Multiobjective decision making: Theory and Methodology. North Holland. •Hansen P., Labbe M., Wendell R.E. (1989). Sensitivity analysis in multiple objective linear programming. The tolerance approach. European Journal of Operational Research. Vol. 38, n.1, pp. 63-69. Rect@194 Vol.10 (2009) Hinojosa M.A., M´armol, A.M. •Hinojosa M.A., M´armol A.M. (2009). Egalitarianism and utilitarianism in multiple criteria decision problems with partial information. En prensa en Group Decision and Negotiation. •M´armol A.M., Puerto J.(1997). Special cases of the tolerance approach in multiobjective linear programming. European Journal of Operational Research. Vol. 98, n. 3, pp. 610-616. •M´armol A.M., Puerto J., Fern´andez F.R.(2002). Sequential Incorporation of Imprecise Information in Multiple Criteria Decision Processes. European Journal of Operational Research. Vol. 137, pp. 123-133. •Nash, J. (1950). The bargaining problem. Econometrica. Vol. 18, 155-162. •Rawls, J. (1971). A Theory of Justice. Cambridge, Mass.: Harvard University Press. •Weber M. (1987). Decision Making with Incomplete Information, European Journal of Operational Research 28, 44–57. •Wendell R.E. (1985). The tolerance approach to sensitivity analysis in linear programming. Management Science. Vol. 31, n. 5, pp. 564-578. •Wendell R.E. (2004). Tolerance sensitivity and optimality bounds in linear programming. Management Science. Vol.50, n.6, pp. 797-803. •Yano H., Sakawa M. (1989). A unified approach for characterifing Pareto Optimal solutions of multiobjective optimifation problems: the hyperplane method. European Journal of Operational Research 39, 61-70. Rect@195 Vol.10 (2009)