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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«Гомельский государственный технический университет имени П. О. Сухого»

Факультет автоматизированных и информационных систем

Кафедра «Информационные технологии»

направление специальности 1-40 01 02-01 «Информационные системы и технологии в проектировании и производстве»

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

к курсовому проекту

по дисциплине «Оптимизация проектных решений»

на тему: «Программное средство для выбора оптимального компьютера для сотрудников организации»

Гомель 2015 

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

Оптимизация как раздел математики существует достаточно давно. Оптимизация – это выбор, то есть то, чем постоянно приходится заниматься в повседневной жизни. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее нахождение наилучшего варианта среди всех существующих. В любой практической оптимизационной задаче существует много совпадающих этапов. Наиболее важным этапом является моделирование рассматриваемой физической ситуации с целью получения математической функции, которую необходимо минимизировать, а также определения ограничений, если таковые существуют. Затем следует выбрать подходящую процедуру для осуществления минимизации. Эта процедура должна быть реализована на практике, что во многих реальных случаях вынуждает использовать ЭВМ для выполнения большого объема вычислений.

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

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

1 АНАЛИЗ МЕТОДОВ ОДНОКРИТЕРИАЛЬНОЙ И МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

1.1 Оптимизация. Основные понятия

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

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

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

По наличию ограничений на целевую функцию и рабочие параметры различают оптимизацию без ограничений и при наличии ограничений.

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

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

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

С теорией оптимизации тесно связаны математическое программирование, теория исследования операций, теория принятия решений, динамическое программирование [1].

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

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

Выделим основные этапы решения задачи оптимизации [2]:

– постановка задачи. На этом этапе аналитику необходимо трансформировать слова заказчика в четко сформулированную задачу;

– построение математической модели задачи. Здесь четко поставленная и сформулированная жизненная проблема формализуется математически.

– решение математической модели задачи;

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

Рассмотрим более подробно однокритериальные и многокритериальные задачи оптимизации.

1.2 Однокритериальная оптимизация

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

Общая постановка задачи одномерной оптимизации заключается в следующем: дана некоторая функция f(x) от одной переменной x, необходимо определить такое значение x*, при котором функция f(x) принимает экстремальное значение. Под ним обычно понимают минимальное или максимальное значения. В общем случае функция может иметь одну или несколько экстремальных точек. Нахождение этих точек с заданной точностью можно разбить на два этапа. Сначала экстремальные точки отделяют, т.е. определяются отрезки, которые содержат по одной экстремальной точке, а затем уточняют до требуемой точности e.

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

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

Большим достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений f(x) в заданных точках [3].

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

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

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

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

,                              (1.1)

где – целевая функция, критерий оптимальности или линейная форма;

       –  коэффициенты целевой функции;    

       – вектор неизвестных.

При ограничениях:

                               (1.2)

,                  (1.3)

                                         (1.4)

где    - коэффициенты ограничений;

         – вектор неизвестных;

         - величины правых частей ограничений.

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

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

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

1.3 Многокритериальная оптимизация

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

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

Некоторые из подходов к задачам со многими критериями [5]:

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

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

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

В многокритериальной задаче оптимизации сравнение решений по предпочтительности осуществляется не непосредственно, а при помощи заданных на X числовых функций f1, f2, … fm, называемых критериями. Предполагается, что m ≥ 2, при m = 1 задача оптимизации является однокритериальной.

В задачах принятия индивидуальных решений критерии служат для выражения «интенсивности» существенных свойств (признаков) решений. В задачах принятия групповых решений критерий U характеризует «качество» (или предпочтительность) решений с точки зрения индивида i, входящего в группу {1, 2, …, m}.

По своему характеру критерии подразделяются на два типа: количественные и качественные. Критерий является количественным, когда его значения имеет смысл сравнивать, указывая, на сколько, или во сколько раз одно значение больше другого, и качественным, когда такие сравнения бессмысленны [6].

2 РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ

2.1 Структуризация задачи

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

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

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

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

Рисунок 2.1 – Структурная схема задачи выбора компьютера для сотрудников организации

2.2 Метод полного перебора

