벤슨의 알고리즘

해롤드 벤슨의 이름을 딴 벤슨의 알고리즘은 다목적 선형 프로그래밍 문제와 벡터 선형 프로그램을 푸는 방법이다.이것은 "결과 집합에서 효율적 극한점"을 찾음으로써 작동한다.^[1]벤슨의 알고리즘에서 일차 개념은 벡터 최적화 문제의 상위 이미지를 절단면을 통해 평가하는 것이다.^[2]

알고리즘의 개념

벡터 선형 프로그램 고려

{\displaystyle \min _{C}Px\;{\text{{}}에 해당됨

for $P\in \mathbb {R} ^{q\times n}$ , $A\in \mathbb {R} ^{m\times n}$ , $b\in \mathbb {R} ^{m}$ and a polyhedral convex ordering cone $C$ having nonempty interior and containing no lines.실현 가능한 집합은 $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ = $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ { $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ : $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ ${\displaystyle S=\{x\in \mathb {R} ^{n}\;$ $Ax\geq$ b $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ 특히 벤슨의 $P[S]+C$ 은 설정된 $P[S]+C$ P [ $P[S]+C$ + C $P[S]+C$ 의 극한점을 찾는데 $P[S]+C$ 이를 upper image라고 한다.^[2]

$C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ = $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ + $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ { y $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ : $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ 0 $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ , $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ … , $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ q $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ } ${\displaystyle$ C $=\mathb {R} _{+}^{q}:$ $=\\{y\in \mathb {R} ^{q:y_{1}\geq 0,\dots,y_{q}\geq$ 0 $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ 다목적 선형 프로그램의 특별한 경우(다목적 최적화)를 얻는다.

이중 알고리즘

다목적 선형 프로그램을 위한 기하학적 이중성을^[4] 바탕으로 한 벤슨의 알고리즘에는 이중 변종이 있다.^[3]

구현

벤솔브 - 무료 VLP 해결사

www.bensolve.org

내부

github에 연결

참조

^ Harold P. Benson (1998). "An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem". Journal of Global Optimization. 13 (1): 1–24. doi:10.1023/A:1008215702611.
^ ^a ^b Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508.
^ Ehrgott, Matthias; Löhne, Andreas; Shao, Lizhen (2011). "A dual variant of Benson's "outer approximation algorithm" for multiple objective linear programming". Journal of Global Optimization. 52 (4): 757–778. doi:10.1007/s10898-011-9709-y. ISSN 0925-5001.
^ Heyde, Frank; Löhne, Andreas (2008). "Geometric Duality in Multiple Objective Linear Programming" (PDF). SIAM Journal on Optimization. 19 (2): 836–845. doi:10.1137/060674831. ISSN 1052-6234.

이 응용 수학 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

[Benson-1] Harold P. Benson (1998). "An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem". Journal of Global Optimization. 13 (1): 1–24. doi:10.1023/A:1008215702611.

[Lohne-2] Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508.

[EhrgottLöhne2011-3] Ehrgott, Matthias; Löhne, Andreas; Shao, Lizhen (2011). "A dual variant of Benson's "outer approximation algorithm" for multiple objective linear programming". Journal of Global Optimization. 52 (4): 757–778. doi:10.1007/s10898-011-9709-y. ISSN 0925-5001.

[HeydeLöhne2008-4] Heyde, Frank; Löhne, Andreas (2008). "Geometric Duality in Multiple Objective Linear Programming" (PDF). SIAM Journal on Optimization. 19 (2): 836–845. doi:10.1137/060674831. ISSN 1052-6234.

[1]

[2]

[4]

[3]

Search

벤슨의 알고리즘

네임스페이스

더

목차

알고리즘의 개념

이중 알고리즘

구현

참조