Planteamiento del Problema

En la toma de decisiones, a menudo nos encontramos con situaciones donde debemos optimizar múltiples objetivos simultáneamente. Estos objetivos pueden ser conflictivos entre sí, lo que dificulta la búsqueda de una solución única que sea óptima para todos ellos. La Programación Multiobjetivo (PMO) proporciona herramientas y técnicas para abordar este tipo de problemas.

A continuación, se presentan algunas de las principales técnicas y enfoques utilizados en la PMO:

• Técnicas Generadoras: Buscan generar un conjunto de soluciones eficientes o no dominadas, entre las cuales el decisor puede elegir la que mejor se adapte a sus preferencias.
  • Método de las Ponderaciones
  • Método de las Restricciones
• Programación Compromiso: Trata de encontrar soluciones de compromiso que se encuentren lo más cerca posible de un punto ideal, representando la mejor combinación posible de los objetivos.
• Programación por Metas: Busca soluciones satisfactorias que cumplan con los niveles de aspiración establecidos por el decisor para cada objetivo.

Técnicas Generadoras

Método de las Ponderaciones

Este método consiste en asignar un peso o ponderación a cada objetivo y luego agregarlos en una única función objetivo. La optimización de esta función ponderada genera un punto eficiente para cada conjunto de pesos.

Teorema

X* ∈ K es eficiente si, y solo si, existe un vector λ ∈ R^p, con λ_i > 0 ∀i y Σλ_i = 1, tal que X* es óptimo para f(λ).

Método de las Ponderaciones (Zadeh 1963)

Se construye un problema mono-objetivo mediante la escalarización de la función vectorial objetivo. Se define una función objetivo escalar como suma ponderada de las funciones objetivo de partida, asignando a cada f_i un peso o ponderación λ_i.

Dado Max(f₁(X),…, f_p(X)) X∈K -> Max Σ λ_i f_i (X), X ∈ K, Σ λ_i = 1, λ_i ≥ 0

Método de las Ponderaciones (II)

Funciones de los pesos:

• De cálculo: para cada vector de pesos se obtiene un punto extremo del conjunto eficiente, lo que permite generar, o al menos, aproximar, el conjunto eficiente.
• Información sobre la importancia relativa asignada a cada objetivo f_i.
• Eliminación de las unidades de medida (normalización).

Método de las Ponderaciones (III)

Para este método se verifica que:

• Los pesos elegidos no guardan relación con las preferencias del decisor.
• Para cada vector de pesos λ se obtiene, al menos, un punto extremo eficiente.
• Variando los pesos (recorrer el espacio de ponderaciones) se puede generar el conjunto eficiente, aunque no siempre se obtiene su representación completa (aproximación).
• Si los pesos son no negativos las soluciones son eficientes.

Método de las Ponderaciones (III)

Inconvenientes:

• Combinaciones distintas de pesos pueden llevar a un mismo punto extremo.
• Si alguno de los pesos es cero y existen óptimos alternativos, la solución generada puede no ser eficiente. Aunque esta situación es factible teóricamente, es poco habitual en la práctica.
• Necesitamos resolver el problema monocriterio propuesto qp-1 veces, siendo p el número de objetivos y q el número de vectores λ que queramos proponer.

Método de las Ponderaciones (III)

Sólo genera puntos extremos eficientes (vértices del conjunto eficiente), ya que detecta como punto eficiente el punto de tangencia de la poligonal que define el conjunto eficiente con la familia de rectas en el caso de dos objetivos, o de hiperplanos en el caso de p objetivos, definida como función objetivo:

2 objetivos: λ f₁ (X) + (1 – λ) f₂ (X)

p objetivos: Σ λ_i f_i (X)

Método de las Ponderaciones (IV)

Dado un problema con dos objetivos (bicriterio):

Max λ₁f₁(X)+λ₂f₂(X) -> Max (1-λ₂)f₁(X)+λ₂f₂(X)

s.a X∈K                                       s.a X∈K

λ₁+ λ₂ = 1                                  0 ≤ λ₂ ≤ 1

λ₁, λ₂ ≥ 0

La asignación del valor de las ponderaciones es la clave de esta técnica.

Método de las Ponderaciones (V)

¿Cómo recorrer los posibles vectores λ?

