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

ВВЕДЕНИЕ.

ГЛАВА 1. РАЗРАБОТКА АЛГОРИТМА И МЕТОДИКИ ПОСТРОЕНИЯ УСЛОВНОЙ РАЗВЕРТКИ ОТСЕКА ТОПОГРАФИЧЕСКОЙ ПОВЕРХНОСТИ МЕЖДУ ДВУМЯ ЗАДАННЫМИ ТОЧКАМИ.

1.1. Разбиение топографической поверхности на треугольные ячейки.

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

1.3. Выбор направления пути для построения условной развертки части топографической поверхности.

1.4. Последовательное построение условной развертки части топографической поверхности по заданному пути.

1.5. Алгоритм построения условной развертки части топографической поверхности по заданному пути. Численный пример.

1.6. Перенос заданных точек на условную развертку.

1.7. Выводы.

ГЛАВА 2. РАЗРАБОТКА АЛГОРИТМА ПОСТРОЕНИЯ И МЕТОДИКИ ПОИСКА КВАЗИГЕОДЕЗИЧЕСКОЙ ЛИНИИ НА ТОПОГРАФИЧЕСКОЙ ПОВЕРХНОСТИ.

2.1. Алгоритм построения квазигеодезической линии между двумя заданными точками на топографической поверхности по ее условной развертке.

2.2. Определение принадлежности отрезка прямой, соединяющей две заданные точки, построенной на развертке.

2.3. Корректировка пути построения условной развертки между двумя точками на топографической поверхности.

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

2.5. Выводы.

ГЛАВА 3. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ШТЕЙНЕРА НА ТОПОГРАФИЧЕСКОЙ ПОВЕРХНОСТИ, ПРИМЕНИТЕЛЬНО К ПРОКЛАДКЕ ТРУБОПРОВОДОВ.

3.1. Построение кратчайших линий, соединяющих заданные точки на плоскости.

3.2. Построение квазигеодезической линии, соединяющей три заданные точки на топографической поверхности.

3.3. Построение квазигеодезической линии, соединяющей п заданных точек на топографической поверхности.

3.3. Выводы.

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

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

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

Общим критерием оптимизации практически для всех транспортных сетей является поиск минимального дерева, связывающего заданные точки. Если при такой оптимизации допускается добавление новых точек, то такая задача известна, как задача по построению кратчайшего дерева Штейнера (далее КДШ) для заданных точек [6, 8, 28, 40, 51, 52, 55, 64, 135].

Поиск КДШ для точек, заданных на плоскости, относится к разряду сложных задач. При большом числе заданных узлов применение алгоритма прямого перебора становится практически невозможным из-за резкого роста объема вычислений. Поэтому были разработаны специальные алгоритмы для избежания прямого перебора вариантов [9, 12, 13, 14, 20, 29, 33, 34, 39, 48 ,73, 89, 96, 100, 105, 114, 120, 122, 123, 124, 127, 128].

Реальная гористая местность сильно отличается от ее плоскостной модели. Здесь задача поиска КДШ еще более усложняется. Известные алгоритмы по построению КДШ для топографической поверхности [2, 21, 35, 37, 38, 41, 45, 47, 50, 53, 61, 69, 75, 79, 90] практически не используют накопленную богатейшую методическую и алгоритмическую базу для поиска КДШ на плоскости. Это обстоятельство делает невозможным разработку универсального способа решения задач для любой местности, состоящей из сильно пересеченных и относительно ровных участков.

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

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

Поиск конфигурации инженерной сети наименьшей протяжённости можно свести к следующей геометрической задаче: построить связывающую линию для некоторого множества точек в пространстве Е3, имеющую кратчайшую длину. Эту задачу называют проблемой Штейнера [3, 4, 44, 58, 59, 67, 78, 86, 110, 118, 121, 125, 130, 134].

Проблемой Штейнера занимались многие известные ученые. Так, например, Торричели и Ферма установили, что в общем случае, кратчайшая сеть для трех точек будет найдена введением еще одной точки [1, 17, 54, 65]. При этом ребра, соединяющие дополнительную точку с вершинами треугольника, сходятся под углами в 120°. Так же решением проблемы Штейнера занимались ученые Р. Курант [26, 27, 30, 57, 119] и В.М.Прокофьев [31, 36, 83, 84, 85], которые установили, что линия кратчайшей длины на плоскости состоит из отрезков прямых и имеет вершины трёх типов. Первый тип - это тупик, т.е. вершина инцидентная только одному отрезку. Второй тип - это колено, т.е. вершина инцидентная двум отрезкам, сходящимся под углом не менее 120°. И третий тип - это узел, т.е. вершина инцидентная трём отрезкам, сходящимися под углами в 120°.

