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

Размещено на http://www.allbest.ru/

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

, (1.1)

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

, (1.2)

, (1.3)

(1.4)

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

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

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

a_{i, j} коэффициенты ограничений;

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

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

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

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

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

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

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

Перечислим некоторые из подходов к задачам со многими критериями:

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

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

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

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

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

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

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

В многокритериальной задаче оптимизации сравнение решений по предпочтительности осуществляется не непосредственно, а при помощи заданных на X числовых функций f₁, f₂, … f_m, называемых критериями (а также показателями качества или эффективности, критериальными функциями, целевыми функциями и т. п.). Предполагается, что m ? 2 при m = 1 задача оптимизации является однокритериальной.

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

В задачах принятия индивидуальных решений критерии служат для выражения «интенсивности» существенных свойств (признаков) решений. В задачах принятия групповых решений критерий U характеризует «качество» (или предпочтительность) решений с точки зрения индивида i, входящего в группу {1, 2, ..., m}. Например, если решений конечное число и индивид i все их проранжировал (упорядочил по предпочтительности), то можно принять F_i(x?) = 1 для наиболее предпочтительного решения х?, f_i(x??) = 2 для следующего по предпочтительности решения х", и т. д.

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

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

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

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

 (1.5)

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

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

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

(1.6)

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

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

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

(1.7)

Элементы этой матрицы (относительные значимости объектов) можно рассматривать как отношения истинных важностей

(1.8)

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

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

 (1.9)

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

Таблица 1.1 - Девятибалльная шкала относительной важности объектов

Степень важности	Определение	Пояснения
1	Объекты одинаково важны	Оба объекта вносят одинаковый вклад в достижение цели
3	Один объект немного важнее другого	Есть основания предпочесть один объект другому, но их нельзя считать неопровержимыми
5	Один объект существенно важнее другого (сильное превосходство)	Существуют веские свидетельства того, что один из объектов более важен
7	Один объект явно важнее другого	Имеются неопровержимые свидетельства превосходства одного объекта над другим
9	Один объект абсолютно важнее другого	Превосходство одного объекта над другим не вызывает сомнения
2, 4, 6, 8	Значения, приписываемые промежуточным суждениям	Используются, когда выбор между двумя соседними нечетными числами затруднителен

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

(1.10)

где k - число экспертов;

n - количество альтернатив.

После этого определяются обобщенные оценки предпочтения альтернатив над другими (с учетом мнения всех экспертов) - и находится сумма всех оценок . Находятся веса альтернатив по формуле (1.11):

(1.11)

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

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

Определение степени влияния факторов на производительность труда по методу предпочтений выполняется в следующем порядке.

1. Каждому эксперту предлагается выполнить ранжирование альтернатив по предпочтению. В данном примере каждый эксперт присваивает номер 1 фактору, который (по его мнению) оказывает наибольшее влияние на рост производительности труда; 2 следующему по важности фактору, и т.д. Оценки, указанные экспертами, сводятся в матрицу размером MxN, где M количество экспертов, N количество альтернатив. Обозначим эти оценки как Xij, i=1,...,M, j=1,...,N.

Чем больше вес, тем более предпочтительной является альтернатива (по мнению экспертов).

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

Для проверки согласованности мнений экспертов вычисляется величина, называемая коэффициентом конкордации (W). Ее расчет выполняется в следующем порядке [7].

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

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

Предприятие планирует освоить выпуск нового изделия в количестве не менее 15 000 штук в год. Для этого ему необходимо приобрести станки двух типов. Характеристики станков, из которых делается выбор, приведены в таблицах 2.1 и 2.2. При этом, на изготовление изделия, предприятие может выделить не более 150 часов в месяц. Существует также ограничение по стоимости (не более 2000 млн.руб.) и по потребляемой мощности (не более 100000 кВт-ч в месяц).

Таблица 2.1 - Технические характеристики станков первого вида

Станок	ST11	ST12	ST13	ST14	ST15
Производительность, изд./час	8	5	19	13	11
Стоимость, млн. руб.	930,0	310,0	1320,0	450	957,0
Энергоэффективность, кВт-ч/изд.	15,3	30,5	27,0	25,0	13,6

Таблица 2.2 - Технические характеристики станков второго вида

Станок	ST21	ST22	ST23	ST24	ST25
Производительность, изд./час	16	17	12	15	10
Стоимость, млн. руб.	1400,0	1200,0	1100,0	700,0	550,0
Энергоэффективность, кВт-ч/ изд.	22,0	14,0	33,0	20,0	21,3

