Programación lineal multiobjetivo

La programación lineal multiobjetivo es un subcampo de la optimización matemática . Un programa lineal multiobjetivo (PLMO) es un programa lineal con más de una función objetivo. Un PLMO es un caso especial de un programa lineal vectorial . La programación lineal multiobjetivo también es un subcampo de la optimización multiobjetivo .

En términos matemáticos, un MOLP se puede escribir como:

${\displaystyle \min _{x}Px\quad {\text{st}}\quad a\leq Bx\leq b,\;\ell \leq x\leq u}$

dónde${\displaystyle B}$es un${\displaystyle (m\times n)}$matriz,${\displaystyle P}$es un${\displaystyle (q\times n)}$matriz,${\displaystyle a}$es un${\displaystyle m}$Vector de -dimensiones con componentes en${\displaystyle \mathbb {R} \cup \{-\infty \}}$,${\displaystyle b}$es un${\displaystyle m}$Vector de -dimensiones con componentes en${\displaystyle \mathbb {R} \cup \{+\infty \}}$,${\displaystyle \ell }$es un${\displaystyle n}$Vector de -dimensiones con componentes en${\displaystyle \mathbb {R} \cup \{-\infty \}}$,${\displaystyle u}$es un${\displaystyle n}$Vector de -dimensiones con componentes en${\displaystyle \mathbb {R} \cup \{+\infty \}}$

Un punto factible${\displaystyle x}$Se denomina eficiente si no hay ningún punto factible.${\displaystyle y}$con${\displaystyle Px\leq Py}$,${\displaystyle Px\neq Py}$, dónde${\displaystyle \leq }$indica el ordenamiento por componentes.

A menudo, en la literatura, el objetivo de la programación lineal multiobjetivo es calcular el conjunto de todos los puntos extremos eficientes... ^{[ 1 ]} También existen algoritmos para determinar el conjunto de todas las caras máximas eficientes. ^{[ 2 ]} Con base en estos objetivos, el conjunto de todos los puntos eficientes (extremos) puede considerarse la solución de la MOLP. Este tipo de concepto de solución se denomina basado en conjuntos de decisión . ^{[ 3 ]} No es compatible con una solución óptima de un programa lineal, sino que se asemeja al conjunto de todas las soluciones óptimas de un programa lineal (que es más difícil de determinar).

Los puntos eficientes se denominan frecuentemente soluciones eficientes . Este término es engañoso porque un único punto eficiente puede obtenerse resolviendo un programa lineal, como el programa lineal con el mismo conjunto factible y cuya función objetivo es la suma de los objetivos del MOLP. ^{[ 4 ]}

Referencias más recientes consideran conceptos de solución basados ​​en conjuntos de resultados ^{[ 5 ]} y algoritmos correspondientes. ^{[ 6 ] [ 3 ]} Supongamos que MOLP está acotado, es decir, hay algún${\displaystyle y\in \mathbb {R} ^{q}}$de tal manera que${\displaystyle y\leq Px}$para todos los factibles${\displaystyle x}$Una solución de MOLP se define como un subconjunto finito.${\displaystyle {\bar {S}}}$de puntos eficientes que contienen una cantidad suficiente de información para describir la imagen superior de MOLP. Denotando por${\displaystyle S}$el conjunto factible de MOLP, la imagen superior de MOLP es el conjunto${\displaystyle {\mathcal {P}}:=P[S]+\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:\;\exists x\in S:y\geq Px\}}$. Una definición formal de una solución ^{[ 5 ] [ 7 ]} es la siguiente:

Un conjunto finito${\displaystyle {\bar {S}}}$de puntos eficientes se llama solución a MOLP si ${\displaystyle \operatorname {conv} P[{\bar {S}}]+\mathbb {R} _{+}^{q}={\mathcal {P}}}$("conv" denota la envoltura convexa ).

Si MOLP no está acotado, una solución consiste no solo en puntos sino en puntos y direcciones ^{[ 7 ] [ 8 ]}

Las variantes multiobjetivo del algoritmo simplex se utilizan para calcular soluciones basadas en conjuntos de decisión ^{[ 1 ] [ 2 ] [ 9 ]} y soluciones basadas en conjuntos de objetivos. ^{[ 10 ]}

Las soluciones basadas en conjuntos de objetivos se pueden obtener mediante el algoritmo de Benson . ^{[ 3 ] [ 8 ]}

La programación lineal multiobjetivo es equivalente a la proyección poliédrica . ^{[ 11 ]}