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

Андреева Е. А., Цветкова Е. Г. Решение изопериметрической пространственной задачи методами нелинейного программирования // Молодой ученый. — 2009. — №11. — С. 18-22.

1. Введение. 

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

В настоящее время разработано большое количество численных методов решения задач оптимального управления и нелинейного программирования и работа по их созданию и совершенствованию продолжается [7]-[11]. Из широко известных численных методов можно выделить два основных типа: прямые и непрямые. В прямых методах поиск решения заключается в нахождении предельных точек минимизируемых (максимизируемых) последовательностей в пространстве исходных переменных. Среди них -  модификации метода проекции градиента, метод возможных направлений и другие. В методах второго типа решение задачи сводится к задачам безусловной минимизации. Данный переход, в частности, происходит вследствие изменения методов внешней и внутренней (барьерной) штрафной функции, метода модифицированной функции Лагранжа, метода с оценкой критерия и других. Вычислительные подходы к решению задач нелинейного программирования и поиска оптимального управления получили широкое освещение и систематизацию в работах Ю.Г.Евтушенко [8]-[10].

 

1. Формализация пространственных изопериметрических задач.

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

Плоскость   назовем опорной плоскостью выпуклого множества  в направлении n, функцию - опорной функцией фигуры  в направлении n.

            Введем сферические координаты в трехмерном евклидовом пространстве, тогда  , .

Положим  , , и назовем эту функцию опорной функцией фигуры  в соответствующем направлении.   

            Аналогично при введении полярных координат в  вводится понятие опорной функции плоской фигуры в : , .

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

Определим ширину выпуклой пространственной фигуры  в направлении n:

Диаметром выпуклой фигуры  назовем

.

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

.

Рис.1 Опорная функция выпуклой фигуры

 

Теорема [15]: Опорная функция выпуклой замкнутой регулярной фигуры в  почти всюду на множестве  удовлетворяет неравенству:

(1)

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

(2)

Опорная функция рассматриваемых фигур удовлетворяет граничным условиям:

(3)

 

2. Постановка задачи.

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

Для фигуры вращения формула (2) имеет вид:

(4)

ограничения на ширину:

,

(5)

условия выпуклости:

(6)

 В заданных направлениях  накладываются дополнительные ограничения на ширину:

(7)

где параметры ,  удовлетворяют условиям:

(8)

Не ограничивая общности рассмотрения, положим  в направлении толщины искомой фигуры:

(9)

Пусть далее - ширина фигуры в направлении t: , . Задача формализуется как задача оптимального управления, где роль функции управления играет радиус кривизны ,  [4].  Динамические ограничения и ограничение на управление следуют из условия выпуклости фигуры.

Задача (4)-(9) формализуется как задача оптимального управления с фазовыми и промежуточными ограничениями:

,

(10)

при динамических ограничениях:

   

(11)

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

(12)

фазовых ограничениях:

(13)

промежуточных

   

(14)

и граничных условиях:

         

(15)

           .

(16)

 

3. Решение задачи нелинейного программирования.

Применим к решению рассматриваемой задачи методы математического программирования.  Заметим, что система (11),(12) может быть представлена  в виде:

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

   ,

  .

Промежуточные ограничения описываются соотношениями:

.

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

(17)

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

 

(18)

(19)

, .

(20)

где   - матрица размерности ,  - вектор размерности ,

 

 (21)

В этом случае неизвестным является вектор значений траектории .  Применяя метод проекции градиента, проектируем антиградиент минимизируемой функции  так, что направлением спуска становится  вектор , где   - соответствующая матрица проектирования [14], - единичная матрица.  Результаты решения задачи приведены на рис.2-6, табл.1.

 

Рис.2. График функции ширины

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

Рис.4.  График функции радиуса кривизны

 

Рис.5. Вид сечения оптимальной фигуры

Рис.6. Вид оптимальной фигуры

Таблица 1.

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

Литература

1.                 Андреева Е.А. Оптимальное управление динамическими системами. Тверь, 1999.

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

3.                 Андреева Е.А., Надь Е. Двойственность в теории экстремальных задач. Международная школа по оптимальному управлению. Учебное пособие., Калинин, 1985.

4.                 Бляшке В. Круг и шар.- М.: Наука, 1951.

5.                 Болтянский В.Г., Яглом И.М. Выпуклые фигуры. М.: Наука, 1951.

6.                 Боннезен Т., Фенхель В. Теория выпуклых тел.- Берлин, 1934.

7.                 Васильев Ф.П. Лекции по методам экстремальных задач. М.:Московский университет, 1974.

8.                 Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

9.                 Евтушенко Ю.Г., Мазурик В.П. Программное обеспечение систем оптимизации.- М.: Знание, 1989.  48 с.

10.             Евтушенко Ю.Г., Жадан В.Г. Барьерно-проективные методы решения задач нелинейного программирования //ЖВМиМФ, 2002, Т.34.

11.              Дубовицкий А.Я., Милютин А.А. Задачи на экстремум при наличии ограничений. М., ЖВМиМФ, 1965, №3.

12.             Красноженов Г.Г. Применение численных методов к решению экстремальных задач геометрии. Диссертация канд. ф.м. наук. Тверь, ТвГУ, 2001.

13.             Мухачева Э.А.  Рациональный раскрой промышленных материалов, М., Машиностроение, 1984.

14.             Трифонов А.Г. Постановка задачи оптимизации и численные методы ее решения, М., Дело, 2002.

15.             Цветкова Е.Г. Построение оптимальных пространственных фигур методами нелинейного программирования. Диссертация канд. ф.м. наук. Тверь, ТвГУ, 2009.

 



[1] Работа выполнена при финансовой поддержке ведущих научных школ (НШ-5073.2008.1)

Обсуждение

Социальные комментарии Cackle