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

ВВЕДЕНИЕ

ГЛАВА I. Использование многогранных поверхностей в прикладных задачах.

§1. Аппроксимация областей достижимости многогранниками

§2. Представление информационных множеств невыпуклыми многогранниками

§3. Сжимающие отображения

§4. Проблема Штейнера

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

§6. Хранение информации

§7. Кристаллы

ГЛАВА II. Развертки многогранников

§1. Определения

§2. Многогранники, не допускающие натуральных разверток

§3. Доказательство всюду плотности многогранников, имеющих НР

ГЛАВА III. Задача о смятом рубле

§1. Введение

§2. Постановка задачи, определения и основные результаты

§3. Описание сетки складывания

§4. Реализация складывания цветка

§5. Завершение доказательства.

Реализация складывания большого квадрата.

§6. Наиболее простое складывание, увеличивающее периметр.

ГЛАВА IV. Сложность выпуклых стереоэдров.

§1. Формулировка.

§2. Доказательство.

Актуальность темы.

Диссертация посвящена развитию теории многогранных поверхностей для задач оптимизации.

Важнейшим объектом в задачах оптимизации является множество допустимых решений. Задачи представления и аппроксимации этого множества выпуклыми многогранниками хорошо изучены. Однако во многих прикладных задачах выпуклая аппроксимация поверхностей, ограничивающих множество допустимых решений, является грубой и уводит от существа задачи. Изучение многогранных поверхностей является сложной, малоисследованной математической задачей. Применение теории многогранных поверхностей в таких задачах как, например, задача Штейнера на криволинейной поверхности или задача Лотова о решении системы задач линейного программирования, приводит к качественно новым результатам. Более того, развитие аппарата многогранных поверхностей позволяет формировать математические модели и ставить оптимизационные задачи для многих новых и важных областей науки и техники.

Помимо положения в пространстве, многогранные поверхности имеют свойства внутренней геометрии: площадь; расстояние между точками, как длина кратчайшей кривой, соединяющей точки и лежащей на поверхности; углы между кратчайшими. По-разному расположенные многогранные поверхности в пространстве могут иметь одинаковую внутреннюю геометрию. Это поднимает следующие вопросы: когда две различные поверхности совпадают в смысле внутренней геометрии; можно ли непрерывно перевести одну поверхность в другую при условии выполнения различных ограничений (без самопересечений, без растягиваний, без разрывов и т.п.). Многогранные поверхности могут быть устроены достаточно сложно, даже в окрестности некоторой точки пространства. Они могут касаться сами себя сложным образом. Очевидно, что все это важно при решении прикладных задач, математические модели которых формируется с использованием многогранных поверхностей.

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

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

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

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

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

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

4. Задача Штейнера. Известная задача Штейнера имеет следующую формулировку: требуется соединить набор заданных городов сетью дорог, минимизируя общую длину этой сети. Существуют различные варианты этой задачи: общая, прямоугольная, на плоскости, на криволинейной поверхности. Основываясь на идеях развертки можно свести криволинейную задачу к существенно более простому плоскому случаю.

5. Решение набора задач линейного программирования. В многокритериальном методе достижимых целей возникает ситуация, когда нам нужно решить одновременно большое количество задач линейного программирования (ЛП) на одном и том же многограннике.

6. Складывание поверхностей. Складывание поверхностей, так же называемое теорией оригами имеет высокий прикладной потенциал. На практике часто встречается ситуация складывания чего-либо трехмерного из плоского листа. Гофрирование листов, складывающиеся антенны, телескопы, упаковка, буклеты И т.д.

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

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

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

Рис. 1: Натуральная развертка куба

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

Доказаны две теоремы, иллюстрирующие свойства разверток:

Теорема 11.1. Существует невыпуклая полиэдральная сфера с выпуклыми гранями, не допускающая ни одной натуральной развертки.

Основная идея теоремы изображена на рисунке 3. Многогранник, у которого нет натуральной развертки, получается добавлением треугольных пирамид в каждой из вершин некоторого выпуклого многогранника (например, куба). Эти пирамиды могут быть сколь угодно малыми. Одним из выводов из этой теоремы является то, что для невыпуклых многогранников обычная аппроксимация может не сохранять такое существенное свойство как натуральная развертка.