Кроме того, при выборе станков необходимо учесть мнение экспертов в отношении этого оборудования (таблицы 2.3 и 2.4)

Таблица 2.3 - Эксплуатационные характеристики станков первого вида

Станок	ST11	ST12	ST13	ST14	ST15
Сервисное обслуживание	да	нет	да	да	нет
Надежность (наработка на отказ), ч	100 000	170 000	50 000	90 000	110 000
Удобство в использовании	отлично	плохо	плохо	очень хорошо	хорошо

Таблица 2.4 - Эксплуатационные характеристики станков первого вида

Станок	ST21	ST22	ST23	ST24	ST25
Сервисное обслуживание	да	да	да	нет	да
Надежность (наработка на отказ), ч	130 000	140 000	120 000	100 000	130 000
Удобство в использовании	очень хорошо	хорошо	плохо	плохо	отлично

Таблица 2.5 - Вариант задания

Однокритериальная оптимизация	Многокритериальная оптимизация
метод	параметр	Метод экспертного анализа	Число экспертов	Метод отбора	Выбор лучшего решения
перебор	произв.	Саати	2	Парето	МАИ

В соответствии с вариантом задания на курсовой проект (таблица 2.5) необходимо:

1) разработать программное средство оптимизации по заданному критерию в рамках существующих ограничений методом полного перебора (критерий выбирает пользователь);

2) разработать программное средство многокритериальной оптимизации с учетом мнения одного или двух экспертов. Для этого необходимо:

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

- определить лучшую альтернативу методом экспертного анализа (Метод предпочтений);

- реализовать отбор бесперспективных альтернатив (Множество Парето);

- определить лучшую альтернативу методом анализа иерархий.

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

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

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

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

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

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

1. Для начала необходимо перевести все качественные оценки в числовую форму по шкале Харрингтона. Диапазон значений по данной шкале приведён в таблице 2.6

Таблица 2.6 Шкала Харрингтона

Качественные оценки	Очень плохо	Плохо	Удовлетворительно	Хорошо	Отлично
Количественные оценки	0.0 - 0.2	0.2 - 0.36	0.36 - 0.63	0.63 - 0.8	0.8 - 1.0

Оценки типа «да/нет» так же переводятся в числовую форму, причём оценке «да» соответствует значение - 0.67, а «нет» - 0.33.

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

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

Пусть имеется m экспертов: Э₁, Э₂, ..., Э_m и n критериев: Z₁, Z₂, ..., Z_n .

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

составляется исходная матрица k предпочтений размером mЧn, причём 1 ? k_ij ? n, где ;

составляется модифицированная матрица K предпочтений. С оценками:

; (2.1)

находятся суммарные оценки предпочтений по каждому критерию:

; (2.2)

вычисляются исходные веса критериев:

(2.3)

Наиболее предпочтительной является альтернатива, имеющая максимальный вес.

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

(2.4)

Находится . Находится коэффициент конкордации:

(2.5)

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

3. Реализуется метод Парето для отбора бесперспективных альтернатив.

Суть данного метода заключается в следующем: одна альтернатива превосходит вторую, если она превосходит ее, по крайней мере, по одной компоненте и не хуже второй по любой другой компоненте. Если альтернатива удовлетворяет этому свойству относительно всех других альтернатив, то ее называют парето-оптимальной [7].

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

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

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

4. Определяем лучшую альтернативу методом анализа иерархий (МАИ). Рассмотрим более подробно данный метод.

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

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

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

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

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

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

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

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

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

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

Рисунок 2.1 - Схема алгоритма метода Саати

Данная схема состоит из восьми основных блоков, два из них являются подпрограммами. Алгоритмы подпрограмм представлены на рисунках 2.2 и 2.3 соответственно. Рассмотрим данные подпрограммы более подробно.

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

Рисунок 2.2 - Схема алгоритма вычисления сумм оценок по столбцам

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



Рисунок 2.3 - Схема алгоритма вычисления суммы значений массива

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

целевой саати однокритериальный алгоритм

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

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

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

Созданное приложение состоит из семи пользовательских классов, реализующих методы, описанные в разделе 2.2. Рассмотрим каждый класс более подробно.

Класс Odnomernaj - содержит методы для организации однокритериальной оптимизации методом полного перебора по заданному критерию с учётом ограничений. Рассмотрим структуру класса.

