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

Андреева Е. А., Цветкова Е. Г. Решение изопериметрической пространственной задачи методами нелинейного программирования // Молодой ученый. — 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)

Основные термины (генерируются автоматически): нелинейного программирования, экстремальных задач, численных методов, опорной функцией фигуры, задач нелинейного программирования, опорной функции, экстремальных задач геометрии, выпуклой пространственной фигуры, изопериметрических задач, оптимального управления, методами нелинейного программирования, Андреева Е.А, численных методов решения, опорной функции фигуры, решения задач, задача оптимального управления, направлении n, изопериметрических экстремальных задач, решения задач оптимального, решению задач нелинейного.

Обсуждение

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