Построение и анализ сложности механизмов выбора логическими методами тема автореферата и диссертации по математике, 01.01.11 ВАК РФ

' АКАДЕМИЯ НАУК СССР

\А ВСЕСОЮЗНЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИМ ИНСТИТУТ '} СИСТЕМНЫХ ИССЛЕДОВАНИЙ

Специализированный Совет Д 003.03.02

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

ШОЛОМОВ Лев Абрамович

УДК 519.816:519.95

ПОСТРОЕНИЕ И АНАЛИЗ СЛОЖНОСТИ МЕХАНИЗМОВ ВЫБОРА ЛОГИЧЕСКИМИ МЕТОДАМИ

Специальность 01.01.11 — системный анализ и автоматическое управление

АВТОРЕФЕРАТ

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

Москва 1988

Работа выполнена во Всесоюзном научно-исследовательском институте системных исследований АН СССР (ВНИИСИ).

Официальные оппоненты:

член-корреспондент АН СССР, профессор Ю. И. Журавлев,

доктор физико-математических наук, доцент Ю. Н. Тюрин,

доктор физико-математических наук, ст. научи, сотр. В. И. Опойцев.

Ведущая организация — Кафедра теории и организации больших систем Московского физико-технического института.

Защита состоится «_»_ 1988 г. в _час.

на заседании специализированного совета Д 003.63.02 Всесоюзного научно-исследовательского института системных исследований по адресу: 117312, г. Москва, проспект 60-летия Октября, д. 9.

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

Автореферат разослан «_»._ 1988 г.

Ученый секретарь специализированного совета к. ф.-м. н., с. н. с.

В. С. ЛЕВЧЕНКОВ

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

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

Информация о выборе решений специалистом, используемая для построения модели, может быть условно разделена на два вада:

а) информация о результатах выбора,

б) информация о процедуре выбора.

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

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

1-1

значительно отличаться от фактического процесса принятия решений.

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

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

В последнее время проявляется тенденция к рассмотрению более сложных,"неклассических" моделей выбора (М.А.Айзерман, A.B. Малшевский, Б.М.Литвахов), но основное внимание уделяется описанию и свойствам классов реализуемых функций. Для прикладных целей недостаточно принципиального ответа на вопрос, может ли. выбор, обладающий определенными свойствами, быть реализован моделью из некоторого класса. Важно найти более простую реализацию в этом классе, уметь ориентировочно предсказать ее сложность. Желательно иметь методы упрощения (оптимизации) моделей без нарушения выполняемых ими функций.

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

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

Цель работы состоит в

- исследовании фунуоиональных возможностей классов механизмов выбора достаточно общего вида,

- разработке для них теоретически эффективных методов решения задач анализа, синтеза и оптимизации,

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

Теоретической и методологической основой работы слугат:

- теория выбора,

- метода дискретной математики - алгебра логики,.теория графов, комбинаторный анализ,

- Методы исследования управляющих систем, развитые К.Э.Шенноном, С.В.Яблонским, О.Б.Лупановым, З.И.Нечипоруком.

Кроме этого использованы некоторые идеи теории распознавания образов, относящиеся к алгебраическому подходу Ю.И.Журавлева и статистическому подходу В.Н.Вапника л Л.Я.Червоненкиса.

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

На базе логического метода проведено исследование этих за-

1-2

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

Основные результаты работы получены в следующих направлениях:

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

- Для большинства задач, связанных с анализом, синтезом и оптимизацией рассматриваемых моделей указаны теоретически эффективные методы решения, для других доказана ^/Р-трудность и некоторые из /V?-трудных задач решены в ослабленных постановках.

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

Эти или аналогичные им результаты прежде в исследованиях других авторов не встречались.

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

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

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

Предложенный в работе логический метод является удобным инструментом для представления и исследования задач выбора. Он нашел применение в системе подготовки студентов - излагается и существенно используется в учебном пособии "Теория выбора и принятия решений", М.: Наука, 1982, написанном коллективом авторов под руководством И.М.Макарова.

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

