авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 |
-- [ Страница 1 ] --

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

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

УНИВЕРСИТЕТ

ВОЛОГОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

БАКИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ВОРОНЕЖСКИЙ ЭКОНОМИКО-ПРАВОВОЙ ИНСТИТУТ

СОВРЕМЕННЫЕ ПРОБЛЕМЫ

ИНФОРМАТИЗАЦИИ

В МОДЕЛИРОВАНИИ И АНАЛИЗЕ

СЛОЖНЫХ СИСТЕМ

Сборник трудов

Выпуск 12

(по итогам XII международной

открытой научной конференции) Издательство "Научная книга" Воронеж - 2007 СПИ-МА-2007 ББК 32.81 С56 Современные проблемы информатизации в моделиро вании и анализе сложных систем: Сб. трудов. Вып. 12/ Под ред. д.т.н., проф. О.Я.Кравца. - Воронеж: "Научная книга", 2007. - 128 с. (129-256) ISBN 978-5-98222-185-8 Сборник трудов по итогам XII Международной открытой на учной конференции “Современные проблемы информатизации в моделировании и анализе сложных систем”, проводившейся в но ябре 2006 - январе 2007 гг., содержит материалы по следующим ос новным направлениям: моделирование сложных систем и техноло гических процессов;

анализ и синтез сложных систем.

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

Редколлегия сборника:

Кравец О.Я., д-р техн. наук

, проф., руководитель Центра дис танционного образования ВорГТУ (главный редактор);

Алиев А.А., д-р техн. наук, проф., зав. кафедрой ИТиП БГУ;

Блюмин С.Л., за служенный деятель науки РФ, д-р физ.-мат. наук, проф., кафедра ПМ ЛГТУ, Водовозов А.М., канд. техн. наук, доц., зав. кафедрой УВС ВолГТУ;

Подвальный С.Л., заслуженный деятель науки РФ, д-р техн. наук, проф., зав. кафедрой АВС ВорГТУ.

ББК 32. С Коллектив авторов, ISBN 978-5-98222-185- СПИ-МА- Введение Уважаемые коллеги!

Перед Вами сборник трудов, опубликованный по итогам двенадца той Международной открытой научной конференции “Современные про блемы информатизации”. Конференция проводилась в рамках плана Феде рального агентства по образованию Воронежским государственным техни ческим университетом, Бакинским государственным университетом, Воло годским государственным техническим университетом, Липецким госу дарственным техническим университетом, Воронежским экономико правовым институтом в ноябре 2006 - январе 2007 гг.

Было решено провести в рамках настоящей конференции три тема тически дифференцированные – «Современные проблемы информатиза ции в непромышленной сфере и экономике», «Современные проблемы ин форматизации в моделировании и анализе сложных систем», «Современ ные проблемы информатизации в проектировании и телекоммуникациях».

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

Представители ведущих научных центров и учебных заведений Рос сии, Украины, Беларуси, Казахстана и Азербайджана представили резуль таты своих исследований, с которыми можно ознакомиться не только в на стоящем сборнике, но и на http://www.sbook.ru/spi.

Настоящий сборник содержит труды участников конференции по следующим основным направлениям:

· моделирование сложных систем и технологических процессов;

· анализ и синтез сложных систем.

Председатель Оргкомитета, руководитель Центра дистанционного образования Воронежского государственного технического университета, д-р техн. наук, проф. О.Я.Кравец kravets@vsi.ru СПИ-МА- 3. Моделирование сложных систем и технологических процессов Авсеева О.В., Журавлев С.В., Кравец О.Я.

ОПТИМИЗАЦИЯ СТРОИТЕЛЬНОГО ПРОИЗВОДСТВА ЗА СЧЕТ ПЕРЕРАСПРЕДЕЛЕНИЯ РЕСУРСОВ ПРИ ОДНОВРЕМЕННОМ СОКРАЩЕНИИ СРОКОВ СТРОИТЕЛЬСТВА mail@vilec.ru В настоящее время в условиях рыночной экономики и самофинанси рования перед строительными компаниями наиболее остро встает вопрос об оптимальном планировании и управлении строительством с целью по лучения большей прибыли. Крупные компании, ведущие одновременное строительство многих объектов, должны планировать свое производство таким образом, чтобы сократить затраты на строительство. Затратная часть строительства в числе прочих содержит затраты на использование рабочей силы и техники (так называемых нерасходуемых или нескладируемых ре сурсов). Уменьшение затрат может быть проведено, в частности, путем пе рераспределения нескладируемых ресурсов между объектами строительст ва.

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

Математическая модель представляет собой следующую задачу: тре буется минимизировать функцию t max c u + g j (y j ) (1) ij ijt jJ iI t =0 jJ d при ограничениях x j s max y l, j s J s, s = 1,...,| F |. (2) s lK ( j ) t -s y j s - x j s t +s, j s J s, s = 1,...,| F |. (3) j j eij s mij s uij st eij s M ij s при t [ x j s, y j s ], i I, j s J s, (4) 1, если js, ресурс i потребляется работой eij s = 0, в противном случае.

СПИ-МА- uij s t = 0 при t [ x j s, y j s ], i I, j s J s. (5) y js r uij st W j s, j s J s, s = 1,...,| F |. (6) ij s iR k t = xx js y js D js, j s J s. (7) |F | u Vi, i I, t 0. (8) ij st s =1 j sJ s uijt, x j, y j 0, (9) uijt, x j, y j - целые, (10) где F - множество объектов строительства;

I - множество ресурсов;

J s множество работ по s -му объекту, s = 1,...,| F | ;

J = U J s - множество работ s по всем объектам строительства;

K ( j ) - множество работ, непосредствен-s но предшествующих работе j s, K ( j s ) J s ;

K - число типов ресурсов, 1 K | I | ;

R1k,..., Rlk - классы ресурсов в каждом типе k, являющихся взаимо заменяемыми, Rsk I, s = 1,...,l, Rsk Rsk = при s1 s2 ;

R k = U Rsk - все ресур 1 s сы типа k, 1 k K ;

mij, M ij - минимально и максимально допустимое ко личество ресурса i, потребляемое работой j, 0 mij M ij +, i I, j J ;

t -, t + - минимальное и максимальное время выполнения работы j, j j 0 t j t + +, j J ;

x j, y j - моменты начала и окончания выполнения ра j боты j ;

x j, y j - целые;

W jt - объем работы j, выполненный к моменту времени t, j J ;

W j - весь объем работы j ;

rij - производительность ресур са i по работе j - объем работы, выполняемый ресурсом i за единицу вре мени по работе j, 0 rij +, i I, j J ;

J ds - множество работ по s -му объекту, имеющих директивные сроки окончания, J ds J s ;

J d = U J ds, s J d J - множество всех работ комплекса, имеющих директивные сроки;

D j - директивный срок окончания выполнения работы j, j J d ;

Vi - коли чество ресурса i, доступное системе в любой момент времени, Vi 0, i I ;

cij затраты на использование ресурса i в работе j, 0 cij +, i I, j J ;

uijt - интенсивность потребления ресурса - количество ресурса i, потреб ляемое работой j в момент времени t ;

t max = max y j.

jJ Первое слагаемое в функции (1) представляет собой затраты на ис пользование ресурсов, а второе – штраф за нарушение директивных сро ков. Штрафные функции g j ( y j ) здесь имеют сложный вид. Они неявно за висят от процента распроданной площади по каждому объекту и от цен на недвижимость в текущий момент времени. Обычно при календарном пла нировании решается задача минимизации времени строительства за счет СПИ-МА- перераспределения ресурсов. В реальности сокращение времени строи тельства не всегда бывает экономически выгодно для компании вследствие постоянного роста цен на недвижимость. И в условиях ограниченных ре сурсов для строительной компании решение перебросить ресурсы с одного объекта на другой (более критичный по срокам завершения вследствие то го, что большая часть квартир уже продана) может привести к сокращению затрат и увеличению прибыли.

Список использованных источников 1. Соболев В.И. Оптимизация строительных процессов. – Ростов н/Д.: Феникс, 2006. – 256 с.

2. Михалевич В.С., Кукса А.И. Методы последовательной оптимиза ции в дискретных сетевых задачах оптимального распределения ресурсов.

– М.: Наука, 1983. - 208с.

3. Вяхирев Д.В. Об одном алгоритме решения задачи альтернативно го распределения ресурсов в сетевых моделях // Технические, программ ные и математические аспекты управления сложными распределенными системами. Материалы научно-технической конференции ООО «ТЕКОМ»

- Н.Новгород, 2003, - с.19-24.

