Диссертация (1149249), страница 5

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

Текст из файла (страница 5)

, up m 0, что говорит о противоречивостизаданного набора «квантов».1.5ПримерРассмотрим пример учёта нескольких «квантов». Пусть m = 3 и заданыдва «кванта» информации об отношении предпочтения ЛПР2−1u =  2 , v =  −1 .−32Первый учитывается с помощью преобразования с матрицей1 00 1Tu = 3 00 30022.После него второй «квант» выглядит как−1 −1 0v = Tu v =  1 .126Повторное применение теоремы 1.3 даёт преобразованиеTv0 = 001100000011101010010101.Объединяя проделанные преобразования, получаем, что учёт двух «квантов»u, v производится построением нового критерия g = T f , гдеT = Tv0 Tu = 304130030314222222.При построении множества Парето с помощью этого критерия встречается система неравенств вида g(x0 ) ≥ g(x00 ). Однако нетрудно видеть, чтоg4 = 41 g3 + 34 g6 , g5 = 34 g3 + 14 g6 , поэтому данная система неравенств эквивалентна системе аналогичного вида, в которой у g удалены четвёртая и пятаякомпоненты.

Таким образом, простое повторное применение теоремы 1.3 приводит к неоправданно большому росту размерности векторного критерия.1.6Последовательный алгоритм учёта набора«квантов» информацииВ общем случае алгоритм сужения множества Парето выглядит следующим образом. Пусть задан набор «квантов» u10 , . . . , up00 . Обозначим черезm = m0 размерность векторного критерия f .Алгоритм 1. На первом шаге строится матрица T1 , порождённая вектором u10 . Вводится матрица Q1 = T1 . Если p0 = 1, то других «квантов» нет, иалгоритм завершается. Если p0 > 1, то строятся образы оставшихся «кван27тов» T1 u20 , . . . , T1 up00 . Если среди них есть хотя бы один вектор T1 uk0 5 0,алгоритм завершается с предупреждением о противоречивости исходного набора «квантов».

Все векторы T1 uk0 ≥ 0 отбрасываются. Если все векторыоказались отброшены, алгоритм завершается. Если нет, то оставшиеся векторы переобозначаются как u11 , . . . , up11 , и алгоритм переходит на следующийшаг.Пусть проделано s − 1 шагов, построены матрицы Tk размерности mk ×mk−1 , k = 1, s − 1, и известна текущая матрица Qs−1 . Остаются неучтённыps−1ми «кванты» u1s−1 , . . . , us−1. На s-ом шаге строится матрица Ts , порождён1ная вектором us−1 . Вычисляется Qs = Ts Qs−1 . Если ps−1 = 1, то «квантов»больше нет, и алгоритм завершает свою работу.

Если же ps−1 > 1, то строятps−1ся образы «квантов» Ts u2s−1 , . . . , Ts us−1. Если среди получившихся векторовесть такие, которые не имеют строго положительных компонент, то алгоритм завершается с предупреждением о противоречивости исходного набора«квантов». Все векторы, не имеющие отрицательных компонент, удаляются.Оставшиеся переобозначаются как u1s , . . . , upss .

Если векторов не осталось, алгоритм завершается. Если ps > 1, алгоритм переходит к следующему шагу.Алгоритм конечен, так как на каждом шаге s выполняется ps < ps−1 , аp0 — конечное число. Отсюда же видно, что алгоритм сделает не более p0шагов, где p0 — количество исходных «квантов».1.7Нахождение образующих двойственногоконусаКак было видно из рассмотренного примера, в процессе учёта «квантов»могут появляться лишние критерии.

С целью их детектирования рассмотрим связь между построением нового векторного критерия и нахождениемобразующих двойственного конуса.Введём обозначение π(i) для номера исходного «кванта», образ которогоπ(i)учитывался на шаге i: Qi−1 u0 = u1i−1 .Утверждение 1.5. После каждого шага s конусnoπ(1)π(s) 1m0cone u0 , . . . , u0 , em0 , . . .

