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

На правах рукописи

ХОВАНОВ Кирилл Николаевич

КОМПЛЕКС АЛГОРИТМОВ ГЕНЕРАЦИИ КОМПОЗИЦИЙ ДЛЯ ПОСТРОЕНИЯ СИСТЕМ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2004

Работа выполнена в Санкт-Петербургском институте информатики и автоматизации РАН (Статус государственного учреждения)

Научный руководитель:

доктор физико-математических наук, профессор Баранов Сергей Николаевич

Официальные оппоненты: доктор физико-математических наук,

Тараканов Александр Олегович

доктор технических наук, профессор Уткин Лев Владимирович

Ведущая организация:

Санкт-Петербургский государственный университет

Защита диссертации состоится « б » Сс^-урО-СД.. 2004 г. в I ^ часов на заседании диссертационного совета Д 002.199.01 при Санкт-Петербургском институте информатики и автоматизации РАН по адресу: 199178, Санкт-Петербург, 14 линия, д. 39.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского института информатики и автоматизации РАН.

Автореферат разослан

«2.7

2004 г.

Ученый секретарь диссертационного саветдЦД®029|

ЬМррвйЯШлаиимир Евгеньевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы диссертационного исследования

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

Важным частным случаем рассматриваемых комбинаторных алгоритмов являются алгоритмы генерации и селекции так называемых композиций (упорядоченных разбиений) (х(1),...,х(т)), *(1)+...+х(т) = п, натуральногочисла п, которым взаимно однозначно сопоставляются монотонно неубывающие траектории, заданные на конечной целочисленной решетке [0,/и]х[0,и]. Такие алгоритмы генерации и селекции композиций используются в различных экспертных системах и в системах поддержки принятия решений (СППР) по распределению дискретных ресурсов по конечному числу позиций..

Особенно важную роль рассматриваемые комбинаторные" алгоритмы играют в СППР, ориентированных на использование нечисловой, неточной и неполной информации о весовых коэффициентах и/или вероятностей. Эти СППР в последнее время широко применяются для синтеза сводных оценок сложных объектов разной природы, например, для построения оценок многопараметрических технических систем военного назначения и НИР, направленных на разработку таких систем, для сводной оценки сложных финансово-экономических объектов (коммерческих банков, страховых компаний и т.п.), для формирования рациональных вариантов инвестиционного портфеля, для оценивания экологического состояния и устойчивости геосистем, для построения непараметрических байесовских оценок распределений случайных величин и т.д.

Комбинаторные объекты (композиции и монотонно неубывающие траектории на целочисленной решетке), используемые в вышеуказанных прикладных методах, весьма многочисленны - их число ~N(m, n) очень быстро растет с увеличением параметров тип. Действительно, даже для умеренных значений т и я число всех возможных композиц! N(5,10)=1001; N(5,20)=10626; N(5,40)=135751; N(10,20)=10015005; N(10;30)=211915132; N(10,40)=20544:5j5634.~£n«^ Поскольку время T(m,n), требуемое для полного перебора ЙДсл

и ■ весьма1 вшико. 1 • РОС^НАДИрЯАЛ^НЛЯ |

комбинаторных объектов, можно в первом приближении оценить сверху

величиной Т(т,п)$=Ст-Щт,п), где константа С определяется типом процессора, особенностями алгоритма, операционной системой и тому подобными обстоятельствами, постольку следует ожидать существенного увеличения времени работы соответствующих методов. Поэтому, весьма актуальной является задача повышения скорости генерации, селекции и оценки композиций.

Таким образом, рассматриваемые в диссертации вопросы исследования и программной реализации комплекса комбинаторных методов генерации, селекции и оценки целочисленных композиций имеют как научную, так и практическую актуальность.

Цель и задачи диссертационной работы.

Цель работы заключается в исследовании и программной'реализации комплекса комбинаторных методов генерации, селекции и оценки целочисленных композиций для разработки программного обеспечения прикладной системы поддержки принятия решений (СППР), реализующей метод построения сводных показателей в условиях неопределенности. Для достижения этой цели должны быть решены следующие основные задачи:

• провести анализ различных прикладных методов на предмет выявления-особенностей использования в этих методах комбинаторных структур; связанных с целочисленными композициями;

• разработать и протестировать алгоритмы генерации, селекции и оценки соответствующих комбинаторных объектов;

• разработать метод распараллеливания построенных алгоритмов генерации композиций;

• разработать программное обеспечение, основанное на созданных алгоритмах генерации целочисленных композиций, системы поддержки, принятия решений, реализуемой на ПЭВМ в виде прикладной программы АСПИД-3W, позволяющей пользователю оценивать в интерактивном режиме сложные многопараметрические объекты.

• проверить работоспособность построенной СППР АСПИД-SW на примере построения по иерархической системе исходных характеристик сводных показателей предпочтительности различных вариантов архиваторов с использованием нечисловой, неточной и неполной информации о сравнительной значимости исходных характеристик эффективности работы этих архиваторов.

Методы исследования

Исследование алгоритмов генерации, селекции и оценки комбинаторных объектов, связанных с целочисленными композициями, проводится в диссертации с использованием методов анализа программ для ЭВМ, методов общей комбинаторики и теории разбиений. Анализ применения разработанных алгоритмов для создания прикладного программного обеспечения

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

На защиту выносятся:

1. Методы генерации, селекции и оценки композиций, учитывающие нечисловую, неточную и неполную информацию.

2. Метод распараллеливания процесса генерации целочисленных композиций с целью реализации процедур их генерирования на многопроцессорных ЭВМ.

3. Методика использования алгоритмов генерации композиций при решении задач методом сводных показателей, решении задачи распределения дискретного ресурса.

4. Комплекс программ, составляющих математическое обеспечение системы СППР АСПИД-3W, основанной на методе рандомизированных сводных показателей с использованием алгоритмов генерации композиций,

5. Методика оценки программного обеспечения с использованием СППР АСПИД-3W.

Научная новизна

1. Разработан новый алгоритм генерации композиций (алгоритм FAST), использующий, в отличие от известного алгоритма Рейнгольда (алгоритм SWIFT), предварительно построенные монотонные пути на целочисленной решетке, что позволяет ускорить процесс примерно в три раза по сравнению с алгоритмом SWIFT.

2. Разработан новый- алгоритм генерации композиций (алгоритм QUICK), отличающийся от известных алгоритмов возможностью использовать дополнительную информацию о компонентах композиции без построения всей композиции, что позволяет в ряде случаев ускорить генерацию композиций на несколько порядков по сравнению с алгоритмами SWIFT и FAST.

3. Предложен новый метод распараллеливания программ генерации композиций, использующий разработанные новые алгоритмы лексикографической нумерации/денумерации композиций (алгоритмы LEXCOMP/COMPLEX), отличающийся от существующих методов распараллеливания большой простотой и позволяющий сократить время генерации множества всех возможных композиций пропорционально числу используемых процессоров.

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

позволяющие сократить время генерации соответствующих композиций, что обеспечивает работу СППР АСПИД-3W в реальном времени.

Практическая и теоретическая ценность

Полученные теоретические результаты об асимптотике числа комбинаторных объектов, связанных с целочисленными композициями, могут быть использованы при анализе скорости работы и предельных возможностей различных комбинаторных алгоритмов.

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

Разработанная в рамках настоящего диссертационного исследования прикладная программа АСПИД-3W, реализующая систему поддержки принятия решений в условиях неопределенности, официально зарегистрирована РосАПО и в настоящее время практически используется для решения многих конкретных задач, связанных с построением сводных оценок сложных объектов различной природы и назначения.

Реализация результатов работы

Система поддержки принятия решений АСПИД-3W и другие программные продукты, разработанные в рамках диссертационной работы, практически использовалась при выполнении перечисленных ниже: НИР, проводимых в Санкт-Петербургском институте информатики и автоматизации РАН (СПИИРАН) лабораторией вычислительных систем и проблем защиты: «Анализ, классификация: и оценка уровня защищенности информационных систем», «Анализ и оценка рисков нарушения безопасности в сложных информационных системах при дефиците информации», «Разработка метрик для оценки качественных аспектов моделей программ» (2001-2003 гг.).