Результаты работы докладывались и обсуждались на Ш Всесоюзной научной школе "Прогнозирование научно-технического прогресса" (Минск, 1979), на Юбилейной конференции научных работ ВНИИСИ (1981), на I Всесоюзном совещании по статистическому и дискретному анализу нечисловой информации и экспертным оценкам (Алма-Ата, 1981), на Всесоюзном семинаре по дискретной математике и ее приложениям (Москва, 1984), на П Всесоюзной конференции "Математические методы распознавания образов" (Дилнжан, 1985), на

1-3

У1 Международной конференции "Основы теории вычислений" (Казань, 198?). Они неоднократно докладывались на семинарах по синтезу управляющих систем в МХУ, по теории графов в ИЛУ Минприбора и АН СССР, семинарах математического отдела ДЭМИ АН СССР, семинарах "Математические методы в экспертных оценках и анализ нечи-- еловой информации", проводимых совместно МГУ, Научным советом по проблеме "Кибернетика" АН СССР и ВСНТО.

Апробация диссертации в целом была проведена во ВНШСИ АН СССР в мае 1987 г. на объединенном семинаре отделов "Математические методы информатики и управления", "Теория и методы принятия решений", "Человеко-машинные методы анализа и синтеза систем".

По теме диссертации автором опубликовано 26 научных работ, из которых 4 в соавторстве (с Д.Б.Юдиным). По материалам исследований также написана монография "Логические методы исследования дискретных моделей выбора" (20 п.л.), включенная в план издательства "Наука" на 1989 г.

Структура и объем работы. Диссертация состоит из.5 глав, заключительной части, содержащей основные результаты и выводы, списка литератург, включающего 127 наименований, содержит 6 рисунков. Полный объем - 311 страниц машинописного текста.

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

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

Введем необходимые понятия. Задано конечное множество И. элементы которого называются вариантами. Функция выбора (на-0- ) с областью определения В & - это отображение, сопостав-

ляющее каждому (предъявлению) множество С(К) с х

вариантов, выбранных в предъявлении X . При ^Функция С называется всюду определенной, а в противном случае -частичной. Обобщением этого понятия является функция неполного выбора, сопоставляющая каждому

Хер множества С XX) выбранных и СП) отвергнутых вариантов

СГХ)иСГХ)^Х.

Функции выбора порождаются некоторыми процедурами (механизмами). Под механизмом выбора понимается пара М = Я-У , где б - некоторая структура на -О- , а 7С _ правило выделения из X на основе б подмножества 7С>(Х). Функ-

ция предполагается всюду определенной. Механизм реа-

лизует функцию (неполного выбора) С , если функция С^ доопределяет С (обозначение С^ ^С ). Для класса меха-

гся множес

'сМ

тех из них, которые заданы на множестве =_0. мощности П Механизмы выбора являются управляющими системами в смысле С.В.Яблонского. Поэтому для них возникают те не типы задач, какие рассматриваются в теории управляющих систем.

Задача анализа состоит в том, чтобы по механизму

МвсЛС

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

Задача синтеза заключается в том, чтобы по функции (непол- . кого выбора) С построить реализующий ее механизм М £гсА[ , либо установить, что это невозможно. Обычно с механизмом М связывается характеристика сложности и ставится задача оптимального синтеза, состоящая в нахождении реализации имеющей

низмов сМ через -С п, обозначается множество всех функций,

М Гсп)

реализуемых механизмами из С/СС , а через -^¿ц - множество

наименьшую сложность Км).

Функция С , используемая для построения механизма НеЖ определена на множестве |3 реально наблюдавшихся предъявлений, в то врег~ как Л1 предполагается применять для выбора в произвольных предъявлениях. Таким образом, требуется, чтобы механизм /Ч удовлетворительно прогнозировал выбор и там, где он реально не производился. В диссертации на основе подхода В.Н. Ва-пника и А.ЯЛервоненккса показано (при определенных статистических допуиениях), что более хорошей способностью прогнозировать выбор обладают механизмы из классов сМ с малой энтропией (под

энтропией НЛсМ) класса сМ понимается логарифм числа вск>-

г<п>

ду определенных функций из ). Поскольку энтропия класса

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

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

же функцию) механизм с наименьшим значением сложно-

сти Км*).

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

Ж

) называется величина Сложность класса механизмов сЯ характеризуется функцией

