ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.02.2024
Просмотров: 30
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное бюджетное государственное образовательное учреждение высшего профессионального образования
«Московский государственный университет» (ФБГОУ ВПО МГИУ)
Кириличев Б.В.
Проектирование систем управления
ч.2
Москва, 2012
Лекция №1
1. Критериальный язык описания задачи выбора
1.1. Многокритериальная оптимизация
В процессе проектирования очень часто приходится сталкиваться с необходимостью поиска такого варианта (альтернативы), который удовлетворял бы сразу нескольким, порой противоречивым, критериям оптимальности. Например, таким как: точность, быстродействие, надежность, вес, стоимость и т.д.
Стремление учесть одновременно несколько критериев и приводит к задаче многокритериальной, или векторной оптимизации.
Рис. 1. К понятию многокритериальной оптимизации
На рис. 1 показана ситуация, когда экстремумы трех различных целевых функций (соответствующих различным критериям оптимальности) не совпадают, а находятся в различных точках пространства X внутренних (варьируемых, управляемых) параметров. Очевидно, что в этом случае выбор компромиссных значений проектных параметров представляет собой непростую задачу.
Существует несколько языков описания проблемы выбора; наиболее употребимы следующие: критериальный язык выбора, язык бинарных отношений, язык функций выбора.
Введем общие понятия для всех задач выбора:
Принятие решения (выбор) – действие над множеством альтернатив, в результате которого, получается подмножество выбранных альтернатив.
Сужение множества альтернатив возможно, если существует способ сравнения альтернатив между собой и определения наиболее предпочтительных. Каждый такой способ называется критерием предпочтения.
Однако прежде необходимо выполнить ряд этапов:
1. Порождение множества альтернатив, из которых предстоит сделать выбор.
2. Определение целей, для достижения которых осуществляется выбор.
Стоит помнить также, что способ порождения альтернатив определяет выбор.
1.2. Множественность задач выбора
Даже в упрощенной постановке, проблема выбора нетривиальна и имеет расхождения в математических постановках задач. Существует множество различных ситуаций выбора и все их можно классифицировать в зависимости от следующих факторов:
1. Свойства множества альтернатив. Это множество может быть конечным, счетным (каждому элементу соответствует некоторое число, номер) или континуальным (между двумя любыми элементами множества может располагаться бесконечное число других элементов множества).
2. Оценка альтернатив может осуществляться по одному или нескольким критериям. Критерии могут иметь как количественный, так и качественный характер.
3. Режим выбора может быть однократным или повторяющимся, допускающим обучение на опыте.
4. Последствия выбора могут быть известны (выбор в условиях определенности), либо может иметь вероятностный характер (известны вероятности возможных исходов, выбор в условиях риска). Выбор может иметь неоднозначный исход, не допускающий введения вероятностей возможных исходов (выбор в условиях неопределенности).
5. Ответственность за выбор может быть односторонней и в частном случае индивидуальной, либо многосторонней. Тогда в первом случае, выбор называют индивидуальным, а во втором групповым.
6. Степень согласованности цели. В случае многостороннего выбора может различаться от полного совпадения (консенсуса), частичного совпадения (компромиссный, или коалиционный выбор), до полного несовпадения целей (выбор в условиях конфликта).
Различные сочетания выше перечисленных вариантов приводят к многообразным задачам выбора, которые изучены в разной степени.
1.3. Классификация критериальных задач выбора
Рис. 2. Классификация задач принятия решений, описываемых на критериальном языке
1.4. Сведение многокритериальной задачи к однокритериальной
Это можно осуществить с помощью введения суперкритерия – скалярной функции векторного аргумента:
, так что задача сведется к максимизации этого суперкритерия:
Суперкритерий позволяет упорядочить альтернативы по величине Isup, выделив, таким образом, наилучшую (в смысле этого суперкритерия) альтернативу. Конкретный вид функции Isupопределяется тем, как мы представляем себе вклад каждого частного критерия в суперкритерий. Чаще всего используют аддитивные функции вида:
(1)
или мультипликативные функции вида:
(2)
Коэффициенты αiиβiотражают относительный вклад частных критериев в суперкритерий. Коэффициенты γiобеспечивают безразмерность величин Ii / γi , что необходимо, например, когда частные критерии имеют разную размерность, препятствующую выполнению арифметических операций над ними (бессмысленно, например, складывать килограммы с рублями!). Кроме того, при необходимости указанные коэффициенты обеспечивают нормирование (например, в приведенном выражении (2) должно выполняться условие
(
3)Достоинства и недостатки свертки (скаляризации) критериев
Преимущество объединения нескольких критериев (векторного критерия) в один скалярный суперкритерий состоит в возможности однократного использования процедуры поиска экстремума этого критерия одним из известных методов и одновременного удовлетворения при этом требованиям всех различных частных критериев, входящих в суперкритерий.
Недостатком является то, что суперкритерий выполняет роль функции, упорядочивающей альтернативы в многомерном пространстве критериев. Однако известно, что упорядочивание точек (альтернатив) в многомерном пространстве в принципе не может быть однозначным и полностью определяется видом упорядочивающей функции. Поэтому даже небольшое изменение суперкритерия (например, его коэффициентов αiи γi) может привести к тому, что оптимальная в новом смысле альтернатива будет сильно отличаться от прежней.
На рисунке 3 видно, как изменяется выбор наилучшей альтернативы при смене коэффициентов в линейной упорядочивающей функции (1):
что отражается в изменении наклона соответствующей прямой:
Линейные комбинации частных критериев придают упорядочению смысл: «чем дальше от нуля в заданном направлении, тем лучше».
Рис. 3. Изменение выбора наилучшей альтернативы при смене коэффициентов в линейной упорядочивающей функции
Другой вариант поиска альтернативы, наиболее удаленной от нуля в заданном направлении.
(4)
Это означает поиск вокруг направления
методом «подтягивания самого отстающего».
1.5. Условная максимизация
Недостатки свертывания нескольких критериев в суперкритерий вынуждают применять другие подходы к решению многокритериальных задач выбора.
Например, можно использовать тот факт, что частные критерии обычно неравнозначны между собой, т.е. одни из них более важны, чем другие.
В предельном случае выделяют один основной, или главный критерий, а остальные рассматривают как дополнительные, второстепенные, сопутствующие.
В
результате можно сформулировать задачу выбора как задачу нахождения условного экстремума основного критерия:(5)
при условии, что дополнительные критерии остаются на заданных им уровнях Сi (рис. 4).
Рис. 4. К решению задачи выбора методом условной максимизации
В некоторых задачах бывает нужно задавать ограничения на дополнительные критерии не жестко, как в предыдущем случае.
Например, если сопутствующий критерий характеризует стоимость затрат, то вместо жесткой фиксации затрат разумнее задавать их верхний уровень, а значит, формулировать задачу с ограничениями типа неравенств:
(6)
Такой метод решения иллюстрирует рис. 5. Оказывается, что столь незначительное на первый взгляд изменение постановки задачи (по сравнению с жесткими ограничениями) требует принципиально иных методов ее решения.
Рис. 5. К решению задачи выбора методом условной максимизации с нежесткими ограничениями
1.6. Метод уступок
В том случае, когда различия между основным и дополнительными критериями не так велико, как в методе условной максимизации, можно упорядочить частные критерии в порядке убывания их важности.
Затем берется первый из них (самый важный) и находится наилучшая по этому критерию альтернатива (на рисунке 6 это
x3*, если самый важный критерий – I1, или x4*, если самый важный критерий – I2).
Далее определяется «уступка» ΔIi, т.е. величина, на которую мы согласны уменьшить достигнутое значение самого важного критерия, чтобы за счет уступки попытаться увеличить, насколько возможно, значение следующего по важности критерия, и т.д.
На рис. 6 полученные таким образом альтернативы изображены точками x5* и x6*).
Рис. 6. К методу уступок
1.7. Поиск альтернативы с заданными свойствами
Этот метод многокритериального выбора относится к тому случаю, когда заранее могут быть указаны значения частных критериев (или их границы).
Задача состоит в том, чтобы найти альтернативу, удовлетворяющую этим требованиям. Если же такая альтернатива во множестве X отсутствует, то найти в этом множестве альтернативу, наиболее близкую к поставленным целям.
При этом удобным является возможность заранее задавать желательные значения критериев Îi как точно, так и в виде верхних или нижних границ.
Назначаемые величины называют уровнями притязаний, а точку их пересечения в k-мерном пространстве критериев – идеальной точкой, целью.
На рисунке 7 это точка x1*; она соответствует недостижимой цели, т.к. не принадлежит множеству X. Достижимой цели соответствует точка x2*.
После того, как цель задана, идея оптимизации состоит в том, чтобы, начав с любой альтернативы, приближаться к цели x* по некоторой траектории в пространстве X. Это достигается введением числовой меры близости между очередной альтернативой и целью x*, т.е. между векторами I(x)=[I1(x),I2(x),…,Ik(x)] и Î(x)=[Î1(x), Î2(x),…, Îk(x)].
Количественно эту меру близости можно описать по-разному. Например, с помощью расстояния:
(7)
Рис. 7. К поиску альтернативы с заданными свойствами
Либо с помощью расстояния:
