Введение к работе
Актуальность проблемы. Многие задачи системного анализа, связанные с принятием повторяющихся решений, требуют построения моделей, описывающих или достаточно хорошо аппроксимирующих экспериментально наблюдаемый выбор. Необходимость в таких моделях возникает при разработке систем поддержки решений и экспертных систем на основе опыта квалифицированных специалистов, при синтезе процедур принятия решений по базовому множеству сценариев, при экстраполяции поведения человеко-машинных систем, прогнозировании выбора, создании обучающих систем и тренажеров.
Информация о выборе решений специалистом, используемая для построения модели, может быть условно разделена на два вида:
а) информация о результатах выбора,
б) информация о процедуре выбора.
Информация типа (а) отражает результаты реального (экспериментально наблюдаемого) выбора, а информация типа (б) в основном базируется на объяснениях (ответах на вопросы) специалиста, производящего выбор.
Абсолютное большинство моделей и методов принятия решений основано на информации типа (б). Однако ее получение часто связано со значительными трудностями. В ряде случаев она в принципе недоступна, поскольку нет лица, производящего выбор (задачи потребительского спроса, естественного отбора в природе). Кроме того, как неоднократно отмечалось в литературе (О.И.Ларичев. Ав-> томатика и телемеханика, 1981, й 8), необходимость анализа своих -і действий обычно искажает стратегии человека, а объяснения могут
1-І
значительно отличаться от фактического процесса принятия решений.
Информацию типа (а), основанную на реальном выборе, следует считать более объективной и надежной. Во многих случаях она является более доступной, а иногда - единственно доступной. Для фор жирования и структуризации экспериментальной информации о выборе могут быть использованы метода ситуационного управления (Д.А.Поспелов. Ситуационно? управление: теория и практика.- М.: Наука, 1986).
Вопросы использования информации типа (а) ранее изучались лишь применительно к простейшим моделям выбора. Так исследования по выявлении предпочтений, ведущие начало от П.Самуэльсона, относятся к модели выбора по одному отношению, а подход на основе функций полезности дает еще более простую модель выбора по скалярному критерию. То же относится к параметрическим моделям, используемым в математической психологии.
3 последнее время проявляется тенденция к рассмотрению более сложных,"неклассических" моделей выбора (М.А.Айзерман, А.В. Малишевский, Б.М.Литвахов), но основное внимание уделяется описанию и свойствам классов реализуемых функций. Для прикладных целей недостаточно принципиального ответа на вопрос, может ли. выбор, обладающий определенными свойствами, быть реализован моделью из некоторого класса. Важно найти более простую реализацию в этом классе, уметь ориентировочно предсказать ее сложность. Желательно иметь методы упрощения (оптимизации) моделей без нарушения выполняемых ими функций.
Тем самым возникает широкий крут задач, ранее не рассматривавшихся и представляющих большой интерес как для собственно теории выбора-, так и для приложений. Исследования в этой области актуальны, поскольку создают теоретическую основу для разработки
конструкгивных методов в важной и перспективной области автоматизации решений.
Цель работы состоит в
исследовании фунуционалышх возможностей классов механизмов выбора достаточно общего вида,
разработке для них теоретически эффективных методов решения задач анализа, синтеза и оптимизации,
анализе характеристик сложности и построении механизмов выбора из рассматриваемых классов, гарантирующих асимптотически наилучшие либо наилучшие по порядку оценки сложности.
Теоретической и методологической основой работы слугат:
теория выбора,
метода дискретной математики - алгебра логики,.теория графов, комбинаторный анализ,
методы исследования управляющих систем, развитые К.Э.Шенноном, С.В.Яблонским, О.Б.Лупановым, Э.И.Нечипоруком.
Кроме этого использованы некоторые идеи теории распознавания образов, относящиеся к алгебраическому подходу Ю.И.Журавлева и статистическому подходу В.Н.Вапника и Л.Я.Червоненкиса.
Научная новизна. В работе предложен и развит новый »;етод описания функций и механизмов выбора, основанный на аппарате алгебры логики (булевой алгебры). Он позволил исследовать и решить целый ряд конструктивных задач, связанных с построением и анализом сложных моделей выбора. Основными из таких задач, выделенных и сформулированных в работе, являются задачи анализа, синтеза, оптимизации и исследования сложностннх характеристик. Эти задачи в теории выбора являются новыми.
На базе логического метода проведено исследование этих за-
-4-.-дач применительно к моделям выбора достаточно общего вида, в числе которых выбор по агрегированному отношению, последовательный, параллельный и последовательно-параллельный выбор, выбор на основе исключения худших вариантов, многошаговая схема обобщенного математического программирования. Из них традиционной является лишь модель выбора по агрегированному отношению, но она изучалась ранее под другим углом зрения.
Основные результаты работы получены в следующих направлениях:
Исследованы функциональные возможности моделей выбора и их зависимость от ряда параметров (типов используемых отношений, глубины, информационной структуры).
Для большинства задач, связанных с анализом, синтезом и оптимизацией рассматриваемых моделей указаны теоретически эффективные методы решения, для других доказана ^/Р-трудность и некоторые из /VP-трудных задач решены в ослабленных постановках.
. - Для рассмотренных моделей выбора и различных характерне- тик их сложности предложены методы реализации, гарантирующие асимптотически наименьшую либо наименьшую по порядку оценку сложности, исследовано взаимное влияние различных характеристик сложности.
Эти или аналогичные им результаты прежде в исследованиях других авторов не встречались.
Практическая ценность. Совокупность результатов и методов, представленных в диссертации, позволяет строить и исследовать значительно более разнообразные и приближенные к реальности модели выбора, чем использовавшиеся ранее подходы, основанные на выявлении предпочтений и нахождении полезностей. Эти методы могут быть применены к решению практически важных проблем, связанных с разработкой моделей принятия решений в задачах управления.
проехтирования, диагностики, искуственного интеллекта на основе наблюдения за действиями опытных специалистов, с построением оптимизационных моделей выбора лучших вариантов, прогнозированием выбора.
Полученные з диссертации оценки сложности и энтропии для классов механизмов выбора позволяют до построения моделей предвидеть их ориентировочную сложность, оценить способность прогнозирования ими выбора в новых ситуациях. Конструкции, на основе которых получены оценки сложности, могут быть использованы для построения экономных моделей с гарантированной сложностью. Развитые в работе методы оптимизации дают возможность упрощения моделей.
Предложенный в работе логический метод является удобным инструментом для представления и исследования задач выбора. Он нашел применение в системе подготовки студентов - излагается и существенно используется в учебном пособии "Теория выбора и принятия решений", М.: Наука, 1982, написанном коллективом авторов под руководством И.М.Макарова.
Апробация работы и публикации. Представленная работа является частью исследований, выполнению: автором во ВНИИСй АН СССР с 1976 по 1987 г.г.
Результаты работы докладывались и обсуждались на Ш Всесосв-ной научной школе "Прогнозирование научно-технического прогресса" (Минск, 1979), на Юбилейной конференции научных работ ВНИИСИ (1981), на I Всесоюзном совещании по статистическому и дискретному анализу нечисловой информации и экспертным оценкам (Алма->
і Ата, 1981), на Всесоюзном семинаре по дискретной математике и ее приложениям (Москва, 1984), на П Всесоюзной конференции "Математические методы распознавания образов" (Дилижан, 1985), на
.-6-
УІ Международной конференции "Основы теории вычислений" (Казань, 198?). Они неоднократно докладывались на семинарах по синтезу управляющих систем в МГУ, по теории графов в ИПУ Минприбора и АН СССР, семинарах математического отдела ЦЭМИ АН СССР, семинарах "Математические методы в экспертных оценках и анализ нечисловой информации", проводимых совместно МГУ, Научным советом по проблеме "Кибернетика" АН СССР и ВСНТО.
Апробация диссертации в целом была проведена во ВНВДСИ АН СССР в мае 1987 г. на объединенном семинаре отделов "Математические методы информатики и управления", "Теория и методы принятия решений", "Человеко-машинные методы анализа и синтеза систем".
По теме диссертации автором опубликовано 26 научных работ, из которых 4 в соавторстве (с Д.Б.Юдиным). По материалам исследований также написана монография "Логические методы исследования дискретных моделей выбора" (20 п.л.), включенная в план издательства "Наука" на 1989 г.
Структура и объем работы. Диссертация состоит из.5 глав, заключительной части, содержащей основные результаты и выводы, списка литературы, включающего 127 наименований, содержит 6 рисунков. Полный объем - 311 страниц машинописного текста.
