Построение оптимальных пространственных фигур методами нелинейного программирования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Тверь - 2009

003460961

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

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

Андреева Елена Аркадьевна

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

Дикусар Василий Васильевич

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

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

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

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

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

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

технический университет

профессор

Рязанов В.В.

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

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

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

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

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

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

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

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

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

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

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

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

выносимыми на защиту, являются:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

R ППЛ1П1ПМ1 ЛПЛП1ЛП11П О 1ТЛ ' О Г11 I I ГУ Q"!"^ n L-ICpdl ! ! ' О ¡1 TSMLi* I'CCJIVMOUW!'!'"

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

В первой главе формулируются свойства пространственных выпуклых фигур. Вводится понятие опорной функции h(n,F) ограниченного замкнутого выпуклого множества Fe /?"', определяемой в сферической системе координат для любого единичного вектора /7 = (cosflsin<^.sin#siiip,cos^),öe[0,2/r],(p€[0./T], выражением h(n,F) = h(n) = h(Q,<p) = max j(/;,.v)|.ve I'j, приводится определение ширины B(n,F) = B(n) = B(0,<p) = h(n) + h{-n), диаметра D(F)= D = ma\B{n) и толщины A(F) = д = minB(n) множества/Л

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

l'/(0.<fl) h,-(0,<p)

S(F) = \\

h-(0,<p)-

2 2sin:p или максимальным (минимальным) объемом

sintp-dO-dip,

h'(Ü.tp)-h(0,(p)

' hrhO.<p) h,;(0.<p) 2 2sin:p

sin ■ dO ■ dip

(1)

(2)

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

3(£,р)>0, ~^в.<р)Т(0,<р)-Х1(0,<р)>0, (в,/р)еП, (3)