, em028является двойственным к конической оболочке строк матрицы Qs .Доказательство. Воспользуемся методом математической индукции.База индукции: s = 1. Выберем произвольный вектор x ∈ Rm0 так, чтобыдля любой строки q1i матрицы Q1 = T1 выполнялось q1i x > 0. Другими сло1вами, T1 x = 0, т.

е. T1 x ∈ Rm+ . По утверждению 1.4 с учётом (1.2) получаем,0что x ∈ cone u10 , e1m0 , . . . , emm0 . С другой стороны, всякий вектор x из конуса 1 10cone u0 , em0 , . . . , emm0 удовлетворяет соотношению T1 x = 0, что доказываетбазу индукции.Индукционное предположение состоит в выполнении указанного в условии свойства для всех шагов до s − 1 включительно. Рассмотрим s-ый шагалгоритма. Пусть конус Qs — коническая оболочка строк Qs . Пусть векторsx ∈ Rms : Qs x = 0. Это означает, что Ts Qs−1 x = 0, т. е.

Ts Qs−1 x ∈ Rm+ .mПо утверждению 1.4 отсюда следует, что Qs−1 x ∈ cone u1s−1 , e1ms−1 , ems−1s−1 .π(s)Это значит, что∃α > 0 : Qs−1 x − αu1s−1 = 0. Так как u1s−1 = Qs−1 u0 , тоπ(s)π(s)Qs−1 x − αu0= 0, т. е. вектор x − αu0 принадлежит конусу, двойственному к коническойоболочке строк Qs−1o, а по индукционному предположениюnπ(1)π(s−1) 10это cone u0 , . . .

, u0, em0 , . . . , emm0 . Поэтомуnoπ(1)π(s) 1m0x ∈ cone u0 , . . . , u0 , em0 , . . . , em0 .noπ(1)π(s) 1m0С другой стороны, ∀x ∈ cone u0 , . . . , u0 , em0 , . . . , em0 представим ввидеπ(s)x = αu0 + x0 ,noπ(1)π(s−1) 10m0где α > 0, и вектор x ∈ cone u0 , . . .

, u0, em0 , . . . , em0 . В силу индукционного предположения справедливо Qs−1 x0 = 0. Так как матрица Tsπ(s)π(s)порождена вектором u1s−1 = Qs−1 u0 , то Ts Qs−1 us = 0. В матрице Ts всекомпоненты неотрицательны, поэтому TsnQs−1 x0 = 0. Отсюда следует,o что иπ(1)π(s) 10Ts Qs−1 x = 0, т. е. Qs двойственен к cone u0 , . . . , u0 , em0 , . . . , emm0 .С помощью двойственности несложно доказывается и критерий непротиворечивости набора «квантов» информации.Утверждение 1.6.

Набор «квантов» противоречив тогда и только тогда,когда на некотором шаге s есть «квант» uk , образ которого Qs uk 5 0.Доказательство. Достаточность. Qs −uk = 0, следовательно, вектор−uk принадлежит конусу, двойственному к конической оболочке строк Qs . По29утверждению 1.5 это означает, чтоnoπ(1)π(s) 1m0−u ∈ cone u0 , . . . , u0 , em0 , . . . , em0 ⊆k0⊆ cone u10 , . . .

, up0 , e1m0 , . . . , emm0 ⊆ K,где K — конус отношения предпочтения ЛПР. uk , −uk ∈ K означает, что этотконус не острый, что противоречит теореме 1.1. Таким образом, не можетсуществовать отношения предпочтения, удовлетворяющего всем аксиомам,при котором u1 m 0, . . . , up m 0. По определению 1.12 набор «квантов»противоречив.Необходимость. Предположим, что на каждом шаге алгоритма s нет«квантов» uk , для которых Qs uk 5 0 и докажем, что в этом случае набор«квантов» непротиворечив.Алгоритм за r шагов успешно завершает свою работу построением матрицы Qr . Отметим, что каждая матрица Ts является матрицей полного ранга, т. е.