В лаборатории интеллектуальных систем СПИИР АН разработанные в диссертации методы обработки композиций практически использовались в НИР «Разработка программных средств оптимизации планирования комплексного БСК», выполнявшейся по договору с ФГУП «Комета» лабораторией интеллектуальных систем СПИИРАН (2002-2003 гг.).

Результаты диссертационной работы были внедрены в ГУП «Санкт-Петербургский информационно-аналитический центр» и использованы при разработке Интегрированной системы информационно-аналитического обеспечения Администрации Санкт-Петербурга (2002-2003 гг.).

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

Публикации

Основные результаты диссертации представлены в 6 научных публикациях.

Апробация работы

Основные результаты и выводы диссертации докладывались:

• на заседаниях кафедры информатики математико-механического факультета СПбГУ (2001-2003 гг.);

• на Международной научной конференции «Информационно-управляющие и вычислительные комплексы на основе новых технологий» (СПб., 1992

г.);

• на Международном научном конгрессе «Народы СНГ накануне третьего тысячелетия»; секция «Математические методы принятия предпринимательских решений» (СПб., 1996 г.);

• на Всероссийской научной конференции «Инвестиционная политика России в современных условиях»; секция «Математические методы обоснования инвестиционных и финансовых решений» (СПб., 1997 г.);

• на Пятой Международной конференции «Вероятностные- методы в дискретной математике». (Петрозаводск, 2002).

Структура и объем диссертации

Диссертация состоит из введения, трех глав, содержащих по три параграфа каждая, заключения и пяти приложений. Общий объем основного текста - 146 стр., приложения - 28 стр. В диссертации имеется 17 рисунков и 25 таблиц. Список литературы содержит 130 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Bos Введении обосновывается: актуальность выбранной темы диссертации, освещаются теоретические и прикладные аспекты исследования комбинаторных объектов, связанных с упорядоченными; разбиениями (целочисленными композициями) натурального числа на фиксированное количество неотрицательных чисел. Описывается общая структура диссертации, выбранная для изложения решения поставленных задач диссертационного исследования.

В главе 1 дается, прежде всего, определение композиции: w-частная композиция (упорядоченное разбиение) натурального числа п есть вектор д: = (х(1),...,х(т)) с целочисленными компонентами, которые удовлетворяют условиям x(i)£0, х(1) +... + х(т) = п, где х(/)е £(n) = {0,l,...,n}, i = l,...,m. Множество всех возможных композиций Х(т,п) состоит из конечного числа N(m,n) элементов. Определяются также основные виды комбинаторных объектов, связанных с понятием композиции. Описывается процедура селекции

введенных комбинаторных объектов на основе использования нечисловой (ординальной), неточной (интервальной) и неполной информации, т.е. информации представимой в виде объединения 1 = 01иН двух систем неравенств: 01 = {*(/•) >.х($); х(и) =х(к), ...} - ординальная (нечисловая) информация; II = {а(|)5*(/)££(/), «е {1,...,от}} - интервальная (неточная) информация о компонентах композиций. Информация 1 = 01 и II называется неполной, поскольку предполагается, что соответствующая система неравенств является непротиворечивой и может, вообще говоря; иметь более одного решения, что не позволяет полностью и однозначно определить единственную композицию (х(1),...,х(л)), удовлетворяющую всем условиям, вытекающим из информации / (§1.1).

Изучается вопрос о возможном усилении системы неравенств, формализующих интервальную информацию, имеющуюся у исследователя. Вводятся различные оценки (функции) комбинаторных объектов, получаемых в результате селекции (§1.1).

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

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

В главе 2 проводится теоретическое оценивание числа N(m,n) всех возможных целочисленных композиций (упорядоченных разбиений натурального числа п на т частей). Для этого исследуется асимптотика величины N(m,n) при различных соотношениях для параметров т,п. Результаты этого исследования формулируются в виде следующих утверждений.

Пусть аргументы функции N{m,n) стремятся к бесконечности и при этом т/п —»0. Тогда имеет место эквивалентность

Щт,п) = •

■ ехр (т - 1)=а(т)п"

(1)

(т - ¡у'12

двух бесконечно оолыних величин.

Пусть аргументы функции Щт,п) стремятся к бесконечности и при этом п/т -» 0. Тогда имеет место эквивалентность

Щт,п) в ■

■ ехр(л)=р(л)(т-/)"

(2)

г,г"1

двух бесконечно больших величин.

Если между неограниченно увеличивающимися аргументами функции Щш,п) сохраняется постоянное отношение {т/п = а>0), то асимптотика поведения этой функции описывается следующей эквивалентностью двух бесконечно больших величин:

1 (1 + аг)"('+"Н/2

Щт,п) =

гю-1/2

(3)

¿/гл а

В частном случае, когда безгранично возрастающие аргументы функции Щш,и) равны (т = п = к, т.е. а = 1), имеет место простая асимптотическая эквивалентность

_!_т2*Ч

Щт,п) =

■¿як

(4)

Проводятся прямые вычисления числа Щш,и) для небольших значений параметров т, п. Часть результатов этих вычислений приведена в таблице 1.

Таблица 1. Значения функции М{ш,н) при т = 2...Л, л = 20....Д00

п\ш 2 3 4 5 6 7

20 21 231 1771 10626 53130 230230

25 26 351 3276 23751 142506 736281

30 31 496 5456 46376 324632 1947792

35 36 666 8436 82251 658008 4496388

40 41 861 12341 135751 1221759 9366819

45 46 1081 17296 211876 2118760 18009460

50 51 1326 23426 316251 3478761 32468436

55 56 1596 30856 455126 5461512 55525372

60 61 1891 39711 635376 8259888 90858768

65 66 2211 50116 864501 12103014 143218999

70 71 2556 62196 1150626 17259390 218618940

75 76 2926 76076 1502501 24040016 324540216

80 81 3321 91881 1929501 32801517 470155077

85 86 3741 109736 2441626 43949268 666563898

90 91 4186 129766 3049501 57940519 927048304

95 96 4656 152096 3764376 75287520 1267339920

100 101 5151 176851 4598126 96560646 1705904746