Теорема 11.2. Для любого выпуклого многогранника Р и его развертки Вороного существует е-близкий ему многогранник Р' в смысле расстояния Хаусдорфа такой, что он имеет натуральную развертку.

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

Рис. 2: Развертка Вороного для куба с центром в точке О

Рис. 3: Многогранник с выпуклыми гранями, не имеющий развертки. есть натуральная развертка.

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

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

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

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

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

Рис. 4: Цветок

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

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

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

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

Приводятся свойства многогранной поверхности, вытекающие из теоремы Кавасаки:

1. К каждой внутренней вершине сетки складывания подходит четное количество ребер.

2. Сумма углов вокруг этой вершины, взятых через один равна 180°.

Процессом складывания назовем гомотопию, непрерывно переводящую Р в Р', изометричную на каждом из многоугольников Рг

Процесс складывания называется реализуемым, если для процесса складывания существует сколь угодно близкая изотопия (уже не изометричная).

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

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

Рис. 5: Складывание треугольника радиальной "гармошкой" со сгибом.

Обоснован ¡юный метод складывания радиальной "гармошкой" со сгибом. Этот метод является новым, неизвестным ранее способом складывания и является обобщением "вывернутых складок" (Crimp folds). Берем произвольную фигуру. На границе выбираем вершину О, откуда проводится набор лучей под равными углами. Лучи разбиваются на четные и нечетные. На каждом луче отмечается точка. Расстояние от О до точек на всех четных (нечетных) лучах совпадает. Соединяя последовательно точки линиями, получаем ломаную - цветок (рис. 4). Теперь эту фигуру можно сложить, как показано на рисунке 5.

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

На основе этих методов доказывается следующая теорема:

Теорема III. 1: Для данного квадрата Р существует реализуемое складывание такое, что периметр сложенного многоугольника Р' превосходит любое наперёд заданное число.

Доказательство проходит в два этапа: Сначала предъявляется сетка складывания, доказывается её корректность. Показывается сложенная фигура Р и дается оценка снизу для периметра Р' в зависимости от параметров сетки складывания N и К. На втором этапе приводится процесс складывания и доказывается его реализуемость.

Эта теорема может быть положена в основу решения задачи, которую поставил В.И. Арнольд более 50 лет назад. Так же она известна как задача о салфетке Маргулиса в теории оригами. Представим себе прямоугольный лист бесконечно тонкой нерастяжимой бумаги. Согнув по определенным линиям, можно сложить прямоугольник в некоторый другой плоский многоугольник. Можно ли в результате таких сгибаний получить многоугольник большего, чем у исходного прямоугольника, периметра?

Исходя из теоремы III. 1 можно заключить, что ответом на этот вопрос утвердительный.

Процесс складывания алгоритмизуем и разработано соответственное программное обеспечение.

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

В четвертой главе в предыдущих главах были изучены такие важные свойства многогранных поверхностей, как "разрезаемость", "складываемость", "изгибаемость". В этой главе изучается ещё одно важнейшее свойство этих поверхностей - количество граней. Задачи такого типа имеют ярко выраженную прикладную направленность (например, создание кристаллических структур с новыми свойствами).

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

Теорема IV.!. Число с! - 1-граней выпуклого нормального с!-мерного стереоэдра не превышает: 2</(2</сП - 1/2) — 2 Эта теорема является небольшим улучшением для оценки Делоне-Сандаковой. Например, для й = 3 оценка улучшилась с 390 до 378.

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

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

2. Предъявлен пример невыпуклого многогранника с выпуклыми гранями, не имеющий натуральной развертки.

3. Доказана теорема о том что множество многогранников, имеющих натуральную развертку всюду плотно.

4. Продемонстрированы возможные направления использования этих методов в различных задачах, имеющих прикладное значение.

5. Улучшена оценка Делоне-Сандаковой о количестве граней стереоэдра. Научная новизна.

Научная новизна складывается из следующих результатов:

• Сформулировано определение многослойной многогранной поверхности и созданы методы работы с нею.

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