Данный класс включает следующие поля:

dataGridView1 - содержит технические характеристики всех альтернатив. Тип поля DataGridView.

dataGridView2 - содержит технические характеристики альтернатив подходящих по заданному критерию. Тип поля DataGridView.

chasmes количество часов на изготовление изделий в месяц. Тип поля double.

moshnmes - максимально возможная потребляемая мощность станками в месяц. Тип поля double.

koluz - количество изделий, выпускаемых предприятием в год. Тип поля double.

stoim - максимально возможная общая стоимость станков. Тип поля double.

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

Proiz - реализует метод полного перебора по критерию «Производительность». В данном методе так же реализована проверка на соответствие альтернатив ограничениям. Результатом метода является список альтернатив, в которых значение критерия «Производительность» удовлетворяет ограничениям.

Stoim - реализует метод полного перебора по критерию «Стоимость». В данном методе так же реализована проверка на соответствие альтернатив ограничениям. Результатом метода является список альтернатив, в которых значение критерия «Стоимость» удовлетворяет ограничениям.

Energ - реализует метод полного перебора по критерию «Энергоэффективность». В данном методе так же реализована проверка на соответствие альтернатив ограничениям. Результатом метода является список альтернатив, в которых значение критерия «Энергоэффективность» удовлетворяет ограничениям.

Sort - сортирует список, полученный в методе Proiz или Stoim,или Energ, по убаванию или возрастанию знасения выбранного критерия (например, если выбран критерий «Стоимость», то список отсортируется по возростанию). На вход подается список альтернатив, а на выходе получаем отсортированный список, причем первый элемент списка - лучшая альтернатива по выбранному критерию.

Класс Mnogomernaj - реализует методы, необходимые для организации многокритериальной оптимизации. Рассмотрим данный класс более подробно.

Данный класс включает следующие поля:

dataGridView1 - содержит технические характеристики всех альтернатив. Тип поля DataGridView.

dataGridView2 - содержит технические характеристики альтернатив подходящих по заданному критерию. Тип поля DataGridView.

oc1, oc2 - матрицы экспертных оценок первого и второго экспертов соответственно. Тип поля double;

ves - содержит веса критериев. Тип поля double;

A1 - содержит итоговые оценки альтернатив. Тип поля double [ ];

soglas - коэффициент согласованности. Тип поля double.

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

Pareto - реализует метод Парето для отбора бесперспективных альтернатив. На вход подаются приведённые в безразмерный вид характеристики станков двух типов. В результате работы метода из сформированных ранее альтернатив удаляются бесперспективные альтернативы;

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

Perev - перевод количественных оценок в безразмерный вид. В качестве параметров метод получает массив исходных оценок (которые нужно перевести), переменную типа bool, которая принимает значение true - если по значению оценка чем больше, тем лучше и false - иначе (например, если рассматривать оценки по критерию «Стоимость», то чем ниже оценка по данному критерию, тем лучше эта альтернатива для нас, а если - оценки по критерию «Производительность», то чем ниже оценка, тем хуже данная альтернатива);

Perevod - перевод оценок типа «Да/Нет» и перевод качественных оценок по шкале Харрингтона. В качестве параметров метод принимает строковое представление исходный оценки.

Soglas - вычесляет коэффициент соглассованности выставленных экспертами оценок. Возвращает число типа double;

Veskrit - расчитывает значения весов по каждому критерию.

Saati - реализует метод экспертного аннализа Саати и метод анализа иерархий. Для реализации метода Саати используются методы Soglas и Veskrit, описанные выше. Результатом выполнения метода является массив, содержащий итогорые оценки каждой альтернативы.

Класс Vizual - содержит методы для отображения результатов работы, как однокритериальной, так и многокритериальной оптимизации.

Класс Form4 - содержит графический интерфейс пользователя для ввода оценок экспертом.

Класс Form3 - содержит графический интерфейс пользователя и использует методы класса Mnogomernaj. В этом классе обрабатываются данные введенные экспертом. В результате выдается конечный результат работы приложения по многокритериальной оптимизации.

Класс Form2 - содержит графический интерфейс пользователя и использует методы класса Odnomernaj. В результате выдается конечный результат работы приложения по однокритериальной оптимизации.

Класс Form1 - содержит графический интерфейс пользователя и использует классы Form2 и Form3.

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

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