Алексейчик М.И.

О ПОЛИГАРМОНИЧЕСКИХ ПРОЦЕССАХ aarestt@mail.ru Рассматриваются структурные, топологические и аналитические свойства множества H, образованного «гармоническими» системами вида x = Ax.

& 1. Совокупность (вещественных) диагонализируемых n n -матриц A, все собственные значения l которых удовлетворяют условию Re l = 0, обозначим H. Матрицу A, принадлежащую H, и соответствующие ей сис тему x = Ax и дифференциальный оператор ID + A, будем называть гармо & ническими. Совокупность положительно определенных, кососимметрич ных и симметричных n n -матриц обозначим p, k, s. Положим H = clH, p = clp.

Теорема 1. Для произвольной матрицы A следующие утверждения эквивалентны: 1) A H, 2) A H и является устойчивой, 3) A вещественно подобна некоторой кососимметричной матрице, 4) при некоторых P p и K k A представима в виде A = KP (матрицы такого вида называются ква зигамильтоновыми), 5) при некоторых P p и K k A представима в виде A = PK.

СПИ-МА- Ясно, что представление гармонической матрицы в квазигамильто новой форме не однозначно. Операции пер- и центротранспонирования обозначим символами p и c.

Теорема. 2. Если A гармоническая, то такими же будут и матрицы - A, A, - A, Ap, Ac, T -1 AT, rA ( r ( -, ) ). Кроме того, если A 0 (и n четно), то, A H A-1 H.

Следствие 1. Если система x = Ax является гармонической, то такими & же будут и следующие, союзные к ней системы:

инвертированная система: x = - Ax, & транспонированная система: x = Ax, & сопряженная система: x = - Ax, & пертранспонированная система: x = Ap x, & центротранспонированная система: x = Ac x, & подобная система: x = T ATx, - & «обратная» система: x = A-1 x ( A 0 ).

& Теорема 3. Свойство матрицы быть квазигамильтоновой инвариантно относительно вещественного преобразования подобия:

( A = KP, P p, K k ) ( T -1 AT = (T -1 KT -1 ) (T PT ), T -1KT -1 p, T PT k ).

Теорема 4. Пусть A = KP ( P p, K k ). Тогда (положительно опреде ленная) квадратичная форма x Px есть интеграл системы x = Ax. & Следствие 2. Всякая H -система является консервативной и, стало быть, эргодической.

Следствие 3. Всякая H -система подчиняется теореме Пуанкаре о возвращении.

Теорема 5. Положительно определенная квадратичная форма x Px является интегралом системы x = Ax тогда и только тогда, когда AP -1 k.

& Теорема 6. Пусть P, Q p, K k. Следующие условия эквивалентны:

1) x Qx есть интеграл системы x = KPx, 2) PKQ = QKP, 3) x Px есть интеграл & системы x = KQx. При их выполнении QKP k H.

& Теорема 7. Пусть P, Q p, K k. Если P и Q коммутативны, то PKQ, QKP H.

Теорема 8. AB H BA H, если хотя бы одна из матриц A, B не вырожденна (и n четно).

2. Через M n обозначим n2 -мерное евклидово пространство, образо ванное вещественными n n -матрицами. Наделим H топологией, индуци рованной пространством M n. Положим H = H \ int H.

Теорема 9. H, H I H, H \ H суть борелевы подмножества M n.

Теорема 10. H ( H ) есть непрерывный образ некоторого выпуклого множества – множества k p ( k p ) – из n2 -мерного евклидова пространст ва.

Следствие 4. H, H – (линейно) связные множества.

СПИ-МА- Теорема 11. Множество H (равно как и H ) однородно: вместе с ка ждой своей точкой A оно содержит и всю прямую {rA : r ( -, )}.

Следствие 5. Множества H и H звездны относительно точки A = 0.

Следствие 6. Множества H и H стягиваемы.

Ясно, что следствие 6 намного сильнее следствия 4. Однако эти следствия покоятся на весьма различных основаниях.

Теорема 12. Для каждой матрицы A H справедливы следующие два (альтернативных) утверждения: 1) A принадлежит int H, если и только ес ли все ее собственные значения простые, 2) A принадлежит H, если и только если она обладает кратными собственными значениями.

Теорема 13. Для каждой матрицы A H справедливы следующие два (альтернативных) утверждения: 1) A принадлежит H I H, если и только если она диагонализируема (т.е. обладает полным набором собст венных векторов), 2) A принадлежит H \ H если и только если она недиа гонализируема.

Теорема 14. При n 2 int H представимо в виде счетного объедине ния гладких – класса C (и даже аналитических) – многообразий размер ности n2 - n.

3. Пусть l j, 1 j n, суть собственные значения вещественной n n матрицы A. Упорядочив Im l j по убыванию, мы получим некий n -мерный вещественный вектор. Подвектор этого вектора, образованный первыми [ n 2] координатами, обозначим w ( A) ( [] – «целая часть»). Построенный таким способом укороченный [ n 2] -мерный вектор w ( A) будем называть частотным (или спектральным) вектором матрицы A. Через w 2 ( A ) обозна чим [ n 2] -мерный вектор, полученный из (упорядоченных по убыванию) квадратов координат вектора w ( A). Равномерную векторную норму будем обозначать ;

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

Теорема 15. Функция w ( A) непрерывна на M n (в частности на H ). В достаточно малой окрестности каждой точки A0 int H функция w ( A) явля ется аналитической.

% %% % % Ниже мы полагаем, что A = KP, A = KP, P, P p, K, K k.

Теорема 16. 2 w ( A) = PK P A, w ( A) = PK P A 2.

() Теорема 17 (о монотонности). P - P p w ( KP ) w KP.

