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

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

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

Наиболее прямолинейным подходом к решению М. з. является сведение ее к обычной («однокритериальной») задаче математнч. программирования путем замены системы целевых функций на одну «сводную» функцию В ее роли могут выступать «взвешенные суммы»«взвешенные максимумы» и др. «свертки» исходных целевых функций. Такой подход концептуально и технически представляется самым удобным. Основным его недостатком является трудно выполнимое требование содержательной сопоставимости значений различных целевых функций, а также неопределенность (и нередко произвольность) в выборе функции Fи, в частности, «весов». Для их установления нередко рекомендуется прибегать к экспертным оценкам.

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

Полезное

Смотреть что такое «МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА» в других словарях:

Многокритериальная оптимизация — или программирование (англ. Multi objective optimization),[1][2] это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения. Задача многокритериальной оптимизации встречаются во… … Википедия

Березовский, Борис Абрамович — Борис Абрамович Березовский … Википедия

Березовский Б. — Борис Абрамович Березовский Депутат Государственной думы России … Википедия

Березовский Б. А. — Борис Абрамович Березовский Депутат Государственной думы России … Википедия

Березовский Борис Абрамович — Борис Абрамович Березовский Депутат Государственной думы России … Википедия

Борис Абрамович Березовский — Депутат Государственной думы России … Википедия

Еленин, Платон — Борис Абрамович Березовский Депутат Государственной думы России … Википедия

Платон Еленин — Борис Абрамович Березовский Депутат Государственной думы России … Википедия

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

Векторная оптимизация — [vector optimization] комплекс методов решения задач математического программирования, в которых критерий оптимальности представляет собой вектор, компонентами которого являются в свою очередь несводимые друг к другу критерии оптимальности… … Экономико-математический словарь

Источник

3. Многокритериальные задачи принятия решений

3.1. Математическая модель многокритериальной оптимизации

В теории многокритериальной оптимизации (МКО) решаются задачи принятия решений одновременно по нескольким критериям. Задача МКО ставится следующим образом: требуется найти числа , удовлетворяющие системе ограничений

, , (3.1)

для которых функции

, , (3.2)

достигают максимального значения.

Множество точек , удовлетворяющих системе (3.1),образует допустимую область . Элементы множестваназываютсядопустимыми решениями или альтернативами, а числовые функции ,–целевыми функциями, или критериями, заданными на множестве D. В формулировке задаче (3.1)-(3.2) присутствует целевых функций. Эти функции отображают множествов множество, которое называетсямножеством достижимости.

В векторной форме математическую модель МКО (3.1)-(3.2) можно записать следующим образом:

при . (3.3)

Здесь – вектор-функция аргумента.

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

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

Ввиду этого в теории МКО понятие оптимальности получает различные толкования, и поэтому сама теория содержит три основных направления:

1. Разработка концепции оптимальности.

2. Доказательство существования решения, оптимального в соответствующем смысле.

3. Разработка методов нахождения оптимального решения.

3.2. Оптимальность по Парето

Если функции достигают максимум в одной и той же точке, то говорят, что задача (3.3) имеетидеальное решение.

Случаи существования идеального решения в многокритериальной задаче крайне редки. Поэтому основная проблема при рассмотрении задачи (3.3) – формализация принципа оптимальности, т.е. определение того, в каком смысле «оптимальное» решение лучше других. В случае отсутствия «идеального решения» в задаче (3.3) ищется компромиссное решение.

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

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

Определение (оптимальность по Парето). В задаче МКО точка называется оптимальной по Парето, если не существует другой точки , которая была бы предпочтительнее, чем .

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

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

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

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

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

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

Источник

Методы решения многокритериальных задач выбора

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

К методам первой группы относятся метод свертки, метод главного критерия, метод пороговых критериев, метод расстояния. Следует отметить, что строгое обоснование этих методов отсутствует и их применение определяется условиями задачи и предпочтением ЛПР.

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

Аддитивная свертка (от англ. addition – сложение) имеет вид

т.е. наилучшим считается решение, которому соответствует максимум общего критерия на множестве альтернатив.

Мультипликативная свертка (от англ. multiplication – умножение) применяется в двух формах:

, (5.3.4) где – знак произведения. Первая из этих форм используется гораздо чаще, чем вторая. Наилучшее решение определяется выражением

Максминная свертка (выбор по наихудшему критерию) имеет вид

причем множитель не имеет значения, так как сравнение альтернатив выполняется в шкале порядка. Наилучшее решение определяется выражением (5.3.5). Подставив в (5.3.5) выражение (5.3.6), получим

поэтому эту свертку называют по основным операциям максиминной. Использование того или иного типа свертки отражает представление ЛПР о стратегии (способе достижения целей).

Метод пороговых критериев часто применяется в задачах обеспечения (удовлетворения), например при планировании и проектировании, когда ограничения задаются в виде

тогда наилучшее решение определяется выражением вида (5.3.5).

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

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

или с учетом веса критериев

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

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

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

Функция выбора по Парето определяется в виде

Функция локально-экстремального выбора записывается в виде

Функция оптимального выбора имеет вид

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

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

Существует значительное число модификаций ЧМ-процедур. Основными условиями при выборе той или иной процедуры являются имеющаяся у ЛПР информация о задаче и требования к точности решения. Обзор этих методов можно найти в [1, 2, 3, 4, 7].

Источник

Лекции по ТПР / Многокритериальные задачи

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

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

Полное и четкое описание цели множеством критериев является основой успешного решения поставленной задачи принятия решений.

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

1. Постановка и анализ задачи (проблемной ситуации)

2. Формулирование цели принятия

3. Формирование системы критериев оценки вариантов решения задачи

4. Генерирование вариантов решения задачи