Разработанный пользовательский интерфейс является простым и интуитивно-понятным для обычного пользователя.

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

Всё приложение разделено на две основные области. Рассмотрим их:

1) Область «Технические характеристики станков» предназначена для ввода технических характеристик станков. В первую таблицу заносятся параметры станков первого типа, во вторую - второго типа. Так же в данных таблицах можно редактировать данные. Для редактирования необходимо выбрать нужную ячейку, кликнуть по ней два раза и ввести новое значение вместо старого.



Рисунок 3.1 - Вид главного окна приложения

2) Область «Меню» это основная часть приложения. Как видно из рисунка 3.1 она состоит из двух вкладок «Однокритериальная оптимизация» и «Многокритериальная оптимизация». Рассмотрим данную часть приложения более подробно.

Вкладка «Однокритериальная оптимизация» предназначена для проведения одномерной оптимизации. Чтобы программа провела оптимизацию для начала необходимо выбрать один из трёх предлагаемых критериев: производительность, энергоэффективность и стоимость. После выбора критерия нужно нажать кнопку «Оптимизировать» после чего приложение выдаст результат проведенной оптимизации, т.е. лучшую пару станков, которые будут выделены красным (лучшая альтернатива по выбранному параметру) и оранжевым (вторая и третья альтернативы, после лучшей) цветами в соответствии с рисунком 3.2.

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



Рисунок 3.2 - Результат работы одномерной оптимизации

Для того, чтобы ввести оценки экспертов, нужно нажать на кнопку «Оптимизировать», после чего появится новое окно, что позволит нам ввести оценки первого эксперта. После ввода оценок жмем кнопку «Ок», после чего выскакивает новое окно, которое позволяет ввести оценки второго эксперта. Если оценки не будут введены, при закрытии окон будет выдано сообщение, представленное на рисунке 3.3

Рисунок 3.3 - Окно, появляющееся, если не введены оценки экспертов

Для закрытия данного окна нужно нажать кнопку «OK», после чего снова появится главное окно приложения и в нём можно снова нажать кнопку «Оптимизировать» и ввести оценки экспертов.

После задания оценок нужно нажать кнопку «Оптимизировать» и приложение выдаст результат оптимизации как представлено на рисунке 3.4.

Рисунок 3.4 - Результат работы многомерной оптимизации

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

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

В поставленной задаче в качестве исходных данных выступают технические характеристики двух типов станков по следующим шести критериям: производительность, энергоэффективность, стоимость станка, сервисное обслуживание, надёжность и удобство в использовании. По данным характеристикам и происходит выбор двух станков разного типа, но так же по условию задачи мало, чтобы станки соответствовали максимальным характеристикам по всем критериям, они должны соответствовать следующим ограничениям: стоимость двух станков не должна превышать 1000 млн. рублей, максимальная потребляемая мощность не должна превышать 50000 кВт-ч в месяц, количество изготавливаемых изделий в год должно быть не менее 10000 штук в год, на изготовление изделия тратиться не более 200 часов в месяц. На основе всех вышеописанных данных производится отбор лучшей пары станков.

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

Для начала проведём одномерную оптимизацию по критерию производительность. Приложение выдаст результат в соответствии с рисунком 3.5.

Рисунок 3.5 - Окно, показывающее правильность работы однокритериальной оптимизации по критерию производительность.

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

Рисунок 3.6 - Окно, показывающее правильность работы многокритериальной оптимизации по критерию энергоэффективности.

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

Заключение

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

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

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

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

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

1. Горбунов В.М. Теория принятия решений. Учебное пособие / В.М. Горбунов. Томск: Национальный исследовательский томский политехнический университет, 2010. 67 с.

2. Матузко Ю.О. Теория принятия решений. Учебно-методическое пособие / Ю.О. Матузко. Запорожье: Запорожская государственная инженерная академия, 2009. 61 с.

3. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. - М.: Изд-во МАИ, 1995. - 344 с.

4. Информационные технологии оптимальных решений. Учебный курс для специальности «Государственное управление и экономика». Минск: Академия управления при Президенте Республики Беларусь, 2003. 241 с.

5. Шикин Е.В. Исследование операций / Е.В. Шикин, Г.Е. Шикина. М.: ТК Велби, Изд-во Проспект, 2006. 280 с.

6. Саати Т.Л. Принятие решений. Метод анализа иерархий / Т. Саати. М.: Радио и связь, 1993. 278 с.