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

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

Синицын Сергей Иванович г-р - 0Д 4

2 2 1'Л 11Г.1 -

ГЕОМЕТРИЧЕСКИЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ ДЛЯ РАЗВЕТВЛЕННЫХ ТЕХНИЧЕСКИХ СЕТЕЙ

Специальность 05.01.01 - Прикладная геометрия и инженерная графика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора технических наук

Нижний Новгород 2000

Работа выполнена в

Нижегородском государственном техническом университете и Нижегородском государственном архитектурно-строительном

университете

член-корреспондент РАН

Научный консультант

Кондратьев В.В.

Официальные оппоненты

доктор физико-математических наук, профессор Арансон С.Х. доктор физико-математических паук, профессор Шевченко В.Н.,

Ведущая организация - Нижегородский филиал Института машиноведения

РАН (НФ ИМАШ РАН)

Защита состоится 14 ноября 2000 года в 15 часов на заседании диссертационного совета Д 064.09.03 при Нижегородском государственном архитектурно-строительном университете по адресу: 603600, Нижний Новгород, ул. Ильинская, 65, ауд. 5-202

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного архитектурно-строительного университета

доктор технических наук,

профессор Кучуганов В.Н

Автореферат разослан 12 октября 2000 г.

Ученый секретарь диссертационного совете к.т.н., доцент

В.И. Дергунов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность.

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

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

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

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

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

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

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

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

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

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

Цель и задачи исследования.

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

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

2. Исследование простых наборов заданных точек для выявления общих закономерностей.

3. Разработка общего алгоритма для произвольного набора точек.

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

4.1. Введения весовых коэффициентов,

4.2. Расположения точек в вершинах правильных или монотонных многоугольников,

4.3. Структурной регулярности -заданного набора точек в виде решетки.

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

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

Научная новизна заключается в следующем:

о в проведенных численных и аналитических исследованиях простейших наборов исходных точек, позволивших доказать базовые теоремы для задачи Штейнера и определить геометрические характеристики, которыми обладают деревья Штейнера (ДШ);

• в определении инвариантных геометрических алгоритмов, позволяющих строить минимальное дерево Штейнера;

• в общем методе построения ДШ для произвольного набора точек, позволившем объединить этапы генерации деревьев и вычисление минимального из них;

• в исследовании специальных случаев задачи Штейнера: введении весовых коэффициентов, регулярности структуры, правильности и монотонности многоугольника;

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

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

Практическая ценность заключается:

« в возможности получения минимальных по длине или стоимости изготовления технических систем;

> в возможности проведения параметрической оптимизации состава разветвленной трубопроводной системы;

• сокращении сроков получения данных, необходимых для проектирования геометрии каналов произвольной формы, в которых движутся газы и газовзвеси при дозвуковых и сверхзвуковых скоростях;

• в возможности исследовать разветвленные трубопроводные системы любых структур, в которых осуществляются стационарные и переходные течения несжимаемой жидкости, путем использования разработанных прикладных программ для персонального компьютера. Исследование проводилось по фундаментальной НИР «Разработка теоретических основ, алгоритмов и программ геометрии и графики для параллельных технологий проектирования» (ГР № 01970004538, Нижегородский государственный архитектурно-строительный университет), а также по договорам с различными организациями.

Реализация в промышленности.

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

Апробация работы. Положения и выводы диссертации докладывались и получили положительную оценку:

1. На 2 международных конференциях:

1.1.По методу крупных частиц в НИИ автоматических устройств, Москва, 1993г.

1.2.По компьютерной геометрии и графике «КОГРАФ», НГТУ, Н. Новгород, 1996г.

2. На 3 Всесоюзных конференциях:

2.1. Институт физико-технических проблем энергетики АН ЛитССР, Каунас, 1987г.

2.2.НИИ автоматических устройств, Москва, 1987г., 1989г.

3. На 5 Всероссийских конференциях по компьютерной геометрии и графике «КОГРАФ», НГТУ, Н.Новгород, 1991, 1993, 1997, 1998, 1999.

4. На 1 Всероссийской научно-технической конференции «Компьютерные технологии в науке, проектировании и производстве» НГТУ, Н. Новгород, 1999г.

5. На Всероссийском семинаре-совещании заведующих кафедрами графических дисциплин НГАСУ, Н. Новгород, 2000г.

6. На всесоюзном семинаре НТО им. акад. А.Н. Крылова (Центральное правление НТО им. акад. А.Н. Крылова, Ленинград, 1988г.);

7. на 2 областных конференциях молодых ученых (ГСХИ, Горький, 1986г.; ГПИ, Горький, 1987г.).

8. На областном семинаре НТО им. акад. А.Н. Крылова (ГПИ, Горький, 1988г.).

9. На 2 научно-технических конференциях профессорско-преподавательского состава, аспирантов и студентов «Строительный комплекс», НГАСУ, Н. Новгород, 1995, 1996.

Публикации. По теме диссертации опубликовано 34 работы, в том

числе получен патент РФ.

Объем работы. Диссертация состоит из введения, шести разделов,

заключения с выводами и приложений и содержит 220 страниц. Список

использованных источников включает 155 наименований.

Основные результаты, выносимые на защиту:

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

2. Алгоритм, обеспечивающий максимальную точность определения координат точки Штейнера.

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

4. Аналитический метод определения свойств дерева Штейнера.

5. Геометрические методы построения ДШ.

6. Формулы, позволяющие оценивать эффективность построения дерева Штейнера до самого построения.

7. Результаты решения задачи об определении наилучшей четвертой точки при трех заданных.

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

9. Рекурсивный способ построения ДШ для регулярных структур.

10.Цепной метод для примыкающих друг к другу четырехугольников.

11 .Общий метод построения дерева Штейнера для произвольного набора точек.

12.Нестационарный метод гидравлического расчета разветвленных трубопроводных систем для параметрической оптимизации при проектировании и возможности исследования схем управления.

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

СОДЕРЖАНИЕРАБОТЫ

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

В первом разделе анализируется современное состояние и постановка задач исследования.

При этом анализируются подходы, возникающие при поиске деревьев минимальной длины, одним из которых является построение дерева Штейнера (ДШ), приводится история возникновения и развития путей решения задачи Штейнера. Указываются различные модификации ее. Анализируются существующие зарубежные алгоритмы для построения дерева Штейнера. Так как задача Штейнера NP-трудна, то приводится современный взгляд на теорию сложности и подходы для ее преодоления (теория NP-полноты).

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

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

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

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

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