Известный советский ученый Н. Ф. Четверухин [108, 109] предложил оригинальный метод мыльной пленки, основанный на физическом явлении поверхностного натяжения жидкости. В этой модели имеются две прозрачные параллельные пластины. Положения вершин Аь А2,., Ап фиксируются тонкими стержнями-отрезками перпендикулярными пластинам, концы которых жестко закреплены в них. Полученная таким образом конструкция погружается в мыльный раствор. После извлечения конструкции из раствора образуется мыльная плёнка между стержнями.

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

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

Полным перебором всех возможных вариантов для п узлов плоскости можно решить задачу построения кратчайшей сети между заданными точками. Это доказал Мельзак в работе [111, 133]. По этой схеме пытались решить проблему Штейнера в работах [126, 129, 131, 132]. Резкий рост объемов вычислений при большом количестве узлов делает невозможным решение задачи даже с применением современных мощных ЭВМ.

Поэтому необходимы методы, значительно уменьшающие количество вариантов, подлежащих перебору. В работах [25, 32, 95, 111, 134] предложены фильтры, отсеивающие некорректные варианты по установленным геометрическим признакам. Таким образом, усовершенствованный алгоритм Мельзака может обрабатывать сети только для п< 15. На основе изопериметрической задачи в работе [117] предложен алгоритм построения кратчайшей сети для «<30. Более эффективные алгоритмы для решения проблемы Штейнера были получены на базе теории графов [14, 15, 60, 82, 88, 107].

Приложения проблемы Штейнера для конкретных примеров накладывают дополнительные условия, например, задача построения сети минимальной стоимости. Так же имеются приложения по отраслям. В работах [40, 51, 55, 99] исследуется проблема Штейнера для прокладки линий электропередачи, в работах [61, 106, 111] для автомобильных дорог и в [5, 7, 11, 46, 70, 81, 101] для магистральных нефте- и газопроводов.

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

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

Как было отмечено выше, реальная местность сильно отличается от плоскостной модели и поэтому актуально решение проблемы Штейнера и в других пространственных моделях. В работе [74] была рассмотрена задача построения кратчайшей связывающей сети на поверхности сферы и предложен алгоритм. Для многомерного пространства свойства кратчайших связывающих сетей рассматривались в работах [16, 23, 29, 102]. Для произвольной поверхности задача нахождения кратчайшей линии рассматривалась в работах [49, 62, 63].

С использованием ортогональной метрики решались задачи нахождения кратчайших транспортных сетей внутри городских кварталов или внутри заводских цехов, а также для транспортировки грузов внутри складов. Здесь транспортные линии могут быть выбраны только параллельно осям прямоугольной системы координат. Аналогичная задача возникает также при трассировке соединений на печатных платах [10, 14,15, 30, 31, 32, 60, 113].

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

Н.А.Глаголев [21, 22]. Профессором Н.Н.Рыжовым рассматривалась задача по построению геодезической линии в заданном направлении на топографической поверхности [90]. Приближенный способ построения кратчайшей линии с использованием свойств нормальных сечений рассматриваются в работах [49, 75, 97]. В вышеупомянутых работах рассматривались кратчайшие соединения для двух точек, лежащих на топографической поверхности. Поэтому не представляется возможным использовать их для построения кратчайшей линии, связывающей заданное множество из п точек на топографической поверхности.

Более приемлемым, с целью автоматизации, является цифровое моделирование топографической поверхности [35, 41, 45, 63, 71, 79] и использование волнового алгоритма Ли [42, 43]. Таким образом, созданные методики для построения кратчайших сетей, связывающих заданное множество точек на топографической поверхности, могут быть использованы в системах автоматизированного проектирования.

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

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

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

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

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

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

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

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

Теоретической базой проведенных исследований явились работы ведущих ученых: по теории геометрического моделирования: Бусыгина В. А., Волкова В. Я., Иванова Г. С., КотоваИ. И., Михайленко В. Е., Наджарова К. М., Нурмаханова Б., Осипова В. А., Тевлина А. М., Тузова А. Д., Фролова С. А., Якунина В. И. и многих других; по геометрии связывающих линий: Глаголева Н. А., Есмуханова Ж. М., Калинина В. А., Кельманса А. К., Куранта Р., Мельзака Ю. Г., Мульдекова И. О., Рыжова Н. Н., Четверухина Н. Ф., Штейнера Я. и других.

