Тема: Вариант метода штрафов с аппроксимацией надграфиков вспомогательных функций

Задачи оптимизационного типа встречаются на практике очень часто. Принятие практически каждого решения в экономике и промышленности требует решения такой задачи: для формирования графика загрузки производства необходимо решение задачи минимизации производственных простоев, для решений о конфигурации цепочки поставок, в том числе о расположении складов и способов доставки грузов необходимо решение задачи минимизации логистических затрат, принятие решения о собственном или контрактном производстве требует оптимизации операционных и инвестиционных затрат. Актуальны задачи оптимизации и в технике: к примеру, выбор оптимальной траектории полета в авиации, конструкций механизмов и зданий, формирование конфигурации производственных процессов невозможны без решения задач оптимизации.
При этом многие возникающие на практике задачи могут быть поставлены в виде задач выпуклого программирования или сведены к ним. Таким образом, решение таких задач чрезвычайно актуально, а методы их решения активно разрабатываются и исследуются.
На сегодняшний день существует большое число методов решения указанных задач. К классическим методам можно отнести градиентный метод, метод проекции градиента, координатных спусков, Ньютоновский метод, метод штрафных функций и прочие.
Однако далеко не все из них удобны для практического применения. Поэтому численное исследование новых легко реализуемых на практике алгоритмов условной минимизации остаются актуальными.
Классическая постановка задачи выпуклого программирования следующая:
Пусть решается задача
min{/(x) :х GD}
где D - выпуклое ограниченное замкнутое множество из Rn, а f - определённая в Rn выпуклая функция.
Один из классов методов решения этой задачи составляют методы внешних штрафных функций. Они характерны тем, что сводят исходную задачу выпуклого программирования к последовательному решению задач минимизации некоторых вспомогательных функций на множестве D0, содержащем D. При этом вспомогательные функции на каждом шаге выбираются таким образом, чтобы они мало отличались от f на множестве D и быстро возрастали на множестве D0.
В одной из работ научного руководителя [1] был предложен следующий вариант метода штрафных функций. На каждом шаге метода надграфик вспомогательной функции, построенной на основе внешнего штрафа, и область ограничений исходной задачи погружаются в некоторые многогранные множества. Путем решения задачи линейного программирования (где эти погружающие множества выступают в роли ограничений) находится итерационная точка. На следующем шаге вспомогательная функция изменяется за счет штрафного коэффициента, а аппроксимирующее её надграфик множество строится на основе предыдущего погружающего множества отсечением от него найденной итерационной точки. Такая модификация отличается от классического метода внешних штрафов тем, что не требует на каждой итерации решения задачи минимизации вспомогательной функции.
Данная работа посвящена численному исследованию этого нового метода и сравнению его с классическим методам штрафов. Для этого оба метода были реализованы программно с использованием языка C#. Программный комплекс для решения задачи был проверен на работоспособность на тестовых задачах. С использованием программного комплекса была проведена серия экспериментов на тестовых примерах различной размерности. Каждая из задач решалась обоими методами с одинаковой точностью, и сравнивалось общее время решения задач. Эксперименты выявили преимущество (по времени решения задач) исследуемого варианта метода штрафов перед известным классическим методом на задачах достаточно высокой размерности.
Купить

Во время выполнения работы были достигнуты следующие результаты:
1. Были изучены известные методы решения задачи.
2. Был изучен новый вариант метода внешних штрафных функций с
аппроксимацией надграфиков вспомогательных функций
3. Данный вариант метода штрафов был программно реализован на языке C#.
4. Было протестировано некоторое количество примеров различных
размерностей.
5. На основе проведенных экспериментов были сделаны следующие выводы:
o Для задач больших размерностей исследуемый метод более
эффективен по сравнению с классическим методом штрафов, так как в
указанном случае исследуемым методом заданная точность решения
практически во всех задачах была получена за меньшее число
итераций.
o В результате решения практически всех тестовых задач исследуемым
методом полученное значение целевой функции отличались от
соответствующих оптимальных значений не более, чем на величину
0.001.
Купить