- •Глава 1. Теория множеств
- •1. Основные понятия теории множеств
- •Контрольные вопросы и задания
- •2. Операции над множествами
- •Контрольные вопросы и задания
- •Примеры решения
- •3. Отображения
- •Контрольные вопросы и задания
- •Примеры решения
- •4. Мощность множества
- •0/1 1/1 2/1 3/1 . . .
- •1/2 2/2 3/2 4/2 . . .
- •Контрольные вопросы и задания
- •Примеры решения
- •5. Свойства счетных множеств
- •Контрольные вопросы и задания
- •Примеры решения
- •6. Свойства множества действительных чисел
- •Контрольные вопросы и задания
- •Примеры решения
- •7. Множества мощности континуума и выше
- •Контрольные вопросы и задания
- •Примеры решения
- •8. Нечеткие множества. Основные понятия
- •Примеры записи нечеткого множества
- •Основные характеристики нечетких множеств
- •Примеры нечетких множеств
- •9. Методы построения функций принадлежности нечетких множеств
- •10. Операции над нечеткими множествами
- •Свойства операций и .
- •11. Алгебраические операции над нечеткими множествами
- •12. Принцип обобщения
- •Контрольные вопросы и задания
- •Глава 2. Бинарные отношения и функция выбора
- •1. Бинарные отношения и операции над ними
- •Примеры решения
- •2. Свойства операций над отношениями
- •Контрольные вопросы и задания
- •Примеры решения
- •3. Способы задания бинарных отношений
- •Пример решения
- •4. Свойства бинарных отношений
- •Контрольные вопросы и задания
- •Примеры решения
- •5. Специальные бинарные отношения. Упорядочение и безразличие
- •6. Слабый порядок
- •XIслy ((X, y) Pсл и (y, X) Pсл)
- •XIслy ((y, X)Pсл и (X, y)Pсл).
- •7. Разбиение и эквивалентность
- •8. Качественный порядок
- •Контрольные вопросы и задания
- •Примеры решения
- •9. Нечеткие отношения. Основные понятия
- •10. Операции над нечеткими отношениями
- •11. Функция выбора. Основные понятия
- •12. Классификация функций выбора
- •Контрольные вопросы и задания
- •Примеры решения
- •13. Задача векторной оптимизации
- •Контрольные вопросы и задания
- •Приложение Метод математической индукции
- •Контрольные вопрсы и задания
- •Примеры решения
- •Библиографический список
13. Задача векторной оптимизации
В классических задачах оптимизации необходимо найти минимум или максимум скалярной функции - функции цели или критерия эффективности. Но в практических задачах редко удается свести эффективность к одному показателю.
Пример. Пусть необходимо сконструировать самолет. Основными, одинаково важными, критериями эффективности конструкции являются скорость и дальность полета. Увеличивая дальность полета самолета, мы уменьшаем его скорость и наоборот. Такая ситуация называется конфликтом критериев.
В том случае, когда имеется несколько конфликтующих критериев, говорят, что имеет место задача векторной оптимизации F(x) = { f 1(x), f 2(x),..., f n(x) } орt,
где f I – частные критерии эффективности.
Как правило, не существует такой точки, в которой все f i оптимальны. Поэтому в задаче векторной оптимизации ищут компромиссное решение. Для эффективного поиска такого решения необходимо, чтобы число возможных допустимых вариантов было как можно меньше.
Для достижения такой цели задачу разбивают на 2 этапа.
1) Поиск нехудших (недоминируемых) решений в смысле безусловного критерия предпочтения (БКП). Множество таких точек называется множеством Парето.
2) Выбор компромиссного решения на множестве Парето.
Рассмотрим пример [4]. Пусть имеем два критерия эффективности q1(x) и q2(x), зависящих от одного аргумента х, каждый из которых необходимо минимизировать ( Рис.3 ).
Обозначим Х1 и Х2 – точки минимума критериев q1(x) и q2(x), соответственно. Разобьем область определения аргумента х на три участка: I, II, III. Осуществим на каждом участке выбор точек, лучших по Парето, т.е. по обоим критериям одновременно:
а) Cpar(I) = Х1 – выбор на I участке есть точка X1;
б) Cpar(III) = X2 – выбор на III участке есть точка X2;
в) на участке II нет точки, которая была бы лучше остальных сразу по обоим критериям, т.е. он весь состоит из конфликтующих точек, следовательно, Cpar(II)=[X1, X2].
Рис. 3
Чтобы найти множество Парето в общем случае надо реализовать функцию выбора на основе паретовского механизма (механизма блокировки в смысле бинарного отношения Парето) (см. п. 6). Для того чтобы построить эту функцию достаточно организовать сравнение предлагаемых вариантов по каждой критериальной функции. Для этой задачи можно достаточно легко построить алгоритм решения, т.е. она формализуема.
Для задачи второго этапа необходимо применять неформальные методы выбора, основанные на интуитивных предпочтениях эксперта или лица принимающего решения (ЛПР).
Для организации паретовского механизма выбора необходимо произвести парные сравнения исходных вариантов и отбросить те, для которых найдется доминирующий элемент. Если исходное множество велико, то метод попарного сравнения трудоемок, т.к в общем случае необходимо произвести m(m-1)/2 сравнений, где m – число сравниваемых вариантов.
Более эффективен следующий алгоритм, который производит последовательное накопление элементов искомого множества.
Обозначим X = {xi} – исходное множество сравниваемых вариантов. Для него будем производить отсев плохих точек и получение множества П(Х), содержащее точки Парето.
begin П(Х) := {х1};
for i := 2 to m do
П(Х) := C par ({xi} П(Х) );
end.
При реализации этого алгоритма возможны три случая:
1) Для хi существует такой у П(Х), что у Par xi. В этом слу-чае необходимо прекратить сравнение хi с паретовскими точками и перейти к хi+1.
2) Для хi существует такой у П(Х), что xi Par у. В этом слу-чае необходимо исключить y из П(Х) и продолжить сравнение хi с оставшимися точками пока не будет просмотрено все текущее множество П(Х). Если процесс сравнения не прекратился раньше, чем было просмотрено все П(X), то хi необходимо включить в П(Х).
3) Для хi не существует такого у П(Х), чтобы у Par xi или xi Par у. В этом случае y не исключают и продолжают сравнение хi с оставшимися точками также, как и в случае 2).
Обычно множество недоминируемых точек содержит значительно меньше элементов, чем исходное т.е k = |П(Х)|<<|Х| = m. В этом случае нужно провести O(mk) сравнений, т.е. значительно меньше, чем при всевозможных парных сравнениях.
Данный алгоритм даст верное решение, если для любых множеств X и Y выполняется условие:
CR(X Y) = CR( X CR(Y)) (1)
ТЕОРЕМА 7 [1]. Соотношение (1) выполняется, если функция выбора обладает свойствами Н и О.
ДОКАЗАТЕЛЬСТВО. Вспомним свойства
- наследования (B A) C(A) B C(B);
- отбрасывания: (C(A) B A) (C(B) = C(A)).
Покажем, что при их выполнении для любых множеств Z, Y X выполняется соотношение:
CR(Z Y) Z CR(Y). (2)
Пусть х CR(ZY). Предположим, что при этом х Y, тогда х CR(Z Y)Y. Так как Y Z Y, то, в силу свойства наследования (положив B = Y, A = Z Y) получим, что CR(ZY)Y CR(Y). Значит, если х Y, то x CR(Y), а, следовательно, x Z CR(Y).
Если же х Z то последнее включение также верно. Таким образом, из х CR(ZY) следует x Z CR(Y), что доказывает утверждение (2.2).
Обозначим теперь A = ZY; B = ZCR(Y). По соотношению (2) CR(Z Y) ZCR(Y) ZY, т.е. C(A) B A. Тогда по свойству отбрасывания CR(A) = CR(B) или СR(Z Y) = СR(Z СR(Y)), что совпадает с (1).
Условие (1) в частности выполняется, если R – качественный порядок (см. п. 11, ТЕОРЕМА 5). T.к. отношение Парето таковым является, то алгоритм позволяет построить искомое конфликтное множество.