Правилам в ассоциативных матрицах

Скачать 229.77 Kb.

Название	Правилам в ассоциативных матрицах
страница	1/3
Тип	Документы

1 2 3

Проф. Ю.В. Кандырин, асп. А.М. Кошелев

РАНЖИРОВАНИЕ ОБЪЕКТОВ ПО π и L-ПРАВИЛАМ В
АССОЦИАТИВНЫХ МАТРИЦАХ

Московский энергетический институт (ТУ)

АННОТАЦИЯ

В статье рассмотрена методика ранжирования однородных альтернатив по π и L- правилам в ассоциативных структурах данных для фактор-множеств. Такие задачи возникают при формировании критериально-структурированных автоматизированных справочников по компонентам РЭС, построении очередей на ремонт и др. Предлагаемый подход минимизирует число булевых операций в алгоритмах и позволяет решать задачи практически любых размерностей.
Актуальность задач упорядочивания вариантов в однородных множествах по принятым правилам чрезвычайно широка. Это и решение оптимизационных задач посредством нахождения концевых элементов в частичных и линейных порядках, и проектирование критериально-структурированных справочников для САПР, и формирование очередей на ремонт сложного оборудования.

В представленной работе предложены π и L - правила ранжирования вариантов с помощью аппарата фактор-множеств в ассоциативных матрицах.

Рассмотрим π -правило структурирования альтернатив. На исходном множестве, представленном матрицей реляционного отношения для вариантов
 = {_i{k_l}}; i={1,N}, l= {1,M}(табл.1) выделяется множество показателей качества (ПК): {k_l}, l={1,M}, назначенных лицом, принимающим решения (ЛПР). Далее производится формирование окрестностей и фактор-множеств [1]. Под окрестностью О_i единичного радиуса элемента _i по отношению R будем понимать множество элементов {_i*}, доминирующих или эквивалентных _iтаких, что они могут быть описаны следующим линейным порядком {_i*},_i R.

Таблица 1.

Исходное множество альтернатив в виде реляционного отношения

Варианты	Показатели качества вариантов {k_l}
Варианты	k₁	k₂	…	k_M
₁	k₁₁	k₁₂	…	k₁_M
₂	k₂₁	k₂₂	…	k₂_M
…	…	…	…	…
_N	k_N₁	k_N₂	…	k_NM

Очевидно, что окрестностью минимальных элементов является пустое множество - . Отношение R определяет доминирование альтернатив при их бинарном сравнении. Это отношение может задаваться критериями Парето (π), Слейтера (S), лексикографическим L-критерием, а также метрическими свертками. Окрестность О_i по k_l по π -критерию определяется соотношениями

О_i(/k_l)  {_j : k_l(_j)  k_l(_i), _j, _i  } (для k_l ↓),

О_i(/k_l)  {_j : k_l(_j)  k_l(_i), _j, _i  } (для k_l ↑).

Фактор-множеством Ф^Т_/R (множества  по отношению R) называется множество окрестностей единичного радиуса, взятых для всех _i , i={1,N}, т.е. Ф^Т_/k_l = {О_i(/k_l)}, i = {1,||}. Знак «Т» отображает транзитивность Ф^Т_/k_l.

Поясним методику формирования фактор-множеств и окрестностей на примере. Пусть все показатели качества приведены к минимизации, а линейные порядки вариантов по k_l : {L(/k_l)} на , l = 3 заданы по условию задачи в виде

L(/k₁): <₅, ₃, {₄, ₆}, {₁, ₂}>,

L(/k₂): <₄, {₁, ₂}, {₃, ₆}, ₅>, (1)

L(/k₃): <₆, ₅, ₁, ₄, ₂, ₃>.

Графически, проекции альтернатив на двойки показателей качества {k₁, k₂}, {k₁, k₃}, {k₂, k₃} представлены на рис. 1, 2 и 3, соответственно.

Рис. 1. Проекции альтернатив на двойку {k₁, k₂}

Рис. 2. Проекции альтернатив на двойку {k₁, k₃}

Рис. 3. Проекции альтернатив на двойку {k₂, k₃}

Для данного примера фактор-множества Ф^Т_/k₁, Ф^Т_/k₂, Ф^Т_/k₃ по соответствующим показателям качества представлены в табл. 2, 3 и 4, соответственно.

Таблица 2.

Представление фактор-множества

Ф^Т_/k₁ для L(/k₁)

_i	O_i(/k₁)
₁	₂, ₃, ₄, ₅, ₆
₂	₁, ₃, ₄, ₅, ₆
₃	₅
₄	₃, ₅, ₆
₅	
₆	₃, ₄, ₅

Таблица 3.

