Содержание к диссертации
Введение
1. Введение. Содержание процесса проектирования и место задач выбора 8
2. Анализ решения задач проектного выбора в неметрических постановках 23
2.1. Формализованная постановка задачи проектного выбора 23
2.2. Использование безусловных ж- и S- критериев предпочтения для решения задач выбора вариантов 26
2.3. Лексикографический L-критерий выбора вариантов 30
2.4. Выбор по критерию с уступками (Д - критерий) 32
2.5 Пример выбора ИМС в тг и L- постановках 33
2.6. Анализ свойств неметрических критериальных постановок, используемых для решения МКВ 36
2.7. Анализ основных свойств Парето - постановок задач МКВ 38
2.8 Анализ свойств лексикографических постановок задач МКВ 41
Краткие выводы по разделу 44
3. Решение задач выбора на основе адаптивных неметрических критериальных постановок 46
3.1. Решение задач проектного выбора по жестким и гибким стратегиям.. 46
3.2. Апостериорные методы выбора, основанные на привлечении дополнительной информации от ЛПР 50
3.3. Адаптивные комбинированные неметрические критериальные постановки 56
3.4. Принципы решения задач в комбинированных - постановках 63
3.5. Решение задачи выбора аналога по заданному прототипу 66
3.5 Устойчивость решений задач многокритериального выбора в неметрических постановках 72
Краткие выводы по разделу 77
4. Методы критериального структурирования альтернатив для решениеязадач выбора в справочных CAB 79
4.1. Анализ условий для критериального структурирования вариантов в CAB при решении задач выбора 79
4.2. Условия целесообразности структурирования множеств альтернатив в соответствии с критериальными постановками 83
4.3. Критериальное структурирование МВБ П на основе использования неметрических расслоений 89
4.4. Частично упорядоченное структурирование альтернатив на основе композиции порядков по отдельным показателям качества 98
Краткие выводы по разделу 109
5. Разработка общей методологии и архитектуры построения систем автоматизированного выбора 111
5.1. Концептуальная методология автоматизированного многокритериального выбора альтернатив 111
5.2. Разработка алгоритмов CAB для традиционного и адаптивного подходов 1-15
5.3 Обоснование выбора модели данных для создания системы автоматизированного выбора 120
5.4. Сравнение реляционной и ассоциативной моделей данных для CAB 129
5.5. Процедуры изменения данных и поиска в AM CAB 131
5.6. Анализ возможностей использования СУБД широкого применения в автоматизированных системах выбора альтернатив 136
5.7. Формирование поисковых образов запросов для выбора допустимых вариантов 138
5.8. Процедуры и алгоритм выбора л-оптимальных вариантов 141
5.9 Процедуры и алгоритм выбора L-оптимальных вариантов 144
5.10. Алгоритм выбора оптимальных вариантов по Д- критерию 146
5.11. Примеры решения задач многокритериального выбора в ассоциативных моделях данных 149
Краткие выводы по разделу 158
Основные результаты диссертационной работы 159
Публикации по теме диссертации 160
Список литературы 162
- Использование безусловных ж- и S- критериев предпочтения для решения задач выбора вариантов
- Апостериорные методы выбора, основанные на привлечении дополнительной информации от ЛПР
- Условия целесообразности структурирования множеств альтернатив в соответствии с критериальными постановками
- Примеры решения задач многокритериального выбора в ассоциативных моделях данных
Введение к работе
Современное проектирование электронных и многих других технических систем в своей основе широко использует базовый принцип конструирования, в основе которого заложено широкое использование в новых разработках типовых и стандартных материалов, деталей, коммутационных изделий, модулей, узлов и блоков. Такой подход в значительной степени позволяет проектировать изделия с минимальной стоимостью и максимальной надежностью. Отсюда актуализируется задача выбора альтернативных проектных вариантов технической системы и выбора вариантов компонентов, наилучшим образом отвечающих техническому заданию (ТЗ). Сегодня тысячи фирм поставщиков электронных элементов и других компонентов из многих стран поставляют на рынок свои комплектующие. При этом перед разработчиком возникает задача выбора лучших вариантов среди огромной массы близких по параметрам изделий, с целью проектирования новых конкурентоспособных изделий. Обработка столь большого объема информации в рамках «ручных» способов проектирования не представляется возможной, отсюда встает задача автоматизации выбора типовых и стандартных элементов и построения систем автоматизированного выбора (CAB). Эта задача включает разработку методов, моделей многоцелевого многокритериального выбора (МКВ), методов, алгоритмов и архитектуры построения инвариантных CAB.
Вместе с тем следует отчетливо понимать, что CAB не могут заменить человека и снять с него ответственность за принятые решения. Автоматизированные системы могут лишь, не заменяя интуицию, в значительной мере облегчить решение проблемы и помочь лицу, принимающему решение (ЛПР) осуществить эффективный выбор на базе формально-логического аппарата, доведенного до алгоритмов и компьютерных программ. Отсюда встаёт задача дать разработчику инженерный инструмент многоцелевого сравнения альтернатив и выбора наиболее рациональных вариантов решений.
В диссертационной работе проводится аналитический обзор теоретико-математических аспектов проблемы МКВ по известным в России и за рубежом источникам, исследуются свойства экстенциальных критериальных постановок задач выбора, разрабатываются методики, модели, алгоричмы и компьютерные программы многокритериального выбора типовых и стандартных комплектующих компонентов по совокупности показателей качества. При этом под многокритериальным выбором понимается многоцелевой выбор по ряду критериев (правил сравнения альтернатив), каждый из которых, в свою очередь, может формироваться из некоторой совокупности показателей качества (ПК). Анализируются свойства наиболее важных неметрических критериальных постановок, разрабатываются адаптивные процедуры выбора, основанные на порядковых отношениях ПК в метапоказателях, анализируются вопросы устойчивости решений п^т^маашип^ц^ пдетр Ч"и-ках. В работе предложены две архитектуры построй 4Ияс^%8ШУ№^Щ1вЪго
назначения: для однократного сравнения и выбора вариантов, и для решения задач выбора в устойчивых во времени базах данных (справочниках).
Поставленные и рассмотренные в диссертации задачи особенно важны и актуальны в связи с появлением на рынке огромного числа импортных электронных компонентов близкого функционального назначения из разных стран, предназначенных для использования, как в новых разработках, так и для ремонта ранее созданной аппаратуры. Грамотно, своевременно и быстро проведенный сравнительный анализ и выбор альтернативных вариантов позволит разрабатывать новые изделия не просто в допустимых пределах, а добиваться лучших в том или ином смысле результатов при значительном сокращении времени.
Целью диссертационной работы является анализ свойств многокритериальных неметрических постановок задач выбора альтернатив и разработка формализованных методов, моделей, алгоритмов и компьютерных программ для построения систем автоматизированного многокритериального выбора типовых и стандартных компонентов электронных систем в рамках САПР, включая создание автоматизированных справочников.
в Анализ возможностей и сравнительное исследование свойств неметрических критериев для решения задач автоматизированного выбора типовых и стандартных компонентов электронной аппаратуры.
« Разработка адаптивных критериальных постановок, позволяющих на основе установления частичного порядка на показателях качества восстанавливать частичный порядок альтернатив без введения метрики между ПК.
о Проведение инженерного анализа и оценки устойчивости решений для к и L- неметрических критериальных постановок задач выбора вариантов.
о Разработка методики многокритериального выбора аналогов-вариантов по заданным вариантам-прототипам.
о Разработка методов априорного упорядочивания вариантов по неметрическим критериальным постановкам для решения задач выбора типовых и стандартных компонентов в автоматизированных справочных системах.
в Разработка архитектуры построения и программного комплекса «Система автоматизированного многокритериального выбора типовых компонентов конструкций для САПР электронной аппаратуры - «Выбор-12м»».
Решение поставленных задач основано на использовании принципов системного подхода, аппарата теории исследования операций, теории выбора и принятия решений, теории множеств, теории графов, булевой алгебры и
теории баз данных. Кроме того, в диссертационной работе использованы теоретико-методологические основы построения САПР.
При решении поставленных в диссертационной работе задач получены следующие новые научные результаты:
Исследованы основные свойства неметрических критериев выбора вариантов, которые являются важными для решения инженерных задач. В частности, для экстенциальных неметрических постановок показаны условия их сравнимости, полноты и силы. Показаны пути решения задачи выбора на основе установления частичного или линейного порядка на множестве альтернатив.
Предложен адаптивный метод нарастающего усечения исходного множества альтернатив, основанный на включении в последовательную процедуру выбора всё более сильных критериев по мере нарастания информированности ЛПР.
Исследованы возможности использования априорных, апостериорных и адаптивных моделей выбора. Предложен новый многошаговый подход к решению задачи МКВ посредством формирования дерева целей, основанного на установлении частичного прядка на показателях качества в пространстве надсистемных комплексных метакритериев.
Предложены принципы и разработана методика выбора аналогов для заданных прототипов по метрическим и неметрическим критериям.
Предложены методы инженерной оценки устойчивости решений задачи выбора по неметрическим постановкам.
Разработаны модели и методы критериального структурирования вариантов для автоматизированной системы выбора, основанные на партов-ском и слейтеровском структурировании, а также на адаптивном восстановлении любых частичных порядков из линейных и частичных порядков меньшей размерности, использующие пересечение фактормножеств.
Предложены принципы формирования архитектуры построения автоматизированной системы выбора, для многошаговых процедур, сформированных на основе частичных порядков для показателей качества.
Разработаны новые алгоритмы решения задач выбора по комбинированным неметрическим постановкам.
Разработанные в диссертации методы, модели, алгоритмы и программ
ные продукты могут найти отражение и использоваться при практиче
ской разработке автоматизированных систем выбора различного назна
чения и предназначенных для сравнения и выбора проектных вариан
тов и типовых компонентов ЭА по совокупности показателей качества.
В результате проведенных исследований и разработок, создан инже
нерный инструмент сравнения и выбора альтернатив, позволяющий
обеспечить рабочее место инженера-разработчика автоматизированны
ми средствами поддержки. Предлагаемые методы и модели могут быть
использованы как для создания систем выбора, входящих в состав
САПР, так и для автономных систем выбора оптимальных компонентов
ЭА.
« Разработанная в диссертации система «Выбор 12м» инвариантна по от
ношению к объектам и их характеристикам, позволяет хранить как чи
словую и символьную информацию, так и изображения разного рода в
виде графических файлов. Система предназначена для выбора допусти
мых и оптимальных вариантов по неметрическим и метрическим кри
териям, адаптивным многошаговым критериям, позволяет выбирать
аналоги по прототипам,' она может использоваться широким кругом
специалистов-разработчиков, в ремонтных организациях, а также в j
других приложениях, где требуется провести многокритериальную оценку и выбор альтернатив.
Использование безусловных ж- и S- критериев предпочтения для решения задач выбора вариантов
Таким образом, задача рационального выбора того или иного конкрет ного стандартного или типового компонента в ЭА становится актуальной за дачей проектирования современных конструкций электронной аппаратуры. Для подобной задачи характерно представление информации о стандартных и типовых компонентов устойчивыми множествами в различных базах данных и в справочниках. Эти множества относительно мало подвержены изменениям (по сравнению со скоростью изменения условий, ограничений и показателей качества в каждой вновь возникающей задаче выбора). Отсюда -такая разновидность задач выбора является актуальной и требует своего разрешения с применением автоматизированных систем.
Итак, выбор является процедурой многократно используемой при проектировании объектов. Поэтому разработка методов и моделей процедур выбора, ориентированных на конкретные проектные ситуации, а также соответствующих инструментальных средств поддержки таких процедур, имеет архиважное значение.
Существует большое количество публикаций (монографий и статей) как на русском, так и на иностранных языках, посвященных проблеме выбора. Вопросами многокритериального выбора и принятия решений при проектировании в последние десятилетия занимались Макаров И.М., Виноградская Т.М., Батищев, Горбатов В.Л., Гуткин Л.С., Дубов Ю.А., Травкин СИ., Яки-мец В.Н., Подиновский В.В., Ногин В.Д., Березовский Б.А. и др. Определенный вклад в проблему был внесен и в работах Губонина Н.С., Кандырина Ю.В. и др.
Несмотря на широкий интерес к проблеме, повсеместно наблюдается разрыв между накопленным теоретическим потенциалом и теми инструментальными системами, которые используется в актах реального выбора инженерами. Если оставить в стороне психологические аспекты выбора, то в значительной степени этот разрыв объясняется также и тем, что в указанных публикациях исследуются формальные аспекты проблемы и они, как правило, не увязываются с конкретными ситуациями МКВ, с которыми сталкивается инженер. Поэтому разработка инженерных подходов к формированию принципов построения систем автоматизированного выбора (CAB) является без сомнения актуальной задачей.
CAB, как интерфейсное ядро многокритериальных оценок, сравнения и выбора альтернативных решений, обычно входит в качестве подсистемы в САПР. CAB должна содержать как достаточно полный набор алгоритмов выбора вариантов, так и информацию об элементах, компонентах конструкций и материалах, а также текущих проектных решениях. CAB - интерактивная система. Диалог занимает центральное место в процедурах выбора, так как по своей глубинной сути выбор всегда многокритериален и таит в себе столько же неопределенности и зависимости от опыта лица принимающего решения (ЛПР), сколько и строгой логики. Выбор неотделим от человека, его осуществляющего, от его морали и мировоззрения, от его профессионализма, от окружающей его действительности, от социальных и экономических сторон жизни. Процесс выбора носит, в этом плане, принципиально субъективный, личностный характер.
Тем не менее, понимая всю сложность и нечеткость подсознательных оценок, закладываемых обычно в основу построения процедур проектного выбора, вполне естественно стремление разработать формально-логический аппарат, и создать средства его автоматизации, которые, не заменяя интуицию, в значительной мере облегчали бы решение проблемы.
В данной диссертационной работе разрабатывается методика многокритериального сравнения и выбора компонентов сложных конструктивных систем. Решаются вопросы автоматизации некоторых наиболее важных инвариантных процедур сравнения и выбора технических решений в неметрических постановках. Анализируются свойства таких постановок с точки зрения их использования в инженерных задачах усечения множеств возможных вариантов решений. Проводится анализ априорных, апостериорных и адаптивных постановок задач выбора. Указываются пути решения задач выбора-по многошаговым неметрическим критериальным постановкам с нарастающей силой. Исследуются вопросы устойчивости решений. Особое внимание уделяется созданию автономно функционирующих программных систем автоматизированного сравнения и выбора типовых компонентов и материалов, в которых нашли бы свое отражение разработанные методы. Предметом отдельного исследования предполагается сделать задачу разработки принципов формирования баз данных для CAB, которые были бы настроены, посредством структурирования информации, на возможные критериальные постановки задач выбора.
Постановка задачи выбора наилучшего решения предполагает наличие правила, позволяющего сравнивать качество возможных альтернатив. В простейшем случае такое правило может быть задано скалярной функцией на множестве возможных вариантов, а наилучшее решение определяется из условий экстремума этой функции. Однако в практических задачах построение такой функции вызывает серьезные затруднения. К тому же формирование целевых функций на начальных этапах выбора приводит к максимальному субъективизму и заранее запрограммированному результату, исключая широкий поиск возможных кандидатов на оптимальность по менее сильным критериям. Во многих реальных задачах проектирования целесообразно на множестве альтернатив формировать несколько скалярных функций или критериев оценки, задаваемых неметрическими постановками или отношениями порядка. При таких условиях задача переходит в разряд многокритериальных.
Основная особенность таких многокритериальных задач состоит в том, что их решением является не единственная точка, целое множество эффективных точек, удовлетворяющих поставленной неметрической постановке.
Обзор основных критериальных постановок [2], [9], [10], [11], [25], [31] и др. позволяет провести сравнительный анализ наиболее актуальных формализованных постановок для S, ж, L, Л - критериев, ввести в рассмотрение их графовое представление в виде диаграмм Хассе - частичных (для S,&) и линейных (для L, Л) -порядков альтернатив, полученных на основе бинарных сравнений альтернатив.
С учетом проведенного анализа была сформулирована цель диссертационной работы, которая заключается в разработке инструментальных методов и автоматизированных средств многокритериального выбора компонентов, материалов и проектных решений при проектировании электронной аппаратуры. Показано, что особое внимание должно уделяться силе усечения исходных множеств с помощью различных принципов оптимальности. Рассмотрим подробнее формализованную постановку задачи выбора и основные неметрические одноуровневые критериальные постановки.
Апостериорные методы выбора, основанные на привлечении дополнительной информации от ЛПР
Выделение множества Слейтера П$ и/или Парето Оя при решении многокритериальных задач для практических приложений часто не является удовлетворительным решением. Это связано с тем, что при достаточно большом исходном множестве вариантов множество Слейтера Qs или Парето Пл оказывается недопустимо большим для того, чтобы ЛПР было бы в состоянии осуществить окончательный выбор самостоятельно. Таким образом, выделение множества Qs или QK можно рассматривать как предварительный этап отбрасывания худших вариантов и налицо проблема дальнейшего сокращения альтернатив.
Неопределенность и неоднозначность получаемых решений в такой векторной постановке, по своей сути, связана с неопределенностью выбора цели и обусловлена противоречивостью и ортогональностью отдельных показателей качества. При этом, возможное сужение области получаемых решений, вплоть до единственного, онтологически связано с уточнением целей, т.е. введением дополнительных условий (в том или ином виде) на отношения в пространстве частных целей или посредством иной скаляризации задачи. Разумеется, что для этого потребуется некоторая дополнительная информация, которую придется получать от ЛПР. Это может быть информация о критериях, о самих сравниваемых вариантах и т.д.
Однако, несмотря на вроде бы нежелательный результат векторного выбора, связанный с получением множества, а не единственного решения, хотелось бы отметь и гносеологический аспект этой проблемы. А суть его заключается как раз в том, что при такой векторной постановке, когда ЛПР на первых шагах решения задачи недоинформирован о целях выбора и его приоритетах, возможные (более точные) решения как бы остаются в получаемой совокупности несравнимых решений, без априорных усечений всех подозрительных в более сильных постановках результатов. Т.е. ни один из вариантов, возможно представляющих интерес не должен быть потерян в процессе проце- дур выбора.
Таким образом, снятие неопределенности, в получаемых на последующих шагах решениях, связано с получением ЛПР дополнительной информации по мере продвижения к проектной цели и принятию окончательного решения. Такие уточняющие стратегии в процедурах выбора могут стать основным инструментом решения задач выбора в условиях нечеткой или неполной априорной информации о целях выполняемых процедур.
Главной особенностью методов последовательного усечения исходных множеств альтернатив является принцип декомпозиции и уточнения исходной цели. Если в традиционных подходах к решению задачи выбора критериальная постановка Ск задается на первом этапе решения задачи и ЛПР после выбора критерия уже не вмешивается в процесс решения, то предлагаемый подход предполагает уточнения получаемых решений и вмешательство человека после каждого промежуточного этапа усечения исходного множества. Многорядные фильтрационные алгоритмы выбора позволяют получать более адаптированные к реальной проектной ситуации решения, основанные на эвристиках человека, формирующихся на основе постепенного уточнения априорных представлений ЛПР о целях выполняемых процедур выбора.
Свобода выбора на каждом из этапов последовательно принимаемых решений может быть обоснована тем, что из-за недостатка априорной информации ЛПР через определенный промежуток времени придется снова принимать решение и т.д.
Наиболее эффективная теория последовательного выбора принадлежит Д. Габору, который в [8] пишет, что «управлять в данный момент времени нужно так, чтобы оставалась свобода выбора решений в последующий момент времени, когда будет приниматься следующее решение». При этом следует иметь в виду, что слишком большая свобода выбора вредна и, наверное, имеется оптимум количества альтернативных, несравнимых решений на каждом этапе в общей многорядной процедуре выбора.
Ответ может быть сформулирован исходя из здравого смысла: не спешить, продвигаться к цели поосторожнее и быть готовым изменить свою политику. Не строить планы, которые находятся за пределами компетентности и информированности, способности точно предвидеть все возможные ситуации. Отсюда вывод, общую стратегию выбора решений нужно разбить на ряд последовательных процедур и предусмотреть определенную свободу принятия решений на каждом шаге. Причем, применительно к решению задачи выбора вопрос будет заключаться в формировании таких политик, которые бы наилучшим образом соответствовали начальным целевым установкам через многорядные, последовательные процедуры усечения исходных множеств альтернатив и, в то же время допускали бы разумную коррекцию стратегий на промежуточных этапах этих процедур.
Одним из возможных принципов, позволяющих реализовать изложенный подход, является принцип внешних дополнений Стаффорда Бира. Он связан с использованием нескольких показателей качества или частных критериев: «.,при решении ряда взаимосвязанных вопросов оптимизации число критериев должно быть не меньше числа решаемых вопросов (целей)».
Причем, согласно принципу внешних дополнений Стаффорда Бира и теореме неполноты Геделя [4] каждый новый критерий является очередным «внешним дополнением» и с каждой новой оптимизацией возникает еще одна задача, требующая оптимизации. При этом принципиально нельзя пользоваться критерием, решающим последующий вопрос для решения предыдущего. Значит, при использовании ряда критериев требуется построение многорядных процедур выбора, а само назначение последовательности критериев является предметом эвристик человека, ибо только ЛПР знает, что ему нужно и только ЛПР имеет возможность установить креативную составляющую семантики выбора.
Приведем краткий анализ и дадим классификацию различных моделей многокритериального выбора.
В работе Красненкера А. [30], процедурные модели выбора предлагалось подразделять по способу использования в них дополнительной информации на «априорные», «апостериорные» и «адаптивные». Учитывая, что адаптивным комбинированным постановкам будут посвящены несколько ключе-. вых разделов диссертационной работы, остановимся далее на первых двух.
Априорные модели выбора не используют никакой дополнительной информации в процессе их использования. Предполагается, что вся информация, позволяющая определить наилучшее решение, заложена в самой постановке задачи, если задано множество альтернатив Q и Ск {ПК}. Таким образом, для выбора наилучшей альтернативы ЛПР достаточно априори задать цель в виде той, или иной постановки Cfc, определяющей глобальное качество, и решение будет однозначно найдено. Здесь уместно сослаться на работы, Борисова В.И. [5], Волковича В.Л. [7], Салуквадзе М.Е. [52], Б. Руа [68] и др.
Главный вывод из этих работ: процедуры априорного формирования стратегии выбора основаны на предположении возможности априорного (до решения задачи) определения наилучшего соотношения между показателями качества и другими требованиями. Понятно, что такая возможность существует не всегда и введение или не введение определенных метрических соотношений между показателями качества не может быть задано в отрыве от решаемой конкретной задачи. Метрические критерии сразу же ограничивают область возможных решений, а непосредственный выбор альтернатив в таких процедурах заменяется на выбор метрики для этого выбора при формировании Ск, что совсем не проще изначальной задачи. Если же в качестве моделей априорного типа использовать безусловные неметрические постановки, то как правило, задача не получит единственного решения. Таким образом, налицо существенная ограниченность подхода, обусловленная либо жесткой субъек-" тивностью, вызванной назначением априорной метрики, либо апостериорной неопределенностью, обусловленной задаваемыми априори слабыми критериями.
Условия целесообразности структурирования множеств альтернатив в соответствии с критериальными постановками
Поиск допустимого и лучшего в L-лостановке варианта сводится к поиску в цепи Gi(Q, 11щ\ полученной из Gi(Q, Uj) концевой вершины «ьд Подчеркнем, что основой для предлагаемого подхода к решению многокритериальных задач является интуитивное представление о большей устоичивости критериальных постановок в сравнении с изменениями состава исходного множества альтернатив и требований допустимости. Но даже если концептуально такая устойчивость самих постановок имеет место, неустойчивость априорного структурирования может быть связана с неустойчивостью критериальных решений, вызванных ошибками порядков альтернатив, задаваемых метрическими соотношениями. Известно, что любое номинальное значение характеристики альтернативы, как правило, флуктуирует вследствие возможных технологических или эксплуатационных ошибок. И если СКО таких флуктуации соизмеримы с разницей в номинальных значениях характеристик для разных вариантов, то может возникать проблема неустойчивости решений (см. разд. 3.5). Подобная неустойчивость решений может сделать принципиально невозможным создание CAB с критериальным структурированием альтернатив и возвращает задачу на прямой путь решения по (4.1) и (4.2).
В заключение сравним традиционный и «обратный» подходы к решению задач выбора в автоматизированных системах: 1. Как в традиционном (для условий: (4.1), (4.2)), так и в «обратном» (для условий: (4,3), (4.4)) подходах, в процессе решения задачи о предпочтении тех или иных вариантов используется информация обо всех рассматриваемых вариантах из Ои Од, Но в традиционной процедуре большая часть информации о вариантах 0\Од теряется, несмотря на то, что для них проводится критериальное сравнение, так как эти варианты отбрасываются и уже не принадлежат искомому множеству О0. В «обратной» же процедуре сохраняется вся информация о критериальном сравнении вариантов не только из множества Од, но и всего ИМА О. Поэтому нет необходимости восполнять потери информации, присущие традиционной процедуре, т.е. не надо многократно проводить критериальный выбор по R . Естественно это утверждение справедливо при условии, что полная информация о результатах выбора по критериальной постановке Rk не теряет актуальности при решении задачи выбора в новой критериальной постановке Rkt, 2. Упорядочение вариантов по критериальной оценке Rk сразу на исходном множестве альтернатив (ИМА) требует существенно больших комбинаторных сравнений, чем на множестве допустимых альтернатив Ол, поскольку О з Од. Но мощности этих множеств для некоторых слабых ограничений Сд отличаются не существенно, т.е. /о/&/Од/, следовательно практическое структурирование по R может быть одного порядка сложности для Q и Од, 3. При «обратном» подходе, который наиболее целесообразно применять к устойчивым справочным системам, это означает, что включение или исключение варианта в ИМА О сводится к включению или исключению вершин и соответствующих дуг в G„T и GLT. Таким образом, при выполнении условий (4.3) и (4.4) отсутствует необходимость построения заново графов G H GLT. Следовательно, на основе такого подхода к решению задачи выбора становится возможным однократное построение графа частичного порядка альтернатив для постановки Парето, или цепей лексикографии для типовых критериальных L-постановок и проведение поиска допустимых вариантов среди структур, содержащих заданные критериальные оценки. Все это дает основания для такого формирования структур информационных массивов, которые, были бы настроены на близкие по целям задачи выбора. А это в значительной степени сократит полный перебор и сведет число шагов, необходимых для усечения исходного множества альтернатив, к минимуму. Далее рассмотрим некоторые методы построения информационных массивов CAB, которые позволяют настраивать структуры ИМА О, на критериальные постановки ЛПР.
Решение задач с помощью автоматизированных систем выбора (CAB) предполагает создание рационально организованных банков данных для хранения информации о вариантах Q и их характеристиках {Z} = {У}и{0}и{К}. Известно [60], что любое представление данных в памяти ЭВМ должно включать в себя как собственно сами данные, так явно и неявно задаваемые взаимосвязи между ними, которые и определяют структурирование данных. Такие структуры могут представлять собой упорядоченные классы альтернатив, сгруппированные по определенным признакам. Каждый из классов наделяется определенным приоритетом обращения к нему, и включает в себя наборы несравнимых и эквивалентных по принятому критерию варианты.
Для эффективного использования информационных массивов они должны быть организованы так, чтобы их структурирование отвечало бы целям, для которых они создавались. Свойства (4.3) и (4.4) дают основания для однократного (при создании CAB) структурирования Q в соответствии с возможными постановками задач многокритериального выбора для любых требований по допустимости. Причем, каждая вновь создаваемая структура данных должна отражать заложенную ЛПР объективную картину предпочтений, задаваемую целями выбора.
Рассматриваемый в данном разделе подход, основан на наделении исходного множества альтернатив структурой, связанной с его функциональным назначением и, отражающей устойчивые критериальные требования, присущие ИМА О. При этом целеполагание является прерогативой ЛПР, а креативность в решении задачи выбора как бы переносится с уровня собственно выбора альтернатив на выбор критериальных постановок. Принятые цели определяют задаваемый вид структурирования П..
В соответствии с рассмотренными выше неметрическими постановками рассмотрим последовательно возможные виды структурирования для неметрических я, S, L -постановок.
Л Паретовское расслоение MB A Q. Послойное представление частично упорядоченного множества в виде последовательно задаваемых 7tsp слоев означает, что процедура выбора на структурированном множестве должна начинаться сразу с потенциально эффективных (нехудших по ти-критерию) концевых решений посредством проверки допустимости альтернатив по Сд. Если допустимых вариантов в Ожі - решениях нет, то выбор проводится на следующем слое До частично упорядоченного множества Д если их нет и там, то переходят к третьему слою и т.д.
Таким образом, все исходное множество альтернатив Q априорно разбивается на линейно упорядоченные С1т слои, которые представляют собой настроенную на целевые устремления ЛПР, эффективную структуру представления данных для решения задач МКВ.
Паретовские слои Qm (или уровни соответствующей диаграммы Хае се) определяются индуктивно. К первому слою относятся все Да - оптимальные (концевые, недоминируемые) альтернативы
Примеры решения задач многокритериального выбора в ассоциативных моделях данных
Принятые процедуры разработаны специально для системы автоматизированного выбора, предполагаю щуюю работу с программами выбора допустимых и оптимальных решений, но при построении CAB необходимо учитывать возможности и других известных СУБД.
В последние годы различными фирмами были созданы и получили широкое распространение автономные (самостоятельные) системы управления базами данных (СУБД), обладающие широким набором возможностей и ориентированные как на инвариантные БД, так и на определенные классы задач. Отсюда естественно встает вопрос о возможном использовании таких СУБД как подсистемы для систем автоматизированного выбора (CAB).
Главными требованиями, которые предъявляются к описанию, хранению и обработке данных в CAB являются: Удобство ввода разного типа данных их доступность для редактирования и манипуляции с ними, защита целостности и способы доступа. Компактность представления. (Данные должны занимать минимально возможное пространство на жестком диске). Сегодня известно огромное количество способов хранения данных в ЭВМ. Большинство из актуальных, известных СУБД позволяют автоматически поддерживать целостность баз данных, осуществлять кеширование данных, реализовывать восстановление разрушенной БД, обеспечивают достаточно надежную защиту от несанкционированного доступа к данным, приведем кратко лишь некоторые особенности самых мощных и популярных СУБД: Paradox - в данной СУБД наряду со многими стандартными функциями поддерживаются механизмы транзакций, кэширования данных, и др. Dbase и FoxPro - см. Paradox. DB2 (Database 2) - реляционные базы данных от компании IBM. Одна из сильных черт DB2 - масштабируемость: IBM расширила доступные платформы за пределы своих PC, AS/400, RISC System/600 на машины не-ІВМ. Доступ к данным может быть осуществлен через ODBC (см. ниже). Informix. Поставляется в двух пакетах Informix-SE и Informix-Online. Первый пакет доступен на платформах UNIX и Windows NT/2000 и разработан для небольших и средних приложений. Microsoft SQL Server бх, а также 7.0 являются высокопроизводительными системами управления реляционными БД, работающими полностью внутри операционной системы Windows NT/2000. SQL Server для NT обеспечивает механизм баз данных, который объединяет в себе высокую надежность, безопасность, обработку транзакций, устойчивость к отказам, целостность данных на стороне сервера, удаленные хранимые процедуры, связность и.т.д. Oracle. БД от Oracle Corporation используются приложениями, критичными к функциональности. База данных переносима в широком диапазоне аппаратного обеспечения и операционных систем: UNIX, Windows 95/98/NT/2000, Siemens Novell NetWare и др., что предоставляет полную свободу поиска нужной платформы сервера БД. Microsoft Access - производительный аналог БД Paradox. Начиная с Microsoft Access 2000, рекомендуется использовать именно эту СУБД. Microsoft Excel 95 — ХР. Огромное число справочников имеют формат именно Microsoft Excel. Возможность создания диаграмм, построения графиков (в том числе и по точкам) делают данную программу весьма удобной в использовании." Принципиально все перечисленные СУБД могли бы быть положены в основу создания CAB, хотя каждая из них имеет некоторые ограничения, например, в каждой ячейке Excel не могут быть помещены и обработаны данные интервального типа, прямого представления изображений и т.д., что может создавать неудобства при работе с CAB. Другим важным моментом является выбор метода доступа к данным. В настоящее время существует несколько способов доступа из среды Windows: 1. ODBC (Open Database Connectivity - открытый интерфейс для подключения к базам данных) - программный интерфейс, позволяющий приложениям получать доступ к данным в системах управления базами данных, основанных на языке SQL (Structured Query Language - структурированный язык запросов). 2. ADO (Active Data Objects) — высокоуровневый компонент технологии доступа к данным (т.н. MDAC - Microsoft Data Access Components -компоненты доступа к данным от Microsoft). Данными для ADO могут являться: таблицы Microsoft Access, БД Oracle, MS SQL XML - файлы. В случае разработки программ на языках компании Borland (Inprise), таких как: Delphi, C/C-H-/Visual С может использоваться механизм BDE (Borland Database Engine) обеспечивающий доступ к данным Paradox, DBase, FoxPro, SQL, Access, ODBC и др. При разработке системы автоматизированного выбора в диссертационной работе в качестве средства хранения и манипуляции с данными была разработана собственная СУБД, позволяющая переводить входной язык реляционных описаний данных во внутренний язык ЭВМ, основанный на квазиреляционных (ассоциативных) моделях. Вместе с тем, в разработанной системе автоматизированного выбора предусмотрена также возможниость работы с базами данных Paradox. Кроме того, в качестве источника получения данных может, помимо баз данных Paradox, может использоваться и Microsoft Excel, в случаях, когда это допускается типом используемых данных. Выбор метода и способа хранения данных о МВВ С1 является определяющим, т.к. от него зависят все дальнейшие процедуры по взаимодействию с исполняемыми программами. Поисковый образ запроса (ПОЗ) в AM формируется для решения задачи выбора альтернатив из МВБ Ц хранящихся в БД. Он используется при поиске допустимых и оптимальных вариантов. Напомним, что все дальнейшие утверждения сделаны в предположении априорного упорядочения характеристик по возрастанию их значений в ассоциативных матрицах справа налево и использования всех правил их формирования, оговоренных выше в разделе 5.3. Выбор допустимых вариантов Од из МВБ Q осуществляется по совокупности требований ТЗ на характеристики объекта. Задаваемые техническим заданием условия и ограничения на характеристики, формально представляются в виде троек {pRV}n, с помощью которых формируются столбцы-переменные {д;ра} для всех характеристик, которые оговариваются в ТЗ на выбор. Каждая из характеристик может быть представлена совокупностью своих значений, отвечающих требованиям для отношений R = {=, , , , ...}. При ограничениях типа «равенств» это означает, что характеристика строго равна одному значению р$ = Pjk. Например, если напряжение питающей сети U =22ОБ. В этом случае ПОЗ р-3 = У = 220В соответствует к-й столбец AM характеристики «напряжение