Научную новизну диссертационной работы составляют следующие результаты: геометрические алгоритмы и методика построения условной развертки отсека топографической поверхности между двумя заданными точками; геометрические алгоритмы и методы определения квазигеодезической линии между двумя точками на топографической поверхности с использованием условной развертки отсека топографической поверхности между этими двумя точками; геометрические алгоритмы и методы обратного переноса на поверхность кратчайшего расстояния, найденного на условной развертке отсека топографической поверхности между двумя заданными точками; геометрические методы и алгоритмы поиска кратчайшего связывающего дерева для трех и более точек на топографической поверхности с использованием условной развертки отсека топографической поверхности; прикладные программы ModeBrez, Razvert, Poisk, Perenos, Steiner, RazVlas и RazVlasSt, которые позволяют построить условную развертку отсека топографической поверхности, определить квазигеодезическую линию между двумя точками и точки Штейнера, определить кратчайшие связывающие заданные точки деревья на топографической поверхности.

Апробация работы. Основные результаты диссертационной работы были доложены и обсуждены на:

1. Международной конференции «Молодые ученые — 10-летию независимости Казахстана», г. Алматы, 2001 г.;

2. Второй Международной научно-практической конференции молодых ученых, г. Алматы, 2002 г.,

3. Международной научно-практической конференции «Естественно-гуманитарные науки и их роль в подготовке инженерных кадров», г. Алматы, 2002 г.;

4. На научных семинарах и заседаниях кафедры начертательной геометрии и графики Казахского национального технического университета имени К. И. Сатпаева и кафедры прикладной геометрии Московского авиационного института (технического университета).

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

3.3. Выводы

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

2. Составлены необходимые нам формулы для аналитического вычисления координат точки Штейнера S на плоскости.

3. Разработана блок-схема алгоритма определения точки Штейнера для заданных трех точек. На основе данной блок-схемы написана программа Steiner на языке высокого уровня Object Pascal.

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

5. Разработан алгоритм нахождения КДШ на топографической поверхности для трех заданных точек.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

5. Поставлена и решена задача о кратчайшем соединении трех точек топографической поверхности, которая является обобщением аналогичной задачи Штейнера на плоскости.

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

7. На основе разработанных алгоритмов составлены программы ModeBrez, Razvert, Poisk, Perenos, Steiner, RazVlas и RazVlasSt на языке высокого уровня Object Pascal, которые образуют в совокупности геометрический модуль систе

119

1. Андреев К. А. Избранные работы.— Харьков: Издательство Харьковского государственного университета имени А. М. Горького, 1955.—92 с.

2. Артюшенко В. И. Графо-аналитические способы определения уклонов поверхностей по фотоснимкам и кинокадрам // Автореф. дис. канд. техн. наук: Специальность 150.— М.: МТИПП, 1970.— 16 с.

3. Бабаян Б. А., Попов В. С. Нахождение связывающей сети абсолютно минимальной длины. // Труды семинара отдела структурных Логических схем.— М.: ИТМ и ВТ АН СССР, 1969. Вып.7. — С. 27— 45.

4. Баранов Г. А., КурейчикВ. М., Калашников В. А. Вопросы оптимизации деревьев Штейнера // Электронная техника. Сер.З. Микроэлектронные устройства.— 1978. Вып. 3/9.— С. 27—30.

5. Безкоровайный В. П. Разработка методов оптимизации трасс магистральных газопроводов и их разветвлений для сетей произвольной конфигурации: Автореферат диссертации на соискание ученой степени канд. техн. наук.— М., 1978.— 25 с.

6. Бер А. И., Белов Е. Н., Поляк Б. Т. О некоторых задачах оптимизации сетей // Вычислительные методы и программирование.— М.: изд-во МГУ.— 1966.— №5.— С. 115—123.

7. Березин В. Л., Бородавкин П. П., Бесхижко В. В. Поиск оптимальной конфигурации трубопроводной системы // Строительство трубопроводов .—М., 1976.— № 10 — С. 20—21.

8. Болтянский В. Г. Оптимальное управление дискретными системами.— М.: Наука. 1973.—448 с.

9. Борисов Г. А., Земляченко В. Н., Кукин В. Д. Проблема Штейнера и ее приложения // Доклады на заседании Президиума Корельского филиала АН СССР,—М., 1984.—С. 41—43.

10. Бочко Г. Д., Макаров Л. И. Об одном алгоритме трассировки в прямоугольной решетке // Вычислительная техника.— Каунас, 1974.— С. 111—113.

11. Браун Ю. Г., Гайда В. А. Применение ЭВМ при проектировании газовых сетей // Нефть, газ и нефтехимия.— 1985.— № 4.— С. 14—20.

12. Вайнер В. Г., Зайцев И. Д., Лившиц Э. М. Алгоритм построения связывающих сетей // Автоматика и телемеханика.— М., 1978.— №7.— С. 153—162.

13. Васильев В. В., Гайфуллин Э. Ш. Алгоритм решения задачи Штейнера// Теория графов.— М., МЭИ, 1975.— Вып. 250.— С. 94— 100.

14. Васильев В. В. Алгоритм решения задачи Штейнера с ортогональными расстояниями // Труды МЭИ. Системы автоматизированного проектирования.— М.: 1978. Вып.368.— С. 41—46.

15. Воевидин В. В., Кузнецов М. 3. Матрицы и вычисления.— М.: Наука: 1984.— 318 с.

16. Волков В. Я. Теория параметризации и моделирования геометрических объектов многомерных пространств и ее приложения // Автореф. дисс. докт. тех. наук: 05.01.01.— М.: МАИ, 1983.— 35 с.

17. Геометрические задачи машинной графики больших интегральных схем.— М.: Радио и связь, 1987.— 176 с.

18. Геометрическое моделирование и машинная графика в САПР под ред. Михайленко В. Е.— К.: Вища шк., 1991.— 373 с.

19. Гилой В. Интерактивная машинная графика.— М.: Мир, 1981.— 380 с.

20. Гильберт Е. Н. Поллак Г. О. Минимальные деревья Штейнера // Кибернетический сборник.— М.: Мир, 1974. Вып. 8. С. 19—50.

21. Глаголев Н. А. Задача о построении линии кратчайшей длины в проекциях с числовыми отметками // Матем. сб. № 1. — М.: Изд. АН СССР, 1923.—Т. 31.—С. 6—13.

22. Глаголев Н. А. Проективная геометрия.— М.: Высшая школа, 1973.— 344 с.

23. Гольцева Р. И. Конструктивная геометрия многогранных пространств // Автореф. дис. док. техн. наук: 05.01.01.— Киев: КИСИ, 1992.— 42 с.

24. Гончаров К. В. Геометрические преобразования к исследованию отраженных волн в сейсморазведке // Автореф. дис. канд. техн. наук: 05.01.01.—М.: МАИ, 1975.—24 с.

25. Джиенкулов С. А., Куспеков К. А. Геометрические методы определения кратчайшего маршрута при погрузочно-разгрузочных, транспортных и складских работах // Поиск. № 4.— Алма-Ата: 1995.— С. 127—130.

26. Евдокимов А. Г. Оптимальные задачи на инженерных сетях.— Харьков, Вища школа, 1976.— 153 с.

27. Есмуханов Ж. М. Геометрия плоскости с полярной метрикой // Прикладная геометрия и инженерная графика.— Алма-Ата: КазПТИ, 1978. Вып.З.— С. 10—15.

28. Есмуханов Ж. М. Графический алгоритм обобщенной проблемы Я. Штейнера // Прикладная геометрия и инженерная графика.— Алма-Ата: КазПТИ, 1974. Вып.1. — С. 13—19.

29. Есмуханов Ж. М. Графо-геометрическое моделирование в САПР технических устройств // Автореф. дис. док. техн. наук: 05.01.01., 05.13.12.— Алматы: КазНТУ, 1995.— 84 с.

30. Есмуханов Ж. М. К вопросу построения связывающего дерева с расстоянием первого порядка // Сборник по вопросам математики и механики. — Алма-Ата: КазГУ. 1973. Вып.4.— С. 32—407.

31. Есмуханов Ж. М. О кратчайших связывающих линиях в пространстве с расстояниями первого порядка // Прикладная геометрия и инженерная графика.— Алма-Ата: КазПТИ, 1976. Вып.2.— С. 45—52.

32. Есмуханов Ж. М., Куспеков К. А. Об одном алгоритме построения кратчайших связывающих линий в двумерном пространстве сортогональной метрикой. Алматы. 1994. Деп. в КазгосИНТИ 6.06.1994.— 10 е.—№ 5054.

33. Есмуханов Ж. М., Куспеков К. А. Технология определения кратчайших связывающих линий средствами интерактивной машинной графики // Актуальные вопросы современной науки и техники.— Алматы, 1994.— С. 87—90. (Сб. науч. тр. 4.2).

34. Есмуханов Ж. М. Методы отыскания оптимальных решений некоторых конструктивных задач и их технические приложения // Автореф. дис. канд. техн. наук.— М.: МАИ, 1969.— 28 с.

35. Есмуханова Ж. Ж. Геометрические методы расчета конфигурации инженерных сетей // Автореф. дис. канд. техн. наук: 05.01.01.— М.: МАИ, 1987.— 17 с.

36. Есмуханова Ж. Ж. Алгоритм построения оптимальной конфигурации инженерной сети // Моделирование задач науки и техники методами начертательной геометрии.— Алма-Ата: изд. КазПТИ.— 1986.— С. 43—46.

37. Есмуханова Ж. Ж. Конструирование рациональной конфигурации разветвленных инженерных сетей в трёхмерном пространстве // Технический отчет по теме № 905-02- И ГР. № 81001625, этап 1.— М.: МАИ, 1986.— С. 96—111.

38. Есмуханова Ж. Ж. Геометрические задачи на инженерных сетях // Прикладная геометрия и инженерная графика в теории и практике авиационного автоматизированного проектирования.— Киев: КИИГА, 1984.—С. 58—62.

39. Есуханов Ж. М., Есмуханова Ж. Ж. Подсчёт числа разомкнутых связывающих линий // Материалы XVI научно-технической конференции профессорско-преподавательского состава Казахского политехнического института имени В. И. Ленина.— Алма-Ата: КазПТИ, 1982.

40. Журавлев В. Г., Чиник В. И., Чиник М. А. Построение трассы высоковольтной линии электропередач минимальной длины путём добавления новых точек // Электроэнергетика и автоматика.— Кишинев. АН Молд. ССР.— 1965.

41. Журкин И. Г., Коркин В. С. Об одном подходе к построению цифровой модели рельефа // Изв. вузов. Геодезия и аэрофотосъёмка.— М.: 1983.— №4.—С. 66—71.

42. Зиман Ю. Л., Рябов Г. Г. Волновой алгоритм и электрические соединения // Электронные вычислительные машины.— М.: ИТМ и ВТ АН СССР, 1965.—С. 128.

43. Зиман Ю. Л., Гринберг Г. С. Некоторые новые возможности волнового алгоритма // Институт точной механики и вычислительной техники АН СССР.—М.: 1973.—35 с.

44. Иванов А. О., Тужилин А. К. Задачи Штейнера для выпуклых границ или плоские минимальные сети // Матем. сб.— М.: 1991.— Т. 182. № 12.—С. 1813—1844.

45. Иванов Г. С., Есмуханова Ж. Ж. Построения кратчайших связывающих сетей на топографической поверхности // Начертательная геометрия и машинная графика в практике решения инженерных задач.— Омск: ОМПИ. 1987.—С. 27—32.

46. Иванов Е. Ф. Графика в автоматизированной системе подготовки производства трубных изделий // Автореферат диссертации на соискание учёной степени канд. техн: наук: 05.01.01.— М.: МТИПП, 1975.— 26 с.

47. Иванов С. А. Выбор оптимальной трассы газопроводов с отводами: Автореферат на соискание учёной степени канд. техн. наук.— М.: МИНХиГП, 1971.— 19 с.

48. Калашников В. А., Лебедев Б. К., Литвиненко В. А. Программа построения кратчайшего дерева Штейнера // Республ. фонд алгоритмов и программ.— Киев: Ж АН УССР, 1978, № 5213.

49. Калинин В. А. Теоретические основы геометрического моделирования процессов намотки и выкладки конструкций из волокнистых композиционных материалов // Автореф. дис. док. техн. наук.— М.: МГУПП, 1997.—49 с.

50. Карпенко М. П. Исследование и разработка методов выбора оптимальных трасс для строительства магистральных трубопроводов: Автореферат диссертации на соискание учёной степени канд. техн. наук.— М.— 1971 — 24 с.

51. Каялов Г. М., Каждан А. Э. Построение конфигурации воздушной электрической сети на основе геометрического решения общей проблемы Штейнера // Изв. вузов. Электромеханика.— 1967.— № 1.— С. 34—41.

52. Кельманс А. К. О построении кратчайшей связывающей сети // Кибернетика и управление.— М.: Наука, 1967.— С. 115—130.

53. Киргизбаев Т. К. Геометрическое обеспечение задач проектирования сооружений на рельефе местности в интерактивном режиме // Автореф. дис. канд. техн. наук: 05.01.01.— Киев: КИСИ, 1986.— 16 с.

54. Кокстер С. С. М. Введение в геометрию.— М.: Наука, 1966.— 648 с.

55. Коренблюм Б. И., Рыбальский В. И. Оптимальные распределительные сети // Экономика и математические методы.— М.: 1967. Т. 3. Вып.1.— С. 87—92.

56. Котов И. И., Ползов В. С., Широкова Л. В. Алгоритмы машинной графики.— М.: Машиностроение, 1977.— С. 238.

57. Кофман А. Введение в прикладную комбинаторику.— М.: Мир, 1975.— С. 478.

58. Куспеков К. А. Разработка методики построения кратчайших связывающих линий и ее применение в ПРТС работах // Автореф. дис. канд. техн. наук: 05.01.01., 05.05.05.—Алматы.: КазНТУ, 1996.—22 с.

59. Куспеков К. А., Есмуханов Ж. М. Проблема Штейнера в пространствах с расстояниями первого порядка // Компьютерная геометрия и графика в инженерном образовании.— Нижний Новгород: НПИ. 1991.— С. 121.

60. Куспеков К. А., Есмуханов Ж. М. Проблема Штейнера в пространствах с расстояниями первого порядка // Компьютерная геометрия и графика в инженерном образовании.— Нижний Новгород: НПИ. 1991.— С. 121.

61. Кучинский В. М. Об одном методе оптимизации сетей автомобильных дорог // Строительство и архитектура.— М.: 1973. № 3.— С. 46—52.

62. Кучкарова Д. Ф. Геометрические вопросы водоотведения со сложных поверхностей при автоматизированном проектировании // Автореф. дис. канд. техн. наук: 05.01.01.— Киев: КИСИ, 1981.— 16 с.

63. Лотарев Ю. Т. Задача Штейнера для транспортной сети на поверхности, заданной цифровой моделью / Автоматика и телемеханика.— М, 1980. № 10.—С. 104—115.

64. Люстерник Л.А. Кратчайшие линии.— М.: Госиздат, НТП, 1955.

65. Мартынова О. Р. Геометрическое проектирование трубопроводных микросетей и воспроизведение их элементов // Автореферат дис. канд. техн. наук: 05.01.01.— М.: МАИ, 1990.—С. 18.

66. Математика и САПР: В 2-х кн. пер. с франц./ Шенен П., Коснар М., Гардан И. и др.— М.: Мир, 1988 — 204 + 264 с.

67. Маханов М. Построение конфигурации групповой водопроводной сети на основе геометрического решения // Начертательная геометрия и черчение.— Алма-Ата: КазПТИ, 1979.— С. 72—74.

68. Мацеевич Л. Н. Об одной экстремальной задаче комбинаторного типа // Тезисы докладов аспирантов на научной межвузовской конференции. М.: МАИ.— 1967.— С. 18—19.

69. Местман Б. Я., Тютин А. А. Приближенное решение задачи Штейнера в планарной решетке // Автоматизированное проектирование цифровых вычислительных машин.— Каунас: Наука, 1973.— С. 67—71.

70. Мигдалов В. Н. Разработка методов оптимального проектирования и управления для разветвленных систем нефтепродуктопроводов: Автореферат диссертации на соискание учёной степени, канд. техн. наук.— М.: МИНХ и ГП,— 1982.— 26 с.

71. Митчел Д., Д. Маунт Панадимитриц. Дискретная геодезическая задача // Кибернетический сборник.— Вып. 27.— М.: Мир, 1990.— С. 21—25.

72. Михайленко В. Е., Обухова В. С., Подгорный А. Л. Формообразование оболочек в архитектуре.— Киев: Будивельник, 1972.— 208 с.

73. Мульдеков И. О. Алгоритм построения кратчайшей связывающей сети // Прикладная геометрия и инженерная графика.— Вып. 3.— Алма-Ата. КазПТИ, 1978.— С. 78—80.

74. Мульдеков И. О. Методы решения некоторых конструктивных задач на римановой (сферической) плоскости на основе экстремальных свойств геодезических // Автореферат дис. канд. тех. наук.— М.: МАИ, 1973.— 21 с.

75. Мульдеков И. О. Приближённое построение кратчайшей линии на топографической поверхности с использованием линии нормальных сечений // Геометрические преобразования и их технические приложения — М.: МАИ.— 1971.— Вып. 232 — С.

76. Мусхелишвили Н. И. Курс аналитической геометрии.— М.:Гостехиздат, 1947.— 644 с.

77. Нурмаханов Б. Н. Теоретические и прикладные основы проектирования кривых, поверхностей и гиперповерхностей методом моноидальных преобразований // Автореферат дис. док. техн. наук. М. 1992.— 38 с.

78. Нутенко Л. Я. Использование проблемы Штейнера и ее обобщений для постановки и решения некоторых задач пространственной экономики.— М.: ЦЭМИ АН СССР, 1968.— 82 с.

79. Обидин Ю. С. Цифровое моделирование местности в инженерных целях // Геодезия и картография. 1981.— № 6.— С. 27—29.

80. Панасюк Л. С. Оптимальная аппроксимация и развертывание каналовых поверхностей технических форм: Автореферат диссертации на соискание учёной степени канд. техн. наук.— М.: Киев. 1977.— 18 с.

81. Попов Ю. И. Оптимальное трассирование газосборных сетей на месторождениях: Автореферат диссертации на соискание учёной степени канд. техн. наук.— М.: МИНХ и ГП, 1981.— 22 с.

82. Препарата Ф., Шеймос М. Вычислительная геометрия. Введение.— М.: Мир, 1989.—471 с.

83. Прим Р. К. Кратчайшие связывающие сети и некоторые обобщения // Кибернетический сборник. № 2.— М.: ИЛ, 1961. С. 95—107.

84. Прокофьев В. М. Некоторые свойства кратчайшей линии, соединяющей любое число точек плоскости // Ученые записки Московского гос. пединститута им. Ленина.— М.: МГПИ, 1957.— Вып.З. — С. 53—67.

85. Прокофьев В. М. Соединение точек отрезками, имеющими наименьшую сумму длин // Труды Московского нефтяного института имени И. И. Губкина. М.: МИНХ и ГП.— 1957.— Вып.20.— С. 18— 24.

86. Пчельникова Г. В. Некоторые алгоритмы для решения задачи Штейнера // Алгебра, геометрия и дискретная математика в нелинейных задачах. Под ред. Лупанова О. Б., Новикова А. И., Костушкина.— М.: МГУ, 1991.—С. 98—101.

87. Райан Д. Инженерная графика в САПР: Пер. с англ.— М.: Мир, 1989.— 391 с.

88. Роджерс Д. Алгоритмические основы машинной графики: Пер. с англ.— М.: Мир, 1989.— 512 с.

89. Романенко И. А. Технико-экономические основы проектирования сетей автомобильных дорог.— М.: Высшая школа. 1967.— 267 с.

90. Рыжов Н. Н. О построении кратчайшей линии на топографической поверхности // Труды Московского семинара по начертательной геометрии и инженерной графике.— М.: МЭИ, 1958.— С. 255—259.

91. Сакиева М. К., Есмухан Ж. М. Оптимальные связывающие линии // Труды международной конференции «Молодые ученые — 10-летию независимости Казахстана».— Алматы: КазНТУ, 2001,— ч. 1.— С. 450—453.

92. Сакиева M. К. Нахождение кратчайшего пути между двумя точками на топографической поверхности путем построения условной развертки // Труды 2-ой Международной научно-практической конференции молодых ученых.— Алматы: КазНТУ, 2002. Ч. 1.— С. 126—129.

93. Смеляков C.B. О построении оптимальной трассы, имеющей минимальное число пересечений с данной сетью // Вычислительная техника и машиностроение.— Минск, 1983.— №3.— С. 19—27.

94. Соловьев В. В., Печерский A.B., Донский Д.А., Быстров В.М. Построение простейших связывающих деревьев // Применение средств вычислительной техники.— Рязань, 1975.— С. 54-61.

95. Стародетко Е. А. Элементы вычислительной геометрии.— Минск: наука и техника.— 1986.— 239 с.

96. Стоян Ю. Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического проектирования. — Киев: Наук, думка. 1986.— 265 с.

97. Стрекачинский Г. А., Ордин А. А., Федорин В. А. Оптимизация транспортных сетей в прямоугольной метрике // Вопросы транспортных сетей шахт.— Новосибирск. 1976.— С. 3—7.

98. Тверицкий Р. В. Алгоритм поиска кратчайшего пути и его применение для формирования цепей // Вопросы радиоэлектроники. М.: 1970.— Вып. 9, С. 26—37.

99. Терентьев В. Г., Спектор JI. Н. и др. Выбор оптимальной системы транспорта мангышлакской нефти // Строительство трубопроводов. М.: 1967.— №1 —С. 53—56.

100. Филиппов П. В. Начертательная геометрия многомерного пространства и её приложения.— Л.: ЛГУ, 1979.— 280 с.

101. Фокс А., Прат П. Вычислительная геометрия. Применение в проектировании и на производстве. — М.: Мир, 1982. — 304 с.

102. Фролов С. А. Методы преобразования ортогональной проекции. — М.: Машиностроение, 1970. — 152 с.

103. Харит Ю. А. Алгоритм проведения кратчайшей линии на произвольной поверхности вращения // Кибернетика графики и прикладная геометрия.— М.— 1968.— С. 15—16.

104. Хомяк Я. В. Построение оптимальных сетей автомобильных дорог. М.: Транспорт, 1969.— 144 с.

105. Цой С. В., Цай С. М. Прикладная теория графов.— Алма-Ата.: Наука, 1971.

106. Четверухин Н. Ф. О некоторых методических вопросах в преподавании геометрии // Математика в школе.— М, 1955. № 2.— С. 18—24.

