Многокритериальные задачи

ЛЕКЦИЯ 9

МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ

Постановка задачи линейного программирования. Математическая модель задачи. Примеры задач линейного программирования. Графический метод решения задачи. Симплекс– метод решения задачи линейного программирования. Анализ решения задачи линейного программирования.

При анализе различных экономических проектов возникает задача выбора наиболее предпочтительного из них или нескольких предпочтительных проектов. Все проекты, рассматриваемые в этой задаче, можно условно назвать альтернативами. В качестве них могут выступать инвестиционные проекты, регионы, предприятия, товары, различные объекты и системы, сообщества и т.д.

Каждая из сравниваемых альтернатив характеризуются некоторыми показателями. Часть этих показателей выступает в качестве критериев при отборе альтернативы из множества других. Так, при оценке технического изделия основными критериями оценки служат его технические характеристики, а также такие качества, как надежность, эргономичность, внешний вид. При выборе кандидата на должность важнейшими критериями оценки являются квалификация, образование, эрудиция, возраст, коммуникабельность и т.п. В экономических задачах основными критериями служат экономическая эффективность и стоимость, при этом каждый из этих критериев, в свою очередь, может быть подразделен на более частные критерии. Считается, что

n показатели-критерии являются одноименными для всех альтернатив и их количество у всех альтернатив одинаковое;

n другие показатели альтернатив либо одинаковы, либо несущественны в данной задаче.

Если альтернативы оцениваются по m критериям, где m > 1, то такая задача принятия решений называется многокритериальной.

Рекомендуемые материалы

Критерий называется позитивным, если необходимо стремиться к его увеличению, и негативным, если необходимо стремиться к его уменьшению. В конкретных задачах принятия решений характер критерия устанавливается по содержательным соображениям. Преобразование негативного критерия в позитивный (и наоборот) можно осуществить заменой знака. При рассмотрении многокритериальных задач в общем виде, если не оговорено противное, предполагается, что все имеющиеся критерии являются позитивными. В многокритериальной задаче с позитивными критериями цель— получение альтернативы, имеющей как можно более высокие оценки по каждому критерию.

Поиск решения многокритериальной задачи не представляет особых сложностей, если предпочтение по одному критерию влечет за собой такое же предпочтение по другому критерию, т.е. критерии кооперируются. Например, такая ситуация имеет место, когда при покупке автомобиля преследуется цель купить престижный и красивый автомобиль. Очень часто эти два критерия совпадают, и престижный автомобиль является одновременно красивым.

Решение многокритериальной задачи также не представляет особых сложностей, если критерии нейтральны по отношению друг к другу, т.е. поиск решения по одному критерию никаким образом не отражается на поиске решения по другому критерию. Например, это имеет место, когда при покупке автомобиля мы преследуем цель купить надежный и красивый автомобиль.

Однако приведенные примеры являются частными случаями. В общем, сложность решения многокритериальных задач состоит в том, что критерии конкурируют друг с другом. В большинстве практических задач поиск более предпочтительного решения по одному критерию приводит к тому, что решение становится менее предпочтительным по другому критерию, т.е. решения несравнимыми между собой. Например, рассматривая стоимость и престижность в качестве критериев при покупке автомобиля, можно утверждать, что более дешевый (более предпочтительный по первому критерию) автомобиль является менее престижным (менее предпочтительным по второму критерию). Анализ таких ситуаций может быть осуществлен при помощи определения множества Парето.

Множество Парето

Предположим, что при оценке альтернатив использовались два критерия: стоимость (К₁) и надежность (К₂). Значения критериев для трех альтернатив представлены в таблице.

Очевидно, что альтернатива 3 является наиболее предпочтительной, так как она не хуже остальных альтернатив по всем критериям.

Альтернатива a_i является доминирующей по отношению к альтернативе a_k, если по всем критериям оценки альтернативы a_i не хуже, чем альтернативы a_k, а хотя бы по одному критерию оценка a_i лучше. При этом альтернатива a_k называется доминируемой. Из определения следует, что альтернатива 3 из приведенного выше примера является доминирующей по отношению к альтернативе 1 и альтернативе 2. Это можно увидеть из рис. 1, где альтернатива 3 занимает самое правое и верхнее положение по отношению к другим альтернативам.