% % Теорема 18. Справедливы следующие соотношения 2 w 2 ( A) - w 2 ( A) K P - P + P ( K + K ) K - K, % % % % % (K ) K - K% () w 2 ( A) - w 2 A % % % %, K P-P + P +K 2 2 2 2 СПИ-МА- ) ( () 2 w ( A) - w A % % % % % P + P K-K, P- P K P+ ( ) + P% () w ( A) - w A % % % % K -K.

P- P P+ K P 2 2 2 Теорема 19. Матрица e (фундаментальная матрица системы x = Ax ) At & и обратная к ней матрица e являются полигармоническими функциями - At - времени. При каждом t матрица Pe ± At P ортогональна, а линейное пре - образование x ® Pe ± At P x изометрично.

Теорема 19 (достаточно элементарная и хорошо известная в литера туре) открывает возможность эффективного применения (посредством подстановки x = e At y ) теоремы Боголюбова к исследованию возмущенной системы x = Ax + e B ( t ) с почти периодической матрицей-функцией B ( t ).

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

Теорема 20. Если A 0, то скалярный дифференциальный оператор (D + w 2 ) аннулирует и фундаментальную матрицу-функцию, и любое j решение системы x = Ax.

& Теорема 20 (точнее ее разностный аналог) дают необходимое теоре тическое обоснование для выявления частотного состава полигармониче ских процессов методами авторегрессионного спектрального анализа.

Алексейчик М.И.

ПРИМЕЧАНИЯ К СПЕКТРАЛЬНОМУ АНАЛИЗУ aarestt@mail.ru Рассматриваются некоторые уточнения и дополнения к спектральной теореме Шура (теорема 2 ниже) и к теореме Виландта – Хофмана о возму щении спектра нормальной матрицы. Основные результаты получены при весьма ограничительных предположениях ( Re l 0 или Im l 0 ) о спектрах рассматриваемых матриц. Эти предположения, однако, оказываются впол не приемлемыми для некоторых частных, но важных приложений к теории колебаний.

1. Наряду с данной комплексной n n -матрицей A рассмотрим ее эрмитову и косоэрмитову части A+ и A-, определяемые соотношением 2A± = A ± A*. Через l ( A ) обозначим вектор из собственных значений матри цы A, упорядоченных произвольно фиксированным способом. Положим l = l ( A), a = Re l, b = Im l, a + = l ( A+ ), b - = Im l ( A- ).

СПИ-МА- Координаты указанных векторов будем помечать индексом 2 2 2 j {1,K, n}. Отметим, что A = A+ + A- = a + + b -, где – евклидова норма.

2 2 2 2 Теорема 1. A+ - a = d 2 = A- - b, где d = A - l.

2 2 2 2 2 Следствие 1. A+ - A- = a + - b - = a - b.

Следствие 2. A+ A- A+ 1 2 A A- a b.

2 2 2 2 Следствие 3. a = 0 A- = A+ + b, b = 0 A+ = A- + a.

Теорема 2. d 0 ;

причем d = 0 A N, где N – множество нормаль ных матриц.

2 Теорема 2 позволяет величину d = A - l трактовать как меру ук лонения точки A от множества N.

2 2 Следствие 4. 0 d 2 = a + - a = b - - b.

2 2 2 Теорема 3. a + min a - Pa + A+ a + max a - Pa +, 2 2 2 b + min b - P b - A- + max b - P b -, b где min и max берутся по всем матрицам перестановки P.

2 Теорема 4. min a - Pa + d 2 max a - Pa +, 2 min b - P b - d 2 max b - P b -.

Следствие 5. max {min a - Pa +, min b - Pb - } min { A+, A- }.

Теорема 5. b = 0 min a - Pa + A- max a - Pa +, a = 0 min b - P b - A+ max b - P b -.

Установленные результаты дают необходимые логические основа ния и определенные инструментальные средства для проведения совмест ного анализа динамики систем x = Ax, x = A+ x и x = A- x. При этом величины & & & 2 A, A+, A- уместно трактовать как некий «динамический потенциал»

указанных систем.

Сопоставим распределение координат a1,K,a n вектора a с распреде лением координат a1+,K,a n+ вектора a +. Оба распределения обладают оди наковым средним a = n -1trA+ = n -1 Re trA. Теорема 6 показывает, что по срав нению со вторым первое распределение более компактно: оно имеет меньший размах, меньший диапазон и меньшую дисперсию.

Теорема 6. max a + - min a + max a j - min a j, max a + max a j, j j j min a j min a j, причем указанные неравенства являются строгими, если A+ + и A- не имеют общих собственных векторов;

далее, n -1 (a + - a ) n -1 (a j - a ), n -1 (a + - a ) - n-1 (a j - a ) = d 2 n 0, 2 2 j j СПИ-МА- при этом указанные неравенства являются строгими, если A N. Кроме то го, n -1 (a + - a ) n -1 (a j - a ) + n -1 (a + - a j ), 2 j j если a1+,K,a n+ и a1,K,a n упорядочены по убыванию.

Аналогичное утверждение справедливо и для координат векторов b и b. Один из фундаментальных результатов теории возмущений отражает Теорема 7. max j min k a j - a k+ max j min k l j - a k+ A- 2, max j min k b j - b k- max j min k l j - i b k- A+, где 2 – спектральная норма матрицы.

Теорема 8. Если матрица A+ является определенной (положительно или отрицательно), то l j a + + b j-, причем A- 0 l j a +.

j j Аналогичное утверждение справедливо и в случае определенности (эрмитовой) матрицы iA-. Теорема 8 и ее аналог суть прямые следствия де терминантного неравенства Островского – Таусски.

Следствие 6. Если матрица A+ (iA- ) является определенной и b = ( a = 0 ), то a j a + ( b j b j- ), причем равенство достигается j только при A = 0 ( A = 0 ).

- + Следствие 6 допускает очевидную и полезную переформулировку в терминах геометрических средних. Из теоремы 5 и теоремы Виландта – Хофмана вытекает Теорема 9. Предположим, что Re l ( A) = 0, а матрица B косоэрмитова.

Тогда min l ( A) - Pl ( B ) A - B. Это неравенство действительно и в сим метричном случае, когда Im l ( A) = 0, а матрица B эрмитова.

Из теоремы 9 и теоремы Вейля немедленно вытекает Теорема 10. Если матрицы A и B эрмитовы, а их (вещественные) собственные значения упорядочены по убыванию, то l ( A) - l ( B ) A - B, l ( A) - l ( B ) A - B 2, где – равномерная векторная норма.

2. В пространстве R n рассмотрим систему && + Bx + Cx = 0, кратко обо x & значаемую S. Через H обозначим совокупность систем S, характеристи ческий полином которых не имеет корней с ненулевой вещественной ча стью, а имеет только корни вида ± -1w j, w j [ 0, ), j {1,K, n}. Упорядочив частоты w j = w j ( S ) по убыванию, образуем n -вектор w = w ( S ). Через w 2 = w 2 ( S ) обозначим n -вектор, полученный из квадратов координат век тора w = w ( S ). Совокупность устойчивых по Ляпунову систем S H, обла дающих только положительными (любыми неотрицательными) частотами, обозначим H ( H 0 ). Системы, принадлежащие H, H 0 \ H или H \ H 0 назы ваются соответственно собственно гармоническими, обобщенно гармони СПИ-МА- ческими или квазигармоническими. В вещественном евклидовом про странстве, образованном блочными n 2n -матрицами ( B C ), множества H, H 0, H являются связными (и, более того, стягиваемыми и, следова тельно, линейно связными) борелевскими множествами, причем H = clH = clH 0.

Для всякой системы S H справедливо соотношение 2 2 2, 2 w + B+ + + + = B- + + B- +2 + C- C+ где B++, B-+ (C+, C- ) – неотрицательно и неположительно определенные + + части симметричной матрицы B + ( C + ). Матрицы B++ и B-+ получаются из спектрального разложения B + = m j v j vj матрицы B + ( B+ - B- ) путем заме + + ны m j на max {m j, 0} и - min {m j, 0} соответственно. Отметим, что в приве денном выше соотношении не фигурирует матрица C -.

Полагая матрицы P1,K, P4 положительно определенными, рассмотрим системы S1 : && + P1P2 x = 0 и S2 : && + P3 P4 x = 0. При сравнительном спектральном x x анализе этих (принадлежащих H ) систем важную роль могут играть оцен ки:

2 w 2 ( S1 ) - w 2 ( S2 ) min ( Pi Pj - Pl + Pl Pi - Pk ), ( ), w 2 ( S1 ) - w 2 ( S2 ) min Pi Pj - Pl + Pl Pi - Pk 2 2 2 w ( S1 ) - w ( S 2 ) min Pk Pl Pk, Pi Pj Pi w ( S1 ) - w ( S 2 ), min Pi Pj Pi - Pk Pl Pk где min берется по i, j {1, 2}, i j, k, l {3, 4}, k l. Отметим, что последнее неравенство допускает удовлетворительную рациональную аппроксима цию.

Считая n четным, матрицу P положительно определенной, а матри цу G невырожденной кососимметричной, рассмотрим систему S : && + Gx - Px = 0, хорошо известную в механике в связи с задачей гироско x & пической стабилизации. Полагая S H (что имеет место при подходящем выборе G ), системе S сопоставим (принадлежащую H 0 \ H ) систему S : && + Gx = 0. Приняв w = w ( S ), w = w ( S ), можем записать:

% %x % & P, max w 2 max w 2 - min l j ( P ) min l j ( P ), max j min k w j - w k % %j j 2 2 2 2 2 2 w w + w -w, w2 w2 + w, w2 PG P.

w2 + % % % % Считая P положительно определенной, а G кососимметричной мат рицами, введем в рассмотрение системы S1 : && + Gx = 0, S2 : && + Px = 0, S3 : && + Gx + Px = 0.

x x x & & СПИ-МА- Ясно, что S1 H 0, S2, S3 H. Примем i w = w ( Si ), i {1, 2,3}. При совме стном спектральном анализе рассматриваемых систем важное значение 2 2 могут иметь тождество 3w = 1w + 2w и следующие неравенства:

, iw - j w k w, w - j w k w, "i k j ;

w - jw kw i i 2 2 1w 2 + 2w 2, G 0 3w 2 2 2 2 2 1w 2 + 3 w 2 - 1w 2, 2w 2 + 3w 2 - 2w 2.

w2 w 3 В заключение отметим, что исследование соотношений между сис темами S1, S 2, S3 становится особенно удобным и плодотворным в так назы ваемом нормальном случае, т.е. в случае коммутативности (положительно определенной и кососимметричной) матриц P и G. Отметим, что в этом случае дифференциальный оператор ID 2 + 2GD + P допускает следующее мультипликативное представление ( )( ) ID 2 + 2GD + P = ID + G + i P - G 2 ID + G - i P - G 2.

Изложенный материал примыкает к работам [1-5], содержащим биб лиографию.

Список использованных источников 1. Андерсон Т. Статистический анализ временных рядов. М.: Мир, 1976. 755 с.

2. Заковоротный В.Л. Динамика трибосистем. Самоорганизация, эволюция. Ростов н/Д: Издат. центр ДГТУ. 2003. 502 с.

3. Заковоротный В.Л., Блохин В.П., Алексейчик М.И. Введение в динамику трибосистем. Ростов н/Д: ИнфоСервис, 2004. 680 с.

4. Заковоротный В.Л., Флек М.Б. Динамика процесса резания. Си нергетический подход. Ростов н/Д: Терра, 2006. 875 с.

5. Марпл-мл. Л.С. Цифровой спектральный анализ и его приложения.

М.: Мир, 1990. 584 с.

Бабкин Е.А., Бобрышев Е.А.

О СОБЫТИЙНЫХ МОДЕЛЯХ ДИСКРЕТНЫХ СИСТЕМ bea@kursknet.ru, egbobryshev@mail.ru Введение Для представления имитационных моделей дискретных систем (ДС) ДС существуют следующие виды моделей [8]: модели, ориентированные на процессы, транзактные модели, событийные модели и модели, ориентированные на активности.

СПИ-МА- В событийных моделях основным объектом является событие, и про цесс функционирования ДС представляется в виде последовательности со бытий.

Существует множество разных подходов, явно или неявно иденти фицируемых как концепции дискретного событийного моделирования [4].

1. Формально–логические подходы (например, формализм Лакне ра);

2. DEVS – формализм;

3. Сущностная структура системы;

4. Событийно–ориентированные графические методы (событийные графы, имитационные графы, событийные алгоритмы);

5. Диаграммы циклов активности;

6. Сети Петри;

7. Логико–базируемые подходы;

8. Графы потоков управления;

9. Обобщенные полумарковские процессы.

10. Подходы, основанные на макс-алгебре и др.

В данной работе развивается идея, предложенная в [7,8]. Обобщается понятие событийного алгоритма, даются определения потоков событий и предлагается символьная нотация событийных алгоритмов.

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

Статические свойства системы будем представлять в виде набора пе ременных состояния xi X таких, что вектор значений (x1, x 2,..., x n ) X (n ) однозначно определяет ее состояние.

Под функцией изменения состояния будем понимать некоторую функцию j : X (n ) ® X (n ). Под входной функцией будем понимать некоторую функцию j : I ® X (n ), где I = ( x1I, x2I...xm ) – множество векторов на входе, оп I ределяющих влияние на систему внешней среды. Под выходной функцией будем понимать некоторую функцию j : X (n ) ® O, где O = ( x1O, x2,..., xkO ) – O множество векторов на выходе, определяющих влияние системы на внеш нюю среду. Векторы I и O, а также входные и выходные функции служат также для представления взаимодействия с внешней средой.

Определим аналогично функции изменения переменной состояния.

( n) f :X ® Xj, j:I ® Xj.

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

Определим событие как мгновенное изменение состояния некоторой подсистемы системы S [3]. В принципе может возникнуть ситуация, когда СПИ-МА- событию не соответствует изменение какой–либо переменной состояния, однако эту ситуацию можно разрешить, учитывая, что для данной задачи имеет смысл лишь сам факт события, и не играет роли соответствующее ему изменение состояния. Такое событие назовем обобщенным.

Событие e может иметь следующие атрибуты:

· t ( e ) – момент времени, когда произойдет событие;

· fi – функция изменения переменной состояния, входная или вы ходная функция, соответствующая данному событию.

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

Кроме того для идентификации событий удобна давать ему имя и/или уни кальный идентификатор.

Событие e назовем входным для системы s, если ему соответствует входная функция j I, выходным для системы s, если ему соответствует вы ходная функция jO, собственным событием системы s, если ему соответ ствует функция изменения переменной состояния j X.

События с соответствующими им функциями описывают динамиче ские свойства подсистем системы.

Событийным алгоритмом системы s назовем граф G = V, A, D, где V = E C U – множество вершин графа, A = A0 At – множество дуг гра фа, – множество функций инцидентности. Здесь · Е – множество вершин графа, отображающих события в подсисте ме. "e E (d o (e ) {0,1}) (d i (e ) Z + ) ( Z + = N {0}, N – множество натуральных чисел);

· С – множество вершин графа, отображающих выбор. Каждой вер шине c C сопоставим некоторую функцию con : I X (n ) ® L R, представ ляющую собой условие выбора планируемых событий.

"c C (d o (e ) N ) (d i (e ) N ). Каждой инцидентной по выходу дуге для c C ставиться в соответствие некоторое подмножество множества L, опреде ляющее выбор пути. В случае, если некоторый выход должен быть безус ловным, поставим ему в соответствие множество L.

· U – множество объединяющих вершин. Каждой вершине u U со поставим некоторую функцию un : I X (n ) H ® U R, где H – история – множество состоящее из упорядоченных наборов событий.

"u U (d o (e ) N ) (d i (e ) N ).

· A0 – множество дуг первого рода, определяемых следующим обра зом: "a A0 a = (v1, v 2 ), v1, v 2 E C U.

СПИ-МА- · At – множество дуг второго рода, определяемых следующим обра зом: "a At a = (v1, v 2 ), v1 E C U ;

v 2 E U. Каждой дуге второго рода ставиться в соответствие некоторая функция t : X ® T = R +, где T – множе ство интервалов времени;

– некоторое множество, определяемое пред метной областью. В частности, это может быть множество T, либо множе ство X (n ).

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

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

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

Графом макрособытий назовем граф MG = ME, At, Д, где ME – мно жество вершин, обозначающих макрособытия. Вершина макрособытия me ME замещает собой подграф событийного алгоритма системы.

Событийной моделью системы назовем EM = G, X ( n),F,C,e0, где · G – событийный алгоритм системы.

· X ( n) – множество состояний системы.

· F –множество функций изменения состояния.

· C – множество функций выбора для вершин v C U.

· e0 – событие инициализации модели.

Событийные алгоритмы представляют собой удобный инструмент для описания событийных моделей дискретных систем. Для формализации СПИ-МА- задачи построения событийного алгоритма, равно как и для его преобразо вания в программно реализуемые графы макрособытий [7,8] или событий ные графы [5,6], однако требуется некоторый формально–логический ин струмент, обладающий следующими свойствами:

· способность отображать планирование событий;

· способность учитывать время планирования событий;

· способность учитывать условия планирования и выполнения со бытий.

Задача создания подобной формальной системы, была поставлена еще в середине XX в. Главной целью, однако, в этом случае была создание теоретической основы дискретно–событийно моделирования.

Майкл Лакнер в 60–е гг. XX в. [2,3] представил теорию дискретных событийных систем, в которых изменение, а не время, стало первоначаль ным;

теория и «Исчисление Изменений» требуют, чтобы время определя лось в терминах изменений.

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

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

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

Введем представление отношения планирования, отображаемое Dt стрелкой ®, где знак Dt – интервал планирования. Это отношение опи сывает класс пар логических ситуаций «предыдущий–следующий» и ото бражается как a Dt ® e. Здесь a – высказывание о происхождении события или некоторая логическая функция высказываний о происхождении собы тий и о состояниях подсистем;

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

СПИ-МА- Если через время Dt после того, как произошло событие e1 должно произойти событие e2, то будем говорить, что e1 планирует e2 с интерва лом Dt и обозначать e1 Dt ® e2 или e2 ¬Dt e1.

Если событие e1 планирует событие e2 только при условии с, то бу дем обозначать это как e1 c Dt ® e2 или e2 ¬Dt e1 c.

Следует также заметить, что событие e2 может планироваться не сколькими событиями одновременно или же планироваться при условии, что произошли или не произошли некоторые другие события. В этом слу чае в определении допустимы отношения дизъюнкции, конъюнкции или отрицания применимо к событиям и/или к условиям.

Например, если событие e3 произойдет через Dt после e1 при усло вии, что произойдет событие e1 и до момента времени t ( e1 ) + Dt не про изойдет событие e2, то обозначим это как e1 e2 Dt ® e3. Здесь t ( e1 ) – момент времени, когда произошло событие e1.

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

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

Формальным потоком событий назовем такое индексированное множество событий Tr = ei i = 1, n, что "ei Tr \ {e0 } ( ei -1 c t ® ei ) (здесь c – некоторая логическая функция), причем $ek E ( ek ei -1 t ® ei ).

Два формальных потока событий Tr1 = ei i = 1, n и Tr2 = e j j = 1, m на зовем параллельными, если ( ) ()( ) "ei Tr1 "e j Tr2 ( ei e j ) $ei Tr1 $e j1, e j2 Tr2 t ( e1 ) t e j1 ;

t e j Два формальных потока событий Tr1 = ei i = 1, n и Tr2 = e j j = 1, m на ( ) зовем пересекающимися, если $ei Tr1 $e j Tr2 ( ei = e j ) ( ei t ® e j ) Будем говорить, что два параллельных потока событий Tr1 = ei i = 1, n и Tr2 = e j j = 1, m сходятся к событию ek, если em cm en cn Dt ® ek, где cm, cn – некоторые логические функции.

В случае описания потоков событий допускается последовательная нотация их следования, например e1 Dt ® e2 c1 0 ® e3 c2 Dt ® e4.

1 Фактическим потоком событий назовем множество уже произошед ших в системе событий, упорядоченных по времени.

СПИ-МА- Пример В качестве примера рассмотрим модель СМО с отказами с одним ка налом и одним конечным накопителем (рис. 2).

Рис. 2. Система массового обслуживания Введем следующие переменные состояния системы: x = ( x1, x2, x3, x4 ) x1 – состояние канала. x1 = 0, если канал занят и x1 = 1, если свободен.

x2 – количество элементов в очереди. Если вместимость очереди m, то она имеет m + 1 состояние.

x3 – количество поступивших заявок.

x4 – количество отклоненных заявок.

Начальное состояние системы x0 = (1, 0, 0, 0 ) Рассмотрим события возникающие в системе.

eпз – событие поступления заявки в систему ( x3 + + ). Если заявки по ступают постоянно с задержкой tпз, то eпз t ® eпз.

пз Канал может генерировать 2 события: eзк – занятие канала ( x1 = 0 ) и eoк – освобождение канала ( x1 = 1 ). Причем, если заявка в канале обрабаты вается tоз единиц времени, то eзк t ® eок. оз В очереди могут происходить следующие события:

eпзо – поступление заявки в очередь ( x2 + + ).

eузо – удаление заявки из очереди ( x2 - - ).

eооз – отказ в обработке заявки ( x4 + + ).

Итак, при поступлении заявки в СМО происходят следующие собы тия:

если канал занят, то если очередь не полна, то заявка становится в очередь иначе, происходит отказ в обслуживании заявки иначе заявка поступает в канал для обработки.

То есть мы имеем eпз ( x1 = 1) ® eзк eпз ( x1 = 0 ) ( x2 m ) ® eпзо eпз ( x1 = 0 ) ( x2 = m ) ® eооз СПИ-МА- В свою очередь, при освобождении канала, в случае, если очередь не пуста происходит удаление первой заявки из очереди и занятие ею канала, то есть eок ( x2 0 ) ® e узо и eузо 0 ® eзк.

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

Графическое представление событийного алгоритма для данного примера приведено на рис. 3.

Рис. 3. Событийный алгоритм СМО Выводы Итак, в данной работе в качестве обобщения были даны формальные определения событийного алгоритма, графа макрособытий, потоков собы тий.

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

Список использованных источников 1. Ingalls R.G., Morrice D.J., Yucesan E., Whinston E.B.. Execution Conditions: A Formalization of Event Cancellation in Simulation Graphs INFORMS Journal on Computing © 2003 INFORMS Vol. 15, No. 4, Fall 2003, pp. 397– 2. Lackner, M.R. (1964). ``Digital Simulation and System Theory,'' Sys tem Development Corporation, Santa Monica, CA.

3. Lackner, M.R. (1962). ``Toward a General Simulation Capability,'' In:

Proceedings of the AFIPS Spring Joint Computer Conference, pp. 1-14, San Francisco, CA, May 1-3.

4. Page E.H. Jr, Simulation modeling methodology: principles and etiol ogy of decision support.

СПИ-МА- 5. Schruben L.W. Mathematical programming models of discrete event system dynamics. 2000 Winter Simulation Conference 6. Schruben L.W. Simulation Modeling with Event Graphs. Communica tions of the ACM. 26: 957–963 (1983).

7. Бабкин Е.А. Методические указания по моделированию вычисли тельных систем на событийно-ориентированном языке. – Ротапринт, Курск, КПИ, 1988.

8. Бабкин Е.А. Событийные модели дискретных систем. – Курск. гос.

ун-т. Курск, 2005. – 18 с. Деп. в ВИНИТИ 14.01.05, № 30-В2005.

Барановский Н.В.

МОДЕЛЬ КОМПАНДЕР-ЭКСПАНДЕР ДЛЯ СИСТЕМЫ УСВОЕНИЯ ДАННЫХ ОБ УРОВНЕ АНТРОПОГЕННОЙ НАГРУЗКИ НА КОНТРОЛИРУЕМОЙ ЛЕСОПОКРЫТОЙ ТЕРРИТОРИИ firedanger@narod.ru В работах [1, 2] представлены новый вероятностный критерий лес ной пожарной опасности и критерий прогноза лесопожарных возгораний, которые учитывают метеоданные, грозовую активность и антропогенную нагрузку. Однако применение формулы для определения вероятности воз никновения лесных пожаров непосредственно для каждого выдела затруд нено (необходимо использовать некоторые интегральные коэффициенты по лесничеству или лесхозу, так как количество имеющихся статистиче ских данных по числу лесных пожаров по отдельно взятым выделам не достаточно для репрезентативности данных об уровне антропогенной на грузки на территории отдельно взятого выдела). На контролируемой тер ритории антропогенная нагрузка может исходить от населенного пункта, дороги или взаимного влияния этих источников антропогенной нагрузки.

Цель исследования – разработать математическую модель системы усвоения данных об уровне антропогенной нагрузки (СУДАН).

Первостепенной проблемой создания СУДАН является отсутствие теоретических основ проблемы антропогенного влияния (стресса) и веро ятностного прогнозирования лесных пожаров. Поэтому представим неко торые определения и понятия данной теории.

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

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

Фоновая АН характеризуется минимальным уровнем АН на КЛПТ.

Во многих случаях для простоты фоновый уровень АН может быть поло жен равным уровню природной пожарной опасности (не более 2 %).

Существуют точечные и линейные источники АН. Кроме того, АН на КЛПТ может быть в результате суперпозиции источников АН. Будем считать уровень фоновой антропогенной нагрузки не превышающим уро вень лесной пожарной опасности от грозовой активности. В дальнейшем для простоты мы их приравняем. Кстати, для Тимирязевского лесхоза Томской области такое допущение соответствует действительности, так как число пожаров от гроз составляет менее 1,4 % [3].

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

Рис.1. Точечный источник АН: схема воздействия (1.а) и функция распределения вероятностей (1.б) - определяется по статистическим дан ным.

На рисунке 2 представлен линейный источник АН.

Рис.2. Линейный источник АН: схема воздействия (2.а) и функция распределения вероятностей (2.б) - определяется по статистическим дан ным СПИ-МА- Рассмотрим математическую модель СУДАН, базирующуюся на процедуре компандер-экспандер. Будем рассматривать точки зарегистри рованных лесных пожаров как точки экспериментальных данных по полю распределения АН в окрестности ее источника (в данной работе рассмат ривается точечный источник). Необходимо ввести дополнительную поляр ную систему координат на рассматриваемой территории с центром в насе ленном пункте. Направление оси Х принять в соответствии одному из на правлений (север, юг, запад, восток). Из статистических данных определя ется радиус круга, в котором будем рассматривать поле АН. Разделим круг на несколько секторов (число разбиений определяется из статистических данных). В итоге будем иметь сетку в рассматриваемой области.

Сканирование области будем проводить по направлению часовой стрелки. Пусть сектор будет равен 450. Как уже было сказано данных очень мало и поэтому необходимо неким образом интерпретировать имеющиеся данные и обобщить их на всю рассматриваемую область. Для системы ус воения нужны сведения о пространственном распределении лесных пожа ров за прошлые лесопожарные сезоны. Для этого могут быть использованы книги регистрации пожарных происшествий. Принцип действия системы усвоения. В некоторой e-окрестности (определяется по статистическим данным) точечного источника АН проводится разделение на сектора. За тем все случаи зарегистрированных лесных пожаров, находящиеся в пре делах +450/2 от лучей, разделяющих круг на сектора, при одинаковых рас стояниях от точечного источника, проецируются на эти направляющие лу чи. То есть идет процедура сжатия данных (процедура компандер). В итоге по каждому направляющему лучу будем иметь зависимость числа пожаров от расстояния от точечного источника.

После этого этапа методами сплайн-идентификации и аппроксима ции таблично-заданных функций [4] восстанавливается зависимость числа лесных пожаров (либо уровень АН) от расстояния от точечного источника АН в направлении каждого направляющего луча. После работы процедуры компандера и восстановления зависимости в направлении луча нам необ ходимо распространить эти данные на весь сектор (случай распростране ния), либо с помощью сплайн-идентификации и аппроксимации таблично заданных функций восстановить информацию об уровне АН в сечении R=const для всех таких сечений по всем секторам (случай восстановления).

Это процедура экспандера. После работы процедуры экспандера будем иметь некоторое поле распределения АН в интересующей нас области.

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

СПИ-МА- Список использованных источников 1. Н.В. Барановский. Влияние антропогенной нагрузки и грозовой активности на вероятность возникновения лесных пожаров // Сибирский экологический журнал, 2004. № 6, с. 835- 2. Г.В. Кузнецов, Н.В. Барановский. Детерминированно вероятностный прогноз лесопожарных возгораний. // Пожаровзрывобезо пасность. 2006, Т. 15. № 5, С. 56 – 59.

3. Маценко В.В., Соколов А.Я., Калинин С.И., Андриянова Ф.И., Ан дреева Т.А., Ананьин С.В., Крылов М.Н., Казанцева Л.В. Генеральный план противопожарного устройства лесов. Том 1. Пояснительная записка.

5-99.14-17-ПМ. Барнаул: Государственный проектно-изыскательский ин ститут «Росгипролес», Алтайский филиал, 1999. 139 С.

4. О.В. Бартеньев. Фортран для профессионалов. Математическая библиотека IMSL: Ч. 3. М.: Диалог-МИФИ, 2001. 368 с.

Березенко Е.Р.

К ВОПРОСУ ИССЛЕДОВАНИЯ ИМИТАЦИОННОЙ МОДЕЛИ ОПЕРАТОРА ТАКТИЧЕСКОЙ ОБСТАНОВКИ (ОБСЛУЖИВАНИЕ МНОГОЦВЕТНОГО ПОТОКА) Helen154@yandex.ru В современных условиях широко применяются радиолокационные станции для наблюдения за различными объектами (целями) с задачами обнаружения, распознавания, определения их местоположения, скорости и направления движения, а также управления ими или поражения (в систе мах вооруженной борьбы с воздушным, морским или наземным противни ком). С точки зрения системы массового обслуживания оператор РЛС ре шает задачи по обслуживанию неоднородного потока требований, посту пающих на экран.

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

В качестве прибора для обслуживания поступающих требований рас сматривается оператор.

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

Построенная имитационная модель оператора дает возможность:

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

прогнозировать и оптими зировать деятельность оператора;

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

Список использованных источников 1. Л.Клейнрок Вычислительные системы с очередями М., Мир, 1979.

Блюмин С.Л.

БЫСТРЫЕ ОТОБРАЖЕНИЯ slb@stu.lipetsk.su Быстрые алгоритмы выполнения операций используются в различ ных областях прикладной математики (см., например, [1]). При их форму лировке в терминах отображений (см., например, [2]) следует учитывать наличие произведений отображаемых множеств, композиций отображе ний, изменения их порядка. Так, если A, B, C, D, K, L, M, N, S – некоторые множества, k:AC®K, l:AD®L, m:BC®M, n:BD®N, s:KLMN®S – некоторые отображения, то быстрое отображение их композиции опре деляется существованием множеств T,U и отображений t:AB®T, u:CD®U, v:TU® S таких, что s(k(a,c), l(a,d), m(b,c), n(b,d))=v(t(a,b), u(c,d)), так как в правой части этого равенства используются 4 отображения про изведений пар и 1 отображение произведения четырех множеств, а в пра вой – 3 отображения произведений пар множеств:


A C.

|.\ /.

| | | | |/ |\ | | B D |.

k l m n | | K L. M N | | t | u |.

T U s v S СПИ-МА- Если множества A,…,S совпадают с А, отображения k,l,m,n совпа дают и задают бинарную операцию на А (так что A, - группоид [2]), и при этом задана еще одна коммутативная ассоциативная операция · на А (так что A, · - коммутативная полугруппа[2]), определяющая тетрарную операцию s, то множества T,U совпадают с А, отображения t,u совпадают с операцией ·, отображение v совпадает с операцией, вышеуказанное ра венство выражает ее дистрибутивность относительно ·, (a·b)(c·d)=(ac)·(ad)·(bc)·(bd) (так что A, ·, - кольцоид [2]), и в то же время – быстрое выполнение правой части, содержащей 4 операции и 3 операции ·, сводящихся в ле вой части к 1 операции и 2 операциям ·.

Список использованных источников 1. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. – М.: Мир, 1989. – 448 с.

2. Общая алгебра / Под общ. ред. Л.А. Скорнякова. – Тт. 1,2. – М.:

Наука, 1990, 1991. –592 с., 480 с.

Блюмин С.Л.

РЕДУКЦИЯ АРНОСТИ АЛГЕБРАИЧЕСКИХ ОПЕРАЦИЙ И НОРМАЛЬНЫЕ ФОРМЫ ДИСКРЕТНЫХ СИСТЕМ slb@stu.lipetsk.su Пусть A,b - группоид, то есть над элементами множества А задана бинарная алгебраическая операция b:АА®А, b:(a,b)|®b(a,b). Редукция ее арности означает [1], что она индуцирует унарную операцию w:АА®АА над парами элементов множества А, которая может быть за дана, например, в виде w:(a,b)|®(b(a,b),a). Если считать, что операции вы полняются потактно, то слева координаты пары берутся на предыдущем такте, а справа – на текущем. Переходя на язык сосредоточенных систем с дискретным временем t{…,-1,0,1,…} и состоянием х=(х1,х2)ХХ, это можно записать в виде x1[t]=b(x1[t-1],x2[t-1]), x2[t]=x1[t-1], который, как из вестно из теории дискретных систем [2], представляет нормальную форму из двух уравнений первого порядка автономной системы, описываемой одним уравнением второго порядка x[t]=b(x[t-1],x[t-2]), получаемую вве дением переменных x1[t]=x[t], x2[t]=x[t-1]=x1[t-1], так что x2[t-1]=x[t-2].

Аналогичным образом переход к нормальной форме системы, описывае мой уравнением n-го порядка x[t]=n(x[t-1],...,x[t-n]), может быть истолко ван как редукция n-арной операции n:Х…Х®Х к унарной w:Х…Х®Х…Х. Подобные преобразования известны и в теории дифференциальных уравнений и систем. С другой стороны, в [3] показано, СПИ-МА- как тернарная операция t:ХХX®X, описывающая распределенную 2D систему x[t,s]=t(x[t-1,s],x[t,s-1],x[t-1,s-1]), может быть редуцирована к би нарной b:(ХХ)(ХХ)®ХХ переходом к базовой 2D-модели и к после довательности унарных – переходом к ассоциированной сосредоточенной модели переменной структуры. В [4] показано, как тернарная операция, описывающая одномерный клеточный автомат x[t,s]=t(x[t-1,s-1],x[t-1,s],x[t 1,s+1]), может быть редуцирована к бинарной. В [5] показано, как пентар ная операция, описывающая двумерный клеточный автомат x[t;

s1,s2]=p(x[t 1;

s1,s2],x[t-1;

s1-1,s2],x[t-1;

s1+1,s2],x[t-1;

s1,s2-1],x[t-1;

s1,s2+1]), может быть ре дуцирована к последовательности унарных переходом к его ассоциирован ной модели.

Список использованных источников 1. Langer H. Induced groupoids and induced semigroups // Contributions to General Algebra. – 1979. – No. 1. – P. 177-186.

2. Иванов В.А., Ющенко А.С. Теория дискретных систем автомати ческого управления. – М.: Наука, 1983. – 336 с.

3. Блюмин С.Л. Двумерные преобразования сигналов и анализ дву мерных систем. – Липецк: ЛГТУ, 1991. – 76 с.

4. Pedersen J. Cellular automata as algebraic systems // Complex Sys tems. – 1992. – Vol. 6, No. 3. – P. 237-250.

5. Блюмин С.Л. О конструировании линейными клеточными автома тами // Автоматика и телемеханика. – 1981. - № 11. – С. 131-138.

Гольдштейн М.Л.

БАЗОВАЯ КОНЦЕПТУАЛЬНАЯ МОДЕЛЬ ДЕЯТЕЛЬНОСТИ ПО ОБЕСПЕЧЕНИЮ АКТИВНЫХ ЭТАПОВ ЖИЗНЕННОГО ЦИКЛА НПС-СКЦ mlg@imm.uran.ru Институт математики и механики УрО РАН (ИММ) является голов ной организацией в УрО РАН по развитию вычислительных, телекомму никационных и информационных ресурсов. Общая специфика таких ре сурсов – многопроцессорность, сложность, дороговизна. Один из способов их массового освоения и применения – концентрация в суперкомпьютер ных центрах (СКЦ), работающих на регулярной основе (24 часа в сутки), и коллективное использование в рамках организации, корпорации, региона, страны в целом. При этом целесообразно рассматривать СКЦ как социо техническую научно–практическую структуру (НПС). СКЦ–НПС обеспе чивает функции производства и НИОКР вычислительных, информацион ных, телекоммуникационных и образовательных услуг в рыночной эконо мике, направленных на удовлетворение интересов всех участников дея СПИ-МА- тельности. Система сложная и эта сложность просматривается как на уровне обеспечения собственного жизненного цикла (ЖЦ), так и ЖЦ целе вого наполнения. Где ЖЦ представлен пятиблочной моделью “создание – функционирование – поддержка функционирования – реинжиниринг – за вершение”, из которых создание, поддержка и реинжиниринг можно отне сти к активным этапам по признаку получения нового качества. Сложность подобных систем требует разрешения комплекса проблем и задач не толь ко на профильном уровне, но и на системном. Путь их разрешения – мо делирование проблемных ситуаций (ПС) с последующим их анализом и синтезом оптимальных решений, направленных на снижение неопределён ностей всех видов.

В развернутой форме деятельность по обеспечению активных этапов ЖЦ СКЦ ИММ может быть описана в форме базовой концептуальной мо дели с функциями:

a) систематизации понятий, знаний и действий по основаниям:

- объекты-источники ПС, - ресурсы для разрешения ПС, - модель деятельности по разрешению ПС, - системно-интеллектуальная поддержка деятельности, - эффективность деятельности;

б) объединения понятий, знаний и действий с учетом сложности ПС;

в) использования понятий, знаний и действий для фиксации реально го и желаемого состояний ситуации.

Пути реализации функций – применение:

а) передовых технологий:

- параллельных вычислительных;

- телекоммуникационных;

- научно-исследовательских (компьютерные лаборатории со спе циализацией в области параллельных вычислительных технологий и мно гопроцессорных систем);

- производственных (промышленные предприятия с конкретными задачами для многопроцессорной вычислительной техники);

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

б) системных методов: фиксации реального состояния;

целеполага ния;

фиксации желаемого состояния;

в) интеллектуальных диалогов по схеме: лицо, принимающее реше ние/эксперт/разработчик;

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

лицо, принимающее решение/объект;

г) аппарата моделирования:

- вербального (предметно-гуманитарного);

- полуформализованного, называемого так потому, что, обладая полностью формализованным (аналитическим или функционально эквива СПИ-МА- лентным графическим) синтаксисом, он связан с нечеткой семантикой и, особенно, прагматикой. В состав системы полуформализованных моделей включены: концептуальные (общая, базово-уровневая и модификацион ная), выполненные по пятиблочной схеме “функции – пути реализации – структура – направленность – цель”;

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

