Материал: Разработка приложения для выбора покупки пары станков

Разработка приложения для выбора покупки пары станков

Содержание

Введение

. Теоретические сведения

.1 Основные понятия оптимизации проектных решений

.2 Классификация методов оптимизации

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

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

.5 Методы экспертного анализа

. Алгоритмический анализ задачи

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

.2 Описание алгоритма решения задачи

.3 Описание схемы алгоритма метода Саати

Описание разработанного приложения

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

.2 Инструкция пользователя

.3 Анализ исходных данных и верификация работы программы

Заключение

Список использованных источников

Приложение А Листинг программы

Введение

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

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

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

Таким образом, можно сказать, что решение задачи оптимизации проектных решений достаточно нелёгкий процесс, однако часто необходимый, особенно в различных сферах безотходного производства, нефтегазовой, химической и оптической промышленности.

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

1. Теоретические сведения

.1 Основные понятия оптимизации проектных решений

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

Рассматривая некоторую произвольную систему, описываемую т уравнениями с n неизвестными, можно выделить три основных типа задач. Если t=n, задачу называют алгебраической. Такая задача обычно имеет одно решение. Если t>n, то задача переопределена и, как правило, не имеет решения. Наконец, при t<n задача недоопределена и имеет бесконечно много решений. В практике проектирования чаще всего приходится иметь дело с задачами третьего типа.

В процессе решения задачи оптимизации участвуют следующие лица: лицо, принимающее решение; эксперты.

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

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

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

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

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

В случае одного проектного параметра является функцией одной переменной и ее графики - некоторая кривая на плоскости. При двух - целевая функция является функцией двух переменных и ее графиком есть поверхность.

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

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

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

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

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

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

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

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

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

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

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

.2 Классификация методов оптимизации

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

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

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

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

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

Ограничения могут накладываться как по технологическим, так и по экономическим соображениям.

В зависимости от управляющих параметров различают следующие задачи:

оптимизация при одной управляющей переменной - одномерная оптимизация,

оптимизация при нескольких управляющих переменных - многомерная оптимизация,

оптимизация при неопределённости данных,

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

В зависимости от критерия оптимизации различают:

с одним критерием оптимизации - критерий оптимальности единственный.

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

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

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

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

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

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

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

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

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

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

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

, (1.1)

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

, (1.2)

 ,            (1.3)

   (1.4)

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

сj - коэффициенты целевой функции;, j - коэффициенты ограничений;- величины правых частей ограничений.

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

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