Полный перебор – это простейший метод минимизации. Суть метода заключается в последовательном переборе элементов, имеющих различные значения интересующего параметра. В ходе перебора находится элемент, у которого значение параметра, интересующего нас, наиболее полно удовлетворяет требованиям. Главный недостаток данного метода – долгое время выполнения при больших количествах обрабатываемых элементов. Основная задача при реализации такого метода заключается в написании алгоритма, требующего наименьшее время на поиск решения. Блок схема алгоритма представлена на рисунке 2.2.

Рисунок 2.2 – Блок-схема алгоритма полного перебора

2.3 Метод Ранга

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

Метод приписывания баллов (метод ранга). Этот метод основан на том, что эксперты оценивают важность частного критерия по шкале от 0 до 10. При этом разрешается оценивать важность дробными величинами или приписывать одну и ту же величину из выбранной шкалы нескольким критериям. Обозначим через hik - балл i-го эксперта для k-критерия, тогда

                                                                                            (2.1)

где - сумма баллов i-ой строки;

        m – количество критериев.

        rik – называют весом, подсчитанным для k-го критерия i-м экспертом.

Отсюда, учитывая, что , где L - количество экспертов, получим веса альтернатив:

                                               (2.2)

Лучшей считается альтернатива, имеющая наибольший вес.

Блок-схема алгоритма представлена в приложении А.

2.4 Метод Парето

Итальянский экономист В. Парето сформулировал один из самых распространенных экономических критериев оптимальности. Он формулируется очень просто: «Следует считать, что любое изменение, которое никому не причиняет убытков и которое приносит некоторым пользу, является улучшением».

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

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

Алгоритм выделения области Парето:

1. Выбрать проект Пi, полагая i = 1.
2. Проект Пi сравнивается с остальными по всем показателям и отмечаются те из них, которые строго хуже, чем Пi.
3. Отмеченные проекты не могут принадлежать области Парето и из дальнейшего рассмотрения исключаются.
4. Полагаем i = i + 1.
5. Если и проект Пi уже был отмечен на предыдущих итерациях, то выполняется переход к п.4.
6. Если и проект еще не помечен, то производится переход к п. 2.
7. Если , где n – число сравниваемых проектов, то осуществляется переход к п. 8.
8. Оставшиеся не отмеченными проекты образуют множество эффективных решений (область Парето).

Если использовать дополнительную информацию, например, об относительной важности показателей, то можно получить дальнейшее уточнение мест проектов [6].

2.5 Метод анализа иерархий

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

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

Метод анализа иерархий применяется при решении самых разнообразных проблем, среди которых, в частности: проектирование транспортных систем крупных городов, разработка планов обеспечения энергетическими ресурсами отраслей промышленности, оценка сценария развития высшего образования, определение приоритетных направлений научных исследований и др.[7].   

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

3.1 Постановка задачи

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

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

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

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

Для решения задачи многокритериальной оптимизации необходимо выполнить несколько этапов. Рассмотрим их.

Изначально необходимо организовать перевод возможности проведения видеоконференций в безразмерную величину. Диапазон значений приведён в таблице 3.1.

Таблица 3.1 – Перевод в безразмерную величину

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

Далее принимается во внимание оценки экспертов. И используя все это, находится оптимальное решение.

3.2 Структура программного комплекса

Программное обеспечение для решения поставленной задачи было реализовано в среде разработки MS Visual Studio 2013 на языке C#. Данная среда разработки позволяет быстро, эффективно и просто создать полноценное и многофункциональное приложение.

Исходные данные в таблицы считываются с файла. Пример файла с исходными данными представлен на рисунке 3.1.

Рисунок 3.1 – Пример файла с исходными данными

С помощью существующих компонентов в MS Visual Studio 2013 на языке C# создан графический интерфейс, как и все остальные методы, они размещены в классах Form1, Form2, Form3, Form4, Line, MultiCriterionOptimization, OneCriterionOptimization здесь же отображаются результаты работы приложения.

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

• класс Form1, главный класс, который отображается при запуске программы;
• класс Form2, который отображается информацию о разработанном приложении;
• класс Form3, для реализации однокритериальной оптимизации;
• класс Form4, для реализации многокритериальной оптимизации;
• класс Line, содержит информацию об альтернативах, реализует перевод в безразмерные величины;
• класс OneCriterionOptimization, в нем реализован полный перебор;
• класс MultiCriterionOptimization, в нем реализован метод Ранга, метод Парето, метод анализа иерархий .

Исходный код приложения представлен в приложении Б.

Таблица 3.2 – Описание класса Line