Рассмотрим теперь альтернативы 1 и 2. Из рис. 1 также следует, что альтернативы 1 и 2 не находятся в отношении доминирования. Действительно, по стоимости предпочтительнее альтернатива 1, а по надежности - альтернатива 2. Эти альтернативы являются несравнимыми по отношению предпочтения между векторными оценками, так как их невозможно сравнить непосредственно на основе критериальных оценок. Множество несравнимых альтернатив образуют область эффективных решений и называется множеством Парето, а альтернативы, образующие это множество Парето-оптимальными. Если вернуться к примеру, то оставшиеся альтернативы 1 и 2 принадлежат множеству Парето.

Дать однозначный ответ на вопрос, какую же из Парето-оптимальных альтернатив следует считать оптимальной, для общего случая, не имея дополнительной информации о критериях, невозможно.

Общая методика исследования многокритериальных задач на основе математического моделирования может быть реализована в рамках одного из следующих подходов.

Первый подход. Для заданной многокритериальной задачи находится множество ее Парето-оптимальных альтернатив, а выбор конкретной альтернативы из множества Парето-оптимальных предоставляется принимающему решение.

Второй подход. Производится сужение множества Парето-оптимальных альтернатив (в идеале — до одной) с помощью некоторых формализованных процедур, что облегчает окончательный выбор альтернативы для лица, принимающего решение. Отметим, что такое сужение может быть произведено только при наличии дополнительной информации о критериях или о свойствах оптимального решения.

Рассмотрим некоторые простейшие способы сужения Парето-оптимального множества, акцентируя при этом внимание на необходимой дополнительной информации.

1. Указание нижних границ критериев. Набор оценок нижних границ по каждому критерию представляет собой дополнительную информацию. При указании нижних границ критериев оптимальной может считаться только такая Парето-оптимальная альтернатива, для которой оценка по каждому из критериев не ниже назначенной оценки. Это приводит к сужению Парето-оптимального множества.

При использовании этого способа окончательный выбор Парето-оптнмальной альтернативы производится из суженного Парето-оптимального множества принимающим решение (на основе субъективных соображений).

Основной недостаток метода состоит в том, что оптимальное решение становится здесь субъективным, так как зависит, во-первых, от величин назначаемых нижних границ критериев и, во-вторых, от окончательного выбора, совершаемого принимающим решение.

2. Субоптимизация. Субоптимизацию производят следующим образом: выделяют один из критериев, а по всем остальным критериям назначают нижние границы. Оптимальным при этом считается исход, максимизирующий выделенный критерий на множестве альтернатив, оценки которых по остальным критериям не ниже назначенных.

С помощью метода субоптимизации задача многокритериальной оптимизации превращается в задачу скалярной оптимизации на суженном допустимом множестве. Выделение одного из критериев, а также указание нижних границ для остальных критериев основано на дополнительной информации, получаемой от принимающего решение. Следовательно, окончательное решение здесь также имеет субъективный характер.

3. Лексикографическая оптимизация. Этот метод основан на упорядочении критериев по их относительной важности. После этого процедуру нахождения оптимального решения проводят следующим образом. На первом шаге отбирают исходы, которые имеют максимальную оценку по важнейшему критерию. Если такой исход единственный, То его и считают оптимальным. Если же таких исходов несколько, То среди них отбирают те, которые имеют максимальную оценку по следующему за важнейшим критерию и т. д. В результате такой процедуры всегда остается (по крайней мере, в случае конечного множества исходов) единственный исход — он и будет оптимальным.

Термин «лексикографический» отражает аналогию между этим методом и методом упорядочивания слов в словаре. При лексикографическом подходе требуется ранжирование показателей по важности, а значения показателей располагаются на шкале порядка. После того как важнейший показатель выбран, может быть определена альтернатива, имеющая наивысшее значение по этому показателю. Если такая альтернатива одна, то ее выбирают и процедура заканчивается. Если по определенному показателю имеется несколько альтернатив с одним и тем же наивысшим значением, то они сравниваются по второму по важности показателю. Процесс продолжается таким образом до тех пор, пока не будет выявлена единственная альтернатива, или пока не будут проверены все показа-ели.

Основными недостатками метода лексикографической оптимизации являются следующие.

n При практическом применении данного метода возникают трудности в установлении полной упорядоченности критериев по их относительной важности.

n Фактически при использовании этого метода принимается во внимание только первый — важнейший критерий. Например, следующий за ним по важности критерий учитывается только тогда, когда важнейший критерий достигает максимума в нескольких альтернативах.

