Методы многокритериальной оптимизации реферат

Обновлено: 04.07.2024

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

Файлы: 1 файл

Многокритериальной оптимизация(опт р).doc

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

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

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

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

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

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

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

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

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

В многокритериальной задаче оптимизации сравнение решений по предпочтительности осуществляется не непосредственно, а при помощи заданных на X числовых функций f1, f2, … fm, называемых критериями.

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

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

Вложенные файлы: 1 файл

Пояснительная записка.docx

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Можно ли скачать документ с работой

Да, скачать документ можно бесплатно, без регистрации перейдя по ссылке:

Каждый человек время от времени оказывается в ситуации, когда достижение некоторого результата может быть осуществлено не единственным способом. В таких случаях приходится отыскивать наилучший способ. Однако в различных ситуациях наилучшими могут быть совершенно разные решения. Все зависит от выбранного или заданного критерия. На практике оказывается, что в большинстве случаев понятие "наилучший" может быть выражено количественными критериями – минимум затрат, минимум времени, максимум прибыли и т.д. Поэтому возможна постановка математических задач отыскания оптимального (optimum – наилучший) результата, так как принципиальных различий в отыскании наименьшего или наибольшего значения нет. Задачи на отыскание оптимального решения называются задачами оптимизации. Оптимальный результат, как правило, находится не сразу, а в результате процесса, называемого процессом оптимизации. Применяемые в процессе оптимизации методы получили название методов оптимизации. Чтобы решить практическую задачу надо перевести ее на математический язык, то есть составить ее математическую модель[1].
Математическая модель представляет собой стройную и глубокую совокупность знаний о математических моделях со своими проблемами, с собственными путями развития, обусловленными внутренними и внешними причинами и задачами. Математика дает удобные и плодотворные способы описания самых разнообразных явлений реального мира и тем самым выполняет в этом смысле функцию языка. Эту роль математики прекрасно осознавал Галилей, сказавший: "Философия написана в грандиозной книге – Вселенной, которая открыта нашему пристальному взгляду. Но понять эту книгу может лишь тот, кто научился понимать ее язык и знаки, которыми она изложена. Написана же она на языке математики".
Итак, математика – это область человеческого знания, в которой изучаются математические модели.
Часто в математической модели требуется найти наибольшее или наименьшее значение некоторой функции на некотором множестве, то есть решить задачу оптимизации. Методов решения задач оптимизации достаточно много. Некоторые из них рассматривались при отыскании экстремальных значений функций одной и многих вещественных переменных. Кроме точных методов широко используются и приближенные, например, метод дихотомии и т.д.
Знание методов нахождения оптимального решения позволяет инженеру и офицеру выбирать наиболее эффективные и самые экономичные способы эксплуатации и ремонта машин, находить оптимальные решения тактических задач.
Целью данной курсовой работы является разработка программного комплекса, который будет осуществлять выбор пары станков, удовлетворяющих ограничениям и являются оптимальным выбором для предприятия. Выбор осуществляется при помощи однокритериальной и многокритериальной оптимизации.

1 АНАЛИТИЧЕСКИЙ ОБЗОР ЛИТЕРАТУРЫ В ОБЛАСТИ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

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

