Многоцелевые модели принятия решений

Многоцелевые модели принятия решений Процесс принятия решений актуален в силу того, что все больше расширяются масштабы, количество элементов и взаимосвязей подсистем в организационных системах. Усложнение связей между элементами системы вызывает неопределенность в знании реальной структуры системы, что может быть связано с так называемым человеческим фактором, умышленным или специальным искажением информации и т.д. В отличие от одномерных (однокритериальных) задач многомерные (многокритериальные) задачи возникают в ситуации, когда или существует общая цель, выразить которую одним критерием трудно, или существуют различные точки зрения, которые неизбежно нужно учитывать. Прикладной целью применения данного типа задач является также нахождение согласия между представителями с различными ценностями, интересами, суждениями, целями, приоритетами, поскольку здесь, так же как и в большинстве проблем реального мира, мы сталкиваемся с несовместимыми целями, что вызывает необходимость в компромиссе. Однако почти все математические методы оптимизации предназначены для нахождения экстремума одной функции - т.е. для одной цели. Поэтому чаще всего пытаются свести многоцелевую задачу к одноцелевой. Эта процедура в большинстве случаев приводит к серьезному искажению существа проблемы и, следовательно, к неоправданной замене одной задачи другой. Априорные процедуры многоцелевой оптимизации и соответствующие им методы принятия решения В процедурах априорного типа делается явное или неявное предположение, что вся информация, позволяющая определить наилучшее решение, скрыта в формальной модели задачи и, следовательно, с помощью некоторых преобразований может быть из этой формальной модели извлечена и использована. Иначе: полагаем, что • множества альтернатив U • и целевых функций W1(u), W2(u), ... вполне достаточно для объективного, не зависящего от отсутствующих в данной модели факторов, определения оптимального решения. Метод главной компоненты Заключается в том, что критерий качества связывается с одним из показателей, выбранных в роли основного (главного). На основные показатели накладываются ограничения. В этом случае: • по главному показателю реализуется критерий оптимальности, • по остальным – пригодности. Например, предположим, имеется вектор полезного эффекта в виде , где – компоненты вектора, например, для машины: производительность, экологичность, надежность, себестоимость и т.д. Тогда метод главной компоненты заключается в произвольном выборе одного из компонентов в качестве главного, по которому производится оптимизация и выбирается решение. При этом остальные компоненты переводятся в разряд ограничений. Этот метод прост, нагляден и часто применяется, например, в машиностроительной практике, однако принципиальным его недостатком является произвол в выборе главного критерия. Метод уступок Применяется для задач, у которых критерии не равнозначны. Прежде чем решать поставленную задачу по методу уступок, необходимо: • расположить критерии по их значимости (наиболее важный – считается первым); • отыскать оптимальное значение W1* целевой функции W1 ; • сделать уступку по первому показателю эффективности, т.е. ухудшить величину W1* до значения W1**=k1W1*; • ввести в задачу дополнительное ограничение W1і =W1**; • отыскать оптимальное значение W2* целевой функции W2 ; • сделать уступку по второму показателю эффективности, т.е. ухудшить величину W2* до значения W2**=k2W2*; • ввести в задачу дополнительное ограничение W2і =W2**; • новую задачу с двумя дополнительными ограничениями решить по третьему показателю эффективности и т.д.; Процесс решения задачи заканчивается, когда решение будет получено по всем показателям. Окончательный план и будет наиболее рациональным - получено оптимальное значение наименее важного критерия при условии гарантированных значений предшествующих показателей эффективности. Метод Гермейера (принцип равномерной оптимальности) Пусть каждый критерий Wi(u) характеризует некоторый показатель изделия альтернативы u – материалоемкость, трудозатраты, грузоподъемность, надежность, устойчивость, экологичность и т.д. Наилучшая альтернатива, по-видимому, характеризуется наиболее удачным сочетанием всех этих показателей качества, т.е. имеет максимальное значение "глобального" качества. Таким образом, для выбора наилучшей альтернативы достаточно уяснить, каким образом глобальное качество зависит от единичных показателей качества, после чего многоцелевая задача может быть сведена к задаче скалярной оптимизации с использованием функции вида: где λi – коэффициент значимости i-го показателя качества. Обычно Этот метод можно применять, если достаточно точно известны λi. Обычно λi определяются с помощью метода экспертных оценок или на основании хорошо апробированных статистических данных. Основная трудность заключается в способе назначения коэффициентов значимости. Обычно для их определения используют экспертные методы. Поэтому в ряде ситуаций может употребляться модель, в которой глобальное качество альтернативы представляет собой сумму единичных показателей (принцип равномерной оптимальности): Этой моделью пользуются в задачах, в которых критерии имеют одну и ту же единицу измерения (как правило, стоимостную). Основным недостатком принципа равномерной оптимальности является невозможность компенсации недопустимо малых значений некоторых критериев достаточно большими значениями других. Апостериорные процедуры многоцелевой оптимизации и соответствующие им методы принятия решения В основе апостериорных процедур лежит предположение, что формальная модель многоцелевой задачи не содержит информации, достаточной для однозначного выбора наилучшей альтернативы. Следовательно, решения, принимаемые с помощью апостериорных процедур, имеют принципиально субъективный характер, что предопределяет необходимость привлечения субъективных суждений конструктора. Учет предпочтений субъекта в этом случае является одним из наиболее эффективных методов снятия имеющейся неопределенности. Апостериорные процедуры принятия решений заключаются в формулировке дополнительных требований, накладываемых на предпочтения субъекта, выполнение которых позволяет однозначно восстановить некоторую скалярную функцию полезности P(u), после чего задача принятия решений сводится к скалярной оптимизации. Типичная структура апостериорной процедуры решения многокритериальных задач такова. Сначала выполняется проверка гипотезы о независимости по полезности. Если ответы субъекта позволяют сделать вывод, что независимость действительно имеет место, то с помощью специальных методов (часто используется принцип лотереи) восстанавливаются все величины, необходимые для идентификации искомой функции полезности. Основным достоинством апостериорных процедур – по сравнению с априорными – является четкое определение условий, при выполнении которых ими можно пользоваться. Но их практическое использование часто наталкивается на необходимость сбора чрезвычайно большого количества информации, а также на то, что субъект (конструктор) во многих случаях либо не может дать информацию, необходимую для реализации процедуры, либо дает ее с большими ошибками. Это связано, как правило, с неподготовленностью субъекта к решению такого рода задач. Адаптивные процедуры многоцелевой оптимизации и соответствующие им методы принятия решения Как известно, в кибернетике под адаптацией понимается «…процесс накопления и использования информации в системе, направленный на достижение определенного, обычно оптимального в некотором смысле состояния или поведения системы при начальной неопределенности или изменяющихся внешних условиях». Из приведенного определения можно сформулировать некоторые общие принципы адаптации: • адаптация представляет, как правило, непрерывный динамический управляемый случайный процесс; • в процессе адаптации управление процессом должно быть оптимальным по какому-либо одному или нескольким критериям (показателям). В процессе адаптации (адаптивного управления) могут меняться: • параметры, • структура системы, • алгоритм функционирования, • управляющие воздействия и т.д. Как известно, процесс оптимального проектирования может интерпретироваться в виде задачи оптимального управления. Поэтому к нему могут быть полностью применены как общие принципы, так и методы адаптации. Метод анализа иерархий Метод анализа иерархий (МАИ) – методологическая основа для решения задач выбора альтернатив посредством их многокритериального рейтингования. Метод анализа иерархий создан американским ученым Т. Саати и вырос в настоящее время в обширный междисциплинарный раздел науки, имеющий строгие математические и психологические обоснования и многочисленные приложения. Возможности метода 1. Метод позволяет провести анализ проблемы. При этом проблема принятия решения представляется в виде иерархически упорядоченных: a) главной цели (главного критерия) рейтингования возможных решений, b) нескольких групп (уровней) однотипных факторов, так или иначе влияющих на рейтинг, c) группы возможных решений, d) системы связей, указывающих на взаимное влияние факторов и решений. Предполагается, так же, что для всех перечисленных «узлов» проблемы указаны их взаимные влияния друг на друга (связи друг с другом). 2. Метод позволяет провести сбор данных по проблеме. В соответствие с результатами иерархической декомпозиции модель ситуации принятия решения имеет кластерную структуру. Набор возможных решений и все факторы, влияющие на приоритеты решений, разбиваются на относительно небольшие группы – кластеры. Разработанная в методе анализа иерархий процедура парных сравнений позволяет определить приоритеты объектов, входящих в каждый кластер. Для этого используется метод собственного вектора. Итак, сложная проблема сбора данных разбивается на ряд более простых, решающихся для кластеров. 3. Метод позволяет оценить противоречивость данных и минимизировать ее. С этой целью в методе анализа иерархий разработаны процедуры согласования. В частности, имеется возможность определять наиболее противоречивые данные, что позволяет выявить наименее ясные участки проблемы и организовать более тщательное выборочное обдумывание проблемы. 4. Метод позволяет провести синтез проблемы принятия решения. После того, как проведен анализ проблемы и собраны данные по всем кластерам, по специальному алгоритму рассчитывается итоговый рейтинг – набор приоритетов альтернативных решений. Свойства этого рейтинга позволяют осуществлять поддержку принятия решений Например, принимается решение с наибольшим приоритетом. Кроме того, метод позволяет построить рейтинги для групп факторов, что позволяет оценивать важность каждого фактора. 5. Метод позволяет организовать обсуждение проблемы, способствует достижению консенсуса. Мнения, возникающие при обсуждении проблемы принятия решения, сами могут в данной ситуации рассматриваться в качестве возможных решений. Поэтому метод анализа иерархии можно применить для определения важности учета мнения каждого участника обсуждения. 6. Метод позволяет оценить важность учета каждого решения и важность учета каждого фактора, влияющего на приоритеты решений. В соответствии с формулировкой задачи принятия решения величина приоритета напрямую связана с оптимальностью решения. Поэтому решения с низкими приоритетами отвергаются как несущественные. Как отмечено выше, метод позволяет оценивать приоритеты факторов. Поэтому, если при исключении некоторого фактора приоритеты решений изменяются незначительно, такой фактор можно считать несущественным для рассматриваемой задачи. 7. Метод позволяет оценить устойчивость принимаемого решения. Принимаемое решение можно считать обоснованным лишь при условии, что неточность данных или неточность структуры модели ситуации принятия решения не влияют существенно на рейтинг альтернативных решений. Определение иерархической структуры Иерархическая структура – это графическое представление проблемы в виде перевернутого дерева, где каждый элемент, за исключением самого верхнего, зависит от одного или выше расположенных элементов. Часто в различных организациях распределение полномочий, руководство и эффективные коммуникации между сотрудниками организованы в иерархической форме. На Рис.1 приведена схема классификатора, организованного по иерархическому принципу. Иерархия вообще — это такое построение системы из подсистем, когда каждой подсистеме приписывается определенное целое число, называемое ее уровнем, причем взаимодействие подсистем существенно зависит от разности их уровней, подчиняясь некоторому общему принципу. Рис. 1. Иерархия классификаторов Уровень – группа всех однотипных (равноправных, однородных, гомогенных и т.п.) узлов. Название уровня отражает назначения, функцию группы узлов в ситуации принятия решения. Каждый узел определяется не только своим названием, но и названием уровня, которому он принадлежит. Ясно, что отдельный уровень образуют альтернативные решения (узлы этого уровня однотипны в том смысле, что они являются решениями; прочие узлы таковыми не являются). Главный критерий рейтингования, как правило, один – это отдельный уровень. На рейтинг оказывают влияние несколько групп факторов – это также уровни. Иерархический принцип организации структуры возможен только в многоуровневых системах (это большой класс современных социальных и технических систем). Заключается в упорядочении взаимодействий между уровнями в порядке от высшего к нижнему. Каждый уровень выступает как управляющий по отношению ко всем нижележащим и как управляемый, подчиненный, по отношению к вышележащему. Каждый уровень специализируется также на выполнении определенной функции. Абсолютно жестких иерархий не бывает, часть систем нижних уровней обладает меньшей или большей автономией по отношению к вышележащим уровням. В пределах уровня отношения элементов равны между собой, взаимно дополняют друг друга, им присущи черты самоорганизации (закладываются при формировании структуры). В простых системах иерархия не требуется, так как взаимодействие осуществляется по непосредственным связям между элементами. В сложных системах непосредственные взаимодействия между всеми элементами невозможны (требуется слишком много связей), поэтому непосредственные контакты сохраняются лишь между элементами одного уровня, а связи между уровнями резко сокращаются. (Рис.2) Рис. 2. Типичный вид иерархической системы Расстановка приоритетов Приоритеты — это числа, которые связаны с узлами иерархии. Они представляют собой относительные веса элементов в каждой группе. Подобно вероятностям, приоритеты — безразмерные величины, которые могут принимать значения от нуля до единицы. Чем больше величина приоритета, тем более значимым является соответствующий ему элемент. Сумма приоритетов элементов, подчиненных одному элементу выше лежащего уровня иерархии, равна единице. Приоритет цели по определению равен 1.0 (на рисунке 1.000 – десятичная точка). На рис. 3 показана иерархия, в которой приоритеты всех элементов не устанавливались лицом, принимающим решение (ЛПР). Рис. 3. Простейшая иерархическая структура МАИ с приоритетами, определенными по умолчанию В таком случае по умолчанию приоритеты элементов считаются одинаковыми, то есть все четыре критерия имеют равную важность с точки зрения цели, а приоритеты всех альтернатив равны по всем критериями. Другими словами, альтернативы в этом примере неразличимы. Заметим, что сумма приоритетов элементов любого уровня, равна единице. Если бы альтернатив было две, то их приоритеты были бы равны 0.500, если бы критериев было 5, то приоритет каждого был бы равен 0.200. В этом простом примере приоритеты альтернатив по разным критериям могут не совпадать, что обычно и бывает на практике. Приведем пример, в котором локальные приоритеты альтернатив по разным критериям не совпадают. Глобальные приоритеты альтернатив относительно цели вычисляются путем умножения локального приоритета каждой альтернативы на приоритет каждого критерия и суммирования по всем критерия. Рис.4. Более сложная иерархическая структура, содержащая глобальные и локальные значения приоритетов по умолчанию Если приоритеты критериев изменятся, то изменятся значения глобальных приоритетов альтернатив, следовательно, может измениться их порядок. На Рис. 5 показано решение данной задачи с изменившимися значениями приоритетов критериев, при этом наиболее предпочтительной альтернативой становится A3. Пример задачи МАИ Метод можно применять независимо от того, заданы альтернативы или нет. Но при небольшом числе конкретно сформулированных вариантов выбора разумно направить усилия только на сравнение этих вариантов. Именно такая идея лежит в основе метода. Основные этапы подхода • Структуризация задачи в виде иерархии с несколькими уровнями: цели – критерии – альтернативы. • Попарное сравнение элементов каждого уровня (в числовом виде). • Вычисление коэффициентов важности для элементов каждого уровня. • Подсчет количественного индикатора качества каждой альтернативы и определение лучшей из них. • Для иллюстрации будем использовать приведенный выше пример строительства аэропорта. Структуризация Предположим, что для строительства аэропорта предварительно были отобраны три площадки: А, В, К. Тогда структура задачи будет выглядеть следующим образом. Цели: Прием и отправка большого числа пассажиров. Критерии: • Стоимость строительства. • Время в пути от центра города до аэропорта. • Количество людей, подвергающихся шумовым воздействиям. Альтернативы: Площадка А. Площадка В. Площадка К. Попарные сравнения ЛПР дается шкала определений уровня важности, в которой каждому определению ставится в соответствие число. Уровень важности Количественное значение Равная важность Умеренное превосходство Существенное превосходство Значительное превосходство Очень большое превосходство 1 3 5 7 9 При сравнении элементов, принадлежащих одному уровню иерархии, ЛПР строит матрицу сравнений. Критерии С1 Стоимость С2 Время в пути С3 Фактор шума Собств. вектор Вес С1 Стоимость 1 5 3 2,47 0,65 С2 Время в пути 1/5 1 3 0,848 0,22 С3 Фактор шума 1/3 1/3 1 0,48 0,13 На нижнем уровне сравниваются заданные альтернативы по каждому критерию. По критерию С1 Альтернатива А В К Собств. вектор Вес А 1 7 3 2,76 0,69 В 1/7 1 3 0,755 0,19 К 1/3 1/3 1 0,48 0,12 По критерию С2 А 1 1/7 1/5 0,31 0,12 В 7 1 3 2,76 0,65 К 5 1/3 1 1,18 0,28 По критерию С3 А 1 5 5 2,93 0,68 В 1/5 1 1/5 0,34 0,09 К 1/5 5 1 1 0,23 Вычисление коэффициентов важности Собственный вектор вычисляется как среднегеометрическое значений относительной важности альтернатив, например: для критерия С1: Нормировка (вес): собственный вектор делится на сумму всех собственных векторов матрицы, например, для С1:  Определение наилучшей альтернативы Синтез полученных коэффициентов важности осуществляется по формуле: где S – показатель качества j-й альтернативы; w – вес i-го критерия; V – важность j-й альтернативы по i-му критерию. Для нашего примера: S(A)=0.65*0.69+0.22*0.07+0.13*0.68=0.552 S(B)= 0.65*0.19+0.22*0.65+0.13*0.09=0.278 S(K)= 0.65*0.12+0.22*0.28+0.13*0.23=0.17 Итак, альтернатива А оказалась лучшей.  Метод МАИ хорош тем, что в нем построена единая стройная математическая теория, которая позволяет обосновать конкретную функцию полезности в зависимости от предпочтений ЛПР. Полученные результаты позволяют оценивать любые, в том числе и вновь появляющиеся альтернативы. Недостаток заключается в том, что построение функции полезности требует много времен и усилий ЛПР. Пример задачи с использованием МАИ Был проведен анализ трех университетов: А, В и С на предмет их желательности. Для сравнения были выбраны два основных критерия: местонахождение университета и его академическая репутация (Рис. 6). Рис. 6. Иерархия удовлетворения университетом Покажем, как определяется матрица сравнения А для задачи выбора одного из трех университетов. Начнем с главного иерархического уровня, который имеет дело с критериями академической репутации (R) университета и его местонахождения (L). С точки зрения лица принимающего решение (ЛПР), академическая репутация университета существенно важнее его местонахождения. Следовательно, он приписывает элементу (2, 1) матрицы А значение 5, т.е. =5. Это автоматически предполагает, что =1/5. Матрица сравнения А: L R L 1 1/5 R 5 1 Элементы матриц (альтернативы репутации) и (альтернативы местоположения) определены на основе суждений ЛПР, касающихся относительной важности трех университетов А В С А В С , . Следующий шаг состоит в вычислении вектора приоритетов по данной матрице. В математических терминах это вычисление главного собственного вектора, который после нормализации становится вектором приоритетов. Относительные веса вычисляются в виде средних значений элементов соответствующих строк нормализованной матрицы А, элементы которой определяются путем деления элементов каждого столбца матрицы парных сравнений на сумму элементов этого же столбца Ход вычислений: 1. Определение относительных весов матриц парных сравнений. Относительные веса критериев R и L могут быть определены путем деления элементов каждого столбца на сумму элементов этого же столбца. Следовательно, для нормализации матрицы А делим элементы первого столбца на величину 1+5=6, элементы второго – на величину 1+1/5=1,2. Искомые относительные веса и критериев вычисляются теперь в виде средних значений элементов соответствующих строк нормализованной матрицы A. Следовательно, L R Средние значения элементов строк: =(0,83+0,83)/2=0,83, =(0,17+0,17)/2=0,17. В результате вычислений получили =0,83, =0,17. 2. Определение относительных весов альтернативных решений Относительные веса альтернативных решений, соответствующих университетам А, В и С, вычисляются в пределах каждого критерия R и L с использованием следующих двух матриц сравнения. А В С Суммы элементов столбцов равны 8, 3,5, 1,7 соответственно. А В С Суммы элементов столбцов равны 1,83, 3,67, 5,5 соответственно. 3. Получение нормализованных матриц При делении элементов каждого столбца матриц и , на сумму элементов этих же столбцов получаем следующие нормализованные матрицы. А В С Средние значения элементов строк: (0,125+0,143+0,118)/3=0,129, = (0,25+0,286+0,294)/3=0,277, (0,625+0,571+0,588)/3=0,594. А В С Средние значения элементов строк: (0,545+0,545+0,545)/3=0,545, (0,273+0,273+0,273)/3=0,273, (0,1 82+0,182+0,182)/3=0,182. Величины = (0,545;0,273;0,182) дают соответствующие веса для университетов А, В и С, с точки зрения академической репутации. Аналогично величины (=(0,129;0,277;0,594) являются относительными весами, касающимися местонахождения университетов. Если матрица парных сравнений не является согласованной, то для нее находят индекс согласованности, который дает информацию о степени нарушения согласованности. В компактной форме условие согласованности матрицы А формулируется следующим образом: матрица А будет согласованной тогда и только тогда, когда , где - вектор-столбец относительных весов . Здесь не проверяем согласованность 4. Оценка альтернатив основана на вычислении комбинированного весового коэффициента