Диссертация (Алгоритмы сужения множества Парето на основе информации о предпочтениях ЛПР), страница 6

По утверждению 1.5 коническая оболочка строк Qs1s0двойственна конической оболочке cone e1m0 , . . . , emm0 , u , . . . , u , следовательно, для ∀i = 1, ms , ∀j = 1, m0 , r = 1, s имеем q i ej > 0, q i ur > 0. РассмотримmsP11теперь n ∈ T q . Справедливо 0 = q n =αi q i n. Так как в правой чаi=2сти все слагаемые неотрицательны, они должны быть равны нулю. А значит,n ∈ T q l , то есть T q l ⊇ T q 1 .Достаточность.

Если q l сонаправлена с q 1 , то очевидно, что q 1 выражается через q l и, следовательно, может быть исключена из списка образующихконической оболочки строк Qs .Пусть q l не сонаправлена с q 1 . Рассмотрим тогда векторы p± = q 1 ±εq l длянекоторого ε > 0. По условию T q l ⊇ T q 1 , следовательно, ∀n ∈ T q 1 ⇒1s10p± n = 0. Для n ∈ e1m0 , .

. . , em,u,...,u\Tqв силу nq 1 > 0, nq l > 0 приm0достаточно малом ε справедливо p± n > 0. Поэтому векторы p± принадле1s0жат конусу, двойственному к cone e1m0 , . . . , emm0 , u , . . . , u , т. е. коническойmsPоболочке строк Qs . Значит, существуют разложения p± =αi± q i с неотриi=1цательными коэффициентами.ms α+ + α−Pα+ + α1−p+ + p−ii i=q .

Если 1< 1, тоВернёмся теперь к q 1 =222i=1+−msPα+αiii1q1 =+− q , и q не является существенной.i=2 2 − α1 − α132ms α+ + α−Pα1+ + α1−ii iЕсли= 1, тоq = 0, и в силу того, что все строки Qs22i=2ненулевые и имеют лишь неотрицательные компоненты, все коэффициентысправа равны нулю. Следовательно, αi+ = αi− = 0 для ∀i = 2, ms . Тогдаp± = α1± q 1 = q 1 ± εq l , и строки q 1 и q l коллинеарны. А так как строки Qsмогут иметь лишь неотрицательные компоненты, то q 1 и q l сонаправлены,следовательно, q 1 лишняя.ms α + + α −α1+ + α1−αi+ + αi− − 2 1 Pii iЕсли> 1, тоq +q = 0, и, как в преды222i=2дущем случае, все коэффициенты должны быть равны нулю.

Но тогда p± =0 = q 1 ± εq l , что возможно только при q 1 = q l = 0, но в матрице Qs попостроению не может быть нулевых строк.С помощью данного утверждения можно дополнить алгоритм 1 проверкойгенерируемых на каждом шаге новых критериев на существенность и такимобразом решить проблему чрезмерного роста размерности нового векторногокритерия.33Глава 2Случай нечёткогоотношения предпочтенияЛПРПерейдём теперь к обобщению задачи учёта информации об отношениипредпочтения на нечёткий случай. Это позволит моделировать ситуации, вкоторых ЛПР может быть не вполне убеждён в готовности к определённым компромиссам.

С каждым «квантом» информации ассоциируется степень уверенности ЛПР в нём. Математически они представляют собой степени принадлежности нечёткому конусу, содержащемуся в конусе отношенияпредпочтения. Естественным образом оценка множества выбираемых вариантов также оказывается нечёткой.В начале этой главы напоминаются основные определения теории нечётких множеств. Затем рассматриваются нечёткие конические оболочки и вводится понятие нечёткого двойственного конуса. Несколько утверждений посвящено описанию свойств этих объектов. Обобщается и алгоритм нахождения образующих двойственного конуса вместе с критерием их избыточности.Следующий параграф содержит математическую постановку задачи учёта «квантов» нечёткой информации.

Приведены обобщения аксиом на нечёткий случай. Завершает главу описание применения алгоритма нахожденияобразующих нечёткого двойственного конуса для учёта «квантов» и проверки их непротиворечивости.342.1Нечёткие множестваНапомним основные определения из теории нечётких множеств.Определение 2.1 [47]. Нечёткое множество A — множество объектов из некоторого универсального множества X с ассоциированной функциейпринадлежности λA (x) : X 7→ [0; 1]. Для удобства в качестве обозначениянечёткого множества будем использовать и символ его функции принадлежности: λA .Определение 2.2 [47].

Нечёткое множество A является выпуклым, если∀x, y ∈ Rm , ∀α > 0 ⇒ λA (αx + (1 − α)y) > min {λA (x); λA (y)}.Определение 2.3 [41]. Замыканием нечёткого множества A называетсянечёткое множество cl A с функцией принадлежностиnoλcl A (x) = sup α ∈ [0; 1] x ∈ cl {z ∈ X |λA (z) > α} , ∀x ∈ X.Очевидно, всякое множество является подмножеством своего замыкания.Множество, совпадающее со своим замыканием, называется замкнутым.Определение 2.4 [37]. Нечёткое множество A называется нечёткимконусом, если его функция принадлежности удовлетворяет условию∀x ∈ Rm , ∀α > 0 ⇒ λA (αx) = λA (x).2.2Нечёткие конические оболочкиПерейдём теперь к понятиям, определения которых ещё не часто встречаются в литературе.

По аналогии с чётким случаем, нам будет удобно задаватьнечёткие конусы с помощью образующих. Следовательно, необходимо обобщить определение конической оболочки.Определение 2.5 [4]. Нечёткая коническая оболочка конечного числавекторов a1 , . . . , aq ∈ Rm со степенями уверенности α1 , . .