• Доказана теорема о всюду плотности многогранников, имеющих натуральную развертку.

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

• Доказано существование невыпуклых многогранников с выпуклыми гранями, не имеющих натуральную развертку.

• Улучшена оценка числа граней стереоэдра.

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

Заключение.

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

1. С.П. Оловянишников, Обобщение теоремы Коши о выпуклых многогранниках, Матем. сборник т. 18 (69):3 (1946), "об изгибании бесконечных выпуклых поверхностей".

2. A.B. Погорелов, Однозначная определенность выпуклых поверхностей, Труды матем. ин-та имени Стеклова АН СССР, т. 29 (1949).

3. В.И.Арнольд, Задачи Арнольда , Фазис, Москва (2000),1956-1

4. В.И.Арнольд, Избранное-60 М. , Фазис 1997

5. V.l. Arnold Arnold's Problems, Springer Phasis 2004, p.2

6. I.V. Yaschenko Make your dollar bigger now!!!, Math. Intelligencer 1998 20(2) 38-40

7. А.Д.Александров, Выпуклые многогранники, M.-JL, (1949).

8. Fukuda, Abstracts of the conference "Discrete Geometry", May 26-31, 1997, Mathematisches Forschunginstitut Oberwolfach, 27-28.

9. A.Schoenflies, Kristallsysteme und Kristallstruktur. Leipzig, 1891.

10. L.Bieberbach. Ueber die Bewegungsgruppen der Euklidischen Räume. Math.Ann.,1911, 70, 297-336.

11. L.Bieberbach. Ueber die Bewegungsgruppen des n-dimensionalen Euklidischen Raumes mit einen endlichen Fundamentalbreich., Gott.Nachr.,1910, 75-84.

12. Д.Касселс. Введение в геометрию чисел. Москва, 1969.

13. Б.Н.Делоне, Н.Н.Сандакова. Теория стереоэдров., Изв.АН СССР, (1961), 64, 28-51.

14. В. Delaunay, sur la sphere vide. Изв АН СССР, ОМЕН, JV« 6, (1934) 189 с.

15. Б.Н. Делоне, Геометрия положительных квадратичных форм, Успехи матем. наук, Вып. 3 (1937) Вып. 4 (1938)

16. Б.Н. Делоне, Доказательство основной теоремы стереоэдров, ДАН СССР 138, № б, (1961) 1270-1272.

17. М.И.Штогрин. Правильные разбиения Дирихле-Вороного для второй триклинной группы, Труды МИАН, 123, (1973).

18. N.Dolbilin, A.Dress, D.Huson. Two Finiteness Theorems for Periodic Tilings of d-Dimensional Euclidean Space , Discrete and Computational Geometry, 20:143-153 (1998).

19. P. McMullen. The volume of certain convex sets. Math.Proc.Cambridge Phil.Soc. 91 (1982) 91-97.

20. P.Engel. Geometric Crystallography. Dodrecht (1986).

21. E.Miller and I.Pak Metric combinatorics of convex polyhedra: cut loci and nonoverlap-ping unfoldings, preprint(2003)

22. J. O'Rourke, Folding and unfolding in computational geometry in Discrete and Computational Geometry (Tokyo 1998) Springer, Berlin 2000, pp 258-266.

23. G.M. Ziegler, Lectures on polytopes , New York, 1995

24. A.Tarasov. A new upperbound for the number of (d-l)-faces of a convex d-stereohedron. Abstracts of the Third Geometry Festival, Budapest (1996)

25. A.C. Тарасов, О сложности выпуклых стереоэдров, Математические заметки 1997 Т. 61 вып 5, с.797-800

26. A.C. Тарасов, Многогранники, недопускающие натуральных разверток , Успехи математических наук. 1999 Т. 54 вып 3, с.185-186

27. A.C. Тарасов Решение задачи Арнольда о "мятом рубле", Чебышевский сборник 2004, том 5. выпуск 1(9), с.174-187

28. Вороной Г.Ф. Исследование о примитивных параллелоэдрах, Собрание сочинений, 2, Киев (1952).

29. Minkowski Н., Dicontinuitätsbereich für Arithm/ Äquivalenz, J.reine Angew/ Math 129, (1905) 220-247.