Возникает задача исследования: поведения функции ^¿^J и раз- , работки методов синтеза, гарантирующих оценки, "близкие" к tj^fî) В работе ставятся и другие задачи оценочного характера. Одна из них связана с исследованием взаимного влияния различных характеристик сложности ¿(14) ж к (И) . Вводится величина

сл (С)' тш{Ш)1ме<А.,См *С, k(M)-kJCl).

Ее сравнение с tj^ (С). показызает к какому увеличению сложности fj приводит минимизация к • Аналогично может быть введена величина (С) и на ее основе изучено влияние t на к,

Модели выбора существенно отличаются от моделей, традиционно рассматриваемых в теории управляющих систем. Хотя ее результаты и конкретные метода на задачи выбора не переносятся, общая методология исследования управляющих систем, связываемая с женами К.Э.Шеннона, С.В.Яблонского, О.Б.Лупанова, Ю.И.Куравлева, Э.И.Нечипорука, оказала заметное влияние на данную работу.

В диссертации изучаются модели выбора на базе нескольких бинарных отношений К , заданных на (н отражающих "пред-

почтительность" одних вариантов другим). Содержательные соображения накладывают ограничения на вид используемых отношений. Будем рассматривать цепочку вложенных классов отношений

образованных

'соответственно отношениями линейного порядка L , слабого порядка W , полупорядка , интервального порядка X , частичного порядка Р и произвольными отношениями R, (определения см. в Фишберн П. Теория полезности для принятия решений,- М.: Наука, 1978). Все отношения предполагаются антирефлексивными, а порядки строгими. Отношению

соответствует функция выбора

гч •

Функциц, реализуемые моделями выбора на базе нескольких отношений, строятся из функций выбора по отдельным отношениям применением операций суперпозиции (К)) и композиции

, где т - нетривиальная монотонная теоретико-множественная (т.-м.) операция. Конкретные модели выбора будут описаны при изложении результатов соответствующих глав.

Дальше будем считать, чво вариантом I свяжем булеву переменную ¿С- и предъявлению X — — Ц сопоставим булев набор X = >• ■> ^п ) , где <Х- = ( €: X . Тогда функцию неполного выбора С ~(С\С°, Р) можно описать набором частичных булевых функций С кЛ )} с - 1>П^

I не определено в остальных случаях.

Функция СМ) выбора по отношению Я имеет булево опиЛ

сание ** л

л л., ¿^

где £ *('(■) я { ] I ] Я I } . Если функция

с а)

образована

суперпозицией С2 (К)) , то

с«т = с;<}(с;П)г.-лГ(х)), с-йп,

а если - композицией

, то

где - булева функция, соответствующая т.-м. операции ^Р .

Этих средств в основном достаточно для нахождения булевых описаний рассматриваемых в работе механизмов выбора. Они позво-

ляют решить задачу анализа механизмов с полиномиальной сложностью.

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

Вторая глава посвящена агрегированию отношений и вложению отношений в критериальные пространства.

Один из наиболее распространенных способов выбора по набору бинарных отношений состоит в том, что задается операция -г •• г—я , находится отношение =

> называемое агрегированным, и производится выбор С!ГгМ<0а Исходные отношения обычно

О, Г

