Многоцелевое линейное программирование

Многокритериальное линейное программирование — это подобласть математической оптимизации . Многоцелевая линейная программа (MOLP) — это линейная программа с более чем одной целевой функцией. MOLP — это частный случай векторной линейной программы . Многоцелевое линейное программирование также является подобластью многоцелевой оптимизации .

Формулировка задачи

В математических терминах MOLP можно записать как:

\min _{x}Px\quad {\text{s.t.}}\quad a\leq Bx\leq b,\;\ell \leq x\leq u

где $B$ это $(m\times n)$ матрица, $P$ это $(q\times n)$ матрица, $a$ это $m$ -мерный вектор с компонентами в $\mathbb {R} \cup \{-\infty \}$ , $b$ это $m$ -мерный вектор с компонентами в $\mathbb {R} \cup \{+\infty \}$ , $\ell$ это $n$ -мерный вектор с компонентами в $\mathbb {R} \cup \{-\infty \}$ , $u$ это $n$ -мерный вектор с компонентами в $\mathbb {R} \cup \{+\infty \}$

Концепции решения

Возможная точка $x$ называется эффективным, если не существует допустимой точки $y$ с $Px\leq Py$ , $Px\neq Py$ , где $\leq$ обозначает покомпонентное упорядочение.

Часто в литературе целью многоцелевого линейного программирования является вычисление набора всех эффективных экстремальных точек. ^[1] Существуют также алгоритмы определения множества всех максимальных эффективных граней. ^[2] Исходя из этих целей, совокупность всех эффективных (крайних) точек можно рассматривать как решение МОЛП. Этот тип концепции решения называется основанным на наборе решений . ^[3] Он не совместим с оптимальным решением линейной программы, а скорее параллелен множеству всех оптимальных решений линейной программы (которое труднее определить).

Эффективные точки часто называют эффективными решениями . Этот термин вводит в заблуждение, поскольку единственная эффективная точка уже может быть получена путем решения одной линейной программы, например, линейной программы с тем же набором допустимых решений и целевой функцией, представляющей собой сумму целей MOLP. ^[4]

В более поздних источниках рассматриваются на основе набора результатов. концепции решений ^[5] и соответствующие алгоритмы. ^[6]^[3] Предположим, что MOLP ограничен, т.е. существует некоторый $y\in \mathbb {R} ^{q}$ такой, что $y\leq Px$ для всех возможных $x$ . Решение MOLP определяется как конечное подмножество ${\bar {S}}$ эффективных точек, несущих достаточное количество информации для описания верхнего образа МОЛП. Обозначая $S$ допустимое множество MOLP, верхний образ MOLP — это множество ${\mathcal {P}}:=P[S]+\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:\;\exists x\in S:y\geq Px\}$ . Формальное определение решения ^[5]^[7] заключается в следующем:

Конечное множество ${\bar {S}}$ эффективных точек называется решением задачи MOLP, если $\operatorname {conv} P[{\bar {S}}]+\mathbb {R} _{+}^{q}={\mathcal {P}}$ («ув» обозначает выпуклую оболочку).

Если MOLP не ограничен, решение состоит не только из точек, но и из точек и направлений. ^[7]^[8]

Методы решения

Многокритериальные варианты симплексного алгоритма используются для вычисления решений на основе набора решений. ^[1]^[2]^[9] и решения, основанные на наборе целей. ^[10]

Решения на основе набора целей могут быть получены с помощью алгоритма Бенсона . ^[3]^[8]

Связанные классы проблем

Многокритериальное линейное программирование эквивалентно многогранному проектированию. ^[11]

Ссылки

^ Перейти обратно: ^а ^б Экер, Дж. Г.; Куада, Айова (1978). «Нахождение всех эффективных экстремумов для многоцелевых линейных программ». Математическое программирование . 14 (1): 249–261. дои : 10.1007/BF01588968 . ISSN 0025-5610 . S2CID 42726689 .
^ Перейти обратно: ^а ^б Экер, Дж. Г.; Хегнер, Н.С.; Куада, Айова (1980). «Генерация всех максимальных эффективных граней для многоцелевых линейных программ». Журнал теории оптимизации и приложений . 30 (3): 353–381. дои : 10.1007/BF00935493 . ISSN 0022-3239 . S2CID 120455645 .
^ Перейти обратно: ^а ^б ^с Бенсон, Гарольд П. (1998). «Алгоритм внешней аппроксимации для генерации всех эффективных экстремальных точек в наборе результатов многоцелевой задачи линейного программирования». Журнал глобальной оптимизации . 13 (1): 1–24. дои : 10.1023/А:1008215702611 . ISSN 0925-5001 . S2CID 45440728 .
^ Эрготт, М. (2005). Многокритериальная оптимизация . Спрингер. CiteSeerX 10.1.1.360.5223 . дои : 10.1007/3-540-27659-9 . ISBN 978-3-540-21398-7 .
^ Перейти обратно: ^а ^б Хейде, Фрэнк; Лёне, Андреас (2011). «Концепции решения векторной оптимизации: свежий взгляд на старую историю» (PDF) . Оптимизация . 60 (12): 1421–1440. дои : 10.1080/02331931003665108 . ISSN 0233-1934 . S2CID 54519405 .
^ Дауэр, JP; Салех, ОА (1990). «Построение набора эффективных целевых значений в многоцелевых линейных программах». Европейский журнал операционных исследований . 46 (3): 358–365. дои : 10.1016/0377-2217(90)90011-Y . ISSN 0377-2217 .
^ Перейти обратно: ^а ^б Лёне, Андреас (2011). Векторная оптимизация с помощью инфимума и супремума . Векторная оптимизация. дои : 10.1007/978-3-642-18351-5 . ISBN 978-3-642-18350-8 . ISSN 1867-8971 .
^ Перейти обратно: ^а ^б Лёне, Андреас; Вайсинг, Бенджамин (2017). «Векторный решатель линейных программ Bensolve – заметки по теоретическим основам». Европейский журнал операционных исследований . 260 (3): 807–813. arXiv : 1510.04823 . дои : 10.1016/j.ejor.2016.02.039 . ISSN 0377-2217 . S2CID 17267946 .
^ Арманд, П.; Маливерт, К. (1991). «Определение эффективного множества в многокритериальном линейном программировании». Журнал теории оптимизации и приложений . 70 (3): 467–489. CiteSeerX 10.1.1.161.9730 . дои : 10.1007/BF00941298 . ISSN 0022-3239 . S2CID 18407847 .
^ Рудлофф, Биргит; Улус, Фирдевс; Вандербей, Роберт (2016). «Параметрический симплекс-алгоритм для задач линейной векторной оптимизации». Математическое программирование . 163 (1–2): 213–242. arXiv : 1507.01895 . дои : 10.1007/s10107-016-1061-z . ISSN 0025-5610 . S2CID 13844342 .
^ Лёне, Андреас; Вайсинг, Бенджамин (2016). «Эквивалентность между многогранной проекцией, многоцелевым линейным программированием и векторным линейным программированием». Математические методы исследования операций . 84 (2): 411–426. arXiv : 1507.00228 . дои : 10.1007/s00186-016-0554-0 . ISSN 1432-2994 . S2CID 26137201 .