Проиллюстрируем рассмотренные в этом пункте методы нахождения оптимального решения в многокритериальных ЗПР на следующем примере.

Пример. Выбор места работы. Предположим, что Вам предстоит выбрать место работы из девяти вариантов, представленных в табл. 5.1. В качестве основных критериев взяты: зарплата 3, длительность отпуска Д, время поездки на работу В. Так как критерий В имеет характер потерь, оценки по этому критерию берутся со знаком «минус». Какой вариант является оптимальным?

Решение. Выделим вначале Парето-оптимальные варианты. Здесь третий вариант доминирует на девятым:

шестой вариант доминирует на восьмым:

шестой вариант доминирует на вторым:

седьмой вариант доминирует на первым:

Других пар находящихся в отношении доминирования по Парето, нет. Отбрасывая доминируемые по Парето варианты {1,2,8,9}, получаем Парето-оптимальное множество {3, 4, 5, 6, 7}. При отсутствии информации об относительной важности рассматриваемых критериев, а также о каких-либо дополнительных свойствах оптимального решения дальнейшее сужение Парето-оптимального множества произвести нельзя. Поэтому формальный анализ заканчивается указанием Парето-оптимального множества и окончательный выбор оптимального варианта производится принимающим решение из этих пяти вариантов на основе каких-то дополнительных соображений.

Рассмотрим теперь второй подход, который приводит к сужению Парето-оптимального множества на основе дополнительной информации.

1. Указание нижних границ критериев. Наложим, например, следующие ограничения на оптимальное решение:

зарплата — не менее 600 руб;

длительность отпуска — не менее 30 дней;

время поездки — не более 40 мин.

Варианты, удовлетворяющие этим дополнительным ограничениям: {3,6,9}; из них оптимальными по Парето являются варианты 3 и 6. Остается сделать окончательный выбор между вариантами 3 и 6.

2. Субоптимизация. Пусть в качестве выделенного критерия выступает критерий зарплата; ограничения: длительность отпуска — не менее 30 дней, время поездки — не более 40мин. Отбросим варианты, которые не удовлетворяют данным ограничениям; остаются варианты: {2, 3, 5, 6, 9}. Из них максимальную зарплату имеет вариант 3. Этот вариант и будет оптимальным.

3. Лексикографическая оптимизация. Упорядочим критерии по относительной важности, например, следующим   образом: 3 " В " Д (т.е. важнейший критерий — зарплата следующий за ним по важности — время поездки, наименее важный критерий — длительность отпуска). Максимальное значение по критерию 3 имеют варианты 1 и 7. Далее сравниваем эти варианты по второму по важности критерию В. Так как время поездки для этих вариантов одинаково, переходим к третьему критерию Д; по критерию длительность отпуска лучшим является вариант 7, который и является здесь оптимальным.

Методы свертки критериев

Наиболее распространенным эвристическим приемом решения той или иной конкретной многокритериальной задачи является ее сведение к решению некоторой скалярной (однокритериальной) задачи, целевая функция которой чаще всего представляет собой определенную комбинацию имеющихся критериев К₁, К₂, . . ., К_m. Такой прием носит название скаляризации многокритериальной задачи. В зависимости от способа комбинирования имеющихся нескольких критериев в единый скалярный получаем тот или иной тип скаляризации, выбираемый исходя из существа решаемой задачи и наличия дополнительной информации о предпочтениях.

Линейная свертка частных критериев. Процесс скаляризации начинают с подбора коэффициентов линейной свертки, т.е. положительных чисел λ_i, i = 1, 2,..., m. Эти числа можно рассматривать как некие «веса» или «коэффициенты важности» соответствующих критериев. Более важному из них назначают больший коэффициент в линейной свертке критериев, а менее важному меньший. Эти коэффициенты и составляют дополнительную информацию о решаемой многокритериальной задаче.

Весовые коэффициенты обычно используются в нормированном виде и удовлетворяют равенству

l₁+l₂+…+l_m = 1

т.е. предполагается, что весовые коэффициенты неотрицательны. Каждый критерий умножается на свой весовой коэффициент, а затем все взвешенные критерии суммируются и образуют взвешенную целевую функцию, значение которой интерпретируются как "коэффициент качества" полученного решения. Полученная скаляризованная функция максимизируется на допустимой области ограничений. Найденное в итоге решение объявляется выбираемым (т.е. «наилучшим») решением.