представкш скалярным критерием, т.е. принадлежат классу (/Я (либо ¿[у ), результирующее отношение Я этим свойством может не обладать.

В работе рассматривается круг задач, обратных задачам агрегирования. Они относятся к различным видам декомпозицга отношений на более простые отношения (из класса

либо оО ) . Построение декомпозиций оказывается тесно связанным с вложением отношений в соответствующие типы критериальных прострвнств.

Г** пя

Дадим ряд определений. Для X ^ 6 !\ положим Д(.Х}У) = = (Ыгде Л и у являются $ -

^ г**

ми^сомпонентами наборов X и у . Бинарное отношение ^ на Я называется порядковым, если

(А(^)-А(Яз'))

и правильным, если выполнено свойство монотонности 1-6

л А'^ЗсУ^ЗуЦ.

Отношение Я £ вложи?,ю в критериальное пространство ^аз-мернорти «Я , если существуют ^>тображение о(. '• А порядковое отношение Р на К , такие что где =

жение называется правильным, если отношение р правильное. В случае, когда Л Ф^ -Х^£^ ) , будем говорир о вло-

жении в пространство строгих критериев, а если роль & играет С., , где

- о вложении в пространство

к -значных критериев.

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

Теорема 2.5. I. Непустое отношение & вложимо в пространство строгих критериев размерности тогда и только тогда, когда оно допускает представление

___ (2)

где Р - т.-м. операция} ЦбХ }

2. То же справедливо для правильных вложений при дополнительном условии

, где ^ - класс нетривиальных монотонных т.-м. операций.

При отсутствии требования строгости представления из теоремы 2.5 заменяются соответственно на ,

VI^ %Гу W В случае к -значных кри-

териев роль играет класс слабых порядков с не бо-

лее к уровнями аквивалентности. Цусть

Г

- некоторый класс т.-м. операций, замкнутый относительно суперпозиции. Класс назовем аС-полным, ее-

ли любое отношение (антирефлексивное) представимо в виде

(2), где тР .На основе диаграммы Поста, описывающей стру-

ктуру всех замкнутых классов булевых функций, доказана

Теорема 2.6. Класс является -полным тогда и только тогда, когда

Для X-полного класса с/" обозначим через ми-

нимально е число и такое, что всякое отношение представимо в виде (2), где £ . в работе предложен ме-

тод декомпозиции отношений, обеспечивающий асимптотически наилучшую оценку функции

Теорема 2.7. Для любого «¿-полного класса с/"

Из теорем 2.5 и 2.6 следует, что всякое отношение правильно вложимо в пространство строгих критериев. Поэтому могут быть введены функции 1)(г1) н

Ып)

, первая из которых указывает минимальную размерность пространств строгих критериев, в которые вкладываются произвольные отношения . Я ~ , а вторая - то же самое при условии правильности. Следствием теорем 2.5 и 2.7 являются оценки

Т.М.Виноградская и А.М.Рубчинский (ДАН СССР, т. 251, й 2, 1980) и независимо Б.А.Березовский и Л.М.Кемпнер (Автоматика и телемеханика, 1981, й I) доказали, что при любом (< 2 всякое отношение вложимо в пространство к -значных критериев. Для характеристики вложений введем функции являющиеся аналогами

. Кроме того, сняв ограничения на вид критериев, определим функции

Жп)

и а (П.) . ранее была известна линь оценка ^ 2П (Березовский, Кеминер), которая, очевидно, распространяется на (Л)} ¿¿^ (П.) Г-7

( к*з), Жп) ж . В диссертации с использованием

разностных множеств Зингера доказана Теорема 2.9. Имеют место оценки

Разрыв между верхней и нижнёй оценками здесь составляет примерно 1,58. В случае /ч = 2 его удается сократить до 1,2 за счет повышения нижней оценки.

Отметим, что имеются исследования, посвященные вложению отношений (уже не произвольных) для специальных видов порядковых отношений ^ . Случай, когда ^ совпадает с отношением >• на множестве наборов, рассматривался в работах Б.Душника - Е.Миллера, Т.Хлрагучи, У.Троггера, К.Богарта, а случай, когда р является мажоритарным отношением, - в работах Д.Мак-Гервея, Р.Сти-рнза, П.Эрдеша - Л.Мозера. Но развитые там методы на отношения общего вида не распространяются, а оценки имеют другой ввд.

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

Он характеризуется сложностью Д (К) = I I • • •({ , где I & 1 означает мощность К (число пар), и глубиной

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

Теорема 3.1. Задача выяснения принадлежности функции классу

J] п и задача синтеза в классе Пс являются /VP-трудными.

В работе предложен метод, названный методом последовательной аппроксимации, который при определенных статистических допущениях эффективно строит реализации для почти всех (но не для всех) функций из -Cf¡c , k=COíli>t, причем наилучшие одновременно по сложности и глубине. v

Всюду определенная функция С называется верхней аппроксимацией функции

■ , если она представима отно-■шением, удовлетворяет условию и для

произвольной функции С , обладающей этими свойствами; выполнено тХСП)^С(К))

. В работе доказано, что всякая функция С'(С.,С обладает верхней аппроксимацией С

и С .где . .

fw-iw U л,

