В математической оптимизации , порядковое оптимизации является максимизация функций , принимающих значения в частично упорядоченном множестве ( «посетом»). [1] [2] [3] [4] Порядковая оптимизация имеет приложения в теории сетей массового обслуживания .
Математические основы
Определения
Частичный порядок является бинарным отношением «≤» в течение множества P , который является рефлексивным , антисимметричным и транзитивным , то есть, для всех в , б , и с в Р , имеем:
- a ≤ a (рефлексивность);
- если a ≤ b и b ≤ a, то a = b (антисимметрия);
- если a ≤ b и b ≤ c, то a ≤ c (транзитивность).
Другими словами, частичный порядок - это антисимметричный предпорядок .
Набор с частичным порядком называется частично упорядоченным набором (также называемым poset ). Термин « упорядоченный набор» иногда также используется для позы, если из контекста ясно, что не подразумеваются никакие другие виды заказов. В частности, полностью упорядоченные множества также могут называться «упорядоченные множества», особенно в областях, где эти структуры более распространены, чем посеты.
Для различных элементов а, Ь из частично упорядоченного множества P , если A ≤ B или B ≤ , то и б являются сопоставимыми . В остальном они несравнимы . Если каждые два элемента ЧУМа сопоставимы, ЧУМ называется полностью упорядоченным множеством или цепочкой (например, натуральные числа по порядку). Позиционирование, в котором каждые два элемента несравнимы, называется антицепью .
Примеры
Стандартные примеры позет, возникающих в математике, включают:
- В действительных числах упорядочены по стандарту менее чем или равные отношению ≤ (полностью упорядоченное множество, а).
- Множество подмножеств данного множества (его мощности ), упорядоченное по включению
- Множество подпространств векторного пространства, упорядоченное по включению.
- Для частично упорядоченного множества Р , то пространство последовательностей , содержащее все последовательности элементов из Р , где последовательность последовательности предшествует Ь , если каждый элемент в течение предшествует соответствующий пункт в б . Формально ( a n ) n ∈ℕ ≤ ( b n ) n ∈ℕ тогда и только тогда, когда a n ≤ b n для всех n в ℕ.
- Для множества X и частично упорядоченного множества Р , тем функциональное пространство , содержащее все функции из X в Р , где Р ≤ г тогда и только тогда , когда F ( х ) ≤ г ( х ) для всех х в X .
- Множество вершин ориентированного ациклического графа, упорядоченное по достижимости .
- Множество натуральных чисел с отношением делимости .
Extrema
Есть несколько понятий «наибольшего» и «наименьшего» элемента в позиционном множестве P , а именно:
- Наибольший элемент и наименьший элемент: элемент г в Р является наибольшим элементом , если для каждого элемента а в P , ≤ г . Элемент т в P является наименьшим элементом , если для каждого элемента а в P , в ≥ м . У посета может быть только один наибольший или наименьший элемент.
- Максимальные элементы и минимальные элементы: элемент g в P является максимальным элементом, если нет такого элемента a в P , что a > g . Аналогично, элемент m в P является минимальным элементом, если в P нет такого элемента a , что a < m . Если ЧУМ имеет наибольший элемент, он должен быть единственным максимальным элементом, но в противном случае может быть более одного максимального элемента, и то же самое для наименьших элементов и минимальных элементов.
- Верхние и нижние границы : Для подмножества А из Р , элемент х в Р есть верхняя граница А , если ≤ х , для каждого элемента а в A . В частности, й не должен быть в A , чтобы быть верхней границей A . Аналогичным образом , элемент х в Р является нижней гранью А , если ≥ х , для каждого элемента а в A . Наибольший элемент из Р представляет собой верхнюю грань Р самого, и наименьший элемент является нижняя граница Р .
Например, рассмотрим натуральные числа, упорядоченные по делимости: 1 - наименьший элемент, поскольку он делит все другие элементы, но в этом множестве нет ни самого большого элемента, ни каких-либо максимальных элементов: любой g делит 2 g , поэтому 2 g больше, чем g, и g не может быть максимальным. Если вместо этого мы рассматриваем только натуральные числа, которые больше 1, то полученный poset не имеет наименьшего элемента, но любое простое число является минимальным элементом. В этом ЧУМ 60 - это верхняя граница (но не наименьшая верхняя граница) {2,3,5}, а 2 - нижняя граница {4,6,8,12}.
Дополнительная конструкция
Во многих таких случаях poset имеет дополнительную структуру: например, poset может быть решеткой или частично упорядоченной алгебраической структурой .
Решетки
Ч.у.м. ( L , ≤) является решеткой , если оно удовлетворяет следующие два аксиом.
- Существование бинарных объединений
- Для любых двух элементов a и b из L множество { a, b } имеет соединение : (также известный как наименьшая верхняя граница или супремум).
- Существование двоичного кода встречается
- Для любых двух элементов a и b из L множество { a, b } пересекается : (также известный как точная нижняя граница или точная нижняя грань).
Соединение и пересечение точек a и b обозначаются а также , соответственно. Это определение делает а также бинарные операции . Первая аксиома говорит, что L - полурешетка соединения ; второй говорит, что L - встречная полурешетка . Обе операции монотонны по порядку: из a 1 ≤ a 2 и b 1 ≤ b 2 следует, что a 1б 1 ≤ а 2 b 2 и a 1б 1 ≤ а 2б 2 .
Из аргумента индукции следует, что каждое непустое конечное подмножество решетки имеет соединение (супремум) и встречу (инфимум). С дополнительными предположениями можно сделать дальнейшие выводы; см. Полноту (теория порядка) для более подробного обсуждения этого предмета.
Ограниченная решетка имеет наибольшее (или максимум) и не менее элемент (или минимум), обозначим 1 и 0 в соответствии с соглашением (также называемой верхней и нижней ). Любую решетку можно превратить в ограниченную, добавив наибольший и наименьший элемент, и каждая непустая конечная решетка ограничена, взяв соединение (соответственно, пересечение) всех элементов, обозначенное (соотв.) где .
ЧУМ является ограниченной решеткой тогда и только тогда, когда каждый конечный набор элементов (включая пустой набор) имеет соединение и пересечение. Здесь соединение пустого набора элементов определяется как наименьший элемент, а встреча пустого множества определяется как наибольший элемент . Это соглашение согласуется с ассоциативностью и коммутативностью функций meet and join: объединение объединения конечных множеств равно объединению объединений множеств, и, соответственно, объединение объединения конечных множеств равно объединению пересечений множеств, т. е. для конечных подмножеств A и B ч.у.набора L ,
а также
держать. Принимая B за пустое множество,
а также
что согласуется с тем фактом, что .
Упорядоченная алгебраическая структура
ЧУМ может быть частично упорядоченной алгебраической структурой . [5] [6] [1] [7] [8] [9] [10]
В алгебре , упорядоченная полугруппа является полугруппа ( S , •) вместе с частичным порядком ≤ , который совместим с операцией полугрупповой, а это означает , что х ≤ у подразумевает г • х ≤ г • у и х • г ≤ у • г для все х , у , г в S . Если S - группа и упорядочена как полугруппа, получается понятие упорядоченной группы , и аналогично, если S - моноид, его можно назвать упорядоченным моноидом . Частично упорядоченные векторные пространства и векторные решетки важны при оптимизации с несколькими целями . [11]
Порядковая оптимизация в информатике и статистике
Проблемы порядковой оптимизации возникают во многих дисциплинах. Ученые-информатики изучают алгоритмы выбора , которые проще алгоритмов сортировки . [12] [13]
Статистическая теория принятия решений изучает «проблемы отбора», которые требуют определения «лучшей» субпопуляции или определения «почти лучшей» субпопуляции. [14] [15] [16] [17] [18]
Приложения
С 1960-х годов область порядковой оптимизации расширилась как в теории, так и в приложениях. В частности, антиматроиды и « алгебра макс-плюс » нашли применение в сетевом анализе и теории массового обслуживания , особенно в сетях массового обслуживания и системах с дискретными событиями . [19] [20] [21]
Смотрите также
- Стохастическая оптимизация
- Теория вычислительной сложности
- Эвристика
- Уровень измерения («Порядковые данные»)
Рекомендации
- ^ a b Дитрих, BL ; Хоффман, AJ О жадных алгоритмах, частично упорядоченных множествах и субмодульных функциях. IBM J. Res. Dev. 47 (2003), нет. 1, 25–30.
- ^ Топкис, Дональд М. Супермодульность и дополнительность . Границы экономических исследований. Princeton University Press, Princeton, NJ, 1998. xii + 272 pp. ISBN 0-691-03244-0
- ^ Зингер, Иван Абстрактный выпуклый анализ . Серия монографий и продвинутых текстов Канадского математического общества. Публикация Wiley-Interscience. John Wiley & Sons, Inc., Нью-Йорк, 1997. xxii + 491 с. ISBN 0-471-16015-6
- ^ Бьёрнер, Андерс; Циглер, Гюнтер М. Введение в гридоиды. Приложения Matroid, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Кембридж, 1992 г.,
- ^ Fujishige, Satoru Субмодульные функции и оптимизация . Второе издание. Annals of Discrete Mathematics, 58. Elsevier BV, Amsterdam, 2005. xiv + 395 с. ISBN 0-444-52086-4
- ^ Гондран, Мишель; Мину, Мишель Графики, дииды и полукольца. Новые модели и алгоритмы . Серия исследований операций / интерфейсов компьютерных наук, 41. Springer, New York, 2008. xx + 383 pp. ISBN 978-0-387-75449-9
- ^ Мурота, Кадзуо Дискретный выпуклый анализ . Монографии SIAM по дискретной математике и приложениям. Общество промышленной и прикладной математики (SIAM), Филадельфия, Пенсильвания, 2003. xxii + 389 с. ISBN 0-89871-540-7
- ^ Топкис, Дональд М. Супермодульность и дополнительность . Границы экономических исследований. Princeton University Press, Princeton, NJ, 1998. xii + 272 с. ISBN 0-691-03244-0
- ^ Циммерманн, У. Линейная и комбинаторная оптимизация в упорядоченных алгебраических структурах . Аня. Дискретная математика. 10 (1981), viii + 380 с.
- ^ Cuninghame-Green, Raymond Minimax алгебра . Конспект лекций по экономике и математическим системам, 166. Springer-Verlag, Berlin-New York, 1979. xi + 258 pp. ISBN 3-540-09113-0
- ^ Зэлинеску, К. (2002). Выпуклый анализ в общих векторных пространствах . Ривер Эдж, Нью-Джерси: World Scientific Publishing Co., Inc., стр. Xx + 367. ISBN 981-238-067-1. Руководство по ремонту 1921556 .
- ^ Дональд Кнут . Искусство программирования , Том 3: Сортировка и поиск , третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89685-0 . Раздел 5.3.3: Выбор минимального сравнения, стр.207–219.
- ^ Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Глава 9: Медианы и статистика порядка, стр. 183–196. Раздел 14.1: Динамическая статистика заказов, стр. 302–308.
- ^ Гиббонс, Джин Дикинсон ; Олкин, Ингрэм и Собел, Милтон, Выбор и упорядочение популяций , Wiley, (1977). (Переиздано SIAM как "Классик прикладной математики".)
- ^ Gupta, Shanti S .; Панчапакесан, С. (1979). Процедуры множественного принятия решений: теория и методология отбора и ранжирования популяций . Ряд Уайли по вероятности и математической статистике. Нью-Йорк: Джон Вили и сыновья. С. xxv + 573. ISBN 0-471-05177-2. Руководство по ремонту 0555416 . (Переиздано SIAM как "Классик прикладной математики".)
- ^ Сантнер, Томас Дж., И Тамхейн, А.С., Планирование экспериментов: ранжирование и отбор , М. Деккер, (1984).
- ^ Роберт Э. Беххофер, Томас Дж. Сантнер, Дэвид М. Голдсман. Дизайн и анализ экспериментов для статистического отбора, скрининга и множественных сравнений . Джон Вили и сыновья, 1995.
- ^ Фридрих Лизе, Клаус-Дж. Miescke. 2008. Статистическая теория принятия решений: оценка, тестирование и выбор . Springer Verlag.
- ^ Глассерман, Пол; Яо, Дэвид Д. (1994). Монотонная структура в дискретно-событийных системах . Ряд Уайли в вероятности и математической статистике: прикладная вероятность и статистика. Нью-Йорк: John Wiley & Sons, Inc., стр. Xiv + 297. ISBN 0-471-58041-4. Руководство по ремонту 1266839 .
- ^ Баччелли, Франсуа Луи; Коэн, Гай; Ольсдер, Герт Ян; Квадрат, Жан-Пьер (1992). Синхронизация и линейность: алгебра для дискретных систем событий . Ряд Уайли в вероятности и математической статистике: вероятность и математическая статистика. Чичестер: John Wiley & Sons, Ltd., стр. Xx + 489. ISBN 0-471-93609-X. Руководство по ремонту 1204266 .
- ^ Хайдерготт, Бернд; Олдсер, Герт Ян; ван дер Вуде, Джейкоб (2006). Max plus в работе: Моделирование и анализ синхронизированных систем, курс по алгебре max-plus и ее приложениям . Принстонская серия по прикладной математике. Принстон, Нью-Джерси: Издательство Принстонского университета. С. xii + 213. ISBN 978-0-691-11763-8. Руководство по ремонту 2188299 .
дальнейшее чтение
- Fujishige, Satoru Субмодульные функции и оптимизация . Второе издание. Annals of Discrete Mathematics, 58. Elsevier BV, Amsterdam, 2005. xiv + 395 с. ISBN 0-444-52086-4
- Гондран, Мишель; Мину, Мишель Графики, дииды и полукольца. Новые модели и алгоритмы . Серия исследований операций / интерфейсов компьютерных наук, 41. Springer, New York, 2008. xx + 383 pp. ISBN 978-0-387-75449-9
- Дитрих, Б.Л .; Хоффман, AJ О жадных алгоритмах, частично упорядоченных множествах и субмодульных функциях. IBM J. Res. Dev. 47 (2003), нет. 1, 25–30.
- Мурота, Казуо Дискретный выпуклый анализ . Монографии SIAM по дискретной математике и приложениям. Общество промышленной и прикладной математики (SIAM), Филадельфия, Пенсильвания, 2003. xxii + 389 с. ISBN 0-89871-540-7
- Топкис, Дональд М. Супермодульность и дополнительность . Границы экономических исследований. Princeton University Press, Princeton, NJ, 1998. xii + 272 с. ISBN 0-691-03244-0
- Зингер, Иван Абстрактный выпуклый анализ . Серия монографий и продвинутых текстов Канадского математического общества. Публикация Wiley-Interscience. John Wiley & Sons, Inc., Нью-Йорк, 1997. xxii + 491 с. ISBN 0-471-16015-6
- Бьёрнер, Андерс; Циглер, Гюнтер М. Введение в гридоиды. Приложения Matroid, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Кембридж, 1992 г.,
- Циммерманн, У. Линейная и комбинаторная оптимизация в упорядоченных алгебраических структурах . Аня. Дискретная математика. 10 (1981), viii + 380 с.
- Cuninghame-Green, Raymond Minimax алгебра . Конспект лекций по экономике и математическим системам, 166. Springer-Verlag, Berlin-New York, 1979. xi + 258 pp. ISBN 3-540-09113-0
- Баччелли, Франсуа Луи; Коэн, Гай; Ольсдер, Герт Ян; Квадрат, Жан-Пьер (1992). Синхронизация и линейность: алгебра для дискретных систем событий . Ряд Уайли в вероятности и математической статистике: вероятность и математическая статистика. Чичестер: John Wiley & Sons, Ltd., стр. Xx + 489. ISBN 0-471-93609-X. Руководство по ремонту 1204266 .
- Глассерман, Пол; Яо, Дэвид Д. (1994). Монотонная структура в дискретно-событийных системах . Ряд Уайли в вероятности и математической статистике: прикладная вероятность и статистика. Нью-Йорк: John Wiley & Sons, Inc., стр. Xiv + 297. ISBN 0-471-58041-4. Руководство по ремонту 1266839 .
- Хайдерготт, Бернд; Олдсер, Герт Ян; ван дер Вуде, Джейкоб (2006). Max plus в работе: Моделирование и анализ синхронизированных систем, курс по алгебре max-plus и ее приложениям . Принстонская серия по прикладной математике. Принстон, Нью-Джерси: Издательство Принстонского университета. С. xii + 213. ISBN 978-0-691-11763-8. Руководство по ремонту 2188299 .
- Хо, Ю.К. , Шринивас, Р., Вакили, П., "Порядковая оптимизация динамических систем с дискретными событиями", J. of DEDS 2 (2), 61-88, (1992).
- Аллен, Эрик и Мария Д. Илич . Решения об обязательствах на основе цены на рынке электроэнергии . Достижения в промышленном контроле. Лондон: Springer, 1999. ISBN 978-1-85233-069-9
Внешние ссылки
- Аннотированный библиографический по порядковому оптимизации на Ю-Чи Хо