Введение 3
Глава 1. Теоретическая часть 5
1.1. Метод на основе метрики в пространстве критериев 5
1.2. Симплексный метод 7
1.3. Метод внешних штрафных функций 10
1.4. Метод наискорейшего спуска 12
1.5. Метод дихотомии 13
Глава 2. Практическая часть 15
2.1. Описание работы программы 15
2.2. Численные эксперименты 17
2.3. Решение прикладной оптимизационной задачи 38
Заключение 42
Список используемой литературы 43
Приложение. Листинг программы 44
Во многих областях, от промышленного до социального сектора, лица, принимающие решения, сталкиваются с растущей необходимостью учитывать несколько критериев в процессе своей работы. К примеру, перед производителем может встать необходимость так организовать производственный процесс, чтобы получить максимальный объем выпуска продукции при минимальном браке. Часто для разрешения такого рода проблем можно составить математическую модель, представляющую собой задачу многокритериальной оптимизации. Неизвестные величины, которые подбираются в процессе решения задачи для получения оптимального решения, выбираются в качестве переменных. Они входят в целевые функции, представляющие собой рассматриваемые критерии или цели. Также вводятся ограничения на значения переменных. Например, может включаться ограничение на количество затрачиваемых ресурсов, которое не должно превышать их наличные запасы. Таким образом, ставится задача оптимизации нескольких функций на заданном допустимом множестве.
Для решения подобных задач существуют различные методы, которые находят компромиссные решения, учитывая противоречивый характер критериев и степень их важности. К основным подходам к решению многокритериальных задач относят метод последовательных уступок, метод свертки критериев, метод контрольных показателей, метод на основе метрики в пространстве критериев или, как его еще называют, метод «идеальной» точки, и др. В связи с частотой возникновения многокритериальных задач на практике исследование методов их решения по-прежнему актуально.
Данная выпускная квалификационная работа посвящена исследованию метода на основе метрики в пространстве критериев, сводящему исходную многокритериальную задачу к однокритериальной.
Целью выпускной работы является реализация программы, позволяющей находить решение многокритериальной задачи с линейными целевыми функциями и ограничениями, применяя один вариант метода на основе метрики в пространстве критериев и численное исследование этого метода. В качестве вспомогательного метода решения соответствующей однокритериальной задачи используется метод внешних штрафных функций. Для достижения поставленной цели необходимо было выполнить следующие работы:
1. Изучить подход к решению многокритериальных на основе метрики в пространстве критериев и метод внешних штрафных функций;
2. Программно реализовать исследуемый метод и спроектировать удобный пользовательский интерфейс;
3. Провести серию численных экспериментов для подтверждения работоспособности программы и проанализировать результаты;
4. Решить прикладную задачу многокритериальной оптимизации.
Для программной реализации метода используется язык C# и технология Windows Forms для создания пользовательского интерфейса.
Выпускная работа состоит из введения, двух глав, заключения, списка используемой литературы и приложения.
В первой главе содержатся теоретические основы исследуемого метода на основе метрики в пространстве критериев, выбираются и описываются подходы, которые применяются к решению вспомогательных задач, возникающих на различных этапах решения исходной задачи.
Во второй главе представлены результаты разработки программы. Показывается процесс работы и возможности пользовательского интерфейса, подтверждается работоспособность программы на серии примеров различных размерностей, решается прикладная задача многокритериальной оптимизации.
Поставленная цель выпускной квалификационной работы, программно реализовать и численно исследовать метод на основе метрики в пространстве критериев для задач с линейными целевыми функциями и ограничениями, была достигнута.
На первом этапе работы был изучен и описан подход к решению многокритериальных задач на основе метрики в пространстве критериев. Изучены методы нелинейного программирования, выбран один вариант метода внешних штрафных функций для решения однокритериальной задачи, соответствующей исходной многокритериальной задачи. Среди методов безусловной минимизации для решения вспомогательных задач на каждой итерации метода штрафных функций был выбран метод наискорейшего спуска. Полный шаг находится методом дихотомии.
На втором этапе была разработана программа на языке C#, реализующая исследуемый метод, и спроектирован интерфейс к ней. Проведены численные эксперименты для задач различных размерностей, с разными видами целевых функций и областями ограничений. Была решена одна прикладная задача производственного типа. Программа показала успешность своей работы. Решения задач получены с достаточно высокой точностью довольно быстро.
В дальнейшем для исследования метода на основе метрики в пространстве критериев можно применить иные методы условной оптимизации и сравнить эффективность их работы; также можно расширить исследование на случаи с нелинейными частными критериями и ограничениями.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
