Автор работы: Пользователь скрыл имя, 24 Сентября 2015 в 15:57, курсовая работа
Оптимизация как раздел математики существует достаточно давно. Оптимизация – это выбор, то есть то, чем постоянно приходится заниматься в повседневной жизни. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее нахождение наилучшего варианта среди всех существующих. В любой практической оптимизационной задаче существует много совпадающих этапов.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
Учреждение образования
«Гомельский государственный технический университет имени П. О. Сухого»
Факультет автоматизированных и информационных систем
Кафедра «Информационные технологии»
направление специальности 1-40 01 02-01 «Информационные системы и технологии в проектировании и производстве»
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту
по дисциплине «Оптимизация проектных решений»
на тему: «Программное средство для выбора оптимального компьютера для сотрудников организации»
Исполнитель: студент группы ИТ-42 | |
Зигинов Н. В. | |
Руководитель: | |
Мурашко И. А. | |
Дата проверки ____________________ | |
Дата допуска к защите _____________ | |
Дата защиты _____________________ | |
Оценка работы: ___________________ | |
Подписи членов комиссии по защите курсовой работы: ____________________ | |
Гомель
2015
СОДЕРЖАНИЕ
Оптимизация как раздел математики существует достаточно давно. Оптимизация – это выбор, то есть то, чем постоянно приходится заниматься в повседневной жизни. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее нахождение наилучшего варианта среди всех существующих. В любой практической оптимизационной задаче существует много совпадающих этапов. Наиболее важным этапом является моделирование рассматриваемой физической ситуации с целью получения математической функции, которую необходимо минимизировать, а также определения ограничений, если таковые существуют. Затем следует выбрать подходящую процедуру для осуществления минимизации. Эта процедура должна быть реализована на практике, что во многих реальных случаях вынуждает использовать ЭВМ для выполнения большого объема вычислений.
Универсальных методов, подходящих для поиска экстремума абсолютно любой функции не существует, поэтому необходимо изучить предложенные методы оптимизации и найти лучший для решения конкретной задачи.
Данный курсовой проект ставит себе целью исследовать методы оптимизации и применить их на практике, а также разработать Windows-приложение которое автоматически определит оптимальное решение для поставленной задачи. Основной задачей проекта является определение оптимального компьютера для сотрудников организации из предложенных по критериям, важность которых выставляют эксперты.
Оптимизация – это процесс приведения объекта (системы) в оптимальное (наилучшее) состояние. Для проведения оптимизации необходимы: математическая модель объекта, целевая функция и оптимизационный алгоритм. Целевая функция формализует требования, предъявляемые к объекту. Оптимизационный алгоритм ищет экстремум целевой функции.
Оптимизация осуществляется при помощи алгоритмов математического программирования и бывает структурной, параметрической и структурно-параметрической. В процессе структурной оптимизации оптимизируется структура объекта, в процессе же параметрической – оптимизируются параметры элементов, входящих в состав структуры. Эти задачи решаются при помощи алгоритмов дискретного, непрерывного и дискретно-непрерывного математического программирования, соответственно.
В зависимости от числа критериев, по которым выполняется оптимизация объекта, различают однокритериальную и многокритериальную оптимизацию.
По наличию ограничений на целевую функцию и рабочие параметры различают оптимизацию без ограничений и при наличии ограничений.
В случае параметрического синтеза при известной структуре объекта подбираются параметры элементов таким образом, чтобы минимизировать (максимизировать) целевую функцию.
Следует заметить, что существующие оптимизационные алгоритмы обычно не гарантируют нахождение глобального оптимума, но это не является критическим. Например, для увеличения вероятности нахождения глобального оптимума можно значительно увеличить число итераций, использовать несколько алгоритмов, многократно запускать соответствующие алгоритмы.
Если помимо подбора параметров необходимо еще и определить структуру объекта, то мы будем уже иметь дело со структурно-параметрическим синтезом, который решается при помощи алгоритмов дискретно-непрерывного математического программирования. Если задача параметрической оптимизации сейчас решается практически для любых объектов, то развитие структурно-параметрической оптимизация сейчас находится лишь на начальной стадии развития.
С теорией оптимизации тесно связаны математическое программирование, теория исследования операций, теория принятия решений, динамическое программирование [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.1) – (1.4), называется допустимым решением или допустимым планом задачи линейной оптимизации. Совокупность всех допустимых планов называется множеством допустимых планов. Допустимое решение называется оптимальным, если оно обеспечивает максимальное (или, в зависимости от условий задачи, минимальное) значение целевой функции.
Решение задач линейной оптимизации может быть получено без особых затруднений (естественно, при корректной формулировке проблемы). Классическим методом решения задач данного типа является симплекс-метод. В случае лишь двух переменных успешно может использоваться также графический метод решения, обладающий преимуществом наглядности. Очевидно, в случае n>2 применение графического метода невозможно.
При решении ряда оптимизационных задач требуется, чтобы значения неизвестных выражались в целых числах. К задачам подобного типа относятся те, в которых требуется определить необходимые для принятия решений значения физически цельных объектов (машин, агрегатов различного типа, людей, транспортных единиц и т.д.) [4].
Чтобы получить более полную характеристику достоинств и недостатков проектируемого объекта, нужно ввести больше критериев качества в рассмотрение. Как результат: задачи проектирования сложных систем всегда многокритериальные, так как при выборе наилучшего варианта приходится учитывать много различных требований, предъявленных к системе.
С привычной точки зрения задача со многими критериями решения не имеет, но к счастью это не так, всегда есть возможность одновременного удовлетворения всех заданных условий. А так как практически любая подобная ситуация допускает разные компромиссные разрешения, то и подходы к их поиску многочисленны и весьма разнообразны.
Некоторые из подходов к задачам со многими критериями [5]:
Концепция принятия решения в качестве первичного элемента деятельности рассматривает решение как сознательный выбор одной из ряда альтернатив, называемых, в зависимости от их конкретного содержания, стратегиями, планами, вариантами и т.п. Этот выбор производит лицо, принимающее решение и стремящееся к достижению определенных целей. В роли такого лица выступают отдельные люди или группы людей, обладающие правами выбора решения и несущие ответственность за его последствия.
Применение математических методов при принятии решений предполагает построение подходящей математической модели. Для задач оптимизации в условиях определенности, когда случайные и неопределенные факторы отсутствуют, компонентами такой модели являются множество X всех альтернативных решений, из которых и надлежит произвести выбор одного наилучшего, или оптимального решения, и описание предпочтений лица, принимающего решение. Для того чтобы была обеспечена возможность выбора, множество X должно содержать не менее двух решений.