En el caso de la Programación Multiobjetivo Lineal Bicriterio, el Método de las Ponderaciones es la Programación Lineal Paramétrica.

Hay que calcular los valores de λ que proporcionen un cambio de base, es decir, un cambio de vértice en el conjunto de oportunidades.

Método de las Restricciones

Este método optimiza uno de los objetivos mientras que el resto se incorpora al conjunto de restricciones como restricciones paramétricas. Para cada conjunto de valores del vector de términos independientes (ε), se genera un punto eficiente (frontera o interior).

Supongamos el siguiente problema multiobjetivo: Opt (f₁(X),…, f_p(X)), s.a. X∈K

Según este método, se optimiza uno de los objetivos y el resto se incorporan al modelo en forma de restricciones paramétricas:

Opt f_k(X), s.a. X∈K, f_j(X) ≥ ε_j ∀j              j = 1,…,k-1,k+1,…., p        

(ε) -> Si alguno de los objetivos debe minimizarse          

La variación paramétrica de los términos independientes (ε_j) se hará en función de los valores ideales y anti-ideales para cada objetivo:

Valor anti-ideal del objetivo j ≤ ε_j ≤ valor ideal objetivo j

Método de las Restricciones (Marglin 1967)

La solución de este problema, para distintos valores de ε_j, genera puntos, tanto extremos como interiores, del conjunto eficiente sólo cuando las restricciones paramétricas son activas en la determinación del óptimo. Es decir: f_j(X*) = ε_j ∀ j ≠ k

Si en el óptimo alguna de las restricciones es no activa (se verifica en desigualdad) y existen óptimos alternativos, la solución puede no ser eficiente. Aunque esta situación es factible teóricamente, en la práctica es poco usual.

Requiere solucionar el problema qp-1 veces, siendo p el nº de objetivos y q el nº de valores que demos al vector de términos independientes.

Simplex Multicriterio

Es el único método multiobjetivo que genera todos los puntos extremos eficientes.

Se basa en el algoritmo del Simplex desplazándose de un punto extremo al punto extremo adyacente, proporcionando una representación exacta del conjunto eficiente.

Su principal inconveniente es la enorme complejidad de los cálculos para su implementación.

El software disponible es útil sólo para problemas de tamaño moderado:

• ADBASE: 50 variables, 50 restricciones y un máximo de 3 objetos.
• MLP: 50 variables, 50 restricciones y un máximo de 8 objetos, si bien en la práctica para problemas de tamaño mucho más reducido.

Notas

• La generación de todo el conjunto eficiente requiere una adecuada variación paramétrica, para la que existen algunos algoritmos.
• En problemas lineales existen algoritmos que permiten determinar todo el conjunto eficiente.
• En problemas reales el conjunto eficiente suele ser muy extenso por lo que es importante reducir su dimensión para que el decisor pueda elegir.
• Programas informáticos.

Programación Compromiso

Técnicas Compromiso (Yu y Zeleny 1973)

• Tratan de determinar, dentro del conjunto eficiente, las soluciones que mejor se adaptan a las preferencias del decisor.
• Para ello se utiliza el punto ideal y el Axioma de Zeleny: “Dadas dos soluciones posibles, la preferida será la que se encuentre más próxima al punto ideal”.
• Las soluciones más cercanas al punto ideal se llaman soluciones compromiso y al conjunto de todas las soluciones compromiso se le llama conjunto compromiso.
• El concepto fundamental de esta técnica es el de distancia que se utiliza como indicador de las preferencias del decisor.

Distancia. Definición

Sea K un conjunto. Se llama distancia o métrica en K a toda aplicación: d: KxK → R tal que para todo X,Y,Z∈K se cumple:

1. d(X,Y) > 0 si X ≠ Y
2. d(X,X) = 0
3. d(X,Y) = d(Y,X)
4. d(X,Y) ≤ d(X,Z) + d(Z,Y)

Distancia Generalizada en un Espacio n-dimensional

Dados los puntos X=(x₁,x₂,…,x_n) e Y=(y₁,y₂,…,y_n), se define la familia de métricas o distancias L_p (1≤p<∞) como L_p(X,Y)= (Σ|x_i –y_i|^p)^1/p

Para cada valor de p obtendremos distintas métricas o distancias.

