Автор: Бахтиярова Лилия Ильнуровна

Рубрика: Математика

Опубликовано в Молодой учёный №9 (143) март 2017 г.

Дата публикации: 05.03.2017

Статья просмотрена: 25 раз

Библиографическое описание:

Бахтиярова Л. И. Численные методы для решения задачи о нахождении выпуклой пространственной фигуры вращения максимальной площади поверхности при заданных ограничениях на ее ширину // Молодой ученый. — 2017. — №9. — С. 1-7.



Целью научного исследования является формализация задач о построении оптимальных выпуклых тел в форме задач оптимального управления и нелинейного программирования, исследование свойств полученных задач, разработка, реализация и сравнение численных методов их решения.

Ключевые слова: опорная функция, поверхность вращения, радиус кривизны, нелинейное программирование, дискретная аппроксимация

Геометрические задачи о нахождении тел, максимальной или минимальной площади и объема с определенными ограничениями на ширину фигуры, широко распространены не только в математике, но и в практических приложениях. Такого рода задачи применяются в технике, производстве, задачах раскроя и упаковки, при размещении груза и объектов на различных транспортах. Знакомые задачи: Зедонора, в которой среди n-угольников, имеющих заданный периметр, требуется найти n-угольник максимальной площади; Архимеда, в которой необходимо найти шаровой сегмент, вмещающий наибольший объем среди всех сегментов, обладающей определенной площадью; Евклида и многие многие другие, решались еще в далеком прошлом. Поэтому решение экстремальных задач геометрии актуально и немаловажно не только с теоретической, но и с практической точки зрения. Формализовав задачуонахождения выпуклой, пространственной, центрально симметричной фигуры вращения максимальной площади поверхности при заданных ограничениях на ее ширину, как задачу математической теории оптимального управления. В работе при помощи программных средств рассматриваются и сравниваются результаты применения численных методов при построении «подозрительной на оптимальность» поверхности вращения.

Для описания свойств ограниченного замкнутого выпуклого множества используется его опорная функция, определяемая выражением:

(1)

где — единичный вектор направления в сферической системе координат.

С помощью опорной функции определяется ширина поверхности вращения: , диаметр: D= [2] и толщина множества: Использование данного подхода позволяет формализовать ограничения на ширину рассматриваемых фигур, выразить такие характеристики, как периметр, площадь, объем, а также получить аналитическое выражение условий выпуклости. В частности, в случае плоской фигуры при введении полярной системы координат опорная функция является функцией полярного угла . При этом радиус кривизны фигуры в каждой точке вычисляется по формуле: , и в силу выпуклости фигуры, неотрицателен. Для вычисления периметра и площади могут быть использованы соотношения (2)-(3):

(2)

(3)

В работе приведенные соотношения служат основой для формализации рассматриваемых задач, решение которых сводится к определению опорной функции.

Задача о построении выпуклой фигуры , имеющей максимальную площадь поверхности S(F)

Требуется найти выпуклую фигуру вращения максимальной площади поверхности:

(4)

опорная функция, которой удовлетворяет условиям:

(5)

Введем функции , и обозначим независимую переменную через .

В новых обозначениях задача является задачей оптимального управления с фазовыми и промежуточными ограничениями

минимизировать функционал:

(6)

при ограничениях:

(7)

,,,(8)

, ,

(9)

Дискретная аппроксимация

Разобьем равномерно отрезок интегрирования точками , , полагая , , , . Обозначим .

Используя формулы Эйлера аппроксимации производных: , с учетом (7), получаем рекуррентные соотношения: При этом , , . Пусть — номера точек отрезка разбиения, соответствующих точкам , отрезка . Дополнительные ограничения на ширину принимают вид: [5].

Метод левых прямоугольников

Расчёт интеграла в целевом функционале проводим по формуле левых прямоугольников. Дискретная задача, аппроксимирующая (6)-(9) с точностью , имеет вид:

минимизировать функцию

(10)

при ограничениях:

(11)

,(12)

.(13)

При такой постановке задачи становится доступным широкий спектр методов математического программирования с высокой скоростью сходимости. В частности, для решения рассматриваемой задачи применен метод градиентного спуска. Ограничения на переменные учитываются с помощью проекции градиента. Для определения направления приближения к экстремуму применяется наискорейший спуск.

В методе наискорейшего спуска шаг градиентного спуска выбираем из условий: , . На каждой итерации данная одномерная задача оптимизации решается методом дихотомии с заданным интервалом изменения , равным , и точностью определения решения . Градиент минимизируемой функции вычисляем по формулам [5]:

(14)

Метод Симпсона

Для вычисления интеграла в целевом функционале можем использовать формулу Симпсона. Дискретная задача, аппроксимирующая исходную задачу с использованием схемы Симпсона, имеет вид: минимизировать функционал

(15)

при ограничениях:

(16)

,(17)

.(18)

Градиент минимизируемой функции вычисляем по формулам:

(19)

Сравнительный анализ интегральных методов

Приведем результаты решения задачи в таблице 1 методом градиентного спуска с помощью формул левых прямоугольников и формулы Симпсона рис.1 и 2. Построено оптимальное решение задачи при наборах параметров: 1) q=500, =0,9,D=1, ==и 2) q=2000, =0,9,D=1, ==.