задаёт инъективное отображение. Следовательно, Qr = Tr Tr−1 . . . T1также задаёт инъективное отображение, является матрицей полного ранга,а значит, её столбцы и строки линейно независимы. Отсюда вытекает, чтодвойственный к конической оболочке строк Qr конус C является острым.Действительно, если бы он не был острым, существовал бы ненулевой векторz ∈ C : − z ∈ C.

Но тогда в силу двойственности Qr z = 0, Qr (−z) = 0,и т. к. суммирование даёт нули в левой части и неотрицательные компоненты в правой, должно выполняться равенство Qr z = 0, что противоречитлинейной независимости столбцов nматрицы Qr . Но конус C oпо утверждеπ(1)π(r)0нию 1.5 есть не что иное как cone u0 , . . . , u0 , e1m0 , . . . , emm0 . Этот конус0совпадает с cone u1 , . .

. , up , e1m0 , . . . , emm0 , т. к. все отброшенные на какомлибо шаге i кванты uj обладают свойством Ti uji−1 = Qi uj ≥ 0, откуда из-заjнеотрицательности nкомпонент матриц Ts следуетo Qr u ≥ 0, и по утверждеπ(1)π(r)0нию 1.5 uj ∈ cone u0 , . . . , u0 , e1m0 , .

. . , emm0 . Если в качестве m взятьконусное бинарное отношение с конусом C\{0}, то окажется, что оно транзитивно, иррефлексивно в силу остроты C, удовлетворяет аксиомам инвариантности и согласованности. Более того, т. к. все «кванты» uk ∈ C, верныравенства uk m 0. Следовательно, набор «квантов» непротиворечив по определению 1.12.301.8Исключение лишних критериевФормализуем понятие лишнего критерия.

Т. к. мы будем пользоватьсятем, что новые критерии суть образующие определённого конуса, введёмопределение лишней образующей.Определение 1.13. Пусть a1 , . . . , ap — образующие некоторого конуса.Вектор ai называется существенной образующей, еслиcone a1 , . . . , ap 6= cone a1 , . . . , ai−1 , ai+1 , . . . , ap .В противном случае образующая ai лишняя.Пусть в процессе учёта квантов получен новый критерий g = Qf размерности l. Рассмотрим коническую оболочку строк матрицы Q. Предположим,что одна из её образующих лишняя, не умаляя общности, пусть это перваястрока q 1 .

Тогда критерий g1 можно удалить, поскольку он на выбор не влияет:g2 (x)g1 (x) g3 (x)  g2 (x)  .  ≥ 0 ⇔  .  ≥ 0. ..  .. gl (x)gl (x)Действительно, из определения 1.13 q 1 ∈ cone q 2 , . . . , q l , следовательно,lPαk q k . Необходимость выполняется, так как тогда∃α2 , . . .

, αl > 0 : q 1 =k=2gk (x) > 0, ∀k = 2, l, и g1 (x) =lPαk gk (x) > 0. Достаточность получаетсяk=2автоматически, стоит лишь заметить, что если g2 (x) = · · · = gl (x) = 0, то иg1 (x) = 0, чего быть не могло.Более того, справедливо и противоположное неравенство:2q vq3v...ql v50⇔1q vq2v...ql v 5 0.Так что исключение лишних критериев не влияет на детектирование противоречивости «квантов».31Утверждение 1.7. Строка q k является лишней образующей коническойоболочки строк матрицы Qs в том и только в том случае, если существуетстрока q l , l 6= k, для которой T q l ⊇ T q k , где множество T(q) = eim0 qeim0 = 0, i = 1, m0 ∪ ui qui = 0, i = 1, s .Доказательство.

Не умаляя общности, для удобства обозначений положим k = 1.Необходимость. Так как q 1 лишняя, она принадлежит конической обоmsPлочке оставшихся строк, значит, ∃α2 , . . . , αms > 0 : q 1 =αi q i . Если в правойi=2части нет ненулевых коэффициентов, то q 1 = 0, но по построению матрицыQs = Ts Ts−1 · · · · · T1 в ней не может быть нулевых строк: все строки матрицTr ненулевые и имеют только неотрицательные компоненты.Пусть в правой части есть положительные коэффициенты, для определённости положим αl > 0.

Характеристики

Список файлов диссертации