Оптимизация в широком смысле слова находит применение в науке, технике и в любой другой области человеческой деятельности.
Оптимизация – целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев – невозможно. Особенно большие трудности возникали при решении задач оптимизации процессов в химической технологии из–за большого числа параметров и их сложной взаимосвязи между собой. При наличии ЭВМ задача заметно упрощается [2].
Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:
– количество продукции – расход сырья"
–количество продукции – качество продукции"
Выбор компромиссного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.
При постановке задачи оптимизации необходимо наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого.
Типичный пример неправильной постановки задачи оптимизации: "получить максимальную производительность при минимальной себестоимости".
Ошибка заключается в том, что ставится задача поиска оптимума 2–х величин, противоречащих друг другу по своей сути.
Правильная постановка задачи могла быть следующая:
– получить максимальную производительность при заданной себестоимости;
– получить минимальную себестоимость при заданной производительности;
В первом случае критерий оптимизации – производительность а во втором – себестоимость.
Так же при постановке задачи оптимизации нужны:
– наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта. Объект должен обладать определенными степенями свободы – управляющими воздействиями.
– возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.
– учет ограничений.
Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод ). Оптимизируемый вариант работы объекта должен оцениваться какой–то количественной мерой–критерием оптимальности.
Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.
На основании выбранного критерия оптимальности составляется целевая функция, представляющая собой зависимость критерия оптимальности от параметров, влияющих на ее значение.
Вид критерия оптимальности или целевой функции определяется конкретной задачей оптимизации.
Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.
Наиболее общей постановкой оптимальной задачи является выражение критерия оптимальности в виде экономической оценки (производительность, себестоимость продукции, прибыль, рентабельность).Однако в частных задачах оптимизации, когда объект является частью технологического процесса, не всегда удается или не всегда целесообразно выделять прямой экономический показатель, который бы полностью характеризовал эффективность работы рассматриваемого объекта. В таких случаях критерием оптимальности может служить технологическая характеристика, косвенно оценивающая экономичность работы агрегата (время контакта, выход продукта, степень превращения, температура). Например устанавливается оптимальный температурный профиль, длительность цикла – "реакция – регенерация". Но в любом случае любой критерий оптимальности имеет экономическую природу [3].
Критерий оптимальности должен иметь ясный физический смысл ,отражать наиболее существенные стороны процесса , должен иметь количественную оценку.
При этом всякое изменение значений управляющих параметров двояко сказывается на величине R:
– прямо, так как управляющие параметры непосредственно входят в выражение критерия оптимизации;
– косвенно – через изменение выходных параметров процесса, которые зависят от управляющих.
Как правило, для конкретных задач оптимизации химических производств критерий оптимальности не может быть записан в виде аналитического выражения.
В принципе, для оптимизации вместо математической модели можно использовать и сам объект, однако оптимизация опытным путем имеет ряд существенных недостатков:
– необходим реальный объект;
– необходимо изменять технологический режим в значительных пределах, что не всегда возможно;
– длительность испытаний и сложность обработки данных. Наличие математической модели (при условии, что она достаточно надежно описывает процесс) позволяет значительно проще решить задачу оптимизации аналитическим либо численным методами.
Итак, для решения задачи оптимизации необходимо:
– составить математическую модель объекта оптимизации,
– выбрать критерий оптимальности и составить целевую функцию,
– установить возможные ограничения, которые должны накладываться на переменные,
– выбрать метод оптимизации, который позволит найти экстремальные значения искомых величин.
Принято различать задачи статической оптимизации для процессов, протекающих в установившихся режимах, и задачи динамической оптимизации.
В первом случае решаются вопросы создания и реализации оптимальной модели процесса, во втором – задачи создания и реализации системы оптимального управления процессом при неустановившихся режимах эксплуатации.
Если требуется определить экстремум целевой функции без задания условий на какие–либо другие величины, то такая оптимизация называется безусловной. Такие критерии обычно используются при решении частных задач оптимизации (например, определение максимальной концентрации целевого продукта, оптимального времени пребывания реакционной смеси в аппарате и т.п.)[4].
Если необходимо установить экстремум целевой функции при некоторых условиях, которые накладываются на ряд других величин (например, определение максимальной производительности при заданной себестоимости, определение оптимальной температуры при ограничениях по термостойкости катализатора и др.), то такая оптимизация называется условной.
Процедура решения задачи оптимизации обязательно включает, помимо выбора управляющих параметров, еще и установление ограничений на эти параметры.
Ограничения могут накладываться как по технологическим, так и по экономическим соображениям.
В зависимости от управляющих параметров различают следующие задачи:
– оптимизация при одной управляющей переменной – одномерная оптимизация,
– оптимизация при нескольких управляющих переменных – многомерная оптимизация,
– оптимизация при неопределённости данных,
– оптимизация с непрерывными, дискретными и смешанным типом значений управляющих воздействий.
В зависимости от критерия оптимизации различают:
– с одним критерием оптимизации – критерий оптимальности единственный.
– со многими критериями. Для решения задач со многими критериями используются специальные методы оптимизации.

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

2 МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ, ЛЕЖАЩИЕ В ОСНОВЕ РАЗРАБОТКИ

2.1 Метод полного перебора

Рисунок 2.1  Схема алгоритма перебора
2.2 Метод Парето

В. Парето открыл эффект концентрированного напряжения. В данном случае имеется в виду, что концентрация на жизненно важной деятельности больше всего влияет на достижение желаемых результатов. Отсюда вытекает правило 20/80: концентрация 20 % времени на наиболее важных проблемах может привести к получению 80% результатов. Остальные 80% времени обеспечивают лишь оставшиеся 20% результатов.
Алгоритм нахождения множества Парето:
 принять P(Y)=Y, i=1, j=2. Создаётся текущее множество Паретооптимальных векторов, которое в начале совпадает с множеством Y.
 проверить выполнение неравенства. Если да, то перейти к п.3. Если нет, то перейти к п.5.
 Удалить из текущего множества P(Y) вектор, так как он не является Паретооптимальным. Перейти к п.4.
 Проверить выполнение неравенства j Список, содержащий информацию о станках первого типа
machineTwo List Список, содержащий информацию о станках второго типа
machineCounter int Счетчик станков

