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

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

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

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

\min _{C}Px\;{\text{ subject to }}Ax\geq b

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

В случае $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

Внутренний

Ссылка на гитхаб

Ссылки

^ Гарольд П. Бенсон (1998). «Алгоритм внешней аппроксимации для создания всех эффективных экстремальных точек в наборе результатов многоцелевой задачи линейного программирования». Журнал глобальной оптимизации . 13 (1): 1–24. дои : 10.1023/А:1008215702611 .
^ Jump up to: ^а ^б Андреас Лёне (2011). Векторная оптимизация с минимумом и максимумом . Спрингер. стр. 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] Jump up to: ^а ^б Андреас Лёне (2011). Векторная оптимизация с минимумом и максимумом . Спрингер. стр. 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 ]