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

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

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

Шаг 1. Исключение заведомо неоптимальных вариантов решений

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

Таблица 3 - Исходные данные примера

Рисунок 2 - Расположение альтернатив после нормализации данных

Шаг 2. Нормализация исходных данных

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

Где

Cн _ нормированная стоимость

С _ стоимость

_ минимальная стоимость

_ максимальная стоимость

Где

- нормированный дефект

- эффективность

- минимальная эффективность

_ максимальная эффективность

Результаты расчетов показаны в 4-м и в 5-м столбце таблицы 3.

Шаг 3. Расчет индексов стоимости и дефекта

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

Таблица 4 - Нормализованные исходные данные и расчетные параметры примера

Заполним 4-ый столбец, с названием «Индекс стоимости». В первую его строчку занесем частное от деления нормированной стоимости варианта решения 2 на нормированные потери предшествующего варианта решения (с номером 1) и так далее вплоть до предпоследней клетки столбца, как показано линиями в таблице 4.

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

Шаг 4. Расчет шансов оптимальности вариантов решений

Заполним 6-й столбец таблицы 4. Для удобства выделим курсивом числа, не большие единицы, стоящие в 4-м и в 5-м столбце таблицы 4.

В первую строку столбца 6 занесем число из первой строки индекса стоимости. Затем, идя от первой строки столбца 6 вниз, будем вносить в клетку разность отмеченных курсивом индексов стоимости, стоящих в текущей и последующей (с большим номером) клетках Индекса стоимости (столбец 4). Так, во вторую строку занесем число 0,355 как разность между 0,555 и 0,2. Продолжаем этот процесс, пока не закончатся отмеченные курсивом числа.

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

В редких случаях процесс завершится полным заполнением всех клеток столбца 6, тогда в клетке, в которой «встретились» оба процесса заполнения (сверху и снизу), окажется число 1. Как правило, же, одна клетка окажется незаполненной. В нее нужно внести число, которое дополняет сумму всех чисел столбца 6 до числа 2. В нашем примере это число равно

2 - 0,2 - 0,355 - 0,261 - 0,5 - 0,3 = 0,384

Теперь заполним последний столбец таблицы 4 (столбец 7), перенеся в него числа столбца 6, умноженные на 50 (рекомендуется округлить их до ближайших целых чисел так, чтобы сумма всех чисел в столбце 7 составила 100).

Числа, стоящие в 7-м столбце таблицы 4, характеризуют целесообразность выбора соответствующих им решений в качестве оптимальных. В рассматриваемом примере, таким образом, наилучшим решением является решение (Д) под номером 5 [1].

1.3 Формулирование требований к результатам исследования

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

2. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ

2.1 Построение математической модели

На факультете ИСТ Самарского государственного архитектурно-строительного университета разработан и реализован метод расчета шанса оптимальности, называемый «Простой и универсальный метод принятия решений в пространстве критериев «стоимость _ эффективность». Создателем этой модели является С.А. Пиявский.

Перейдем к формированию математической модели. Пусть задано вариантов решений, характеризуемых количественными значениями двух критериев: стоимости и эффективности. Обозначим через номер варианта решения, а через - значения для него количественных критериев стоимости и эффективности. Будем считать, что среди вариантов решений нет неэффективных по Парето и что номера вариантов решений следую в порядке возрастания их стоимости. Нормируем значения критериев от минимального, принятого за нуль, до максимального, принятого за единицу, и перейдем от нормированной эффективности к нормированному дефекту , дополняющему нормированную эффективность до единицы. [1]

Тогда

(1)

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

Рисунок 3 - Направляющие линии оценочной функции при расчете шансов оптимальности вариантов решений

Для «внутреннего» варианта решения с номером наклон направляющих прямых ограничен линиями ОС, ОВ.

Это выразится неравенством

(2)

С учетом ограничений, наложенных на коэффициенты оценочной функции, неравенство (2) распадется на два неравенства:

если , то

, откуда ,

, откуда ;

если , то

, откуда ,

, откуда .

Для оптимальности варианта решения с номером 1 направляющая прямая Г должна находиться между прямой ОА и осью ординат на рисунке 3. Аналогично рассуждениям, проведенным для «внутреннего» варианта решения, легко показать, что этому отвечают условия [1]

.

Заметим, что в данном случае неравенство (2) в предположении приводит к условию , что возможно лишь в вырожденном случае .

Для оптимальности варианта решения с номером направляющая прямая Г должна находиться между прямой ОD и осью абсцисс на рисунке 3. Аналогично предыдущим рассуждениям, легко показать, что этому отвечают условия [1] .

Заметим, что в данном случае неравенство (2) в предположении приводит к условию , что возможно лишь в вырожденном случае .

2.2 Допущения и упрощения при моделировании

Особенно простые результаты в виде конечных формул получаются в задаче, в которой сравниваются всего три варианта решения, в этом случае шансы оптимальности решений таковы [1]:

Для решения, отображенного точкой 1, , для решения, отвечающего точке 2, , а для решения, отвечающего точке 3, .

3. ИНФОРМАЦИОННАЯ СИСТЕМА

3.1 Обзор аналогов

3.1.1 Программа многокритериальной оценки и выбора [ПРИНН6]

Метод ПРИНН очень сложен математически, но не требует от пользователя практически никаких усилий. В его основу положено привлечение для оценки альтернатив оптимально подобранной группы “экспертов”.

Одна из удачных реализаций существует на портале sciyouth.ru [5].

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

Для этого нужно:

1) Запустить программу

2) Ввести перечень вариантов решений "+Вариант"

3) Ввести перечень критериев "+Критерий" и указать для каждого:

a) Его тип (количественный, качественный)

b) Направление оптимизации (максимум, минимум или несущественно)

c) Группу важности (от 0 до 5, большей важности отвечает больший номер группы)

d) Для всех вариантов решения ввести значения всех критериев,

Рисунок 4 - Интерфейс программы [ПРИНН6]

Программа «ПРИНН» показывает результат в зависимости от пользователя, вводимые данные могут быть совершенно одинаковыми, а результат совершенно разным.

Результат в программе «ПРИНН» зависит от степени важности вводимого параметра по пятибалльной системе.

3.1.2 Программа принятия решений в многокритериальных ситуациях (MBI-AHP)

MBI-AHP - программа позволяет принимать решений в многокритериальных ситуациях. MBI-AHP решает такие проблемы как:

1) Портфельное управление

2) Выбор продавца и (или) клиента

3) Стратегическое Планирование

4) Управление персоналом

C помощью MBI-AHP можно выбрать людей с лучшими навыками, для выполнения конкретных требований и определить ключевые силы и слабости служащего для дальнейшего совершенствования. Пример работы программы представлен на рисунках 5, 6, 7 [6].

Рисунок 5 - Интерфейс программы (MBI-AHP)

Рисунок 6 - Интерфейс программы (MBI-AHP)

Рисунок 7 - Интерфейс программы (MBI-AHP)

3.1.3 Сравнительный анализ

Из выбранных аналогов ПРИНН6 и MBI-AHP представляет собой очень сильные инструменты для решения многокритериальных задач. Программа MBI_AHP поддерживает работу с БД, предоставляет результаты графически, но сложна в освоении. Данная программа хорошо подходит для коммерческих предприятий. Программа ПРИНН6 не поддерживает работу с БД, не позволяет увидеть графически результат, зато достаточно проста в использовании, предоставлена в открытом доступе на сайте СГАСУ факультета информационных систем и технологий активно используется студентами.