Distancia Generalizada en un Espacio n-dimensional. Casos Particulares

• p=1. Distancia de Manhatan. Es la distancia más larga L₁(X,Y)=Σ|x_i –y_i|
• p=2. Distancia Euclídea. L₂(X,Y)=√Σ|x_i –y_i|²
• A partir de p=3 las distancias ya no tienen significado. Generalmente el punto ideal es geométrico, pero sí lo pueden tener como indicador de las preferencias del decisor.
• p=∞. Distancia de Tchebycheff. L_∞(X,Y)= Max |x_i –y_i|

Determinación de Soluciones Compromiso

Generalmente el punto ideal es inalcanzable, debido al conflicto que existe entre los objetivos. Por este motivo, vamos a determinar los puntos más próximos al ideal que, según el axioma de Zeleny, son los preferidos por el decisor.

Distancia al Punto Ideal

• Para cada objetivo f_i se define el grado de proximidad h a su ideal f_i* como: h_i = |f_i*-f_i|
• Puesto que los objetivos están dados en unidades distintas, para poder agregar los grados de proximidad de todos los objetivos es preciso normalizarlos: d_i = |f_i*-f_i(X)| / |f_i*-f_i|
• Si el objetivo i alcanza su valor ideal -> d=0
• Si el objetivo i alcanza su valor anti-ideal -> d=1

Nota: Si existen dos objetivos -> 0≤d_i≤1, Si hay más de dos objetivos no necesariamente se verifica que 0≤d_i≤1. El decisor asigna a cada d_i una ponderación w_i como expresión de la preferencia que asocia a la discrepancia entre la realización del objetivo i-ésimo y su ideal.

Determinación de Soluciones Compromiso

Las soluciones compromiso o soluciones más próximas al ideal son las soluciones del problema:

Min L_p (Σ w_i(|f_i*-f_i(X)| / |f_i*-f_i|)^p)^1/p, 1≤p≤∞, sa X ∈ K

Límites del Conjunto Compromiso. Teorema de Yu

Yu demostró (1973) que para problemas con dos objetivos el conjunto compromiso está acotado por L₁ y L_∞.

Freimer y Yu demostraron (1976) que para problemas con más de dos objetivos los puntos L₁ y L_∞ no tienen que definir necesariamente al conjunto compromiso. Pueden existir soluciones fuera del intervalo [L₁ y L_∞], aunque en la práctica este resultado es poco probable.

Programación por Metas

Tiene su origen en los trabajos de Charnes y Cooper en 1961. Recoge el concepto de satisfacción de objetivos introducido por Simon en 1955 (Premio Nóbel de Economía 1978). La desarrollan Ijiri, Lee e Ignizio, entre otros. En principio se utilizó para resolver problemas industriales, extendiéndose posteriormente a otros campos como economía, agricultura, etc. Es uno de los enfoques multicriterio más utilizados actualmente, sobre todo en problemas complejos de gran tamaño.

El decisor actúa primero, incorporando información explícita al proceso mediante el establecimiento de preferencias y prioridades.

La programación por metas trata de proporcionar alguna combinación que satisfaga unos niveles de aspiración para los distintos objetivos fijados por el decisor: soluciones satisfactorias.

Si lo anterior no es posible, se procura obtener la solución que más se ajuste a las preferencias expresadas: “soluciones más cercanas” al conjunto satisfactorio.

Modelo de Programación por Metas. Conceptos Básicos

El decisor:

• Establece los objetivos que trata de optimizar (máximo o mínimo).
• Asigna a cada objetivo un nivel de aspiración u_i (nivel de logro del atributo que el decisor considera aceptable, cantidad que se desea alcanzar como mínimo o bien, cantidad que no se desea superar).

Formulación de las metas (expresión matemática de los niveles de aspiración de cada objetivo):

• Si el objetivo es maximizar, φ_i(X) ≥ u_i
• Si el objetivo es minimizar, φ_j(X) ≤ u_j
• Si se desea el valor exacto de un objetivo, φ_k(X) = u_k

X* es solución satisfactoria si, siendo admisible (eficiente o no), es la más próxima a los niveles de aspiración fijados por el decisor.

Las metas no son funciones matemáticas que se puedan optimizar. Para ello se transforman en igualdades introduciendo variables de desviación negativas (n) y positivas (p) -> φ(X) + n – p = u