[EckerKouada1978-1] Перейти обратно: ^а ^б Экер, Дж. Г.; Куада, Айова (1978). «Нахождение всех эффективных экстремумов для многоцелевых линейных программ». Математическое программирование . 14 (1): 249–261. дои : 10.1007/BF01588968 . ISSN 0025-5610 . S2CID 42726689 .

[EckerHegner1980-2] Перейти обратно: ^а ^б Экер, Дж. Г.; Хегнер, Н.С.; Куада, Айова (1980). «Генерация всех максимальных эффективных граней для многоцелевых линейных программ». Журнал теории оптимизации и приложений . 30 (3): 353–381. дои : 10.1007/BF00935493 . ISSN 0022-3239 . S2CID 120455645 .

[Benson1998-3] Перейти обратно: ^а ^б ^с Бенсон, Гарольд П. (1998). «Алгоритм внешней аппроксимации для генерации всех эффективных экстремальных точек в наборе результатов многоцелевой задачи линейного программирования». Журнал глобальной оптимизации . 13 (1): 1–24. дои : 10.1023/А:1008215702611 . ISSN 0925-5001 . S2CID 45440728 .

[Ehrgott2015-4] Эрготт, М. (2005). Многокритериальная оптимизация . Спрингер. CiteSeerX 10.1.1.360.5223 . дои : 10.1007/3-540-27659-9 . ISBN 978-3-540-21398-7 .

[HeydeLöhne2011-5] Перейти обратно: ^а ^б Хейде, Фрэнк; Лёне, Андреас (2011). «Концепции решения векторной оптимизации: свежий взгляд на старую историю» (PDF) . Оптимизация . 60 (12): 1421–1440. дои : 10.1080/02331931003665108 . ISSN 0233-1934 . S2CID 54519405 .

[DauerSaleh1990-6] Дауэр, JP; Салех, ОА (1990). «Построение набора эффективных целевых значений в многоцелевых линейных программах». Европейский журнал операционных исследований . 46 (3): 358–365. дои : 10.1016/0377-2217(90)90011-Y . ISSN 0377-2217 .

[Löhne2011-7] Перейти обратно: ^а ^б Лёне, Андреас (2011). Векторная оптимизация с помощью инфимума и супремума . Векторная оптимизация. дои : 10.1007/978-3-642-18351-5 . ISBN 978-3-642-18350-8 . ISSN 1867-8971 .

[LöhneWeißing2017-8] Перейти обратно: ^а ^б Лёне, Андреас; Вайсинг, Бенджамин (2017). «Векторный решатель линейных программ Bensolve – заметки по теоретическим основам». Европейский журнал операционных исследований . 260 (3): 807–813. arXiv : 1510.04823 . дои : 10.1016/j.ejor.2016.02.039 . ISSN 0377-2217 . S2CID 17267946 .

[ArmandMalivert1991-9] Арманд, П.; Маливерт, К. (1991). «Определение эффективного множества в многокритериальном линейном программировании». Журнал теории оптимизации и приложений . 70 (3): 467–489. CiteSeerX 10.1.1.161.9730 . дои : 10.1007/BF00941298 . ISSN 0022-3239 . S2CID 18407847 .

[RudloffUlus2016-10] Рудлофф, Биргит; Улус, Фирдевс; Вандербей, Роберт (2016). «Параметрический симплекс-алгоритм для задач линейной векторной оптимизации». Математическое программирование . 163 (1–2): 213–242. arXiv : 1507.01895 . дои : 10.1007/s10107-016-1061-z . ISSN 0025-5610 . S2CID 13844342 .

[LöhneWeißing2016-11] Лёне, Андреас; Вайсинг, Бенджамин (2016). «Эквивалентность между многогранной проекцией, многоцелевым линейным программированием и векторным линейным программированием». Математические методы исследования операций . 84 (2): 411–426. arXiv : 1507.00228 . дои : 10.1007/s00186-016-0554-0 . ISSN 1432-2994 . S2CID 26137201 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]