Таблица 1

Сравнительный анализ интегральных методов

Параметры:

q=500

Методы

Параметры:

q=2000

Методы

Левых прямоуго-льников

Симпсона

Левых прямоуго-льников

Симпсона

Количество итерации

27357

256

Количество итерации

22098

213

Время расчетов, мин

22

2

Время расчетов, мин

20

1

Достигнутая точность

Достигнутая точность

Значение минимизируе-мой функции

-3,1229

-3,1169

Значение минимизируе-мой функции

-3,1265

-3,1158

Построено численное решение (15)-(18) при следующих значениях параметров: q=500, =0,9,==. На рис.1. приведены графики функций , и сечение фигуры полученных методом проекции градиента.

D:\Для диссертации\Фото для работ\Симпсон.png

Рис. 1. Экранная форма интегральных методов без ограничений на ширину

Приведем результаты решения задачи (15)-(18) методом проекции градиента с одним активным дополнительным ограничением. Построено оптимальное решение задачи при значениях параметров: q=500, =0,9,D=1, ==. На рис.2 представлена экранная форма программного продукта, построены графики и сечение фигуры, соответствующих оптимальным решениям задачи.

D:\Для диссертации\Диссертация\Симпсон с доп огр.png

Рис. 2. Экранная форма интегральных методов при одном дополнительном ограничении

Сравнительный анализ градиентных методов

Для определения направления приближения к экстремуму в методе градиентного спуска применим метод Ньютона. Гессиан минимизируемой функции вычисляем по формулам [2], [5]:

,

,

, (20)

Приведём сравнительный анализ численных решений рассматриваемой задачи, полученных методом градиентного спуска, наискорейшего спуска, сопряженных градиентов, Ньютона, Флетчера-Ривза. Результаты численных экспериментов и анализ эффективности методов при решении задачи для 500 и 2000 точек разбиения приведены, соответственно, в табл. 2 и 3. Метод Ньютона сходится быстрее и позволяет получить более точное решение, если начальная точка, из которой запускается численный процесс оптимизации, находится в некоторой окрестности одной из точек минимума. В качестве такой точки целесообразно выбирать решение, полученное методом наискорейшего спуска.

Таблица 2

Сравнительный анализ градиентных методов

Параметры:

q=500

Методы

Градиентного спуска

Наискорей-шего

спуска

Флетчера-Ривза

Сопряжен-ных

градиентов

Ньютона

Количество итерации

27357

16458

1745

18

10

Время расчетов, мин

22

12

8

0,08

0,009

Достигнутая точность

Значение минимизируемой функции

-3,1229

-3,1238

-3,1241

-3,1245

-3,1239

Таблица 3

Сравнительный анализ градиентных методов

Параметры:

q=2000

Методы

Градиентного спуска

Наискорей-шего

спуска

Флетчера- Ривза

Сопряжен-

ных

градиентов

Ньютона

Количество итерации

22098

57814

1689

17

11

Время расчетов, мин

20

23

7

0,09

0,008

Достигнутая точность

Значение минимизируемой функции

-3,1265

-3,1263

-3,1264

-3,1265

-3,1265

Результаты, полученные в работе численно, соответствуют аналитическому решению данной задачи, приведенные во многих работах Андреевой Е. А. [2], Цветковой Е. Г. [5], Красноженова Г. Г. [4] и других.

Литература:

  1. Andreeva E. A., Klötzler R. Zur analytischen Lösung geometrischer Optimierungsaufgaben mittels Dualität bei Steuerungstheorie // ZAMM. 1984.
  2. Андреева Е. А., Цирулева В. М. Численные методы решения экстремальных задач. Тверь, 2002.
  3. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.:Наука, 1982.
  4. Красноженов Г. Г. Применение численных методов к решению экстремальных задач геометрии. Диссертация канд. ф.м. наук. Тверь, ТвГУ, 2001.
  5. Цветкова Е. Г. Решение экстремальных задач геометрии методами оптимального управления и нелинейного программирования // Математика. Информационные технологии. Образование: Сборник научных трудов. Оренбург: ОГУ, 2008. С.103–106.
  6. Цветкова Е. Г. Применение методов нелинейного программирования к решению экстремальных геометрических задач// Математические методы управления: Сборник научных трудов. Тверь: ТвГУ, 2009. С. 97–108.
Основные термины (генерируются автоматически): градиентного спуска, экстремальных задач, вращения максимальной площади, максимальной площади поверхности, экстремальных задач геометрии, фигуры вращения максимальной, методом градиентного спуска, решения задачи, оптимального управления, наискорейшего спуска, оптимальное решение задачи, численных методов, решения экстремальных задач, результаты решения задачи, левых прямоугольников, опорная функция, поверхности вращения, пространственной фигуры вращения, нелинейного программирования, метод градиентного спуска.

Ключевые слова

нелинейное программирование, опорная функция, поверхность вращения, радиус кривизны, дискретная аппроксимация

Обсуждение

Социальные комментарии Cackle
Задать вопрос