Материал: 1831

ABOUT MODELLING OF THE RADIAL FILTRATION BY A MRTHOD OF SPREADSHEETS

V. I. Sologaev, N. V. Zolotarev

In this article we considering how we can construct computer model of the radial filtration in spreadsheets on base field experiments, that al¬ lows to calculate influence of the radial contour infiltration and to track of its

УДК 515.2

Сологаев Валерий Иванович - д-р техн. наук, профессор кафедры «Городское строительство и хозяйство» Сибирской государственной автомо­ бильно-дорожной академии. Основное направле­ ние научных исследований - защита от подтоп­ ления в городском строительстве. Имеет 78 опубликованных работ. e-mail: solooaev@rol.ru

Золотарев Николай Валерьевич - асси­ стент, Омский Государственный Аграрный Уни¬ верситет. Основное направление научных исследо¬ ваний - Мелиорация, рекультивация и охрана зе­ мель. Имеет более 6 опубликованных работ. E-mail: zolotarev-nikolai@rambler. ru

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

ны точки с весами: Mi, q-i, М2, q2 , M3 , q3 , M4, q4 (рис.1).

щ

\V , T / V P

Рис. 2. Топология 1 при q1 = q2 = q3 = q4

Радиальные отрезки M4, q4 N M3, q3 N''', а M4 ] q4 N'''<N M3 ] q3 . Поэтому на пер¬ вом шаге соединяем точки кратчайшим рас¬ стоянием M3, q3N''' M4, q4, то есть образуется кратчайшее дерево для двух точек M3, M4 -

КД2.

Шаг 2. Сравниваем расстояние меж¬ ду КД2 и точками M 1 , q1 и M 2 , q 2 . Просчитав все варианты соединения по дугорадиальным отрезкам выявляем, к КД2 нуж¬ но соединить точку M 2 , q2 через узловую точ¬ ку N. Строим КД3 для точки M2, q2 и КД2.

Шаг 3. Соединяем M1, q1 с КД3 через точку N' дуго-радиальным отрезком с узло¬ вой точкой N. Построенная топология крат¬ чайшего дерева для четырех точек имеет минимальную суммарную длину:

L=q(|M1 N'|+|N'N|+|NM3|+|M2N|+|NM4|) = q((|M1N'|+|N'M3|+|M2M4|) или

L=q(|p1 - Pз|+|Pз(ф1 - Ф3) +|p2 - p4|) Топология 2. Пусть весовые коэффици¬

енты q1 > q2 + q3 + q4

Так как в этом случае пункт M1, q1 име¬ ет более значимый вес, можно построить не¬ сколько конфигураций (рис. 3 - а, б, в, г)

б)

в)

г)

Рис. 3. Конфигурация КД4

при q1 > q 2 + q 3 + q 4

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

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

1. Куспеков К.А. Минимальное деревья на Е2 с полярной метрикой. Материалы 6-Международной науно-практической конференции, посвященной 125-летию Национального технического университета «Харьковский политехнической институт» и 10-летию Украинской ассоциации по прикладной геометрии. 21-24 апреля 2009 г. - Харьков, С.93-97.

2. Есмухан Ж.М., Куспеков К.А. Проблемы Штейнера и её прикладной алгоритм. Научный журнал «ПОИСК» №1, 2006, С.227-231.

Definition of optimum topology of the shortest tree for four points of the plane with

polar metrics

K.A. Kuspekov, V.J. Volkov

In article the technique of construction of an optimum configuration of the shortest tree for four points of a plane with the polar metrics is considered. The weight is enclosed to each point - the factor considering indicators of an engineering network.

Волков Владимир Яковлевич - д-р техн. наук, профессор, зав. кафедрой «Начертательной гео­ метрии, инженерной и машинной графики» Сибир­ ской государственной автомобильно-дорожной ака­ демии. Основное направление научных исследований - геометрическое моделирование многокомпонентных многофакторных процессов. Имеет более 200 опуб­ ликованных работ. E-mail: volkov vv39@mail.ru

Куспеков Кайырбек Амиргазыулы - канд. техн. наук, доцент, зав. кафедрой «Начертательной гео¬ метрии и графики» Казахского национального тех¬ нического университета. Основное направление на¬ учных исследований - геометрическое моделирова¬ ние инженерных объектов. Имеет более 66 опубли­ кованных работ.

E-mail: kuspekov k@mail.ru

Введение

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

Авторами были разработаны алгоритмы оп¬ тимизации траектории перемещения объекта с учетом его угловой ориентации на основе наибо¬ лее эффективных современных вычислительных подходов: роевого интеллекта, генетического, вероятностной дорожной карты, декомпозиции линейных и угловых координат, направленного волнового [1,2,3,4,5,6].

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

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

Для сравнительной оценки использовалось 3 частных критерия оценки эффективности ал-

горитмов и методик расчета на их основе:

математическое ожидание значения времени расчетов, с; Me - информационная длина ис­ следуемого алгоритма (требуемый объем па¬ мяти, занимаемой всеми массивами и пере¬ менными алгоритма при его реализации),

байт; 51-усл - математическое ожидание зна­ чения относительной погрешности к условно¬ му глобальному оптимуму целевой функции, % (таблица 1).

Указанные три частных критерия исполь¬ зовались для сравнительного анализа пред¬ ложенных методик путем сравнения числен¬ ных значений критериев при программной реализации соответствующих алгоритмов, т.е. при применении метода эталонных тестов и проведении вычислительных экспериментов [7,8].

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

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

могут быть описаны в форме параллеле¬ пипедов различных размеров [9].

Методом эталонных тестов производилось сравнение разработанных методик поиска оп¬ тимальной траектории объекта на основе: 1 - направленного волнового алгоритма; 2 - ал¬ горитма роевого интеллекта; 3 - генетическо¬ го подхода; 4 - алгоритма декомпозиции ли¬ нейных и угловых координат; 5 - алгоритма вероятностной дорожной карты; 6 - распа¬ раллеленного алгоритма роевого интеллекта; 7 - распараллеленного алгоритма декомпози¬ ции линейных и угловых координат. Для этого были проведены несколько серий вычисли¬ тельных экспериментов, моделирующих про¬ цесс поиска оптимальной по значению целе¬ вой функции траектории перемещения объек¬ та в среде с полидистантными поверхностя¬ ми , построенными вокруг реальных поверхно¬ стей препятствий [10].

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

Количество разбиений каждой траектории на кусочно-линейные участки вдоль оси X0 неподвижной системы координат принима¬ лось равным: /m a x =20. Соответственно, макси¬ мальные значения индексов остальных коор¬ динат груза при поиске траектории принима¬ лись равными: jmax=20; /W=20; /max=5; mmax=17 (индексы /, j, k, /, m соответствовали коорди­ натам x, y, z, у, ю ) .

Сочетание линейных и угловых координат груза позволяет представить область пере¬ метений груза в виде гиперкуба с размерами равномерной сетки индексов (РСИ): 20x20x20x5x17. То есть, полный граф состоя¬ ний объекта при поиске траектории состоял из 680000 вершин.

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

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

Для методик, использующих элементы ве¬ роятностного выбора (на основе алгоритмов № 2, 3 и 5), предварительно были проведены несколько серий экспериментов, по 1200 не¬ зависимых экспериментов для каждого соче¬ тания значений варьируемых параметров, на рабочей области с одинаковым, детермини¬ рованным расположением препятствий, зада¬ ваемых высотами поверхности препятствий Ynp(i,k) и описываемых следующими условия­ ми на РСИ 100x100 (см. рисунок 1,а):

пр(/,к)=2,5 УЛЕ - при (29</<31) и (20<к<80);