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

• Автор: Тарасов, Алексей Сергеевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 56 с. : 24 ил.

Содержание
ВВЕДЕНИЕ

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

в прикладных задачах.

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

многогранниками

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

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

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

5. Решение набора задач

линейного программирования

6. Хранение информации
7. Кристаллы
ГЛАВА II. Развертки многогранников
1. Определения
2. Многогранники, не допускающие
натуральных разверток
3. Доказательство всюду плотности
многогранников, имеющих НР
ГЛАВА III. Задача о смятом рубле
1. Введение
2. Постановка задачи, определения и
основные результаты
3. Описание сетки складывания
4. Реализация складывания цветка
5. Завершение доказательства.
Реализация складывания большого квадрата. 6. Наиболее простое складывание,
увеличивающее периметр.
ГЛАВА IV. Сложность выпуклых стереоэдров.
1. Формулировка.
2. Доказательство.
Заключение.
Литература


Целыо диссертации является разработка новых типов конструкций многогранных поверхностей, методов работы с ними и применении результатов для решения оптимизационных задач. Методы исследования. Для решения поставленных задач использовались методы дифференциальной геометрии и комбинаторной геометрии. В первой главе диссертации приведен обзор задач, где могут применяться методы работы с многогранными поверхностями. Аппроксимация областей достижимости многогранниками. В первом параграфе описывается основная связь задач оптимизации с многогранниками. Представление информационных множеств невыпуклыми многогранниками. Во втором параграфе приводится содержательный пример задачи, использующей невыпуклые многогранники. Этой задачей является маневрирование космического аппарата с помощью набора микро-двигателей. Сжимающие отображения. В данном параграфе описывается связь между сжимающим отображением и многослойными поверхностями. Приводятся примеры возможных использований этой связи. Например, метод компьютерного хранения сжимающих отображений. Задача Штейнера. Известная задача Штейнера имеет следующую формулировку: требуется соединить набор заданных городов сетью дорог, минимизируя общую длину этой сети. Существуют различные варианты этой задачи: общая, прямоугольная, на плоскости, на криволинейной поверхности. Основываясь на идеях развертки можно свести криволинейную задачу к существенно более простому плоскому случаю. Решение набора задач линейного программирования. В многокритериальном методе достижимых целей возникает ситуация, когда нам нужно решить одновременно большое количество задач линейного программирования (ЛГ1) на одном и том же многограннике. Складывание поверхностей. Складывание поверхностей, так же называемое теорией оригами имеет высокий прикладной потенциал. На практике часто встречается ситуация складывания чего-либо трехмерного из плоского листа. Гофрирование листов, складывающиеся антенны, телескопы, упаковка, буклеты и т. Со складыванием поверхностей связан ряд оптимизационных задач: использовать для создания определенной трехмерной конструкции плоский многоугольник минимальной площади, сделать складывание с минимальной суммарной длиной линий сгиба, сложить данный многоугольник в трехмерную фигуру с экстремальными свойствами (максимальный объем, максимальная площадь определенной проекции и т. Примером может служить задача об упаковке космического телескопа. Необходимо сложить без растяжений, разрывов и склеек определенный плоский многоугольник (плоскую линзу Френеля) в компактную область с цилиндрическим форм фактором, так чтобы суммарная длина линий сгиба была минимальной. Во второй главе описано решение двух задач, связанных с разверткой, особым типом многогранной поверхности - разрезанной поверхностью многогранника. Еще один тип разверток - развертка Вороного, которая образуется следующим образом: возьмем некоторую точку на поверхности многогранника - О. Теперь определим множество разрезов - все такие точки X, для которых существует две и более одной кратчайших ОХ. Эта область является графом, разрезав по которой мы и получим развертку Вороного. Теорема II. Существует невыпуклая полиэдральная сфера с выпуклыми гранями, не допускающая ни одной натуральной развертки. Основная идея теоремы изображена на рисунке 3. Многогранник, у которого неї' натуральной развертки, получается добавлением треугольных пирамид в каждой из вершин некоторого выпуклого многогранника (например, куба). Эти пирамиды могут быть сколь угодно малыми. Одним из выводов из этой теоремы является то, что для невыпуклых многогранников обычная аппроксимация может не сохранять такое существенное свойство как натуральная развертка. Теорема ІІ. Для любого выпуклого многогранника Р и его развертки Вороного существует 6-близкий ему многогранник Р* в смысле расстояния Хаусдорфа такой, что он имеет натуральную развертку. Принцип доказательства этой теоремы основан на следующем. Построим развертку Вороного на многограннике Р. Теперь подразобьем все грани многогранника Р, по линиям развертки Вороного. Рис. Рис.