Помощь студентам в учебе
РЕШЕНИЕ МНОГОКРИТЕРИАЛЬНЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ НА ОСНОВЕ МИНИМАКСНОГО КРИТЕРИЯ
|
Введение 3
1. Теоретические основы многокритериальных задач оптимизации и основные подходы к их
решению 6
1.1 Постановка и формулировка задачи многокритериальной оптимизации 6
1.2. Классические методы решения задачи многокритериальной оптимизации 7
1.2.1 Метод последовательных уступок 7
1.2.2 Метод главного критерия 9
1.2.3 Метод свертки критериев 10
1.2.4 Метод на основе минимаксного критерия 11
2. Методы отсечений для задач выпуклого программирования 13
2.1 Метод секущей гиперплоскости 15
3. Разработка программного продукта, реазлизующего метод решения многокриетриальных
оптимизационных задач на основе минимаксного криетрия 17
3.1 Алгоритм решения многокритериальных оптимизационных задач 17
3.2 Практическая реализация исследуемого метода 19
3.2.1 Описание работы и графического интерфейса программы 19
3.2.2. Решение конкретных задач при помощи разработанной программы 22
3.3 Практическое сравнение исследуемого метода с методом линейной свертки 31
Заключение 35
Список использованных источников 39
Приложение 43
1. Теоретические основы многокритериальных задач оптимизации и основные подходы к их
решению 6
1.1 Постановка и формулировка задачи многокритериальной оптимизации 6
1.2. Классические методы решения задачи многокритериальной оптимизации 7
1.2.1 Метод последовательных уступок 7
1.2.2 Метод главного критерия 9
1.2.3 Метод свертки критериев 10
1.2.4 Метод на основе минимаксного критерия 11
2. Методы отсечений для задач выпуклого программирования 13
2.1 Метод секущей гиперплоскости 15
3. Разработка программного продукта, реазлизующего метод решения многокриетриальных
оптимизационных задач на основе минимаксного криетрия 17
3.1 Алгоритм решения многокритериальных оптимизационных задач 17
3.2 Практическая реализация исследуемого метода 19
3.2.1 Описание работы и графического интерфейса программы 19
3.2.2. Решение конкретных задач при помощи разработанной программы 22
3.3 Практическое сравнение исследуемого метода с методом линейной свертки 31
Заключение 35
Список использованных источников 39
Приложение 43
В настоящее время, почти во всех областях человеческой деятельности, это может быть, как экономика, так и сфера космических технологий, человек в процессе принятия решений сталкивается с необходимостью делать выбор на основании множественных целей, некоторые из них в свою очередь могут оказаться противоречивыми.
Бывают ситуации, когда человек полагается только на собственный опыт или использует интуитивный подход, но в большинстве сфер жизни человека нельзя опираться только на собственные ощущения и суждения, и принимать решения без соответствующего анализа . Для получения ответов, в таких ситуациях, требуется подробно изучить вопрос и путем вычислений найти оптимальную альтернативу.
По причине того, как человек старается рационализировать процессы для эффективной работы в различных сферах, несомненный теоретический и практический интерес представляют вопросы изучения методов оптимизации. И такое внимание со стороны исследователей вполне обосновано, ведь приводя систему в состояние, в котором все поставленные цели были учтены и достигнута максимальная полезность, можно добиться больших результатов с меньшими потерями, к примеру, оптимизировав процесс производства, можно сократить отходы, что в свою очередь может сказаться на уменьшение затрат на ресурсы.
При совершении выбора, который позволит достичь целей, наиболее близко соответствующие поставленным изначально, необходимо иметь набор альтернатив, по которым будет совершаться поиск наилучшего решения. Следует учитывать, что многие альтернативы должны быть максимально полными и репрезентативными с учетом всех возможных решений. Также не стоит забывать о критерии оценки их качества, позволяющий непосредственно выбирать предпочтительные альтернативы из исходного набора [11,16].
Существенно облегчает нахождение оптимального решения задача, предполагающая достижение единственной цели, причем эта цель может быть записана в виде скалярной функции, которая выступит в роли критерия качества выбора. Предполагается, что известна область допустимых значений, входящих в целевую функцию, это множество всех возможных точек оптимизации, которые удовлетворяют накладываемым ограничениям. В такой ситуации, когда в задаче преследуется одна цель, эта задача выбора наилучшего решения может быть соответствующим образом преобразована и описана моделью математического
программирования. Задачам математического программирования
посвящена многочисленная литература (см., напр., [13,14,17,35]).
Сложности в принятии решений начинают возникать, когда в процессе поиска оптимального выбора, следует учитывать несколько целей. Такие задачи могут быть сформулированы как многокритериальные задачи оптимизации. Для решения таких задач, используются определенные подходы, применяющие более широкие и гибкие методы, которые учитывают противоречивый характер критериев при вычислении оптимальных, или компромиссных, решений.
Актуальность темы выпускной работы заключается в том, что ни одна экономическая проблема не ограничивается одним критерием, по этой причине возникают трудности в принятии решений, связанные с учетом множества критериев качества и ограниченности ресурсов.
Целью работы является численное исследование одного метода решения многокритериальных задач оптимизации, использующего обобщенный минимаксный критерий. Требуется программно реализовать исследуемый метод, используя при этом для решения однокритериальной задачи один из методов отсечений. Кроме того, планируется сравнить на одних и тех же тестовых примерах исследуемый метод с одним из классических методов многокритериальной оптимизации, а именно, методом свертки критериев.
Сформулированная цель предопределила совокупность решаемых задач:
— провести сравнительный анализ существующих методов многокритериальной оптимизации;
— исследовать методы отсечений с аппроксимацией надграфика функции цели;
— создать программный продукт, реализующий исследуемый метод решения оптимизационных многокритериальных задач (с использованием вспомогательного метода отсечений с аппроксимацией надграфика функции цели) для случая, когда область ограничений задачи является многогранником.
Бывают ситуации, когда человек полагается только на собственный опыт или использует интуитивный подход, но в большинстве сфер жизни человека нельзя опираться только на собственные ощущения и суждения, и принимать решения без соответствующего анализа . Для получения ответов, в таких ситуациях, требуется подробно изучить вопрос и путем вычислений найти оптимальную альтернативу.
По причине того, как человек старается рационализировать процессы для эффективной работы в различных сферах, несомненный теоретический и практический интерес представляют вопросы изучения методов оптимизации. И такое внимание со стороны исследователей вполне обосновано, ведь приводя систему в состояние, в котором все поставленные цели были учтены и достигнута максимальная полезность, можно добиться больших результатов с меньшими потерями, к примеру, оптимизировав процесс производства, можно сократить отходы, что в свою очередь может сказаться на уменьшение затрат на ресурсы.
При совершении выбора, который позволит достичь целей, наиболее близко соответствующие поставленным изначально, необходимо иметь набор альтернатив, по которым будет совершаться поиск наилучшего решения. Следует учитывать, что многие альтернативы должны быть максимально полными и репрезентативными с учетом всех возможных решений. Также не стоит забывать о критерии оценки их качества, позволяющий непосредственно выбирать предпочтительные альтернативы из исходного набора [11,16].
Существенно облегчает нахождение оптимального решения задача, предполагающая достижение единственной цели, причем эта цель может быть записана в виде скалярной функции, которая выступит в роли критерия качества выбора. Предполагается, что известна область допустимых значений, входящих в целевую функцию, это множество всех возможных точек оптимизации, которые удовлетворяют накладываемым ограничениям. В такой ситуации, когда в задаче преследуется одна цель, эта задача выбора наилучшего решения может быть соответствующим образом преобразована и описана моделью математического
программирования. Задачам математического программирования
посвящена многочисленная литература (см., напр., [13,14,17,35]).
Сложности в принятии решений начинают возникать, когда в процессе поиска оптимального выбора, следует учитывать несколько целей. Такие задачи могут быть сформулированы как многокритериальные задачи оптимизации. Для решения таких задач, используются определенные подходы, применяющие более широкие и гибкие методы, которые учитывают противоречивый характер критериев при вычислении оптимальных, или компромиссных, решений.
Актуальность темы выпускной работы заключается в том, что ни одна экономическая проблема не ограничивается одним критерием, по этой причине возникают трудности в принятии решений, связанные с учетом множества критериев качества и ограниченности ресурсов.
Целью работы является численное исследование одного метода решения многокритериальных задач оптимизации, использующего обобщенный минимаксный критерий. Требуется программно реализовать исследуемый метод, используя при этом для решения однокритериальной задачи один из методов отсечений. Кроме того, планируется сравнить на одних и тех же тестовых примерах исследуемый метод с одним из классических методов многокритериальной оптимизации, а именно, методом свертки критериев.
Сформулированная цель предопределила совокупность решаемых задач:
— провести сравнительный анализ существующих методов многокритериальной оптимизации;
— исследовать методы отсечений с аппроксимацией надграфика функции цели;
— создать программный продукт, реализующий исследуемый метод решения оптимизационных многокритериальных задач (с использованием вспомогательного метода отсечений с аппроксимацией надграфика функции цели) для случая, когда область ограничений задачи является многогранником.
Многокритериальная оптимизация является очень важной сферой для исследования, поскольку затрагивает все больше областей человеческой деятельности, которые стремятся оптимизировать свои процессы. В этой
связи растет интерес к улучшению работы ранее созданных методов или же разработке новых подходов для нахождения оптимальных вариантов при принятии решений.
Целью выпускной работы являлось исследование метода решения многокритериальных задач оптимизации на основе минимаксного критерия, с использованием вспомогательного метода отсечений с аппроксимацией надграфика функции цели, после чего требовалось программно реализовать исследуемый метод.
В ходе дипломного проекта были изучены классические методы многокритериальной оптимизации, а также методы отсечений для решения задач выпуклого программирования, проведен их анализ и выявлены имеющиеся недостатки.
На основании проделанного исследования, можно сделать следующие выводы:
• в настоящее время, чаще всего, лицо принимающее решение, сталкивается с задачами именно многокритериальной оптимизации; такие задачи требуют более гибких форм в используемых подходах, так как в процессе принятия решений требуется учитывать более одного критерия оптимальности;
• частные критерии находятся в разных отношениях друг с другом, т.е. могут иметь одну или разные направленности, или быть совершенно «безразличны» другу к другу; по этой причине требуется экспертное оценивание критериев и их взаимоотношений;
• при выборе подхода следует учитывать всю имеющуюся информацию о решаемой задаче, так как не всякий метод подходит для решения произвольной многокритериальной задачи;
• метод отсечения находится на стадии разработки и совершенствования;
при реализации этого метода возникают технические и
фундаментальные сложности, в виду таких трудностей, с помощью
36
данного метода целесообразнее будет решать относительно небольшие задачи, имеющие десятки функций и ограничений.
Для реализации программного продукта была выбранная среда Visual Studio и язык C#, на платформе Windows Form был разработан модуль решения задачи, обладающий интерактивными функциями работы. Приведено подробное описание компонентов и возможностей созданной программы, а также даны рекомендации по выбору некоторых параметров. Были проанализированы результаты экспериментов и сделаны выводы, доказывающие, в очередной раз, что следует с особой тщательностью подходит к выбору методов решения поставленных задач, для получения достоверных результатов.
Разработанный продукт может быть перенесен на платформу ASP.NET, что при дальнейшем развитии различных аспектов, в числе которых производительность, масштабируемость, более компактный код, позволит применять его на корпоративном уровне.
Подводя итог к проделанной работе, можно сказать о том, что несмотря на сложность поставленных задач, ставящих перед собой достижение нескольких целей, требуется находить способы их решения, для успешного функционирования составляющих структур организации. В связи с этим прибегают к многокритериальной оптимизации, правильно подобранные методы которой, позволяют найти оптимальное решение задачи. Один из таких методов был изучен и применен в ходе разработки программного продукта, позволяющего упростить решения задач с несколькими критериями. Используя современные информационные технологии и прорывы в области математического программирования, можно расширить возможности применяемых систем, с целью ускорения процессов, повышения их эффективности и результативности.
связи растет интерес к улучшению работы ранее созданных методов или же разработке новых подходов для нахождения оптимальных вариантов при принятии решений.
Целью выпускной работы являлось исследование метода решения многокритериальных задач оптимизации на основе минимаксного критерия, с использованием вспомогательного метода отсечений с аппроксимацией надграфика функции цели, после чего требовалось программно реализовать исследуемый метод.
В ходе дипломного проекта были изучены классические методы многокритериальной оптимизации, а также методы отсечений для решения задач выпуклого программирования, проведен их анализ и выявлены имеющиеся недостатки.
На основании проделанного исследования, можно сделать следующие выводы:
• в настоящее время, чаще всего, лицо принимающее решение, сталкивается с задачами именно многокритериальной оптимизации; такие задачи требуют более гибких форм в используемых подходах, так как в процессе принятия решений требуется учитывать более одного критерия оптимальности;
• частные критерии находятся в разных отношениях друг с другом, т.е. могут иметь одну или разные направленности, или быть совершенно «безразличны» другу к другу; по этой причине требуется экспертное оценивание критериев и их взаимоотношений;
• при выборе подхода следует учитывать всю имеющуюся информацию о решаемой задаче, так как не всякий метод подходит для решения произвольной многокритериальной задачи;
• метод отсечения находится на стадии разработки и совершенствования;
при реализации этого метода возникают технические и
фундаментальные сложности, в виду таких трудностей, с помощью
36
данного метода целесообразнее будет решать относительно небольшие задачи, имеющие десятки функций и ограничений.
Для реализации программного продукта была выбранная среда Visual Studio и язык C#, на платформе Windows Form был разработан модуль решения задачи, обладающий интерактивными функциями работы. Приведено подробное описание компонентов и возможностей созданной программы, а также даны рекомендации по выбору некоторых параметров. Были проанализированы результаты экспериментов и сделаны выводы, доказывающие, в очередной раз, что следует с особой тщательностью подходит к выбору методов решения поставленных задач, для получения достоверных результатов.
Разработанный продукт может быть перенесен на платформу ASP.NET, что при дальнейшем развитии различных аспектов, в числе которых производительность, масштабируемость, более компактный код, позволит применять его на корпоративном уровне.
Подводя итог к проделанной работе, можно сказать о том, что несмотря на сложность поставленных задач, ставящих перед собой достижение нескольких целей, требуется находить способы их решения, для успешного функционирования составляющих структур организации. В связи с этим прибегают к многокритериальной оптимизации, правильно подобранные методы которой, позволяют найти оптимальное решение задачи. Один из таких методов был изучен и применен в ходе разработки программного продукта, позволяющего упростить решения задач с несколькими критериями. Используя современные информационные технологии и прорывы в области математического программирования, можно расширить возможности применяемых систем, с целью ускорения процессов, повышения их эффективности и результативности.
Подобные работы
- Гиперграфовые модели и методы решения дискретных задач управления в условиях неопределенности
Диссертации (РГБ), математика. Язык работы: Русский. Цена: 470 р. Год сдачи: 2004 - ГИПЕРГРАФОВЫЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ДИСКРЕТНЫХ ЗАДАЧ УПРАВЛЕНИЯ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ
Диссертации (РГБ), физика. Язык работы: Русский. Цена: 500 р. Год сдачи: 2004 - Системный анализ
Ответы на вопросы, прочее. Язык работы: Русский. Цена: 1600 р. Год сдачи: 2022