Алгоритм Бенсона

---

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

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

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

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

---