Построение оптимальных пространственных фигур методами нелинейного программирования

Размещено на http://www.allbest.ru/

На правах рукописи

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

ПОСТРОЕНИЕ ОПТИМАЛЬНЫХ ПРОСТРАНСТВЕННЫХ ФИГУР МЕТОДАМИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

01.01.09 - Дискретная математика и математическая кибернетика

Цветкова Евгения Геннадьевна

Тверь - 2009

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

Научный руководитель доктор физико-математических наук, профессор Андреева Елена Аркадьевна

Официальные оппоненты: доктор физико-математических наук, профессор Дикусар Василий Васильевич

доктор физико-математических наук, профессор Язенин Александр Васильевич

Ведущая организация Тверской государственный технический университет

Защита состоится «19» февраля 2009 г. в 15 ч 00 мин на заседании диссертационного совета Д002.017.02 при Учреждении Российской академии наук Вычислительный центр им. А.А.Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, 40, конференц-зал

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан «17» января 2009 г.

Ученый секретарь диссертационного совета доктор физико-математических наук, профессор Рязанов В.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Объект исследования и актуальность темы. В настоящее время задачи нахождения выпуклых тел с экстремальными геометрическими свойствами имеют актуальное значение, возникая в различных приложениях, таких, как проектирование электротехнических устройств, поиск оптимальных форм заготовок в раскройно-заготовительных производствах, упаковка тел. Рассматриваемые задачи сводятся к определению формы объемной фигуры, оптимальной по заданному критерию и удовлетворяющей требованиям к ее ширине. В качестве экстремальных геометрических задач в работе рассматриваются задачи нахождения выпуклых тел, обладающих максимальной или минимальной площадью поверхности либо максимальным или минимальным объемом. Решение круга таких задач геометрическими методами приведено в работах российских и зарубежных авторов. Данные методы не всегда позволяют найти экстремальную фигуру с заданными ограничениями. Ряд экстремальных геометрических задач для плоских фигур с ограничениями на ширину решен в работах Андреевой Е.А., Красноженова Г.Г. При этом ощутимой является нехватка методов решения экстремальных задач геометрии о пространственных выпуклых фигурах с заданными ограничениями на ширину. Формально решаемые задачи могут быть представлены задачами оптимального управления с фазовыми ограничениями и нелинейного программирования. В диссертационной работе разработаны алгоритмы построения их численного решения, на основании которых создан комплекс программ в среде программирования Borland Delphi 7.

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

Основные задачи диссертационного исследования. Поставленная в диссертации цель работы достигается путем решения следующих задач:

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

2.Постановка экстремальных задач геометрии в форме задач оптимального управления с фазовыми ограничениями.

3.Вычисление аналитических решений задач о построении выпуклых экстремальных фигур вращения и произвольных выпуклых экстремальных пространственных фигур.

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

5.Аппроксимация экстремальных геометрических задач задачами нелинейного программирования, разработка и реализация численных алгоритмов их решения.

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

Основными результатами диссертационного исследования, выносимыми на защиту, являются:

1.Постановка экстремальных пространственных геометрических задач в форме задач оптимального управления с фазовыми ограничениями.

2.Аналитическое решение экстремальных геометрических задач о построении выпуклых центрально-симметричных фигур вращения с ограничениями на ширину, построение аналитического решения задач о нахождении формы произвольных выпуклых пространственных фигур максимальной площади поверхности и объема.

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

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

5.Сравнительный анализ методов оптимального управления и нелинейного программирования при решении экстремальных геометрических задач для выпуклых пространственных фигур с заданными ограничениями на ширину.

Научная новизна выполненной работы заключается в следующем:

1.Впервые получено аналитическое решение задач о построении экстремальных пространственных выпуклых центрально-симметричных фигур вращения с ограничениями на ширину.

2.Получено аналитическое решение задачи о построении произвольной выпуклой пространственной фигуры максимального объема и максимальной площади поверхности.

3.Произведен сравнительный анализ методов оптимального управления и нелинейного программирования при решении пространственных экстремальных геометрических задач.

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

Внедрение результатов работы. Научные результаты использованы в учебном процессе математического факультета Тверского государственного университета при подготовке студентов по специальности 010100 - Математика, направлению 511200 - Математика. Прикладная математика.

Апробация работы. Основные результаты диссертационной работы и отдельные положения представлены на Межвузовской научно-практической конференции, посвященной 300-летнему юбилею Л.Эйлера (Тверь, 2007г.), научных семинарах кафедры компьютерной безопасности и математических методов управления ТвГУ (2004-2008 гг.) и ВЦ РАН (2008 г.).