КОПП(Р,А) = РЗ(Р) ; КОМОД(Р,А) = D3(P) , (1)

ПП(Д) MOD(A)

где: БЗ-общая длина ДШ, состоящего из трех отрезков;

ПП- величина полупериметра треугольника;

MOD- длина минимального остовного дерева.

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

Определяется набор треугольников для исследования. Для этого проводятся итерации углов треугольника с шагом 10°. Дополнительно в набор

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

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

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

В декартовой системе координат определим:

• единичный квадрат, такой, что любая принадлежащая ему точка удовлетворяет условиям: 0 < х < 1;

0<у < 1.

• модельный треугольник 123, заданный своими углами а,, а2, а3.

Будем полагать: сц > а2 > аз

Алгоритм состоит из 3 шагов.

1.ШАГ) совместим наибольшую сторону модельного треугольника L13 с диагональю единичного квадрата, проходящей через (0,0),

Определим координаты точки 1' как точки пересечения двух прямых 1' 3 и 1' 2 по формулам:

l-tg(a2 +45°) tg(45°-a3)-tg(a2+45°) (2)

У у = tg(450-aj)-X|<. Пока 0° < а2 < 45°, мы будем получать точку 1' внутри единичного квадрата. Осуществим присвоение 1'=1, и на этом алгоритм заканчивается.

2. ШАГ) Если координаты точки 1' оказались вне единичного квадрата (х)'>1), то необходимо повернуть весь треугольник 1'2'3 на угол 9 таким образом, чтобы он вписался в квадрат со стороной m>!. При вращении точки вокруг начала координат существуют зависимости:

х" = x'-cos0-y'-sin0,

(3)

у" = x'-sin0 + y'-cos0, здесь: х', у' - начальные координаты точки, х\у'- координаты после поворота.

Условием вписывания треугольника в квадрат со стороной m будет: Х,- = У2* -

Подставим в это условие формулы вращения (3), учтем, что обе координаты точки 2' равны единице:

х,- • cos0 - у,. • sin 0 = sin 0 + COS0 ,

откуда

xr-l 9 = arctg —--

Ur + U

(4)

Значение угла поворота 0 необходимо подставить в формулы вращения (3) для вычисления координат точек 1" и 2".

3. ШАГ ) Разделим полученные координаты на ш = у2- =- хг . Тем самым мы осуществим операцию подобия с коэффициентом т:

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

Далее приводятся особенности алгоритма численного исследования по поиску минимальной точки.

Первая особенность заключается в том, что для такой простой фигуры, как треугольник, существует всего 3 остовных дерева. Ведь согласно теореме Кэли число различных остовных деревьев для N опорных точек определяется по формуле Nn"2. Их легко вычислить непосредственно и, выбрав минимальное из них, определить тем самым МОД.

Вторая особенность состоит в том, что нам нецелесообразно рисовать изолинии КОМОД вне опорного треугольника. Это требует использования процедуры по определению принадлежности точки треугольнику. Автором был использован метод, связанный с вычислением определителя. Он с геометрической точки зрения представляет удвоенную площадь треугольника ABC с учетом знака. Причем, если знак этой площади положителен, то точка А лежит слева от прямой ВС. В другой интерпретации—это соответствует последовательному обходу ABC против часовой стрелки. Если площадь отрицательна, то А расположена справа от ВС, что приводит к обходу по часовой стрелке. Если определитель равен нулю, то точка А принадлежит прямой ВС. Использование этого метода требует введения логической переменной, которая оценивает знаки площадей треугольников, образуемых текущей расчетной точкой Р со сторонами исходного треугольника ABC. При этом гарантированно обеспечивается, что точка будет внутри треугольника, если все площади либо положительные, либо отрицательные, что зависит от собственной ориентации ABC.

Третья особенность состоит в особом алгоритме по определению координат ТШ. Известно, что существует множество надежных алгоритмов для решения экстремальных задач (покоординатного спуска, движения по градиенту и т.д.). Но в каждом из них существует проблема определения точности, при достижении которой следует останавливать расчет. Приведенный ниже алгоритм является далеко не оптимальным по быстродействию, но он обладает способностью добиваться максимальной точности, которая может

(5)

у2=1.

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

Вначале равномерно покроем единичный квадрат матрицей из 1Ы1 точек. Для каждой из них вычислим ОЗ. Определим точку, для которой ЭЗ минимальна. Координаты ее ХШд УШД получаются путем деления индексов 1 и j на 10. Мы достигли представления координат ТШ с точностью до 0,1. Затем применяем цикл, в котором используем точку, обеспечивающую минимальное значение ВЗ, в качестве центра вспомогательного квадрата со стороной 0,2. Теперь покрываем его матрицей из 21-21 точек и определяем ту из них, которая обеспечивает тт(ОЗ). Координаты ее определяются по формулам:

ХШС= ХШд+0,01 -(¡-10);

УШС= УШД+0,01-0-10).

Тем самым мы достигли сотых долей в представлении координат точки Штейнера. При втором прохождении цикла мы получим точность решения

0.001.и т.д. Критерием остановки цикла служит условие получения хотя бы двух точек, имеющих одинаковое значение тш(Т)3). Это означает, что, ввиду дискретного представления действительных чисел в ЭВМ и ошибок округления при вычислении ЭЗ, достигнута максимальная точность представлена координат ТШ.

Реализация алгоритма численного исследования приведена для МаШсас! 7. Точность полученных результатов находится в интервале 7-14 десятичных цифр. В диссертации приведены все 36 вариантов, здесь только 4.

Делаются выводы:

1. Точка минимального значения 03 всегда одна. Причем других локальных минимумов не встречается для всех исследованных треугольников.

2. Пока наибольший угол в треугольнике остается меньшим 120°, точка Штейнера находится внутри треугольника. А если он равен или больше 120°, ТШ совпадает с вершиной тупого угла. Тем самым ДШ, состоящее из трех отрезков, вырождается в минимальное остовное дерево (МОД), состоящее из двух отрезков (КОМОД=1).

3. Точка Штейнера, расположенная внутри треугольника, всегда обеспечивает меньшую величину ДШ по сравнению с МОД.