Таблица 4.3 – Описание элементов класса Machine.cs
Название Тип Описание
_name string Наименование
_perfomance int Производительность
_price int Стоимость
_energy double Энергоэффективность
_service string обслуживание
_reliability int Надежность
_convenience String Удобство
_serviceMark Double Обслуживание по шкале

Таблица 4.4 – Описание элементов класса Rang.cs
Название Тип Описание
FindAdditional double Метод для нахождения суммы баллов
FindAlternativeAddition double Метод для нахождение суммы альтернатив
RangMethod List Метод Ранга
weight List Список весов
alterList List Список сумм альтернатив

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

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

Рисунок 4.1 – Главное окно программы

Рисунок 4.2 – Таблица с данными по станку

Ниже, под таблицами с исходными данными по станкам располагается таблица с оценками экспертов (рисунок 4.3).

Рисунок 4.3 – Таблица с оценками экспертов

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

Рисунок 4.4 – Редактирование таблицы

Рисунок 4.6 – Успешное выполнение расчета

Рисунок 4.7 – Результаты работы программы

4.3 Верификация работы программы
Исходя из поставленной задачи данной курсовой работы, нам необходимо произвести однокритериальную оптимизацию с помощью полного перебора по заданному критерию, в нашем случае это стоимость. Для того чтобы проверить правильность расчета программой лучшей пары станков по однокритериальной оптимизации необходимо так же учесть ограничения которые обусловлены заданием, которое представлено в пункте 3.1.
Всего возможно 25 альтернатив, т.к. имеются 5 станков первого типа и 5 станков второго типа. После произведения ручного расчета на прохождение по ограничениям получаем следующие данные:
ST11 и ST21: стоимость = 994;
ST11 и ST22: стоимость = 915;
ST11 и ST23: стоимость = 846;
ST11 и ST24: стоимость превышает лимит в 1000 млн. рублей;
ST11 и ST25: стоимость = 798;
ST12 и ST21: стоимость =464;
ST12 и ST22: стоимость =385;
ST12 и ST23: стоимость =310;
ST12 и ST24: стоимость =810;
ST12 и ST25: стоимость =268;
ST13 и ST21: стоимость =674;
ST13 и ST22: стоимость =595;
ST13 и ST23: стоимость =520;
ST13 и ST24: стоимость превышает лимит в 1000 млн. рублей;
ST13 и ST25: стоимость =478;
ST14 и ST21: стоимость =804;
ST14 и ST22: стоимость =725;
ST14 и ST23: стоимость =650;
ST14 и ST24: стоимость превышает лимит в 1000 млн. рублей;
ST14 и ST25: стоимость =608;
ST15 и ST21: стоимость =611;
ST15 и ST22: стоимость =532;
ST15 и ST23: стоимость =457;
ST15 и ST24: стоимость =957;
ST15 и ST25: стоимость =415.
Очевидно, что лучшей парой по производительности является пара ST12 и ST25. Как видно на рисунке 4.9 результаты работы программы сходятся с результатами ручного расчета. Из этого следует, что программа работает верно.

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

Содержание

Постановка задачи многокритериальной оптимизации 4

Методы многокритериальной оптимизации 4

Принцип справедливого компромисса 4

Принцип приближения по всем локальным критериям к идеальному решению 6

Метод квазиоптимизации локальных критериев (метод последовательных уступок) 8

Метод свертывания векторного критерия в суперкритерий 11

Принцип оптимальности по Парето 12

Список литературы 15

Работа содержит 1 файл

реферат 1.docx

«Национальный исследовательский университет

Факультет менеджмента

Отделение логистики

Реферат на тему:

Студент группы 720л,

Постановка задачи многокритериальной оптимизации 4

Методы многокритериальной оптимизации 4

Принцип справедливого компромисса 4

Принцип приближения по всем локальным критериям к идеальному решению 6

Метод квазиоптимизации локальных критериев (метод последовательных уступок) 8

Метод свертывания векторного критерия в суперкритерий 11

Принцип оптимальности по Парето 12

Список литературы 15

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

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

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

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

Оптимизация по Парето;
Лексиминная оптимизация;
Оптимизация по приоритету критериев (лексикографическая оптимизация).

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

Задача многокритериального математического программирования имеет вид:

X – множество допустимых значений переменных х;
k – число целевых функций (критериев);
Fi – значение i-го критерия (целевой функции),
“max” – означает, что данный критерий нужно максимизировать.

Принцип справедливого компромисса

Пусть все локальные критерии, образующие вектор эффективности, имеют одинаковую важность.

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

Этому принципу можно дать следующую математическую интерпретацию. Пусть в области компромиссов Гх даны два решения х’ и х’’, качество которых оценивается критериями F1(х) и F2(х). Решение х' превосходит решение х’’ по критерию F1, но уступает ему по критерию F2. Необходимо сравнить эти решения и выбрать наилучшие на основе принципа справедливого компромисса.
Для сравнения этих решений на основе принципа справедливого компромисса введем меру относительного снижения качества решения по каждому из критериев – цену уступки x:

где и — абсолютные снижения уровня критериев при переходе от решения х' к решению х'' (для критерия F1) и при обратном переходе (для критерия F2).

Если относительное снижение критерия F1 больше, чем критерия F2, то следует отдать предпочтение решению х'. Это следует из сравнения цены уступки по каждому критерию.

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

Шаг 0. Выбираем х' и х’’є Dx.
Шаг 1. Вычисляем по формулам (3.1) х1 и х2.
Шаг 2. Если х1>х2, то выбираем х', если х1 (3.3)

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

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

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

Принцип приближения по всем локальным критериям к идеальному решению

В основу данного подхода положена идея приближения по всем критериям.

Пусть дана задача многокритериального программирования

и заданы граничные условия
(3.12)
(3.13)
x1>=0, x2>=0, …, xn>=0. (3.14)

Среди решений системы (3.11) – (3.14) требуется отыскать такое значение вектора х*(х*1, … , х*n), при котором локальные критерии примут по возможности максимальное (минимальное) значение одновременно.

Рассмотрим каждую отдельную функцию fi(x) и допустим, что для каждого фиксированного i (i=1,m) решена задача максимизации. Пусть соответствующие оптимальные планы характеризуются векторами

xoi(xo1, xo2,…, xon), i=1,m (3.15)

На этих оптимальных планах определим значения критериев соответственно

Foi=(Fi(xo1), Fi(xo2),…, Fi(xon)) (3.16)

Естественно, что векторы (3.15), определяющие векторы точки в пространстве переменных (x1, x2,…, xn)є , будут разными: некоторые из них могут совпадать друг с другом.

Рассмотрим вектор F(х) с компонентами F(x)|Foi из (3.15) и составим квадрат евклидовой нормы

вектора F(x) - Fo, определенного для всех xє .

Заметим, что Fo будет представлять собой единичный вектор в пространстве вектора F(x). Назовем его идеальным значением вектора F(x). Поставленная задача теперь сформулируется так: дана система целевых функций (3.11) и даны условия задачи (3.12) – (3.14). Требуется определить точку xє , в которой функция R(x) достигает минимума.

Таким образом, отыскание векторно-оптимального плана xє в данной задаче сведено к оптимизации выражения (3.17) на решениях системы линейных неравенств (3.12) – (3.14). Поскольку выражение (3.17) представляет собой квадратичную функцию переменных х1, …, хп, то задача отыскания векторно-оптимального плана свелась к задаче выпуклого программирования:

Задана выпуклая функция R(x), определенная на множестве xє . Требуется отыскать точку xє , обеспечивающую выполнение условия R(x*) = minR(x), xє .

Таким образом, алгоритм решения задачи (3.11) – (3.14) состоит из двух основных этапов:
этап 1: maxFi(x), i=1, m;
этап 2: min R(x).

Метод квазиоптимизации локальных критериев (метод последовательных уступок)

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

Вначале производится качественный анализ относительной важности критериев; на основании такого анализа критерии располагаются и нумеруются в порядке убывания важности, так что главным считается критерий F1, менее важен F2, затем следуют остальные локальные критерии F3, F4. ., Fm. Максимизируется первый по важности критерий F1 и определяется его наибольшее значение M1. Затем назначается допустимое снижение (уступка) d1>=0 критерия F1. Определим новую допустимую область X(1), как подобласть X вида

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

После этого находим наибольшее значение М2 второго критерия F2 на множестве X(1) , т. е. при условии, что значение первого критерия должно быть не меньше, чем M1-d1. Снова назначается значение уступки d2>=0, но уже по второму критерию, которое вместе с первым используется при нахождении условного максимума третьего критерия, и т. д. Наконец, максимизируется последний по важности критерий Fm при условии, что значение каждого критерия Fr из m—1 предыдущих должно быть не меньше соответствующей величины Мr - dг; получаемые стратегии считаются оптимальными:

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

1) найти M1= supF1(x), xєX;
2) найти M2= supF2(x), xєX; (3.19)
…
m) найти Mm= supFm(x), xєX;

Если критерий Fm на множестве стратегий, удовлетворяющих ограничениям задачи m) из (3.19) не достигает своего наибольшего значения Мm, то решением многокритериальной задачи считают максимизирующую последовательность из последовательности множеств

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

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

Шаг 1. Пусть х01 — решение задачи (3.19)
max Fl(x), xєX
Шаг 2. Пусть xok - решение задачи
max Fk(x), xєX(k-1)
где Xk определяется из (3.19).
Шаг 3. Если k

Читайте также: