Ранжирование объектов по числу пи и L-правилам в ассоциативных матрицах

Формирование автоматизированных справочников по компонентам районных электрических сетей. Рассмотрение методики ранжирования однородных альтернатив по числу пи и L-правилам в ассоциативных матрицах. Алгоритм построения очередей оборудования на ремонт.

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 08.12.2018
Размер файла 152,8 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http: //www. allbest. ru/

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

Ранжирование объектов по числу пи и L-правилам в ассоциативных матрицах

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

Аннотация

СТАТЬЯ ПРЕДЛАГАЕТСЯ ДЛЯ ПУБЛИКАЦИИ В ЭЛЕКТРОННОМ ЖУРНАЛЕ «СИСТЕМОТЕХНИКА»,

СВЕДЕНИЯ ОБ АВТОРАХ:

Кандырин Юрий Владимирович, академик Российской академии надежности, профессор Московского энергетического института, зам директора Центра инженерного проектирования МЭИ, заместитель заведующего кафедрой Радиоприемных устройств МЭИ, автор более 200 научных работ, в том числе 9 учебных пособий для Вузов и 2-х монографий. Проблемами надежности и многокритериального выбора в САПР РЭС занимается более 40 лет. По этой тематике под его руководством защищены 6 кандидатских диссертаций.

Тел. раб.: 362-79-41, Моб: 8-926-560-02-08.Тел. дом.: 360-19-56. E-mail: ywk@mail.ru

Кошелев Александр Михайлович, аспирант Радиотехнического факультета Московского энергетического института. Лауреат открытого конкурса студенческих работ, кавалер медали Министерства образования и науки РФ.

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

ранжирование алгоритм очередь автоматизированный

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

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

Рассмотрим р -правило структурирования альтернатив. На исходном множестве, представленном матрицей реляционного отношения для вариантов

= {i {kl}}; i={1,N}, l= {1,M}

(табл.1) выделяется множество показателей качества (ПК):

{kl}, l={1,M},

назначенных лицом, принимающим решения (ЛПР). Далее производится формирование окрестностей и фактор-множеств [1]. Под окрестностью Оi единичного радиуса элемента i по отношению R будем понимать множество элементов {i*}, доминирующих или эквивалентных i таких, что они могут быть описаны следующим линейным порядком {i*},i R.

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

Варианты

Показатели качества вариантов {kl}

k1

k2

kM

1

k11

k12

k1M

2

k21

k22

k2M

N

kN1

kN2

kNM

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

Оi(/kl) {j : kl(j) kl(i), j, i } (для kl v),

Оi(/kl) {j : kl(j) kl(i), j, i } (для kl ^).

Фактор-множеством ФТ/R (множества по отношению R) называется множество окрестностей единичного радиуса, взятых для всех i

, i={1,N}, т.е. ФТ/kl = {Оi(/kl)}, i = {1,||}.

Знак «Т» отображает транзитивность ФТ/kl .

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

L(/k1): <5, 3, {4, 6}, {1, 2}>,

L(/k2): <4, {1, 2}, {3, 6}, 5>, (1)

L(/k3): <6, 5, 1, 4, 2, 3>.

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

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

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

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

Для данного примера фактор-множества ФТ/k1, ФТ/k2, ФТ/k3 по соответствующим показателям качества представлены в табл. 2, 3 и 4, соответственно.

Таблица 2 Представление фактор-множества ФТ/k1 для L(/k1)

i

Oi(/k1)

1

2, 3, 4, 5, 6

2

1, 3, 4, 5, 6

3

5

4

3, 5, 6

5

6

3, 4, 5

Таблица 3 Представление факор-множества ФТ/k2 для L(/k2)

i

Oi(/k2)

1

2, 4

2

1, 4

3

1, 2, 4, 6

4

5

1, 2, 3, 4, 6

6

1, 2, 3, 4

Таблица 4 Представление фактор-множества ФТ/k3 для L(/k3)

i

Oi(/k3)

1

5, 6

2

1, 4, 5, 6

3

1, 2, 4, 5, 6

4

1, 5, 6