Публикации. По теме диссертации опубликовано 7 работ, в том числе 2 статьи в изданиях, рекомендованных ВАК для представления результатов кандидатских диссертаций. Список работ приведен в конце автореферата.

Структура и объём работы. Диссертация состоит из содержательной части, включающей введение, четыре главы и заключение, списка литературы из 100 наименований и приложения; содержательная часть изложена на 150 страницах, общий объем - 225 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

Рассматриваются задачи нахождения выпуклой пространственной фигуры , обладающей максимальной (минимальной) площадью поверхности

, (1)

или максимальным (минимальным) объемом

(2)

Условия выпуклости фигуры в сферических координатах, согласно теореме Минковского, выражаются неравенствами:

(3)

где , , , .

Ограничения на ширину фигуры имеют вид:

.(4)

На границе учитываются условия:

.(5)

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

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

(6)

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

, , ,, п.в. ,(7)

, , ,(8)

,(9)

, .(10)

С применением двойственного метода оптимального управления построено аналитическое глобально оптимальное решение рассматриваемой задачи при r=1. Вид экстремальной фигуры, соответствующей аналитическому решению в случае , , , приведен на рис.1.

Для случая построено аналитическое решение задачи о нахождении выпуклой фигуры вращения минимальной площади поверхности, состоящей в максимизации (6) при ограничениях (7),(9),

,,,(11)

Вид фигуры, соответствующей аналитическому решению задачи (6),(7),(9),(11) при ,, , приведен на рис. 2.

Получено аналитическое решение задачи о нахождении выпуклого центрально-симметричного тела вращения максимального объема: минимизировать функционал

(12)

при ограничениях (7)-(10) для случая .

Экстремальная фигура, соответствующая аналитическому решению при , , , имеет вид, представленный на рис.1.

Аналогично при решена задача о построении выпуклой фигуры вращения минимального объема, состоящей в максимизации функционала (12) при ограничениях (7),(9),(11). Вид экстремальной фигуры, соответствующей аналитическому решению при ,, , приведен на рис.2.

Рис.1. Вид фигуры

Рис.2. Вид фигуры

При r>1 рассматриваемые задачи не всегда могут быть решены аналитически, что приводит к необходимости разработки численных методов их решения.

Для задачи (6)-(10) приводится вариация метода проекции градиента с использованием штрафных функций для учета фазовых ограничений. Дискретная задача с использованием внешних квадратичных функций штрафа при сводится к минимизации



(13)

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

,,, (14)

,,

где,,,,,

Из условий стационарности функции

получены рекуррентные соотношения для алгоритма численного решения.

Теорема 2.11. Пусть - локально оптимальное решение задачи (13),(14), тогда , определяются по формулам:

,



пространственный тело нелинейный программирование

Пусть аналитическое решение задачи, , ,площадь поверхности и объем фигуры, полученной аналитически, - численное решение задачи, -количество итераций метода, -площадь поверхности и объем фигуры, полученной численно, ,- точность численного метода, - норма в . Построено численное решение задачи при следующих значениях параметров: =0,8, D=1, r=1, =1, q=3000, =. Начальное приближение выбрано в виде . В результате работы метода получены значения: , , , , , при этом , . На рис. 3,4 приведены графики функций , , полученных методом внешних штрафных функций и аналитически.

Рис.3. Графики



Рис.4. Графики

Аналогично получено численное решение задачи о построении фигуры минимальной площади поверхности при следующих значениях параметров: =0,8, D=1, r=1, =0,8, q=3000, =, . В результате работы метода вычислены значения: , , , , , при этом , . Графики функций , , полученных численно и аналитически, представлены на рис. 5,6.

Рис.5. Графики

Рис.6. Графики

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

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

Задача (6)-(10) приводится к виду: минимизировать функционал

(15)

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

(16)

,(17)

, ,,(18)

,,,.(19)

Строится дискретная задача нелинейного программирования, аппроксимирующая (15)-(19). Пусть , , , , , , , , четно. Применяя формулы Эйлера аппроксимации производных , , с учетом (16),(17) получаем ограничения на : , . Дискретная задача, аппроксимирующая (15)-(19) с точностью , принимает вид: минимизировать

,(20)

,,(21)

(22)

(23)

, ,(24)

,,,,.

Из условий (21) получены линейные ограничения для :

, , ,

.(25)

