Лексикографическая оптимизация
Лексикографическая оптимизация — это разновидность многокритериальной оптимизации . В общем, многокритериальная оптимизация имеет дело с задачами оптимизации, в которых две или более целевые функции подлежат оптимизации одновременно. Часто различные цели можно ранжировать в порядке важности для лица, принимающего решения, так что цель является наиболее важной и объективной является следующим по важности и так далее. Лексикографическая оптимизация предполагает, что лицо, принимающее решения, предпочитает даже очень небольшое увеличение , даже к очень большому увеличению и т. д. Точно так же лицо, принимающее решение, предпочитает даже очень небольшое увеличение , даже к очень большому увеличению и т. д. Другими словами, лицо, принимающее решения, имеет лексикографические предпочтения , ранжируя возможные решения в соответствии с лексикографическим порядком значений их целевой функции. Лексикографическую оптимизацию иногда называют упреждающей оптимизацией . [1] поскольку небольшое увеличение одной объективной ценности предвосхищает гораздо большее увеличение менее важных объективных ценностей.
В качестве примера рассмотрим компанию, которая ставит безопасность превыше всего. Компания хочет максимизировать безопасность своих работников и клиентов. При условии достижения максимально возможной безопасности он хочет максимизировать прибыль. Эта фирма выполняет лексикографическую оптимизацию, где означает безопасность и обозначает прибыль.
В качестве другого примера: [2] в управлении проектами при анализе сетей PERT часто хочется минимизировать среднее время завершения и при этом минимизировать дисперсию времени завершения.
Обозначения
[ редактировать ]Задачу лексикографической максимизации часто записывают так: где функции, которые необходимо максимизировать, упорядочены от наиболее важных к наименее важным; – вектор переменных решения; и - допустимое множество множество возможных значений . Аналогично можно определить задачу лексикографической минимизации.
Алгоритмы
[ редактировать ]Существует несколько алгоритмов решения задач лексикографической оптимизации. [3]
Последовательный алгоритм для общих целей
[ редактировать ]Задача оптимизации лексиминов с n целями может быть решена с использованием последовательности из n задач одноцелевой оптимизации следующим образом: [1] [3] : Алг.1
- Для t = 1,...,n делаем
- Решите следующую однокритериальную задачу:
- Если проблема неосуществима или неограниченна, остановитесь и заявите, что решения нет.
- В противном случае подставьте значение оптимального решения в и продолжить.
- Конец на
Итак, на первой итерации мы находим максимально возможное значение наиболее важной цели. и поместите это максимальное значение в . На второй итерации мы находим максимально возможное значение второй по важности цели. с дополнительным ограничением, согласно которому наиболее важная цель должна сохранять максимальное значение ; и так далее.
Последовательный алгоритм является общим — его можно применять всякий раз, когда у нас есть решатель для одноцелевых функций.
Лексикографический симплексный алгоритм для линейных целей
[ редактировать ]Линейная лексикографическая оптимизация [2] является частным случаем лексикографической оптимизации, в котором цели линейны, а допустимое множество описывается линейными неравенствами. Это можно записать как: где — векторы, представляющие линейные цели, которые необходимо максимизировать, упорядоченные от наиболее к наименее важным; – вектор переменных решения; а допустимое множество определяется матрицей и вектор .
Изерманн [2] распространил теорию двойственности линейного программирования на лексикографические линейные программы и разработал лексикографический симплексный алгоритм . В отличие от последовательного алгоритма, этот симплексный алгоритм рассматривает все целевые функции одновременно.
Средневзвешенное значение для линейных целей
[ редактировать ]Шерали и Сойстер [1] докажите, что для любой задачи линейной лексикографической оптимизации существует набор весов такая, что множество лексикографически-оптимальных решений идентично множеству решений следующей однокритериальной задачи: Один из способов вычисления весов предложен Ягером . [4] Он предполагает, что все объективные значения являются действительными числами от 0 до 1, а наименьшая разница между любыми двумя возможными значениями — это некоторая константа d < 1 (так что значения с разницей меньше d считаются равными). Тогда вес из установлено приблизительно . Это гарантирует, что максимизация взвешенной суммы эквивалентно лексикографической максимизации.
Кокоччони, Паппалардо и Сергеев [5] покажите, что, имея компьютер, который может выполнять числовые вычисления с бесконечно малыми числами , можно выбирать веса, которые являются бесконечно малыми (в частности: ; бесконечно мал; имеет бесконечно малый квадрат; и т. д.), и таким образом свести линейную лексикографическую оптимизацию к одноцелевому линейному программированию с бесконечно малыми числами. Они представляют адаптацию симплексного алгоритма к бесконечно малым числам и представляют несколько работающих примеров.
Характеристики
[ редактировать ](1) Уникальность . В общем, задача лексикографической оптимизации может иметь более одного оптимального решения. Однако, если и являются двумя оптимальными решениями, то их значения должны быть одинаковыми, т. е. для всех . [3] : Thm.2 Более того, если допустимая область представляет собой выпуклое множество , а целевые функции строго вогнутые , то задача имеет не более одного оптимального решения, поскольку если бы существовало два разных оптимальных решения, их среднее было бы другим допустимым решением, в котором целевые функции достигают более высокого значения, что противоречит оптимальности исходного решения.
(2) Частичные суммы . Учитывая вектор функций для оптимизации, для всех t в 1,..., n определите = сумма всех функций от самой важной до t -й по важности. Тогда исходная задача лексикографической оптимизации эквивалентна следующей: [3] : Thm.4 В некоторых случаях вторую проблему решить проще.
См. также
[ редактировать ]- Лексикографическая максим-минутная оптимизация — это вариант лексикографической оптимизации, в котором все цели одинаково важны, а цель состоит в том, чтобы максимизировать наименьшую цель, затем вторую наименьшую цель и так далее.
- В теории игр ядрышко определяется как лексикографически минимальное множество решений. [6]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Шерали, HD; Сойстер, Алабама (1 февраля 1983 г.). «Упреждающее и невытесняющее многоцелевое программирование: взаимосвязь и контрпримеры» . Журнал теории оптимизации и приложений . 39 (2): 173–186. дои : 10.1007/BF00934527 . ISSN 1573-2878 .
- ^ Jump up to: а б с Изерманн, Х. (1 декабря 1982 г.). «Линейная лексикографическая оптимизация» . Операции-Исследования-Спектр . 4 (4): 223–228. дои : 10.1007/BF01782758 . ISSN 1436-6304 .
- ^ Jump up to: а б с д Огрычак, В.; Пиоро, М.; Томашевский, А. (2005). «Проектирование телекоммуникационной сети и задача максим-мин оптимизации» . Журнал телекоммуникаций и информационных технологий . 3 : 43–56. ISSN 1509-4553 .
- ^ Ягер, Рональд Р. (1 октября 1997 г.). «Об аналитическом представлении упорядочения Лексимина и его применении к гибкому распространению ограничений» . Европейский журнал операционных исследований . 102 (1): 176–192. дои : 10.1016/S0377-2217(96)00217-2 . ISSN 0377-2217 .
- ^ Кокоччони, Марко; Паппалардо, Массимо; Сергеев, Ярослав Д. (01.02.2018). «Лексикографическое многокритериальное линейное программирование с использованием методологии Гроссона: Теория и алгоритм» . Прикладная математика и вычислительная техника . Последние тенденции в числовых вычислениях: теория и алгоритмы. 318 : 298–311. дои : 10.1016/j.amc.2017.05.058 . hdl : 11568/877746 . ISSN 0096-3003 .
- ^ Кольберг, Илон (1 июля 1972 г.). «Ядрышко как решение задачи минимизации» . SIAM Journal по прикладной математике . 23 (1): 34–39. дои : 10.1137/0123004 . ISSN 0036-1399 .