где О = {{в,(р\в е [0,2л-], <ре[Ъ,л]\, Ш<р) = Ип,(0.<р) + Ь(0,<р),

Т(0,<р) =

h,„(e,<p) cos<р cos<р --1--"Лв,(р) +h(d,<p), —

snri/> sin^

Sin^j Sill"

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

Д </¡(0, <р) + И(л + 0,л-<р)< О. (4)

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

Л„(0,О) = /7„(;г + 0,;г), Л(0,^) = А(2л-,р), /,г(0,<р) = 11г(2тг.<г>). (5)

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

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

1 = <р, л-,(/) = /;(0 + Л(л--0 = 2/|('), лг,(/) = лп(/). и(1) = л-;(/Н .у, (О- / е [0,я-], формулируем задачу о построении выпуклой центрально-симметричной фигуры максимальной площади поверхности: минимизировать

7 (н) = - 2 / Я- • 5 (^) = - [(.У,: (/) - 1/ 2 • ЛГ) в 1II (/ ) Л

(6)

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

л-|(/) = л-,(М. .у.ЧО+ *,(') = "('). Д<-У,(/)<£1, /е[0.л-], !((/)> о,/;.«. I 6 [0. я\, (7)

-у 1(т1)<аг Х1(ж-Т1)<аг Д < о( < О , г, €(0.;г2], 7 = 1. г, (8)

СГК /

— л',(/) + л',(/)>0, /6[0.Л-], (9)

.у|(0) = л',(л") = Д, .у,(0) = -.у= - Д: . (10)

Построено аналитическое глобально оптимальное решение рассматриваемой задачи при /•=/. Вид экстремальной фигуры, соответствующей аналитическому решению в случае о, = о = 1, д = 0.8, т,=х/2, приведен на рис.1.

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

Х,(Г()>ЙГ,, Л-(л--г,)20,. г, е (О.л- 2], j = l,r ,jr,(0) = *,(*) = £>„х,(0) = jr:(tf) = 0. (11) Вид фигуры, соответствующей аналитическому решению задачи (6),(7),(9).( 11) при а, = А = 0.8,£> = I, г, = ж/2, приведен на рис. 2.

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

J(u) = -\2lK-V(F) = -)(xl\l)-\l2-x{(t)-xl(l))sm(l)dl (12)

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

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

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

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

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

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

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

= ^(х/- ~ (л-; У ) - М,' (д - х[- М,' (х; - о)' + М,к (л-Г - о,-

- 2 У ) ^ Л/,' (д - л-;); -л/Дг; -о); т+л/4'(*,''"-а,1 - (13)

-I

</-\ -1

+ Л/,/ (л - л",''")^ + А//(д-.г,''); + - л)! + »2-йГ$ + А/,,,' (- Л-," - п2

ри ограничениях: .V," =х, +х'1<т,х'2*' =л% +(-.%■) +г/)сг,/ = 0,<?-1, (14)

л-;1 = л, х" = -л2,> о. / = о. <? -1, где<т - п1с1,)' -¡а,х\ =Л'|(/'),Л% = Д",(/'),=;/(/'),/;; = [</■ г, /я], >0./ = 1.10. Из условий стационарности функции

4-1 4-1

/.(/„.Л^.Л'..»./;,,р:) = + --V,' -Л<сг) + ^//"(л-;*1 -Л-; +(л-; -1/')сг)

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

/>; = />Г' + Д.^д-Чт/' +2Л/,' (л-л-;)^-2Л/,' (л-; - о) )<г -р':'а, />■; =4,(2.1/.' (л-Л-,") -2Л/„' (.г'-лЦ /л = /Л" -/„л-ит/'ст + ^Г'я-. / = (ЪМ.

= А,, ^2Л/И1" -2Л/./ (л'," + - д:) j.

р; = /V*' - 24 (•< л/,1' (А - Д'Г ) - рГ'сг, Р™ = /;Г' + РГ'е,

Р'! ™ = я'-"1 -24,(л// (.V,"-'" - рГ" = />Г.....+ —'сг.

Пусть ...........л-2.,„,У„„-аналитическое решение задачи,

и,,,,' = «„„(/').' = 0.<?, л-,.....' = дг|,т (/'), л-;,,,,,' = л-:,,,, (/'),/ = 0, ц , 1'„,-площадь

с/ - Н! .

поверхности и объем фигуры, полученной аналитически, u,xt,x;,J-численное решение задачи, i „-количество итераций метода,

S'L = !" " II/J""'"-1 '100%- 5сл = Ц*' " ~х'«т Ц/Ц"*'1""'' I '100%- = ~ W-1 1 °0%"

5.1 -площадь поверхности и объем фигуры, полученной численно, точности численного метода. ||-]- норма в /?''. Построено численное решение задачи при следующих значениях параметров: А =0,8, D I. г=1, о,=/, q 3000. £,=£, 1(TS. Начальное приближение и"" выбрано в виде

и.....=0,; = 0.(?-1. В результате работы метода получены значения: С„ =380276,

7 = -1.969, й-;:,,. =14, <5^ = 2.7, <5^=0.459, S = 3.091, при этом J„,=-1.96, 5,„ =3.077. На рис. 3.4 приведены графики функций »(/). дМ/), полученных методом внешних штрафных функций и аналитически.

■ Аналитическо-? решение

Решение,полученное методом ш тройных функций

Рис.3. Графики ii(i) Рис.4. Графики xt(i)

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

А 0.8. D=l. г=1. о, -0,8. ч=3000. е, = t\ 10Л и.....= U = 0,с/ -1. В результате

работы метода вычислены значения: С„ =427116. 7=1.213, <Г(1. = 17, = ííj,(i =3.05, 5=1.904. при этом J„„ = 1.25, .V,„ = 1.963. Графики функций »(/), .vi(0, полученных численно и аналитически, представлены на рис. 5,6.

\

• Аналитическое решение

Решение.полученное методом штрафных функций

Рис.5. Графики и(1)

Рис.6. Графики д"|(/)

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

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

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

(15)

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

.Т|(/) + д-,(/)>0, и.в./е[ 0,;г].

-—л,(/) + л-(/)>0. /е[0,л\, sin (

(16)

(17)

(18)

Л<.\||/)<й л-|(г()<о(..у,(л--г|)<а(, Д<о, <0, г, е (0. л-/2]/ = !./■,

л-(0) = л",(/Т) =- Л,л-,(0) = х,(ж) = ч/О" - Л2 ,л-,(0 =.Г|(0. и(1) = Л|(/) + д-|(0 ,( е [О.л]. С9) Строится дискретная задача нелинейного программирования, аппроксимирующая (15)-(19). Пусть д/ = .\-,(/'), л,' = л%(/'), /'=/<т, / = 0,г/,

■ а(1 ) I -- 0.(1 -1, сг = л-/</. т1 = [с! ■ г(/л-], / = !./■,(/ четно. Применяя формулы

Эйлера аппроксимации производных д-|((')-

-i-L, .Vi(/')s-L

2 д. +.v,

учетом (16Ц17) получаем ограничения на д,': ---—+ >0. / = 0.с/-2,

cos(

+ .v,' > 0. / = 0.1/-1. Дискретная задача, аппроксимирующая (15)-

(19) с точностью О(ст), принимает вид: минимизировать

/ Y 1 (*■"'-*■')"

' 1 2 а2

sill(í')

а,

(20)

Y,'*2 -2y,"' + V,' —

при --;-'- + x¡ >0, i =

eos(/')(-vr' --Yi')

sin(/')

+ .V,' >0,/ = 0,9-1, (21)

Л<л-,'<Д < = и-1, (22)

Л-'"' <а,, а,, Л <о,<£>, !</«,< <7/2, у = 1, г, (23)

л-" = л-;' = л. л-,' = л-;н = д+сгл/о: -д2, л-;' = - д:, (24)

=(л-|'*-'-2л-|'" + л-,')/(Т: + л-,', / = 0, ? - 2 , н""1 = 0, Л-,' = (*,"'-л-')/(т,; = 0,<7-1.

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

. .V,""' , Л',"1 +(1 +<т:)лг1'"1 , - ,1 , 1, л-; > --, л-: < -—--—, л-; > 2л-;1 - < 1+а- иу ■, / = 2, ч - 2.

I + о~ 2

(25)

.V,'<--д-'*1, х.' >(\~а1^"')х."', \—2м-2.

собС/'' ' >

Построен алгоритм решения рассматриваемой задачи методом градиентного спуска, где ограничения (22)-(25) учтены посредством проекции .у,' па допустимое множество. Для определения направления приближения к экстремуму применяется метод наискорейшего спуска, сопряженных градиентов, метод Ньютона. В табл.1 приведены результаты работы градиентных методов при решении рассматриваемой задачи. При Л 0.9.1) /.г- 1. «,.-/, т, =1. с, =ек =10'" известно: ./.„, =-1.99, .У,„ =3.1243. Таол.1. Сравнительный анализ градиентных методов при решении задачи

I 1 Змаче- Ч ! \ II ПС Методы намек. 1 сомряж. спуска | град. Ньютона Я Значение маиск. спуска Методы сонряж. град. Ныогона

500 С„ 16448 13 8 2 10"' С„ 120834 "р 24

.7 -1.9890 -1.9890 -1,9891 1 -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

В результате решения задачи методом градиентного спуска при выборе параметров: с/= 500, Д =0,9, £>=/, г=3, а, =0.95, а, =0.975, а, =0.9875,

я/, =63, ш, =125, т, = 250, к .•;, 10 получены значения:Сй = 10114, 7 =-1.8738 , 5 = 2.9434. Графики »(/), опорной функции Л(0 и вид экстремальной фигуры, соответствующих численному решению, приведены на рис.7-9.

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

х"'>аг х,'1""1 >й, . Д I <т; < <?/2. > = 1.г. (26)

< = X? = = < = О, (27)

где /' = /<т ,/ = О,!? ,0" = л-/<7, от/ = [<7 ■ г( / ;г],_/' = 1./-, х,' = х,(/') ,х,'' =0,»' = = = и(/') = (л',"" - 2х,"' + + -V,',/ = 0,<?-2 = 0, л-,' = .V,) = (х,"1 -х,' )/<т, / = 0.<?-1

При <7 = 500, д =0,8. 0=7. г -1, а, =0.8, т, = 1, = 10 " получено:

7 = 1.631, =0.14. <Г,. = 0.31. С, = 12320. V = 2.56, при этом У™ = 1.629, 5„„ =2.56. Вид экстремальной фигуры представлен на рис.2.

При с/ = 500. * -0.9. О 1. 1-2, и. -0,93, о, =0.95. /я, = 150, »»,=250, ¿- = е, =10'" получены значения: Г„-25832. .7 = 1.91, 5 = 2.99. Графики и(/),Л(/) и вид экстремальной фигуры, приведены на рис. 10-12.

"■^/4 "/2 Згг(4 :

Рис.7. График »(/)

Я" Зл" .'7Г 7Г

г 77

Рис.8. График И(1)

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

Ы10 7:1'.

Рис. 10. График и(1)

ю г ю

Рис.1 I. График Н(1)

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

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

при ограничениях (21)-(24).

При выборе параметров: <? = 500, Л=0.8, 0=1, г=1, о, = 1, ///,=1, = гг, =10"'' получено: С„ =28634, <Г,(<=0.33, 1 = -1.945, <^,„=0.17, Г = 0.509. Лиалитическому решению соответствуют величины: 7„„ =-1.949, Г„ =0.509.

Аналогично приведена схема решения задачи о построении выпуклой центрально-симметричной фигуры вращения минимального объема, которая сводится к нахождению максимума функции (28) при ограничениях (21 ).(22),(2б),(27). Выбраны следующие значения параметров: \---0.9, 0=1, г=1. «,=0.9, /н, =|. /:,=,<.-, =10"". При этом получено: С:=12846, =0.28,

.7 = 0.707, =0.14, ( =0.185, 7„„ = 0.706, Г„, = 0.184 . Экстремальная фигура имеет вид, представленный на рис.2.

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

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

(28)

•• cos/ *

при ограничениях: /;(/) +/i(/)>0, . /i(/) + /i(i),/е[0,/г], li(0) = li(x) = Л/2,

Sill/

/|(г( ) + /;(л- -т1)<аг h{Tl)-h(7T-Tl) = br г( е (0,/г/2], j = \,r.

В обозначениях х|(/) = Л(/) + Л(я--/), л■,(/) = /г(/)-Л(л--0, *,(') = *КО, ^(0 = ^(0, 11,(0 = «(0 + ^,(0, »,(0 = дт4(0 +' е [О.л], задача сводится к минимизации

д',"(0+ду(0

х.;(0 + х/(р

2

sin(/)üV

(29)

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

дг,(0 = -т,(0, л-:(0 = .т4(0, A-j(/) = -.v1(0 + w,(/), л-4(/) = -х,(0 + »,(0,

и.(0>0, г/,(/) + к,(О>0, /е[0,я], —д-,(/) + х.(/)>0,

sin/

(30)

Д < л-,(/) < А -0<х:(/)<0, / е [0.Л-] ,Л-,(Г ,)<о,- г,.) < а,,

л-,( ) <-л-,(г,) + й, +6,, Л-, (Л--!■,.)<*, (Л-- т1)-(а1 +Ь,), г, е (0,л/2], у = 1,г, А-(0) = А-(л-) = Д, ,г,(0) = *,(*•) = д-4(0) = хл(х) = 0, ,т.(0) = -х,(х) = .

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

Í 4'•(■>■ )

sin(í')<T

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

1 + 2 1 /И г

А', - IX, + .V.

, „ Д-,"; -2.V,"1 +А-,' , д-'*; -2л-.'*1 + А','

+ Д-, >0. —-;-—+ .v, >-—-\-L-A-,

COS/ A", -.Y,

+ А-,' > О, Д < Д-; < D, - П< А-,' < D, i = 2,с/ - 2,

(31)

(32)

(33)

sin/ ег

д-,'"' <аг х,"""' <аг х,'" < -л-,"' н о, "' > а,""'" "К +b,),j = 1,г, (34)

д-," = .т* = д. д-; = д-,"-' = д+ал/о' - дт д" = д-; = л-г1 = а-:=о, (35)

где I' = ia , i = O.q , а = ж/q, mj = \q ■ r, / л], j = l.r, a-¡ = д',(/'), д< = л,(/'),

A-; = x~(í') = 3-í-,y4 = a'j(/') = ^-,i = 0.q-i,.v? = -Vd! -Д2 ,X* = 0,и;-1 = //Г' = о

а

-2д-"' +дг;

+д-;, / = о,с/- 2, //, = »,(/) =

х1;2-2Х1;1+х:

+ а*2 , / = 0,<?-2.

Описывается схема построения оптимального решения методом | радисн I но1 о спуски. При ^ничсмиил параметров. ¿/ — 500, Д —0.9, и /, /—2, а, = о. = 0.95, 6, =-0.02, А, =0, т, = 166, «/,= 250, г, =10~" получено: 7 =-1.906, 5 = 2.99. С„=27012. График опорной функции и вид экстремальной фигуры приведены на рис. 13,14.

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

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

X х. I + X,

•V, д. ! .V.

О

(36)

5И1(/')сг

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

При ? = 500, \ 0.9. 0=/, г --2, а,=а,= 0.95, ¿,=-0.02, Л,= 0. /», = 166. т, = 250, е, = г,. = 10 г' получено: 7 = -1.46, Г = 0.384, ('„=26821.

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

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

Л.иги:)= ] |С,.Л) + х,~(/,./, 1 вш /, | +1/2 • (д*,:(/,,) + х42(/,,Л))|бш/, |- (37)

-(дс,г(/,,/,) +j:2j(/,,/,))| sin/, I ~\dt,dt2

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

X„: (/,,/,) = X,(/,,/,), (',,';)= -v5 (/,,/,), ) = Xj (/,,/,). x,h(l¡,t,) = xr,(tl.t2),

Л--„ - Л ) = -Л", (л .Л ) + f. С,, ) + С, - ) , .Tj,, (/,,/, ) = -Л-, (/,,(,) + К, )-!/,(/,,/,).

«,(/,,/,) > 0, !(,(/,,/,)> О, /7.в.(/|./,) е 4J,

Л < .V,(Г,,f;> < D, - D < Х,(1,.1:)< D. (/,,/,) е Ч'. (38)

х,(т rr¡¡ )<а г Л < а ( < D. г, е (- ж/2.!г/2).1], е (- ж/2,ж/2)J = ü-

-v,(í,,0) = А, л;,(/,,0) = - Д: , л*, С, ,0) = л*4 (/, ,0) = x5U, ,0) = х,(/, ,0) = О, ^,(/,.-^/2) = х,(/,,яУ2), х,(/, -ж! 2) = х2(1,.ж 12),х:(- л 12,1,) = -х:(ж/2,ж -Г,).

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

./<x„x;) = ¿ I

----с ir» Г ' 4--------

(39)

- ((л-"): +(x;')2)|sin/;' при Л < X," < D. - П < х':' < /Л I = 6 = 0.9,.

х,'": -2х,' "1 + л*,'' + х,''*" -2л-,'''"" + .v;"'

-2х,' м + л-," -х,"*: +2х,"+1 -л,"

- + х." +х," >0,

-х,'' -х:" >0, / = 0,<7, , ./ =0.q, - 2,

(40)

х;" = х;-,,: = д, = = д+о-, л/Б7 - д-. xv" = 1 = = = о, (41) где x¡'' =х,(/,',/,'), хУ = х, (/,',/,'), i = 0.(7, , j = 0,<?: , ет, = ж/q, , <т, = n/q, ,

X;j<i-y;-' , vv*'-x;' ,, , , лГ'-'-х:-'

•ví =*5C, •': ) = --4*í' = xj(í, ,1, ) = ——-——, .r,' = x5(/, ,?,') = ■

cr,

cr,

, , ч x'^ - 2x'"' + x." + - 2x,'"' + x,"

II, = u, (/,./> ) = —-1-1--=-=—+x, 1 + Л", ,

OV

н2* = «,(/,',/,') = — 2л-,'-'+1 + */•' -Х^-"1 +2хг'"'" )/<Г22 + *,'•' —л-,'-' .

Для построения оптимального решения применяется метод градиентного спуска. Ограничения учитываются с помощью проекции л-;',.*-;', 1 = 0,(7,, у =0,1/, , на допустимое множество. При </,=<?, = 500, Д =0.9, />=/, л -/, а, >:, = с,. =10'" получено: 7= -5 = 3.1228, ./.» =-5,„ =3.1243, <>"„',,,.= 0.04, С„ =37215.

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

л-;" = д-;= л-;1 = = о, л-;-" = л-;-1 = л%,н = л-;"-- = о. (42)

При </,=(/;= 500. л -0.9,0=1, г— 1. о, = /, с, = сх = 10ч' получено: 7 = 5 = 2.56, С, =18217.

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

V1

11

а.~ 5ПГ Л

(7,2 (Т.'ЗПГЛ'

(43)

51ПЛ (Т,(Т,

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

При решении данной задачи методом градиентного спуска для </, 500, Д =0.9. £)=/, 1=1, а, =/, С, =^ = 10"" получено: 7 = -0.041, С„ =12814, Г = 0.518, Л,, =-1/24Г,,, =0.519, ^,,,=0.14, Г„ =37215.

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

программирования сводится к максимизации (43) при ограничениях (40),(42). При задании следующих значений параметров: =д,= 500, А =0.9, й=1, г=1, а, ~-1, = *,=10"" получено: С„ =15314, Г = 0.185, 7 = 0.007.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

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

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

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

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

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

» нахождение выпуклых центрально-симметричных

экстремальных фигур вращения;

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

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

6. Показано, что метод градиентного спуска более эффективен при их решении по сравнению с методом внешних штрафных функций. В частности, при решении методом штрафных функций задачи о построении центрально - симметричной фигуры вращения максимальной площади поверхности при выборе параметров: Д =0.8, 0-1, г = 1, а,=1 получено значение отклонения ¿Г, =1.7 за 380276 итераций, при ее решении методом градиентного спуска - <Г(< =0.12 за 27347 итераций. При решении задачи о минимизации площади центрально-симметричной фигуры вращения методом штрафных функций при А =0.8, й=1. г 1. а, -0.8 получено:

=4, с„ = 427116. методом градиентного спуска - <■>,;,, =0.33, Г„ =32711.

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.

7. Цветкова Е.Г. Решение экстремальных задач геометрии методами оптимального управления и нелинейного программирования // Математика. Информационные технологии. Образование: Сборник научных трудов. Оренбург: ОГУ, 2008. С. 103-106.

Технический редактор А.В.Жильцов Подписано в печать 15.01.2009. Формат 60x84 ^

Усл. печ.л. 1,3. Тираж 100 экз. Заказ №6. Тверской государственный университет Редакционно-издательское управление Адрес: Россия, 170100, г.Тверь, ул.Желябова, 33. Тел. РИУ: (4822) 35-60-63.

Введение.

Глава

Теория выпуклых тел.

1.1 Опорная функция выпуклого множества.

Приближение выпуклых тел многогранниками.

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

Изопериметрические неравенства.

1.2 Симметризация и родственные ей преобразования выпуклых тел.

Симметризация Штейнера.

Симметризация Шварца.

Фигуры постоянной ширины.

1.3 Формализация экстремальных задач геометрии.

Задача о построении выпуклой фигуры Т7 е имеющей максимальную площадь поверхности Б(Р).

Задача о построении выпуклой фигуры Г е /^(Д,0) имеющей минимальную площадь поверхности Б(Р).

Задача о построении выпуклой фигуры Ре Р\ (ДД), имеющей максимальный объём У(Р).

Задача о построении выпуклой фигуры Ре ^ (дд), имеющей минимальный объём У(Р).

Глава

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

2.1 Аналитический метод решения задач оптимального управления.

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

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

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

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

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

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

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

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

Дискретная аппроксимаг[ия задачи.

Алгоритм построения решения методом внешних штрафных функг\ий.

Влияние вычислительных параметров на решение задачи.

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

Глава

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

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

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

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

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

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

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

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

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

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

Глава

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

4.1 Решение задачи о построении произвольного выпуклого тела максимальной площади поверхности.

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

4.2 Решение задачи о построении произвольного выпуклого тела минимальной площади поверхности.

4.3 Решение задачи о построении произвольного выпуклого тела максимального объема.

4.4 Решение задачи о построении произвольного выпуклого тела минимального объема.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации автора по теме диссертации в изданиях, рекомендованных ВАК России: Цветкова Е.Г. Задача о построении выпуклой фигуры вращения, обладающей минимальной площадью поверхности, с заданными ограничениями на ширину // Вестник ТвГУ. Сер. Прикладная математика. 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.

7. Цееткова Е.Г. Решение экстремальных задач геометрии методами оптимального управления и нелинейного программирования // Математика. Информационные технологии. Образование: Сборник научных трудов. Оренбург: ОГУ, 2008. С.103-106.

12