Представление факор-множества

Ф^Т_/k₂ для L(/k₂)

_i	O_i(/k₂)
₁	₂, ₄
₂	₁, ₄
₃	₁, ₂, ₄, ₆
₄	
₅	₁, ₂, ₃, ₄, ₆
₆	₁, ₂, ₃, ₄

Таблица 4.

Представление фактор-множества

Ф^Т_/k₃ для L(/k₃)

_i	O_i(/k₃)
₁	₅, ₆
₂	₁, ₄, ₅, ₆
₃	₁, ₂, ₄, ₅, ₆
₄	₁, ₅, ₆
₅	₆
₆	

В [1], [2] показано, что результирующие фактор-множества по Парето с большей размерностью, для совокупности показателей качества {k_M}, l ={1, M}, определяются последовательным пересечением фактор-множеств меньшей размерности:

Ф^Т_/{k₁,k₂...k_M} = Ф^Т_/k₁ ∩ Ф^Т_/k₂ ∩··∩ Ф^Т_/ k_M (2)

В примере, заданном выражением (1) фактор-множества Ф^Т_/k₁, Ф^Т_/k₂, Ф^Т_/k₃ и Ф^Т_/{k₁, k₂, k₃} сведены в таблицу 5, иллюстрируя выражение (2). В таблице, серым цветом выделен столбец фактор-множества, содержащего нехудшие решения для π- критерия. Итак, нехудшими альтернативами Ω_ в -постановке (Ω/{k₁, k₂, k₃}) являются ₁, ₃, ₄, ₅, ₆.

Таблица 5.

Представление фактор-множеств Ф^Т_/k₁, Ф^Т_/k₂, Ф^Т_/k₃ и Ф^Т_/{k₁, k₂, k₃}

_i	Ф^Т_/{k₁})	Ф^Т_/{k₂})	Ф^Т_/{k₃})	Ф^Т_/{k₁, k₂, k₃})
₁	₂, ₃, ₄, ₅, ₆	₂, ₄	₅, ₆	
₂	₁, ₃, ₄, ₅, ₆	₁, ₄	₁, ₄, ₅, ₆	₁, ₄
₃	₅	₁, ₂, ₄, ₆	₁, ₂, ₄, ₅, ₆	
₄	₃, ₅, ₆		₁, ₅, ₆	
₅		₁, ₂, ₃, ₄, ₆	₆	
₆	₃, ₄, ₅	₁, ₂, ₃, ₄		

В свою очередь, результирующая окрестность определяется пересечением окрестностей O_i соответствующих альтернатив ω_i

O_i(Ω/{k₁,k₂...k_M}) = O_i(Ω/k₁) ∩ O_i(Ω/k₂) ∩·····∩ O_i(Ω/k_M), (3)

Ф^Т_/{k₁,k₂...k_M} = O₁(Ω/{k₁,k₂...k_M})  O₂(Ω/{k₁,k₂...k_M})  … O_N(Ω/ k₁,k₂...k_M). (4)

Для бинарного представления процесса формирования фактор-множеств, а также в целях оптимизации хранения данных в электронных базах данных в [2] введено понятие ассоциативной матрицы фактор-множества, имеющей вид, показанный в табл. 6.

1 2 3

Похожие:

	Детские пособия – 2012 По выбору будущей мамы пособие рассчитывается бухгалтером по старым или новым правилам. Расчет по старым правилам в большинстве случаев...		Страховой продукт «от стечения обстоятельств» по страхованию имущества... Правилами страхования имущества граждан, утвержденные Приказом Председателя Правления ОАО «согаз» №533 от 11. 12. 2008г. (далее –...
	Комментарий к Правилам дорожного движения и основам расследования дтп Суняев Л. В. Комментарий к Правилам дорожного движения и основам расследования дтп. Система гарант, 2007		К Правилам обращения за пенсией
	К Правилам регистрации автомототранспортных		К Правилам комплексного банковского обслуживания Клиентов юридических... Правилам комплексного банковского обслуживания Клиентов – юридических лиц, индивидуальных предпринимателей, а также физических лиц,...
	К Правилам комплексного банковского обслуживания Клиентов юридических... Правилам комплексного банковского обслуживания Клиентов – юридических лиц, индивидуальных предпринимателей, а также физических лиц,...		К Правилам заполнения перевозочных документов
	Правилам открытия и обслуживания текущих счетов физических лиц для... Приложение №2 к Правилам открытия и обслуживания текущих счетов физических лиц для совершения расчетных операций		Правилам открытия и обслуживания банковских счетов

Вы можете разместить ссылку на наш сайт:

Все бланки и формы на filling-form.ru