Многокритериальная оптимизация
 Скачать 163.21 Kb.
|
|
Многокритериальная оптимизация ВВЕДЕНИЕ алгоритм интерфейс графический схема В настоящее время начал возрастать интерес к оптимизации различных процессов в разнообразных областях деятельности человека. Такой интерес понятен, ведь оптимальная альтернатива позволяет экономить денежные средства, материальные ресурсы, сократить отходы производства и получать качественную продукцию. В современном обществе даже обычному человеку, который собирается совершить покупку - приходится в том или ином роде решать задачу многокритериальной оптимизации: как выбрать такую оптимальную альтернативу, которая бы удовлетворяла необходимым критериям. Для этого мы прибегаем к помощи экспертов в данной области и отсеиваем варианты, не удовлетворяющие нашим критериям. Оптимизация это достаточно трудоёмкий процесс, требующий больших вычислительных мощностей, поэтому это сугубо компьютерная задача. Компьютеры тесно вошли в нашу жизнь и системы автоматизированного проектирования, автоматизация различных процессов - уже обычное явление, которое никого не удивляет. Напротив, требования к системам автоматизированного проектирования растут. Из - за сложности технологических процессов, применяемых в промышленности возникает большое число задач, которые нельзя решить с помощью обычного математического аппарата дифференциальных уравнений. Кроме того в результате решения этих задач мы получаем множество решений, которые удовлетворяют параметрам модели системы, однако не все они оптимальны. К таким задачам можно отнести, например задачу гидравлического расчёта бурения нефтяных скважин, где необходимо выбрать наземное оборудование, выбрать тип промывочной жидкости, выбрать параметры трубопровода и многое другое, к тому же, в конечном счете, ещё необходимо учитывать ограничения по давлениям при бурении, глубине бурения, типу грунта и так далее. Грамотно решив данную задачу, мы получим такие параметры модели, которые будут максимально приближены к реальной системе, что позволит предсказать исход бурения и возможные осложнения при бурении. В настоящее время существует множество информационных технологий, позволяющих предельно облегчить жизнь и помочь в решении проблем, связанных с процессами принятия решений в различных предметных областях. В частности, очень распространены сейчас системы поддержки принятия решений на основе Метода Анализа Иерархий, разработанного американским ученым Т. Саати. Процессы принятия решений в различных сферах деятельности во многом аналогичны. Метод Саати - универсальный метод поддержки принятия решений, соответствующий естественному ходу человеческого мышления [1]. Целью данного курсового проекта является написание приложения, позволяющего упростить выбор пары станков среди множества альтернативных вариантов, которые будут использованы для освоения выпуска нового изделия на предприятии. В результате выполнения курсового проекта должны быть реализованы однокритериальная и многокритериальная оптимизации, определение наилучшей альтернативы станков с учетом ограничений на годовую производительность, общую стоимость, потребляемую в месяц электроэнергию и количество рабочих часов в месяц. Освоение выпуска нового изделия - важный процесс подготовки производства, значимым элементом которого является правильно выбранное оборудование, с чем и поможет разработанная система поддержки принятия решений. 1. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ .1 Классификация методов оптимизации Принято различать задачи статической оптимизации для процессов, протекающих в установившихся режимах, и задачи динамической оптимизации. В первом случае решаются вопросы создания и реализации оптимальной модели процесса, во втором - задачи создания и реализации системы оптимального управления процессом при неустановившихся режимах эксплуатации. Если требуется определить экстремум целевой функции без задания условий на какие-либо другие величины, то такая оптимизация называется безусловной. Такие критерии обычно используются при решении частных задач оптимизации (например, определение максимальной концентрации целевого продукта, оптимального времени пребывания реакционной смеси в аппарате и т.п.). Если необходимо установить экстремум целевой функции при некоторых условиях, которые накладываются на ряд других величин (например, определение максимальной производительности при заданной себестоимости, определение оптимальной температуры при ограничениях по термостойкости катализатора и др.), то такая оптимизация называется условной [2]. Процедура решения задачи оптимизации обязательно включает, помимо выбора управляющих параметров, еще и установление ограничений на эти параметры (термостойкость, взрывобезопасность, мощность перекачивающих устройств). Ограничения могут накладываться как по технологическим, так и по экономическим соображениям. В зависимости от управляющих параметров различают следующие задачи: - оптимизация при одной управляющей переменной - одномерная оптимизация; - оптимизация при нескольких управляющих переменных - многомерная оптимизация; - оптимизация при неопределённости данных; - оптимизация с непрерывными, дискретными и смешанным типом значений управляющих воздействий. В зависимости от критерия оптимизации различают: - с одним критерием оптимизации - критерий оптимальности единственный; - со многими критериями. Для решения задач со многими критериями используются специальные методы оптимизации [3]. .2 Однокритериальная оптимизация Задачи одномерной минимизации представляют собой простейшую математическую модель оптимизации, в которой целевая функция зависит от одной переменной, а допустимым множеством является отрезок вещественной оси. Общая постановка задачи одномерной оптимизации сводится к следующему: имеется некоторая функция f(x) от одной переменной x, необходимо найти такое значение x*, при котором функция f(x) принимает экстремальное значение. Под этим значением понимают минимальное или максимальное значения. В общем случае функция может иметь одну или несколько экстремальных точек. Поиск таких точек с определённой точностью обычно разбивают на два этапа. На первом этапе экстремальные точки отделяют. Это значит, определяются отрезки, которые содержат по одной экстремальной точке, а затем уточняют до требуемой точности e. Максимизация целевой функции равнозначна минимизации противоположной величины, следовательно, можно рассматривать только задачи минимизации. Для решения задачи минимизации функции f(x) на отрезке [a, b], в большинстве случаев, используют приближенные методы. С их помощь можно найти решения этой задачи с необходимой точностью в результате нахождения конечного числа значений функции f(x) и ее производных в некоторых точках отрезка [a, b]. Методы, использующие только значения функции и не требующие вычисления ее производных, называются прямыми методами минимизации. Достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений f(x) в заданных точках [4]. Среди задач математического программирования самыми распространёнными и наиболее хорошо исследованными являются так называемые задачи линейного программирования (линейной оптимизации). Рассмотрим этот тип задач. Для них характерно то, что целевая функция линейно зависит от  , а также, что ограничения, накладываемые на независимые переменные, имеют вид линейных равенств или неравенств относительно этих переменных.Эти задачи нередко используются на практике - например, при решении проблем, связанных с распределением ресурсов, планированием производства, организацией работы транспорта и т.д. Общая задача линейной оптимизации заключается в нахождении максимума (минимума) линейной целевой функции. Вид целевой функции и ограничений описываются формулами (1.1-1.4).  , (1.1)при ограничениях:  , (1.2) , (1.3) , (1.4)где  -целевая функция, критерий оптимальности или линейная форма; x- вектор неизвестных; - коэффициенты целевой функции; - коэффициенты ограничений; - величины правых частей ограничений. Вектор значений неизвестных x = (x1, x2, …, xn), удовлетворяющих условию задачи (1.1) - (1.4) , называется допустимым решением или допустимым планом задачи линейной оптимизации. Совокупность всех допустимых планов называется множеством допустимых планов. Допустимое решение x* = (x1*, x2*, …, xn*) называется оптимальным, если оно обеспечивает максимальное (или, в зависимости от условий задачи, - минимальное) значение целевой функции. Решение задач линейной оптимизации может быть получено без особых затруднений (естественно, при корректной формулировке проблемы). Классическим методом решения задач данного типа является симплекс-метод. В случае лишь двух переменных успешно может использоваться также графический метод решения, обладающий преимуществом наглядности. Очевидно, в случае n > 2 применение графического метода невозможно. При решении ряда оптимизационных задач требуется, чтобы значения неизвестных x = (x1, x2, …, xn) выражались в целых числах. К задачам подобного типа относятся те, в которых требуется определить необходимые для принятия решений значения физически цельных объектов (машин, агрегатов различного типа, людей, транспортных единиц и т.д. и т.п.). Такие задачи относятся к задачам целочисленной оптимизации. Математическая модель задачи линейной целочисленной оптимизации также определяется формулами (1.1) - (1.4), но в данном случае налагается дополнительное требование целочисленности всех (или части) неизвестных. Если требование целочисленности распространяется лишь на часть неизвестных величин задачи, то такая задача называется частично целочисленной [5]. .3 Многокритериальная оптимизация Многокритериальная оптимизация или программирование - это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения. Задача многокритериальной оптимизации встречаются во многих областях науки, техники и экономики [5]. Достаточно часто в реальных ситуациях качество эксплуатации исследуемого объекта или системы оценивается не единственным критерием или показателем качества, а совокупностью таких критериев, причем представляющих одинаково значимыми. Такая постановка задачи приводит к задаче оптимизации с векторной целевой функцией формула (1.5): (1.5) которая должна трактоваться неким определенным образом. Как правило, относительная значимость этих целей в общем неизвестна до тех пор, пока не будут определены все основные свойства системы и не будут полностью истолкованы все возможные взаимосвязи. По мере того, как число возможных целей возрастает, то, очевидно, что эти взаимосвязи образуют сложную структуру и их становятся труднее идентифицировать. В данном случае многое зависит от интуиции исследователя и его или ее умения точно выражать те или иные предпочтения в процессе оптимизации. Таким образом, стратегия построения многокритериальной оптимизации состоит, прежде всего, в способности адекватно определить постановку задачи так, что бы эта задача допускала свое решение, а также выразить необходимые предпочтения в виде числовых зависимостей и сохранив при этом реальность поставленной задачи. Задача многокритериальной оптимизации формулируется следующим образом формула (1.6): ,(1.6) , где этоn () целевых функций. Векторы решений приведены в формуле (1.7) и относятся к не пустой области определения S: ;(1.7) Задача многокритериальной оптимизации состоит в поиске вектора целевых переменных, удовлетворяющие наложенным ограничениям, и оптимизирует векторную функцию, элементы которой соответствуют целевым функциям. Эти функции образуют математическое описание критерия удовлетворительности и, как правило, взаимно конфликтуют. Отсюда, «оптимизировать» означает найти такое решение, при котором значение целевых функций были бы приемлемыми для постановщика задачи [5]. Итальянский экономист В. Парето сформулировал один из самых распространенных экономических критериев оптимальности. Он формулируется очень просто: «Следует считать, что любое изменение, которое никому не причиняет убытков и которое приносит некоторым пользу, является улучшением». Критерий Парето имеет весьма широкий экономический смысл и очень часто используется при решении сложных экономических задач. Его можно использовать тогда, когда оптимизация одной совокупности показателей, характеризующих объект, не должна ухудшать другую совокупность не менее важных показателей. Критерий Парето не применим к тем ситуациям, когда экономический эффект одних связан с убытками других. Область решений, оптимальных по Парето, получила название области компромиссов. Алгоритм выделения области Парето: 1) Выбрать проект Пi, полагая i = 1. ) Проект Пi сравнивается с остальными по всем показателям и отмечаются те из них, которые строго хуже, чем Пi. ) Отмеченные проекты не могут принадлежать области Парето и из дальнейшего рассмотрения исключаются. ) Полагаем i = i + 1. 5) Если  и проект Пi уже был отмечен на предыдущих итерациях, то выполняется переход к п.4.) Если и проект еще не помечен, то производится переход к п. 2.) Если  , где n - число сравниваемых проектов, то осуществляется переход к п. 8.) Оставшиеся не отмеченными проекты образуют множество эффективных решений (область Парето). Если использовать дополнительную информацию, например, об относительной важности показателей, то можно получить дальнейшее уточнение мест проектов [6]. Метод анализа иерархий, разработанный под руководством американского специалиста по исследованию операций Т. Саати, применяется, в настоящее время, при решении самых разнообразных проблем, среди которых, в частности: проектирование транспортных систем крупных городов, разработка планов обеспечения энергетическими ресурсами отраслей промышленности, оценка сценария развития высшего образования, определение приоритетных направлений научных исследований и др. МАИ не предписывает лицу, принимающему решение (ЛПР), какого-либо «правильного» решения, а позволяет ему в интерактивном режиме найти такой вариант (альтернативу), который наилучшим образом согласуется с его пониманием сути проблемы и требованиями к ее решению [7]. .4 Обзор и выбор языка C# C# - объектно-ориентированный язык программирования. Разработан в 1998 - 2001 годах группой инженеров под руководством Андерса Хейлсберга в компании Microsoft как язык разработки приложений для платформы Microsoft .NET Framework. C# относится к семье языков с C-подобным синтаксисом, из них его синтаксис наиболее близок к C++ и Java. Язык имеет статическую типизацию, поддерживает полиморфизм, перегрузку операторов (в том числе операторов явного и неявного приведения типа), делегаты, атрибуты, события, свойства, обобщённые типы и методы, итераторы, анонимные функции с поддержкой замыканий, |