4. Наименьшим КОМОД=л/3/2 обладает равносторонний треугольник, (выигрыш составляет 13,4%). Чем ближе треугольник к равностороннему, тем меньшим КОМОД он обладает.

5. Любая точка внутри равностороннего треугольника позволяет построить дерево меньшее, чем МОД. Любые другие треугольники обладают этим свойством только в области расположенной рядом с наибольшим углом треугольника.

6. Любой равнобедренный треугольник обладает наименьшим КОМОД для своего класса.

Рис 1. Примеры результатов численного исследования

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

0.4 0.5 0.6 0.7 Рис. 2.

Получив координаты точки Штейнера и изолинии ЭЗ, далее проводим аналитический поиск положения точки Штейнера.

Для этого будем искать минимум функции 03=Р1+Р2+Р3 (рис. 3), как это принято в математическом анализе, приравняв нулю частные производные по координатам. В результате получим следующую систему уравнений:

где:

X

Рис. 3.

ЭХ

¡=1

и

¡=1 ц

5рз з (у. -

зу ¿1 и

¡=1 ^

(6)

I - номер ребра ДШ (соответствует номеру вершины треугольника);

Д - разница концов соответствующих координат;

Ь - функция длины отрезка.

Непосредственное решение системы при произвольном значении координат вершин треугольника наталкивается на значительные вычислительные трудности. Поэтому попробуем произвести замену переменных. Заметим, что в данном случае, ДШ однозначно определяется не только координатами ТШ, но и углами, обозначенными на рис. 3: а, 3, у.

АХ

Из курса аналитической геометрии известно, что, например:

ДХ2ДХ, + AY,AY,

cos у =---!-^—L (7)

L2LJ

Преобразуем систему (6). Помножим первое уравнение системы на AY,

, а второе на —- и сложим эти уравнения. В результате получим: Lj L]

АХ? АХ,АХ, АХ3АХ, AY,2 AY2AY, AY3AY,

-L +-2-i_ +-i-L + —J_ +-i-L +-á-L

lt L2L,

L3L,

l2l,

L3L,

(8)

Очевидно, что сумма первого и четвертого членов уравнения равна 1. Сумма второго и пятого членов уравнения определяет cos у. Оставшиеся члены по аналогии - это cos р.

Повторим подобную процедуру еще 2 раза, меняя индекс в

AX¡ AYj _

дополнительных сомножителях-L и —1. В результате получим следующую

Lj L¡

систему уравнений:

Icosot + cosP = -l;

cos а + cos у = -1; (9)

cos|5 + cos7 = -l;

Решением системы (9) будет: а = р = у = 2я/3. (10)

Таким образом, все углы, примыкающие к ТШ в треугольнике, равны 120°.

Рис. 4

Рис. 5

Получив этот результат, предлагаем два геометрических метода построения ДШ в треугольниках:

• с использованием дуг (рпс.4)

• с использованием прямых (рис.5)

Построим на двух любых сторонах треугольника ABC (рис. 4) дуги величиной 120°. Для определения центров дуг О] и 02 проведем вспомогательные прямые под углами 30° к сторонам треугольника. Пересечение этих дуг определит искомую точку Штейнера S.

Второй метод состоит в том, что на любых двух сторонах исходного треугольника ABC (рис. 5) необходимо построить равносторонние треугольники ABFi и CBF2 внешним образом. В пересечении отрезков CFi и AF2 находится искомая ТШ S.

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

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

Для любого треугольника ABC: SA+SB+SC = CF|= AF2.

Получены зависимости, позволяющие оценить эффективность построения ДШ в произвольных треугольниках еще до самого построения:

КОМОД(а,р)^ ^s'n2(a)+sin2(p)~2sin(a) sin(P)cos(240°-«-P) ? (П)

sin(a) + sin(¡5)

здесь: а, р - два любых внутренних угла треугольника.

В третьем разделе исследуется задача Штейнера для четырех произвольно расположенных точек.

Решен вопрос о структуре ДШ и количестве точек Штейнера для

разнообразных конфигураций исходного набора узлов. Доказывается методом, аналогичным описанному с использованием формул 6-10, что полное ДШ включает в -себя 2 точки Штейнера, к каждой из которых подходят по 3 ребра дерева Штейнера, образующие между собой угол 120°. Исследуются варианты, приводящие к вырождению ДШ. Предложены геометрические способы нахождения точек Штейнера: с использованием дуг (рис. 6), с использованием прямых (рис. 7), диагональный метод (рис. 8).

Рис. б. Построение дерева Штейнера с использованием дуг

На противоположных сторонах исходного четырехугольника ABCD (рис. 6) строим равносторонние треугольники ABE и DCF. Опишем около каждого треугольника окружность. Соединим точки Е и F отрезком. Точки пересечения EF и окружностей определят ТШ G и Н. Докажем это. Углы EGB и EGA опираются на дуги 120°, и на основании теоремы о вписанном угле они равны 60°, следовательно, углы BGH и AGH равны 120°. Аналогично доказывается равенство углов, примыкающих к точке Н.

Доказывается теорема (рис. 6): сумма пяти отрезков ДЩ равна длине отрезка EF, т. е. AG+BG+GH+CH+DH=EF. (12)

Для доказательства достаточно показать BG+GA=EG. Через точку Е проведем диаметр окружности ЕК, обозначим центр этой окружности О. Угол KEG обозначим а. Угол EGK прямой, т.к. он вписанный и опирается на диаметр окружности, тогда EG = ЕК cosa = 2R cosa. Угол KOG=2a на основании теоремы, что вписанный угол меньше центрального в 2 раза. Угол АОК=60°, т.к. он центральный и опирается на дугу KGA=60°.Таким образом, угол GOA=60° - 2a. Подобным образом доказывается, что угол GOB=60°+2a. На основании теоремы косинусов из треугольника GOA получим: GA = 2R sin(30°-a); а из треугольника GOB: GB = 2Rsin(30°+a). После элементарных тригонометрических преобразований получим GA+GB = 2R cosa. Аналогичным образом доказывается, что CH+HD=HF. Теорема доказана.

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

На рис. 7 предлагается метод, использующий только пересечение отрезков. Построим на стороне АО внешним образом равносторонний треугольник АОР. Затем, построенную точку И используем для построения еще 2 равносторонних треугольников РВЬ и БМС. Пересечение отрезков МВ и ЬС

определит первую точку Штейнера 8. Вторая точка Штейнера Т может быть построена, если из точки О провести луч параллельно МВ, а из точки А - луч, параллельный ЬС. Пересечение этих лучей и даст искомую точку Т.

М

Рис. 8.

Покажем на примере четырехугольника ABCD, как следует применять диагональный метод (рис. 8)

На диагонали АС построим равносторонний треугольник АСЕ, он залит серым цветом. Осуществим плоско-параллельное движение этого треугольника без вращения таким образом, чтобы точка Е совпала с точкой D. Тем самым будет построен треугольник FDG, так же залитый серым цветом. Отрезок GB определяет направление ветви BS дерева Штейнера (ДШ) четырехугольника ABCD. При этом длина отрезка GB равна суммарной длине ДШ: GB=BS+SC+ST+AT+DT (13)

Чтобы определить точное положение точки S можно построить дугу 120° на отрезке ВС, либо просто построить угол 120° BSC. Мы укажем альтернативный способ определения точки S, продолжая использовать диагонали четырехугольника ABCD.

На другой диагонали BD построим треугольник BDN. На рис. 8 он залит точками. Осуществим плоско-параллельное движение этого треугольника без вращения таким образом, чтобы точка N совпала с точкой А. Тем самым, будет

построен треугольник ALM, так же залитый точками. Отрезок МС, пересекая GB, и определит искомую точку S. (Заметим, что величина MC=GB).

Вторая точка Штейнера Т может быть построена путем пересечения отрезков АТ и DT. АТ проводим параллельно МС, a DT - параллельно BG.

При использовании диагонального метода целесообразно осуществлять еще одно построение, которое позволит доказать нам (13). Сделаем зеркальное отражение треугольника АСЕ относительно диагонали АС. В том месте, где BG пересекает сторону этого зеркального треугольника, проведем отрезок PQ параллельно ЕС. Точка R получается при пересечении PQ и диагонали АС. Сразу видно, что длина отрезка ВР равна ДШ треугольника RBC, а длина отрезка QD - ДШ треугольника RDA. Но так как QPGD - это параллелограмм, то QD=PG, а значит (13) доказано. Отметим, что подобное построение можно осуществить и для другой диагонали (отрезок XY и точка Z).

Соединение точки F с точкой В и точки L с точкой С позволяет построить второе дерево Штейнера, которое существует для четырехугольника. Но сравнение величин отрезков GB и FB позволяет еще до построения выбрать меньшее из этих двух деревьев. Но более простой способ выбора меньшего из двух деревьев Штейнера позволяет сделать следующая теорема о прямом угле между диагоналями четырехугольника.

X3=-(-J3b»c)/2 В четырехугольнике можно

Например: X, = а + АВ соб(1 80 - 60 - ОАВ);

X, = а + АВ (соб120 собОАВ + втШ этОАВ); XI = а + АВ (-а / 2АВ + -Л Ь / 2АВ); Х,= (73 Ь +а)/2. Остальные координаты показаны на рис. 9. Подставив их в выражение, определяющее длину отрезка 1/=ДХ2+ДУ2, получим:

Ь212=Ь2з4=АС2+В02+л/з АС ВО. Теорема доказана.

Y, « (Вс+Ь)/2

построить два дерева Штейнера (ДШ). Покажем, что, если диагонали четырехугольника перпендикулярны, то оба ДШ равны по величине. Для доказательства расположим все вершины четырехугольника А, В, С, О на осях декартовой системы координат. Точка пересечения разбивает диагонали на отрезки а, Ь, с, с1 (рис. 9). На каждой из сторон построим равносторонние треугольники. Величина одного ДШ (как было показано выше) равна отрезку 12, а другого - 34. Покажем, как вычисляются координаты концов этих отрезков.

Рис. 9

Аналитически исследуется влияние параметров ромбов и параллелограммов, на возможность построения и эффективность ДШ.

На примере параллелограммов покажем результат параметрического исследования. В качестве параметров используются отношение сторон а и угол между сторонами а (рис. 10)

Опуская не трудные, но объемные выкладки, приведем графический результат и главные выводы.

Рис. 11. КОМОД(а.а) для параллелограммов.

1. Наилучшим параллелограммом с точки зрения. возможного построения дерева Штейнера является ромб.

2. Лучшим ромбом является тот, у которого угол между сторонами составляет 60°.

3. Для всех параллелограммов минимальное значение дерева Штейнера достигается у такого, у которого диагональ равна большей стороне.

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

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

Сначала определим переменные, используемые пользователем. Базовый треугольник, задаваемый своими углами (в общем случае произвольными, но автором использован тот же самый набор из 36 треугольников), вписывается в единичный квадрат (0,0; 0,1; 1,1; 1,0). Вершины треугольника обозначаются по степени убывания внутренних углов (1,2,3).

Выбирается поле (прямоугольное или квадратное), внутри которого будут располагаться исследуемые точки, каждая из которых обозначается (4). Экспериментальным подбором определились границы поля: у _ у — —? • у = y = 3

Amin 1 min > in.ix 1 max •

Задается количество четвертых точек, равномерно расположенных в исследуемой области. Около 20 минут на процессоре Pentium 200 МГц требуется для исследования одного варианта, включающего обработку 250x250 = 62500 точек. Такое разрешение достаточно, чтобы выявить все экстремальные точки.

Работа алгоритма заключается в следующем:

1. Вначале определяется относительное расположение исследуемой четвертой точки относительно базового треугольника. При этом различается 19 случаев относительного расположения прямых, в которых лежат его стороны и четвертой точки, сведенных к 4 вариантам:

a). Точка лежит в такой области, что выпуклая оболочка включает в себя все четыре точки.

b). Точка лежит в области, которой соответствует выпуклая оболочка из трех точек, внутри которой располагается 4 точка (триангуляция состоит из трех треугольников).

с). Точка принадлежит прямой, на которой находится один из отрезков базового треугольника. В этом случае триангуляция будет включать только два треугольника, с!). Четвертая точка совпадает с вершиной заданного базового треугольника. Триангуляция состоит из единственного треугольника.

2. В случае расположения точки по варианту а) определяются четыре типа деревьев и вычисляются их длины:

a) полное дерево Штейнера (ПД111) с двумя точками Штейнера (всего 2);

b) сумма двух диагоналей (всего 1);

c) ДШ трех любых точек с оставшейся минимальной стороной (всего 4);

с!) минимальное остовное дерево (всего 1).

3. Из этих четырех типов деревьев путем сравнения между собой определяется минимальное дерево.

В остальных трех вариантах исключаются типы а) и Ь) ввиду невозможности их существования.

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

Полный анализ всех 36 полученных графиков позволяет сделать следующие выводы (на рис. 12,13 приведены 2 варианта):

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

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

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

4. Ни в одной исследуемой точке во всех 36 вариантах не оказалось, что пересечение диагоналей — это меньшее из деревьев, даже в случае отсутствия ПДШ.

5. Наилучшим базовым треугольником по интегральным характеристикам является равносторонний треугольник.

6. Наличие симметрий в базовом треугольнике - всегда благоприятный фактор. Но общая зависимость трудно поддается формализации.

7. В случае произвольного выбора четвертую точку следует располагать на срединном перпендикуляре к сторонам базового треугольника. Это соответствует добавлению равнобедренного треугольника к базовому. При

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

8. Точка локального минимума коэффициента КОМОД находится, как правило, в точке фокуса (вершине построенного на стороне внешним образом равностороннего треугольника). Исключениями из этого правила являются:

a) треугольники, близкие к прямоугольным равнобедренным, требуют отдельного поиска в области симметрии;

b) четырехугольники, слабо искажающие базовый равносторонний или близкие к нему треугольники;

c) четырехугольники с большими тупыми углами, большими 120°. Для них дополнительно требуется рассматривать точки вершин равносторонних треугольников, построенных внутренним образом.

9. Если не учитывать исключение 4 Ь), то наилучшим четырехугольником является ромб с углом 60° между сторонами. При не самом минимальном значении коэффициента КОМОД=0.88... достигается глобальный максимум абсолютного выигрыша в длине ДШ по сравнению с МОД.

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

Рассмотрены новые возникающие ограничения при введении весовых коэффициентов (например, стоимостей изготовления единицы длины трубопровода). Сначала методом, аналогичным описанному в формулах (6-10) выводятся эти ограничения, а затем показывается, что углы в дереве Штейнера с весовыми коэффициентами отличаются от 120° и зависят только от весовых коэффициентов для любого треугольника.

Предложены рекурсивный метод построения ДШ для регулярных структур (рис. 14) и цепной метод для монотонных многоугольников (рис.15). Отдельно исследовались ДШ в правильных многоугольниках. Приведены все варианты полных деревьев Штейнера для многоугольников, число сторон которых меньше 9 (рис. 16-23). Построение осуществлялось вручную с помощью Автокада.

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

в Только симметричные элементарные ячейки в виде ромбов (квадрат-это тоже ромб) позволяют эффективно использовать рекурсивный метод.

• Наилучшей элементарной ячейкой является ромб с углом 60°, следовательно, при возможности выбора именно такие структуры следует организовывать.

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

Цепной метод является дальнейшим развитием диагонального метода построения ДШ в четырехугольнике (рис. 8). Покажем на примере серии

примыкающих друг к другу четырехугольников использование этого метода (рис. 15).

Даны три примыкающих друг к другу четырехугольника ABCD, DCKN, NKLM. На сторонах АВ и LM построим равносторонние внешние треугольники MLF и ABV вместе с описывающими их окружностями. На диагонали CD построим равносторонний треугольник CDE (он залит кирпичной заливкой) и перенесем его параллельно без вращения так, чтобы точка Е совпала с точкой V, построив треугольник GHV (залит аналогично). На диагонали KN построим равносторонний треугольник KNI (он залит точечной заливкой) и перенесем его параллельно без вращения два раза так, чтобы точка I совпала с точкой G и точкой Н, построив два треугольника SR.G и РОН (залитые аналогично). Соединяя точку. F с каждой из четырех точек О, Р, R, S, мы имеем возможность построить 4 различных полных ДШ. Покажем метод построения одного из них, соединяя точку F с точкой R. В том месте, где этот отрезок пересечет описанную около треугольника MLF окружность будет первая точка Штейнера (ТШ). Все дерево изобразим линиями, состоящими из точек.

Отрезок FR пересекает зеркально отраженный треугольник NXK в точке g, через которую проведем отрезок gf параллельно KL. Опишем окружность вокруг равностороннего треугольника с точками g, К, и точкой пересечения KN и gf. Пересечение отрезка FR с этой окружностью определит вторую точку Штейнера. Соединим точку f с точкой G. В том месте, где он пересечет окружность, описанную около точек N, f и точки пересечения KN и gf, будет третья ТШ. Отрезок fG при пересечении зеркально отраженного треугольника DUC строит точку j, из которой параллельно DE строим отрезок ji. Затем алгоритм повторяется аналогично треугольнику KN1, где отрезок ji соответствует отрезку gf. То есть, строим две маленькие окружности. В пересечении нижней окружности и отрезка fG получается четвертая ТШ. Точку i соединяем с точкой V. В том месте, где этот отрезок пересекает верхнюю из маленьких окружностей, получается пятая ТШ, а в том месте, где он пересекает окружность ABV — последняя шестая точка Штейнера.

Естественно, что этот алгоритм легко обобщается на любое количество примыкающих друг к другу четырехугольников.

Затем проводилось исследование правильных многоугольников. Правильные многоугольники обладают тем свойством, что при исследовании их можно сильно ограничить количество вариантов построения ДШ, ввиду полной симметричности получаемых решений. С помощью Autocad, используя дальнейшую модификацию метода построения ДШ с использованием дуг (рис 6.), автором полностью были исследованы путем геометрического построения все возможные варианты существования полного дерева Штейнера в правильных многоугольниках с числом сторон от 4 до 8 и, выборочно, некоторые варианты с большим числом сторон. (Подробное исследование треугольников, включая равносторонний, приведено в разделе 2. Напомним,

что для него КОМОД=0,866...). Отметим, что с ростом числа сторон существенно возрастает число отброшенных вариантов, ввиду невозможности построить ДШ.

Полученные результаты приведены на рис. 16-23. Анализируя полученные результаты, делаем следующие выводы:

« Эффективное построение ДШ (КОМОД<1) возможно для правильных

многоугольников с числом сторон, не превышающих 5. • Увеличение числа сторон многоугольника приводит к возрастанию КОМОД.

Раздел заканчивается общим алгоритмом построения дерева Штейнера для произвольного набора точек.

ТЕОРЕТИЧЕСКИЕ ПРЕДПОСЫЛКИ:

• Дерево Штейнера строят для того, чтобы получить более короткую сеть, чем МОД.

• Теоретически обоснованное желание найти минимальное полное дерево Штейнера часто даже для простейших фигур (трех- и четырехугольников) заканчивается неудачей из-за свойств ПДШ.

« Триангуляция Делоне отличается тем свойством, что полученные

треугольники стремятся к равноуголыюсти. » Задача Штейнера МР-трудна, потому гарантированного результата (абсолютного минимального ДШ) получить скорее не удастся.

ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА.

1. На заданном множестве точек строится минимальное остовное дерево.

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

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

3.1 .внутренние углы (достаточно хранить два любых);

3.2.сумму двух меньших сторон (локальный МОД);

3.3.логическую характеристику принадлежности сторон локального МОД треугольника общему минимальному остовному дереву;

3.4.коэффициент КОМОД треугольника, используя формулу (11)

3.5. характеристику АБС. По определению это абсолютный выигрыш от возможного построения ДШ для каждого треугольника: АБС=МОД-ДШ, подставив определение КОМОД, получим:

АБС=МОД (1 -КОМОД). (14)

Рис. 12. Изолинии КОМОД для четырехугольников с базовым треугольником, имеюиршугш 60? 60?60°

-2-10133

Рис. 13. Изолинии КОМОД для четырехугольников с базовым треугольником, имеющим углы 90°45°45°

И=1

П=2

И=4

Рис. 14. Рекурсивный метод

Рис. 15. Цепной метод

Рис. 20. КОМОД-1,090... Рис. 21. К0М0Д=1,145...

С5

Рис. 22. КОМОД=1,144... Рис. 23. КОМОД-1,180...

Подчеркнем, что, так как АБС зависит от двух переменных, то может оказаться, что маленький и очень эффективный треугольник может не позволить нам получить лучший выигрыш, чем большой, но менее эффективный. Использование характеристики АБС является одним из ключевых моментов работы предлагаемого алгоритма. Чаще всего другими авторами используется КОМОД.

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

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

5. Организуется список треугольников, подходящих для построения ДШ. Он образуется путем отбрасывания из списка пункта 4. всех тупоугольных треугольников, с углом при вершине большими 120°. Оставшиеся треугольники делятся на три группы из условия, учитывающего, сколько сторон локального МОД совпадают с общим МОД:

• в первую группу входят те, у которых совпадают две стороны;

• во вторую группу, если одна сторона совпадает;

• в третью группу, если нет совпадения сторон.

Внутри каждой группы треугольники сортируются по величине АБС (в

начало списка попадают те, у которых АБС больше)

РАБОТА АЛГОРИТМА.

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

Учитывая, что обработка треугольников первой группы на первоначальном этапе тривиальна, более подробно рассмотрим обработку треугольника второй группы.

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

Проделав эту процедуру, мы найдем одно из остовных деревьев графа, величина которого больше длины МОД на разницу между введенной нами второй стороной и отброшенным минимальным отрезком цикла. Обозначим её Д.

Построение ДШ на треугольнике осуществляется только в том случае, если его АБС превосходит Д. В противном случае треугольник просто исключается из списка п.5.

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

В случае возможности построения ДТП (начиная с этого места, все нижесказанное относится к треугольникам, в том числе, и первой группы) рассматриваются все соседние треугольники, примыкающие к сторонам. Число их не превышает 3. Для каждого, используя методы, рассмотренные в 3 разделе пытаемся построить ДШ. При этом, используя теорему о диагоналях (рис. 9), ищем только меньшее нз двух деревьев и контролируем возможность вырождения 7(111. Для примера, если используется метод рис. 6, то условие вырождения заключается в отсутствии пересечения отрезка ЕР со сторонами АВ и СО. В случае успеха нескольких вариантов, выбирается наилучший из них и, рассматривая, как правило, два новых соседних треугольников, используя цепной метод, пытаются построить ДШ с большим числом ТШ.

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

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

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

Если в процессе проектирования трубопроводной системы конструктор принимает решение минимизировать общую или локальную длину сети путем решения задачи Штейнера, то следующим этапом становится определение элементов, входящих в каждую ветвь (клапаны, задвижки и т.д.). При этом предварительно назначаются диаметры трубопроводов, их материал, что однозначно определяет гидравлические характеристики ветви (приведенную длину) и стоимость, которые в общем случае могут существенно отличаться для каждого линейного участка трубопровода. Гидравлический расчет по ¡аданным параметрам позволит уточнить общее сопротивление каждой ветви ш различных режимах работы сети. Тогда становится целесообразным уточнить положение точек Штейнера, используя метод построения ДШ с ?есовыми коэффициентами, где стоимостными (математическими)

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

Выведена система уравнений нестационарного метода.

ск

¿О:

_ П- ^¡Ь: 0:0:

^=0,11 рк = «г),

J . 68

К.

ч J 1 /

N0.25

¡ = 1...\У; ]= 1...М;

к=1 ...С;

(15)

где: ¡, к - текущий номер внутренних вершин, ребер, граничных вершин; М, в - общее количество внутренних вершин, ребер, граничных вершин;

А; - параметр сжимаемости вершины; р; - давление среды в соответствующей вершине, Па; р - плотность рабочей среды, кг/м3; ц у - элемент матрицы инцидентности;

- скорость среды в ] -м ребре в момент времени I, м/с; 8Г площадь поперечного сечения j-гo ребра, м.

- длина ячейки ребра, м;

Е=9,81 - ускорение свободного падения, м/с2; гг координата по высоте 1 -го узла;

§ - суммарный коэффициент местных сопротивлений в _]-м ребре в

данный момент времени; с!р эквивалентный диаметр)-го ребра; А,- коэффициент трения;

К| - эквивалентная шероховатость, берется из справочников в зависимости от материала труб; 0|<1:

Ке: = - число Рейнольдса;

1 v

здесь V - кинематическая вязкость. Для данной модели предложено два метода построения разностных схем по методу Эйлера и методу Рунге-Кутга, проведено тестирование, показано

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

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

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

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

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

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

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

Проведено тестирование метода. Известно,что стационарное решение уравнений квазиодномерного приближения для сопел Лаваля сводится к газодинамическим функциям, которые принимаются за точное решение. Если тот же контур сопла Лаваля рассчитать методом крупных частиц в квазиодномерном приближении до получения установления, то сопоставление полученных результатов расчета с газодинамическими функциями определит точность решения. Приведенные в работе данные показывают, что разница составляет 1,5%, и она связана с действием аппроксимационной вязкости разностной схемы.

Специально поставленным экспериментом по исследованию двухфазного потока (воздуха с капельками воды) проверялось вычисление температурного поля. Для этого в рабочей камере устанавливался датчик, измерявший температуру оседавших на его поверхности капель. Температура 0°С контролировалась визуально через стекло рабочей камеры. При этой температуре изменялся цвет движущегося потока. Полученные расхождения в среднем составляют 1%.

Имеющиеся литературные данные по холодной продувке выпускного канала в крышке цилиндра двигателя внутреннего сгорания сравнивались с результатами вычислительного эксперимента. Меридиональное сечение канала разбивалось сеткой из двухсот прямоугольных ячеек. Универсальность метода подтверждается качественно. При протекании газа внутри канала образуется вихрь. При математическом моделировании подтверждается существование, направление вращения и место расположения вихря. Точность метода оценивалась путем сравнения экспериментальных и расчетных данных в выходном сечении канала (в трех точках). Сопоставление результатов показало, что ошибка может достигать 8%.(рис 24.)

Ввод фшических параметров, рабочей среды

и-

Автоматизированная система подгоювкп исходных данных дня дробных ячеек.

Задание начальных условий

Н Ь

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

значков этап

Расчет одного шага

граничные условия] по

времени

лагрянжев этап

Вьшод н хранения результатов

"Смена начальных услов11Й_