Оценивается также влияние длины цепочки неравенств, задаваемых исследователем для компонент композиции и составляющих систему неравенств / на общее число N(m,n;l) допустимых (с точки зрения информации /) композиций. Для демонстрации влияния ординальной информации / на объем N{m,n\l) множества допустимых (с точки зрения этой ординальной информации /) композиций вычислены значения величины N(7,100; 1(0) для семи видов /(0), 7(1),...,7(6) информации 7, задаваемых соотношениями: /(0) = 0, /(1) = {х(1)>х(2)}, /(2) = {*(1)>д:(2)>лг(3)}, 7(3) = {^(1) > дг(2) > дс(3) > дс(4)>, 7(4) = {,(1) > х(2) > х(3) > х(4) > х(5)}, 1(5) = {х(1) > х(2) > *(3) > х(4) > х(5) > х(6)}, 1(6) = {х(1) > х(2) > х(3) > х(4) > х(5) > х(6) > х(7)}.

Вычисленные значения величины N(7,100; 7(0), коэффициента селекции SEL(l(i)) = N(m,n)/N(m,n;I(i)) и логарифмической меры информации INF(l(i)), определяемой формулой INF(I) = SEL(I), приведены в таблице 2.

Таблица 2. Влияние информации Щ) на число допустимых композиций №(7£0;1(1))

i N(130:1(1)) SEL(I(i)) INF (I (i))

0 32468436 1,00* 0,00

IS 20413107 1,59 s 0,67

2 4558041! 7,12 2,83

3 492791 65,89 6,04-

4 28942: 1121,84 10,13

5; 941 34504,18 15,07

6, 16 2029277,25 20,95

Из этой таблицы видно, что учет ординальной информации- позволяет весьма существенно сократить множество допустимых композиций. Это позволяет надеяться, что прикладные программы, использующие алгоритмы генерации композиций, смогут работать в реальном времени.при наличии у исследователя достаточного объема дополнительной информации о неравенствах, которым должны удовлетворять компоненты используемых композиций (§2.1).

Разрабатываются три алгоритма генерации композиций (алгоритмы SWIFT, FAST, QUICK), один из которых (алгоритм SWIFT) является модификацией известного алгоритма прямой генерации композиций в лексикографическом порядке (алгоритм Рейнгольда), а два других представляют собой новые разработки, в которых используется предварительное генерирование

монотонных путей на целочисленной решетке, с последующим переходом к соответствующим композициям.

Все три рассматриваемые алгоритма генерируют композицию

Лс+|) =(х<'+1>(1).....*<,+|>(т)), непосредственно следующую в лексикографическом

порядке за композицией х0> = (х0)(1),...,х<'}(т)), опираясь только на информацию, содержащуюся в композиции х0> =(х0)(1),...,х0>(т)). Поэтому общая схема всех трех алгоритмов генерации множества всех возможных композиций Х(т,п)

такова: на первом шаге строится композиция л:(|)=(0.....0,и); затем- по

композиции JC® генерируется следующая композиция jc<2) =(0.....0,1,и—1), которая-

служит основой для генерации следующей композиции и так

далее до тех пор, пока не получим последнюю композицию с

лексикографическим номером N(m,n). Таким образом, суть генерации-композиций в лексикографическом порядке сводится к построению композиции = (лс<ж) (1),..., х(,+1) (т)) по композиции х1,) =(*(,)(1),...,х")('п))-

В алгоритме SWIFT (т.е., в алгоритме Рейнгольда) «слабым звеном» является необходимость вычисления на каждом шаге сумм вида y<0(i) =x(')(l)+—+*(')(0> входящих в условия (т.е., входящие в равенства и неравенства), определяющие значения компонент генерируемой композиции д:(,+|> =(х('+1,(1),...,х<'+|)(т)). Указанного недостатка, лишен разработанный нами алгоритм * генерации композиций FAST, в котором переход от композиции к композиции осуществляется с

использованием процедуры сканирования (справа* налево) композиции

для обнаружения компоненты такой, что

при i = l+l,...,m И л(,)(/)>0.

Описанные алгоритмы (SWIFT и FAST) непосредственно генерируют композиции из множества Х{т,п). Однако, можно генерировать сначала монотонные пути /'> =Cy("(0),^<')(l),-,J'<')('n-l),/>')('«)). /"(0) = 0, у(,)(т) = п, на целочисленной решетке каждый из

которых определяет композицию с тем же лексикографическим номером г, а затем вычислить искомые компоненты композиции При

этом проигрыш во времени, необходимом для перехода от монотонного пути

/"=0>('>(0),/"(1).....у(,)(т-1),ум(т)) к композиции х(,) =(х{'>(1),...,х(')(т)),

компенсируется скоростью генерации монотонных путей. На этой идее основан разработанный в диссертации алгоритм QUICK, в котором- переход от монотонного пути к следующему

монотонному пути У+|> = О,<№1>(0),,)'('+|,(1),...,у°*п(т-1),у('*1)(т)) осуществляется при помощи следующей простой процедуры: если у°\Ц) = п для ¿ = /+1,...,?п-1 и

У"(/)<И, то: У'+1)С') = /"(') ДЛЯ i = l...../-1 и /"">(/) = /"(/) для / = /,..., m-1.

Переход от монотонного пути У'+|) =(У"|>(0),У"ч(1),™,У'+,)('я-1),3'(м'1>(,и)) к соответствующей композиции jc(,+1) =(jctwl,(l),... ,х°*1)(т)) осуществляется по формуле х(ы)(0 = У+"(0->'('+"(''-1), где />)=х(ы>(1) + ...+*(,+1)(0, «' = 1.....т.

Для всех трех алгоритмов дается их программная реализация. Разработанные алгоритмы лексикографической нумерации и денумерации-композиций позволяют осуществить распараллеливание процесса генерации композиций при помощи описанных алгоритмов SWIFT, FAST, QUICK многопроцессорных ЭВМ (§2.2).

Проводится теоретический сравнительный анализ программных реализаций» трех разработанных алгоритмов генерации целочисленных композиций. Кроме того, эти реализованные алгоритмы тестируются на реальной ПЭВМ с наработкой статистики, позволяющей оценить зависимость реального времени генерации композиций от значений - параметров т, п. Определяются как среднее время генерации всех N(m,n) возможных целочисленных композиций, так и среднее время генерации одной композиции при различных значениях параметров т, п и при использовании различных алгоритмовЛ

В таблице 3 приведены усредненные (по десяти прогонкам) времена 7Х4(5,л), X = S,F,Q, работы тестируемых алгоритмов при генерации всех возможных композиций из множества Х(5,п) для =10,15,...,45,50.

Таблица 3. Усредненное время работы (в миллисекундах) тестируемых алгоритмов

п 754(5; л) TFA(5-n) TQA(5;n)

10 0,0 0,0 0,9

15 1,0 0,0 1,0

20 2,8 1,0 1,8

25 4,6 1,8 4,7

30? 9,3 4,7 8,3

35 16,6 6,5 16,6

401 28,8 11,4 21,Z

45 43,4 18,5 43,4

50 66,4 27,8 64,6

Проведенный анализ показал, что алгоритм FAST (точнее, программа,, реализующая: этот алгоритм на конкретной ПЭВМ- — все программы, реализующие рассматриваемые алгоритмы, тестировались на ПЭВМ с процессором AMD-K7, имеющим частоту 1200 Мгц, с операционной системой Windows 2000 и с оперативной памятью 256 Мб.) является наиболее быстрым из трех тестируемых алгоритмов: среднее время работы TFA{m,n) этого алгоритма по генерации всех возможных целочисленных композиций в несколько раз (в среднем - более чем в три раза) меньше усредненных времен TSA{m,n) и TQA{m,n) работы алгоритмов SWIFT и QIUCK соответственно. Однако, для практической реализации системы поддержки принятия решений мы выбрали все-таки алгоритм QUICK. Дело в том, что этот алгоритм, в отличие от двух остальных, имеет возможность при генерации всех допустимых (с точки зрения дополнительной информации /) отбрасывать конструируемую композицию на любой стадии ее построения (например, при

вычислении первой компонент композиции), если обнаруживается несоответствие конструируемой композиции требованиям осуществляемой селекции композиций. Два других алгоритма, хотя и не включают «неподходящую» композицию в число отобранных, но вынуждены полностью построить ее для того, чтобы иметь возможность перейти к конструированию композиции со следующим лексикографическим номером. Это преимущество алгоритма QUICK перед алгоритмами SWIFT и FAST становится решающим при создании систем поддержки принятия решений; в которых многократно используется постоянно изменяющаяся информация, определяющая i правила селекции генерируемых композиций (§2.3).

Bi главе; 3 анализируется общая: структура: разработанной системы; поддержки принятия решений АСПИД-3W, зарегистрированной в РосАПО и реализующей описанный в §1.3 метод рандомизированных сводных: показателей.

Рис 1. Блок-схема системы поддержки принятия решений АСПИД-3\У

Система АСПИД-3W, структурная схема которой представлена на рис. 1, реализована в среде Delphi на языке Borland Pascal (размер проекта около 15 тысяч строк исходного кода). Система работает в среде операционных систем. Windows 98/NT/2000, а также использует пакет Microsoft Office 2000 для генерации отчетов. Также, был разработан набор библиотек для вычисления задач на многопроцессорной системе Sun Parastation (16-32 процессора).

Оболочка системы поддержки принятия решений (ОСППР) АСПИД-3 W предназначена для создания в среде Windows на IBM-совместимых ПЭВМ конкретных систем, используемых для"всестороннего оценивания в условиях неопределенности сложных многопараметрических объектов.

В качестве оцениваемых объектов могут выступать сложные технические системы, варианты управленческих и организационных; решений, потребительские товары: и услуги, объекты недвижимости, финансово-экономические проекты, мнения различных экспертов и т.д. При этом оцениваемыми качествами исследуемых, объектов могут служить эффективность, надежность, полезность, безопасность, прибыльность, предпочтительность и т.д.: Реализуя на ПЭВМ ОСППР ACПИД-3W, мы получаем универсальное средство построения гибких интерактивных систем многокритериального оценивания, применимых практически в любых ситуациях, связанных с использованием нечисловой, - неточной i и неполной: информации.

Излагаются основные схемы применения СППР АСПИД-3W для оценки сложных многопараметрических объектов и для оценки вероятностей альтернатив в условиях неопределенности (§3.1).

Подробно описывается г представление результатов построения сводных показателей в виде наглядных АСПИД-диаграмм, примеры которых для случая: трех объектов, характеризуемых пятью показателями, приводятся на рис.2,3.

Object 2 1 I I I I I I 1 Г"

Object 1 ZH HZ ' ZZ 1 IZ

Object 3 1

0.0 0.1 0.2 0.3 0.4 0.S 0.6 0.7 0.8 0.9 1.0

Рис.2.Сводные показатели■ при» отсутствии > ннн-информации (/ = 0)

Object2 I I I I I I I I _ .

Object 1 ' ~

Object 3 ' '"

0.0 0.1 0.2 0.3 0.4 0.S 0.6 0.7 0.8 0.9 1.0

Рис. 3. Сводные показатели; при j ннн-информации > / = {w, > w2 > Wj > w4 > ws]

На этих диаграммах середины полужирных отрезков соответствуют значениям оценок сводных показателей. Длины этих отрезков равны удвоенным стандартным отклонениям рандомизированных сводных показателей. Правые концы тонких линий, расположенных между полужирными отрезками, указывают вероятность доминирования рандомизированного сводного показателя, соответствующего

вышерасположенному полужирному отрезку, над рандомизированным сводным показателем, соответствующим нижерасположенному полужирному отрезку. Этот пример хорошо иллюстрирует результат учета ннн-информации / о весовых коэффициентах: повышается точность оценок сводных показателей (уменьшаются стандартные отклонения) и увеличивается достоверность ранжировки (приближаются к единице многие вероятности доминирования рандомизированных сводных показателей) (§3.1).

Рассматриваются разработанные для СППР АСПИД-3\У алгоритмы обработки нечисловой, неточной и неполной информации (ннн-информации) о весовых коэффициентах, определяющих сравнительную значимость отдельных показателей. Разрабатывается процедура согласования различных компонент инн-информации (§3.2).

Подробно рассматривается пример использования СППР АСПИД-3\У для рейтингования различных вариантов важного и широко распространенного типа программного обеспечения — архиваторов, используемых для «сжатия» информации, хранимой в компьютерах и передаваемой по линиям-связи. Строится иерархическая - система отдельных показателей, каждый из которых оценивает архиваторы с точки зрения: определенного критерия. Последовательно строятся оценки рандомизированных сводных показателей предпочтительности: различных вариантов программного обеспечения (архиваторов) и исследуется влияние на эти показатели дополнительной ннн-информации, которой располагает гипотетический субъект, оценивающий общую предпочтительность архиваторов. Анализируются результаты проведенного с помощью ОСППР АСПИД-3\У исследования качества (предпочтительности) существующих архиваторов (§3.3).

В Заключении приводятся основные результаты и выводы.

В Приложениях 1-5 дается система окон СППР АСПИД-3\¥ (Прил.1), описывается основная схема использования системы АСПИД-3\¥ (Прил.2), указываются исходные характеристики архиваторов, для которых строятся сводные показатели предпочтительности (Прил.З), приводится таблица значений вероятностей попарного доминирования рандомизированных весовых коэффициентов (Прил.4) и дается пример полного отчета ОСППР АСПИД-3\У об одном сеансе своей работы (Прил.5).

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Исследовано влияние неточной (интервальной) и нечисловой (ординальной) информации на общее число допустимых (с точки зрения этой информации) целочисленных композиций. Доказаны соответствующие; теоремы и приведены результаты численных расчетов.

3. Разработаны; два новьж алгоритма и модифицирован один известный алгоритм (алгоритм Рейнгольда) генерации» композиций в лексикографическом порядке, требующие для своей: работы чрезвычайно малый объем машинной памяти.

4. Разработан новый метод распараллеливания программ генерации целочисленных композиций с целью реализации процедур их генерирования на многопроцессорных ЭВМ.

5. Осуществлена программная; реализация трех: разработанных алгоритмов генерации' композиций. Дан сравнительный теоретический анализ программных реализаций и проведено их тестирование на реальной ПЭВМ. Наработана статистика, позволяющая оценить зависимость реального времени генерации от значений параметров композиций.

6. Разработанные алгоритмы генерации, селекции и оценки: композиций, реализованы на ПЭВМ в виде комплекса программ;, составляющих математическое обеспечение работы СППР АСПИД-3'^ основанной на методе рандомизированных сводных показателей..

7. Разработан комплексный демонстрационный пример использования СППР АСПИД-3 W для оценки предпочтительности различных вариантов важного и широко распространенного типа программного обеспечения -архиваторов, используемых для «сжатия» информации, хранимой в компьютерах и передаваемой по линиям связи. Построена иерархическая система тринадцати показателей, характеризующих различные аспекты работы архиваторов.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ3

1. Корников В.В., Хованов К.Н., Хованов Н.В. Система поддержки принятия инвестиционных решений в условиях дефицита информации // Материалы Международной научной конференции; "Информационно-управляющие и вычислительные комплексы на основе новых технологий; Наука и маркетинг". Санкт-Петербург, 2-6 сентября 1992. СПб. СПИАП. 1992. С.67-68.

2. Хованов К.Н. Экспресс-отбор рациональных вариантов предпринимательских решений по распределению ресурсов: // Труды Международного научного конгресса "Народы СНГ накануне третьего тысячелетия". Санкт-Петербург, 15-17 мая г 1996. Том V. Раздел 3. "Методы принятия предпринимательских решений". СПб., Петрополис, 1996. С.20-21.

3. Хованов К.Н. Свидетельство об официальной регистрации программы для ЭВМ' №960087. Программа для ЭВМ "Анализ и Синтез Показателей; при; Информационном Дефиците. АСПИД-ЗШ". Российское агентство по правовой охране программ для ЭВМ, баз данных и топологий интегральных микросхем (РосАПО). М., 22.09.1996.

4. Хованов; К.Н. Экспресс-метод формирования; вариантов инвестиционных проектов // Доклады Всероссийской научной конференции "Инвестиционная политика России в современных условиях". Санкт-Петербург, 15-17 мая 1997. Секция? 5. "Методы обоснования? инвестиционных- и финансовых решений?. СПб., СПбГУ, 1997. С.29-30.

5. Хованов К.Н., Корников В.В., Серегин И.А. Случайные композиции и их применение II Обозрение прикладной и промышленной математики; 2000; Том 7. Вып. 1.С. 152-153.

6. Хованов К.Н. Прикладные математические методы, основанные на: генерации, селекции и оценке целочисленных композиций // Вестник С.-Петербургского ун-та. Серия: математика, механика и астрономия. Деп. ВИНИТИ 01.04.2002 г.№1651-В-39с.

Подписано в печать 24.02.04. формат 60x84 1/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1. Тираж 100 экз. Заказ № 417

ЦОП типографии Издательства СПбГУ. 199061, С.-Петербург, Средний пр., 41.

9-4154

ВВЕДЕНИЕ.

ГЛАВА 1. СИСТЕМА КОМБИНАТОРНЫХ ОБЪЕКТОВ, СВЯЗАННЫХ

С ЦЕЛОЧИСЛЕННЫМИ КОМПОЗИЦИЯМИ.

§1.1. Генерация, селекция и оценка комбинаторных объектов, связанных с целочисленными композициями.

§1.2. Прикладные математические методы, основанные на генерации и селекции целочисленных композиций.

§1.3. Генерация и селекция целочисленных композиций в методах анализа и синтеза сводных показателей сложных объектов.

ГЛАВА 2. АЛГОРИТМЫ ГЕНЕРАЦИИ ЦЕЛОЧИСЛЕННЫХ КОМПОЗИЦИЙ

И ДИСКРЕТНЫХ ПУТЕЙ НА РЕШЕТКЕ.

§2.1. Оценка объема множеств композиций и дискретных путей на целочисленной решетке.

§2.2. Алгоритмы генерации композиций и дискретных путей на целочисленной решетке.

§2.3. Анализ и тестирование алгоритмов генерации композиций и дискретных путей на целочисленной решетке.

ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДА СВОДНЫХ ПОКАЗАТЕЛЕЙ С ИСПОЛЬЗОВАНИЕМ АЛГОРИТМОВ ГЕНЕРАЦИИ ЦЕЛОЧИСЛЕННЫХ КОМПОЗИЦИЙ.

§3.1. Оболочка системы поддержки принятия решений АСПИД-3\У, реализующей метод рандомизированных сводных показателей.

§3.2. Алгоритмы обработки нечисловой, неточной и неполной информации о целочисленных композициях, используемых в ОСППР АСПИД-3\У.

§3.3. Применение метода сводных показателей для оценки программного обеспечения.

Актуальность темы диссертационного исследования

В последние десятилетия получили широкое распространение прикладные программы, использующие алгоритмы генерации и селекции различных комбинаторных объектов. Важное применение комбинаторные алгоритмы находят в современной информатике, где используются методы, предполагающие осуществление направленного перебора различных математических структур (конечных графов, переключательных схем, булевых функций, опорных планов и т.п.) (см., например, работы [22,23,25,26,36,46,47,72,80,86]).

Особенно следует отметить роль комбинаторных алгоритмов перебора структур разного вида (графы, деревья, разбиения и т.п.) в методах многокритериальной оптимизации (см. [56,78,79,97]), теории принятия многокритериальных решений (см. [48,51,52,99,106,124,127]), в методах теории расписаний [41], в системах искусственного интеллекта [54], в современных интерактивных системах анализа данных [28] и т.д. (см., например, [4,46,81,84]).

Критически важными являются комбинаторные алгоритмы для работы ряда экспертных систем [84,127]. Например, одна из немногих успешно действующих экспертных систем, - система SCENARIO-AGENT, разработанная еще в 1988 году в RAND Corporation для анализа стратегических конфликтов, базируется на комбинаторной генерации возможных сценариев развития конфликта, которые затем подвергаются экспертной селекции (см.[84]). Гибкость и универсальность алгоритмов генерации и селекции различных комбинаторных объектов обеспечили их широкое применение в различных прикладных областях, начиная от экономики и военного дела (см., например, [15-18,38,79,89,91,92,115]) и кончая химией [37,87], генетикой и экологией [29-31,42,65-67,69,71,101,102].

Важным частным случаем рассматриваемых комбинаторных алгоритмов являются алгоритмы генерации и селекции так называемых композиций (упорядоченных разбиений) (*(1),.,х(т)), л(1 ) + .+х(т) = п, натурального числа п (см. [72,73,100,120]). Такие алгоритмы генерации и селекции композиций используются в различных экспертных системах и в системах поддержки принятия решений (СППР) по распределению дискретных ресурсов по конечному числу позиций. Например, в основе широко распространенной экспертной системы BATTLE, первый прототип которой был создан в 1988 году в Naval Research Laboratory (USA NAVY), лежит перебор всех возможных распределений (упорядоченных разбиений) боевых сил и средств по целям противника с последующим отбором эффективных вариантов (см. [84]). Особенно важную роль рассматриваемые комбинаторные алгоритмы играют в СППР, ориентированных на использование нечисловой, неточной и неполной информации о весовых коэффициентах и/или вероятностей.

Эти СППР в последнее время широко применяются для синтеза сводных оценок сложных объектов разной природы, например, для построение оценок многопараметрических технических систем военного назначения и НИР, направленных на разработку таких систем [38], для сводной оценки сложных финансово-экономических объектов (коммерческих банков, страховых компаний и т.п.) [1114,17,65-57,115], для формирования рациональных вариантов инвестиционного портфеля [89,91], для оценивания экологического состояния и устойчивости геосистем [29-31], для построения непараметрических байесовских оценок распределений случайных величин [40], для выявления статистических зависимостей по наблюдениям за траекториями стохастического процесса [10] и т.д.

Комбинаторные объекты (композиции и монотонно неубывающие траектории на целочисленной решетке), используемые в вышеуказанных прикладных методах, весьма многочисленны - их число N(m,n) очень быстро растет с увеличением параметров т и п (см. [93]). Действительно, даже для умеренных значений т и п число всех возможных композиций (число всех возможных монотонных траекторий на целочисленной решетке) весьма значительно: 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. Поскольку время T(m,n), требуемое для полного перебора исследуемых комбинаторных объектов, можно в первом приближении оценить сверху величиной T(m,ri)& С-т-N{m,ri), где константа С определяется типом процессора, особенностями алгоритма, операционной системой и тому подобными обстоятельствами, постольку следует ожидать драматического увеличения времени работы соответствующих методов. Поэтому, весьма актуальной является задача повышения скорости вычислений за счет распараллеливания соответствующих вычислительных процессов.

Цель и задачи диссертационной работы

Цель работы заключается в исследовании и программной реализации комплекса комбинаторных методов генерации, селекции и оценки целочисленных композиций для разработки программного обеспечения прикладной системы поддержки принятия решений (СППР), реализующей метод построения сводных показателей в условиях неопределенности. Для достижения этой цели должны быть решены следующие основные задачи:

• провести анализ различных прикладных методов на предмет выявления особенностей использования в этих методах комбинаторных структур, связанных с целочисленными композициями;

• разработать и протестировать алгоритмы генерации, селекции и оценки соответствующих комбинаторных объектов;

• разработать метод распараллеливания построенных алгоритмов генерации композиций;

• разработать программное обеспечение, основанное на созданных алгоритмах генерации целочисленных композиций, системы поддержки принятия решений, реализуемой на ПЭВМ в виде прикладной программы АСПИД-3\У, позволяющей пользователю оценивать в интерактивном режиме сложные много-параметрические объекты.

• проверить работоспособность построенной СППР АСПИД-3\У на примере построения по иерархической системе исходных характеристик сводных показателей предпочтительности различных вариантов архиваторов с использованием нечисловой, неточной и неполной информации о сравнительной значимости исходных характеристик эффективности работы этих архиваторов.

Методы исследования

Исследование алгоритмов генерации, селекции и оценки комбинаторных объектов, связанных с целочисленными композициями, проводится в диссертации с использованием методов анализа программ для ЭВМ, методов общей комбинаторики и теории разбиений. Анализ применения разработанных алгоритмов для создания прикладного программного обеспечения осуществляется с использованием методов теории принятия решений при неопределенности, теории вероятностей и математической статистики. Использовались также методы тестирования программ для ЭВМ и методы оценки работы прикладного программного обеспечения (в частности, методы оценки эффективности работы архиваторов).

Научная новизна

1. Разработан новый алгоритм генерации композиций (алгоритм FAST), использующий, в отличие от известного алгоритма Рейнгольда (алгоритм SWIFT), предварительно построенные монотонные пути на целочисленной решетке, что позволяет ускорить процесс примерно в три раза по сравнению с алгоритмом SWIFT.

2. Разработан новый алгоритм генерации композиций (алгоритм QUICK), отличающийся от известных алгоритмов возможностью использовать дополнительную информацию о компонентах композиции без построения всей композиции, что позволяет в ряде случаев ускорить генерацию композиций на несколько порядков по сравнению с алгоритмами SWIFT и FAST.

3. Предложен новый метод распараллеливания программ генерации композиций, использующий разработанные новые алгоритмы лексикографической нумерации/денумерации композиций (алгоритмы LEXCOMP/COMPLEX), отличающийся от существующих методов распараллеливания большой простотой и позволяющий сократить время генерации множества всех возможных композиций пропорционально числу используемых процессоров.

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

Практическая и теоретическая ценность

Полученные теоретические результаты об асимптотике числа комбинаторных объектов, связанных с целочисленными композициями, могут быть использованы при анализе скорости работы и предельных возможностей различных комбинаторных алгоритмов.

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

Разработанная в рамках настоящего диссертационного исследования прикладная программа АСПИД-3\У, реализующая систему поддержки принятия решений в условиях неопределенности, официально зарегистрирована РосАПО и в настоящее время практически используется для решения многих конкретных задач, связанных с построением сводных оценок сложных объектов различной природы и назначения.

Реализация результатов работы

Система поддержки принятия решений АСПИД-3\У и другие программные продукты, разработанные в рамках диссертационной работы, практически использовалась при выполнении перечисленных ниже НИР, проводимых в Санкт-Петербургском институте информатики и автоматизации РАН (СПИИРАН) лабораторией вычислительных систем и проблем защиты: «Анализ, классификация и оценка уровня защищенности информационных систем», «Анализ и оценка рисков нарушения безопасности в сложных информационных системах при дефиците информации», «Разработка метрик для оценки качественных аспектов моделей программ» (2001-2003 гг.).

В лаборатории интеллектуальных систем СПИИРАН разработанные в диссертации методы обработки композиций практически использовались в НИР «Разработка программных средств оптимизации планирования комплексного БСК», выполнявшейся по договору с ФГУП «Комета» лабораторией интеллектуальных систем СПИИРАН (2002-2003 гг.).

Результаты диссертационной работы были внедрены в ГУП «Санкт-Петербургский информационно-аналитический центр» и использованы при разработке Интегрированной системы информационно-аналитического обеспечения Администрации Санкт-Петербурга (2002-2003 гг.).

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

Апробация работы

Основные результаты и выводы диссертации докладывались: на заседаниях кафедры информатики математико-механического факультета СПбГУ (2001-2003 гг.); на Международной научной конференции «Информационно-управляющие и вычислительные комплексы на основе новых технологий» (СПб., 1992 г.); на Международном научном конгрессе «Народы СНГ накануне третьего тысячелетия»; секция «Математические методы принятия предпринимательских решений» (СПб., 1996 г.); на Всероссийской научной конференции «Инвестиционная политика России в современных условиях»; секция «Математические методы обоснования инвестиционных и финансовых решений» (СПб., 1997 г.); на Пятой Международной конференции «Вероятностные методы в дискретной математике». (Петрозаводск, 2002).

Для решения поставленных задач, обеспечивающих достижение основной цели диссертации, нами выбрана следующая структура диссертационной работы.

В главе 1 определяются основные виды комбинаторных объектов, связанных с понятием целочисленной композиции (упорядоченным разбиением натурального числа на фиксированное число слагаемых): нормированные композиции', монотонные пути (траектории) с закрепленными концами, проходящие через узлы конечной целочисленной решетке; нормированные монотонные пути (траектории) с закрепленными концами. Описывается процедура селекции введенных комбинаторных объектов на основе использования нечисловой (ординальной), неточной (интервальной) и неполной информации. Изучается вопрос о возможном усилении системы неравенств, формализующих интервальную информацию, имеющуюся у исследователя. Вводятся различные коллективные и индивидуальные оценки комбинаторных объектов, получаемых в результате селекции (§1.1).

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

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

В главе 2 проводится, прежде всего, теоретическое оценивание числа N(m,n) всех возможных целочисленных композиций (упорядоченных разбиений натурального числа п на т частей). Для этого исследуется асимптотика величины N(m,n) при различных соотношениях для параметров т,п, значения которых стремятся к бесконечности. Оценивается также влияние длины цепочки неравенств, задаваемых исследователем для компонент композиции, на общее число N(m,n;I) допустимых (с точки зрения данной системы неравенств /) композиций. Помимо исследования асимптотического поведения величины N(m,n), проводятся прямые вычисления этого числа для небольших значений параметров т, п (§2.1). Разрабатываются три алгоритма генерации целочисленных композиций, один из которых является модификацией известного алгоритма прямой генерации композиций в лексикографическом порядке, а два других представляют собой новые разработки, в которых используется предварительное генерирование монотонных путей на целочисленной решетке, с последующим переходом к соответствующим целочисленным композициям. Для всех трех алгоритмов дается их программная реализация. Обсуждается вопрос об использовании разработанных алгоритмов для построения единой процедуры распараллеливания процесса генерации целочисленных композиций с целью реализации генерирования этих комбинаторных объектов на многопроцессорных ЭВМ (§2.2). Проводится теоретический сравнительный анализ программных реализаций трех разработанных алгоритмов генерации целочисленных композиций. Кроме того, эти реализованные алгоритмы тестируются на реальной ПЭВМ с наработкой статистики, позволяющей в первом приближении оценить зависимость реального времени генерации композиций от значений параметров т, п. Определяются как среднее время генерации всех N(m,n) возможных целочисленных композиций, так и среднее время генерации одной композиции при различных значениях параметров т, п и при использовании различных алгоритмов (§2.3).

В главе 3 анализируется общая структура разработанной нами оболочки системы поддержки принятия решений (ОСППР) АСПИД-3\У, реализующей описанный в §1.3 метод рандомизированных сводных показателей (МРСП). Реализованный на ПЭВМ ОСППР АСПИД-3\\^ официально зарегистрирован Российским агентством по правовой охране программ для ЭВМ, баз данных и топологий интегральных микросхем (РосАПО). Подробно излагаются основные схемы применения оболочки СППР АСПИД-3\У для оценки сложных многопараметрических объектов и для оценки вероятностей альтернатив в условиях неопределенности (§3.1). Рассматриваются разработанные нами для ОСППР АСПИД-3\У алгоритмы обработки неточной (интервальной) и нечисловой (ординальной) информации (инн-информации) о весовых коэффициентах, определяющих сравнительную значимость отдельных показателей. В предположении, что ннн-информация представима в виде систем равенств и неравенств, разрабатывается процедура согласования получаемых систем неравенств и проверки непротиворечивости этих систем (§3.2). Подробно рассматривается пример использования ОСППР АСПИД-ЗУ/ для рейтингования различных вариантов важного и широко распространенного типа программного обеспечения - архиваторов, используемых для «сжатия» информации, хранимой в компьютерах и передаваемой по линиям связи. Строится иерархическая система отдельных показателей, каждый из которых оценивает архиваторы с точки зрения определенного критерия. Последовательно строятся оценки рандомизированных сводных показателей предпочтительности различных вариантов программного обеспечения (архиваторов) и исследуется влияние на эти показатели дополнителной ннн-информации, которой располагает гипотетический субъект, оценивающий общую предпочтительность архиваторов. Анализируются результаты проведенного с помощью ОСППР ЛCПИД-ЗW исследования качества (предпочтительности) существующих архиваторов (§3.3).

В Заключении приводятся основные результаты диссертационной работы.

В Приложениях 1-5 дается система окон СППР ЛСПИД-ЗШ (Прил.1), описывается основная схема использования системы АСПИД-ЗУ/ (Прил.2), указываются исходные характеристики архиваторов, для которых строятся сводные показатели предпочтительности (Прил.З), приводится таблица значений вероятностей попарного доминирования рандомизированных весовых коэффициентов (Прил.4) и дается пример полного отчета ОСППР АСПИД-3\М об одном сеансе своей работы (Прил.5).

ЗАКЛЮЧЕНИЕ

Приведем основные результаты и выводы, полученные в настоящей диссертационной работе и выносимые на защиту.

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

2. Исследовано влияние неточной (интервальной) и нечисловой (ординальной) информации на общее число допустимых (с точки зрения этой информации) целочисленных композиций. Доказаны соответствующие теоремы и приведены результаты численных расчетов.

3. Разработаны два новых алгоритма и модифицирован один известный алгоритм (алгоритм Рейнгольда) генерации композиций в лексикографическом порядке, требующие для своей работы чрезвычайно малый объем машинной памяти.

4. Разработан новый метод распараллеливания программ генерации целочисленных композиций с целью реализации процедур их генерирования на многопроцессорных ЭВМ.

5. Осуществлена программная реализация трех разработанных алгоритмов генерации композиций. Дан сравнительный теоретический анализ программных реализаций и проведено их тестирование на реальной ПЭВМ. Наработана статистика, позволяющая оценить зависимость реального времени генерации от значений параметров композиций.

Разработанные алгоритмы генерации, селекции и оценки композиций реализованы на ПЭВМ в виде комплекса программ, составляющих математическое обеспечение работы СППР АСПИД-3\У, основанной на методе рандомизированных сводных показателей.

Разработан комплексный демонстрационный пример использования СППР АСПИД-3\\Г для оценки предпочтительности различных вариантов важного и широко распространенного типа программного обеспечения - архиваторов, используемых для «сжатия» информации, хранимой в компьютерах и передаваемой по линиям связи. Построена иерархическая система тринадцати показателей, характеризующих различные аспекты работы архиваторов.

1. Авен П.О., Мучник И.Б., Ослон A.A. Функциональное шкалирование. Агрегирующие интегральные показатели. М., Наука, 1986.

2. Алимов А.Ф., Дмитриев В.В., Флоринская Т.М. Интегральная оценка экологического состояния и качества среды городских территорий. СПб., СПб. НЦРАН, 1999.

3. Андрианов Ю.М., Субетто А.И. Квалиметрия в приборостроении и машиностроении. Л., ЛГУ, 1990.

4. Беккенбах Э. (Ред.) Прикладная комбинаторная математика. М., Мир, 1968.

5. Бирман Г., Шмидт С. Экономический анализ инвестиционных проектов. М., Экономика, 1997.

6. Богданчук В.З., Егоров Б.М., Катулев А.Н. Агрегирование векторных критериев. Л., ЛИИАН, 1990.

7. Борисенко A.A., Губарев С.И., Дуброва Л.Д. Генерирование сочетаний на основе биномиальных чисел // Автоматиз. системы упр. и приборы автомат. 1985. №73. С.78-80.

8. Бромвич М. Анализ экономической эффективности капиталовложений. М., Мир, 1996.

9. Букан Дж., Кенигсберг Э. Научное управление запасами. М., ИЛ , 1967.

10. Буре В.М., Колесникова О.Н., Корников В.В. Простой статистический метод выявления монотонной зависимости среди наблюдаемых траекторий стохастического процесса. Л., ЛНИВЦ АН СССР, 1983.

11. П.Вишняков И.В. Анализ динамики надежности коммерческих банков // Банковское дело. 1995. № 8. С.7.

12. Вишняков И.В. Стохастические модели рейтингового анализа // Сборник трудов Международного института инвестиционных проектов. М., 1995. С.40-46.

13. Вишняков И.В. О рейтингах коммерческих банков. Экономическая теория и хозяйственная реформа // Сборник научных трудов Санкт-Петербургской инженерно-экономической академии. СПб., 1995. С. 66-69.

14. Вишняков И.В. Надежность коммерческих банков и методы ее оценки. Автореферат диссертации на соискание ученой степени кандидата экономических наук. СПб., СПбГУ, 1995.0

15. Вишняков И.В. Экономико-математические модели оценки деятельности коммерческих банков. СПб., СПбГУ. 1999.

16. Вишняков И.АВ., Довгаль В.В. Анализ динамики надежности коммерческих банков // Математические методы в социально-экономических исследованиях. СПб., Петрополис, 1996. С. 8-33.

17. Вишняков И.В., Михайлов М.В. Методика оценивания финансово-экономических объектов с использованием СППР АСПИД -3. СПб., СПбГУ, 1998.• 18. Вишняков И.В. Пашкус В.Ю. Российские банки. Классические подходы исовременное состояние. СПб., СПбГУ, 1998.

18. Воронцовский A.B. Инвестиции и финансирование. СПб., СПбГУ, 1998.

19. Герасимова Л.В., Погожев И.Б. Комплексная оценка качества проектов и выбор оптимального варианта по методу академика А.Н. Крылова // Стандарты и качество. 1972. №8. С. 37-39.

20. Гитман JI., Джонк М. Основы инвестирования. М., Дело, 1997.

21. Горбатов В.А. Теория частично упорядоченных систем. М., Советское радио, 1976.

22. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. М., Наука, 1999.

23. Гроот М. Оптимальные статистические решения. М., Мир, 1974.

24. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М., Мир, 1998.

25. Гульден Я., Джексон Д. Перечислительная комбинаторика. М., Наука, 1990.

26. Гурин J1.C., Дымарский Я.С., Меркулов А.Д. Задачи и методы оптимального распределения ресурсов. М., Наука, 1968.

27. Дидэ Э. Методы анализа данных. М., Финансы и статистика, 1985.

28. Дмитриев В.В., Мякишева Н.В. Многокритериальная оценка экологического состояния и устойчивости геосистем на основе метода сводных показателей. 1. Качество природных вод // Вестник С.-Петербургского университета. 1996. № 21. С. 40-52.

29. Догановский A.M., Мякишева H.B. Многокритериальная классификация озерных систем в условиях неопределенности // Водные ресурсы Северо-Западного региона России. СПб., РГГМУ, 1999. С. 67-77.

30. Доес Р. Устойчивая привлекательность неправильных линейных моделей принятия решений // Нормативные и дескриптивные модели принятия решений. М., Мир, 1981. С.305-309.

31. Завлин П.Н., Васильев A.B., Кноль А.И. Оценка экономической эффективности инвестиционных проектов. Современные подходы. СПб., Петрополис, 1995.• 34. Зельнер А. Байесовские методы в эконометрии. М., Наука, 1980.

32. Зубов В.И., Петросян JT.A. Задача распределения капиталовложений. Л., ЛГУ, 1971.

33. Кнут Д. Искусство программирования для ЭВМ. Т.1-3. М., Мир, 1976-1978.

34. Кинг Р. (Ред.) Химические приложения топологии и теории графов. М., Мир, 1987.

35. Колганов С.К., Корников В.В., Попов П.Г. Построение в условиях дефицита информации сводных оценок сложных систем. М., Радио и связь, 4.1, 2. 1994, 1998.

36. Колесникова О.Н., Корников В.В., Рожков H.H. Стохастические процессы с равновероятными монотонными реализациями, моделирующие дефицитинформации//Вестник ЛГУ. 1987. №1. С.21-26.

37. Колесникова О.Н., Хованов Н.В. Прямой байесовский метод оценки распределений и параметров одномерных случайных величин. Л., ЛНИВЦ АН СССР. 1981.

38. Конвей Р., Максвелл В., Миллер Л. Теория расписаний. М., Наука, 1975.

39. Корников В.В., Серегин И.А. Комплексная оценка воздействия геопатогенных зон на биологические системы // Математические методы исследования управляемых динамических систем. СПб., СПбГУ, 2000. С. 113-117.

40. Корсаков И.Н. Стохастические модели построения сводных показателей сложных систем в условиях дефицита информации. Автореферат диссертации на соискание ученой степени кандидата физ-мат. наук. Л., ЛГУ, 1989.

41. Корсаков И.Н., Новоселова Г.В. Об одном методе синтеза сводных показателей. Деп. ВИНИТИ, № 4502-В. М., 1986. 16 с.

42. Кофман А. Введение в прикладную комбинаторику. М., Наука, 1975.

43. Кристофидес Н. Теория графов. Алгоритмический подход. М., Мир, 1978.

44. Ларичев О.И. Наука и искусство принятия решений. М., Наука, 1979.

45. Ларичев О.И. Объективные модели и субъективные решения. М., Наука, 1987.

46. Ларичев О.И. Теория и методы принятия решений. М., Логос, 2000.

47. Ларичев О.И., Мошкович Е.М. Качественные методы принятия решений. Вербальный анализ решений. М., Наука, 1996.

48. Левченков В.С. Алгебраический подход в теории выбора. М., Наука, 1990.

49. Лихтенштейн В.Е. Дискретность и случайность в экономико-математических задачах. М., Наука, 1973.

50. Лорьер Ж.-Л. Системы искусственного интеллекта. М., Мир, 1991.

51. Лурье Л. Алгоритм решения распределительной задачи // Применение математики в экономических исследованиях. Т.2., М., 1961, с.200-224.

52. Майника Э. Алгоритмы оптимизации на сетях и графах. М., Мир, 1978.

53. Массе П. Критерии и методы оптимального распределения капиталовложений. М., Мир, 1971.

54. Махмудов З.М. Стохастическая модель дефицита информации при выборе весовых коэффициентов в сводном показателе // Вопросы вычислительной и прикладной математики. 1989. Вып. 87. С. 150-159.

55. Махмудов З.М. Учет дополнительной информации при рандомизированном синтезе сводных показателей // Вопросы вычислительной и прикладной математики. 1990. Вып.88. С. 114-122.

56. Махмудов З.М. Учет ограничений при моделировании неопределенности выбора весовых коэффициентов // Вопросы вычислительной и прикладной математики. 1990. Вып. 90. С. 20-27.

57. Махмудов З.М. Стохастические модели неопределенности выбора весовых коэффициентов в методе сводных показателей. Автореферат диссертации на соискание ученой степени кандидата физ-мат. наук. Л., ЛГУ, 1991.

58. Михайлов М.В. Комбинаторные алгоритмы генерации весовых коэффициентов. Деп. ВИНИТИ, № 2808-В96. М., 1996. 16 с.

59. Михайлов М.В. Построение множества согласованных допустимых векторов весовых коэффициентов в методе сводных показателей. Деп. ВИНИТИ, Ш• 3645-В96. М., 1996. 12 с.

60. Михайлов М.В. Модель рейтингования страховых компаний П Вестник С.-Петербургского университета. 1997. №26. С. 103-106.

61. Михайлов М.В. Применение метода сводных показателей для многокритериального оценивания страховых компаний в условиях неопределенности. Автореферат диссертации на соискание ученой степени кандидата экономических наук. СПб., СПбГУ, 1997.

62. Моррис У. Наука об управлении. Байесовский подход. М., Наука, 1971.

63. Первозванский А.А., Первозванская Т.Н. Финансовый рынок: расчет и риск. М., Финансы и статистика, 1994.

64. Попов П.Г. Система методов и средств обоснования выбора приоритетных фундаментальных и поисковых исследований и распределения ассигнований на них. Автореферат диссертации на соискание ученой степени доктора технических наук. СПб., СПИИРАН, 1995.

65. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и Щ практика. М., Мир, 1980.

66. Риордан Дж. Комбинаторные тождества. М., Наука, 1982.

67. Рожков H.H. Рандомизированный критерий сравнения качества сложных объектов // Экономика и математические методы. Том 27. Вып.З. М., АН СССР, 1991, с.597-600.

68. Савчук В.П. Байесовские методы статистического оценивания. М., 1989.

69. Самандаров Э.Г. Об одном уточнении формулы Стирлинга // Доклады АН Тадж. ССР. 1985. Том 28. №2. С.77-79.

70. Самандаров Э.Г. Замечание к формуле Стирлинга // Доклады АН Тадж. ССР. 1988. Том 32. №8. С.503-505.

71. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М., Мир, 1984.

72. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. М., Наука, 1981.

73. Схрейвер А. Теория линейного и целочисленного программирования. Т. 1, 2. М., Мир, 1991.

74. Такач J1. Комбинаторные методы в теории случайных процессов. М., Мир, 1971.

75. Тондл J1. Отношение предпочтения // Вопросы кибернетики. 1984. №90. С.147-170.

76. Трухаев Р.И. Модели принятия решений в условиях неопределенности. М., Наука, 1981.

77. Уотермаи Д. Руководство по экспертным системам. М., Мир, 1989.

78. Фишберн П. Многомерные функции полезности в теории ожидаемой полезности // Статистические модели и многокритериальные задачи принятия решений. М., 1979. С. 10-44.

79. Харари Ф., Палмер Э. Перечисление графов. М., Мир, 1977.

80. Харгиттаи И., Харгитгаи М. Симметрия глазами химика. М., Мир, 1989.

81. Хей Дж. Введение в методы байесовского статистического вывода. М., Мир, 1987.

82. Хованов К.Н., Корников В.В., Серегин И.А. Случайные композиции и их 9 применение // Обозрение прикладной и промышленной математики. 2000. Том 7.1. Вып. 1.С. 152.

83. Хованов К.Н. Прикладные математические методы, основанные на генерации, селекции и оценке целочисленных композиций // Вестник С.-Петербургского унта. Серия: математика, механика и астрономия. Деп. ВИНИТИ 01.04.2002 г. №1651-В -39 с.

84. Хометок В.В. Элементы теории многоцелевой оптимизации. М., Наука, 1983.

85. Шарп У., Александер Г., Бэйли Дж. Инвестиции. М., Дело, 1997.

86. Шеннон Л. Работы по теории информации и кибернетике. М., ИЛ, 1963.

87. Штойер Р. Многокритериальная оптимизация. Теория вычисления и приложения. М., Радио и связь, 1992.

88. Штойян Д. Качественные свойства и оценки стохастических моделей. М., Наука, 1979.

89. Эддоус М., Стансфилд Р. Методы принятия решений. М., Юнити, 1997. ЮО.Эндрюс Г. Теория разбиений. М., Наука, 1982.

90. Afgan N., Carvalho М. Energy systems assessment with sustainability indicators U Energy Policy. 2000. Vol. 28. P. 603-612.

91. Afgan N., Carvalho M. Multi-criteria sustainability assessment of clean air technologies//Transactions of FAMENA. 2002. Vol. 26. N. 1. P. 1-14.

92. All M. Content of the frustrum of a simplex // Pacific J. Math. Vol.48. N 2. P.313-322.

93. Bawa V. Stochastic dominance: a research bibliography // Management Sci. 1981. Vol.28. P.698-712.

94. Beesack P. Improvements of Stirling's formula by elementary methods // Publ. Elektrotechn. Fak. Univ. Beogradu. 1969. №274. P. 17-21.ft 106.Biswan T. Decision-Making under Uncertainty. London, Macmillan, 1997.

95. BIyth C. Some probability paradoxes in choice from among random alternatives // J. Amer. Stat. Assoc. 1972. Vol.67. N.338. P.366-373.

96. Borcherding K., Schmeer S., Weber M. Biases in multi-attribute weight elicitation // Contributions to Decision Research. 1993, Amsterdam. P.97-128.

97. Dawes R., Carrigan B. Linear models in decision making // Psychol. Bull. 1974. Vol.81. P.95-106.1 lO.Dombi J. Basic concepts for a theory of evaluation: the aggregative operator // Eur. J.Oper. Res. 1982.VoI.10. N3. P.281-293.

98. Gan C. A note on combination generators // ACM Trans. Math. Software. 1985. Vol.11. N.2. P.154-156.

99. Gerber L. The volume cut off a simplex by a half space // Pacific J. Math. 1981. Vol.94. N 2. P.311-314.

100. Jerrum M. Random generation of combinatorial structures from an uniform distribution //Theoretical Computer Science. 1986.Vol.43. N.2-3. P. 169-188.

101. Kahneman D., Slovic P., Tversky (eds.) Judgment under Uncertainty: Heuristics and ' Biases. Cambridge, 1982.

102. Kolari J. Estimating the overall financial performance of banks using a new method for quantifying subjective information // The Journal of Financial Engineering. 1998. Vol.7. N.l. P.59-77.

103. Larichev O., Moshkovich E., Rebrik S. Systematic research into human behavior in multi-attribute object classification problems // Acta Psychologica. 1988. N 68. P.171-182.

104. Lin C., Salkin H. An efficient algorithm for the complete set partitioning problem // Discrete Applied Mathematics. 1983. Vol.6. N.2. P.149-156.

105. Lin C. A parallel algorithm for generating combinations // Comput. And Math. Appl. 1989. Vol. 17. N. 12. P. 1523-1533.

106. MacMahon P. Memoir on the theory of the compositions of numbers // Philosophical Transactions Royal Society of London. 1894. Vol. A184. P.835-901.

107. HO.McGregor J., Narayana T., Ozsoyoglu Z. On touching, crossing and meetings of lattice paths with the diagonal // Utilitas Mathematica. 1986. Vol.30. P.45-51.

108. Markowitz H.M. Portfolio selection //J. of Finance. 1952. Vol.7. N.l. P.77-91.

109. Markowitz H.M. Mean-variance analysis in portfolio choice and capital market. N.Y., 1987.

110. Marlowe J., Paull M. Least cost partition algorithms // Discrete Applied Mathematics. 1989. Vol.22. N.3.P.215-239.

111. Murtagh F. Counting dendrograms: a survey // Discrete Applied Mathematics. 1984. Vol.7. N.2. P. 191-199.

112. Semba I. An efficient algorithm for generating all partitions of the set {l,2,.,n} // J.1.f. Process. 1984. Vol.7. N.l. P.41-42. 126.Spira R. Calculation of the gamma function by Stirling's formula // Math. Comput. 1971. Vol.25. №114. P.317-322.

113. Vari A., Vecsenyi J. Selecting decision support methods in organizations // Journal of Applied Systems Analysis. 1994. Vol.11. P.23-36.

114. Varsi G. The multidimensional content of the frustrum of the simplex // Pacific J. Math. 1973. Vol.46. N 1. P.303-314.

115. Weber M., Eisenfuhr F., Winterfeldt D. The effects of splitting attributes on weights in multi-attribute utility measurement // Management Science. 1988. Vol. 34. N 4. P. 431-445.

116. Wittmuss A. Scalarizing multiobjective optimization problems // Math. Res. 1985. Vol.27. P.255-258.