Мультипликативные свёртки

Рассмотрим мультипликативную свёртку с нормирующими множителями:

где j - нормирующие множители.

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

Посмотрим, какие результаты даст мультипликативная свёртка с весовыми коэффициентами:

где j - нормирующие множители,

вj - весовые коэффициенты.

Итоги отражены в таблице:

Оптимальной стратегией снова является А3.

В конце еще раз напомним непременное правило: перед тем, как применять какую-либо свёртку нужно автоматически всегда выделять множество Парето. И именно для множества Парето применять свёртки. Иначе вы или ваша программа будете выполнять лишнюю ненужную работу.

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

До этого были рассмотрены случаи, когда все критерии оценивали все альтернативы. Все альтернативы можно было сравнить друг с другом по каждому критерию. А что делать, если не все альтернативы будут оценены всеми критериями? В таком случае появятся альтернативы, не сравнимые между собой по некоторым критериям. Рассмотрим такой случай на нашем примере (уберем из него некоторые оценки):

При таком условии альтернативы можно сравнить между собой лишь попарно. Такие попарные сравнения называются бинарными отношениями . Обозначается бинарное отношение (на примере критерия Байеса из нашей таблицы) А1RА2 - альтернатива А1 лучше альтернативы А2.

Дадим математически точное определение бинарных отношений.

Бинарным отношением на множестве? называется произвольное подмножество R множества? Х? , где? Х? - это множество всех упорядоченных пар (ai ;aj) , где ai , aj ? . #

Бинарные отношения очень удобно изображать наглядно. Представим четыре стратегии из нашего примера в виде точек на плоскости. Если имеем, что какая-то альтернатива лучше другой, то проведем стрелку от лучшей альтернативы к худшей. На примере критерия Байеса из нашей таблицы имеем А1RА2 , поэтому на плоскости проведем стрелку от точки А1 к точке А2. Аналогичным образом поступим со всеми начальными данными из таблицы. Заметим, что бинарные отношения не исключают отношения элемента с самим собой. На рисунке такое бинарное отношение будет задаваться петлёй со стрелкой. В результате получим следующую картину:

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

Дадим математически точное определение графа.

Графом называется пара (Е, е), где Е - непустое конечное множество элементов (вершин), е - конечное (возможно и пустое) множество пар элементов из Е (множество дуг). #

Две вершины, соединенные дугой, называются смежными вершинами. Дуга, соединяющая две вершины, называется инцидентной этим вершинам. Две вершины, соединенные дугой, называются инцидентными этой дуге.

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

1)Максимальным элементом множества? по бинарному отношению R называется такой элемент х? , что у? выполняется отношение хRy .

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

Для графов понятие максимальный элемент - это вершина, из которой исходят стрелки во все остальные вершины графа. Например, на рис. 1 максимальным элементом будет вершина А1 - из неё выходят стрелки во все остальные вершины графа.

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

Иначе говоря, оптимальный по Парето элемент множества - это такой элемент, "лучше" которого в рассматриваемом множестве нет.

Для графов понятие оптимальный по Парето элемент - это вершина, в которую не входит ни одна стрелка. Например, на рис. 1 оптимальным по Парето элементом будет вершина А1 - в неё не входит ни одна стрелка.

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

Рассмотрим несколько примеров.

У графа на рис. 2 максимальным элементом будет вершина А1 - из неё выходят стрелки во все остальные вершины графа. Оптимальных по Парето элементов у данного графа нет.

У графа на рис. 3 максимальным элементом будет также вершина А1 - из неё выходят стрелки во все остальные вершины графа. Заметим: то, что в неё входит стрелка из вершины А4 , по определению совершенно не важно. Оптимальных по Парето элементов у данного графа нет.

У графа на рис. 4 максимальными элементами будут вершины А1 и А4 - из них выходят стрелки во все остальные вершины графа. Оптимальных по Парето элементов у данного графа нет.

У графа на рис. 5 максимального элемента нет. Оптимальными по Парето элементами будут вершины А1 и А4 - в них не входит ни одна стрелка.

Отметим очевидные особенности.

У графа либо нет максимальных элементов, либо есть.

Оптимальными по Парето элементами могут быть несколько вершин графа, либо таковых может не быть.

