Введение 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 были реализованы и отлажены программы для исследования вариантов метода отсечений Булатова и вариантов модифицированного метода отсечений.

Купить