структурно-функциональные (в SADT формализме), описывающих процессно-логитическую компоненту разви ваемого СКЦ (структурный состав, применяемые технологии, взаимодей ствие информационных и управляющих потоков);

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

- формального (математического).

Структура: системно-интеграционный подход, управление и плани рование, анализ и синтез.

Направленность: разрешение сложных ПС на активных этапах ЖЦ специальной инструментально-технологической среды, каковой является НПС-СКЦ.

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

Гребенникова Н.И., Нужный А.М.

АВТОМАТИЗАЦИЯ ПОИСКА ОПТИМАЛЬНЫХ ПАРАМЕТРОВ СХЕМЫ ТЕХНОЛОГИЧЕСКОГО ПРОЦЕССА g-naty@yandex.ru Автоматизация проектирования технологических схем должна быть организована на основе максимального использования в проектах новей ших достижений науки и техники с тем, чтобы они имели высокие техни ко-экономические показатели. Наиболее перспективным направлением в решении этой проблемы является автоматизация расчетов на основе при менения графических моделей и средств вычислительной техники.

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


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

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

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

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

Гребенникова Н.И., Мальцева Т.В.

ПРИМЕНЕНИЕ МЕТОДОВ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ ПРИ РАЗРАБОТКЕ СХЕМ ТЕХНОЛОГИЧЕСКИХ ПРОЦЕССОВ g-naty@yandex.ru Для достижения высокого уровня развития технологических процес сов значительно повышаются требования к сокращению сроков нахожде СПИ-МА- ния решений, которые должны обеспечить высокий уровень производства.

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

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

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

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

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

