Дипломная работа: Информационная система двухкритериальной оптимизации

Министерство образования и науки РФ

ФГБОУ ВО

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ»

Кафедра информационных и развивающих образовательных систем и технологий

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к выпускной квалификационной работе бакалавра на тему:

Информационная система двухкритериальной оптимизации

СТУДЕНТА ГИП-112

Тишакова Василия Андреевича

Самара 2016 г.

РЕФЕРАТ

АЛЬТЕРНАТИВА, ЭФФЕКТИВНОСТЬ, КРИТЕРИЙ, ПРИНЯТИЕ РЕШЕНИЯ, ИНФОРМАЦИОННАЯ СИСТЕМА, ВАРИАНТ, ЛПР

Целью данного исследования является изучение сравнительной эффективности проектных решений по летательным аппаратам.

В ходе исследования был разработана ИС двухкритериальной оптимизации по методу предложенный профессором С.А. Пиявским «Простой и универсальный метод принятия решений в пространстве критериев «стоимость - эффективность».

Система спроектирована по методологии UML и реализована на языке программирования C++ в среде Qt Creator.

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

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

БД - база данных;

ОС - операционная система;

ИС - информационная система;

СУБД - система управления базами данных;

ЛПР - лицо принимающее решение;

ФИСТ - факультет информационных систем и технологий;

Э-П - Эджворта-Парето;

СГАСУ - Самарский государственный архитектурно-строительный университет;

UML - (англ. Unified Modeling Language) - унифицированный язык моделирования;

АНР - (англ. Analytic Hierarchy Process) - подход аналитической иерархии;

MAUT _ (англ. Multi-Attribute Utility Theory) _многокритериальная теория полезности

ВВЕДЕНИЕ

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

Способы принятий решений разнообразны, но наиболее интересный является предложенный профессором С. А. Пиявский «Простой и универсальный метод принятия решений в пространстве критериев «стоимость - эффективность». Основной идеей данного метода является то, что предлагается новое понятие шансов оптимальности многокритериальных альтернатив. Это понятие имеет явный смысл, доступный пониманию ЛПР. Понятие применимо в задачах любой размерности и степени неопределенности, однако в данной работе оно иллюстрируется на простой и потому наглядной задаче двухкритериального выбора, что позволяет показать его ценность [1].

1. ПОСТАНОВКА ПРОБЛЕМЫ

1.1 Обзор методов принятий решений и формулирование темы исследования

1.1.1 Обзор метода аналитической иерархий

Подход аналитической иерархии (Analytic Hierarchy Process -- АНР) возник как эвристическое средство сравнения и выбора альтернатив. В настоящее время уже имеются работы по его аксиоматическому обоснованию. Однако в большинстве публикаций он предстает как эвристический подход, апеллирующий к здравому смыслу пользователя. В журналах публикуются оживленные дискуссии между сторонниками и противникам этого широко известного в принятии решений подхода.

Применение MAUT (Multi-Attribute Utility Theory) требует от ЛПР одинаковых усилий для построения функции полезности как при большом, так и при малом числе альтернатив. Такой подход не всегда приемлем. В случае небольшого числа заданных альтернатив представляется разумным направить усилия ЛПР только на сравнение таких альтернатив. Именно эта идея лежит в основе методов АНР, наиболее известными из которых являются основной (аддитивный) вариант и мультипликативный вариант.

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

1. Проводится структуризация задачи в виде иерархической структуры с несколькими уровнями; цели -- критерии -- альтернативы.

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

3. Вычисляются коэффициенты важности для элементов каждого уровня. При этом проверяется согласованность суждений ЛПР.

4. Подсчитывается количественный индикатор качества каждой альтернативы и определяется наилучшая альтернатива.

Таблица 1 - Шкала относительной важности

При парных сравнениях в распоряжении ЛПР дается шкала словесных определений уровня сравнительной важности, причем каждому уровню важности ставится соответственное число (таблица 1). Для обоснования перехода от словесных определений уровня относительной важности к числам в мультипликативном варианте АНР проводится параллель с психофизикой, в которой изучается, как человек, не пользуясь никакими приборами, измеряет объективные физические величины, такие как вес, громкость звука, яркость света и так далее. В матрицах парных сравнений полученные числа используются для определения весов (коэффициентов важности) сравниваемых объектов (критериев, целей, альтернатив). На заключительном этапе методов АНР полезность альтернативы определяется путем синтеза относящихся к ней весов целей, критериев, альтернатив с использованием либо аддитивной, либо мультипликативной формулы [2].

1.1.2 Особенности метода ШНУР

Метод ШНУР выбора лучшей из группы заданных альтернатив имеет следующие особенности.

В методе используются достаточно простые (с психологической точки зрения) процедуры выявления предпочтений ЛПР.

Диалог ведется на понятном для ЛПР языке, причем рассматриваются как качественные, так и количественные оценки альтернатив по критериям.

Метод позволяет сравнить большое число альтернатив при минимальном числе вопросов к ЛПР.

Метод позволяет приспособиться к конкретной задаче (набору альтернатив) и выделить лучшую или предположительно лучшую альтернативу.

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

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

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

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

- предлагает ввести дополнительные критерии, по которым можно различить альтернативы, которые не удалось сравнить данным методом;

передает окончательный выбор на усмотрение ЛПР.

Метод ШНУР является удобным для ЛПР, «прозрачным» и действенным методом решения широкого круга задач [2].

1.1.3 Обзор метода Эджворта - Парето

Выделяет в методе Эджворта - Парето три этапа:

- поиск информации;

- поиск и нахождение альтернатив;

- выбор лучшей альтернативы;

Следует отметить, что это наиболее обобщенное представление процесса принятия решений, но и самое понятное для первоначального восприятия.

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

Для показа выбора альтернативы на основе критериев приведем пример. Допустим, люди желают отдохнуть и выбирают для этого тур. Критериями выступают стоимость и привлекательность маршрута. Есть несколько альтернатив. Необходимо выбрать одну из них. Варианты можно представить в виде таблице 2. Кроме того, эти альтернативы графически изображены на рисунке 1.

Таблица 2 - Оценки альтернативных вариантов туров

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

Предположим, что по какой-то причине поездка по третьему туру стала невозможной (например, из-за последствий прошедшего наводнения). В соответствии с рисунком 1 туры первый и второй не находятся в отношении доминирования. По одному из критериев лучше альтернатива 2, по другому - альтернатива 1.

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

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

Рисунок 1 - Представление альтернатив их оценками по критериям

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

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

Один из возможных способов решения этой задачи состоит в попарном сравнении альтернатив и исключении доминируемых. Задача выделения множества Э-П обычно рассматривается как предварительная. За ней следует наиболее существенный этап принятия решений [3].

1.2 Общее описание метода «Шансов»

Благодаря простоте применения, предлагаемый метод может быть использован вручную любыми лицами, заинтересованными в объективной сравнительной оценке различных вариантов решений по двум критериям, даже если они владеют только элементарной математикой [1].

Выбор наилучшего из нескольких вариантов решения

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