107. Четверухин Н. Ф. Проективная геометрия.— М.: Учпедгиз, 1961.— 260 с.

108. Чудова В. Л., Андрее Б. Н. Универсальная процедура построения дерева Штейнера // Автоматизация проектирования СМ ЭВМ. 1982. Вып.93. — С. 22—30.

109. Шалтянис В., Варнайтес А. Об одном методе уменьшения размерности при решении многоэкстремальных задач // Теория оптимальных решений.— Вильнюс. 1985. Вып.1.— С. 43—46.

110. Шпур Г., Краузе Ф.-Л. Автоматизированное проектирование в машиностроении/Пер. с нем. Г. Д. Волковой и др.; Под ред. Ю. М. Соломенцева, В. П. Диденко.— М.: Машиностроение, 1988.— 648 с.

111. Штейн М. Е. Задача Штейнера в ортогональной геометрии // Методы машинного проектирования цифровой аппаратуры.— М.: Советское радио. 1973.—С. 258—268.

112. Юшка Ф. П. Сети минимальной длины // Вычислительная техника. — Каунас, 1971.—С. 29—41.

113. Яковлев С. В. Методы и алгоритмы решения оптимизационных задач геометрического проектирования // Автореферат дис. канд. физ. матем. наук.— Киев, 1982.— С. 20.

114. Якунин В. И. Современные проблемы и перспективы научных исследований в прикладной геометрии // Начертательная геометрия и машинная графика в практике решения инженерных задач.— Омск: ОМПИ, 1986. С. 12—14.

115. Якутавичене Д. А. Алгоритм для решения задачи о кратчайшем соединении точек плоскости // Самонастраивающиеся системы.— М.: Наука, 1965.— С. 284—287.

116. Ященко В. А. Геометрическое моделирование в задаче оптимального проектирования инженерных сетей // Автореферат дис. канд. техн. наук.—Киев, 1988.—С. 16.

117. Bern М. W. Two probabilistic results on rechti-llnear Steiner trees // Algoritmica.— 1988.—v. 3. —p. 191—204.

118. Chang S. K. The generation of Minimal Trees with a Steiner Topology.— //J. of the association for, Computing Machinery.— 1972.— vol.19. —№ 4. —p. 89—96.

119. Chung E. R. and Graham R. L. Steiner trees for ladders.— // Annals Disorete Math. — 1978. — No. 2. — p. 23—39.

120. Cockayne E. G. and Schiller D. G. Computation of Steiner minimal trees // J. Combinatorics.— 1972. — p. 107—112.

121. Cockayne E. G. On the efficiency of algoritm for Steiner minimal trees // SIAMJ.Appl.Math. 1970.— 18. —No. 1. —p. 150—159.

122. Cockayne E. J. and Melzak Z. A. Steiner's problem for set terminals.— Qart. Appl. Math.26.2. — 1968. — p. 213—218.

123. Du D. Z., Yao K. N. and Huang F. X. Steiner minimal trees // J. Combinatorical Theory — 1982. No. 3. — p. 396—400.

124. Garey M. R., Graham R. L. and Johson D. S. The Comlexity of computing Steiner minimal trees // SIAM. J Appl. Math.— 1977.— vol. 32.— p. 262— 269.

125. Gilbert E. N. and Pollak K. H. O. Steiner minimal trees. // SI AM. J. Appl.Math.— 1968.—vol.16.—No. 1.— p. 171—196.

126. HananM. On Steiner's problem with rectilinear distanse // SIAMJ.Appl.Math. — 1966. vol.14. — No. 2. — p. 203—216.

127. Hwang E. K. Weng J E. and Du D. Z. A. Class of full Steiner minimal trees // J. Dischete Mat.— 1983.— v.45.

128. Jsenberg C. Minimum Roadway Problems. // J. Nethworks, 1981.— vol. 14.—No. 1.—p. 123—139.

129. Komlos J., Shining M. G. Prolalistic partitioning algorithm for the rectlinear Steiner problem // Networks. — 1985. — V. 15. No. 4. — p. 413—424.

130. Kon Z., Markowsts and Berman L., A. Forst Algoritm for Steiner trees // J.Asta Informatica, 1981.—vol. 15.—No. 12.— p. 144—145.

131. Melzak S. A. On the problem of Steiner // J. Canad.Math.Bull. — 1961. — v.4. — p. 143—148.

132. Pollak H. O. Some remarks on the Steiner problem // J. Combin Theory.Ser. — 1978. — a. p 278—295.

133. Steiner J. Uber den punkt kleinsten Entfernung. Monats bericht ten der Akademie der Wissenschaften zu Berlin, a.d.J. 1837. — s. 144.