СПИ-МА- Думачев В.Н.

О ГЕОМЕТРИИ МОДЕЛИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ СТОХАСТИЧЕСКИХ СИСТЕМ dumv@comch.ru В работе рассматривается задача исследования поведения модели объекта управления, описываемой стохастическими дифференциальными уравнениями. Рассмотрим систему дифференциальных уравнений как подмногообразие S в расслоении джетов J n (p ) : E ® M, определяемое F (x, w, p00, p10, p01, p 20, p11, p02 ) = 0, x, w M R, уравнениями где u = p0 U R, pi J i (p ) R n, E = M U. Как и любое дифференциаль ное уравнение оно описывает струю в пространстве джетов J 1 (2,1), с ло кальными координатами ( x, w, u, u t, u w, u ww ), где расширение расслоения до вторых производных (u ww ) является следствием корреляционых соотно шений для средних Винеровского процесса dw = 0, dw 2 = dx.

Последние соотношения позволяют ввести распределение Картана для СДУ в виде q = du - u x + u ww dx - u w dw.

I = q0 I q Градуированный идеал во внешней алгебре L* ( X ) = q0 Lq ( X ) форм класса C на многообразии X, обладающий свойствами dI I будем называть дифференциальным идеалом. Таким образом, для любых w = w k I, w k Lk ( X ) и n L* ( X ) будем иметь w k I, w n I, dw I. Если dS - множество форм dw для w S, то дифференциальный идеал, порожденный S, - это {S, dS}. Тогда для 1 форм распределения Картана I = {S, dS} = {, dq } называется пфаффовым q дифференциальным идеалом. В работе получена на многообразии X пфаффова система ( J, w ), интегральные многообразия которой находятся в естественном взаимно-однозначном соответствии с интегральными много образиями системы ( I, w ), удовлетворяющими уравнениям Эйлера Лагранжа () Lu x d d Lu = + Lu 1 du yy dy y dx 1 + 2 du x для функционала F = fj, где j L (X ).

