Пятая глава содержит исследование вопроса полноты набора количественной информации об относительной важности критериев. Здесь выясняется, что, используя лишь конечный набор информации об относительной важности критериев, можно получить в определенном смысле сколь угодно точное приближение к неизвестному множеству недоминируемых решений в виде Множества Парето некоторой новой многокритериальной задачи. Полученные результаты свидетельствуют о важной роли, которую играет информация об относительной важности критериев [c.13]
В этой главе вводятся и обсуждаются базисные понятия, связанные с принятием решений в многокритериальной среде множество возможных решений, векторный критерий и отношение предпочтения лица, принимающего решение. Дается постановка задачи многокритериального выбора. Кроме того, здесь определяются такие принципиально важные для дальнейшего изложения понятия, как множество недоминируемых решений и множество Парето, без которых невозможна формулировка и строгое обоснование принципа Эджворта-Парето. [c.15]
МНОЖЕСТВО НЕДОМИНИРУЕМЫХ РЕШЕНИЙ 25 [c.25]
Множество недоминируемых решений [c.25]
Множество недоминируемых решений. Как указано в разд. 1.1, решение задачи многокритериального выбора заключается в отыскании множества выбираемых решений Sel X. Выясним, каким образом сведения об отношении предпочтения могут быть использованы в процессе решения задачи многокритериального выбора. [c.26]
МНОЖЕСТВО НЕДОМИНИРУЕМЫХ РЕШЕНИЙ 27 [c.27]
Напоминаем, что здесь отношение предпочтения >х предполагается ир-рефлексивным и транзитивным. При этом заметим, что на самом деле для введения множества недоминируемых решений достаточно требовать от отношения предпочтения лишь свойства асимметричности. [c.28]
МНОЖЕСТВО НЕДОМИНИРУЕМЫХ РЕШЕНИЙ 29 [c.29]
Включение (1.2) устанавливает, что для достаточно широкого класса задач (а именно, для тех задач, для которых выполнена аксиома 1) выбор решений следует производить только среди недоминируемых решений. Кроме того, поскольку все последующие требования (аксиомы), предъявляемые к рассматриваемому здесь классу задач многокритериального выбора, как мы увидим далее, не содержат множества выбираемых решений (и выбираемых векторов), включение (1.2) показывает, что выбранным может оказаться любое подмножество множества недоминируемых решений. [c.29]
Когда Sel X 0 и множество недоминируемых решений состоит из единственного элемента, задача выбора в принципе решена, поскольку это единственное недоминируемое решение в силу включения (1.2) является выбираемым решением и остается только [c.29]
Наряду с множеством недоминируемых решений удобно ввести в рассмотрение множество недоминируемых векторов (недоминируемых оценок) [c.30]
Алгоритм построения множества недоминируемых решений. [c.30]
В предыдущем пункте была отмечена важная роль множества не доминируемых решений (и векторов) в теории принятия решений. Последующее изложение книги позволит еще не раз убедиться в справедливости этого высказывания. По этой причине следует иметь в распоряжении какой-нибудь метод или алгоритм построения множества недоминируемых решений (и векторов). [c.30]
В общем случае вопрос построения множества недоминируемых решений и/или векторов представляется чрезвычайно сложным, однако для конечного множества возможных решений (множества возможных векторов Y) он решается достаточно просто. [c.30]
МНОЖЕСТВО НЕДОМИНИРУЕМЫХ РЕШЕНИЙ 31 [c.31]
Первый шаг алгоритма нахождения множества недоминируемых решений заключается в последовательном сравнении первого решения х, со всеми остальными х2,..., хп. Это сравнение заключается в проверке справедливости соотношения X] >х х, и соотношения Xj ух х ПРИ каждом / = 2,. .., п. [c.31]
При выполнении второго соотношения xt >x xi удалению подлежит первое решение хь после чего сразу же следует перейти ко второму шагу. Если же ни одно из двух приведенных соотношений хх >х xi и >- х не является истинным, ничего удалять не нужно. В том случае, когда сравнения решения xL были проведены со всеми остальными решениями х2,. .-, х , и ни для какого i = 2,..., и не оказалось выполненным соотношение X/ >х хь первое решение следует запомнить как недоминируемое и удалить его из (оставшегося) множества возможных решений. Указанные действия описывают первый шаг алгоритма. [c.31]
Если после выполнения первого шага во множестве возможных решений не осталось ни одного решения (т. е. все оказались удаленными), то алгоритм заканчивает работу. При этом в памяти будет храниться одно не доминируемое решение хх. Оно и представляет собой множество недоминируемых решений. В противном случае (т. е. когда не все решения оказались удаленными), необходимо перейти ко второму шагу. [c.31]
Второй шаг полностью аналогичен первому. А именно, сначала нужно перенумеровать элементы множества Х2. После этого следует провести последовательное сравнение первого решения этого множества со всеми остальными его элементами. При этом сравнение осуществляется совершенно аналогично тому, как это было описано на первом шаге. Выполнение сравнений на втором шаге либо закончится удалением первого решения множества Хъ как доминируемого, либо такого удаления не произойдет. Во втором случае это решение следует запомнить как недоминируемое, а затем удалить его из множества Хг. Если после [c.31]
На каждом шаге алгоритма происходит удаление, по крайней мере, одного возможного решения. Следовательно, после выполнения некоторого конечного числа шагов будут удалены все возможные решения кроме некоторого одного и алгоритм закончит свою работу, так как оставшееся решение не с чем будет сравнивать и потому оно также будет недоминируемым. Это рассуждение доказывает конечность приведенного алгоритма. [c.32]
Применение описанного алгоритма к произвольному конечному множеству возможных решений за конечное число шагов приведет к отысканию, по крайней мере, одного недоминируемого решения. Действительно, недоминируемым запоминается лишь первое решение из множества, которое участвует в выполнении очередного шага алгоритма. Если на всех предыдущих шагах (кроме последнего) не было выявлено ни одного недоминируемого решения, то таковым должно быть последнее решение, поскольку его не может доминировать ни одно из всех остальных возможных решений. Тем самым, получен следующий результат. [c.32]
Чаще всего в практических задачах выбора отношение предпочтения задано лишь частично, либо вообще не задано и его следует построить прежде, чем приступать к решению задачи. В таких случаях схему приведенного выше алгоритма можно использовать для опроса ЛПР с целью выявления его отношения предпочтения и одновременного построения множества недоминируемых решений. Для этого ЛПР сначала предлагают выбрать предпочтительное решение из каждой пары, содержащей первое решение. При этом доминируемые решения, по мере их выявления, сразу [c.32]
Ранее уже говорилось о том, что результаты, связанные с недоминируемыми решениями и векторами и рассмотренные в предыдущем разделе, могут быть переформулированы применительно к множествам Парето. В частности, теорема 1.1 после такой переформулировки принимает следующий вид. [c.38]
Существо полученных здесь результатов можно выразить следующим образом информация об относительной важности критериев полна в том смысле, что только на ее основе для любой задачи определенного достаточно широкого класса можно с любой степенью точности определить неизвестное множество недоминируемых векторов (недоминируемых решений). Если же число возможных векторов конечно, то множество недоминируемых векторов может быть построено точно и полностью. Таким образом, научившись выявлять информацию об относительной важности, можно успешно находить множество недоминируемых решений и векторов, не привлекая информации никакого другого типа. [c.131]
Ниже будет показано, что для определенного класса задач многокритериального выбора нужно лишь научиться успешно извлекать и грамотно использовать информацию об относительной важности критериев. Этого вполне достаточно для того, чтобы, по крайней мере, теоретически получить сколь угодно точное представление о неизвестном множестве недоминируемых векторов (и недоминируемых решений). Такое положение свидетельствует о важной роли информации об относительной важности критериев в процессе принятия решений. [c.132]
Теоретическое обоснование описанного метода последовательного сужения множества Парето на основе количественной информации об относительной важности критериев приведено в пятой главе. Доказанная в ней теорема 5.3 утверждает, что во многих случаях, когда множество возможных векторов состоит из конечного числа элементов (это условие заведомо выполняется, если конечным является множество возможных решений), на основе конечного набора информации об относительной важности критериев, можно точно построить неизвестное множество недоминируемых векторов (а значит, и множество недоминируемых решений). К сожалению, этот результат не является конструктивным в том смысле, что в нем не указывается, какой именно набор информации следует при этом использовать. Неизвестно также, какое количество сообщений об относительной важности при этом нужно иметь. Решение этих вопросов в сильной степени зависит от конкретного вида множества возможных решений и участвующих в задаче выбора критериев. Тем не менее, эта теорема имеет важное теоретическое значение, поскольку она обосновывает описанный метод последовательного сужения множества Парето. По сути дела она утверждает, что при решении задач многокритериального выбора следует лишь научиться выявлять информацию об относительной важности критериев и умело ее использовать на основе только такой информации можно полностью и точно построить множество недоминируемых решений для произвольной задачи многокритериального выбора из достаточно широкого класса, в которой множество возможных решений конечно. Если же указанное множество не является конечным, то с помощью одной информации об относительной важности можно получить сколь угодно точное приближение к искомому множеству недоминируемых решений (см. теорему 5.2). Аналогичное утверждение справедливо не только для решений, но и для векторов. [c.159]
Таким образом, сужение множества приемлемых решений до множества эффективных решений осуществляется на основе анализа предпочтений. Решение называется эффективным, если не существует более предпочтительного. Множество эффективных решений в литературе называют также множеством Парето, множеством недоминируемых решений. Поэтому различают три последовательные стадии такого сужения следующим образом (рис. 12.43). [c.572]
Второе предположение означает, что местные органы, желая одновременно максимизировать выпуск и минимизировать загрязнения, согласны на достижение таких критериальных значений, которые оказываются недоминируемыми одновременно по обоим критериям никакими другими решениями задачи, т.е. преследуют получение оптимума по Парето. [c.21]
Вектор значений показателей / s s Gf называют эффективным (а также неулучшаемым, недоминируемым пли оптимальным по Парето), если не най-, дется другой такой точки множества G/, которая была бы не хуже / по всем показателям и превосходила его хотя бы по одному. На рис. 1.9 изображена одна из эффективных точек. В отличие от нее, точка I/ ,/а] не является эффективной, поскольку точка (/i,/al является более предпочтительной. Множество всех эффективных точек, которое принято называть эффективным множеством (а также недоминируемым множеством или множеством Парето), на рис. 1.9 выделено двойной линией. Те допустимые решения z, для которых /(z) принадлежит эффективному множеству, также принято называть эффективными. При анализе задачи многокритериальной оптимизации заранее можно утверждать лишь, что решение должно быть эффективным, но какое из эффективных решений должно быть выбрано — остается неясным. Для решения эт ого вопроса разрабатываются методы многокритериальной оптимизации, большинство из которых основывается на привлечении к исследованию человека или группы лиц, ответственных за принятие решения. Методы включения человека в исследования можно условно разбить на две большие группы. [c.60]
Множество недоминируемых решений ) обозначается Ndom X и определяется равенством [c.28]
Таким образом, Ndom X представляет собой определенное подмножество множества возможных решений X. В зависимости от вида множества Хи конкретного типа отношения предпочтения >-х множество недоминируемых решений может [c.28]
А Если предположить, что включение (1.2) для некоторого непустого множества Sel X не имеет места, то среди элементов этого множества найдется решение х" е Sel X, для которого выполнено соотношение х" g Ndom А7Тогда, по определению множества недоминируемых решений, существует такое решение х е X, что х >х х". Отсюда, используя аксиому 1, получаем х" g Sel X. Это противоречит начальному предположению о том, что х" — выбранное решение.V [c.29]
Лемма 1.4. При выполнении аксиом 2 3 множество недоминируемых решений Ndom X удовлетворяет включению [c.36]
А Пусть, напротив, для некоторого недоминируемого решения х е Ndom X выполнено соотношение х g P/(X). Тогда, по определению множества парето-оптимальных решений, существует такое возможное решение х е X, что/(х ) > f(x). На основании леммы 1.3 в условиях доказываемого утверждения справедлива аксиома Парето. Поэтому полученное неравенство, в силу аксиомы Парето, влечет соотношение х ух х, которое не совместимо с начальным предположением х е Ndom J. У [c.36]
Алгоритм нахождения множества Парето. Благодаря наличию указанной выше прямой связи между множествами недоминируемых и парето-оптимальных векторов все результаты, полученные ранее для первого множества, нетрудно переформулировать в терминах второго множества. В частности, для построения множества Pf X) (и Р(У)) в случае конечного множества возможных векторов Yможно применять сформулированный в предыдущем разделе алгоритм нахождения множества недоминируемых решений, заменив в нем сравнение по отношению пред-Почтения >х сравнением по отношению >, которое является иррефлексивным и транзитивным. [c.39]
Она имеет ненулевое неотрицатательное решение A j = A 2 - = ц2 = 0, А3 = Л = 0.5. Следовательно, выполняется соотношение у1 ум у2, а значит, вектор у2 не может входить в множество недоминируемых векторов Ndom Y. [c.128]
Случай конечного множества возможных оценок. Когда множество возможных векторов состоит из конечного числа элементов, для точного определения множества недоминируемых векторов (с конусным отношением, у которого конус К — открытый) достаточно располагать лишь определенным конечным набором информации об относительной важности критериев. Об этом свидетельствует следующая ниже теорема. Она имеет важное значение в рамках подхода, развиваемого в данной книге, поскольку теоретически обосновывает исключительную значимость теории относительной важности критериев в вопросах построения множества недоминируемых векторов (недоминируемых решений). В соответствии с этой теоремой, для задач многокритериального выбора определенного класса, используя лишь информацию об относительной важности критериев, можно гочно найти множество недоминируемых векторов (и недоминируемых решений). [c.143]
Пусть Н—М-решение в малом — дискриминирующее (рис. 4.26). Множество всех недоминируемых множеств А В дележей на рисунке заштриховано. Ограничимся рассмотрением необходимой добавки к А В для того, чтобы доминировались все дележи из треугольника KLM. Добавки для остальньрс треугольников описываются аналогичным образом. Ясно, что эта добавка должна сама находиться в треугольнике KLM. Уравнения наклонных сторон этого треугольника имеют вид i =а и 2 = 0. Возьмем в треугольнике KLM некоторую точку х с данными координатами i и 2 (рис. 4.27). Доминируемые ею дележи из этого треугольника составляют два параллелограмма (очерчены пунктиром). Следовательно, если два дележа принадлежат одной добавке до Н—М-решения, то соединяющий их отрезок должен составлять с вертикалью угол не более чем в 30°. В частности, каждая горизонталь может пересекать эту добавку не более чем в одной точке. Значит, вся эта добавка должна лежать на криволинейном отрезке, соединяющем точку L с основанием треугольника дележей и не отклоняющемся от вертикали более чем на 30°. Предположим, что одна из точек криволинейного отрезка не принадлежит добавке. По своему положению она не может доминироваться другими дележами добавки. Никакими дележами вне добавки она, очевидно, также доминироваться не может. Поэтому при сделанном предположении добавка оказывается недостаточной для получения Н—М-решения. Следовательно, каждая точка криволинейного отрезка должна на этой добавке принадлежать. [c.247]