Así, cada meta se transforma en una restricción blanda a incorporar en el modelo.

Valores:

• Son siempre positivas o cero.
• Al menos una de las dos tiene que ser cero (el nivel de aspiración no puede ser sobrepasado y a la vez quedar incompleto). Ambas toman valor cero cuando la meta alcance exactamente su nivel de aspiración u.

Una variable desviación se dice que es no deseada cuando al decisor le interesa su valor más pequeño (cero). Si el objetivo es maximizar (meta φ_i(X) ≥ u_i), la variable desviación no deseada es la negativa n_i. Si el objetivo es minimizar (meta φ_j(X) ≤ u_j), la variable desviación no deseada es la positiva p_j. Si se alcanza exactamente el nivel de aspiración (φ_k(X) = u_k), las dos variables desviación son no deseadas. Las variables desviación no deseadas se incorporan siempre en la función objetivo del problema de programación por metas.

Programación por Metas. Formulación del Problema General

Dado el problema Opt (φ₁(X),…, φ_p(X)) s.a. X∈K donde:

• f_i(X) son objetivos a maximizar con niveles de aspiración u_i
• f_j(X) son objetivos a minimizar con niveles de aspiración u_j
• f_k(X) son objetivos para los que se trata de alcanzar el valor exacto del nivel de aspiración u_k

El problema de programación por metas se formula:

Min(n_i, p_j, n_k+p_k) s.a. X∈K

φ_i(X) + n_i – p_i = u_i

φ_j(X) + n_j – p_j = u_j

φ_k(X) + n_k – p_k = u_k

n_i, p_i, n_j, p_j, n_k, p_k ≥ 0

Existen dos tipos de restricciones:

• Restricciones duras: son las restricciones técnicas del problema original. No pueden ser violadas en ningún caso.
• Restricciones blandas o metas: pueden ser violadas. Los niveles de aspiración no se consideran valores rígidos que no se pueden sobrepasar, sino umbrales que el decisor pretende satisfacer en la medida de lo posible y en caso de no ser alcanzables, quedarse cerca de su consecución.

Distintos procedimientos de minimización de las variables de desviación no deseadas dan lugar a distintos enfoques de la programación por metas. Enfoques y no métodos de resolución ya que cada uno de ellos representa una estructura de preferencias del decisor distinta. Si no existen soluciones satisfactorias, la solución depende del enfoque elegido. Entre dichos enfoques: metas ponderadas y metas lexicográficas.

Metas Ponderadas:

Intuitivamente: Min (n_i+p_j+n_k+p_k)

Inconvenientes:

• Heterogeneidad de las unidades de medida de cada objetivo.
• Igual importancia de todas las metas.

Normalización: Una forma de hacerlo es dividiendo cada variable desviación no deseada por su nivel de aspiración.

Preferencias del decisor: Si el decisor otorga distinta importancia a la normalización de cada meta y pondera éstas a través de w_i, w_j:

Min Σ w_i (n_i / u_i) + Σ w_j (p_j / u_j) + Σ (n_k + p_k) / u_k

s.a. X∈K

φ_i(X) + n_i – p_i = u_i,

φ_j(X) + n_j – p_j = u_j,

φ_k(X) + n_k – p_k = u_k,

n_i, p_i, n_j, p_j, n_k, p_k ≥ 0

Estructura de preferencias del decisor:

• Si los valores de los niveles de aspiración son los valores ideales de cada objetivo, la programación por metas ponderadas equivale a la búsqueda de la eficiencia.
• El objetivo del decisor es minimizar la magnitud global de las desviaciones, sin importarle si alguno de los objetivos de las desviaciones son demasiado grandes o si existen muchas diferencias en el logro de las distintas metas.

Metas Lexicográficas

El decisor asigna niveles de prioridad a la consecución de las metas. Las preferencias del decisor se ordenan lexicográficamente (se satisfacen las metas situadas en el 1º nivel, y sólo una vez satisfechas, se intentan satisfacer las del 2º nivel). El objetivo es minimizar lexicográficamente las variables de desviación no deseadas: Lex Min(n_i, p_j, n_k+p_k)

El orden lexicográfico implica la resolución de tantos problemas de programación matemática como niveles de prioridad haya establecido el decisor, además de un nivel inicial donde se detecta si existen o no puntos factibles en el problema.