Bvметоде последовательной аппроксимации находится отношение Ri , реализующее верхнюю аппроксимацию исходной функции С а ) . строится новая функция >р1)

^íxjx^au^}, сих,)- U cU), c;oi)=xtn U ¿Vx),

XlCfW-Xi Y Xlty00-Xf

находится отношение fií^ , реализующее ее верхнюю аппроксимацию, tsj. д., пока процесс не стабилизируется. К полученному набору . j ) применяется процедура приведения, заменяющая каддое R (Ь-^к) на R^-R/^ C&UR.'1). Й * 4 4 fiUó-í 1 1

СО

м Легко видеть, что этот метод эффективен.

Формулировку теоремы о методе последовательной аппроксимации в целях простоты приведем применительно к частичным функци-1-8

- IS -

ям (а не к функциям неполного выбора). Пусть С обозначает частичную функцию, являющуюся сужением всюду определенной функции С на множество JS , и пусть '¿¡С^ ¿-{X | ixKs*, /х! - мощность множества .А.

Теорема 3.4. Если ^ ~{Х('\..., Х^} -последовательность независимых случайна предъявлений, равномерно распределенных на5Сп;>) J £ д ~ аСп) , и

N>< -сbiw-nH~n'

то при любом ^ -Con.$t для почти всех функций ^^-Сцс

к

вероятность того, что метод последовательной аппроксимации, примененный к , дает реализацию для С и эта реализация является минимальной одновременно по сложности и глубине, стремится к 1 с ростом R.

Отметим, что если. 6 4 С , оценка величины N по-

линомиальна по А . В содержательных задачах величина 5 бывает небольшой.

Доказательство теоремы 3.4 основано на исследовании свойств почти всех реализаций из Пс^.

Далее в работе изучается асимптотическое поведение характеристик сложности и Сп). глубины и взаимное влияние сложности и глубины. Вводится характеристика сложности при минимальной глубине

¿Пс(С)-тт{ Ш | ¿f ^ С , К(Ю -~КПс (С)}

и на ее основе - величины JtLn (С) (C)/Ln (С) и Л„ №)*=■

r I I _ } ''С- 1'с ' • ic. Пс

~rnaJLyLncCC) \ Cfcу . Аналогично определяется величина

) , характеризующая увеличение глубины при минимизации

сложности.

Получены следующие оценки, составляющие содержание теорем

3.5, 3.6 и 3.7,

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

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

Четвертая глава посвящена параллельному выбору. Механизм параллельного выбора задается набором отношений и К -местной операцией

. Ему соответствует функция

Обозначим через Пр и Пр(С^) соответственно классы всех механизмов параллельного выбора и тех механизмов, которые используют отношения класса" , а через -С ^ и Пр(0>) ~ то~ аества реализуемых в них функций выбора. В работе доказано (теорема 4.1), что при любом

класс -О ^ (0^) образуется всеми функциями С — СС\ С ° р /) , которые обладают свойством наследования выбора

и удовлетворяют условию

- (УхеИ)({х}ер +хфсв(Ш)). (3)

Эти условия|эффективно проверяет.

Сочетание методов теорем 4.1 и 4.2 дает способ построения реализаций из

Прф, ф ,

и тем самым эффективно решает

- 18 -

задачу синтеза для любого цепочки (1).

Механизм ^У € Пр будем характеризовать сложностью

Ш)

и числом отношений К (.Я) (как в в классе Пс). Для каждого из параметров и К возникает своя задача минимизации. В работе найден эффективный метод минимизации [_» . -

Задача минимизации /С допускает сведение к некоторому обобщению теоретико-множественной задачи о минимальном дизъюнктивном базисе. Система множеств называется дизъюнктивным базисом системы множеств

(УсеТ^п) и

Система В называется обобщенным дизъюнктивным

базисом для (А':>А"),/11=М{ )■■.,<<„,,} } А - Ы1

если

(Ус'(г1,гп')(ЗСе1>т") и в,

Ул

1 Пр

Пусть - некоторый механизм класса Пр, С=С/€

- реализуемая ем функция, ее логическое опи-

сание - множество существенных переменных функции

- функция, полученная из ¿"УХ) подстановкой ' . Положиа

Л- V (СП)(Г) Л л- Л

кил *

Функции н ДС обладают единственной минимальной д.н.ф.; пусть А £ ж Дд^ - системы множеств, соответствующих конъюнкциям этих д.н.ф.

Теорема 4.4. Задача минимизации А механизма эквивалентна задаче нахождения минимального (т.е. содержащего наименьшее число множеств) обобщенного дизъюнктивного базиса

для (Ал >¿1*1 •

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

Пусть - характеристики сложности и

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

Теорема 4.5.

Эти оценки сохраняются, если ограничить«! механизмами выбора из класса Пр(^) при любом Ддя единственного не подпа-

дающего под этот случай класса Л/ цепочки (I) обе сценки повышаются асимптотически в П раз^

Как и раньше, введем величины (С) и (С) , характеризующие сложность при минимальном числе отношений число отношений при минимальной сложности. Обозначим через и* / \

/СПр (К ) максимумы этих величин по всем ^ ^ Пр • (Отметим, что в классе Пс функции ¿->г1с ^^ и КПс совпадают с

и » поэтому для изучения взаимного влия-

ния характеристик /_» и /С там использовались функции другого вида.)

Доказаны теоремы 4.7 и 4.8, в которых на основе построения

- 20 - * *

функций выбора с большими значениями ¿-»Пр и ^лр получены оценки

Они показывают, что минимизация числа отношений в реализациях приводит к увеличению максимальной сложности функций асимптотически в П- раз, а минимизация сложности - к увеличению максимального числа отношений по порядку не менее чем в ^[71 раз (легко доказать, что это возрастание не превосходит А2. ).

•Пятая глава посвящена механизмам выбора со свойством полноты. Функции С - С) . реализуемые "естественными" моделями выбора, обладают свойством

(УхеЛЖЛХ)леС1(Юл{ос]

содержательно означающим, что если вариант ОС- „приемлем" и предъявляется только он, то X не отвергается. Класс всех таких функций обозначим через -Со и класс механизмов выбора, в котором реализуемы все функции из ■Сд , будем называть полным. Если реализуемы все функции с несколько более слабым свойством (3), будем говорить о почти полноте.

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

- тройка множеств, образующих разбиение множества Л , в которой И ^0 Н ¥=-0, Каждому С сопоставим булеву функцию

V X V А 3.). Гн ¿еИ"' 1 __

Лека® 5.2.3. Существует система Н~{На } ,

троек На.-(^а. А'^Н™}, такая что дм любой функции каждая жз функций С(°(Ю » входящих в ее логическое описание, представила в виде

С'Щ'ГСу-'"

' Ч „»> т;

где 7 - некоторая монотонная функция } с £ ¡1а у 5- 13Р.

Система Н содержит наименьшее по порядку число множеств и основанные на этом представлении реализации функций из оказываются наилучшими по порядку сложности.

Вначале изучается последовательно-параллельный выбор. Механизм этого класса задается совокупностью ->••■>наборов отношений Я = • ■ ■, ), 6 = и /V -местной операцией -р ¿г . Он реализует функцию

Сложность характеризуется общим числом КСЯ) + от-

ношений системы • /\ и числом ) различных отношений; величина г.. £ называется глубиной. Класс всех механизмов последовательно-параллельного выбора обозначается через ПсПр, а если необходимо указать множество используемых отношений или глубину - через

ПсПр(ф, ПсПр^7 либо ПсПрг^(6^). Вопрос полноты решается следующей теоремой. Теорема 5.Т. Класс механизмов ПсПр^(^) почти полон при любых и О^ 2 с5., где (5 - класс отношений полупорядка.

Этот результат не допускает усиления за счет уменьшения (к либо перехода от S к предыдущему классу цепочки (1).

Предложены методы синтеза, дающие наилучшие по порядку оценки величин К (теорема 5.2) и 2) (теорема 5.3)

где означает равенство по порядку.

Ограничение глубины значением б/? 2 не увеличивает порядка величины Д^^Сп). Для характеристики Х^ это не так: если глубина ограничена константой, оценка из логарифмической превращается в степенную.

Далее исследуются схемы выбора, основанные на концепции обобщенного математического программирования (ОМП), введенной Д.Б.Вди-ным (Экономика и мат. методы, 1984, т. XX, вып. 1). В отличие от традиционного математического программирования в ОМП допустимость и оптимальность трактуются в терминах бинарных отношений.

С предъявлением X — -О. связываются множество вариантов, оптимальных по отношению Я , _

в множество вариантов, допустимых по отношению Я при множестве эталонов

/Мтв„(Х)-{хе%1(Уи€ги) иЯх}.

Схема (Ш записывается в виде

а) I Z

где

■Те Г

. При заданном

требуется найти оптимальные варианты допустимого множества 2. , определенного условием справа от черты.

Многошаговая схема ОШ представляет собой последовательность из схем

*к<*\>икш

относястхся к шагай - Здесь X результат ша-

Хн» V

^ * Л - предъявление.

12в$юрнационно1 структурой схемы называется набор

__- 23 - }

где - множество всех таких ') , что X ^ нс-

* 4- I

пользуется на шаге Ъ . Естественным образом вводится понятие

глубины схемы. Класс многошаговых схем обозначается через МнОМП, а при ограничении на глубину Ж и класс используемых от-

ношений - через МнОМП^Сб^).

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

