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


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


Метод отсечений Булатова

Работа №53232
Тип работыДипломные работы, ВКР
Предметматематика
Объем работы68
Год сдачи2017
Стоимость4880 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 36
Не подходит работа?

Узнай цену на написание

Введение 2
1 Методы отсечения с аппроксимацией области ограничений 4
1.1 Постановка задачи 4
1.2 Метод отсечений Булатова 6
1.3 Модифицированный метод отсечений 7
1.4 Модифицированные метод отсечений с обновлением погружающих множеств 9
2 Описание рассматриваемой модификации 11
3 Описание программ 12
3.1 Метод отсечений Булатова 13
3.2 Вариант метода отсечений Булатова 16
3.3 Модифицированный метод отсечений 18
3.4 Вариант модифицированного метода отсечений 22
4 Эксперименты 24
4.1 Метод Булатова 25
4.2 Метод Булатова с обновлением погружающих множеств .... 29
4.3 Модифицированный метод отсечений 30
4.4 Модифицированный метод отсечений с обновлением погружающих множеств 35
Заключение 38
Список литературы 40
Приложение


Задачи выпуклого программирования часто встречаются на практике, поэтому разработка HOBBIX И модификация существующих методов остается актуальной задачей.
Есть множество классов методов решения задач выпуклого программирования. Один из таких классов образуют методы отсечений, которые можно раз дел итв на 3 группы: методы отсечений с аппроксимацией надграфика целевой функции, методы отсечения с аппроксимацией области ограничений и, достаточно редко встречающаяся группа методов, использующих аппроксимацию как надграфика так и области ограничений целевой задачи.
В данной работе численно исследуются варианты метода Булатова ([1], с. 28-30) и модифицированного метода отсечений [2] в которых заложена возможности изменения от шага к шагу внутренних вспомогательных точек, участвующих в построении отсекающих плоскостей.
Метод отсечений Булатова и модифицированный метод отсечений используют при построении отсечений произвольную внутреннюю точку(-и) из допустимой области. Обычно эту точку задают на предварительном шаге метода и оставляют зафиксированной на всем протяжении решения задачи. В работе исследуется варианты указанных методов, где вспомогательные точки перемещаются в допустимой области согласно определенному правилу.
Отметим, что существенной проблемой методов отсечений является неограниченное накопление в процессе счета отсекающих плоскостей, которые формируют аппроксимирующее множество, что влечет за собой увеличение вычислительных затрат и накопление ошибок округления. В статье [3], научным руководителем работы и Р.С. Яруллиным был предложен один подход к построению методов отсечений с обновлением аппроксимирующих множеств за счет отбрасывания любого числа отсекающих плоскостей. С использованием этого подхода в упомянутых выше модифицированный метод отсечений была заложена возможность обновления погружающих множеств.
В рамках работы в среде Matlab были реализованы и отлажены программы для исследования вариантов метода отсечений Булатова и вариантов модифицированного метода отсечений.


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

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

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


В рамках работы были реализованы и исследованы четыре варианта методов отсечений с аппроксимацией допустимой области. На основе полученных результатов можно сделать следующие выводы:
- Вариант метода отсечений Булатова более эффективен (с точки зрения скорости сходимости) чем оригинальны метод отсечений лишь для задач размерность которых превышает 4. Оптимальным значением параметрам является диапазон от 0.2 до 0.45.
- Вариант метода отсечений Булатова с обновлением погружающих множеств становится эффективнее варианта метода отсечений Булатова без обновления погружающих множеств при размерности задачи больше 5. Оптимальным значением параметра а является диапазон от 0 до 0.45, параметра Д и АД, значения 0.1 и 0.0001 соответственно.
- Вариант модифицированного метода отсечений является эффективнее чем модифицированный метод отсечений. Оптимальным значением параметрам является диапазон от 0.2 до 0.5.
- Вариант модифицированного метода отсечений с обновлением погружающих множеств оказался наиболее эффективным из всех рассматриваемых методов. Оптимальным значением параметра м является диапазон от 0 до 0.45, параметра Д и АД, значения 0.1 и 0.0001 соответственно.
В целом можно заключить, что модификация с перемещением вспомогательных точек в допустимой области согласно определенном правилу положительно влияет на скорость сходимости методов отсечений с аппроксимацией допустимой области. Так же, варианты методов отсечений с обновлением погружающих множеств обеспечивают меньшую погрешность вычислении.
Перспективой дальнейшего исследования данных методов являются: доказательство сходимости вариантов методов отсечений и теоретическое исследование оптимальности параметра а.



[1] В. П. Булатов Методы погружения в задачах оптимизации / В. П. Булатов
- Изд-во Наука, 1977..
[2] И. Я. Заботин О некоторвгх алгоритмах погружений-отсечений для задачи математического программирования / И. Я. Заботин // Известия Иркутского государственного университета. Сер.Математика. - 2011.- Т.4. - № 2.
- С. 91- 101.
[3] И. Я. Заботин Метод отсечений с обновлением погружающих множеств и оценки точности решения / И. Я. Заботин, Р. С. Яруллин // Учению записки Казанского Университета. Физико-математические науки - 2013.- Т.155. кн.2.


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

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


Подобные работы


© 2008-2021 Cервис помощи студентам в выполнении работ
.