Содержание к диссертации
Введение
Глава 1. Методы, модели и средства проектирования муниципальной интегрированной информационной системы 8
1.1. Город как предметная область муниципальной интегрированной информационной системы 8
1.2. Опыт создания интегрированных информационных систем города 12
1.3. Анализ методов и средств проектирования интегрированных информационных систем города 19
1.4. Применение методов и средств имитационного моделирования в поддержке принятия решений 23
1.4.1. Анализ существующих средств автоматизации моделирования...23
1.4.2. Общее описание этапов имитационного моделирования 32
1.4.3. Вычислительные эксперименты 36
1.4.4. Поддержка функций направленного вычислительного эксперимента 37
1.4.5. Интегрированная информационная среда 44
Выводы по первой главе 46
Глава 2. Методы и модели принятия решений в интегрированной информационной системе управления городом 49
2.1. Общие модели и методы 49
2.2. Методы анализа мультипликатора 49
2.3. Регрессионные уравнения эконометрической модели города 55
2.4. Математические модели, используемые при строительстве новых городов 66
2.5. Колебания и разветвления в динамических системах 68
2.5.1. Экономический хаос 69
2.5.2, Колебания населения городов 70
2.6. Модель финансовой деятельности инновационного банка 71
2.6.1. Модель финансовых циклов 71
2.6.2. Модель финансирования при конкурсном отборе 73
2.6.3. Модель рискового финансирования 74
2.7. Математическая модель управления трудовыми ресурсами 79
2.7.1. Цели и критерии управления 79
2.7.2. Модель движения кадров 84
2.8. Имитационное моделирование медико-демографических процессов 90
Выводы по второй главе 98
Глава 3. Модели оперативного планирования и оперативного управления городом 100
3.1. Основные определения теории дискретных технологических систем 100
3.2. Математическая модель системы в задаче планирования 104
3.2.1. Определение задачи планирования как задачи составления расписания 104
3.2.2. Ресурсы 107
3.2.3. Система ограничений 110
3.2.4. Критерии 115
3.2.5. Расписание 116
3.3. Поиск решения задачи составления расписания для ГДТС на базе метода двойного ранжирования 117
3.3.1. МДР как обобщенная эвристическая схема 117
3.3.2. МДР как точный комбинаторный метод 122
3.4. Выделение инвариантной и настраиваемой части 128
3.4.1. Система ограничений 130
3.4.2. Множество оптимизирующих требований 131
3.4.3. Критерии 132
3.5. Оперативное управление городом 134
3.5.1. Основные понятия 134
3.5.2. Функциональная структура комплекса управления городом 136
3.6. Оценка стоимости проекта 141
Выводы по третьей главе 147
Заключение 148
Литература 149
Приложения 162
- Анализ методов и средств проектирования интегрированных информационных систем города
- Математические модели, используемые при строительстве новых городов
- Математическая модель системы в задаче планирования
- Поиск решения задачи составления расписания для ГДТС на базе метода двойного ранжирования
Введение к работе
Актуальность темы. За последние пять-шесть лет в результате реформ в нашей стране сложилась совершенно новая система самоуправления, Возникли новые органы, наделенные совершенно новыми полномочиями для своего уровня. Претерпела значительные изменения законодательно-правовая база. Созданные в старой системе информационные технологии поддержки принятия решения не отвечают современным потребностям органов муниципального управления.
Во-первых, во все эти системы так и не были достаточно эффективно интегрированы. Объяснением, по-видимому, служит отсутствие до последнего времени достаточно мощных технических и программных средств для обеспечения эффективной эксплуатации таких автоматизированных систем (АС) в реальном масштабе времени, обработки и хранения достаточно больших объемов информации, сложность самой проблемы построения интегрированных систем, призванных решать глобальные задачи управления социально-экономическими объектами; а также недостаточные масштабы исследований, ведущихся в данном направлении.
Во-вторых, на аналогичном уровне управления информационные технологии не реализовывали столь широкий круг полномочий, а на вышестоящих уровнях не учитывали всех особенностей территориального управления и имели несколько другую специфическую направленность. Следовательно на современном этапе в России существует некоторый вакуум в технологиях поддержки принятия решения в управлении на муниципальном уровне.
В-третьих, зарубежная практика в этой области до самого последнего времени не отвечала требованиям комплексности и охватывала главным образом автоматизацию информационно-справочных задач, практически не используя задачу управления как целевую функцию. Основываясь на отечественном опыте комплексного системного подхода, где используется всевозможное аналитическое, моделирующее и оптимизирующее наполнение вычислительных ресурсов, связанных с достижениями в об- -6-ласти теории управления, математики и кибернетики, нетрудно предсказать создание образцов принципиально нового типа АС муниципального управления, аналогов которых в мире нет.
Перечисленные факторы характеризуют потребность и необходимость в создании и внедрении математического, моделирующего и оптимизирующего наполнения муниципальной интегрированной информационной системы (МИИС), которая бы обеспечивала комплексную информационно-аналитическую поддержку процессов принятия решений в муниципальном управлении. Поэтому разработка такой темы как "Разработка моделей принятия решений в системах управления городом" является весьма актуальной и перспективной темой для научного исследования.
Цель и задачи исследования. Целью диссертационной работы является разработка моделей различных подсистем МИИС.
Для достижения поставленной цели в диссертационной работе осуществляется решение следующих основных задач: всесторонний анализ предметной области (ПрО) посредством классификации, статистики, анализа структур и моделей; отбор наиболее удачных из созданных моделей для интеграции их с разработанными в ходе диссертационного исследования; разработка эконометрической модели города; разработка модели финансовой деятельности инновационного банка. В рамках задачи оперативного планирования и оперативного управления городом: разработка математической модели в задаче составления расписания; описание функциональной структуры комплекса оперативного управления городом.
Объект исследования. Объектом исследования является крупный город и город-гигант России, включая его структуру и процесс управления городом.
Предмет исследования. Предметом исследования в данной работе являются модели принятия решений в системах управления городом.
Методы исследования. Методологической и теоретической основой исследования явились труды российских и зарубежных ученых в области проектирования систем управления городом, построения моделей сложных систем проектирования интегрированных автоматизированных систем. В работе используется комплексный системный подход, теория графов, математическая статистика, нисходящий подход, математические методы теории множеств, классификационный анализ, теория динамических систем, теория дискретных технологических систем.
Научная новизна. Научная новизна работы состоит в разработке и внедрении автором математических и имитационных моделей. создана эконометрическая модель города, на основе которой возможно проведение всестороннего анализа процессов жизнедеятельности города и прогнозирование его социально-экономического развития. разработана функциональная структура комплекса оперативного управления городом. разработана модель финансовой деятельности инновационного коммерческого банка, применимая при финансировании городских программ. разработаны и внедрены модель управления трудовыми ресурсами и модель медико-демографических процессов в городе.
Практическая значимость. Практическая значимость исследования заключается в использовании разработанных моделей при проектировании муниципальных информационных интегрированных систем.
Апробация работы. Основные результаты исследования, изложенные в диссертации прошли апробацию на научно-практических конференциях и в печати: опубликовано 4 работы.
Достигнутые результаты в диссертационном исследовании были применены при создании типового проекта МИИС.
Анализ методов и средств проектирования интегрированных информационных систем города
Как уже было сказано в п. 1.2, в области создания ПАСУ города проведено много работ и накоплен серьезный опыт в реализации интеграции в АС. При этом были созданы и применены различные методы интеграции.
Наиболее широко применяются методы межмодульной интеграции и интеграции неоднородных баз данных.
Метод межмодульной интеграции эффективен лишь при позадачном подходе к проектированию АС, что характерно для АСУ. При комплексном подходе к проектированию АС, который является базовым для МИИС, когда вся система в целом и отдельные модули ее подвергаются системному анализу, в применении этого метода либо совсем отпадает необходимость, либо использование его становиться частным случаем при разработке реализации каких-либо задач.
Метод межмодульной интеграции базируется на представлении АС и их составляющих частей в виде информационных модулей «вход - выход» и интеграции этих модулей по входам, выходам, информационным переходам на этапах анализа и синтеза ИАС. Благодаря этому производится исключение некоторых модулей обра ботки данных (МОД), объединение их пар или комплексов в один модуль или же упрощение МОД, посредством устранения повторяющихся в других МОД вычислительных процедур. Этот метод реализует функциональную интеграцию, обеспечивая сопряженность и согласованность функциональных задач и подсистем взаимодействующих АС по составу и содержанию в рамках И АС.
Использование метода интеграции неоднородных баз данных характерно лишь при позадачном походе, когда для конкретных задач, решаемых АС, создавалась своя база данных (БД) средствами выбранной СУБД. Метод интеграции неоднородных баз данных основан на формальном определении семантики моделей данных с использованием метамодели данных. Этот метод реализует информационную интеграцию. Зачастую вся АС включала целый набор таких БД, реализованных разными СУБД с различными типами моделей данных. Для исключения огромного количества дублирования данных с помощью этого метода разрабатывались средства преобразования данных из одних моделей в другие, из одних форматов в другие и т.п.. Иногда множественность БД была связана с ограниченными возможностями СУБД или их специфичностью, или с ограниченными возможностями техники. Но в современных условиях, когда а) развита концепция банка данных (БнД); б) когда имеются новые мощные СУБД, рассчитанные на большие данных, имеющие стандартные интерфейсы с другими СУБД; в) когда создана мощная техника, на которой могут создаваться и эксплуатироваться такие БнД; г) когда созданы мощные сетевые технологии, позволяющие создавать распределенные БнД, этот метод перестал быть актуальным, особенно при комплексном системном подходе, используемом при создании БнД для таких систем как МИИС.
Методы комплексного системного подхода к проектированию сложных систем, декомпозиции, агрегации, координации, анализа и синтеза сложных систем, теории графов и сетей не являются специфическими, а используются повсеместно при анализе сложных систем, связанных не только с информационными процессами. Они используются при анализе ПрО и построении ее модели, а также при дальнейшем проектировании этой системы.
В процессе интеграции функциональных элементов АС и выбора структур ИАС нередко применяются методы имитационного моделирования, подробно рассмотренные в п. 1.4. Методы имитационного моделирования весьма наукоемкие и требуют высокой квалификации от проектировщиков, которые будут их использовать [57].
Все средства интеграции, реализующие описанные в работе и другие методы интеграции, делятся на три группы: программно - алгоритмические, информационно -лингвистические, технические.
Первую группу составляют пакеты прикладных программ (ППП) и системы управления базами данных (СУБД).
ППП - это совокупность совместимых программ, ориентированных на пользователей определенной квалификации, для решения определенного класса задач [39]. В настоящее время эти средства интеграции получили широкое развитие. Современные ППП с удобным интерфейсом, системой настройки на конкретные условия применения, с широким перечнем функциональных возможностей, как обрабатывающего, так и обслуживающего характера, предоставляют пользователям любой квалификации средства интеграции в любой интересующей их области. ППП способен весьма эффективно поддерживать функциональную интеграцию в АС.
Математические модели, используемые при строительстве новых городов
В нашей стране и за рубежом разработано множество математических моделей, позволяющих моделировать отдельные аспекты при проектировании новых городов. Наиболее развитой является модель функционального зонирования территории города [116], которая связана с укрупненной разработкой будущего плана размещения функциональных зон города. В понятие функция здесь вкладывается широкий смысл, это может быть «жилая зона», «зона отдыха» и т.д. В результате решения этой задачи получаем проектируемые затраты на освоение территории при условии ее закрепления за некоторой, условной функциональной зоной.
Однако взаимосвязи между отдельными функциями носят сложный характер и фактически невозможно их адекватное отражение в модели с учетом вычислительной и интеллектуальной сложности.
Упрощение взаимосвязей при функциональном зонировании приводит к оптимизации по линейному критерию разряда территории. В свою очередь, это приведет к тому, что городские функции неизбежно будут планироваться к размещению на более дешевых в освоении участках под застройку и город окажется разорванным, разбросанным по отдельным площадкам. Отдельные его части будут находиться в случайных пространственных взаимоотношениях и в дальнейшем никакими средствами невозможно будет обеспечить его целостность и разумную пространственную организацию [119]. Может быть, именно такая точка зрения и породила множество "спальных" районов в Ленинграде и Москве. Пакет прикладных программ, соответствующий модели функционального зонирования позволяет, как утверждается в [116], моделировать не только новые, но и реконструируемые города, однако в рамках новой экономической системы, приватизации жилья и производства, сферы обслуживания, принципы, заложенные в модель являются не соответствующими реальным экономическим отношениям.
Разработан ряд математических моделей для оптимального размещения предприятий. В большинстве из них основной является схема открытой транспортной задачи линейного программирования: т.е. для каждого пункта задан набор мощностей, определены потребности предприятий в сырье, удельные приведенные затраты. Известны пункты потребления продукта и объемы их потребностей, а также транспортные расходы. В результате решения задачи определяются рекомендуемые объемы производства для любого пункта, минимизирующие суммарные производственно транспортные затраты. В [7] приводится модель размещения многоотраслевых производств. Она сводится к задаче дискретного программирования и приводит к созданию последовательности планов. Все представления модели являются статическими и не позволяют учесть существующие ограничения и реальные условия в рамках живого города.
Наибольшее число моделей посвящено моделированию внутригородских корреспонденции населения и моделированию проектирования систем городских путей сообщения. Большинство моделей основано на простой гравитационной модели Уил-сона (Wilson, 1967). Эта модель связана с распределением корреспонденции из каждого пункта отправления между всеми пунктами прибытия, поэтому ее применимость ограничивается случаем трудовых корреспонденции [48]. Расчет модели может позволить дать полную картину посещения учреждений при передвижениях населения из жилых районов и по дороге с работы домой, а также оценку планировочной ситуации. Это открывает возможность постановки задачи размещения учреждений бытового обслуживания. Однако, недостаток этой модели также связан с уменьшением доли планирования государственных предприятий обслуживания в связи с приватизацией этой отрасли городского хозяйства.
Одним из недостатков приведенных транспортных моделей является отсутствие развития инструментария, позволяющего оперативно получать рекомендации по изменению маршрутов городского транспорта при аварийном (ремонтном) закрытии отдельных транспортных магистралей, при изменении размещения жилых районов и промышленных предприятий в городе.
При оперативном принятии решений такое моделирование и соответственно подобный инструментарий является обязательным.
Региональные экономические системы отличаются сильной разнородностью переменных, отражающих различные экономические, демографические, экологические, энергетические и др. показатели. К тому же осложняет моделирование подобных систем их большая размерность, наличие инерционных звеньев, большое число внешних и внутренних контуров управления и т.д. Общий подход к построению математических моделей подобных систем разработан и опробован в США [117,118,127,128,131]. Он сводится к представлению модели в виде системы дифференциальных и разностных уравнений. При этом коэффициенты указанных уравнений получают статистическими методами. Успешное применение этой методики отражено в п.2.3.
Однако, в вышеуказанной методике не используются балансовые соотношения между различными переменными модели, вытекающие из естественных законов сохранения в любой системе. Такие соотношения в системе рассматриваются в рамках теории балансных динамических систем [30,46,51,55,88,113,120,121]. Балансными называют такие многомерные динамические системы, у которых некоторая сумма переменных остается в течении переходного процесса постоянной.
Применение теории балансных динамических систем на практике дает не только возможность достижения адекватности модели реальной системе путем учета такого важного аспекта, как соблюдение балансных зависимостей, но и придание модели свойств саморегулирования (гомеостатичноети), которыми должны обладать моделируемые экономические системы.
Рассмотрим на некоторых примерах «плохое» поведение динамических систем. Под термином «плохое» поведение будем здесь понимать нестабильные колебания, появляющиеся в стабильном процессе вследствие изменения параметров системы и/или существующей окружающей среды.
Приведенные ниже примеры из области экономики и роста городов представляют собой яркое подтверждение полезности применения теории динамических систем для анализа моделей.
Математическая модель системы в задаче планирования
Задача составления расписания в общей постановке сводится к разработке такого порядка взаимодействия элементов рассматриваемой системы во времени и пространстве, который наиболее оптимальным образом достигает поставленную цель. Поэтому естественно потребовать для определения постановки задачи составления расписания наличие описания взаимодействующих элементов среды функционирования, цели функционирования и критерия оценки способов ее достижения.
Математическая модель разрабатываемая для решения задачи составления расписания, с одной стороны должна иметь довольно общий характер, обеспечивающий возможное применения ее для описания систем широкого класса, с другой стороны, учитывая требования адекватности, в рамках данной модели должны быть предусмотрены возможности отражения всевозможных конкретных особенностей реальных систем. Данные требования приобретают особую актуальность при рассмотрении ГДТС. Действительно, требование гибкости делает практически непригодными большинство из разработанных в литературе моделей конкретных систем. Дело в том, что при классификации реальных систем и разработке математических моделей, большинство работ проводилось на основе учета отраслевых особенностей функционирования систем, в то время, как класс ГДТС выходит за рамки отраслевой принадлежности. Подход же основанный только на математической теории систем, взятой изолированно от прикладных аспектов, тоже не приводит к успеху из-за отсутствия возможностей учета особенностей реальных систем в их конкретном проявлении. По этому в рамках класса ГДТС представляет интерес рассмотрение некоторой, унифицированной модели гибкой системы на единой понятийной основе учитывающей опыт предшествующих разработок. Кроме того, данная модель должна учитывать свое функциональное назначение и применение в задаче составления расписания для ГДТС. Поэтому все требования к модели ГДТС, сформулированные в первом разделе настоящей работы, должны быть соблюдены на этапе разработки математической модели. Таким образом, учитывая гибкость рассматриваемой системы, требуется рассмотреть такую модель системы, которая бы позволила оперировать не только количественными и качественными характеристиками заданных объектов, но и самими объектами и связями между ними.
Данным требованиям, в наибольшей степени, удовлетворяет модель, предлагаемая в рамках задачи составления расписания в работах [81,82,86,87]. Рассмотрим данный подтип. Для постановки задачи составления расписания для ГДТС требуется определение характеристик отражающих состав и внутреннюю организацию рассматриваемого класса систем, возможность набора целей функционирования и способа оценки вариантов достижения целей в условиях рассматриваемых систем. Как известно, ДТС может быть описана следующими параметрами: С - множество целевых заданий допустимых для ДТС; О - множество технологических операций реализуемых в ДТС; G - множество ресурсов ДТС; Ф - множество ограничений наложенных на среду функционирования ДТС; F - множество критериев для оценки качества работы ДТС, рассматриваемых в зависимости от производственной ситуации; Т - период функционирования. Понятие целевого задания в рамках общего описания ДТС вводится путем определения множества плановых заданий % , ограничений наложенных на процесс выполнения плановых заданий фс , критериев определяющих способ оценки указанного процесса J7 , соотнесенных с конкретным временным периодом J1 в течение которого необходимо выполнить рассматриваемое целевое задание: Плановое задание представляет собой совокупность некоторого множества объектов обработки pt, определенного для них технологического процесса 777 и времен запуска и выпуска (f_( и f{ соответственно): Технологические процессы представляют собой частично упорядоченное множество операций, которые необходимо выполнить над множеством объектов в период времени, ограниченный временами запуска выпуска. Под операцией понимаем некоторую последовательность действий, для выполнения которой должно быть задействовано некоторое множество ресурсов. Данное множество ресурсов должно быть определено в описании операции наряду с трудоемкостью ее выполнения. Если трудоемкость заранее не известна, например, для транспортной операции, то необходимо вместо трудоемкости указать ссылку на процедуру вычисления данного параметра, использующую характеристики конкретных, выбранных для выполнения рассматриваемой операции ресурсов. При рассмотрении множества ограничений необходимо отметить, что система ограничений складывается как из непосредственных ограничений системы, отражающих функциональные возможности ресурсов по выполнению всего допустимого множества операций, так и из группы ограничений налагаемых в рамках целевого за дания, на процесс выполнения заданных для каждого множества объектов обработки технологических операций. Таким образом, рассматривая данные параметры описания ГДТС, для поста новки задачи составления расписания необходимо задать следующие параметры: Множество технологических операций, реализуемых в ГДТС не входит в постановку задачи, т.к. с одной стороны не все возможные операции могут потребоваться для выполнения указанного множества целевых заданий, с другой - необходимые операции указываются опосредованно, через имена технологических процессов (сопоставляемых объектам обработки). Множество ресурсов представлено J типами, каждый из вторых разбит на Mj групп: однородных ресурсов, где каждая группа однородного ресурса состоит из отдельных единиц: Под однородностью ресурсов подразумеваем взаимозаменяемость единиц ресурсов из однородной группы по отношению к выполнению технологических операций из некоторого класса. Основным требованием накладываемым на информационное описание групп и единиц ресурсов, является наличие возможности учета характеристик указанных -объектов по которым может быть проведен сравнительный анализ объектов одного типа. На производстве, например, по отношению к оборудованию в качестве таких характеристик могут выступать надежность, точность, производительность; в учебном расписании, можно ввести подразделение аудиторий по степени удобства использования для преподавания различных предметов и т.п.
Поиск решения задачи составления расписания для ГДТС на базе метода двойного ранжирования
На основе анализа существующих методов решения задач составления расписания, для данной постановки задачи наиболее подходящим является концепция Метода двойного ранжирования (МДР) [87]. Рассмотрим данную концепцию с позиций решения задачи составления расписания.
МДР является довольно гибким инструментом для решения ЗСР. С одной стороны, его можно использовать, как обобщенную эвристическую схему, накрывающую обширный класс эвристических методов решения таких задач, с другой - как точный оптимизационный метод решения ЗСР с оптимизационным функционалом представляющим собой суммарный штраф за отступление от требований пользователя. Данные два аспекта и будут рассмотрены ниже.
Задача составления расписания, в общем виде, представляет собой оптимизационную задачу перечисления, формулируемую в следующем виде. Имеется множество объектов Е, разбитое на J типов Е - \Е, ii = 1, j\ и некоторый набор ограничений.
Требуется набрать множество & = \ТгТг "" Т/\ где ТІ выборки из теоретико-множественного произведения Т = \]? у.J2x....-x JTj] , так чтобы каждый элемент J7. из R удовлетворял предложенным ограничениям и само множество R максимизировало некоторый предварительно заданный критерий. Точное решение данной задачи может быть найдено только путем полного перебора вершин графа изображенного на рис. 3.1, где E, = \eJk = i,K} решена точными методами за какое-либо разумное время из-за своей размерности. В этих условиях внимание разработчиков привлекает область искусственного интеллекта, занимающаяся поиском приближенных решений для задач подобного рода. Основным моментом данных исследований, является искусственное доопределение исходной постановки, путем учета имеющейся априорной информации о задаче. Обычно такую информацию пытаются интерпретировать в виде ограничений непосредственно усекающих пространство поиска решения либо, в виде так называемых функций предпочтения, придающих поиску направленный характер. Данная схема поиска решения получила название эвристическая. Эвристический подход широко используется при решении задач составления расписания. Известно множество примеров, когда успешная попытка выбора и формализации некоторой априорной информации дает существенный выигрыш в ресурсах требуемых для решения задачи. Таким образом, перед разработчиком стоят задачи выделения априорных знаний об исследуемом процессе, их формализации и создания такого метода, структура которого в той или иной мере подразумевала бы данный набор формализованных знаний. Но фиксированный выбор и жесткая формализация значительно снижают адаптационные свойства получаемых программных решений по отношению к изменению среды функционирования. Данное обстоятельство делает практически непригодными существующие реализации для работы в условиях ГДТС. Поэтому для ГДТС требуются разработка метода, имеющего хорошие адаптационные характеристики к гибкому характеру рассматриваемых систем.
На путях реализации данных требований был создан метод, двойного ранжирования (МДР) [87]. При разработке МДР, был проведен анализ РСН в наиболее общей постановке, фактически представляющий собой оптимизационную задачу пере числения, на основе которого были выделены две составляющие, оказывающие влияние на ход поиска решения: 1) порядок обработки типов элементов входящих в комбинацию; 2) порядок выбора элементов одного типа.
Первая составляющая, с одной стороны, опирается на аппарат приоритетно -порождающих функций упорядочивающих выбор функций предпочтения (ФП), придающих процессу поиска решения оптимизационный характер, с другой стороны -реализует отсечение областей просмотра на основе учета ограничений, отражающих изменение среды функционирования.
Второй же аспект, путем определения порядка обработки типов объектов в процессе решения задачи, фактически поддерживает перестраиваемость структуры алгоритма поиска решения (отслеживающую изменение целей функционирования объекта управления).
Итак, применение метода двойного ранжирования, предполагает представление процесса решения ЗСР в виде последовательного выбора комбинаций. Выбор комбинации производится путем определения допустимого пути на графе поиска решения (задаваемого неявным способом). Неявный способ задания графа поиска решения, заключается в построении только тех путей, которые удовлетворяют заданным ограничениям и необходимы на рассматриваемых шагах просмотра.
Первое учитываемое ограничение представляет собой фиксацию порядка просмотра типов выбираемых объектов и само по себе отсекает значительную часть исходного графа, в которой учитываются различные способы набора одних и тех же комбинаций. В результате получаем множества типов элементов, из которых необходимо взять по единственному элементу при наборе комбинации. Учет системы огра ничений, при определенном порядке просмотра множеств типов элементов, приводит к последовательному набору для каждого из элементов первого уровня, множества претендентов на вхождение в комбинацию удовлетворяющих ограничениям. Далее, определив для каждого элемента первого уровня претендентов на вхождение вместе с ним в комбинацию, можно для каждого из претендентов опять набрать множество допустимых по ограничениям элементов. Последовательно применяя данную процедуру к каждому из выбранных претендентных элементов, можем полностью построить граф поиска решения. Поиск на графе указанного вида происходит в соответствии с вычисленными значениями наборов функций предпочтений, определенных для каждого типа элементов. Таким образом, в рамках неявного задания графа поиска решения, при рассмотрении каждого типа элементов, построение возможных путей проводится лишь для самого предпочтительного элемента, который определяется с помощью заданных функций предпочтения. Если на каком либо из этапов выбора претендентов, не удается получить непустое множество, то происходит возвращение на предыдущий этап, где происходит замена рассматриваемого наиболее предпочтительного элемента, на элемент, являющегося наиболее предпочтительным среди оставшихся элементов, после исключения уже рассмотренного. Так происходит выбор наиболее предпочтительных элементов в набираемую комбинацию из группы подходящих по ограничениям.
