Автореферат (1149248)
Текст из файла
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиБАСКОВ Олег ВладимировичАЛГОРИТМЫ СУЖЕНИЯ МНОЖЕСТВА ПАРЕТОНА ОСНОВЕ ИНФОРМАЦИИ О ПРЕДПОЧТЕНИЯХ ЛПР05.13.01 — Системный анализ, управление и обработка информации(по прикладной математике и процессам управления)АВТОРЕФЕРАТдиссертации на соискание учёной степеникандидата физико-математических наукСанкт-Петербург2014Работа выполнена в ФГОУ ВПО «Санкт-Петербургский государственныйуниверситет».Научный руководитель: доктор физико-математических наук, профессорНогин Владимир ДмитриевичОфициальные оппоненты: доктор технических наук, профессорПетровский Алексей Борисович(Институт системного анализа РАН,заведующий лабораторией методов и системподдержки принятия решений)доктор физико-математических наук, профессорФлегонтов Александр Владимирович(Российский государственный педагогическийуниверситет им.
А.И.Герцена, заведующийкафедрой информационных системи программного обеспечения)Ведущая организация:Федеральное государственное бюджетноеучреждение науки «Санкт-Петербургскийэкономико-математический институт РАН»(СПбЭМИ)Защита состоится « »2014 г. вчасов на заседании советаД212.232.50 по защите диссертаций на соискание учёной степени кандидатанаук, на соискание учёной степени доктора наук при Санкт-Петербургскомгосударственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., 35, факультет ПМ—ПУ, ауд. 327.Отзывы на автореферат в 2-х экземплярах просим направлять по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., 35, учёномусекретарю диссертационного совета Д212.232.50 Г. И.
Курбатовой.С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034,Санкт-Петербург, Университетская наб., 7/9. Автореферат и диссертацияразмещены на сайте www.spbu.ru.Автореферат разослан « »2014 г.Учёный секретарь диссертационного советад-р физ.-мат.
наук, проф.Г. И. КурбатоваОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫАктуальность темы. Задачи принятия решения часто встречаются вразличных областях человеческой деятельности. В них лицу, принимающемурешение (ЛПР), необходимо выбрать одну или несколько альтернатив из множества возможных вариантов. При этом каждая альтернатива оценивается,как правило, по нескольким критериям, и варианта, оптимального с точкизрения всех критериев, не существует, что существенно осложняет выбор.Центральную роль в задачах многокритериального выбора играет принцип Эджворта — Парето, в соответствии с которым выбор должен производиться из множества парето-оптимальных вариантов, также называемого множеством Парето.
Однако на практике оно, как правило, оказываетсядовольно широким, причём все его элементы имеют различную значимостьдля ЛПР. Выбор конкретного парето-оптимального решения (или некоторогосравнительно узкого подмножества таких решений) до настоящего временипредставляет собой открытую концептуальную проблему, от успешного решения которой зависит качество принимаемых решений во многих областяхтехники и экономики.К настоящему времени разработано большое число подходов к решениюзадач многокритериального выбора. Значительный вклад в эту область внесли такие известные учёные, как Ю.
Б. Гермейер, О. И. Ларичев, А. В. Лотов, В. Д. Ногин, А. Б. Петровский, В. В. Подиновский, F. Y. Edgeworth,R. L. Keeney, V. Pareto, H. Raiffa, B. Roy, T. L. Saaty и многие другиеотечественные и зарубежные авторы. Предложенные подходы можно выделить в следующие группы: методы многокритериальной теории полезности(MAUT — Multiattribute Utility Theory), «outranking approaches», методы вербального анализа решений, различные итеративные процедуры принятия решений, а также аксиоматический подход к сужению множества Парето.Многие существующие подходы являются эвристическими: предлагаетсяправило поиска «наилучшего» решения, однако, в каком смысле оно «наилучшее» и для какого класса задач это правило применимо, не обосновывается.Поэтому актуальным представляется развитие таких методов, для которыхизвестен класс задач, где их применение допустимо.К числу таких методов относится развиваемый с 1980-х годов В.
Д. Ноги3ным аксиоматический подход к сужению множества Парето. Он существенноотличается от многих других методов тем, что не ставит задачу предоставитьЛПР решение, которое оно должно выбрать. Цель данного похода в том, чтобы помочь ЛПР сузить круг поиска «наилучшего» решения, которым изначально является множество парето-оптимальных вариантов. Сужение производится с помощью «квантов» информации об отношении предпочтения ЛПР,характеризующих готовность ЛПР пойти на компромисс. То, что при этомвсе исключённые при сужении варианты заведомо выбраны быть не могут,строго доказывается при условии выполнения аксиом «разумного» выбора.Предметом исследования являются задачи принятия решений примногих критериях.Цель диссертационной работы заключается в развитии аксиоматического подхода к сужению множества Парето.Ставятся задачи:1. предложить алгоритм, обеспечивающий сужение множества Парето наоснове произвольного конечного набора числовой информации об отношении предпочтения ЛПР и оформить этот алгоритм в виде пакетаприкладных программ ParSetRe;2.
построить и обосновать алгоритм, обеспечивающий сужение множестваПарето на основе произвольного конечного набора числовой информации о нечётком отношении предпочтения ЛПР;3. разработать критерий проверки предоставленных ЛПР «квантов» нанепротиворечивость, т. е. на согласованность с аксиомами «разумного»выбора.Научная новизна диссертации заключается в создании новых алгоритмов сужения множества Парето при помощи произвольного конечного наборачисловых «квантов» информации об отношении предпочтения ЛПР.Теоретическая и практическая значимости. В работе развиваетсяаксиоматический подход к сужению множества Парето и тем самым вносится определённый вклад в теорию принятия решений при многих критериях.Полученные результаты могут быть применены в различных задачах науки, техники и экономики.
Разработан программный пакет ParSetRe, который4позволит ЛПР применять аксиоматический подход в стоящих перед ним задачах.Достоверность научных результатов обеспечивается строгостью доказательств и согласованностью со всеми ранее полученными результатамив этой области.Апробация результатов исследования. Приведённые в диссертациирезультаты докладывались на XLI, XLII, XLIII, XLIV международных научных конференциях аспирантов и студентов «Процессы управления и устойчивость» факультета прикладной математики — процессов управления СПбГУ(Санкт-Петербург, 2010–2013), международной конференции «Конструктивный негладкий анализ и смежные вопросы» (Санкт-Петербург, 2012), VIIмосковской международной конференции по исследованию операций ORM2013 (Москва, 2013).Публикации. Материалы диссертации опубликованы в девяти работах[1–9], из которых три [1–3] являются статьями в журналах, входящих в Перечень ведущих рецензируемых научных журналов и изданий ВАК.Структура и объём диссертации.
Диссертация состоит из введения,четырёх глав, заключения и списка литературы, включающего 48 наименований. Объём составляет 84 страницы.Поддержка. Работа поддержана Российским фондом фундаментальныхисследований (проекты №№ 08-01-00301, 11-07-00449а, 14-07-00899).СОДЕРЖАНИЕ ДИССЕРТАЦИИВо введении обосновываются актуальность и научная новизна работы,обозреваются известные методы решения задачи многокритериального выбора, приводятся основные положения, выносимые на защиту.Первая глава диссертации посвящена рассмотрению случая чёткого отношения предпочтения ЛПР.
Описывается модель многокритериального выбора, состоящая из трёх объектов: множества возможных вариантов X, числового векторного критерия f размерности m и бинарного отношения предпочтения X , определённого на множестве возможных вариантов, но известного лишь частично. Отношение предпочтения отражает вкусы ЛПР в томсмысле, что запись x0 X x00 содержательно означает, что из пары вариан5тов x0 , x00 ЛПР выберет первый и не выберет второй.
Отобразив множествовариантов с помощью векторного критерия f в пространство Rm , можно получить множество возможных векторов Y = f (X), на котором индуцированоотношение предпочтения Y . Это так называемая векторная форма задачимногокритериального выбора.Формулируются аксиомы «разумного» выбора, накладывающие ограничения на свойства отношения предпочтения. Среди существенных требований, которые могут нарушаться в некоторых практических задачах, стоитотметить транзитивность и инвариантность относительно положительноголинейного преобразования. Кроме того, в них отношение предпочтения Yраспространяется на всё пространство Rm и получает обозначение . Такимобразом, становится возможным сравнивать и те варианты, которые не являются допустимыми.Цель ЛПР — найти множество выбираемых вариантов C(X). Однако математическое определение этому множеству в данном подходе сознательноне даётся, т.
к. оно существенно зависит от предпочтений ЛПР, которые может быть трудно выразить. На него лишь накладывается одно ограничение:множество выбираемых вариантов C(X) не должно содержать альтернатив,доминируемых по отношению предпочтения. Поэтому ищется не само множество C(X), а оценка сверху на него, которая предъявляется ЛПР для окончательного выбора.При выполнении аксиом справедлив принцип Эджворта — Парето, в соответствии с которым все выбираемые варианты должны лежать во множествеПарето Pf (X) = {x ∈ X |6 ∃x0 ∈ X : x0 X x}. Это исходная оценка сверху намножество выбираемых вариантов, которую предстоит улучшать в процессерешения задачи.Сужение множества Парето производится с помощью «квантов» дополнительной информации об отношении предпочтения ЛПР.Определение 1. Вектор u ∈ Rm задаёт «квант» информации об отношении предпочтения ЛПР, если он имеет хотя бы одну положительную и хотябы одну отрицательную компоненты и u 0.Содержательно «квант» информации описывает компромисс, на которыйсогласно ЛПР.
Отрицательные компоненты соответствуют тем критериям, покоторым ЛПР готово пойти на уступки. Абсолютные величины этих компо6нент показывают наибольший приемлемый размер уступок. Положительныекомпоненты показывают наименьший прирост по тем критериям, ради повышения оценок по которым которых ЛПР идёт на компромисс.Для учёта одного «кванта» информации применяется теорема, доказанная В.
Д. Ногиным (см. монографию «Принятие решений в многокритериальной среде: количественный подход», изд. 2, испр. и доп. М.: Физматлит, 2005). В ней строится новый векторный критерий g и доказывается,что множество Парето относительно него окажется лучшей оценкой сверху на множество выбираемых решений, нежели исходное множество Парето:C(X) ⊆ Pg (X) ⊆ Pf (X).Преобразование векторного критерия линейно, и его можно записать ввиде g = T f , где T — матрица соответствующей размерности, компонентыкоторой полностью определяются учитываемым «квантом» информации. Сеё помощью строится множество возможных векторов Z относительно новоговекторного критерия g как образ исходного множества возможных векторов:Z = T Y. На нём также можно индуцировать отношение предпочтения Z .Оказывается, что тройка hZ, g, Z i описывает задачу многокритериальноговыбора, для которой выполнены все аксиомы «разумного» выбора.Пусть теперь в исходной задаче hX, f, X i задано несколько «квантов»u1 , .
. . , up . После учёта первого так, как описано выше, появляется новая задача многокритериального выбора. Если удастся перенести в неё оставшиеся«кванты» информации, то задача учёта p «квантов» будет сведена к задачеучёта p − 1 «кванта». Роль новых «квантов» играют образы исходных: доказывается, что T u2 0, . . ., T up 0. Однако в соответствии с определением укаждого из этих векторов должны найтись хотя бы одна строго положительная и хотя бы одна строго отрицательная компоненты. Поэтому возможныдва специальных случая.Если какой-либо из образов «квантов» не имеет отрицательных компонент, не умаляя общности, T up ≥ 0, то соотношение T up 0 не несёт дополнительной информации и полностью соответствует аксиомам. Поэтому такиеобразы можно отбросить: описываемая этими «квантами» информация излишняя.Если какой-либо из образов «квантов» не имеет положительных компонент или вовсе оказывается нулевым вектором, не умаляя общности, T up 5 0,7то можно показать, что тогда нарушаются аксиомы «разумного» выбора.Другими словами, ЛПР предоставлена противоречивая информация.Определение 2.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
