Алгоритм Бенсона - Википедия - Bensons algorithm

Алгоритм Бенсона, названный в честь Гарольд Бенсон, это метод решения многоцелевое линейное программирование задачи и векторные линейные программы. Это работает путем нахождения «эффективных экстремальных точек в наборе результатов».^[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

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

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