5

6

6

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

ФТ/{k1,k2...kM} = ФТ/k1 ? ФТ/k2 ?··? ФТ/ kM (2)

В примере, заданном выражением (1) фактор-множества ФТ/k1, ФТ/k2, ФТ/k3 и ФТ/{k1, k2, k3} сведены в таблицу 5, иллюстрируя выражение (2). В таблице, серым цветом выделен столбец фактор-множества, содержащего нехудшие решения для р- критерия. Итак, нехудшими альтернативами Щ в -постановке (Щ/{k1, k2, k3}) являются 1, 3, 4, 5, 6.

Таблица 5 Представление фактор-множеств ФТ/k1, ФТ/k2, ФТ/k3 и ФТ/{k1, k2, k3}

i

ФТ/{k1})

ФТ/{k2})

ФТ/{k3})

ФТ/{k1, k2, k3})

1

2, 3, 4, 5, 6

2, 4

5, 6

2

1, 3, 4, 5, 6

1, 4

1, 4, 5, 6

1, 4

3

5

1, 2, 4, 6

1, 2, 4, 5, 6

4

3, 5, 6

1, 5, 6

5

1, 2, 3, 4, 6

6

6

3, 4, 5

1, 2, 3, 4

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

Oi(Щ/{k1,k2...kM}) = Oi(Щ/k1) ? Oi(Щ/k2) ?·····? Oi(Щ/kM), (3)

ФТ/{k1,k2...kM} = O1(Щ/{k1,k2...kM}) O2(Щ/{k1,k2...kM}) … ON(Щ/ k1,k2...kM). (4)

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

Таблица 6 Ассоциативная матрица фактор-множества линейного порядка L(/kj)

Окрестности\ Альтернативы

O1(1)

O2(2)

ON(N)

1

0

B12

B1N

2

B21

0

B2N

...

N

BN1

0

Здесь каждый столбец задаёт окрестность Oi(i) i -го варианта. Совокупность всех окрестностей по kl представляет собой транзитивное фактор-множество ФТ/kl . Вхождение варианта в соответствующую окрестность идентифицируется «1» в данной ячейке, отсутствие - «0». Так, если вариант входит в окрестность i -ой альтернативы, то элемент ассоциативной матрицы Bi,j = 1, и Bi,j = 0, если - не входит. В ассоциативной форме, окрестности представляют собой столбцы ассоциативной матрицы и, матрица результирующего фактор-множества для выбранных показателей качества формируется в виде последовательного поэлементного пересечения столбцов ассоциативных матриц фактор-множеств меньшей размерности

, l = {1, M}. (5)

Все приведенные рассуждения строго справедливы для безусловных неметрических -критериев. Причем, порядок пересечения фактор-множеств более низкой размерности для -критерия неважен в силу безусловности критерия Парето. В отличие от р-критерия, L-критерий является условным, следовательно, порядок всех последующих пересечений ассоциативных матриц для ПК будет влиять на результат. Исходя из определения, приведенного в [1], каждый последующий применяемый ПК раскрывает неопределенность между альтернативами

по предыдущим ПК или критериям, следовательно, поэлементное произвольное (независимое от порядка) пересечение по выражению (5) - невозможно.

Cформулируем определение L-правила пересечения Oli .

Утверждение 1:

Пусть имеется два фактор-множества ФТ/k1, ФТ/k2. Назовем окрестностью OiН(Щ/<k1,k2>) неразличимых вариантов {щi-1, щi} по < k1,k2> выражение

OiН(Щ/<k1,k2>)) = [(Oi(Щ/ k1) ? Oi+1(Щ/ k1)) (Oi(Щ/ k1) ? Oi(Щ/ k2))]. (6)

Окрестность сравнимых вариантов OiС(Щ/<k1,k2>) определяется как

OiС(Щ/<k1,k2>) = Oi (Щ/k1),

где i - не является индексом несравнимого варианта. (7)

Тогда определим полное транзитивное фактор-множество ФТ/<k1,k2> как результат пересечения ФТ/k1, ФТ/k2 в виде совокупности окрестностей несравнимых и сравнимых вариантов