[НЕТ

^Смена контура

[НЕТ

конец

ДА

ДА

Рис 24. Алгоритм вычислительного эксперимента для геометрической оптимизации контура канала.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведенные в работе численные, аналитические и параметрические

исследования решения задачи Штейнера для простых наборов точек

позволили:

• выявить свойства дерева Штейнера, которые заключаются в том, что ребра, примыкающие к точкам Штейнера, образуют между собой углы по 120°, а значит, определяются три направления параллельности некоторых ребер ДШ между собой;

• разработать инвариантные геометрические алгоритмы построения дерева Штейнера, при осуществлении которых автоматически контролируется процесс вырождения ДШ;

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

• определить закономерности, помогающие выявлять «хорошие» конфигурации заданных наборов точек с целью построения на них наиболее эффективных ДШ. За исключением правильных многоугольников эти закономерности связаны с симметрией набора;

• доказать теоремы, использование которых гарантированно позволяет сократить на начальных этапах генерации общее число рассматриваемых вариантов с трех до одного;

• показать возрастающую «узость» интервала параметров, при котором еще возможно построить полное дерево Штейнера.

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

• сортировка начальной конфигурации треугольников Делоне по характеристике абсолютного выигрыша от возможного построения ДШ по сравнению с исключаемой величиной МОД глобального набора точек;

• разрастание локального полного ДШ жестко связано с неубыванием абсолютного выигрыша.

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

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

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

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

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

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

7. Сравнение расчетных данных со специально поставленными экспериментами показало, что расхождение в среднем составляет единицы процентов, что свидетельствует о высоком качестве модели.

Работы, опубликованные автором.

1. Синицын С.И. Компьютерная система подготовки данных для численного моделирования физических процессов в плоском теле произвольной конфигурации, созданного с помощью АВТОКАДА. //КОГРАФ 93. Тезисы докладов. Н. Новгород, 1993, с. 44

2. Синицын С.И. Метод гидравлического расчета трубопроводных систем произвольной конфигурации И Информационное извещение, Н. Новгород, 1991, с.З

3. Синицын С.И. Ограничения для деревьев Штейнера с весовыми коэффициентами.// 8 Всероссийская научно-практическая конференция по графическим информационным технологиям КОГРАФ-98. Тезисы докладов. Н. Новгород, 1993, с. 162

4. Синицын С.И. Число точек Штейнера в полном дереве Штейнера. //Компьютерные технологии в науке, проектировании и производстве, I Всероссийская научно-техническая конференция. Тезисы докладов. Часть IX.- Н. Новгород, 1999, с 27

5. Синицын С.И. Геометрический способ построения точек Штейнера в четырехугольнике // Компьютерные технологии в науке, проектировании и

производстве. I Всероссийская научно-техническая конференция. Тезисы доклада, Часть 1Х.-Н. Новгород, 1999, с 28

6. Синицын С.И. Теорема о величине дерева Штейнера в четырехугольнике //Компьютерные технологии в науке, проектировании и производстве. I Всероссийская научно-техническая конференция. Тезисы доклада, Часть IX.-Н. Новгород, 1999, с 28

7. Синицын С.И. Теорема о прямом угле между диагоналями четырехугольника. // Компьютерные технологии в науке, проектировании и производстве. 1 Всероссийская научно-техническая конференция. Тезисы доклада, Часть 1Х.-Н. Новгород, 1999, с 28

8. Синицын С.И. Способ вычисления эффективности построения дерева Штейнера в треугольнике, заданном двумя своими меньшими углами. // Начертательная геометрия, инженерная и компьютерная графика. Международный межвузовский научно- методический сборник трудов кафедр графических дисциплин. - Н. Новгород, 1999, с.50-53

9. Синицын С.И. Структуры и способы построения деревьев минимальной длины для произвольных планарных четырехугольников //Начертательная геометрия, инженерная и компьютерная графика. //Международный, межвузовский научно- методический сборник трудов кафедр графических дисциплин. - Н. Новгород, 1999, с.53-55

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

Н. Новгород, 1999, с.177-180

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

Н. Новгород, 1999, с.180-181

12. Синицын С.И. Геометрический способ построения дерева Штейнера для правильных многоугольников. //КОГРАФ-99. 9-я Всероссийская научно-техническая конференция по графическим информационным технологиям и системам. Тезисы доклада. Н. Новгород, 1999 г

13. Синицын С.И. Рекуррентный способ построения дерева Штейнера для регулярных структур. // КОГРАФ-99. 9-я Всероссийская научно-техническая конференция по графическим информационным технологиям и системам. Тезисы доклада. Н. Новгород, 1999г

14. Синицын С.И. Определение эффективных монотонных многоугольников для решения задачи Штейнера. //КОГРАФ-99. 9-я Всероссийская научно-техническая конференция по графическим информационным технологиям и системам. Тезисы доклада. Н. Новгород, 1999г

15. Синицын С.И. Геометрическое построение дерева Штейнера в произвольном планарном четырехугольнике без использования дуг.

// Начертательная геометрия, инженерная и компьютерная графика. Международный межвузовский научно-методический сборник трудов кафедр графических дисциплин. Выпуск 5.-Н. Новгород, 2000, с. 183-285

16. Синицын С.И. Диагональный метод построения дерева Штейнера. // Начертательная геометрия, инженерная и компьютерная графика. Международный межвузовский научно-методический сборник трудов кафедр графических дисциплин. Выпуск 5. - Н. Новгород, 2000, с. 285-287

17. Синицын С.И. Особые случаи построения дерева Штейнера для четырех заданных точек. //Начертательная геометрия, инженерная и компьютерная графика. Международный межвузовский научно-методический сборник трудов кафедр графических дисциплин. Выпуск 5.-Н. Новгород, 2000, с.287-290

18. Синицын С.И. Рекурсивный способ построения дерева Штейнера для регулярных структур. // Начертательная геометрия, инженерная и компьютерная графика. Международный межвузовский научно-методический сборник трудов кафедр графических дисциплин. Выпуск 5.-Н. Новгород, 2000, с.290-291

Работы, опубликованные в соавторстве

19. Котляр И.В., Аташкин В.В., Синицын С.И Расчетное исследование переходных процессов ГТД с РСА. // Проблемы повышения эффективности систем и устройств судовой энергетики. Межвузовский сборник. - Горький, 1984, с.81-85

20. Косолапов Е.А., Синицын С.И. К оценке точности численного решения методом крупных частиц задач внутренней газодинамики. // Шестая научная конференция молодых ученых Волго-Вятского региона. Тезисы докладов. -Горький, 1986, с.144

21. Клабуков В.Я., Косолапов Е.А., Гребенщиков Л.Т., СиницынС.И. Организация расчета нестационарной двухфазной газодинамики в пакете прикладных программ для исследования сложного теплообмена. //Совершенствование газодинамических элементов судовых агрегатов и устройств. Межвузовский сборник. - Горький, 1986, с. 131-136

22. Клабуков В.Я., Косолапов Е.А., Гребенщиков Л.Т., Синицын С.И. Пакет прикладных программ для исследований сложного теплообмена при двухфазных течениях. // Радиационный теплообмен в технике и технологии. Тезисы доклада VI Всесоюзной научно-технической конференции. - Каунас, 1987, с. 38

23. Синицын С.И., Малахов A.B. Автоматизированная система подготовки данных для расчета методом крупных частиц течений сплошных сред в каналах с произвольной образующей. Н Проблемы повышения эффективности судовых энергетических установок. - Горький, 1988, с.82-90

24. Синицын С.И., Синицын Д.И., Программно-аппаратный комплекс "SELEKTOR"//Информационное извещение. - Горький, 1991,. с. 1-2

25. Синицын С.И., Соколов И.В. Способ визуализации результатов гидравлического расчета разветвленной трубопроводной системы. // Компьютерная геометрия и графика в инженерном образовании КОГРАФ-91. Материалы всесоюзной конференции. - Н. Новгород, 1991, с. 173

26. Шишкин Д.А. Синицын С.И. Камера для сушки дисперсных материалов. Патент RU 2005971 С1. Опубликован 15.01.94. Бюл. №1

27. Немцев З.Ф., Курилов В.К., Черняховский В.В., Синицын С.И., Осипов И.С., Быков Б.И. О физическом содержании произведения давления на объем. //Научно-техническая конференция профессорско-преподавательского состава, аспирантов и студентов. Тезисы докладов. Часть 5. Н. Новгород 1995, с.57

28. Немцев З.Ф., Курилов В.К., Черняховский В.В., Синицын С.И., Быков Б.И. Новый параметр состояния в термодинамике. //Научно-техническая конференция профессорско-преподавательского состава, аспирантов и студентов «Строительный комплекс-96» Тезисы докладов. Часть 5. Н. Новгород, 1996, с.93

29. Синицын С.И., Белецкая С.Б. Задача Штейнера для треугольников и специальных триангуляции. //КОГРАФ-96. Тезисы международной конференции по компьютерной геометрии и графике. Тезисы доклада. -Н. Новгород, НГТУ, 1996, с. 118-119

30. Синицын С.И., Белецкая С.Б., Синицын Д.И. Выбор количества точек Штейнера и их расположения для произвольного треугольника. //Инновационные подходы к решению педагогических, организационно-экономических, инженерно-технических и производственных проблем. Сборник научных трудов.- Н. Новгород, изд-во ВГИПИ, 1997, с.240-243

31. Синицын С.И., Белецкая С.Б., Синицын Д.И. Численное исследование эффективности построения дерева Штейнера для произвольных треугольников. // Инновационные подходы к решению педагогических, организационно-экономических, инженерно-технических и производственных проблем. Сборник научных трудов,- Н. Новгород, изд-во ВГИПИ, 1997, с.240-243

32. Синицын С.И., Белецкая С.Б., Синицын Д.И. Формула для вычисления эффективности построения дерева Штейнера в треугольниках. //VII Всероссийская конференция по компьютерной геометрии и графике КОГРАФ-97. Тезисы докладов. - Н. Новгород 1997, НГТУ, с. 143

33. Синицын С.И., Белецкая С.Б., Синицын Д.И. Оптимальные конфигурации четырехугольников для построения дерева Штейнера. // VII Всероссийская конференция по компьютерной геометрии и графике КОГРАФ-97. Тезисы докладов. - Н. Новгород, НГТУ, 1997, с. 143

34. Синицын С.И., Турлапов В.Е., Белецкая С.Б. Структурный анализ и синтез на графах: Методическое пособие. - Н. Новгород, НГТУ, 1998, с. 30

ЛР № 020823 от 21.09.98. Подписано в печать 10.10.00. Формат 60x90 1/16 Печать офсетная. Объем 2 печ.л. Тираж 120 экз. Заказ

Нижегородский государственный архитектурно-строительный университет 603600, Н. Новгород, Ильинская,65

Отпечатано в полиграфическом центре Нижегородского государственного архитектурно-строительного университета, 603600, Н. Новгород, Ильинская,65