Теорема 5.6. Класс МнОШ^(^) полон при любых и О^Щ.

Усилить теорему, уменьшив « или заменив

и на предыдущий класс цепочки (Х); нельзя. Сложность

тсб) многошаговой схемы 3 измеряется числомТ ее шагов. Разработан метод построения схем, обеспечивающий наименьшую по порядку оценку Т при ограничениях на ^ и . Теорема 5.7. При любых с/ и Э «^Г

Порядок оценки не меняется, если ограничения на ^ и Ог. сняты. Исследована также сложность многошаговых схем, реализующих частичные функции выбора, заданные на множестве мощности N .

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

Множеством худших по отношению Я вариантов в предъявлении X считается _

В^СХЫлеХ! Г^еХ) л^ л

-24-

Отношению Я сопоставляется функция выбора и рассматривается механизм параллельного выбора, получающийся из механизма главы 4 заменой С^ на С^ . Класс всех таких механизмов обозначается через Пр', а если фиксировано множество допустимых отношений - через Пр'(^).

В работе доказано (теорема 5.9), что модель Пр' обладает существенно большими возможностями, чем Пр: класс Пр'(б^) почти полон при любом

01 З^Г (усилить этот результат, заменив ЪГ на ¿Ь « нельзя). Предложен метод синтеза, гарантирующий наименьшую по порядку оценку числа отношений (теорема 5.10).

Отдельно исследован случай Пр (¿С), когда свойство почти полноты нарушено. Доказано (теорема 5.11), что в этом классе реализуемы те и только те функции выбора, которые доопределимы до функций со свойством монотонности

конструктивно получена оценка ~

Ш. ЗАКЛЮЧЕНИЕ

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

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

2. Изучена задача вложения бинарных отношений в пространст-

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

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

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

- 26 -

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

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

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

делая ее полной.

Основной материал по теме диссертации содержится в следующих публикациях.

1. Шоломов Л.А. Логические методы в задачах согласованного выбора. Препринт. М.: ВНШСИ, 1978 , 76 с.

2. Шоломов Л.А. Применение логических методов в задачах последовательного выбора. Препринт. М.: ВНИИСИ, 1980, 56 с.

3. Шоломов Л.А. Двухэтапный последовательный выбор по системе отношений. I. Полиномиальная полнота задачи. // Изв. АН СССР. Техническая кибернетика, 1981, }в 2, с. 72-79.

4. Шоломов Л.А. Двухэтапный последовательный выбор по системе отношений. П. Реализация в специальном случае. // Изв. АН СССР. Техническая кибернетика, 1981, й 3, с. 41-45.

5. Шоломов Л.А. Асимптотическое поведение некоторых сложно-стных характеристик композиции функций выбора. // I Всесоюзное совещание по статистическому и дискретному анализу нечисловой информации, экспертным оценкам и дискретной оптимизации (тез. докладов). М. - Алма-Ата: ВИНИТИ, 1981, с. 349-350.

6. Шоломов Л.А. Логические методы композиции функций выбора. Препринт. М.: ВНИИСИ, 1981, 56 с.