Построен алгоритм решения рассматриваемой задачи методом градиентного спуска, где ограничения (22)-(25) учтены посредством проекции на допустимое множество. Для определения направления приближения к экстремуму применяется метод наискорейшего спуска, сопряженных градиентов, метод Ньютона. В табл.1 приведены результаты работы градиентных методов при решении рассматриваемой задачи. При =0.9, D=1, r=1, =1, , = известно: , .

Табл.1. Сравнительный анализ градиентных методов при решении задачи

q	Значение	Методы	q	Значение	Методы
		наиск. спуска	сопряж. град.	Ньютона			наиск. спуска	сопряж. град.	Ньютона
500		16448	13	8			120834	32	24
		-1,9890	-1,9890	-1,9891			-1,9897	-1,9898	-1,9898
		0,12	0,11	0,11			0,07	0,05	0,05
		0,05	0,04	0,04			0,015	0,01	0,01
		3,1227	3,1229	3,1229			3,1238	3,1239	3,1239

Экстремальная фигура имеет вид, представленный на рис. 1.

В результате решения задачи методом градиентного спуска при выборе параметров: , =0,9, D=1, r=3, =0.95, =0.975, =0.9875, , , , = получены значения:, , Графики , опорной функции и вид экстремальной фигуры, соответствующих численному решению, приведены на рис.7-9.

Аналогично разработан и реализован алгоритм решения задачи (6),(7),(9),(11): максимизировать функцию (20) при ограничениях (21), (22),

(26)

,,, ,, ,,

,,,,(27)

При , =0,8, D=1, r=1, =0,8, , = получено: , , , =12320, , при этом , . Вид экстремальной фигуры представлен на рис.2.

При , =0,9, D=1, r=2, =0,93, =0,95, , , = получены значения: =25832, , . Графики , и вид экстремальной фигуры, приведены на рис. 10-12.

Рис.7. График Рис.8. График Рис.9. Вид фигуры

Рис.10. График Рис.11. График Рис.12. Вид фигуры

Разработан и реализован алгоритм построения методом градиентного спуска оптимального решения задачи о нахождении выпуклой центрально-симметричной фигуры вращения максимального объема: минимизировать

(28)

при ограничениях (21)-(24). При выборе параметров: , =0.8, D=1, r=1, =1, , = получено: , , , , . Аналитическому решению соответствуют величины: , . Экстремальная фигура имеет вид, представленный на рис.1.

Аналогично приведена схема решения задачи о построении выпуклой центрально-симметричной фигуры вращения минимального объема, которая сводится к нахождению максимума функции (28) при ограничениях (21),(22),(26),(27). Выбраны следующие значения параметров: =0.9, D=1, r=1, =0.9, , =. При этом получено: =12846, , , , , , . Экстремальная фигура имеет вид, представленный на рис.2.

Для рассмотренных задач произведен анализ влияния вычислительных параметров на оптимальное решение. Приведены результаты их численного решения методом градиентного спуска при заданном количестве и расположении дополнительных ограничений.

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

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

, , , ,

В обозначениях , , , , , задача сводится к минимизации

(29)

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

, , , ,

,,

,

, , , ,

,.(30)

Дискретная задача нелинейного программирования, аппроксимирующая (29),(30) с точностью , имеет вид: минимизировать функцию

(31)

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

,(32)

,(33)

,,(34)

,(35)

где , , , , , , ,

,,,,, , , , .

Описывается схема построения оптимального решения методом градиентного спуска. При значениях параметров: , =0.9, D=1, r=2, 0.95, =-0.02, =0, , , =0,9, =0, = получено: , , =27012. График опорной функции и вид экстремальной фигуры приведены на рис. 13,14.

Рис.13. График Рис.14. Вид фигуры

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

(36)

при ограничениях (32)-(35).

При , =0.9, D=1, r=2, ==0.95, , =0, , , = получено: , , =26821.

Четвертая глава диссертационной работы посвящена решению задач о построении произвольных выпуклых экстремальных пространственных фигур. Рассматривается задача о нахождении формы пространственной выпуклой фигуры максимальной площади поверхности: минимизировать

(37)

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

(38)

,

,

,.

Дискретная задача, аппроксимирующая (37),(38), имеет вид:

(39)

(40)

,

, , ,

(41)

где , , , , , , .

Для построения оптимального решения применяется метод градиентного спуска.

Ограничения учитываются с помощью проекции , , , на допустимое множество. При , =0.9, D=1, r=1, =1, = получено: , -, , .