. , αq ∈ [0; 1] — нечёт-35кое множество с функцией принадлежностиλ(x) =max(x1 ,...,xq )∈Rq+ :qPx=xk a kk=1mink=1,q : xk 6=0αk , ∀x ∈ Rm ,гдеRq+ = (x1 , . . . , xq ) ∈ Rq ∀k = 1, q ⇒ xk > 0 .Максимум и минимум существуют, потому что различных αk конечноечисло. Минимум по пустому множеству считается равным 1; максимум попустому множеству — 0.В обозначениях определения 2.5 введём оператор(n)gradeλ x =minαk ,(2.1)k=1,q : xk >0где (n) — ссылка на рассматриваемое представление вектора x, которая будетопускаться, если понятно, о каком представлении идёт речь.

Так, для i =1, q будем подразумевать представление ai = ai и писать gradeλ ai = αi , адля нулевого вектора gradeλ 0 = 1. Из определения 2.5 следует, что λ ai >gradeλ ai .Введём также обозначение для множества представлений, на которых достигается максимум в определении 2.5:()qXOptrepλ x = (x1 , . . . , xq ) ∈ Rq+ : x =xk ak gradeλ x = λ(x) .k=1Покажем корректность этого определения.Утверждение 2.1. Нечёткая коническая оболочка конечного числа векторов является выпуклым нечётким конусом.Доказательство. В обозначениях определения 2.5 возьмём векторы x, yи покажем, что для ∀α ∈ (0; 1) имеет место неравенство λ(αx + (1 − α)y) >min {λ(x); λ(y)}.

Возьмём соответствующие представления векторов x и y изqqPPkOptrepλ x и Optrepλ y: x =xk a , y =yk ak . Тогда αx + (1 − α)y =k=1k=136qP(αxk + (1 − α)yk )ak , иk=1λ(αx + (1 − α)y) > gradeλ (αx + (1 − α)y) ==mink=1,q : αxk +(1−α)yk >0αk > minmink=1,q : xk >0αk ;minαk=k=1,q : yk >0= min {λ(x); λ(y)}.Таким образом, доказана выпуклость.Для доказательства того, что нечёткая коническая оболочка являетсяконусом, рассмотрим произвольный вектор x и число α > 0.

Очевидно,gradeλ αx = gradeλ x для представлений этих векторов, отличающихся лишьмножителем α. Но тогда и λ(αx) = λ(x).В некоторых случаях удобнее пользоваться следующим определением.Определение 2.6 [4]. Нечёткая коническая оболочка конечного числавекторов a1 , .

. . , aq ∈ Rm со степенями уверенности α1 , . . . , αq : 1 = α0 > α1 >α2 > . . . > αq > 0 — нечёткое множество с функцией принадлежностиλ(x) =maxk=0,q : x∈cone {a1 ,...,ak }αk , ∀x ∈ Rm .Максимум по пустому множеству считается равным 0, а коническая оболочка пустого множества векторов — {0}.Утверждение 2.2. Определения 2.5 и 2.6 эквивалентны.Доказательство. Рассмотрим векторы a1 , . . . , aq со степенями уверенности α1 , . .

. , αq : 1 > α1 > α2 > . . . > αq > 0. Пусть λ1 (x) — функция принадлежности нечёткой конической оболочки этих векторов с соответствующимистепенями принадлежности из определения 2.5, а λ2 (x) — из определения 2.6.Возьмём произвольный вектор x ∈ Rm .Если x 6∈ cone a1 , . . . , aq , то в обоих определениях максимум берётся попустому множеству, и, следовательно, λ1 (x) = λ2 (x) = 0.Если x = 0, то gradeλ x = 1, а так как ∀k = 1, q ⇒ αk 6 1, то и λ1 (x) = 1;а в определении 2.6 при k = 0 достигается максимальное значение 1; поэтомуλ1 (x) = λ2 (x) = 1.37Пусть теперь x ∈ cone a1 , . .

. , aq \{0}. Так как cone {∅} ⊆ cone a1 ⊆ . . . ⊆ cone a1 , . . . , aq ,∃k = 1, q : x ∈ cone a1 , . . . , ak \ cone a1 , . . . , ak−1 .Тогда ∀i ∈ N : k 6 i 6 q ⇒ x ∈ cone a1 , . . . , ai , и максимум в определении2.6 выбирается из αk , . . . , αq . По выбору степеней принадлежности максимумравен λ2 (x) = αk .Обратимся к определению 2.5.

Так как x ∈ cone a1 , . . . , ak ,∃(x1 , . . . , xk ) : ∀i = 1, k ⇒ xi > 0, x =kXxi ai .i=1Здесь xk 6= 0, так как в противном случае x ∈ cone a1 , . . . , ak−1 , что противоречит выбору k. Для такого набора минимум выбирается из подмножества α1 , . . . , αk−1 и αk , и равен αk . Поэтому λ1 (x) > αk . Предположим,∗что λ1 (x) > αk . Пусть x∗1 , . .

. , x∗q ∈ Optrepλ x, и gradeλ x = αk . Преждевсего отметим, что минимум в (2.1) не может браться по пустому множе∗ству, так как x 6= 0. Значит, λ1 (x) = αk > αk , и по выбору степеней принадлежности k ∗ < k. Кроме того, ∀i ∈ N : k 6 i 6 q ⇒ x∗i = 0, так как∗иначе среди минимизируемых значений оказались бы αi , меньшие αk .