ФТ/<k1, k2> = OiН(Щ/<k1,k2>) OiС(Щ/<k1,k2>) (8)

Проиллюстрируем L-правило небольшим примером. Пусть линейные порядки по каждому из показателей качества заданы (1) и требуется решить задачу выбора в L-критериальной постановке L(/<k1, k2>). Фактор-множества порядков L(/k1), L(/k2) приведены в табл. 2 и табл.3, соответственно. Выделяем неразличимые по k1 группы альтернатив - это {щ1, щ2} и {щ4, щ6} (табл. 7). Пересекая, по правилу (6), окрестности неразличимых вариантов по k1, получаем:

Рис. 4 Выделение неразличимых по k1 групп альтернатив

O4Н(/<k1, k2>) = (O4(/k1) ? O6(/k1)) (O4(/k1) ? O4(/k2)) = ({3, 5, 6} ? {3, 4, 5}) ({3, 5, 6} ? {}) = {3, 5} {} = {3, 5},

O6Н(/<k1, k2>) = (O6(/k1) ? O4(/k1)) (O6(/k1) ? O6(/k2)) = ({3, 4, 5} ? {3, 5, 6}) ({3, 4, 5} ? {1, 2, 3, 4}) = {3, 5} {3, 4} = {щ3, щ4, щ5}.

Следовательно, неразличимость по k1 в отношении {щ4, щ6} устранена. Повторяя все вышеизложенное для альтернатив {щ1, щ2} получаем

O1Н(/<k1, k2>) = (O1(/k1) ? O2(/k1)) (O1(/k1) ? O1(/k2)) = ({2, 3, 4, 5, 6} ? {1, 3, 4, 5, 6}) ({2, 3, 4, 5, 6} ? {2, 4}) = {3, 4, 5, 6} {2, 4} = {2, 3, 4, 5, 6},

O2Н(/<k1, k2>) = (O2(/k1) ? O1(/k1)) (O2(/k1) ? O2(/k2)) = ({1, 3, 4, 5, 6} ? {2, 3, 4, 5, 6}) ({2, 3, 4, 5, 6} ? {1, 4}) = {3, 4, 5, 6} {1, 4} = {1, 3, 4, 5, 6}.

Неразличимость не раскрыта. Остальной порядок неопределенностей не содержит, следовательно, остальные окрестности фактор-множества ФТ/<k1, k2>, строго равны окрестностям фактор-множества ФТ/k1 (см. выражение (7), (8)). Таким образом, согласно (8), фактор-множество

В таблицу 8 сведены все окрестности фактор-множества ФТ/<k1, k2> для вариантов {i}, i = {1, 6}. Квазилинейный порядок, соответствующий этому фактор-множеству, следующий:

ФТ/<k1, k2> = {O1(/<k1, k2>), O2(/<k1, k2>), O3(/<k1, k2>), O4(/<k1, k2>), O5(/<k1, k2>), O6(/<k1, k2>)}.

L(/{k1, k2}) = <5, 3, 4, 6, {1, 2}> (9)

Таблица 7 Представление фактор-множества ФТ/< k1,k2>

i

Oi(/<k1, k2>)

1

2, 3, 4, 5, 6

2

1, 3, 4, 5, 6

3

5

4

3, 5

5

6

3, 4, 5

Теперь решим эту же задачу классическим способом, описанным в [1]. Линейный порядок L(/k1) задан выражением (1). Раскрываем неопределенности с помощью показателя качества k2. Альтернативы 1, 2 по данному показателю неразличимы, поэтому неопределенность раскрыть не удаётся. Значение k2(4) ? k2(6), следовательно {4, 6} раскрывается в <4, 6>. Тогда квазилинейный порядок для двух ПК в приоритете < k1, k2> можно представить в виде

L(/<k1, k2>) = <5, 3, 4, 6, {1, 2}> (10)

Сравнивая (9) и (10) убеждаемся, что частичные порядки идентичны, следовательно, пересечение фактор-множеств по L-правилу дает верный результат, а значит, Утверждение 1 можно считать верным.

