close

Вход

Забыли?

вход по аккаунту

?

Модели многокритериальной оптимизации с равноценными критериями.

код для вставкиСкачать
Работа выполнена при финансовой поддержке РФФИ (проект ќ 1301-00238).
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Келдыш М. В. О собственных значениях и собственных функциях некоторых
классов несамосопряженных уравнений // Докл. АН СССР. 1951. Т. 77. ќ 1. С. 1114.
2. Хромов А. П. Конечномерные возмущения вольтерровых операторов. Дис.
докт. физ.-мат. наук. Новосибирск. 1973. 242 с.
3. Шкаликов А. А. О полноте собственных и присоединенных функций обыкновенного дифференциального оператора с нерегулярными краевыми условиями //
Функц. анализ. 1976. Т. 10. ќ 4. С. 6980.
4. Хромов А. П. О порождающих функциях вольтерровых операторов // Матем.
сборник. 1977. Т. 102(144). ќ 3. С. 457472.
5. Freiling G. Zur Vollstandigkeit des Systems der Eigenfunktionen und Hauptfunktionen irregularer Operator-b
uschel // Math. Z. 1984. Vol. 188. N 1. P. 55-68.
6. Тихомиров С. А. Конечномерные возмущения интегральных вольтерровых
операторов в пространстве вектор-функций. Дис. канд. физ.-мат. наук. Саратов.
1987. 126 с.
7. Гасымов М. Г., Магеррамов А. М. О кратной полноте системы собственных
и присоединенных функций одного класса дифференциальных операторов //Докл.
АН Азерб. ССР. 1974. Т. 30. ќ 12. С. 912.
8. Шкаликов А. А. Краевые задачи для обыкновенных дифференциальных уравнений с параметром в граничных условиях // Тр. семин. им. И. Г. Петровского. М.:
Изд-во Моск. ун-та. 1983. ќ 9. С. 190229.
9. Вагабов А. И. Введение в спектральную теорию дифференциальных операторов. Ростов-на-Дону: Изд-во Рост. ун-та. 1994. 160 с.
10. Рыхлов В.С. Кратная полнота собственных функций обыкновенного дифференциального полиномиального пучка // Исследования по теории операторов: Сб.
статей / БНЦ УрО АН СССР. Уфа. 1988. С. 128140.
УДК 519.4
Д. С. Смирнова
МОДЕЛИ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ
С РАВНОЦЕННЫМИ КРИТЕРИЯМИ
Будем рассматривать задачу многокритериальной оптимизации по
качественным критериям в виде
G = hA, (qj )j?J i ,
(1)
где А непустое множество допустимых альтернатив, (qj )j?J ? критерии
оценки этих альтернатив. Качественный критерий qj характеризуется
тем, что шкалой для его измерения
служит некоторое линейно упоряj
доченное множество (цепь) Cj , ? ; формально qj представляет собой
79
отображение qj : A ? Cj . Каждой альтернативе a ? A сопоставляется
вектор q(a) = (qj (a))j?J , называемый векторной оценкой альтернативы a и содержащий всю информацию об этой альтернативе; при этом
в теоретическом анализе сравнение альтернатив заменяется сравнением
их векторных оценок.
Q
Иногда на отображение q : A ?
Cj накладывают дополнительное
условие:
j?J
(?j ? J)qj (a1 ) = qj (a2 ) ? a1 = a2 .
(2)
Заметим, что условие (2) позволяет отождествить альтернативу с ее векторной оценкой.
Обозначим через К класс моделей многокритериальной оптимизации
вида (1) с дополнительным условием (2). Напомним, что отношение предпочтения по Парето задается следующей формулой:
a1 ?P ar a2 ? (?j ? J)qj (a1 ) ?j qj (a2 ).
В общем случае можно задать различные отношения предпочтения ?.
Тогда в качестве оптимальных альтернатив для модели G будем рассматривать множество альтернатив M? , которые являются максимальными
относительно предпочтения ?, при этом множество всех максимальных
по Парето-предпочтению альтернатив составляет так называемый паретовский оптимум.
В общем случае для моделей многокритериальной оптимизации класса K , в которых введено отношение предпочтения альтернатив ? , важными являются две задачи:
1. Сокращение множества оптимальных альтернатив.
2. Исследование на внешнюю устойчивость множества оптимальных
альтернатив M? .
Напомним, что свойство внешней устойчивости подмножества M? в
модели G ? K задается формулой
(?a ? A)(?a? ? M? )a .? a? .
(3)
В настоящей статье будем рассматривать модель G вида (1) с дополнительной информацией о равноценности критериев в следующем виде:
1) Все критерии измеряются в одной шкале hC, ?i, т.е. все Cj = C и
считаются равноценными.
2) Наборы значений критериев не зависят от порядка перечисления компонент.
80
В этом случае определим симметрическое отношение предпочтения
по Парето следующей формулой:
a1 ?Spar a2 ? (?? 1 , ? 2 )(q?1 (1) (a1 ) ? q?2 (1) (a2 ) ? ... ? q?1 (n) (a1 ) ? q?2 (n) (a2 )),
(4)
где ? 1 , ? 2 некоторые перестановки на множестве 1...n.
Заметим, что
?par ??spar
(5)
Теорема 1. Следующие условия эквивалентны между собой:
1)(?? 1 , ? 2 )? 1 (a1 ) ?par ? 2 (a2 ),
2)(?? 2 )a1 ?par ? 2 (a2 ),
3)? ? (a1 ) ?par ? ? (a2 ), где ? ? перестановка, в которой элементы
расположены по возрастанию.
1) ? 2) и 2) ? 1) следует из определения симметрического отношения предпочтения по Парето.
Докажем 1) ? 3). Дано:
Доказательство.
pi1 (c1 ) = (c1?1 (1) , c1?1 (2) , ..., c1?1 (n) ),
pi2 (c2 ) = (c2?2 (1) , c2?2 (2) , ..., c2?2 (n) ),
c1?1 (1) ? c2?2 (1) , ..., c1?1 (n) ? c2?2 (n) .
Доказательсьво проведем по индукции по числу критериев.
База индукции: n = 1. Тогда c1 = (c11 ), c2 = (c21 ). Следовательно, существует только одна перестановка ? 0 тождественная. Из условия 1)
получаем, что ? 0 (c1 ) ?par ? 0 (c2 ), но в данном случае ? 0 = ? ? , следовательно, условие 3) также выполнено.
Далее рассмотрим случай n = 2. Тогда c1 = (c11 , 12 ), c2 = (c21 , 22 ). Из
условия 1) получаем, что (c1i1 , c1i2 ) ? (c2j1 , c2j2 ).
Рассмотрим всевозможные варианты расположения компонент в векторах.
1) (c1i1 , c1i2 ) и (c2j1 , c2j2 ) уже расположены по возрастанию. Тогда
? ? (c1 ) ? ? ? (c2 ).
2)(c1i1 , c1i2 ) и (c2j1 , c2j2 ) Расположены по убыванию, т.е. c1i1 ? c2j1 , c1i2 ? c2j2 .
В этом случае получаем ? ? (c1 ) = (c1i2 , c1i1 ), ? ? (c2 ) = (c2j2 , c2j1 ), следовательно, $? ? (c1 ) ? ? ? (c2 ).
3) В одном векторе компоненты расположены по возрастанию, а в
другом по убыванию. Пусть c1i1 ? c1i2 , но c2j1 deg c2j2 . Надо показать, что
(c1i1 , c1i2 ) ? (c2j2 , c2j1 ). Так как (c1i1 , c1i2 ) ? (c2j1 , c2j2 ), то c1i1 ? c2j1 и c1i2 ? c2j2 , то
c1i1 ? c1i2 ? c1j2 ? c2j1 , следовательно, c1i1 ? c2j2 , c1i2 ? c2j1 , отсюда следует,
что (c1i1 , c1i2 ) ?par (2j2 , c2j1 ).
81
Шаг индукции: пусть теорема верна для n ? 1 компоненты. Рассмотрим случай n компонент. Имеем
? 1 (c1 ) = (c1?1 (1) , c1?1 (2) , ..., c1?1 (n) ),
? 2 (c2 ) = (c2?2 (1) , c2?2 (2) , ..., c2?2 (n) ).
Обозначим
c1?1 (j1 ) = min(c1?1 (j) ),
c2?2 (j2 ) = min(c2?2 (j) ).
Первый случай: j1 = j2 .
cb1 = (c1?1 (1) , ..., c1?1 (j1 ?1) , c1?1 (j1 +1) , ...c1?1 (n) ),
cb2 = (c2?2 (1) , ..., c2?2 (j2 ?1) , c2?2 (j2 +1) , ...c2?2 (n) ).
В этом случае cb1 ?par cb2 , по предположению индукции ? ? (cb1 ) ?
?par ? ? (cb2 ). Тогда дла векторов
(c1?1 (1) , ..., c1?1 (j1 ?1) , c1?1 (j1 +1) , ...c1?1 (n) ),
(c2?2 (1) , ..., c2?2 (j2 ?1) , c2?2 (j2 +1) , ...c2?2 (n) )
доминирование по Парето имеет место. Следовательно, перестановка ? ?
приводит к паретовскому доминированию.
Второй случай: j1 6= j2 .
(c1?1 (1) , ..., c1?1 (j1 ) , ..., c1?1 (j2 ) , ...c1?1 (n) ),
(c2?2 (1) , ..., c2?2 (j1 ) , ..., c2?2 (j2 ) , ...c2?2 (n) ).
По предположению верны следующие неравенства:
c1?1 (j1 ) ? c1?1 (j2 ) ? c2?2 (j2 ) .
.
Рассмотрим перестановку
(c1?1 (1) , ..., c1?1 (j2 ) , ..., c1?1 (j1 ) , ...c1?1 (n) ),
82
(6)
(c2?2 (1) , ..., c2?2 (j1 ) , ..., c2?2 (j2 ) , ...c2?2 (n) ).
Согласно первому случаю и воспользовавшись неравенствами (6), получаем, что перестановка ? ? приводит к паретовскому доминированию.
Теорема доказана.
MSpar G ? MP ar G. Это означает, что в случае равноценных критериев мы получаем сокращение паретовского оптимума.
Пусть множество критериев J конечно, все цепи
hCj , ?ij?J удовлетворяют условию максимальности. Тогда в любой задаче G ? K s , в которой отношение предпочтения альтернатив является симметрическим отношением предпочтения по Парето, множество альтернатив оптимальных по симметрическому отношению
предпочтения по Парето MSpar G будет внешне устойчивым.
Надо показать, что ?a ? A?a? ? MS parG такой,
что a ?spar a? . Зафиксируем a ? A. Возможны два случая:
1) если a ? MSpar G, то a? = a и a ?spar a;
2) если a ?
/ MSpar G, тогда ?a1 ? A, a < a1 если a1 ? MSpar G, то требуемое
утверждение доказано, иначе ?a2 ? A, a1 < a2 , если a2 ? MSpar G, то
требуемое утверждение доказано и т.д.
В результате получаем последовательность
Следствие.
Теорема 2.
Доказательство.
a <Spar a1 <Spar a2 <Spar ...,
а так как упорядоченное множество A, ?P ar удовлетворяет условию
обрыва возрастающих цепей, то эта последовательность оборвется на конечном номере k , причем имеет место a ?Spar ak и ak ? A? , то есть для
модели G выполнено условие внешней устойчивости множества MSpar G.
Теорема доказана.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Подиновский В. В., Ногин В. Д. Паретооптимальные решения многокритериальных задач. М: Наука, 1982. 256 с.
2. Розен В. В. Математические модели многокритериальной оптимизации по качественным критериям //Компьютерные науки и информационные технологии: материалы Междунар. науч. конф. Саратов: Издат. центр ѕНаукаї, 2012. 266 с.
3. Смирнова Д. С. Модели многокритериальной оптимизации с частично упорядоченным множеством критериев//Компьютерные науки и информационные технологии: материалы Междунар. науч. конф. Саратов: Издат. центр ѕНаукаї, 2012.
293 с.
83
Документ
Категория
Без категории
Просмотров
4
Размер файла
358 Кб
Теги
критериям, оптимизация, модель, равноценными, многокритериальной
1/--страниц
Пожаловаться на содержимое документа