ДВА ПОДХОДА К СТРУКТУРИРОВАНИЮ АЛЬТЕРНАТИВ
Ю.В. Кандырин, Г.Л. Шкурина
9 СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ
УДК 68.5.01:658.512.2.011.56
ДВА ПОДХОДА К СТРУКТУРИРОВАНИЮ АЛЬТЕРНАТИВ
Ю.В. Кандырин, Г.Л. Шкурина
Предложены модели формирования частичных порядков альтернатив при условии их линейного упорядочивания по требуемым показателям качества. Рассмотрены методы, основанные на формировании результирующего частичного порядка с помощью графов Бержа и на преобразованиях окрестностей фактор-множеств. Разработка указанных подходов необходима для критериального структурирования вариантов объектов при многокритериальном выборе альтернатив. Ключевые слова: задачи выбора, оптимальные варианты, линейное и частичное упорядочивание альтернатив, критериальное структурирование объектов.
Введение
При проектировании автоматизированных систем поддержки принятия решений практически важным вопросом является формирование структуры альтернатив, нацеленной на оптимизацию выбора оптимальных в том или ином смысле вариантов.
Использование рационально организованных структур хранения данных в системах автоматизированного выбора позволяет существенно более эффективно решать задачи многокритериального выбора, значительно экономить машинное время на поиск информации, так как процедура выбора в этом случае будет начинаться с оптимальных вариантов. При этом такая вновь создаваемая структура данных должна отражать заложенную лицом, принимающим решение (ЛПР), объективную картину предпочтений, задаваемую частичным или линейным порядком альтернатив [1].
Постановка задачи
Описываемый подход основан на наделении множества возможных вариантов ={i}, i={1, N} структурой, отражающей критериальные требования {C}. В этом случае решением задачи выбора будут максимальные элементы множества , частично (или линейно) упорядоченного отношением RK, задающим предпочтения среди альтернатив. Отношение RK задается тем или иным критерием выбора, назначаемым ЛПР в качестве целеполагания.
Предлагаемое решение – это, прежде всего, качественно новый подход. Исходное множество альтернатив представляется проектировщику упорядоченным в соответствии с его целевыми устремлениями, которые формально выражены через критериальные постановки. Известно [1], что основные принципы оптимальности подразделяются на два различных класса оптимизационных задач: неметрические и метрические. Основной недостаток неметрических безусловных критериев оптимальности в том, что они не позволяют корректно и точно разрешить проблему устойчивости решений и обладают меньшей силой, по сравнению с метрическими постановками. При этом принцип оптимальности RKi сильнее RKj или RKi RKj, если 0i 0j, где 0i RKi ()и 0j RKi ().
Важнейшую информацию о степени противоречивости целей при выборе из множества возможных альтернатив (МВА) дает вид распределения предпочтительности альтернатив по различным критериальным постановкам. При выборе появляется возможность оперативной оценки потерь при отступлении от оптимальных решений. И еще одним достоинством описываемого подхода является высокая эффективность оптимизационных процедур. Последнее связано с тем, что решение задачи выбора на соответствующем упорядоченном множестве фактически сводится к проверке допустимости решений по условиям и ограничениям только для максимальных элементов [2]. Такие задачи особенно актуальны для создания автоматизированных справочников по элементной базе в единой системе автоматизированного проектирования (САПР), где от задачи к задаче сохраняются устойчивые критериальные и функционально ориентированные постановки задач выбора для компонентов.
Первый подход к решению задачи
Эффективность предложенного подхода можно обеспечить, решив задачи получения необходимых частичных порядков высоких размерностей на основе преобразований базовых линейных или частичных порядков малых размерностей. Структурирование альтернатив отражают целеполагание ЛПР, хотя математические модели структурирования могут быть различными.
Первый подход основан на применении графов Бержа, позволяющих представить частично упорядоченные множества совокупностью линейно упорядоченных множеств, а второй – на формировании результирующих частично упорядоченных множеств с помощью фактор-множеств линейных порядков
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)
107
ДИСКРЕТНЫЕ ВОЛНЫ ПЕРЕКЛЮЧЕНИЯ И ДИССИПАТИВНЫЕ СОЛИТОНЫ …
вариантов. Основной концептуальный смысл и порядок переструктурирования альтернатив на множестве возможных вариантов (МВА ) можно графически интерпретировать (рисунок) как настройку базы данных на конкретную задачу выбора в соответствии с ее пониманием ЛПР.
MBA Ω
L (Ω/k1)
L (Ω/k2)
… L (Ω/km)
Задание ЛПР критериев
структурирования
G (Ω, U)
Рисунок. Формирование адаптивного частичного порядка G (, U) в соответствии с целевой постановкой задачи выбора из линейных порядков альтернатив
Рассмотрим математическую модель представления частично упорядоченного множества совокупностью линейно упорядоченных множеств, которые описываются графами [2].
Пусть частично упорядоченному множеству /Rk соответствует транзитивный граф Бержа G = , где UD1 = {i, j, если i j, i j {1, N}}.
Обозначим:
G = – обыкновенный (неориентированный) граф, полученный из G = заменой сигнатуры UD2 на UD1 при сохранении носителя ; при этом UD2 = {{i, j}, если (i j) (j i), i j {1, N}};
G = – обыкновенный граф, «дополнительный» к G = , сигнатура которого UD1 яв-
ляется дополнением сигнатуры UD2, т.е. UD2 UD1 = , а UD2 UD1 = ;
GA = < , UA >, GB = – графы Бержа – транзитивные турниры, соответствующие линейно упорядоченным множествам /UA и /UB;
GT = – граф Бержа, который является транзитацией (транзитивной ориентацией) обыкновенного графа G = , если орграф GT = , полученный в результате ориентации всех ребер из UD1 графа G = , является транзитивным;
GT = – противоположная GT = транзитация графа G, т.е. для i j {1, N} из UT следует UT.
Под объединением и пересечением графов Gi= и Gj = следует понимать
операции объединения и пересечения носителей i, j и сигнатур Ui, Uj. Таким образом, показаны не только необходимые и достаточные условия для представления час-
тично упорядоченного множества двумя линейно упорядоченными множествами.
Граф частичного порядка G можно представить в виде пересечения двух графов линейных порядков GA и GB тогда и только тогда, когда существует транзитация GT дополнительного графа G, или, в формализованном виде,
G = GA GB, если GT для G,
(1)
108
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)
Ю.В. Кандырин, Г.Л. Шкурина
что является необходимыми и достаточными условиями для представления частично упорядоченного множества двумя линейно упорядоченными множествами.
Если выполнено условие (1), то орграфы линейных порядков GA и GB определяются как объединения исходного графа частичного порядка G и противоположных транзитаций графа G :
GA = G GT; GB = G GT.
Из линейных порядков диаграмм Хассе HA и HB может быть восстановлен граф частичного порядка более высокой размерности G. Очевидно, что в нем концевые, недоминируемые вершины графа {1, 2} оптимальны по Парето (для минимизации), что является способом нахождения частично упорядоченного множества. Такое представление используется, в частности, для специального кодирования. Последнее дает возможность получить код, позволяющий эффективно находить задачи выбора по концевым вершинам [3].
Второй подход к решению задачи
Следующий подход предполагает использование математических моделей, основанных на описа-
нии множеств возможных вариантов с помощью фактор-множеств (/R). По определению фактор
множеством называется множество окрестностей единичного радиуса, взятых для всех i , i={1, N}. Под окрестностью Оi элемента i будем понимать множество элементов {i*}, доминирующих или эквивалентных i таких, что они могут быть описаны следующим линейным порядком: {i*}, i R (для min) [3]. Очевидно, что окрестностью минимальных элементов является пустое множество. В самом общем виде это отношение R может задаваться критериями Парето, Слейтера и т.д. [1, 2].
Пусть в качестве правила сравнения вариантов принимается критерий Парето, позволяющий устанавливать частичные порядки с минимумом требуемой начальной информации. Определим окрестность
Оi в фактор-множестве по показателю качества kl как Оi (/kl) {j: kl (j) kl (i), j, i }. Тогда фактор-множество /kl можно представить как совокупность окрестностей (/kj) = {Оi (/kl)}, i = {1, ||}, l={1, M}.
Рассмотрим пересечение окрестностей Оi (/k1) и Оi (/k2) для альтернативы i по показателям качества k1 и k2:
Oi (/k1) Oi (/k2) = {i: k1 (i) kj1 (j), l, j } {i: k2 (i) k2 (j),
i, j } = {i: [k1 (i) k1 (j)] [k2 (i) k2 (j)], l, j }. Продолжая для l={1, M}, получаем:
Oi (/kl) = {i: kl (l) kl (j), l{1, M}, j, i }.
(2)
И, если Oi (/kl) = , то i – вариант, не доминируемый любым j . При этом i – оптимальный вариант по принятому критерию Парето.
{k1, … kM} = {i: Oi (/kl, l {1, M}) = }.
Таким образом, решение для -постановки вида (/{k1,…, kM}) определяется пересечением окрестностей фактор-множеств для порядков альтернатив по всем показателям качества из выделенной совокупности {k1, …, kM}. Для автоматизации решения задач построения критериально структурированных множеств необходимо, чтобы методы решения задач были тесно увязаны с моделями хранимых данных об альтернативах, важна и компактность хранения информации, и оптимальные пути доступа к ней. Этим требованиям наиболее полно удовлетворяют ассоциативные матрицы (АМ), как показано в таблице.
Альтернативы i
1 2 … N
О1 (i) 0
B21 … BN1
Окрестности Оi (i)
О2 (i)
…
B12 … 0…
……
BN2 …
ОN (i)
B1N B2N …
0
Таблица. Ассоциативная матрица Al фактор-множества Ф(/kl) линейного порядка L(/kl)
В строках АМ располагаются альтернативы, а столбцы отображают окрестности. Если альтерна-
тива i доминирует альтернативу k , то элемент ассоциативной матрицы Bij принимает значение «1». Иначе говоря,
0, Вij 0,
1,
j i , i j; j i ,
j,i L( kl ), j,i L( kl ),
j i , j i ,
l 1, M ; l 1, M .
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)
109
ДИСКРЕТНЫЕ ВОЛНЫ ПЕРЕКЛЮЧЕНИЯ И ДИССИПАТИВНЫЕ СОЛИТОНЫ …
Естественно, что элементы, стоящие на главной диагонали, всегда принимают значение «0», так
как альтернатива не может войти в окрестность самой себе. Если альтернативы i, j несравнимы по данному показателю качества, то элементы Bij, Bji принимают значение «1». В остальных случаях элементы, расположенные симметрично относительно главной диагонали, связаны отношением отрицания Bij = Bji. Рассмотрим далее основные свойства фактор-множеств, которые представляются совокупностью АМ.
1. АМ всегда имеют размер NN, т.е. являются квадратными. Так как в строках матрицы отложены альтернативы, а в столбцах – их окрестности и количество окрестностей всегда совпадает с количеством альтернатив, то число строк равно числу столбцов.
2. Элементы ассоциативной матрицы Al, min, Bij, Bji равны тогда и только тогда, когда альтернативы i , j несравнимы по kl. Перейдем к получению решения задачи выбора оптимальных по -критерию. Для этого, как сле-
дует из выражения (2) необходимо реализовать пересечение фактор-множеств всех назначенных ЛПР показателей качества. Рассмотрим пересечение столбцов Сl1 и Cl2 произвольных ассоциативных матриц Al1, max, Al2, max фактор множеств
B1
Сl1
Сl2
=
B2
B1
B2
G1
=
G2
,
... ... ...
BN l1 BN l2 GN
где Gi = (Bi)l1 (Bi)l2 , i = {1, N}.Очевидно, что результат будет аналогичным для всех столбцов АМ.
Окончательно, для всех АМ l {1, M} фактор-множеств показателей качества Ф (/kl) получаем
выражение, определяющее результирующую ассоциативную матрицу (РАМ) Aрез, 1, 2.., m :
Gij = B1ij B2ij … BMij, i, j = {1, N}.
(3)
Формализованное выражение (3) назовем -правилом пересечения ассоциативных матриц фактор-
множеств. Основная особенность пересечения по -правилу – обладание свойством свободной переста-
новки пересекаемых элементов. Альтернатива i включается во множество нехудших решений, если для столбца, т.е. для окрестности Оi(i/{k1, ...,kM}) альтернативы i, выполняется условие
N Gi, j 0.
j 1
Заключение
Решение задачи выбора математической модели для критериального априорного структурирования альтернатив дает возможность адаптировать структуры данных к их целевому использованию при решении задач многокритериального выбора. Структурирование вариантов основано на композиции порядков более низкого уровня в частичные порядки более высокого уровня. Само преобразование структур осуществляется в соответствии с рассмотренными выше правилами. Предложенные подходы составляют методику структурирования и выбора рациональных вариантов. Она реализована на практике в программных комплексах: «Выбор 12М», «Choоse» и «Ряд», разработанных в Московском энергетическом институте (техническом университете) и внедренных на ряде предприятий и в вузах.
Литература
1. Кандырин Ю.В., Шкурина Г.Л., Сазонова Л.Т. Решение задач многокритериального выбора по последовательно принимаемым SpL-критериям // Концептуальное проектирование в образовании, технике и технологии: Межвуз. сб. науч. тр. – Волгоград: ВолгГТУ, 2000. – С. 96–100.
2. Кандырин Ю.В., Московский А.Е., Шкурина Г.Л. Методика формирования оптимальных очередей ремонтов по техническим характеристикам объектов // Известия ВолгГТУ. Проблемы управления, вычислительной техники и информатики в технических системах. – 2007. – № 2 (28). – С. 95–99.
3. Кандырин Ю.В., Сазонова Л.Т., Шкурина Г.Л. Математические модели структурирования альтернатив для решения задач выбора в САПР // Известия ВолгГТУ. – 2011. – № 3 (76). – С. 111–115.
Кандырин Юрий Владимирович – Национальный исследовательский университет «Московский энергетиче-
ский институт», кандидат технических наук, профессор, ywk@mail.ru
Шкурина Галина Леонидовна
– Волгоградский государственный технический университет, кандидат тех-
нических наук, доцент, shgl@bk.ru
110
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)
9 СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ
УДК 68.5.01:658.512.2.011.56
ДВА ПОДХОДА К СТРУКТУРИРОВАНИЮ АЛЬТЕРНАТИВ
Ю.В. Кандырин, Г.Л. Шкурина
Предложены модели формирования частичных порядков альтернатив при условии их линейного упорядочивания по требуемым показателям качества. Рассмотрены методы, основанные на формировании результирующего частичного порядка с помощью графов Бержа и на преобразованиях окрестностей фактор-множеств. Разработка указанных подходов необходима для критериального структурирования вариантов объектов при многокритериальном выборе альтернатив. Ключевые слова: задачи выбора, оптимальные варианты, линейное и частичное упорядочивание альтернатив, критериальное структурирование объектов.
Введение
При проектировании автоматизированных систем поддержки принятия решений практически важным вопросом является формирование структуры альтернатив, нацеленной на оптимизацию выбора оптимальных в том или ином смысле вариантов.
Использование рационально организованных структур хранения данных в системах автоматизированного выбора позволяет существенно более эффективно решать задачи многокритериального выбора, значительно экономить машинное время на поиск информации, так как процедура выбора в этом случае будет начинаться с оптимальных вариантов. При этом такая вновь создаваемая структура данных должна отражать заложенную лицом, принимающим решение (ЛПР), объективную картину предпочтений, задаваемую частичным или линейным порядком альтернатив [1].
Постановка задачи
Описываемый подход основан на наделении множества возможных вариантов ={i}, i={1, N} структурой, отражающей критериальные требования {C}. В этом случае решением задачи выбора будут максимальные элементы множества , частично (или линейно) упорядоченного отношением RK, задающим предпочтения среди альтернатив. Отношение RK задается тем или иным критерием выбора, назначаемым ЛПР в качестве целеполагания.
Предлагаемое решение – это, прежде всего, качественно новый подход. Исходное множество альтернатив представляется проектировщику упорядоченным в соответствии с его целевыми устремлениями, которые формально выражены через критериальные постановки. Известно [1], что основные принципы оптимальности подразделяются на два различных класса оптимизационных задач: неметрические и метрические. Основной недостаток неметрических безусловных критериев оптимальности в том, что они не позволяют корректно и точно разрешить проблему устойчивости решений и обладают меньшей силой, по сравнению с метрическими постановками. При этом принцип оптимальности RKi сильнее RKj или RKi RKj, если 0i 0j, где 0i RKi ()и 0j RKi ().
Важнейшую информацию о степени противоречивости целей при выборе из множества возможных альтернатив (МВА) дает вид распределения предпочтительности альтернатив по различным критериальным постановкам. При выборе появляется возможность оперативной оценки потерь при отступлении от оптимальных решений. И еще одним достоинством описываемого подхода является высокая эффективность оптимизационных процедур. Последнее связано с тем, что решение задачи выбора на соответствующем упорядоченном множестве фактически сводится к проверке допустимости решений по условиям и ограничениям только для максимальных элементов [2]. Такие задачи особенно актуальны для создания автоматизированных справочников по элементной базе в единой системе автоматизированного проектирования (САПР), где от задачи к задаче сохраняются устойчивые критериальные и функционально ориентированные постановки задач выбора для компонентов.
Первый подход к решению задачи
Эффективность предложенного подхода можно обеспечить, решив задачи получения необходимых частичных порядков высоких размерностей на основе преобразований базовых линейных или частичных порядков малых размерностей. Структурирование альтернатив отражают целеполагание ЛПР, хотя математические модели структурирования могут быть различными.
Первый подход основан на применении графов Бержа, позволяющих представить частично упорядоченные множества совокупностью линейно упорядоченных множеств, а второй – на формировании результирующих частично упорядоченных множеств с помощью фактор-множеств линейных порядков
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)
107
ДИСКРЕТНЫЕ ВОЛНЫ ПЕРЕКЛЮЧЕНИЯ И ДИССИПАТИВНЫЕ СОЛИТОНЫ …
вариантов. Основной концептуальный смысл и порядок переструктурирования альтернатив на множестве возможных вариантов (МВА ) можно графически интерпретировать (рисунок) как настройку базы данных на конкретную задачу выбора в соответствии с ее пониманием ЛПР.
MBA Ω
L (Ω/k1)
L (Ω/k2)
… L (Ω/km)
Задание ЛПР критериев
структурирования
G (Ω, U)
Рисунок. Формирование адаптивного частичного порядка G (, U) в соответствии с целевой постановкой задачи выбора из линейных порядков альтернатив
Рассмотрим математическую модель представления частично упорядоченного множества совокупностью линейно упорядоченных множеств, которые описываются графами [2].
Пусть частично упорядоченному множеству /Rk соответствует транзитивный граф Бержа G = , где UD1 = {i, j, если i j, i j {1, N}}.
Обозначим:
G = – обыкновенный (неориентированный) граф, полученный из G = заменой сигнатуры UD2 на UD1 при сохранении носителя ; при этом UD2 = {{i, j}, если (i j) (j i), i j {1, N}};
G = – обыкновенный граф, «дополнительный» к G = , сигнатура которого UD1 яв-
ляется дополнением сигнатуры UD2, т.е. UD2 UD1 = , а UD2 UD1 = ;
GA = < , UA >, GB = – графы Бержа – транзитивные турниры, соответствующие линейно упорядоченным множествам /UA и /UB;
GT = – граф Бержа, который является транзитацией (транзитивной ориентацией) обыкновенного графа G = , если орграф GT = , полученный в результате ориентации всех ребер из UD1 графа G = , является транзитивным;
GT = – противоположная GT = транзитация графа G, т.е. для i j {1, N} из UT следует UT.
Под объединением и пересечением графов Gi= и Gj = следует понимать
операции объединения и пересечения носителей i, j и сигнатур Ui, Uj. Таким образом, показаны не только необходимые и достаточные условия для представления час-
тично упорядоченного множества двумя линейно упорядоченными множествами.
Граф частичного порядка G можно представить в виде пересечения двух графов линейных порядков GA и GB тогда и только тогда, когда существует транзитация GT дополнительного графа G, или, в формализованном виде,
G = GA GB, если GT для G,
(1)
108
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)
Ю.В. Кандырин, Г.Л. Шкурина
что является необходимыми и достаточными условиями для представления частично упорядоченного множества двумя линейно упорядоченными множествами.
Если выполнено условие (1), то орграфы линейных порядков GA и GB определяются как объединения исходного графа частичного порядка G и противоположных транзитаций графа G :
GA = G GT; GB = G GT.
Из линейных порядков диаграмм Хассе HA и HB может быть восстановлен граф частичного порядка более высокой размерности G. Очевидно, что в нем концевые, недоминируемые вершины графа {1, 2} оптимальны по Парето (для минимизации), что является способом нахождения частично упорядоченного множества. Такое представление используется, в частности, для специального кодирования. Последнее дает возможность получить код, позволяющий эффективно находить задачи выбора по концевым вершинам [3].
Второй подход к решению задачи
Следующий подход предполагает использование математических моделей, основанных на описа-
нии множеств возможных вариантов с помощью фактор-множеств (/R). По определению фактор
множеством называется множество окрестностей единичного радиуса, взятых для всех i , i={1, N}. Под окрестностью Оi элемента i будем понимать множество элементов {i*}, доминирующих или эквивалентных i таких, что они могут быть описаны следующим линейным порядком: {i*}, i R (для min) [3]. Очевидно, что окрестностью минимальных элементов является пустое множество. В самом общем виде это отношение R может задаваться критериями Парето, Слейтера и т.д. [1, 2].
Пусть в качестве правила сравнения вариантов принимается критерий Парето, позволяющий устанавливать частичные порядки с минимумом требуемой начальной информации. Определим окрестность
Оi в фактор-множестве по показателю качества kl как Оi (/kl) {j: kl (j) kl (i), j, i }. Тогда фактор-множество /kl можно представить как совокупность окрестностей (/kj) = {Оi (/kl)}, i = {1, ||}, l={1, M}.
Рассмотрим пересечение окрестностей Оi (/k1) и Оi (/k2) для альтернативы i по показателям качества k1 и k2:
Oi (/k1) Oi (/k2) = {i: k1 (i) kj1 (j), l, j } {i: k2 (i) k2 (j),
i, j } = {i: [k1 (i) k1 (j)] [k2 (i) k2 (j)], l, j }. Продолжая для l={1, M}, получаем:
Oi (/kl) = {i: kl (l) kl (j), l{1, M}, j, i }.
(2)
И, если Oi (/kl) = , то i – вариант, не доминируемый любым j . При этом i – оптимальный вариант по принятому критерию Парето.
{k1, … kM} = {i: Oi (/kl, l {1, M}) = }.
Таким образом, решение для -постановки вида (/{k1,…, kM}) определяется пересечением окрестностей фактор-множеств для порядков альтернатив по всем показателям качества из выделенной совокупности {k1, …, kM}. Для автоматизации решения задач построения критериально структурированных множеств необходимо, чтобы методы решения задач были тесно увязаны с моделями хранимых данных об альтернативах, важна и компактность хранения информации, и оптимальные пути доступа к ней. Этим требованиям наиболее полно удовлетворяют ассоциативные матрицы (АМ), как показано в таблице.
Альтернативы i
1 2 … N
О1 (i) 0
B21 … BN1
Окрестности Оi (i)
О2 (i)
…
B12 … 0…
……
BN2 …
ОN (i)
B1N B2N …
0
Таблица. Ассоциативная матрица Al фактор-множества Ф(/kl) линейного порядка L(/kl)
В строках АМ располагаются альтернативы, а столбцы отображают окрестности. Если альтерна-
тива i доминирует альтернативу k , то элемент ассоциативной матрицы Bij принимает значение «1». Иначе говоря,
0, Вij 0,
1,
j i , i j; j i ,
j,i L( kl ), j,i L( kl ),
j i , j i ,
l 1, M ; l 1, M .
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)
109
ДИСКРЕТНЫЕ ВОЛНЫ ПЕРЕКЛЮЧЕНИЯ И ДИССИПАТИВНЫЕ СОЛИТОНЫ …
Естественно, что элементы, стоящие на главной диагонали, всегда принимают значение «0», так
как альтернатива не может войти в окрестность самой себе. Если альтернативы i, j несравнимы по данному показателю качества, то элементы Bij, Bji принимают значение «1». В остальных случаях элементы, расположенные симметрично относительно главной диагонали, связаны отношением отрицания Bij = Bji. Рассмотрим далее основные свойства фактор-множеств, которые представляются совокупностью АМ.
1. АМ всегда имеют размер NN, т.е. являются квадратными. Так как в строках матрицы отложены альтернативы, а в столбцах – их окрестности и количество окрестностей всегда совпадает с количеством альтернатив, то число строк равно числу столбцов.
2. Элементы ассоциативной матрицы Al, min, Bij, Bji равны тогда и только тогда, когда альтернативы i , j несравнимы по kl. Перейдем к получению решения задачи выбора оптимальных по -критерию. Для этого, как сле-
дует из выражения (2) необходимо реализовать пересечение фактор-множеств всех назначенных ЛПР показателей качества. Рассмотрим пересечение столбцов Сl1 и Cl2 произвольных ассоциативных матриц Al1, max, Al2, max фактор множеств
B1
Сl1
Сl2
=
B2
B1
B2
G1
=
G2
,
... ... ...
BN l1 BN l2 GN
где Gi = (Bi)l1 (Bi)l2 , i = {1, N}.Очевидно, что результат будет аналогичным для всех столбцов АМ.
Окончательно, для всех АМ l {1, M} фактор-множеств показателей качества Ф (/kl) получаем
выражение, определяющее результирующую ассоциативную матрицу (РАМ) Aрез, 1, 2.., m :
Gij = B1ij B2ij … BMij, i, j = {1, N}.
(3)
Формализованное выражение (3) назовем -правилом пересечения ассоциативных матриц фактор-
множеств. Основная особенность пересечения по -правилу – обладание свойством свободной переста-
новки пересекаемых элементов. Альтернатива i включается во множество нехудших решений, если для столбца, т.е. для окрестности Оi(i/{k1, ...,kM}) альтернативы i, выполняется условие
N Gi, j 0.
j 1
Заключение
Решение задачи выбора математической модели для критериального априорного структурирования альтернатив дает возможность адаптировать структуры данных к их целевому использованию при решении задач многокритериального выбора. Структурирование вариантов основано на композиции порядков более низкого уровня в частичные порядки более высокого уровня. Само преобразование структур осуществляется в соответствии с рассмотренными выше правилами. Предложенные подходы составляют методику структурирования и выбора рациональных вариантов. Она реализована на практике в программных комплексах: «Выбор 12М», «Choоse» и «Ряд», разработанных в Московском энергетическом институте (техническом университете) и внедренных на ряде предприятий и в вузах.
Литература
1. Кандырин Ю.В., Шкурина Г.Л., Сазонова Л.Т. Решение задач многокритериального выбора по последовательно принимаемым SpL-критериям // Концептуальное проектирование в образовании, технике и технологии: Межвуз. сб. науч. тр. – Волгоград: ВолгГТУ, 2000. – С. 96–100.
2. Кандырин Ю.В., Московский А.Е., Шкурина Г.Л. Методика формирования оптимальных очередей ремонтов по техническим характеристикам объектов // Известия ВолгГТУ. Проблемы управления, вычислительной техники и информатики в технических системах. – 2007. – № 2 (28). – С. 95–99.
3. Кандырин Ю.В., Сазонова Л.Т., Шкурина Г.Л. Математические модели структурирования альтернатив для решения задач выбора в САПР // Известия ВолгГТУ. – 2011. – № 3 (76). – С. 111–115.
Кандырин Юрий Владимирович – Национальный исследовательский университет «Московский энергетиче-
ский институт», кандидат технических наук, профессор, ywk@mail.ru
Шкурина Галина Леонидовна
– Волгоградский государственный технический университет, кандидат тех-
нических наук, доцент, shgl@bk.ru
110
Научно-технический вестник информационных технологий, механики и оптики, 2012, № 4 (80)