Пример. В таблице представлены результаты оценки кандидатов на некоторую должность с использованием трехбалльной системы по двум критериям образование и опыт работы. Необходимо сделать выбор кандидата.

Решение. Векторные оценки кандидатов представим точками на координатной плоскости (по оси абсцисс откладываем значения критерия К₁, а по оси ординат — значения критерия К₂). Точки на рис. являются векторными оценками кандидатов. Из этого рисунка видно, что оптимальными по Парето являются кандидаты с номерами 1, 2, 5.

Рис. 1.

Полагаем, что l₁ = 0.4 и  l₂ = 0.6. Используя табл. 2, получим следующие оценки кандидатов:

О₁ = l₁К₁ + l₂К₂ = 0.4∙1 + 0.6∙3 = 2.2,

О₂ = l₁К₁ + l₂К₂ = 0.4∙2 + 0.6∙2 = 2,

О₅ = l₁К₁ + l₂К₂ = 0.4∙3 + 0.6∙1 = 1.8.

Отсюда можно заключить, что первый кандидат является наилучшим, так как О₁ > О₂ > О₃.

Линейная свертка основана на неявном постулате: "низкая оценка по одному критерию может быть компенсирована высокой оценкой по другому". Однако, этот постулат верен отнюдь не для всех моделей. Простейший пример - ухудшение качества изображения телевизора не может быть компенсировано качеством его звука.

Метод последовательных уступок

При решении многокритериальной задачи методом последовательных уступок вначале производится качественный анализ относительной важности частных критериев; на основании такого анализа критерии располагаются и нумеруются в порядке убывания важности, так что главным является критерий K₁, менее важен. K₂, затем следуют остальные частные критерии К₃, К₄ ..., K_n. Максимизируется первый по важности критерий K₁ и определяется его наибольшее значение Q₁. Затем назначается величина «допустимого» снижения (уступки) D₁>0 критерия K₁ и ищется наибольшее значение Q₂ второго критерия K₂ при условии, что значение первого критерия должно быть не меньше, чем Q₁– D₁. Снова назначается величина уступки D₂>0, но уже по второму критерию, которая вместе с первой используется при нахождении условного максимума третьего критерия, и т. д. Наконец, максимизируется последний по важности критерий K_n при условии, что значение каждого критерия К_s из n –1 предыдущих должно быть не меньше соответствующей величины Q_s– D_s. Получаемые в итоге альтернативы считаются оптимальными.

Метод последовательных уступок целесообразно применять для решения тех многокритериальных задач, в которых все частные критерии естественным образом упорядочены по степени важности.

При использовании метода последовательных уступок критерии предварительно упорядочивают по важности, а затем последовательно решают несколько оптимизационных задач (число задач равно числу критериев) в порядке убывания важности критериев.

Допустим, что первый критерий К₁ существенно важнее всех остальных, критерий К₂ намного важнее всех критериев, кроме К₁, критерий К₃ существенно важнее всех, кроме К₁ и К₂, и т. д., то естественно считать, что i-ое решение (альтернативу) лучше j-го решения (j-ой альтернативы), когда это i-ое решение лучше j-го по критерию К₁. Если i-oe и j-ое решения эквивалентны по К₁, то предпочтение отдается лучшему по критерию К₂, и т. д. Такое упорядочение называется лексикографическим, оно возможно лишь при значительной неравноценности критериев. В приводимой таблице дается пример такого упорядочивания пяти альтернатив А₁, .... A₅ по четырем критериям К₁, ..., К₄. В клетках — значения а_ij для i-ой альтернативы по j-му критерию.

Таблица 6. Результаты многокритериального оценивания

По каждому критерию хотим иметь максимум, К₁ — самый важный, К₄ — самый неважный.

Можно для каждого критерия сразу задать границу, за которую не должны выходить значения критерия, и искать оптимальное решение поочередно по каждому критерию, считая, что остальные укладываются в заданные границы (то есть практически сразу вводя дополнительные ограничения, которые могут появляться из каких-то соображений или решения оптимизационных задач, внешних по отношению к данной задаче). Иногда используют парные сравнения значений критериев.

