Содержание к диссертации
Введение
ГЛАВА 1. Система комбинаторных объектов, связанных с целочисленными композициями 12
1.1. Генерация, селекция и оценка комбинаторных объектов, связанных с целочисленными композициями 13
1.2. Прикладные математические методы, основанные на генерации и селекции целочисленных композиций 26
1.3. Генерация и селекция целочисленных композиций в методах анализа и синтеза сводных показателей сложных объектов 37
ГЛАВА 2. Алгоритмы генерации целочисленных композиций и дискретных путей на решетке 50
2.1. Оценка объема множеств композиций и дискретных путей на целочисленной решетке 51
2.2. Алгоритмы генерации композиций и дискретных путей на целочисленной решетке 63
2.3. Анализ и тестирование алгоритмов генерации композиций и дискретных путей на целочисленной решетке 75
ГЛАВА 3. Программная реализация метода сводных показателей с использованием алгоритмов генерации целочисленных композиций 84
3.1. Оболочка системы поддержки принятия решений АСПИД-ЗХУ, реализующей метод рандомизированных сводных показателей 85
3.2. Алгоритмы обработки нечисловой, неточной и неполной информации о целочисленных композициях, используемых в ОСППР АСПИД-3\У 96
3.3. Применение метода сводных показателей для оценки программного обеспечения 107
Заключение 139
Список литературы 141
- Прикладные математические методы, основанные на генерации и селекции целочисленных композиций
- Алгоритмы генерации композиций и дискретных путей на целочисленной решетке
- Анализ и тестирование алгоритмов генерации композиций и дискретных путей на целочисленной решетке
- Алгоритмы обработки нечисловой, неточной и неполной информации о целочисленных композициях, используемых в ОСППР АСПИД-3\У
Введение к работе
Актуальность темы диссертационного исследования
В последние десятилетия получили широкое распространение прикладные программы, использующие алгоритмы генерации, селекции и оценивания различных комбинаторных объектов. Такие алгоритмы являются важными составными частями, например, методов целочисленного программирования, в которых они применяются для генерации опорных планов. Особенно следует отметить роль комбинаторных алгоритмов перебора структур разного вида (графы, деревья, разбиения и т.п.) в методах многокритериальной оптимизации, в процедурах принятия многокритериальных решений, в системах искусственного интеллекта, в современных интерактивных системах анализа данных, в экспертных системах и т.д.
Важным частным случаем рассматриваемых комбинаторных алгоритмов являются алгоритмы генерации и селекции так называемых композиций (упорядоченных разбиений) , , натурального числа , которым взаимно однозначно сопоставляются монотонно неубывающие траектории, заданные на конечной целочисленной решетке . Такие алгоритмы генерации и селекции композиций используются в различных экспертных системах и в системах поддержки принятия решений (СППР) по распределению дискретных ресурсов по конечному числу позиций.
Особенно важную роль рассматриваемые комбинаторные алгоритмы играют в СППР, ориентированных на использование нечисловой, неточной и неполной информации о весовых коэффициентах и/или вероятностей. Эти СППР в последнее время широко применяются для синтеза сводных оценок сложных объектов разной природы, например, для построения оценок многопараметрических технических систем военного назначения и НИР, направленных на разработку таких систем, для сводной оценки сложных финансово-экономических объектов (коммерческих банков, страховых компаний и т.п.), для формирования рациональных вариантов инвестиционного портфеля, для оценивания экологического состояния и устойчивости геосистем, для построения непараметрических байесовских оценок распределений случайных величин и т.д.
Комбинаторные объекты (композиции и монотонно неубывающие траектории на целочисленной решетке), используемые в вышеуказанных прикладных методах, весьма многочисленны – их число очень быстро растет с увеличением параметров и . Действительно, даже для умеренных значений и число всех возможных композиций весьма велико: N(5,10)=1001; N(5,20)=10626; N(5,40)=135751; N(10,10)=92378; N(10,20)=10015005; N(10;30)=211915132; N(10,40)=2054455634.
Поскольку время , требуемое для полного перебора исследуемых комбинаторных объектов, можно в первом приближении оценить сверху величиной , где константа определяется типом процессора, особенностями алгоритма, операционной системой и тому подобными обстоятельствами, постольку следует ожидать существенного увеличения времени работы соответствующих методов. Поэтому, весьма актуальной является задача повышения скорости генерации, селекции и оценки композиций.
Таким образом, рассматриваемые в диссертации вопросы исследования и программной реализации комплекса комбинаторных методов генерации, селекции и оценки целочисленных композиций имеют как научную, так и практическую актуальность.
Цель и задачи диссертационной работы
Цель работы заключается в исследовании и программной реализации комплекса комбинаторных методов генерации, селекции и оценки целочисленных композиций для разработки программного обеспечения прикладной системы поддержки принятия решений (СППР), реализующей метод построения сводных показателей в условиях неопределенности. Для достижения этой цели должны быть решены следующие основные задачи:
провести анализ различных прикладных методов на предмет выявления особенностей использования в этих методах комбинаторных структур, связанных с целочисленными композициями;
разработать и протестировать алгоритмы генерации, селекции и оценки соответствующих комбинаторных объектов;
разработать метод распараллеливания построенных алгоритмов генерации композиций;
разработать программное обеспечение, основанное на созданных алгоритмах генерации целочисленных композиций, системы поддержки принятия решений, реализуемой на ПЭВМ в виде прикладной программы АСПИД-3W, позволяющей пользователю оценивать в интерактивном режиме сложные многопараметрические объекты.
проверить работоспособность построенной СППР АСПИД-3W на примере построения по иерархической системе исходных характеристик сводных показателей предпочтительности различных вариантов архиваторов с использованием нечисловой, неточной и неполной информации о сравнительной значимости исходных характеристик эффективности работы этих архиваторов.
Методы исследования
Исследование алгоритмов генерации, селекции и оценки комбинаторных объектов, связанных с целочисленными композициями, проводится в диссертации с использованием методов анализа программ для ЭВМ, методов общей комбинаторики и теории разбиений. Анализ применения разработанных алгоритмов для создания прикладного программного обеспечения осуществляется с использованием методов теории принятия решений при неопределенности, теории вероятностей и математической статистики. Использовались также методы тестирования программ для ЭВМ и методы оценки работы прикладного программного обеспечения (в частности, методы оценки эффективности работы архиваторов).
На защиту выносятся:
-
Методы генерации, селекции и оценки композиций, учитывающие нечисловую, неточную и неполную информацию.
-
Метод распараллеливания процесса генерации целочисленных композиций с целью реализации процедур их генерирования на многопроцессорных ЭВМ.
-
Методика использования алгоритмов генерации композиций при решении задач методом сводных показателей, решении задачи распределения дискретного ресурса.
-
Комплекс программ, составляющих математическое обеспечение системы СППР АСПИД-3W, основанной на методе рандомизированных сводных показателей с использованием алгоритмов генерации композиций.
-
Методика оценки программного обеспечения с использованием СППР АСПИД-3W.
Научная новизна
-
Разработан новый алгоритм генерации композиций (алгоритм FAST), использующий, в отличие от известного алгоритма Рейнгольда (алгоритм SWIFT), предварительно построенные монотонные пути на целочисленной решетке, что позволяет ускорить процесс примерно в три раза по сравнению с алгоритмом SWIFT.
-
Разработан новый алгоритм генерации композиций (алгоритм QUICK), отличающийся от известных алгоритмов возможностью использовать дополнительную информацию о компонентах композиции без построения всей композиции, что позволяет в ряде случаев ускорить генерацию композиций на несколько порядков по сравнению с алгоритмами SWIFT и FAST.
-
Предложен новый метод распараллеливания программ генерации композиций, использующий разработанные новые алгоритмы лексикографической нумерации/денумерации композиций (алгоритмы LEXCOMP/COMPLEX), отличающийся от существующих методов распараллеливания большой простотой и позволяющий сократить время генерации множества всех возможных композиций пропорционально числу используемых процессоров.
-
Разработаны новые алгоритмы обработки и представления неточной (интервальной) и нечисловой (ординальной) информации о весовых коэффициентах, отличающиеся от существующих процедур возможностью непосредственного учета дискретности весовых коэффициентов и позволяющие сократить время генерации соответствующих композиций, что обеспечивает работу СППР АСПИД-3W в реальном времени.
Практическая и теоретическая ценность
Полученные теоретические результаты об асимптотике числа комбинаторных объектов, связанных с целочисленными композициями, могут быть использованы при анализе скорости работы и предельных возможностей различных комбинаторных алгоритмов.
Разработанные в диссертации алгоритмы и их программные реализации на ЭВМ находят применение при создании прикладного программного обеспечения для систем, реализующих байесовское оценивание распределений и параметров случайных величин, для систем поддержки принятия решений, для систем оценивания вероятностей альтернатив по нечисловой, неточной и неполной информации и т.д.
Разработанная в рамках настоящего диссертационного исследования прикладная программа АСПИД-3W, реализующая систему поддержки принятия решений в условиях неопределенности, официально зарегистрирована РосАПО и в настоящее время практически используется для решения многих конкретных задач, связанных с построением сводных оценок сложных объектов различной природы и назначения.
Реализация результатов работы
Система поддержки принятия решений АСПИД-3W и другие программные продукты, разработанные в рамках диссертационной работы, практически использовалась при выполнении перечисленных ниже НИР, проводимых в Санкт-Петербургском институте информатики и автоматизации РАН (СПИИРАН) лабораторией вычислительных систем и проблем защиты: «Анализ, классификация и оценка уровня защищенности информационных систем», «Анализ и оценка рисков нарушения безопасности в сложных информационных системах при дефиците информации», «Разработка метрик для оценки качественных аспектов моделей программ» (2001-2003 гг.).
В лаборатории интеллектуальных систем СПИИРАН разработанные в диссертации методы обработки композиций практически использовались в НИР «Разработка программных средств оптимизации планирования комплексного БСК», выполнявшейся по договору с ФГУП «Комета» лабораторией интеллектуальных систем СПИИРАН (2002-2003 гг.).
Результаты диссертационной работы были внедрены в ГУП «Санкт-Петербургский информационно-аналитический центр» и использованы при разработке Интегрированной системы информационно-аналитического обеспечения Администрации Санкт-Петербурга (2002-2003 гг.).
Все указанные примеры практического использования результатов диссертационной работы подтверждены соответствующими актами о внедрении.
Публикации
Основные результаты диссертации представлены в 6 научных публикациях.
Апробация работы
Основные результаты и выводы диссертации докладывались:
на заседаниях кафедры информатики математико-механического факультета СПбГУ (2001-2003 гг.);
на Международной научной конференции «Информационно-управляющие и вычислительные комплексы на основе новых технологий» (СПб., 1992 г.);
на Международном научном конгрессе «Народы СНГ накануне третьего тысячелетия»; секция «Математические методы принятия предпринимательских решений» (СПб., 1996 г.);
на Всероссийской научной конференции «Инвестиционная политика России в современных условиях»; секция «Математические методы обоснования инвестиционных и финансовых решений» (СПб., 1997 г.);
на Пятой Международной конференции «Вероятностные методы в дискретной математике». (Петрозаводск, 2002).
Структура и объем диссертации
Диссертация состоит из введения, трех глав, содержащих по три параграфа каждая, заключения и пяти приложений. Общий объем основного текста – 146 стр., приложения – 28 стр. В диссертации имеется 17 рисунков и 25 таблиц. Список литературы содержит 130 наименований.
Прикладные математические методы, основанные на генерации и селекции целочисленных композиций
В случае отсутствия «настоящей» эмпирической информации о частотах осуществления различных альтернатив развития конфликта мы можем воспользоваться «квази-эмпирической» информацией, получаемой в результате учета числа kt «равноценных аргументов», свидетельствующих в пользу осуществления альтернативы Ап и общего числа к таких «равноценных аргументов». Например, можно опросить к
«равноценных» экспертов, каждый из которых должен указать одну и только одну альтернативу, которая, по его мнению, осуществится в процессе развития конфликта. Тогда число kt экспертов, указавших на осуществление альтернативы Alt можно принять за эмпирически наблюдаемое число реализаций этой альтернативы. При этом коэффициенты «важности» априорной (Fj(A)) и эмпирической («квази-эмпирической») (У2(к)) информации в формуле (26) можно также оценить экспертным путем с использованием метода сводных показателей (см. 1.3).
Итак, проанализированные прикладные методы распределения дискретного ресурса и метод байесовского оценивания вероятностей альтернатив основаны, фактически, на алгоритмах генерации и селекции целочисленных композиций. Некоторые из этих алгоритмов реализованы нами в виде оболочек систем поддержки принятия решений (ОСППР) РРР (Рациональное Распределение Ресурсов) и СОВЛ (Система Оценивания Вероятностей Альтернатив) (см. [89,91,92]).
Перейдем теперь к описанию важного прикладного метода, называемого методом сводных показателей (МСП) (см., например, [1,3,6,48-51,83,94,110,130]), в котором существенное применение находят генерация и селекция целочисленных композиций. При использовании этого метода предполагается, что рассматривается k объектов (сложных технических систем, альтернатив принимаемого решения, вариантов развития финансово-экономической конъюнктуры и т.д.), исследуемое качество которых (скажем, надежность, эффективность, перспективность, предпочтительность и т.д.) достаточно полно описывается векторами отдельных показателей qU) {q\n,..-,4 ), q\n є[0,1], і = І,...,т, j = l,...,k, каждый из которых есть многокритериальная оценка соответствующего объекта и представляет собой значение вектора отдельных показателей q =(qlt...,qm).
Введем на множестве всех оцениваемых объектов отношение (строгого) покомпонентного доминирования, обозначаемое и определяемое соотношением
Это соотношение можно трактовать как утверждение, что объект qir) предпочтительнее по оцениваемому качеству, чем объект 7(,) тогда и только тогда, когда он не менее предпочтителен по каждому отдельному критерию (qlr) .q\s)) и существует критерий, по которому первый объект предпочтительнее второго (q{p q{jS)) (см. [82]). Наряду с отношением "строгого" упорядочения по предпочтительности введем отношение порядка ("нестрогого") следующим образом: Обратно, отношение строгого порядка t можно определить через отношение порядка Существенной трудностью, возникающей при упорядочении объектов с помощью отношения покомпонентного доминирования, обычно является наличие большого числа объектов qir), qw, несравнимых по отношению порядка , т.е. объектов, для которых не выполняется ни соотношение q r) tjw ни соотношение ?Ы 7(г - Оценить долю сравнимых (по отношению порядка ) объектов позволяет следующее утверждение, являющееся следствием теоремы, приведенной в работе [15, с. 154-155]. Пусть две многокритериальные оценки выбираются совокупности {q = (ql q„%q, є.[,\],і = \ т) всех возможных векторов отдельных показателей. Под выбором "наугад" здесь понимается выбор двух независимых случайных величин qir) = (q}r),...,q% ), qU) =(qi } ,-, ), каждая из которых равномерно распределена на указанном множестве всех возможных векторов отдельных показателей. Тогда вероятность сравнимости (по отношению порядка ) этих двух случайных векторов определяется формулой Из формулы (4) видно, что шансы встретить сравнимые многокритериальные оценки качества быстро уменьшаются с ростом числа используемых критериев. Для решения указанной проблемы несравнимости многокритериальных сценок обычно используется так называемый метод сводных показателей (МСП), суть которого состоит в построении по вектору отдельных показателей (по многокритериальной оценке) q = {q% qm) сводного показателя Q, представляющего собой некоторую функцию Q = Q(q) = Q(qt,....tqm) вектора отдельных показателей q, удовлетворяющую условию монотонности.
Алгоритмы генерации композиций и дискретных путей на целочисленной решетке
Решив прямую и обратную задачи лексикографической нумерации монотонных путей (целочисленных композиций) мы можем приступить к построению процедуры распараллеливания генерации указанных комбинаторных объектов. Пусть у нас имеется к процессоров, каждый из которых может осуществлять генерацию композиций из множества Х{т,п) (монотонных путей из множества К(/м,л)) начиная с некоторой композиции х{,г 1 ={х{ г- (\),...ух{,,- (т)) имеющей лексикографический номер /гЧ, и кончая композицией хм =(jc"r)(l),...,j:( 5(m)), имеющей лексикографический номер.
Тогда процедуру распараллеливания генерации в лексикографическом порядке всех композиций из множества Х(т,п) (всех монотонных путей из множества Г(/и,и)) можно представить следующим образом.
Сначала целочисленный отрезок [l,N(mtri)] разбивается на к целочисленных отрезков ви да [/,_,,/,], г = \,...,к, где целое число tr определяется соотношением tr r [N(mtn)[r\, r = l,...,k-\, /0=0. tr N(m,n) (здесь выражение [х] означает целую часть числа х). Затем в каждом процессоре восстанавливается композиция (монотонный путь), имеющая лексикографический номер t и производится генерация всех композиций (всех монотонных путей), имеющих лексикографические номера от /,_, до /, -1 с использованием, например, разработанных алгоритмов SWIFT, FAST и QUICK.
Применение разработанной процедуры распараллеливания на к процессоров генерации в лексикографическим порядке комбинаторных объектов, связанных с целочисленными композициями, позволяет сократить время генерации всего множества таких комбинаторных объектов примерно в к раз. Даже такое умеренное сокращение времени генерации композиций, пропорциональное числу используемых процессоров, может существенно улучшить функционирование соответствующих прикладных программ, позволив им работать в интерактивном режиме реального времени.
В этом параграфе мы проведем сравнительный анализ и тестирование разработанных алгоритмов генерации целочисленных композиций SWIFTt FAST и QUICK описанных в 2.2. Результатом работы этих алгоритмов является селекция множества Х(т,п;1) допустимых (с точки зрения дополнительной информации /) целочисленных композиций (множество У (/и, и;/) допустимых монотонных дискретных путей на целочисленной решетке) с одновременным получением индивидуальных и коллективных оценок соответствующих комбинаторных объектов. Поэтому целью оптимизации таких алгоритмов можно считать минимизацию как времени генерации множества Х(т,п) всех допустимых композиций, так и времени проверки выполнения условий, составляющих информацию /, для селекции допустимых композиций и вычисления их оценок.
Прежде всего, следует заметить, что процедуры перебора всех возможных композиций и монотонных путей, используемые в рассматриваемых алгоритмах (SWIFT, FAST и QUICK), требуют для своего выполнение объем времени, пропорциональный общему числу N(m,ri) всех возможных /и-частных композиций х -=(х(\),...,х(тУ) натурального числа п. Иными словами, имеют место простые соотношения для времени генерации элементов множества Х(т,п) всех возможных целочисленных композиций, где Sn Flt Q, суть времена генерации одной композиции алгоритмами SWIFT, FAST и QUICK, соответственно. Так как константы Sn F,t Q; нетрудно определить с достаточной точностью по реальным прогонкам соответствующих алгоритмов, то основную задачу сравнительного анализа рассматриваемых алгоритмов можно определить как задачу оценки числа Iier(m,n) итераций, необходимых для определения соответствия генерируемых композиций (монотонных путей) условиям, содержащимся в дополнительной информации /, имеющейся у исследователя.
Для определенности, будем рассматривать задачу оценки величины Iter(m,ri) для генерируемых траекторий вида {(0,0),(1,у(1)),...,(т-1,у(т-1)),(т,п)}, заданных на конечной целочисленной решетке [0tm]x[0,n] (см. 1.1).
В случае простейшей целочисленной решетки [0,1]х[0,п] единственная возможная траектория ((0,0),(1,«)) состоит из одного звена. Поэтому здесь достаточно всего одной итерации (Iter(l,n)), для проверки выполнения для данной траектории условий, содержащихся в дополнительной информации / .
Траектории ((0,0),(1,j),(2,tt)), j = 0,...,n, заданные на решетке [0,2]х[0,п] , имеют уже два звена ( ((0,0),(1, j)) и ((l,j),(2,n)) ), каждое из которых проверяется на соответствие информации / за одну итерацию. Отсюда, общее число Iter(2,n) итераций для проверки всех путей вида ((0,0),(/,/),(2,л)) на предмет соответствия дополнительной информации определяется формулой
При рассмотрении траекторий на решетке [0,2]х[0,п], можно выделить первое звено ((0,0),(1, j)), а оставшуюся часть ((l,j)f(2,k),(3,ti)) полной траектории ((0fi),(l j),(2,k),(3,n)) - рассматривать как траекторию на решетке [l,3]x[j,n]. Отсюда имеем рекуррентную формулу В общем случае, когда траектория ((0,0),(1,у") (І + 1,п)) задана на целочисленной решетке [0,і + 1]х[о,л], описанный выше способ выделения «первого звена» в рассматриваемых траекториях, позволяет записать рекуррентную формулу.
Анализ и тестирование алгоритмов генерации композиций и дискретных путей на целочисленной решетке
Однако, для практической реализации ОСППР АСПИД-3\У мы выбрали все таки алгоритм QUICK. Дело в том, что этот алгоритм, в отличие от двух остальных, имеет возможность отбрасывать конструируемую композицию на любой стадии ее построения (например, при вычислении первой компонент композиции), если обнаруживается несоответствие конструируемой композиции требованиям осуществляемой селекции композиций. Два других алгоритма, хотя и не включают «неподходящую» композицию в число отобранных, но вынуждены полностью построить ее для того, чтобы иметь возможность перейти к конструированию композиции со следующим лексикофафическим номером. Это преимущество алгоритма QUICK перед алгоритмами SWIFT и FAST становится решающим при создании системы принятия решений типа АСПИД, в которой многократно используется постоянно изменяющаяся информация, определяющая правила селекции генерируемых композиций.
Итак, во второй главе диссертации получены следующие основные результаты: 1. Проведен анализ асимптотики числа N(m,ri) всех возможных целочисленных композиций (упорядоченных разбиений натурального числа и на то частей). Доказаны теоремы об асимптотике величины N(m,n) при различных соотношениях для параметров т,п, значения которых стремятся к бесконечности (2.1). 2. Исследовано влияние неточной (интервальной) и нечисловой (ординальной) информации на общее число допустимых (с точки зрения этой информации) целочисленных композиций. Доказаны соответствующие теоремы и приведены результаты численных расчетов (2.1). 3. Разработаны два новых алгоритма и модифицирован один известный алгоритм генерации целочисленных композиций в лексикографическом порядке. Разработанные алгоритмы требуют для своей работы чрезвычайно малый объем машинной памяти, так как построение последующей композиции опирается только на информацию об одной предшествующей композиции (2.2). 4. Разработан новый метод распараллеливания программ генерации целочисленных композиций и монотонных путей на целочисленной решетке с целью реализации процедур генерирования этих комбинаторных объектов на многопроцессорных ЭВМ и/или в многоагентских системах (2.2). 5. Осуществлена программная реализация трех разработанных алгоритмов генерации целочисленных композиций. Дан сравнительный теоретический анализ программных реализаций и проведено их тестирование на реальной ПЭВМ. Наработана статистика, позволяющая, в первом приближении, оценить зависимость реального времени генерации композиций от значений параметров: определено среднее время генерации всех возможных целочисленных композиций при различных значениях параметров и при использовании различных алгоритмов (2.3).
В этой главе анализируется общая структура разработанной нами оболочки системы поддержки принятия решений (ОСППР) АСПИД-ЗШ, реализующей описанный в 1.3 метод рандомизированных сводных показателей (МРСП). Реализованный на ПЭВМ ОСППР АСПИД-3\ официально зарегистрирован Российским агентством по правовой охране программ для ЭВМ, баз данных и топологий интегральных микросхем (РосАПО). Подробно излагаются основные схемы применения оболочки СППР ACnHfl-3W для оценки сложных многопарамстрических объектов и для оценки вероятностей альтернатив в условиях неопределенности (3.1). Рассматриваются разработанные нами для ОСППР АСПИД-3\У алгоритмы обработки неточной (интервальной) и нечисловой (ординальной) информации {ипн-информации) о весовых коэффициентах, определяющих сравнительную значимость отдельных показателей. В предположении, что ннн-информация представима в виде систем равенств и неравенств, разрабатывается процедура согласования получаемых систем неравенств и проверки непротиворечивости этих систем (3.2). Подробно рассматривается пример использования ОСППР АСПИД-3\У для рейтингования различных вариантов важного и широко распространенного типа программного обеспечения - архиваторов, используемых для «сжатия» информации, хранимой в компьютерах и передаваемой по линиям связи. Строится иерархическая система отдельных показателей, каждый из которых оценивает архиваторы с точки зрения определенного критерия. Последовательно строятся оценки рандомизированных сводных показателей предпочтительности различных вариантов программного обеспечения (архиваторов) и исследуется влияние на эти показатели дополнителной ннн-информацни, которой располагает гипотетический субъект, оценивающий общую предпочтительность архиваторов. Анализируются результаты проведенного с помощью ОСППР АСПИД-3\У исследования качества (предпочтительности) существующих архиваторов (3.3).
В настоящем параграфе описывается общая структура разработанной нами оболочки системы поддержки принятия решений ЛСПИД-3\У (см. [90]) (АСПИД -аббревиатура для «Анализ и Синтез Показателей при Информационном Дефиците), являющейся одним из возможных вариантов реализации метода рандомизированных сводных показателей, подробного описанного в 1.3.
Оболочка системы поддержки принятия решений (ОСППР) АСПИД-3\У предназначена для создания в среде Windows па IBM-совместимых ПЭВМ конкретных систем, используемых для всестороннего оценивания в условиях неопределенности сложных миогопараметрических объектов.
В качестве оцениваемых объектов могут выступать сложные технические системы, варианты управленческих и организационных решений, потребительсике товары и услуги, объекты недвижимости, финансово-экономические проекты, мнения различных экспертов и т.д. При этом оцениваемыми качествами исследуемых объектов могут служить эффективность, надежность, полезность, безопасность, прибыльность, предпочтительность и т.д.
Реализуя на ПЭВМ ОСППР АСПИД-3W, мы получаем универсальное средство построения гибких интерактивных систем многокритериального оценивания, применимых практически в любых ситуациях, связанных с использованием нечисловой, неточной и неполной информации.
В основе гибких интерактивных систем поддержки принятия решений (СППР), реализуемых в среде Windows на IBM-совместимых ПЭВМ при помощи универсальной оболочки АСПИД-3\У, лежит метод сводных показателей (МСП), суть которого состоит в "свертке" многих оценок сложного объекта в единую оценку, представляющую собой сводный (глобальный, интегральный, обобщенный, генеральный, синтетический и т.п.) показатель, синтезирующий отдельные (локальные, дифференциальные, частные, маргинальные, аналитические и т.п. - соответственно) показатели, характеризующие качество (эффективность, надежность, безопасность, прибыльность, полезность, предпочтительность и т.п.) любых многопараметрических объектов: сложных технических систем; вариантов управленческих, организационных и инвестиционных решений; потребительских товаров и услуг; финансово-экономических проектов; мнений отдельных экспертов и экспертных комитетов и т.д., и т.п.
Отвлекаясь от содержания многокритериальных оценок и от природы оцениваемых объектов, упрощенную схему построения сводного показателя Q некоторого исследуемого объекта можно представить в виде последовательности следующих шагов.
Алгоритмы обработки нечисловой, неточной и неполной информации о целочисленных композициях, используемых в ОСППР АСПИД-3\У
Еще одна схема применения ОСППР ЛСПИД-3\У возникает при необходимости использования иерархической системы синтеза сводных показателей качества сложных объектов. Дело в том, что при попытке непосредственного синтезирования в единый показатель большого числа (ш 7) отдельных показателей возникает ряд затруднений. Во-первых, как показывают исследования психологов и опыт практической работы, эксперты затрудняются при сравнении значимости критериев, если им предъявляется сразу более 5-7 отдельных показателей (см., например, [48-51,108,114,116,129]). Во-вторых, практика многокритериального оценивания подтверждает, что чем более однородна группа сравниваемых по значимости отдельных критериев, тем более достоверны устойчивы результаты сравнения; а достаточной однородности трудно ожидать от больших (т 7) групп отдельных показателей. И, наконец, в-третьих, комбинаторные алгоритмы, реализуемые ОСППР АСПИД-3\У, не позволяют работать в интерактивном режиме реального времени при большом числе (/и 7) исходных характеристик.
Учитывая указанные трудности, возникающие при обработке большого числа отдельных показателей, можно предложить следующую схему последовательного синтеза сводных показателей различного уровня. На первом шаге все множество исходных характеристик xlt...,xm разбивается на от, подмножеств, каждое из которых содержит не более 5-7 относительно однородных характеристик. Для всех этих подмножеств обычным образом строятся сводные показатели ?(_/, ;1), jt = I,..., m,.
Если объем /л, множества сводных показателей QU Y), jl-\t...,mi, слишком велико для непосредственного синтеза сводного показателя следующего уровня, то это множество опять разбивается на тг подмножеств, каждое из которых содержит не более 5-7 относительно однородных сводных показателей. Для всех этих подмножеств строятся сводные показатели Q(j2 ,2), j2 =1 m2, следующего (второго) уровня, относительно которых сводные показатели предыдущего (первого) уровня играют роль исходных характеристик. Этот процесс построения иерархии сводных показателей разного уровня заканчивается, когда на г-ом шаге получается единственный сводный показатель Q(\;r), синтезирующий все многообразие исходных отдельных показателей и промежуточных сводных показателей. При помощи такой иерархаизации системы исходных характеристик удается, используя свертки 5-7 показателей, за 3-5 шагов получить сводный показатель, синтезирующий две-три тысячи исходных отдельных показателей. Рассмотрим, наконец, схему применения ОСППР ACni -3W для многокритериального оценивания вероятностей альтернатив. Эта схема применения разработанной нами ОСППР связана с задачей оценивания вероятностей р{,...,р,. попарно несовместных случайных событий Al,...,Ak, образующих полную группу: при любой реализации соответствующего случайного испытания (наблюдения) имеет место одно и только одно из событий А1,...,Ак. Предполагается, что вероятности pi,...,рк оцениваются с точки зрения т частных критериев и/или источников информации. При этом, каждый критерий (источник) дает нечисловую (порядковую) и неточную (интервальную) информацию /(/), / = ] т, о вероятностях р;, j = \,...,k. Поскольку вероятности plt...,pk альтернатив А1,...,Ак обладают всеми свойствами весовых коэффициентов, постольку ОСППР АСПИД-3\У дает возможность провести оценивание этих вероятностей по следующей схеме. Для каждого /-го частного критерия (источника информации) вводится информация /(f) в виде системы равенств и неравенств для весовых коэффициентов \vt =/J,,...,wt = рк, интерпретируемых как вероятности соответствующих альтернатив. Используя метод построения числового образа нечисловой информации /(і), получаем оценки р}(І(і)), і = 1,...,ni, j = 1,...,&, вероятностей альтернатив А ,Ак. Теперь каждая альтернатива AJt у = 1,,,., , имеет вектор оценок вероятности р} . компонента р}{І{і)) этого вектора есть оценка вероятности альтернативы А}, сделанная с точки зрения /-го критерия (с учетом информации /(г), полученной из І-то источника сведений). Для свертки отдельных оценок pj(I(\)),...,pj(I(m)) вероятности альтернативы исследователь может привлечь дополнительную информацию / о степени надежности (достоверности) т отдельных критериев (источников сведений), дающих информацию /(/), і = 1,...,т. Эта дополнительная информация / задается системой равенств и неравенств для весовых коэффициентов Wp...,Wm, определяющих надежность отдельных критериев и интерпретируемых как вероятности того, что из соответствующих источников получена достоверная информация. Полученные с использованием информации / сводные показатели Q(j;I), и могут быть приняты за искомые оценки Pj(I), вероятностей альтернатив А}, j = \...tk. Оценки точности и достоверности вычисляются так же, как и при синтезе сводных показателей качества. Заметим, что изложенная схема многокритериального оценивания вероятностей альтернатив по нечисловой, неточной и неполной информации /(/), / = 1,...,/и, получаемой при помощи т отдельных критериев (отдельных источников информации), и по дополнительной информации /о достоверности самих источников информации, может быть проинтерпретирована как схема многокритериальной классификации (диагностики). При такой интерпретации оценки р}(Щ)), / = 1,..., т, j = 1,...,к, трактуются как оценки вероятностей попадания объекта в j-yio классификационную категорию, вычисленные с применением /-го критерия (с использованием /-го источника информации). Вычисленные же величины р }{1), j = \i...,k, можно понимать как искомые сводные оценки вероятности попадания объекта в /-ую категорию, учитывающие как информацию /(1),...,/(/л), получаемую из различных источников, так и информацию / о достоверности этих источников.
Все построенные в настоящем параграфе схемы применения разработанной нами ОСППР АСПИД-ЗУ/ опираются на удобную систему окон, подробно описанную в Приложении 1 и позволяющую пользователю работать с имеющейся у него информацией в реальном времени и в интерактивном режиме. При этом, основным элементарным шагом в интерактивном применении ОСППР АСПИД-ЗШ служит процедура применения анализа и синтеза сводных показателей, проводимая как последовательность обращений к рабочим и операционным окнам нашей ОСППР, описанная в Приложении 2.