7. Шоломов Л.А. Энтропийный подход к выработке коллективного решения. // Методы анализа данных, оценивания и выбора. Сборник трудов. М.: ВНИИСИ, 1982, вып. 10, с. 84-93.

8. Шоломов Л.А. Обзор оценочных результатов в задачах выбора. // Изв. АН СССР. Техническая кибернетика, 1983, й I, с. 60-87.

9. Шоломов Л.А. Сложность представления функций выбора в виде композиции. I. Асимптотические оценки характеристик сложности. // Кибернетика, 1984, й 2, с. 5-9,13.

10. Шоломов Л.А. Сложность представления функций выбора в

виде композиции. П. Взаимное влияние параметров реализации. // Кибернетика, 1984, № 4, с. 10-14,22.

11. Шоломов Я.А. О сложности реализации бинарных отношений путем теоретико-множественных операций над отношениями линейного порядка. // Проблемы кибернетики, вып. 41, М.: Наука, 1984, с. 101-109.

12. Шоломов Л.А. О сложности реализации функций выбора системой отношений частичного порядка. // Проблемы кибернетики, вып. 41, М.: Наука, 1984, с. Ш-116.

13. Шоломов Л.А. О представлении бинарного отношения набором критериев. // Изв. АН СССР. Техническая кибернетика, 1984, К I, с. 6-14.

14. Шоломов Л.А. О сложности одного механизма выбора со свойством универсальности. // Методы анализа данных, оценивания и выбора. Сборник трудов. Ц.: ВНИИСИ, 1984, вып. II, с. 63-69.

15. Шоломов Л.А. Об устойчивости одной процедуры коллективного выбора. // Методы анализа данных, оценивания и выбора. Сборник трудов. Ы.: ВНИИСИ,. 1984, вып. II, с. 69-73.

16. Шоломов Л.А. Оценка сложностных характеристик одного механизма выбора с участием нескольких лиц. // Изв. АН СССР. Техническая кибернетика, 1985, Л 2, с. 3-13.

17. Един Д.Б., Шоломов Л.А. Многошаговые схемы обобщенного математического программирования. // Докл. АН СССР, 1985, т. 282, * 5, с. 1065-1069.

18. 1&нн Д.Б., Шоломов Л.А. Обобщенное математическое программирование и функции выбора. // Изв. АН СССР. Техническая кибернетика, 1985, £ 3, с. 3-16.

19. Еоломов 1.А. Задачи моделирования выбора и задачи распознавания. // Математические метода распознавания образов. Все-

союзная научная конференция. Тез. докладов. Ереван: AJI Арм. ССР, 1985, с. 187-189.

20. Шоломов Л.А. О сложности механизма последовательного выбора. // Методы анализа данных, оценивания и выбора в системных исследованиях. Сборник трудов. М.: ВНИКСИ, 1986, вып. 14, с. 6676.

21. Шоломов Л.А. Мажоритарный выбор при отраничении на тип отношений. //-Анализ задач формирования и выбора альтернатив (Задачи выбора на четких и нечетких данных). Сборник трудов. М.: ВНШСИ, 1986, вып. 10, с. 11-17.

22. Шоломов Л.А., Юдин Д.Б. Синтез многошаговых схем выбора, // Автоматика и гелемеханика, 1986, й 10, с. II5-I26.

23. Шоломов Л.А. Функциональные возможности и сложность механизмов выбора, основанных на исключении худших вариантов. // Изв. АН СССР. Техническая кибернетика, 1987, № I, с. 10-17.

24. Шоломов Л.А. Мажоритарная декомпозиция отношений. // Проблемы выбора и нечеткие множества. Сборник трудов. : ВНИИСИ, 1987, вып. 14.

25. Шоломов Л.А., Един Д.Б. Сложность многошаговых схем обобщенного математического программирования. // Изв. АН СССР. Техническая кибернетика, 1988, № I.

26. Sholomov L.A. The complexity of the sequential choice mochnnian. // Fundaméntala of Computation Theory, International Conference PCT'87 / Eds L.Budach, E.G.Bukharajev, O.B.lupanov. - Berlin: Springer-Verlag, 1987 (Lecture Notes in Computer Science,} v. 278, p. 406-403.