Заказать работу


Тип работы:
Предмет:
Язык работы:


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

Работа №35061
Тип работыДипломные работы
Предметматематика
Объем работы78
Год сдачи2018
Стоимость4900 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 8
Не подходит работа?

Узнай цену на написание
Введение 3
Глава 1. Теоретические основы проведенной работы 6
1.1 Метод штрафных функций 6
1.2 Вариант метода штрафов с аппроксимацией надграфиков
вспомогательных функций 7
1.1.1 Постановка задачи Ошибка! Закладка не определена.
1.1.2 Описание метода Ошибка! Закладка не определена.
Глава 2 Практическая реализация методов 10
2.1 Работа с программой 10
Глава 3 Численные эксперименты 15
Заключение 20
Список использованной литературы 21
Приложение
Задачи оптимизационного типа встречаются на практике очень часто. Принятие практически каждого решения в экономике и промышленности требует решения такой задачи: для формирования графика загрузки производства необходимо решение задачи минимизации производственных простоев, для решений о конфигурации цепочки поставок, в том числе о расположении складов и способов доставки грузов необходимо решение задачи минимизации логистических затрат, принятие решения о собственном или контрактном производстве требует оптимизации операционных и инвестиционных затрат. Актуальны задачи оптимизации и в технике: к примеру, выбор оптимальной траектории полета в авиации, конструкций механизмов и зданий, формирование конфигурации производственных процессов невозможны без решения задач оптимизации.
При этом многие возникающие на практике задачи могут быть поставлены в виде задач выпуклого программирования или сведены к ним. Таким образом, решение таких задач чрезвычайно актуально, а методы их решения активно разрабатываются и исследуются.
На сегодняшний день существует большое число методов решения указанных задач. К классическим методам можно отнести градиентный метод, метод проекции градиента, координатных спусков, Ньютоновский метод, метод штрафных функций и прочие.
Однако далеко не все из них удобны для практического применения. Поэтому численное исследование новых легко реализуемых на практике алгоритмов условной минимизации остаются актуальными.
Классическая постановка задачи выпуклого программирования следующая:
Пусть решается задача
min{/(x) :х GD}
где D - выпуклое ограниченное замкнутое множество из Rn, а f - определённая в Rn выпуклая функция.
Один из классов методов решения этой задачи составляют методы внешних штрафных функций. Они характерны тем, что сводят исходную задачу выпуклого программирования к последовательному решению задач минимизации некоторых вспомогательных функций на множестве D0, содержащем D. При этом вспомогательные функции на каждом шаге выбираются таким образом, чтобы они мало отличались от f на множестве D и быстро возрастали на множестве D0.
В одной из работ научного руководителя [1] был предложен следующий вариант метода штрафных функций. На каждом шаге метода надграфик вспомогательной функции, построенной на основе внешнего штрафа, и область ограничений исходной задачи погружаются в некоторые многогранные множества. Путем решения задачи линейного программирования (где эти погружающие множества выступают в роли ограничений) находится итерационная точка. На следующем шаге вспомогательная функция изменяется за счет штрафного коэффициента, а аппроксимирующее её надграфик множество строится на основе предыдущего погружающего множества отсечением от него найденной итерационной точки. Такая модификация отличается от классического метода внешних штрафов тем, что не требует на каждой итерации решения задачи минимизации вспомогательной функции.
Данная работа посвящена численному исследованию этого нового метода и сравнению его с классическим методам штрафов. Для этого оба метода были реализованы программно с использованием языка C#. Программный комплекс для решения задачи был проверен на работоспособность на тестовых задачах. С использованием программного комплекса была проведена серия экспериментов на тестовых примерах различной размерности. Каждая из задач решалась обоими методами с одинаковой точностью, и сравнивалось общее время решения задач. Эксперименты выявили преимущество (по времени решения задач) исследуемого варианта метода штрафов перед известным классическим методом на задачах достаточно высокой размерности.
Во время выполнения работы были достигнуты следующие результаты:
1. Были изучены известные методы решения задачи.
2. Был изучен новый вариант метода внешних штрафных функций с
аппроксимацией надграфиков вспомогательных функций
3. Данный вариант метода штрафов был программно реализован на языке C#.
4. Было протестировано некоторое количество примеров различных
размерностей.
5. На основе проведенных экспериментов были сделаны следующие выводы:
o Для задач больших размерностей исследуемый метод более
эффективен по сравнению с классическим методом штрафов, так как в
указанном случае исследуемым методом заданная точность решения
практически во всех задачах была получена за меньшее число
итераций.
o В результате решения практически всех тестовых задач исследуемым
методом полученное значение целевой функции отличались от
соответствующих оптимальных значений не более, чем на величину
0.001.
Специальная литература
1. Zabotin, K. Kazaeva Cutting-Plane Method with Embedding of Epighraphs of
Auxilliary Functions// Constructive Nonsmooth Analysis and Related Topics
(dedicated to the memory of V.F. Demyanov) (St. Petersburg, Russia, May
22-27, 2017)
2. Ф.П. Васильев Численные методы решения экстремальных задач –
Москва:Наука,1988
3. И.Я. Заботин, О.Н. Шульгина, Р.С. Яруллин. Метод отсечений и
построение на его основе смешанных алгоритмов. Учен. зап. Казан. унта. Сер. физ.-матем. науки – Т. 156, 2014. – C. 14–24.
4. Булатов В. П. Методы погружения в задачах оптимизации / В. П.
Булатов. Новосибирск : Наука, 1977. – 161 с.
II. Электронные источники
5. http://www.machinelearning.ru/wiki/index.php?title=Метод_штрафных_ф
ункций – алгоритм метода штрафных функций

Работу высылаем на протяжении 30 минут после оплаты.

Пожалуйста, укажите откуда вы узнали о сайте!




Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!



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

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


Специальная литература
1. Zabotin, K. Kazaeva Cutting-Plane Method with Embedding of Epighraphs of
Auxilliary Functions// Constructive Nonsmooth Analysis and Related Topics
(dedicated to the memory of V.F. Demyanov) (St. Petersburg, Russia, May
22-27, 2017)
2. Ф.П. Васильев Численные методы решения экстремальных задач –
Москва:Наука,1988
3. И.Я. Заботин, О.Н. Шульгина, Р.С. Яруллин. Метод отсечений и
построение на его основе смешанных алгоритмов. Учен. зап. Казан. унта. Сер. физ.-матем. науки – Т. 156, 2014. – C. 14–24.
4. Булатов В. П. Методы погружения в задачах оптимизации / В. П.
Булатов. Новосибирск : Наука, 1977. – 161 с.
II. Электронные источники
5. http://www.machinelearning.ru/wiki/index.php?title=Метод_штрафных_ф
ункций – алгоритм метода штрафных функций

Работу высылаем на протяжении 30 минут после оплаты.

Пожалуйста, укажите откуда вы узнали о сайте!



© 2008-2018 Сервис продажи готовых курсовых работ, дипломных проектов, рефератов, контрольных и прочих студенческих работ.