Многокритериальный выбор. Метод последовательных уступок. Методические указания по выполнению лабораторной ра боты ЮгоЗап гос унт сост. В. В. Апальков, Р. А. Томакова
Скачать 0.6 Mb.
|
УДК 519.816 Составители: В.В. Апальков, Р.А. Томакова Рецензент Кандидат технических наук, доцент Е. И. Аникина Многокритериальный выбор. Метод последовательных уступок: методические указания по выполнению лабораторной ра- боты / Юго-Зап. гос. ун-т; сост.: В.В. Апальков, Р.А. Томакова. – Курск: ЮЗГУ, 2017. – 12 с. Библиогр.: с. 12. Излагается цель лабораторной работы, в теоретической части рассмат- риваются многокритериальная модель задачи принятия решений в услови- ях определенности, проблемы решения многокритериальных задач, метод последовательных уступок. В практической части приводятся пример выпол- нения задания на лабораторную работу и вопросы для самопроверки. Методические указания соответствуют требованиям рабочей програм- мы по направлению подготовки бакалавров 09.03.04 «Программная инжене- рия». Предназначены для студентов всех форм обучения направления подго- товки бакалавров 09.03.04 «Программная инженерия». Текст печатается в авторской редакции Подписано в печать Формат 60 84 1/16. Усл. печ. л. . Уч.- изд. л. . Тираж 25 экз. Заказ. Бесплатно. Юго-Западный государственный университет. 305040, г. Курск, ул. 50 лет Октября, 94. Цель работы: изучить метод решения многокритериальных задач принятия решений (ЗПР) в условиях определенности – метод последовательных уступок. Теоретическая часть Многокритериальная модель задачи принятия решений в ус- ловиях определенности может быть представлена в виде: , , , , , , t A K X f P r , (1) где t – постановка задачи; A – множество допустимых альтернативных решений; K – множество критериев; X – множество шкал критериев; f – отображение множества допустимых решений в множество векторных оценок; P – система предпочтений ЛПР; r – решающее правило. Структурная схема процесса построения и выбора оптимального решения для многокритериальной задачи принятия решений представ- лена на рисунке 1. В реальных задачах, возникающих на практике, оценивание аль- тернативных решений осуществляется с помощью векторного крите- рия, компоненты которого являются не скалярами, а векторами. В зависимости от содержания условия в постановке задачи могут возникать требования определения, например, наиболее предпочтительного решения, либо полностью упорядоченного множества допустимых решений, либо выделения множества не- доминируемых решений и т.д. Множество A представляет собой совокупность альтернатив- ных решений, в каждой задаче удовлетворяющих определенным ограничениям и рассматриваемых как возможные способы дости- жения поставленной цели. Элементы множества A называются также допустимыми решениями, альтернативами, вариантами вы- бора. Множество допустимых альтернативных решений либо зада- ется, либо формируется в процессе исследования. Рассматриваемые варианты выбора могут характеризоваться различными признаками, которые выражаются критериями из мно- жества K . Рисунок 1 – Схема процесса выбора оптимального решения в мно- гокритериальной задаче принятия решений Тогда каждому решению i A ставится в соответствие n-мерная векторная оценка 1 , , ( ) i i in x х х , где ij x – оценка характеристики варианта i A по шкале j X критерия j K , 1,..., j n Совокупность векторных оценок свойств вариантов по шка- Полученное упорядочивание соответствует поставленной за- даче? Разработка оценочных шкал критериев Формирование множе- ства допустимых ре- шений Оценка допустимых решений по шкалам критериев Получение информа- ции о предпочтениях Построение решающе- го правила Упорядочивание до- пустимых решений Анализ результатов упорядочивания Постановка задачи Начало ? Конец Д а нет да лам критериев из множества X и образует множество допусти- мых решений. Качество варианта i A при наличии многих критериев пред- ставляется векторной функцией 1 ( ) ( ) , , i i i im y f x y y , где ( ) ik k i y f x R – оценка варианта i A по частному критерию k f , 1,..., k m ; 1 ( ,..., ) m f f f Совокупность векторных оценок вариантов образует множе- ство оценок качества решения, или множество достижимых це- лей. В теории принятия решений предполагается, что каждое ЛПР имеет некоторую свою систему предпочтений P , из которой он исходит при рациональных действиях. Под системой предпочтений ЛПР будем понимать совокуп- ность обычно неструктурированных его представлений, связанных с достоинствами и недостатками сравниваемых решений. В многокритериальной модели система предпочтений описы- вается совокупностью P некоторых множеств с соотношениями предпочтения (например, наборов критериев, интервалов между оценками допустимых решений определенного вида и т.п.). Решающее правило (метод принятия решения) r представляет собой принцип сравнения векторных оценок и вынесения сужде- ний о предпочтительности одних из них по отношению к другим. Оно может быть задано в виде аналитического выражения, алго- ритма или словесной формулировки. Например, из двух векторных оценок предпочтительнее та, которая имеет хотя бы одну максимальную компоненту и ни одной минимальной. Решающее правило должно приводить к такому упорядоче- нию множества допустимых решений, которое соответствует со- держательной постановке задачи и согласуется с принятыми в мо- дели допущениями и системой предпочтений ЛПР. К принимаемым допущениям относятся допущения о полноте множества решений и набора критериев, о соответствии множества шкал множеству кри- териев и т.п. В зависимости от принятых допущений, а также от це- лей и предпочтений ЛПР, могут быть построены различные ре- шающие правила. Проблемы, связанные с решением многокритериальных задач принятия решений При решении многокритериальных ЗПР возникает ряд специ- фических проблем, носящих не формальный (т. е. не вычислитель- ный), а концептуальный характер. Главная из них – рациональный выбор принципа оптимальности, определяющего свойства опти- мального решения и дающего ответ на вопрос – в каком смысле оп- тимальное решение лучше всех других решений (превосходит дру- гие решения). Принципиальное отличие многокритериальных задач приня- тия решений от однокритериальных детерминированных задач за- ключается в том, что для них имеется множество различных прин- ципов компромисса и соответствующих им принципов оптималь- ности, которые приводят к выбору различных оптимальных реше- ний. Это предъявляет серьезные требования к выбору принципа оп- тимальности. Рассмотрим основные проблемы, связанные с решением мно- гокритериальных задач принятия решений. Проблема 1 – выделение области компромисса. В многокрите- риальных задачах принятия решений имеются противоречия между некоторыми частными критериями, составляющими векторный критерий. Однако эти противоречия обычно является нестрогими, так как иначе задача становится конфликтной антагонистической. В силу этого множество допустимых решений A D распадается на две непересекающиеся части: область согласия C A D и область компро- мисса K A D . В области согласия C A D противоречий между частными критериями не возникает и качество решения может и должно быть улучшено одновременно по всем частным критериям или, во всяком случае, без снижения значений любого из них. В области компромисса K A D противоречия между некоторыми частными кри- териями имеются, при этом улучшение качества решения по одним частным критериям приводит к ухудшению качества решения по другим частным критериям. Все это дает основание утверждать, что оптимальное ре- шение может принадлежать только области компромисса, т. е. * K A A D В связи с этим утверждением, поиск оптимального решения надо ограничить только областью компромисса K A D . Отсюда воз- никает проблема 1 – выделение области компромисса K A D из мно- жества допустимых решений A D . Выделение области компромисса K A D обычно является первым этапом при решении многокритери- альных задач принятия решений. При этом следует отметить важ- ный практический результат – сужение области альтернативных вариантов решений, что уже само по себе улучшает качество при- нимаемых решений. В отдельных случаях поиск оптимальных ре- шений с приемлемой для практики точностью можно ограничить выделением области компромисса. Проблема 2 – выбор схемы компромисса и соответствующего ей принципа оптимальности. Поиск оптимальных решений в об- ласти компромисса может быть осуществлен только на основе не- которой выбранной схемы компромисса. Число возможных схем компромисса достаточно велико, поэтому обоснование и рацио- нальный выбор схемы компромисса представляет собой сложную концептуальную проблему. Рациональный выбор схемы компромисса соответствует рас- крытию смысла оператора оптимизации: * ( ) ( ) A f A opt f A A D , (2) где * A – оптимальный вариант выбора, A D – множество допусти- мых решений, f – отображение множества допустимых решений в множество векторных оценок. Проблема 3 – нормализация критериев. Эта проблема возни- кает в тех задачах, в которых частные критерии имеют различные единицы измерения. Для осуществления возможности оперирова- ния с векторными критериями необходимо нормализовать значения частных критериев, т. е. привести их к единому, безразмерному, масштабу измерения. К настоящему времени разработано большое число различных схем нормализации. Проблема 4 – учет приоритета критериев. Частные крите- рии, составляющие векторный критерий, имеют различную важ- ность и значимость, что является основанием и позволяет упорядо- чить критерии. В связи с этим эта проблема сводится к рациональ- ному выбору схемы компромисса. Перечисленные проблемы являются наиболее важными и час- то встречающимися, но они не охватывают всего множества про- блем, связанных с решением многокритериальных задач принятия решений. Следует отметить, что рассмотренные проблемы 2 - 4 но- сят концептуальный характер, и при их реализации следует при- менять различные эвристические процедуры, основанные на науч- ной аргументации, в которых существенная роль принадлежит экс- пертам и консультантам. Перейдем от множества допустимых решений A D к множест- ву F D допустимых векторных оценок 1 ( ,..., ) m f f f , задаваемых частными критериями k f , 1,..., k m Рассмотрим возможный принцип компромисса – принцип по- следовательных уступок. Метод последовательных уступок В основу метода последовательных уступок положено требо- вание расположения частных критериев по значимости. Предпола- гается, что все частные критерии, составляющие векторный крите- рий упорядочены по убыванию важности: 1 ,..., m f f . Будем также считать, что каждый из них нужно максимизировать. Процедура построения компромиссного решения сводится к следующему. Сначала находится решение, обращающее в максимум наибо- лее значимый частный критерий 1 f . Затем назначается, исходя из практических соображений и точности определения исходных данных, величина некоторой «ус- тупки» 1 f , которую ЛПР согласен сделать для того, чтобы обра- тить в максимум второй частный критерий 2 f . Налагаем на значение частного критерия 1 f ограничение, чтобы это значение было не меньше, чем 1 1 max – f f , и при этом ограничении находим решение, обращающее в максимум частный критерий 2 f . Аналогично назначается «уступка» для частного критерия 2 f , ценой которой можно максимизировать частный критерий 3 f , и так далее. Достоинство такого способа построения компромиссного ре- шения заключается в том, что известна цена «уступки» в одном по- казателе для приобретения выигрыша в другом. При этом важно отметить, что свобода выбора решения, приобретаемая ценой даже незначительных «уступок», может оказаться существенной, так как в районе максимума обычно эффективность решения меняется очень слабо. Практическая часть Рассмотрим применение метода последовательных уступок на примере двухкритериальной задачи принятия решений: 1 1 2 ( ) 3 max f x x x , 2 1 2 ( ) 7 max f x x x , где 1 2 ( , ) x x x . Множество допустимых решений A D задается неравенствами: 1 2 2 4 x x , 1 2 10 x x , 1 2 , 0 x x Пусть частные критерии, составляющие векторный критерий упорядочены по убыванию важности: 1 2 , f f . Находим решение, об- ращающее в максимум наиболее значимый частный критерий 1 f . Первая задача имеет вид: 1 1 2 ( ) 3 max f x x x , при ограничениях 1 2 2 4 x x , 1 2 10 x x , 1 2 , 0 x x Найдем решение этой задачи геометрическим методом (рису- нок 2). Уравнение линии уровня функции 1 ( ) f x имеет следующий вид: 1 2 3x x c , где c – const. Градиент функции 1 ( ) f x – вектор 1 ( ) (3; 1) f x , показываю- щий направление наибольшего возрастания функции в точке x Максимум частного критерия 1 f достигается в вершине мно- гоугольника допустимых решений * (10;0) x . При этом * 1 ( ) 30 f x , * 2 ( ) 10 f x Рисунок 2 – Графическое решение первой задачи Назначим «уступку» 1 6 f (20% от максимального значения критерия 1 f ) и решим вторую задачу: 2 1 2 ( ) 7 max f x x x , при ограничениях 1 2 2 4 x x , 1 2 10 x x , 1 2 3 24 x x , 1 2 , 0 x x Аналогично, геометрическим методом получим решение этой задачи (рисунок 3). Уравнение линии уровня функции 2 ( ) f x имеет следующий вид: 1 2 7 x x c , где c – const. Градиент функции 2 ( ) f x – вектор 2 ( ) (1;7) f x Максимум частного критерия 2 f достигается в вершине мно- гоугольника допустимых решений ** (8,5;1,5) x . При этом ** 2 ( ) 19 f x , ** 1 ( ) 24 f x Рисунок 3 – Графическое решение второй задачи Отметим, что оптимальное решение последней задачи ** (8,5;1,5) x принадлежит множеству Парето ( точки отрезка, со- единяющего две вершины многоугольника допустимых решений первой задачи с координатами (0;10) и (10;0) ). Вопросы для самопроверки 1. Многокритериальная модель ЗПР в условиях определен- ности. 2. Множество допустимых решений. 3. Множество достижимых целей. 4. Система предпочтений ЛПР. 5. Решающее правило. 6. Проблемы, связанные с решением многокритериальных ЗПР. 7. Область согласия. 8. Область компромисса. 9. Принцип последовательных уступок. Литература 1. Лотов, В.А. Многокритериальные задачи принятия ре- шений [Текст]: учебное пособие / В.А. Лотов, И.И. Поспелова. – М: МАКС Пресс, 2008. – 197 с. 2. Ногин, В.Д. Принятие решений в многокритериальной среде. Количественный подход / В.Д. Ногин. – 2-е изд., испр. и доп. – М.: ФИЗМАТЛИТ, 2005. –176 с. 3. Петровский, А. Б. Теория принятия решений [Текст]: учеб- ник / А. Б. Петровский. – М.: Академия, 2009. – 400 с. 4. Томакова, Р. А. Методы и алгоритмы теории принятия ре- шений [Текст]: учебное пособие / Р. А. Томакова, В. В. Апальков; Юго-Зап. гос. ун-т. – Курск: ЮЗГУ, 2015. – 164 с. 5. Черноруцкий, И. Г. Методы принятия решений [Текст]: учебное пособие для студентов вузов / И. Г. Черноруцкий. – СПб.: БХВ-Петербург, 2005. – 416 с. |