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

ВВЕДЕНИЕ

 

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

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

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

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

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

 

1 ТЕОРЕТИЧЕСКИЕ  СВЕДЕНИЯ

 

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

 

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

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

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

Задачей принятия решений называется пара <X, ОП>, где X – множество вариантов, ОП – принцип оптимальности, дающий представление о качестве вариантов, в простейшем случае правило предпочтения вариантов. Решением задачи <X, ОП> является множество Xоп ÍX, полученное с помощью принципа оптимальности ОП.

Элементы множества X называют альтернативами или вариантами. Принцип оптимальности задаёт понятие лучших альтернатив: лучшими считают альтернативы, принадлежащие Xоп.

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

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

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

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

1) Постановка (формулировка) задачи (проблемы). На этом этапе аналитик должен трансформировать слова заказчика в четко сформулированную задачу;

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

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

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

3) Решение математической  модели задачи. Рассмотрим некоторые типы задач:

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

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

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

 

 

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

 

Классификацию задач оптимизации проводят по следующим признакам:

1) поп виду отображения функции детерминированное, вероятностное или неопределённое, что позволяет выделить  соответственно:

• задачи ПР в условиях определенности (детерминированные);
• задачи ПР в условиях риска (вероятностная неопределённость);
• задачи ПР в условиях неопределённости;

2) в зависимости от числа критериев, по которым выполняется оптимизация объекта:

• задачи ПР со скалярным критерием (однокритериальная задача);
• задачи ПР с векторным критерием (многокритериальные задачи);

3) тип системы - отображает предпочтения одного лица или коллектива:

• задачи индивидуального ПР;
• задачи группового ПР;

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

• оптимизация без ограничений;

• оптимизация при наличии ограничений (наложении ограничения на соответствующий критерий);

5) в зависимости от алгоритмов математического программирования оптимизация бывает:

•  структурной – оптимизируется структура объекта и используются дискретные алгоритмы математического программирования;
• параметрической – оптимизируются параметры (номиналы) элементов, т.е. при известной (заданной) структуре объекта подбираются параметры (номиналы) элементов таким образом, чтобы минимизировать (максимизировать) целевую функцию. Используются алгоритмы непрерывного математического программирования;
• структурно-параметрической. Используются алгоритмы дискретно-непрерывного программирования [3].

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

 

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

 

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

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

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

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

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

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

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

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