El algoritmo de Benson

El algoritmo de Benson , que recibe su nombre de Harold Benson , es un método para resolver problemas de programación lineal multiobjetivo y programas lineales vectoriales. Funciona encontrando los "puntos extremos eficientes en el conjunto de resultados". ^{[ 1 ]} El concepto principal del algoritmo de Benson es evaluar la imagen superior del problema de optimización vectorial mediante planos de corte . ^{[ 2 ]}

Consideremos un programa lineal vectorial.

${\displaystyle \min _{C}Px\;{\text{ sujeto a }}Ax\geq b}$

para${\displaystyle P\in \mathbb {R} ^{q\times n}}$,${\displaystyle A\in \mathbb {R} ^{m\times n}}$,${\displaystyle b\in \mathbb {R} ^{m}}$y un cono de ordenamiento convexo poliédrico${\displaystyle C}$que tiene interior no vacío y no contiene líneas. El conjunto factible es${\displaystyle S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}}$. En particular, el algoritmo de Benson encuentra los puntos extremos del conjunto${\displaystyle P[S]+C}$, que se denomina imagen superior. ^{[ 2 ]}

En caso de${\displaystyle C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}}$, se obtiene el caso especial de un programa lineal multiobjetivo ( optimización multiobjetivo ).

Existe una variante dual del algoritmo de Benson, ^{[ 3 ]} que se basa en la dualidad geométrica ^{[ 4 ]} para programas lineales multiobjetivo.

Bensolve: un solucionador VLP gratuito

• www.bensolve.org

Interno

• Enlace a GitHub