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

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

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

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

МЕТОДАМИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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), тогда , определяются по формулам:

,