n СПИ-МА- Егоров С.И., Ломтадзе С.Р.

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ КОРРЕКЦИИ ОШИБОК ПОМЕХОУСТОЙЧИВЫМИ КОДАМИ РИДА-СОЛОМОНА С ИСПОЛЬЗОВАНИЕМ ИНФОРМАЦИИ О НАДЕЖНОСТИ СИМВОЛОВ esi@cafct.kursk.ru, sergo-lomtadze@rambler.ru Известно, что помехоустойчивые коды Рида-Соломона (РС) могут гарантированно исправлять любой набор из t ошибочных символов, тогда и только тогда, когда выполняется условие 2t+1d (d – минимальное кодо вое расстояние). В [1] предложен простой декодер РС-кодов, исправляю щий во многих случаях t+1 ошибочных символов. Предложенный декодер реализует списочное декодирование, формируя список возможных векто ров ошибок {e(a)}, a=0,…l-1 (l- размер списка). Ошибки в принятом из ка нала слове исправляются только в том случае, если в списке находится только один вектор ошибок. Применение декодера [1] для декодирования многих РС-кодов, используемых на практике, дает значительное уменьше ние доли кодовых слов с неисправимыми ошибками FER (Frame Error Rate) по сравнению с традиционными декодерами РС-кодов.

Дополнительное уменьшение FER может быть получено на выходе декодера [1] путем выбора из списка векторов ошибок (для l1) наиболее вероятного. Для этого можно использовать информацию о надежности принятых из канала символов или отдельных бит. В предлагаемой работе приводятся обоснование процедуры выбора вектора ошибок из списка и результаты исследования усовершенствованного в соответствии с вышеиз ложенным декодера [1] в канале с аддитивным белым гауссовским шумом (AWGN) и модуляцией BPSK.

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

n-1 m-1 n-1 m- (r d (a ) = (r j*,k - c*(,k ) ) 2 = a * - Map(r j,k - e(jak) )) 2, (1) j j,k, j =0 k =0 j =0 k = где n- длина кодового слова в символах;

m- количество бит в симво * ле;

rj,k и r j,k - “мягкое” и “жесткое” решения относительно принятого из e (jak) - битовое представление канала бита кодового слова соответственно;

, *( a ) вектора ошибок;

a- номер вектора ошибок в списке, a=0,…,l-1;

c j,k - ка нальное представление исправленного кодового слова;

Map(x) – функция, отображающая логическое значение бита в канальное представление:

Map(x)= -1, если x=1, Map(x)= +1, если x=0.

Из (1) можно получить:

СПИ-МА- n-1 m-1 n-1 m - (4 r (a ) ( r j*,k 2 * e (jak) ), = - 1) + d j,k, j =0 k =0 j =0 k = Первая сумма не зависит от вектора ошибок и является постоянной для принятого из канала слова. Вторую сумму можно представить в сле дующем виде n ( a ) -1 m- (r (a ) * yi(,a ) ) Dd =4 k log( X i( a ),k i =0 k = (a) где н(a) – число ненулевых ошибочных символов вектора ошибок e(a);

X i локаторы этих ошибочных символов;

yi(,a ) - значения бит ошибочных сим k (a ) волов. Dd находится как учетверенная сумма абсолютных значений ка нальных бит принятого слова, в которых исправляются ошибки.

Для нахождения минимального расстояния между принятым и ис правленным кодовым словом достаточно найти минимальное значение Dd (a ) для всех a=0…l-1, и номер z вектора ошибок в списке определяется как n ( a ) -1 m- (r * yi(,a ) )).

z = arg min ( k log( X i( a ),k i =0 k = a =o,...,l - Результаты исследования усовершенствованного декодера приведе ны на графике. Исследовались РС-коды с d=13, определенные над конеч ным полем GF(28). Модель канала – BPSK, AWGN, Eb/No=7 db. На графике з обозначает коэффициент повышения достоверности, равный отношению FER на выходе стандартного декодера к FER на выходе декодера, исправ ляющего t+1 ошибку. Кривая 1 соответствует случаю исправления t+ ошибок без использования мягких решений, 2 – с использованием мягких решений.

Использование мягких решений для выбора векторов ошибок из списка позволяет расширить область эффективного применения алгоритма из [1] относительно n примерно в два раза.

СПИ-МА- Список использованных источников 1. Egorov S., Markarian G., Pickavance K. A Modified Blahut Algorithm for Decoding Reed-Solomon Codes Beyond Half the Minimum Distance // IEEE Trans. on Commun., vol. 52, no. 12, December. 2004, pp. 2052-2056.

Жизняков А.Л.

НЕКОТОРЫЕ ВОПРОСЫ ВЫЧИСЛЕНИЯ ДВУМЕРНОГО НЕПРЕРЫВНОГО ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ lvovich@newmail.ru Вейвлет-преобразование в настоящее время находит широкое при менение в обработке цифровых изображений. При этом, как правило, при реализации алгоритмов используется так называемое «быстрое» дискрет ное вейвлет-преобразование, основанное на алгоритме Малла [1]. Отсутст вие избыточности и возможность обратного преобразования позволяет ус пешно применять этот подход в алгоритмах фильтрации (восстановления) и сжатия изображений. Использование масштабов, кратных двум позволя ет строить эффективные в вычислительном отношении алгоритмы.

Однако в обработке изображений можно выделить ряд задач, реше ние которых основано на использовании избыточности, а наличие обрат ного преобразования не обязательно. К ним относятся, прежде всего, зада чи связанные с выделением признаков, отслеживанием особенностей, сег ментацией и т.п. Можно показать также, что в этих случаях, более эффек тивным может оказаться изменение масштаба изображения не кратное [2]. Кроме того, быстрое вейвлет - преобразование не инвариантно сдвигу сигнала, что существенно ограничивает возможности преобразования в за дачах распознавания, классификации, поиска по шаблону, сегментации и др.

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

Целью работы является анализ возможностей применения непре рывного вейвлет – преобразования в алгоритмах обработки изображений.

Одной из проблем, возникающих при реализации алгоритмов вейв лет - обработки, является то, что в большинстве приложений используется вейвлет - преобразование с масштабным множителем равным 2. Однако можно показать [3], что в рамках многомасштабного анализа этот множи тель должен быть рациональным числом и никаких других требований не налагается. Поэтому можно построить схемы с другими целыми или дроб ными множителями. Их использование может привести к лучшей локали зации по частоте. Для вейвлетов с масштабным множителем 2 их Фурье – СПИ-МА- образ сосредоточен в основном в пределах одной октавы между p и p/2, тогда как вейвлет – базисы с дробными множителями могут иметь ширину полосы пропускания, более узкую, чем октава.

Непрерывным вейвлет преобразованием функции называют функ цию двух переменных W (a, b) W f, a,b = f ( x ) | y (a, b, x, a, b R, a 0, где вейвлеты y (a, b, x) являются масштабированными и сдвинутыми ко пиями порождающего вейвлета y ( x) L2 ( R), a - масштабирующий коэффи циент, b - величина сдвига [4].

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

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

Пусть s – строка изображения, длиной N. Тогда вейвлет преобразо вание этой строки запишется как x-b N - 1 j + s dx, (1) y Ws, a, b = j a a j j = причем коэффициент сжатия а может быть любым вещественным числом (кроме нуля).

Такой вариант, по сути, является численной реализацией непрерыв ного вейвлет – преобразования. При этом вопрос о его обратимости не ста вится.

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

y ( x) = ( x 2 - 1) exp[- x 2 / 2] (2) Можно ввести несколько элементарных подходов к непрерывному вейвлет-преобразованию изображений. Например, выполнить преобразо вание (1) только по строкам или столбцам изображения, либо сначала при менить преобразование к строкам, а затем к столбцам. Другой подход, предполагает, объединение каким либо способом (например, взятие моду ля) результатов преобразования строк и столбцов в одной матрице коэф СПИ-МА- фициентов. Также можно ввести в (2) сферическую симметрию и перейти к двумерному неразделимому преобразованию с вейвлетом вида:

y 2( x, y ) = ( x 2 + y 2 - 2) exp[- (x 2 + y 2 )/ 2].

При этом очевидно, что масштабирующие коэффициенты a1 и a2 в x - b1 y - b2 x - b1 y - b вейвлетах y, y и y 2 могут не совпадать. Это, a1 a 2 a1 a оказывается важным при анализе анизотропных изображений, характери стики которых зависят от выбранного направления. При этом можно вве сти вращения, вида:

y 2q ( x, y ) = y 2( x cos q - y sin q, x sin q + y cos q ) Преобразование изображения S(i,j) по строкам (столбцам) можно ус ложнить, если потребовать, чтобы изменение масштаба преобразования ai адаптивно выбиралось для каждой строки i, 1 i N (столбца j, 1 j N ). В этом случае необходимо введение какого-либо формального критерия, оп ределяющего выбор масштаба преобразования для каждой строки или столбца. Например, выбирается масштаб, на котором вейвлет коэффициен ты обладают наибольшей дисперсией, энтропией и т.д.

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

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

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

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

Рассмотрим возможность такого преобразования для одномерного сигнала. В качестве адаптивного критерия здесь может быть использован, например, порог равный отношению мощности ВЧ- составляющей, к мощ ности НЧ – составляющей СПИ-МА- s max s Ps = Am / An, (3) m = s +1 n = где Ai – i–я составляющая энергетического спектра сигнала. В качестве частоты среза при разделении НЧ и ВЧ компонент выбирается такое s, при котором порог достигает заданного значения Ps=P0.

Для вычисления значения Р может быть использован простой алго ритм. Сначала вычисляются две суммы s max - A и L(0) 2 = As max.

L(0)1 = n n = Затем для каждого следующего шага i=1.. smax-1:

L1i ) = L1i -1) - A( s max - i ), L(2i ) = L(2i -1) + A( s max -i ) ( ( и вычисляется отношение (3). Кратность изменения масштаба определяет ся отношением полос.

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

Для двумерного перегруппированного (НЧ составляющие лежат в начале координат) спектра, вычисленного на основе БПФ (рис.1), коэффи циент масштабирования Dw1 + Dw, k= Dw при условии, что E (Dw1 ) + E (Dw2) = P0.

E (Dw1 ) Рис. 1. Полосы «верхних» и «нижних» частот в спектре Список использованных источников 1. Малла С. Вэйвлеты в обработке сигналов: Пер. с англ. – М.: Мир, 2005. – 671 с.

СПИ-МА- 2. Жизняков А.Л., Вакунов Н.В. Вейвлет-преобразование в обработ ке и анализе изображений. – М.: Государственный научный центр Россий ской Федерации – ВНИИ Геосистем, 2004.-102 с.

3. Добеши И. Десять лекций по вейвлетам. – Ижевск: НИЦ "Регу лярная и хаотическая динамика", 2001. – 464 с.

4. Переберин А.В. О систематизации вейвлет преобразований // Вы числительные методы и программирование. – 2001. – Т. 2. – С. 15 – Исаев С.А.



Pages:   || 2 | 3 | 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.