В графе не может один (или одни) элемент быть максимальным, а другой (или другие) элемент быть оптимальным по Парето.

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

Матрица смежности вершин графа - это квадратная матрица размера m x m (m - это количество вершин) с элементами:

По матрицам смежности искать максимальные элементы и элементы, оптимальные по Парето - одно удовольствие! Максимальные элементы - это те, чьи строки состоят из всех единиц (кроме себя самих - там может быть как нуль, так и единица). А оптимальные по Парето элементы - это те, чьи столбцы состоят из всех нулей.

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

Элементы матрицы инцидентности будут такими:

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

Налицо также очевидна закономерность: максимальные элементы - это те, чьи строки содержат единиц на одну меньше, чем количество строк (вершин), а оптимальные по Парето элементы - это те, чьи строки не содержат минус единиц.

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

Другая очень распространенная группа методов скаляризации векторной задачи математического программирования - свертка критериев.

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

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

A = {ak ,k = 1~K}. (64)

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

X ak = 1, ak > 0, Vk е K , (65)

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

Получается однокритериальная (скалярная) задача математического программирования:

F0 = max X af (X). (66)

В результате решения данной задачи получается точка оптимума X0.

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

Теорема Карлина 1.

В выпуклой задаче многокритериальной оптимизации точка X0 е S оптимальна по Парето, если существует вектор весовых коэффициентов A0 = {a° > 0, k = 1,K}, для которого выполняется соотношение:

X«Оf0(X0) = maxX«0h (X). (67)

Теорема Карлина 2.

Если в выпуклой задаче многокритериальной оптимизации точка X0 е S Парето-оптимальна, то существует вектор весовых коэффициентов A0 = {a° > 0, к = 1,К}, для которого выполняется соотношение:

X«0f^X°) = maxX«0fk (X). (68)

«h (X) =ma„xXakJkк=1 40eS к =1

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

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

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

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

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

F0 = max П (af (X))Рк. (69)

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

Так, существует свертка вида: (70)

minF0 =X| f (X)V

fк Наиболее широкое применение данная свертка получила при p = 2, которая трактуется как минимизация суммы квадратов относительных отклонений функционалов от своих достижимых оптимальных значений. Данная точка в случае равноценности критериев показывает решение, наиболее близкое к недостижимой «идеальной» точке (в которой все критерии принимают свое максимальное значение). Однако данной свертке также свойственен следующий распространенный недостаток: «хорошее» значение сводного критерия достигается ценой низких значений некоторых частных критериев.

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

Т.е. мы получаем новый суперкритерий F, который является функцийот частных критериев. В общем случае, функциюназывают сверткой частных критериев .

К основным этапом свертывания относятся:

1. Обоснование допустимости свертки

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

Показатели результативности;

Показатели ресурсоемкости;

Показатели оперативности.

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

2. Нормировка критериев

Правила нормализации критериев, мы рассматривали ранее в предыдущем разделе.

3. Учет приоритетов критериев

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

4. Построение функции свертки

Для свертывания критериев, используют такие основные типы функций:

Аддитивные функции свертки;

Мультипликативные;

Агрегированные, а также могут быть другие варианты сверток.

Аддитивная свертка

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

(2.9)

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

таблица 2.1.

Таблица относительной важности критериев

Мультипликативная свертка

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

При использовании мультипликативных критериев не требуется нормировка частных критериев, и это является их преимуществом .

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

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

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

Если первые mпоказателей надо увеличить, а остальные – уменьшить, то используют функцию агрегирования вида:

(2.11)

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

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

Рассмотрим в качестве примера такую задачу:

Перед тем как преобразовывать эти критерии в 1, мы должны привести их в однородном состоянии. Т.е. в данном случае нужно максимизировать f2→ f2" = -f2. И тогда получим: . После этого суммируем частных критериевв один, и можем дальше решить задачу обычным путем.

Также нужно учитывать и весовые коэффициенты, при этом их сумма должна быть = 1, и каждый из весовых коэффициентов должен быть неотрицательной величиной. Весовые коэффициенты распределяется по важности этих самих частных критериев . В данном случае, весовые коэффициенты будут распределяться следующим образом: 0,5; 0,2; 0,3.

