Алгоритм Бенсона - Bensons algorithm - Wikipedia

Алгоритм Бенсона, названный в честь Гарольд Бенсон, это метод решения многоцелевое линейное программирование задачи и векторные линейные программы. Это работает путем нахождения «эффективных экстремальных точек в наборе результатов».^[1] Основная идея алгоритма Бенсона - оценить верхнее изображение векторная оптимизация проблема рубки.^[2]

Идея алгоритма

Рассмотрим векторную линейную программу

{ displaystyle min _ {C} Px ; { text {при условии}} Ax geq b}

за ${ Displaystyle П ин mathbb {R} ^ {д раз п}}$ , ${ Displaystyle А в mathbb {R} ^ {м раз п}}$ , ${ displaystyle b in mathbb {R} ^ {m}}$ и многогранный выпуклый упорядочивающий конус ${ displaystyle C}$ с непустым внутренним пространством и без строк. Возможный набор ${ Displaystyle S = {х in mathbb {R} ^ {n}: ; Ax geq b }}$ . В частности, алгоритм Бенсона находит крайние точки из набора ${ Displaystyle P [S] + C}$ , который называется верхним изображением.^[2]

В случае ${ displaystyle C = mathbb {R} _ {+} ^ {q}: = {y in mathbb {R} ^ {q}: y_ {1} geq 0, dots, y_ {q} geq 0 }}$ , получаем частный случай многоцелевой линейной программы (многокритериальная оптимизация ).

Двойной алгоритм

Существует двойной вариант алгоритма Бенсона,^[3] который основан на геометрической двойственности^[4] для многоцелевых линейных программ.

Реализации

Bensolve - бесплатный решатель VLP

www.bensolve.org

Внутренний

Ссылка на github

Рекомендации

^ Гарольд П. Бенсон (1998). «Алгоритм внешнего приближения для генерации всех эффективных экстремальных точек в исходном наборе задачи многократного объективного линейного программирования». Журнал глобальной оптимизации. 13 (1): 1–24. Дои:10.1023 / А: 1008215702611.
^ ^а ^б Андреас Лёне (2011). Векторная оптимизация с точками инфимума и супремума. Springer. С. 162–169. ISBN 9783642183508.
^ Эрготт, Матиас; Лёне, Андреас; Шао, Личжэнь (2011). «Двойной вариант« алгоритма внешнего приближения »Бенсона для многоцелевого линейного программирования». Журнал глобальной оптимизации. 52 (4): 757–778. Дои:10.1007 / s10898-011-9709-y. ISSN 0925-5001.
^ Хейде, Франк; Лёне, Андреас (2008). «Геометрическая двойственность в многоцелевом линейном программировании» (PDF). SIAM Journal по оптимизации. 19 (2): 836–845. Дои:10.1137/060674831. ISSN 1052-6234.

Этот Прикладная математика -связанная статья является заглушка. Вы можете помочь Википедии расширяя это.

[Benson-1] Гарольд П. Бенсон (1998). «Алгоритм внешнего приближения для генерации всех эффективных экстремальных точек в исходном наборе задачи многократного объективного линейного программирования». Журнал глобальной оптимизации. 13 (1): 1–24. Дои:10.1023 / А: 1008215702611.

[Lohne-2] а ^б Андреас Лёне (2011). Векторная оптимизация с точками инфимума и супремума. Springer. С. 162–169. ISBN 9783642183508.

[EhrgottLöhne2011-3] Эрготт, Матиас; Лёне, Андреас; Шао, Личжэнь (2011). «Двойной вариант« алгоритма внешнего приближения »Бенсона для многоцелевого линейного программирования». Журнал глобальной оптимизации. 52 (4): 757–778. Дои:10.1007 / s10898-011-9709-y. ISSN 0925-5001.

[HeydeLöhne2008-4] Хейде, Франк; Лёне, Андреас (2008). «Геометрическая двойственность в многоцелевом линейном программировании» (PDF). SIAM Journal по оптимизации. 19 (2): 836–845. Дои:10.1137/060674831. ISSN 1052-6234.

[1]

[2]

[3]

[4]