Защищенная курсовая работа Парето (Неизвестные варианты курсовых работ)

Московский государственный техническийуниверситет им. Н. Э. Баумана.Курсовая работапо дисциплине:«МЕТОДЫ ОПТИМИЗАЦИИ И ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ »по теме:«МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ»Выполнил:студент 3-го курса, гр. АК3-61Ягубов Роман БорисовичПроверил:Бушуев Александр Юрьевичг. МоскваОглавлениеВведение ..................................................................................................................................................... 2История .................................................................................................................................................... 2Практика ..................................................................................................................................................

3Актуальность ........................................................................................................................................... 3Концептуальная постановка задачи ........................................................................................................... 3Математическая постановка задачи ........................................................................................................... 3Методы многокритериальной оптимизации.............................................................................................. 3Метод взвешенных сумм с точечным оцениванием весов ....................................................................

3Принцип справедливого компромисса ................................................................................................... 4Принцип приближения по всем локальным критериям......................................................................... 4Метод свертывания векторного критерия в суперкритерий .................................................................. 4Метод Парето для решения задачи ........................................................................................................... 4Понятие Парето-оптимального множества. ...........................................................................................

4Построения множества Парето ............................................................................................................... 4Аксиомы, являющиеся основой принципа Парето ................................................................................ 5Алгоритм решения задачи .......................................................................................................................... 6Результат вычислительного эксперимента ................................................................................................

6Аналитическое решение задачи .............................................................................................................. 6Графическое представление множества Парето .................................................................................... 7Сравнение результатов с точным решением .......................................................................................... 8Выводы по работе ....................................................................................................................................... 8Приложение ................................................................................................................................................

9Список используемой литературы ........................................................................................................... 10ВведениеПри рассмотрении различных задач из жизни мы всегда имеем дело с большим количествоминформации. Бывает не всегда очевиден выбор: профессии, квартиры, машины, девушки и т. д.Иногда важными являются многие качественные факторы. Получается неопределенность в исходнойинформации и последствий нашего выбора.ИсторияМетоды решения задач математического программирования с одним критерием интенсивноразрабатывались последние полвека. Изучение данных методов отражало самый ранний и простойэтап в развитии математического программирования. Жизнь оказалась значительно сложнее.

Ведь,мы неотъемлемо вступили в 21 век (информационный век), становится ясно, что практически любаясерьезная реальная задача может иметь больше одного критерия. Лица, принимающие решения(ЛПР), в значительно большей степени, чем когда бы то ни было, ощущают необходимостьоценивать альтернативные решения с точки зрения нескольких критериев. Окончательный выборвсегда остаётся за ними. [1]2ПрактикаИсследования различных задач показывают, что они могут быть многокритериальными. Так,часто встречающееся выражение «достичь максимальной прибыли при наименьших затратах» ужеозначает принятие решения при двух критериях. Оценка задач может производится на основе болеедесятка критериев.

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

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

Его интересы субъективны и служат основой соизмерения различныхчастных критериев.Существуют различные способы вовлечения человека в процесс принятия решений, на основекоторых строятся различные многокритериальной методы принятия решений. Эти методы условноразбивают на три большие группы:1. основанные на выявлении предпочтений ЛПР и построения единственного критерия качестварешения до рассмотрения конкретных альтернатив;2.

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

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

При этом каждый критерий умножается на соответствующий ему весовойкоэффициент (коэффициент важности).(4)При этом возникают трудности с правильным подбором весовых коэффициентов .Существуют различные способы выбора коэффициентов . Одним из них являетсяназначение в зависимости от относительной важности критериев. [4]Метод Парето для решения задачиМетод для демонстрации состояния системы, при котором значение каждого частногопоказателя, характеризующего систему, не может быть улучшено без ухудшения других.Таким образом, по словам самого Парето: «Всякое изменение, которое никому не приноситубытков, а некоторым людям приносит пользу (по их собственной оценке), является улучшением».Значит, признаётся право на все изменения, которые не приносят никому дополнительного вреда.Понятие Парето-оптимального множества.Определение: альтернатива А называется доминирующей по отношению к альтернативе В,если по всем критериям оценки альтернативы А не хуже, чем альтернативы В, а хотя бы по одномукритерию оценка А лучше.

Альтернатива В при этом называется доминируемой.(5),Если для некоторой точкине существует более предпочтительной по Парето точки,т.е. такой точки , что, то тогда точканазывается эффективным или Паретооптимальным решением многокритериальной задачи (относится к множеству Парето).Построения множества ПаретоПриближенное построение множества Парето относится к числу очень важных и трудныхзадач численного анализа. С расширением круга проблем, значение методов эффективного анализа4множества Парето непрерывно растёт. Увы, совсем недавно стали уделять значительное времячисленным методам построения точек множества Парето.

Рассмотрим проблемы на простыхпримерах.Случай с двумя критериями.То есть в каждой точкесоотношенияопределяют отображениемножествана и ставят в соответствие некоторую точкув плоскости критериев.Множествоносит название множества (достижимости) предельных возможностей.Множество Парето представляет собой лишь часть границы множества достижимости.Приближенное построение множества Парето сводится к последовательному решению задачматематического программирования. Опишем одну из возможных схем расчета.Фиксируем некоторые желательные значения критериев:, чтобы онипринадлежали множеству предельных возможностей.Теперь решаем две оптимизационные задачи.(6),решив эти задачи, определим точки, проведя через них прямую, получим простейшуюаппроксимацию множества Парето.Для уточнения аппроксимации решаем следующие задачи:(7),[5]находим еще две точки, принадлежащие этому множеству.Через точки проводим ломаную, которая будет следующим приближением.