После подсчета вместе с весовыми коэффициентами, мы получим целевую функцию такого вида: или.

Открываем электронную книгу Excel и, как и для решения однокритериальной задачи определяем ячейки под переменные . Для этого в ячейку А3 вводим подпись «Переменные», а соседние три ячейки В2, С2 и D2 вводим значения переменных. Это могут быть произвольные числа, например единицы или нули, далее они будут оптимизироваться. В нашем случае это единицы.

рис.2.11. Определение переменных, целевых и ограничений

В четвертой строке задаем целевую функцию. В А4 вводим подпись «Целевая», а в В4, С4, D4 наши значения.

В ячейку F6,F7и F8 вводим формулы «=B6*$B$3+C6*$C$3+D6*$D$3», «=B7*$B$3+C7*$C$3+D7*$D$3»,«=B8*$B$3+C8*$C$3+D8*$D$3» соответственно.

После открытия окна «Поиск решения» в поле «Оптимизировать целевую функцию» ставим курсор и делаем ссылку на ячейку «F4». В окне появится $F$4. В связи с тем, что целевая функция максимизируется, далее нужно проверить, что флажок ниже поля стоит напротив надписи «Максимум».

После ставим курсор в поле «Изменяя ячейки переменных» и обводим ячейки с переменными В3, С3 и D3, выделяя ячейки с переменными. В поле появиться $B$3:$D$3.

В нижней части окна находится поле «Ограничения». Добавляем все необходимые ограничения, «F6» «» «F6», «F7:F8» «≤» и «G7:G8».

Вводим дополнительное ограничение, и получим следующую формулу «B3:D3», «», «0».

рис.2.12. Параметры поиска решения

Далее выбираем метод решения «Поиск решения линейных задач симплекс-методом». Для запуска вычислений нажимаем кнопку «Найти решение». Появляется надпись, что решение найдено. Выбираем «Сохранить найденное решение» и «ОК» видим результат.

рис.2.13. Окончательный результат решения по методу свертывания критериев

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

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

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

ВАЖНЫЙ (В)- m B ={0,4; 1/0,7; 0/1};

ОЧЕНЬ ВАЖНЫЙ (OB) - m OB ={0/0,7; 1/1};

НЕ ОЧЕНЬ ВАЖНЫЙ (НОВ) - m HOB = {0/0,1; 1/0,4; 0/7}.

Для оценки альтернатив использовались лингвистические значения:

Альтернативы получили следующие оценки по критериям:

Взвешенные оценки альтернатив R i имеют следующие функции принадлежности:

Оценки предпочтительности альтернатив равны: m(a 1) = 0,90, m(a 2) = 0,62, m(a 3) = 1,0. Лучшей альтернативой является a 3 , a худшей – а 2 .

Решение задачи методом анализа иерархий

На заданном наборе критериев была построена трехуровневая иерархия, на верхнем уровне которой определена цель выбора (с G). На втором уровне находятся обобщенные критерии: прибыль (с P) к и риск (с R) . На третьем уровне иерархии расположены перечисленные выше критерии с 1 , ..., с 5 . При этом критерии c 1 , с 2 , с 3 , входят в группу критерия c P , а критерии с 4 , с 5 - в группу критерия c R . Экспертные предпочтения и полученные приоритеты приведены в матрицах попарных сравнений:

В результате иерархического синтеза получены векторы приоритетов альтернатив:

Альтернативой с наименьшим риском является а 1 , а наибольшую прибыль обеспечивает а 3 . Эта же альтернативаимеет максимальный приоритет относительно цели выбора.

Сравнение полученных результатов

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

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

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

Анализ приведенных результатов позволяет сделать следующие выводы:

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

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

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

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

Основные понятия

1. Нечеткие множества.

2. Нечеткие числа.

3. Лингвистические переменные.

4. Лингвистический критерий.

5. Лингвистическая оценка.

6. Нечеткие операции и отношения.

7. Нечеткие отношения предпочтения.

8. Максиминная свертка нечетких множеств.

9. Нечеткий логический вывод.

10. Композиционное правило вывода.

11. Методология применения методов теориинечетких множеств.

12. Сравнительный анализ методов.

13. Практические результаты применения методовпринятия решений.

Контрольные вопросы и задания

1. Перечислите и дайте определения основным элементам теории нечетких множеств.

2. Дайте определение нечетким операциям, отношениям и свойствам отношений.

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

4. Составьте алгоритмы и программы многокритериального выбора альтернатив методом максиминной свертки.

5. Постановка задачи выбора альтернатив на основе нечеткого отношения предпочтения.

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

7. Постановка задачи выбора альтернатив с аддитивным критерием.

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

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

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

11. Постановка задачи многокритериального выбора с использованием правила нечеткого вывода.

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

13. Рассмотрите применение принципов пересечения нечетких множеств в экономических и управленческих задачах принятия решений.

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

15. Поставьте задачи из области экономики, наилучшим образом формализуемые математическим аппаратом нечеткого логического вывода.

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

Литература

1. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений: Пер. с англ. - М.: Мир, 1976. - 165 с.

2. Нечеткие множества и теория возможностей. Последние достижения: Пер. с англ. - М.: Радио и связь, 1986. - 408 с.

3. Борисов А. П., Крумберг О. А., Федоров И. П . Принятиерешенийна основе нечетких моделей. - Рига: Зинатне, 1990. - 184 с.

4. Нечеткие множества в моделях управления и искусственного интеллекта/Под ред. Д. А. Поспелова. - М.: Наука, 1986. - 312 с.

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

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

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel .

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 1 2 3 4 5 6 7 8 9 10
Количество целевых функций 2 3 4 5 6

При этом ограничения типа x i ≥ 0 не учитывайте. Если в задании для некоторых x i отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом .

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП

Решение транспортной задачи

Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.

Экстремум функции двух переменных

Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

Объем товара Х (в партиях)	Доход G(X)
	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Алгоритм метода последовательных уступок (компромиссов)

Вначале производится качественный анализ относительной важности критериев. На основании такого анализа критерии нумеруются в порядке убывания важности.
Ищем максимальное значение f 1 * первого критерия f=f 1 (x) на всем множестве допустимых решений. Затем назначаем величину «допустимого» снижения (уступки ) Δ 1 критерия f 1 (x) и определяем наибольшее значение f 2 * второго критерия f=f 2 (x) при условии, что значение первого критерия должно быть не меньше, чем f 1 (x)-Δ 1 . Затем назначаем величину «допустимого» снижения (уступки ) Δ 2 критерия f 2 (x) и определяем наибольшее значение f 3 * третьего критерия f=f 3 (x) при условии, что значение второго критерия должно быть не меньше, чем f 2 * - Δ 2 и т. д. Таким образом, оптимальным решением многокритериальной задачи считается всякое решение последней из задач последовательности:
1) найти max f 1 (x)=f 1 * в области x ∈ X;
2) найти max f 2 (x)=f 2 * в области, задаваемой условиями x ∈ X; f 1 (x) ≥ f 1 * -Δ 1 (6)
……………………………………………………………….
m) найти max f m (x)=f m * в области, задаваемой условиями
x ∈ X; f i (x) ≥ f i * -Δ i , i=1,...,m-1
Очевидно, что если все Δ i =0, то метод уступок находит только лексикографически оптимальные решения, которые доставляют первому по важности критерию наибольшее на Х значение. В другом крайнем случае, когда величины уступок очень велики, решения, получаемые по этому методу, доставляют последнему по важности критерию наибольшее на Х значение. Поэтому величины уступок можно рассматривать как своеобразную меру отклонения приоритета частных критериев от жесткого лексикографического.
Метод последовательных уступок не всегда приводит к получению только эффективных точек, но среди этих точек всегда существует хотя бы одна эффективная. Это следует из следующих утверждений.
Утверждение 3 . Если X ⊂ R n - множество замкнутое и ограниченное, а функции f i (x) непрерывны, то решением m-й задачи из (6) является, по крайней мере, одна эффективная точка.
Утверждение 4 . Если x * - единственная (с точностью до эквивалентности) точка, являющаяся решением m-й задачи из (6), то она эффективна.

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

Пример №1 . Решить методом последовательных уступок многокритериальную задачу.
f 1 (x)=7x 1 +2x 3 -x 4 +x 5 → max ,

при ограничениях
-x 1 +x 2 +x 3 =2 ;
3x 1 -x 2 +x 4 =3 ;
5x 1 +2x 2 +x 3 +x 4 +x 5 =11;
x i ≥ 0 для i=1,2,...,5.
Упорядочим критерии согласно их нумерации, то есть будем в начале работать с критерием f 1 (x), а затем с критерием f 2 (x).
При решении примера методом искусственного базиса была получена симплекс-таблица (табл.). Возьмем ее в качестве начальной, вычислив относительные оценки для функции f=f 1 (x). Получим таблицу 10. Таблица 11 определяет точку, доставляющую функции f1(x) наибольшее значение f 1 * , равное 16.
Таблица 10. Таблица 11.

			7	0
	c в		X 1	x 2				x 4	x 2
	2	x 3	-1	1	2		x 3	1/3	2/3	3
	-1	x 4	3	-1	3		x 1	1/3	-1/3	1
	1	x 5	3	2	6		x 5	-1	3	3
		f 1	-9	5	7		f 1	3	2	16

Далее переходим к решению задачи
f 2 (x)=x 1 -5x 2 -4x 3 +x 4 → max
при ограничениях задачи, к которым добавлено новое ограничение f 1 (x)≥f 1 * -Δ:
-x 1 +x 2 +x 3 =2,
3x 1 -x 2 +x 4 =3 , (7)
5x 1 +2x 2 +x 3 +x 4 +x 5 =11,
7x 1 +2x 3 - x 4 +x 5 ³16-Δ,
x i ≥ 0 для i=1,2,...,5.
Новое ограничение преобразуем в равенство и заменим переменные x 1 , x 3, x 5 , используя таблицу 11, выражениями
x 1 =1/3x 2 -1/3x 4 +1, x 3 =-2/3x 2 -1/3x 4 +3, x 5 =-3x 2 +x 4 +3.
В результате этих преобразований дополнительно введенное ограничение примет вид -2x 2 -x 4 +x 6 =-16+Δ. Итак, получили задачу параметрического программирования с параметром в правой части ограничений.
В качестве начальной таблицы для задачи (7) можно использовать таблицу 12, которая получена из таблицы 11 в результате пополнения ее еще одной строкой и пересчета строки относительных оценок. Решим задачу (7) для произвольного параметра Δ≥0. Для этого столбец правых частей ограничений в таблице 12 представим в виде двух столбцов z′, z″: z i 0 =z i ′+z i ″Δ. При выборе главной строки в таблице 12 следует использовать значения из столбца z′. Полученная далее таблица 13 является оптимальной при Δ=0 и при всех значениях Δ, удовлетворяющих условиям
3+(-1/9) Δ ≥ 0, 1+(-1/9) Δ ≥ 0, 3+1/3 Δ ≥ 0, 0+1/3 Δ ≥ 0.
Из этой системы неравенств получаем 0 ≤ Δ ≤ 9. При этих значениях параметра решением задачи является точка x*=(1+(-1/9)Δ, 0, 3+(-1/9)Δ, 0+1/3Δ, 3+1/3Δ).
Таблица 12. Таблица 13.

		1	-5
с в		x 4	x 2	z′	z″			x 6	x 2	z′	z″
-4	x 3	1/3	2/3	3	0		x 3	-1/9	4/9	3	-1/9
1	x 1	1/3	-1/3	1	0		x 1	-1/9	-5/9	1	-1/9
0	x 5	-1	3	3	0		x 5	1/3	11/3	3	1/3
0	x 6	3	2	0	1		x 4	1/3	2/3	0	1/3
	f 2	-2	2	-11	0		f 2	2/3	10/3	-11	2/3

При Δ > 9 таблица 13 не является оптимальной, и нужно выполнить шаг двойственного симплекс-метода с главным элементом, стоящим на пересечение второй строки и первого или второго столбцов. Получим таблицу 14, из которой видно, что при Δ > 9 решениями являются точки, доставляющие функции f 2 (x) значение –5. Таблица 14 определяет опорное решение x ** =(0,0,2,3,6).
Таблица 14.

		x 1	x 2	z′	z″
	x 3	-1	1	2	0
	x 6	-9	5	-9	1
	x 5	3	2	6	0
	x 4	3	-1	3	0
	f 2	6	0	-5	0

Найдем эти решения. Выберем главным столбец с 0-оценкой. В зависимости от Δ главной строкой будет первая или вторая строка. Если
(-9+Δ)/5 > 2, то главной строкой будет выбрана 1-я. А значит, следующей будет таблица 15. Она определяет опорное решение X=(0,2,0,5,2) , если
–19+Δ≥0. Итак, если D≥19, оптимальными решениями будут все точки выпуклой комбинации
ax ** +(1-a)x * =(0, 2-2a, 2a,5-2a,2+4a), где a∈.
Таблица 15.

		x 1	x 3	z′	z″
	x 2	-1	1	2	0
	x 6	-4	-5	-19	1
	x 5	5	-2	2	0
	x 4	2	1	5	0
	f 2	6	0	-5	0

Если (-9+Δ)/5 > 2, то главной строкой будет выбрана 2-я. А значит, следующей после таблицы 14 будет таблица 16. Таблица 16 определяет решение X=(0, (-9+Δ)/5, (19-Δ)/5, (6+Δ)/5, (48-2Δ)/5), если –19+Δ≤0. Итак, если Δ≤19, оптимальными решениями будут все точки выпуклой комбинации
ax**+(1-a)x*=(0, (1-a)(-9+Δ)/5, (19-Δ)/5+a(-9+Δ)/5, (6+Δ)/5+a(9-Δ)/5, (48-2Δ)/5+a(-18+2Δ)/5), где a∈.
Таблица 16.

		x 1	x 6	z′	z″
	x 3	4/5	-1/5	19/5	-1/5
	x 2	-9/5	1/5	-9/5	1/5
	x 5	33/5	-2/5	48/5	-2/5
	x 4	6/5	1/5	6/5	1/5
	f 2	6	0	-5	0

Окончательный результат формулируется следующим образом: решением многокритериальной задачи являются:
точки x*=(1+(-1/9)Δ, 0, 3+(-1/9)Δ, 0+1/3Δ, 3+1/3Δ), если 0 ≤ Δ ≤ 9,
точки x**=(0, (1-a)(-9+Δ)/5, (19-Δ)/5+a(-9+Δ)/5,
(6+Δ)/5+a(9-Δ)/5,(48-2Δ)/5+a(-18+2Δ)/5), если 9 < Δ ≤ 19,
точки x *** =(0, 2-2a, 2a,5-2a,2+4a), если Δ ≥ 19,
где a∈.

Пример №2 . Методом последовательных уступок найти решение задачи, считая, что критерии упорядочены по важности в последовательности {f 2 ,f 1 }, и Δ 2 =1.
f 1 =-x 1 +3x 2 → max,
f 2 (x)=4x 1 -x 2 → max ,
Первая задача из последовательности (6) в данном случае имеет вид:
f 2 (x)=4x 1 -x 2 → max ,
при ограничениях
-x 1 +x 2 ≤1, x 1 +x 2 ≥3, x 1 -2x 2 ≤0 , x 1 ≤4 , x 2 ≤3.
Решение этой задачи можно найти графически. Из рисунка 14 видно, что максимум критерия f 2 (x) на множестве X достигается в вершине x 5 =(4,2) и f 2 * =f 2 (x 5)=14.
Графическое решение примера №2.

Рис.
Добавим к ограничениям задачи условие f 2 ≥f 2 * -Δ и сформулируем вто­рую задачу последовательности (6):
f 1 =-x 1 +3x 2 → max,
-x 1 +x 2 1 , x 1 +x 2 3, x 1 -2x 2 0 , x 1 4 , x 2 3,
4x 1 -x 2 13
Ее решением (рис.) будет вершина x 4 =(4,3) и f 1 * =f 1 (x 4)=5. Так как, оптимальное решение последней задачи единственно, то в силу утверждения 5, x 4 принадлежит множеству Парето.
Отметим, что при Δ∈ методом последовательных уступок будет найдена одна из точек отрезка , а при Δ>1, одна из точек отрезка . Все эти точки и только они принадлежит множеству Парето.