Nivel 0: determinar si existen puntos admisibles en el conjunto de oportunidades.

Nivel 1: minimizar las variables de desviación no deseadas del 1er nivel de prioridad.

Min n_i s.a. X∈K φ_i(X) + n_i – p_i = u_i n_i, p_i ≥ 0

Si n_i = 0, la solución X* satisface la primera meta y se pasa al siguiente nivel. Si n_i > 0, la meta no se ha satisfecho. Fin del problema. El método para en la solución X* obtenida, que será la más cercana al cumplimiento de la meta.

Nivel 2: minimizar las variables de desviación no deseadas del 2º nivel de prioridad.

Min p_j s.a. X∈K φ_i(X) + n_i – p_i = u_i n_i = 0, φ_j(X) + n_j – p_j = u_j n_i, p_i, n_j, p_j ≥ 0

donde manteniendo la meta del 1er nivel de prioridad, se quiere satisfacer le meta del 2º. Para conseguir el cumplimiento de la meta del 1er nivel, se introducen dos restricciones de igualdad que lo garantizan.

Al resolver el problema planteado en este 2º nivel de prioridad puede ocurrir:

• Si la solución es p_s = 0 -> la solución satisface la meta del 2º nivel y se pasa al siguiente nivel de prioridad.
• Si p_j > 0 -> la meta no se ha satisfecho. Fin del problema. El método para en la solución X* obtenida, que satisface la 1ª meta y es la más cercana al cumplimiento de la 2ª meta.

Nivel 3: minimizar las variables de desviación no deseadas del 3er nivel de prioridad.

Min (n_k + p_k) s.a. X∈K φ_i(X) + n_i – p_i = u_i n_i = 0 φ_j(X) + n_j – p_j = u_j p_j = 0 φ_k(X) + n_k – p_k = u_k n_i, p_i, n_j, p_j, n_k, p_k ≥ 0

donde manteniendo las metas del 1er y 2º nivel de prioridad, se quiere satisfacer la meta del 3º. Por eso se exige que n_i y p_j sean cero.

Al resolver el problema planteado en este 3er nivel de prioridad puede ocurrir:

• Si la solución es n_k = p_k = 0 -> la solución satisface la meta del 3er nivel y todas las metas establecidas por el decisor.
• Si n_k ó p_k > 0 -> la meta no se ha satisfecho. Fin del problema. El método para en la solución X* obtenida, que satisface la 1ª y la 2ª meta y es la más cercana al cumplimiento de la 3ª meta.

Comentarios:

Si la solución es n_k = p_k = 0 -> Se han conseguido anular todas las variables de desviación no deseadas -> Es una solución satisfactoria. Si no es eficiente se trata de conseguir la eficiencia. Si n_k ó p_k > 0 -> la solución final no es satisfactoria, pero es la que más se acerca a las preferencias del decisor.

En cualquiera de los enfoques, si no se encuentra una solución satisfactoria, el decisor puede:

• Relajar la meta lo suficiente para que se pueda cumplir y seguir el proceso.
• En el enfoque lexicográfico, cambiar el orden de los niveles de prioridad.
• Analizar si existen metas redundantes.
• En el enfoque lexicográfico, excesiva priorización de las metas.
• Fijación de niveles de aspiración demasiado optimistas, cercanos a los valores ideales de los objetivos. Inclusión de metas de ambos lados que restringen el espacio satisfactorio.

Enfoque Lexicográfico. Estructura de Preferencias del Decisor

Es un enfoque adecuado para problemas en los que no sea conveniente la compensación entre objetivos.

Soluciones Satisfactorias y Eficientes

Llamando X** a la solución del problema anterior:

• Si X** = X* -> X* es solución eficiente, ya que no se ha podido mejorar ningún objetivo sin modificar la satisfacción de las metas. Si X** ≠ X* -> X* no es eficiente ya que la nueva solución la domina. X** sí es eficiente.
• Proporcionar soluciones eficientes a partir de soluciones satisfactorias dominadas. Se puede aplicar alguna técnica generadora (por ejemplo, el método de las ponderaciones) a las funciones objetivo del problema sujeto al conjunto satisfactorio (restricciones duras y blandas).