Рассмотрим пример. Распространенным является следующий способ решения многокритериальных задач. Решают оптимизационную задачу с одним первым критерием, считая, что других критериев нет. Потом решают задачу с одним вторым критерием. И так далее. После выявления тех экстремальных уровней, которые в принципе достижимы по каждому критерию в отдельности, для каждого критерия, начиная с наиболее важного, задается порог, который не должен нарушаться. Затем считают условие нерушимости порога по первому критерию ограничением, решают задачу оптимизации для второго критерия, добавляют ограничения по порогу второго критерия, решают задачу для третьего критерия и т. д. Поясним сказанное примером.

Предприниматель покупает в одном месте мужские свитера (в количестве не более 60 штук), в другом — женские (не более 40 штук). С помощью мягкой щетки он делает начес и продает по 2 условные единицы за мужские и по 4 единицы за женские. За некоторый единичный интервал времени она может начесать не более 80 свитеров. Поскольку предприниматель хочет удержаться и на рынке мужских свитеров (пусть их индекс М), и на рынке женских свитеров (пусть их индекс Ж), постольку она интересуется не максимумом дохода или прибыли, а оценками сразу по нескольким критериям. Пусть закупочные цены в условных единицах таковы: мужские свитера по 1 ед/шт., женские по 2 ед/шт. Оптимизационная задача предпринимателя выглядит так (х_м, х_ж— объемы закупок):

На рисунке показана допустимая область, направления благоприятных изменений критериев К₁, К₂, К_з. Отдельно по каждому из критериев решения находятся сразу (по К₁: x_м = 60, К₁ = 120; по К₂: x_ж = 40, К₂ = 160; по К₃: x_м = х_ж = 0, К₃ = 0;). Зная значения критериев для однокритериальных задач, ситуацию на рынках и свои финансовые возможности, этот предприниматель выбирает такие пороги: П₁ = 100 (т.е. он хочет иметь К₁ ³ П₁ = 100), П₂ = 112 (хочет иметь К₂ ³ П₂ = 112) К₃ ³ П₃ = 120

Сначала он решает такую задачу: Решением будет х_ж = 30, К₂ =120 ³ 112

(что дает x_м ³50, х_ж ³ 28 с целевой функцией . Ясно, что решением будет х_м = 50, х_ж = 28 с К₃ =106 £ 120 = П₃, чем и завершится данная задача. Если бы было Пз ~ 95, то решения в данной задаче не существовало.

Важно, что каждый из способов работы со многими критериями возможен только при определенных условиях, в каких-то рамках. При решении многокритериальных задач появляются специфические проблемы, которых нет в однокритериальных задачах, и эти проблемы зачастую не удается до конца разрешить. Поэтому работа с многокритериальными задачами всегда трудна и требует высокой квалификации исследователя.

Метод идеальной точки

Точка а называется идеальной, если она оптимальна сразу по всем критериям. Как правило, такой точки не существует, но для каждой реальной альтернативы можно определить расстояние до идеальной точки и выбрать ту, для которой это расстояние минимально. Метод идеальной точки сводит исходную многокритериальную задачу к решению обычной однокритериальной задачи.

Пример. Из пяти предложенных проектов, характеристики которых даны в таблице, необходимо выбрать проект для вложения инвестиций. Из таблицы видно, что различные критерии оценки приводят к выбору различных проектов.

                                                                                                                                     Таблица 1

Т.о., каждый проект оптимален лишь по одному показателю оценки, что создает существенную неопределенность при выборе наиболее удачного варианта капитальных вложений.

Решение.

1. Для каждого показателя находим его максимальное значение. Эти значения соответствуют условному идеальному проекту.

2. Исходные значения показателей нормализуем по формуле:

где х_ij — нормализованные показатели эффективности j-го проекта;

а_ij — исходные показатели экономической эффективности проекта.

                                                                                                                Таблица 2

3. Для каждого анализируемого проекта находим рейтинговую оценку R_j:

где l₁, l₂, ... l_n — весовые коэфф. показателей, назначаемые экспертом.

Рейтинговая оценка проекта позволяет сравнить каждый показатель экономической эффективности проектов с условным эталонным проектом, имеющим наилучшие результаты по всем сравниваемым показателям.

                                                                                                             Таблица 3

Проведенный анализ существенно уменьшил неопределенность в принятии инвестиционного решения и показал, что наиболее эффективным из предлагаемых проектов капиталовложений является проект III.