5. Разработка или выбор методов и моделей оценки вариантов решения задачи по отдельным критериям

6. Оценка вариантов по отдельным критериям

7. Выбор наиболее предпочтительного варианта решения

8. Анализ выбранного варианта решения лицом, принимающим решение

9. Реализация выбранного решения

Рис.1.1. Этапы подготовки и принятия решений

Следовательно, постановку многокритериальной задачи предопределяет сам исследователь (ЛПР) из-за того, что не смог сформировать в математическом виде целевую функцию, а на этапе 7 он сталкивается с необходимостью решения многокритериальной задачи.

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

Примеры постановок многокритериальных задач из разных областей деятельности:

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

 Оценка качества продукции (технического уровня разработок) по множеству потребительских свойств. Следствием данной задачи является определение

цены на продукцию на основе потребительских свойств.

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

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

К ЛАССИФИКАЦИЯ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ

Первым признаком, по которому проведем классификацию многокритериальных задач, является характер решаемой МКЗ.

Исходными данными для дискретных МКЗ является матрица значений единичных

, размерности n m, строками которой являются объекты (варианты)

( i =l. n ), а столбцами – критерии k j ( j =l. m ).

Второй класс образует непрерывные многокритериальные задачи (НМКЗ), которые формулируются следующим образом:

Область определения параметров (переменных) A задается обычно в виде системы ограничений, например, в многокритериальных задачах линейного программирования

– система линейных неравенств.

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

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

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

b) задачи, в которых необходимо упорядочить многокритериальные объекты. Постановка многокритериальной задачи в таком виде чаще всего имеет место для дискретных МКЗ, например, упорядочить по предпочтению варианты технических систем, по качеству — образцы продукции;

d) задачи, в которых требуется выделить подмножество эффективных (конкурирующих) объектов. Такие подмножества называют оптимальными по Парето.

Чтобы говорить об эффективных объектах, надо ввести понятие доминируемого объекта.

чтительнее. Объект В i называют доминирующим, а В l – доминируемым.

Следует подчеркнуть, что прежде чем решать

дискретную задачу выделения наиболее предпочти-

тельного объекта, необходимо сначала выделить

подмножество эффективных объектов, так как иско-

мый объект может находиться только в этом под-

Для дискретных МКЗ выделение подмножества

эффективных объектов тривиально, так как доста-

точно исключить из исходного множества домини- 0 0

Рис.1.2. Выделение эффективных

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

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

b) вид требуемого решения. По этому параметру задачи ранжируются по сложности следующим образом:

оценка объектов (самая сложная задача); упорядочение объектов по предпочтению;

выделение наиболее предпочтительного объекта;

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

Пусть для дискретной МКЗ задана матрица значений критериев

чений каждого критерия проранжируем объекты (варианты), тем самым перейдем от

Для расчета коэффициента согласия вычислим сначала:

Коэффициент согласия определяется по формуле:

Данные поправки рассчитываются по формуле:

– число повторений ранга i, т.е. число объектов, у которых одинаковое значение

Коэффициент согласия изменяется в интервале [0;1]. Коэффициент Е равен единице, если по всем критериям объекты одинаково упорядочены. Это соответствует случаю, когда один из объектов (имеющий первый ранг по всем критериям) доминирует все остальные, объект с рангом 2 доминирует все последующие и т.д. В этом тривиальном случае автоматически выделяется наиболее предпочтительный объект, кроме того, все объекты упорядочиваются по предпочтению. Конечно, задачи, для которых коэффициент согласия близок к единице, являются простыми в решении и, напротив, задачи, для которых Е мало, более сложны.

Перечисленные характеристики объективно отражают сложность задач. Вместе с тем, сложность задачи зависит от субъективных факторов: насколько она правильно и точно понимается ЛПР, т.е. насколько оно подготовлено к ее решению. Успешно решать задачу может лишь ЛПР, хорошо знающее объект исследования, понимающее цель задачи (цель принятия решения), в противном случае не будет получено удовлетворительного результата.

П РОБЛЕМЫ РЕШЕНИЯ МКЗ

Основная проблема в решении МКЗ заключается в неоднородности пространства критериев, так как единичные критерии измеряются в различных единицах измерения. Поэтому в большинстве методов осуществляется переход от физических единиц к

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

Например, если некоторый критерий принимает одно и то же значение для всех рассматриваемых объектов (вариантов решений), то естественно считать, что данный критерий не информативен с точки зрения выбора решения, значит, важность такого критерия можно считать малой. В качестве меры информативности критерия рекомен-

Далее надо отметить проблему агрегирования множества критериев в скаляр. В большинстве методов эта проблема решается тем или иным способом, но в некоторых методах она снимается путем введения определенного принципа выбора наиболее предпочтительного объекта (решения).

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

Другой важной проблемой решения МКЗ является оценка доверия к получаемому решению. Дело в том, что при решении задач используется субъективная информация, поэтому у ЛПР возникает недоверие к результату.

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

Говоря об устойчивости решения МКЗ, необходимо сказать о взаимозависимости

устойчивости и взаимосвязи исходных данных для дискретных МКЗ (матрица значений единичных критериев по всем объектам). Если критерии статистически взаимосвязаны между собой (коэффициент множественной корреляции принимает большое значение), то, как указывалось ранее, задача будет простой, и, значит, результат будет более устойчив как по отношению к субъективным данным, так и по отношению к методам решения.

К ЛАССИФИКАЦИЯ МЕТОДОВ РЕШЕНИЯ МКЗ

Прежде чем переходить к методам, рассмотрим сначала подходы к решению МКЗ, каждый из которых характеризует класс методов.

Использование max-min-принципа выбора наиболее предпочтительного объекта. В

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

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

Источник