30. Гильберт Д., Кон-Фоссен С., Наглядная геометрия, "Наука", Москва (1981), 344.

31. Е.С. Федоров, Симметрия правильных систем фигур. С.-Пб., (1890).

32. Bern, M. and Hayes, В. "The Complexity of Flat Origami." In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. Atlanta, GA, pp. 175-183, 1996.

33. Kawasaki, T. "On the Relation Between Mountain-Creases and Valley-Creases of a Flat Origami." In Proceedings of the 1st International Meeting on Origami Science and Technology (Ed. H. Huzita). Ferrara, Italy, pp. 229-237, 1989. Hull, T. "On the

34. Cauchy A sur les polytopes et polyèdres, seconde memuare J.Ecole Polytéchnique 1813- T.9 p.87-98

35. Hull, T. "On the Mathematics of Flat Origamis." Congr. Numer. 100, 215-224, 1994.

36. S.B. Myers. Connections Between Differential Geometry an Topology. Duke Math. J., v. 1, n. 3, p. 376-391, 1935 (I. Simply Connected Surfaces); v.2 n.l? p.95-103, 1936 (II. Closed Surfaces).

37. Кац И.Я., Куржанский А.Б. Минимаксная многошаговая фильтрация в статистически неопределенных ситуациях , Автоматика и телемеханика. 1978. Я2 11. С. 74-87.

38. Калман Р.Е. Идентификация систем с шумами Успехи мат. наук. 1985. Т. 40. № 4. С. 27-41.

39. Ширяев В.И. Алгоритмы реального времени оценивания и позиционного управления динамическими системами в условиях неопределенности , Материалы VIII НТК "Экстремальная робототехника". -СПб.: Изд-во СПбГТУ, 1997. С.253-263.

40. Куржанский А.Б. Задачи идентификации теория гарантированных оценок, Автоматика и телемеханика. 1991. JV® 4. - С. 3-26.

41. Кунцевич В.М. Определение гарантированных оценок векторов состояния и параметров линейных динамических систем при ограниченных возмущениях, Докл. АН СССР. 1986. №3. С. 567-570.

42. Калман Р.Е. Об общей теории систем управления, Тр. 1 Конгресса ИФАК. -М.: Изд-во АН СССР, 1961.- С. 521-547.

43. Покотило В.Г. Новый метод квазиоптимальной аппроксимации пересечения эллипсоидов. Препр., АН УССР. Ин-т кибернетики им В.М. Глушкова. Киев, 1990.- 18с.

44. Рокитянский Д.Я. Точное решение эллипсоидов, аппроксимирующих область достижимости одного класса линейных систем, Изв. РАН. Теория и системы управления. 1996. №1. С.16-22.

45. Buchta С., Müller J., and Tichy R. F. Stochastical approximation of convex bodies, Math. Ann. 1985. V.271(2). P. 225-235.

46. Fukuda K., Liebling Т. M., Margot. F. Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron, Computational Geometry. 1997. V8. -P.l-12.

47. Bárány I., Рог A. 0-1 polytopes with many facets, Advances in Math. 2001. V.161. P. 209-228.

48. M.R. Garey, R.L. Graham and D.S. Johnson The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics 32:835-850, 1977

49. Z.A. Melzak On problem of Steiner, Canada. Math. Bull. 4 (1961) 143-148

50. Лотов A.B., Бушенков B.A., Каменев Г.К. Черных О.Л. Компьютер и поиск компромисса. Метод достижимых целей. М.:Наука, 1997.

51. Lotov A.V., Bushenkov V.A. and Kamenev G.K., Interactive Decision Maps. Approximation and Visualization of Pareto frontier. Boston: Kluwer Academic Publishers, 2004.

52. Бурмистрова Л. В., Ефремов Р. В., Лотов А. В. Методика визуальной поддержки принятия решений и ее применение в системах управления водными ресурсами. Известия АН. Сер. Теория и Системы Управления, 2002, № 5.

53. Finn Ankersen,Shu-Fan Wu, Aleksander Aleshin, Alexander Vankov, Vladimir Voloshi-nov On Optimization of Spacecraft Thruster Management Function.