Bensonsův algoritmus - Bensons algorithm - Wikipedia

Bensonův algoritmus, pojmenoval podle Harold Benson, je metoda řešení vícecílové lineární programování problémy a vektorové lineární programy. Funguje to tak, že najdete „efektivní extrémní body v sadě výsledků“.^[1] Primárním konceptem v Bensonově algoritmu je vyhodnocení horního obrazu vektorová optimalizace problém řezací roviny.^[2]

Idea algoritmu

Zvažte vektorový lineární program

${ displaystyle min _ {C} Px ; { text {předmět}} Axe geq b}$

pro ${ displaystyle P in mathbb {R} ^ {q krát n}}$, ${ displaystyle A in mathbb {R} ^ {m krát n}}$, ${ displaystyle b in mathbb {R} ^ {m}}$ a polyedrický konvexní objednávkový kužel ${ displaystyle C}$ s neprázdným interiérem a bez řádků. Realizovatelná sada je ${ displaystyle S = {x v mathbb {R} ^ {n}: ; Axe geq b }}$. Zejména Bensonův algoritmus najde extrémní body sady ${ displaystyle P [S] + C}$, který se nazývá horní obrázek.^[2]

V případě ${ displaystyle C = mathbb {R} _ {+} ^ {q}: = {y in mathbb {R} ^ {q}: y_ {1} geq 0, dots, y_ {q} geq 0 }}$, získá se speciální případ vícecílového lineárního programu (multiobjektivní optimalizace ).

Duální algoritmus

Existuje dvojí varianta Bensonova algoritmu,^[3] který je založen na geometrické dualitě^[4] pro vícecílové lineární programy.

Implementace

Bensolve - bezplatný řešič VLP

• www.bensolve.org

Vnitřní

• Odkaz na github

Reference

Tento aplikovaná matematika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.