Автоматизацию описанных процедур наиболее эффективно проводить в ассоциативной модели данных. В бинарном представлении, пересечение фактор-множеств ФТ/k1 и ФТ/k2 реализуется через поэлементное пересечение ассоциативных матриц А1 и А2 соответственно. Так как, неразличимые варианты {щi-1, щi} характеризуются значениями «1», стоящими симметрично, относительно главной диагонали матрицы (табл.6), то элементы матрицы А12 фактор-множества

ФТ/<k1, k2> можно определить как

(11)

где aij1 - элемент ассоциативной матрицы A1 фактор-множества ФТ/k1, aij2 - элемент ассоциативной матрицы A2 фактор-множества ФТ/k2, aij - элемент ассоциативной матрицы A12 фактор-множества ФТ/{k1, k2}.

Из выражения (11) видно, что процесс формирования пересечения по L-правилу, в бинарном виде проще, т.к. требует значительно меньше операторов.

Проиллюстрируем полученное правило примером. Пусть линейные порядки заданы выражениями (1) и требуется решить задачу выбора в соответствии с L(/<k1,k2>) -правилом. Ассоциативные матрицы фактор-множеств порядков L(/k1), L(/k2) показаны в таблицах 9 и 10 соответственно. В табл. 9 цветом выделены элементы, соответствующие неразличимым вариантам по k1.

Таблица 8 Ассоциативная матрица фактор-множества ФТ/ k1

Окрестности\ Альтернативы

O1(i)

O2(i)

O3(i)

O4(i)

O5(i)

O6(i)

1

0

1

0

0

0

0

2

1

0

0

0

0

0

3

1

1

0

1

0

1

4

1

1

0

0

0

1

5

1

1

1

1

0

1

6

1

1

0

1

0

0

В результирующую матрицу (таблица 11) подставляются (см. 11) все элементы из таблицы 8 кроме тех, что выделены цветом. В этих позициях итоговой матрицы элементы определяются по нижней части выражения (11).

Таблица 9 Ассоциативная матрица фактор-множества ФТ/ k2

Окрестности Альтернативы

O1(i)

O2(i)

O3(i)

O4(i)

O5(i)

O6(i)

1

0

1

1

0

1

1

2

1

0

1

0

1

1

3

0

0

0

0

1

1

4

1

1

1

0

1

1

5

0

0

0

0

0

0

6

0

0

1

0

1

0

a21рез = a211 ? a212 =1 ? 1 = 1,

a12рез = a121 ? a122 =1 ? 1 = 1,

a64рез = a641 ? a642 =1 ? 0 = 0,

a46рез = a461 ? a462 =1 ? 1 = 1.

Таблица 10 Ассоциативная матрица фактор-множества ФТ/< k1, k2>

Окрестности\ Альтернативы

O1(i)

O2(i)

O3(i)

O4(i)

O5(i)

O6(i)

1

0

1

0

0

0

0

2

1

0

0

0

0

0

3

1

1

0

1

0

1

4

1

1

0

0

0

1

5

1

1

1

1

0

1

6

1

1

0

0

0

0

Квазилинейный порядок, соответствующий данной матрице результирующего фактор-множества, выглядит, как и полученный ранее в реляционных структурах (10):

L(/{k1, k2}) = <5, 3, 4, 6, {1, 2}> (11)

Выводы

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

Литература

1. Кандырин Ю.В. Методы и модели многокритериального выбора вариантов в САПР. Учебное пособие для вузов. М.: Издательство МЭИ, 2004г. -172с.

2. Кандырин Ю.В., Кошелев А.М. Алгоритмы установления приоритетов объектов по техническим показателям в целях назначения оптимальной очередности их ремонтов. М: Издательство Машиностроение, журнал «Вестник информационных и компьютерных технологий», №7, 2006.

3. С.18-25.

4. Кандырин Ю.В. Принципы построения информационных систем для автоматизированного многокритериального выбора. -М.: Журнал “Радиотехника”, 1999г. № 5. -С. 32-37

Размещено на Allbest.ru


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.