Вы здесь

Сужение множества Парето на основе взаимно зависимой информации об отношении предпочтения ЛПР

Автор: 
Климова Ольга Николаевна
Тип работы: 
Кандидатская
Год: 
2009
Артикул:
322424
129 грн
(417 руб)
Добавить в корзину

Содержимое

Содержание
Введение.................................................................3
Глава 1. Сужение множества Парето на основе простейшего набора взаимно зависимой информации....................................................XI
1.1. Основные понятия теории многокритериального выбора и относительной важности критериев....................................11
1.2. Учёт непротиворечивости простейшего набора взаимно зависимой информации..........................................................16
1.3. Сужение множества Парето на основе взаимно зависимой информации об отношении предпочтения ЛИР.......................................29
1.4. Учёт взаимно зависимой информации в случае нечеткого отношения предпочтения........................................................41
Глава 2. Сужение множества Парето с использованием различных наборов взаимно зависимой информации............................................57
2.1. Учёт непротиворечивости различных наборов взаимно зависимой информации..........................................................57
2.2. Сужение множества Парето на основе различных наборов взаимно зависимой информации об отношении предпочтения ЛИР..................62
2.3. Инвариантность результатов теоремы 2.1 и теоремы 2.4 относительно линейного положительного преобразования.............................81
2.4. Учёт взаимно зависимой информации с использованием нелинейных функций минимума....................................................85
Глава 3. Задача выбора оптимального химического состава судостроительной
стали..................................................................102
Заключение.............................................................107
Литера гура............................................................109
2
Введение
Задачи выбора наилучшего решения широко представлены в различных областях техники и экономики.
В тех случаях, когда решения оцениваются по одному критерию, наилучшим считается го, которому соответствует максимальное значение данного критерия. Но, как правило, задачи выбора являются многокритериальными, т.е. имеющиеся альтернативы оцениваются сразу по нескольким критериям. Сложность подобных задач заключается в невозможности достижения наилучших значений по всем кри териям одновременно.
Многокритериальные задачи выбора являются предметом изучения теории принятия решения, призванной помочь лицу, принимающему решение (ЛПР) выбрать наилучшее решение из множества имеющихся альтернатив.
13 настоящее время не существует единого подхода к решению многокритериальных задач. Но какой бы метод не применялся, как правило, на первом этапе происходит выделение множества Парето из множества всех вариантов. Используемый при этом принцип Парето заключается в том, чтобы исключить из множества возможных решений те варианты, которые могут' быть улучшены по всем параметрам.
К сожалению, выделенное множество Парето оказывается достаточно широким, тогда как перед лицом, принимающим решение, стоит задача выбрать одну наилучшую или сравнительное небольшое множество наилучших альтернатив. В связи с этим и возникает так называемая «проблема сужения множества Парето».
К настоящему времени разработано множество различных эвристических подходов к решению данной проблемы. Формально данные подходы можно разделить на несколько групп.
Первую группу составляют методы, основанные на формировании обобщенного критерия с последующей его максимизацией |21].
Наиболее распространенный и самый простой обобщенный критерий - это
т
линейная свертка Ф(х) = /,(*), где /,(*),—,/«(*) набор критериев, а
некоторые положительные числа, характеризующие важность критериев.
3
Принимается, что чем большее значение принимает целевая функция Ф(Х), тем лучше решение, соответствующее ей.
Автором, впервые предложившим использовать линейную свертку для решения задач многокритериального выбора, считается французский ученый XVII века Ж. Ш. Борда [1]. В России же одним из первых, кто применил линейную свертку, был инженер-корабел А Н. Крылов [331.
Одним из недостатков данного подхода является то, что веса Л, не имеют
точного определения. Поэтому каждое лицо, которое назначает их, будет вкладывать в них свое собственное понимание, возможно, отличное от представления других. Другой недостаток состоит в следующем. Согласно принципу Эджворта-Парето, выбранным может быть любое парсто-оптимальное решение, тогда как при максимизации линейной свертки может быть получено не каждое парето-оптимальное решение. Это означает, что какие-то решения, имеющие основания быть выбранными, в силу использования данного подхода, никогда не будут выбраны. К тому же не для любого класса многокритериальных задач допустимо использование обобщенного критерия [9, 17].
Вообще говоря, на основе каждого из существующих необходимых и достаточных условий парето-оптимальности можно построить обобщенный критерий определенного вида. Наилучшим решением обычно считается то, которому соответствует максимальное значение этого критерия.
К известным методам, основанным на применении обобщенного критерия можно причислить метод анализа иерархий (T.JT. Саати (30, 43J), процедуры теории полезности Multi-Attribute Utility Theory (P.JI. Кини и X. Райфа [3], О.И. Ларичев [4]), методы целевого программирования [34, 35, 36,44].
В следующей группе подходов ЛПР предлагается в качестве своего отношения предпочтения выбрать уже известное заранее отношение предпочтения >- v. После чего поиск наилучшего решения производиться во множестве доминируемых
D(X) = {-V* | V х е Х,х *х*:х Ух jc*} или недоминируемых вариантов
N(X) = {x*\3x<=X:x>-x х*}.
4
Одним из ранних примеров использования этого подхода является правило голосования Кондорсе [1]. Также к данной группе можно отнести известные методы ELECTRE (Б. Рой), MACBETH (Дж. Бранс) и другие [4, 36].
Положительной стороной данного подхода является изученность свойств используемого отношения предпочтения. Однако, большинство из существующих в настоящее время «искусственных» отношений достаточно сложны в своем задании, что делает затруднительным для ЛПР выбор того отношения предпочтения, которое ему наиболее подходит. Кроме того, множество доминируемых вариантов, внутри которого следует искать наилучшее решение, зачастую оказывается пустым, а множество недоминируемых вариантов едва отличающимся от исходного множества возможных решений. Еще одним существенным недостатком является то, что данные процедуры эвристичны и, используя различные отношения предпочтения при решении одной и той же задачи, будут получаться различные оптимальные решения.
Другую группу составляют так называемые интерактивные (человеко-машинные) процедуры, впервые предложенные в работе [37].
На каждом шаге гакой процедуры ЛПР должен предоставить определенную информацию, на основе которой строится последовательность точек. Если данная последовательность сходится, то ее предел считается наилучшим решением [34, 36]. В настоящее время разработано множество интерактивных методов, основанных на визуализации множества Парето и приближении к наилучшему вектору при помощи информации, выявляемой у ЛПР (Лотов A.B. [39]).
Одной из главной проблем описанного подхода является многократное в ходе решения задачи использование информации, получить которую от ЛПР сложно, а порой и невозможно.
Общим признаком для всех упомянутых выше подходов является отсутствие возможности описать тот класс задач, в которых использование данных подходов гарантированно приведет к выбору наилучшего решения. Вследствие чего, теоретическая ценность данных подходов снижается и проблема сужения множества Парето по-прежнему остается актуальной.
Еще одну группу составляют методы, в основе которых лежит использование свойств отношения предпочтения. Среди таких свойств выделяются
5
асимметричность, транзитивность, различные типы инвариантности отношения предпочтения [5, 11,20, 32].
Когда значения критериев измеряются в качественных шкалах, то для сужения области поиска наилучшего решения может оказаться полезным использование свойства независимости критериев по предпочтению [4]. Два критерия /, и /2 независимы по предпочтению от других критериев если предпочтения
между альтернативами, различающимися лишь опенками по первому и второму критериям, не зависят от фиксированных значений по другим критериям.
Часто для сужения множества Парето используется дополнительная информация о важности критериев для ЛПР [21]. В ряде случаев вводится поня тие качественной важности критериев [22-27]. Она заключается в следующем. Пусть имеется набор критериев У|,и две векторные оценки У = ,
у" - (у\у/*), которые отличаются лишь /'-ой и у-ой компонентами, причем УІ =у* > у" = у'г Если при выборе между векторами у' и у9 ЛПР предпочтет первый вектор, то говорят, что /-й критерий важнее у-го критерия. Недостатком использования дайной информации является то, что она позволяет лишь незначительно сузить множество Парето. В то время как введение понятия количественной информации об относительной важности критериев [16, 19, 40, 41] дает возможность более существенно сужать множество Парею. Пусть У1 = (У\і—>/т) и У" ~ ІУЇ>-чУт) " Два парето-оптимальных вектора. Причем первый вектор превосходит второй по всем компонентам, соответствующим группе критериев А, а второй превосходит первый по всем компонентам, соответствующим группе критериев В, т.е. имеет место
Уі“Уі-п,> 0 УієЛ; у]-у)=™]> 0 УуєЯ; = У*є/\{ЛиВ).
В этом случае выбор первого вектора в пользу второго, означает, что ЛПР готово пойти на потери по каждому менее важному критерию /, (у е В) в размере
иУ, ради получения прибавки в размере по каждому более важному критерию f
(/є А). Данная информация выражает готовность ЛІІР идти на компромисс в ходе принятия решения, в результате которого и становится возможным сужение множества Парето.
6
Использование описанной выше информации об отношении предпочтения ЛПР лежит в основе аксиоматического подхода, в рамках которого предполагаются выполненными несколько аксиом, характеризующих «разумный» выбор ЛПР [10,
12-15, 18]. В частности, в них накладываются следующие требования на отношение предпочтения: вариант, не выбираемый из пары вариантов, не выбирается и из всего множества выбираемых решений; отношение предпочтения транзитивно, отношение предпочтения согласовано с критериями; отношение предпочтения инвариантно относительно линейного положительного преобразования.
Введение данных аксиом, во-первых, гарантирует правомерность использования принципа Эджворга-Парето; во-вторых, позволяет производить более значимое, а главное - обоснованное сужение множества Парето.
Согласно аксиоматическому подходу, процесс сужения происходит в несколько этапов. Сначала выявляется информация об отношении предпочтения в форме относительной важности критериев. Следующим этапом менее важный критерий заменяется новым, вычисленным по определенным формулам. На третьем этапе решается задача многокритериального выбора с исходным множеством возможных решений, но уже с новым векторным критерием. Полученное в результате решения этой задачи новое множество Парето оказывается уже первоначального множества Парето, и тем самым представляет собой более точную оценку сверху для неизвестного множества выбираемых решений. Следует отметить, что в рамках данного аксиоматическою направления не накладывается никаких ограничений на множество выбираемых решений и векторный критерий.
Данная диссертационная работа лежит в русле описанного выше аксиоматического подхода и представляет собой его дальнейшее развитие.
Объектом исследования являются задачи многокритериального выбора, включающие в себя множество возможных решений, числовой векторный критерий и бинарное отношение предпочтения. Предметом исследования является процесс учета взаимно зависимой информации [8, 16] об отношении предпочтения ЛПР в задачах многокритериального выбора.
Простейшим примером взаимно зависимой информации является случай, когда один критерий важнее другого, а тот, в свою очередь важнее первого. Информация
7
подобного рода на практике возникает довольно часто, поэтому представляет собой не только теоретический, но практический интерес.
Цель данной работы заключается в получении правил сужения множества Парето в задачах многокритериального выбора при наличии набора взаимно зависимой информации об отношения предпочтения ЛПР. Для достижения поставленной цели необходимо было решить следующие задачи:
- получить критерии непротиворечивости набора взаимно зависимой информации об отношении предпочтения ЛПР;
- получить формулы для вычисления нового векторного критерия, на основе которого может быть построена оценка сверху для неизвестного множества выбираемых решений более точная, чем множество Парето.
В качестве теоретических методов исследования был использован аппарат выпуклого анализа [28, 31], теории бинарных отношений и линейной алгебры [2]. Теоретические положения и выводы сформулированы в виде лемм и теорем, и доказаны математическими средствами.
Теоретическая значимость работы заключается в получении новых правил сужения множества Парето при наличии взаимно зависимой информации об отношении предпочтения ЛПР.
Практическая значимость работы состоит в возможности использования полученных результатов для обоснованного сужения множества Парето при решении различных многокритериальных задач из области техники и экономики.
Основные результаты работы докладывались и обсуждались на 37-й и 40-й международных конференциях студентов и аспирантов «Процессы управления и устойчивость» (Санкт-Петербург, 2006, 2009), на 5-й Московской международной конференции по исследованию операций (Москва, 2007), а также на 13-й Всероссийской конференции «Математические методы распознавания образов» (Зеленогорск, 2007).
Первая глава посвящена проблеме сужения множества Парето на основе простейшего типа взаимно зависимой информации об отношении предпочтения ЛПР.
В начале главы приводятся основные понятия задачи многокритериального выбора. Предполагаются выполненными четыре аксиомы «разумного» выбора.
8
Затем последовательно формулируются две задачи многокритериального выбора с различными наборами взаимно зависимой информации.
Первая трехкритериальная задача содержит информацию вида: группа
критериев {/,/2} важнее критерия с наборами положительных параметров {м\ууу2} и м'з, а критерий /3, в свою очередь, важнее группы критериев {/^/2} с наборами положительных параметров у3 и {у,,у2}. Во второй задаче векторный критерий содержит четыре элемента и взаимно зависимая информация представлена уже двумя наборами: группа критериев {/,,/2} важнее критерия /3 с наборами положительных параметров {и'[,и>£} и и-', а критерий в свою очередь, важнее группы критериев {/|,/2} с наборами положительных параметров у3 и \у\,у'г)\ критерий / важнее критерия /4 с наборами положительных параметров и'", м>”, а критерий /, важнее критерия с наборами положительных параметров
?;> уг
Информация, полученная от ЛПР, может быть в некотором смысле не согласованной, т.е. содержать противоречивые сведения о предпочтениях ЛПР. В связи с этим, проводится подробный анализ взаимно зависимой информации на непротиворечивость и доказываются критерии, выполнение которых гарантирует непротиворечивость взаимно зависимой информации.
В доказанных теоремах для каждой из рассматриваемых задач приводятся правила того, как следует производить учет набора взаимно зависимой информации с целью сужения множества Парето. Для этого необходимо решить новую задачу многокритериального выбора на прежнем множестве выбираемых решений, но уже с новой векторной функцией. Множество Парето, полученное в новой задаче, и будет представлять собой оценку сверху для множества выбираемых решений более точную, чем множество Парето исходной задачи.
На практике предпочтения ЛПР нередко имеют расплывчатый, нечеткий характер. ЛПР может лишь с определенной степенью уверенности заявить, что одно решение для него предпочтительнее другого и что одна группа критериев важнее другой. Поэтому практический интерес представляет то, каким образом учитывается набор взаимно зависимой информации в случае нечеткого отношения
9