PROGRAMACIÓN
MULTIOBJETIVO
PROGRAMACIÓN MULTIOBJETIVO
• La programación multiobjetivo es el enfoque más utilizado para tratar problemas de decisión
con criterios múltiples. Las técnicas de programación múltiples forman parte de un campo que
se entiende rápidamente, por lo que existen nuevas metodologías que tienen una importancia
directa tanto con la construcción de modelos de planificación como análisis de decisiones.
• El Problema de Optimización Multiobjetivo (POM) (llamado también multicriterio o vectorial)
puede definirse como el problema de encontrar: “un vector de variables de decisión que
satisfagan un cierto conjunto de restricciones y optimice un conjunto de funciones objetivo. Estas
funciones forman una descripción matemática de los criterios de desempeño que suelen estar en
conflicto unos con otros y que se suelen medir en unidades diferentes”. El término “optimizar” en
este caso toma pues un significado diferente al del caso de problemas mono-objetivo.
El Problema de Optimización Multiobjetivo (POM) general se define
formalmente de la manera siguiente:
Encontrar el vector
→ 𝑥Ԧ ∗ = 𝑥1∗ , 𝑥2∗ , … , 𝑥𝑛∗
Que satisfaga
Las 𝑚 restricciones de desigualdad:
𝑔𝑖 𝑥Ԧ ≤ 0 𝑖 = 1,2, … , 𝑚
Las 𝑝 restricciones de igualdad:
ℎ𝑖 𝑥Ԧ ≤ 0 𝑖 = 1,2, … , 𝑝
Y optimice la función vectorial:
𝑓Ԧ 𝑥Ԧ = 𝑓1 𝑥Ԧ , 𝑓2 𝑥Ԧ , … , 𝑓𝑘 𝑥Ԧ 𝑇
Para poder determinar qué tan “buena” es una cierta solución, es
necesario contar con algún criterio para evaluarla. Estos criterios se
expresan como funciones computables de las variables de decisión a
las que se denomina funciones objetivo. En problemas del mundo
real, algunas de estas funciones objetivo suelen estar en conflicto
entre sí, y algunas deben minimizarse mientras otras han de
maximizarse. Las funciones objetivo pueden ser conmensurables
(medidas en las mismas unidades) o no conmensurables (medidas en
unidades distintas).
Un conjunto (o región) de puntos se define como un conjunto
convexo en un espacio n-dimensional si, para todos los pares de
puntos y en el conjunto, el segmento rectilíneo que los une está
también enteramente dentro del conjunto.
Un conjunto (o región) de puntos se define como un conjunto
convexo en un espacio n-dimensional si, para todos los pares de
puntos y en el conjunto, el segmento rectilíneo que los une está
también enteramente dentro del conjunto.
De tal forma, todo punto 𝑥Ԧ𝑖 , donde
𝑥Ԧ = 𝜃𝑥Ԧ1 + 1 − 𝜃 𝑥Ԧ2 , 0≤𝜃≤1
Este también en el conjunto.
VECTOR OBJETIVO IDEAL:
Vector de variables de decisión correspondiente a los
óptimos (factibles) considerando a cada una de las funciones
objetivo del problema como aisladas. Nótese que el vector
ideal es inalcanzable, excepto en el caso en que no existe
ningún conflicto entre las funciones objetivo del problema.
TIPOS DE PROBLEMAS
MULTIOBJETIVO
Existen tres tipos de situaciones que pueden presentarse en un problema
multiobjetivo:
• Minimizar todas las funciones objetivo
• Maximizar todas las funciones objetivo
• Minimizar algunas funciones y maximizar otras.
Por cuestiones de simplicidad, normalmente todas las funciones se convierten ya
sea a un problema de maximización o a uno de minimización. Se puede usar la
siguiente identidad para convertir todas las funciones a maximizarse de manera
que correspondan a un problema de minimización:
𝑚𝑎𝑥𝑓𝑖 𝑥Ԧ = min(−𝑓𝑖 (𝑥)) Ԧ
OPTIMALIDAD DE PARETO
En un problema de optimización de una sola variable, la atención se centra en encontrar el espacio de
la variable de decisión. Por su parte en un problema multiobjetivo el interés se centra en el espacio
objetivo. Por otra parte tener claro que en este tipo de problemas no es posible encontrar una simple
solución que permita optimizar todas las funciones objetivos simultáneamente. Algunos de los
vectores óptimos se pueden extraer por simple inspección.
Dichos vectores son aquellos en donde ninguno de sus componentes puede causar deterioro al resto
de los otros componentes Una definición mucho más formal de la Optimalidad de Pareto se
puede expresar como: Se dice que un vector de variables de decisión
𝑥 ϵ Ω Ω 𝑒𝑠 𝑙𝑎 𝑧𝑜𝑛𝑎 𝑓𝑎𝑐𝑡𝑖𝑏𝑙𝑒 es un óptimo de Pareto si no existe otro 𝑥Ԧ ϵ Ω (𝑡𝑎𝑙 𝑞𝑢𝑒 𝑓𝑖 (𝑥) Ԧ ≤
OPTIMALIDAD DE PARETO
Ԧ
Para un problema multiobjetivo dado 𝑓(𝑥), el conjunto de óptimos de Pareto (𝑃∗ ) se define
como:
𝑃∗ ∶= 𝑥 𝜖 Ω උ∄ 𝑥 ′ 𝜖 Ω 𝑓Ԧ 𝑥 ′ ≤ 𝑓Ԧ 𝑥
La gráfica de las funciones objetivo cuyos vectores no dominados se encuentran en el
conjunto de óptimos de Pareto se denominan frente de Pareto.
Para un problema multiobjetivo dado 𝑓Ԧ 𝑥 , el conjunto de óptimos de Pareto (𝑃∗ ), el frente
de Pareto(𝑃𝐹 ∗ ), se define como:
𝑃𝐹 ∗ ∶= 𝑢 = 𝑓Ԧ = 𝑓1 𝑥 , … , 𝑓𝑘 𝑥 ห𝑥 𝜖 𝑃∗
En general, no es fácil encontrar una expresión analítica de la línea o superficie que
representa los valores de los vectores no dominados en el espacio de las funciones objetivo
y, en la mayor parte de los casos, resulta simplemente imposible obtenerla. El procedimiento
normal para generar el frente de Pareto es calcular todos los puntos factibles Ω y obtener
sus valores correspondientes 𝑓(Ω). Cuando se cuenta con un número suficiente de estos
puntos, es posible determinar los no dominados de entre ellos.
CLASIFICACIÓN DE LAS TÉCNICAS DE
PROGRAMACIÓN MATEMÁTICA
• Ha habido varios intentos por clasificar las diversas técnicas de programación matemática que
existen para resolver problemas multiobjetivo. De primera instancia, resulta fundamental distinguir
las dos etapas en las que puede dividirse la solución de un problema multiobjetivo: la optimización
de las diversas funciones objetivo involucradas y el proceso de decidir qué tipos de “compromisos”
son más convenientes desde la perspectiva del tomador de decisiones (a este segundo proceso se
le denomina “Toma de Decisiones multicriterio”. Es muy común adoptar la propuesta de Cohon &
Marks (1975) porque dichos autores enfocan su clasificación hacia la forma en la que cada técnica
maneja los dos sub-problemas principales de la optimización multiobjetivo, la cual corresponde a
buscar la solución y tomar la decisión. Dichas técnicas son:
• Articulación A priori de Preferencias: Tomar decisiones antes de buscar (decidir => buscar).
• Articulación A posteriori de Preferencias: Buscar antes de tomar decisiones (buscar => decidir).
• Articulación Progresiva de Preferencias: Integrar la búsqueda con la toma de decisiones (decidir
⟺ buscar).