Аналогично строится решение задачи о нахождении формы выпуклой пространственной фигуры минимальной площади поверхности. Соответствующая ей задача нелинейного программирования сводится к максимизации (39) при ограничениях (40),

(42)

При ,=0.9,D=1, r=1,=1,= получено: , .

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

(43)

при ограничениях (40),(41).

При решении данной задачи методом градиентного спуска для , =0.9, D=1, r=1, =1, получено: , , , , , .

Аналогично построено численное решение задачи о нахождении формы выпуклой пространственной фигуры минимального объема. Соответствующая аппроксимирующая задача нелинейного программирования сводится к максимизации (43) при ограничениях (40),(42). При задании следующих значений параметров: , =0.9, D=1, r=1, =1, = получено: , , .

Основные результаты

1.В диссертационной работе экстремальные геометрические задачи формализованы как многомерные задачи оптимального управления с фазовыми ограничениями.

2.Получено аналитическое глобально оптимальное решение в следующих задачах о выпуклых центрально-симметричных фигурах вращения с дополнительным ограничением на ширину:

· нахождение фигуры максимальной площади поверхности;

· нахождение фигуры минимальной площади поверхности;

· нахождение фигуры максимального объема;

· нахождение фигуры минимального объема.

3.Построено аналитическое глобально оптимальное решение в задачах о нахождении произвольных выпуклых пространственных фигур максимальной площади поверхности и максимального объема без дополнительных ограничений на ширину.

4.Разработан и реализован алгоритм метода внешних штрафных функций для построения оптимального решения в задачах о нахождении формы выпуклых центрально-симметричных фигур вращения максимальной и минимальной площади поверхности с заданными ограничениями на ширину. Исследовано влияние параметров метода и параметров задач на оптимальное решение.

5.Продемонстрирована эффективность аппроксимации экстремальных геометрических задач задачами нелинейного программирования. Разработаны и реализованы алгоритмы метода градиентного спуска для решения следующих задач:

· нахождение выпуклых центрально-симметричных экстремальных фигур вращения;

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

· нахождение произвольных экстремальных выпуклых пространственных фигур.

6.Показано, что метод градиентного спуска более эффективен при их решении по сравнению с методом внешних штрафных функций. В частности, при решении методом штрафных функций задачи о построении центрально - симметричной фигуры вращения максимальной площади поверхности при выборе параметров: =0.8, D=1, r=1, =1 получено значение отклонения за итераций, при ее решении методом градиентного спуска - за итераций. При решении задачи о минимизации площади центрально-симметричной фигуры вращения методом штрафных функций при =0.8, D=1, r=1, =0.8 получено: , методом градиентного спуска - , .

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

Публикации автора по теме диссертации

в изданиях, рекомендованных ВАК России:

1. Цветкова Е.Г. Задача о построении выпуклой фигуры вращения, обладающей минимальной площадью поверхности, с заданными ограничениями на ширину // Вестник ТвГУ. Сер. Прикладная математика. 2007. №7. С. 149-161.

2. Цветкова Е.Г. Решение задачи о построении выпуклого тела вращения максимальной площади поверхности методами нелинейного программирования // Вестник ТвГУ. Сер. Прикладная математика. 2008. №3(10). С. 79-96. в других изданиях:

3. Андреева Е.А., Цветкова Е.Г. Оптимальное управление процессом отлова рыбы / Е.А.Андреева, Е.Г.Цветкова // Применение функционального анализа в теории приближений: Сборник научных трудов. Тверь: ТвГУ, 2005. С. 132-144.

4. Андреева Е.А., Цветкова Е.Г., Савичева Ю.А. Решение экстремальных задач геометрии двойственным методом: Учеб. пособие. Тверь: ТвГУ, 2007.- 180 с.

5. Цветкова Е.Г. Задача о построении поверхности вращения, обладающей максимальным объемом, с заданными ограничениями на ширину / Е.Г.Цветкова // Межвузовская научно-практическая конференция, посвященная 300-летнему юбилею Леонарда Эйлера: Сборник статей. Тверь: ТвГУ, 2007. С. 91-104.

6. Цветкова Е.Г. Задача о построении поверхности вращения, обладающей максимальной площадью поверхности, с заданными ограничениями на ширину / Е.Г.Цветкова // Многоуровневая система подготовки специалистов на основе информационных и коммуникационных технологий образования: Сборник научных трудов. Тверь: ТвГУ, 2006. С. 176 - 187.

Размещено на Allbest.ru

...