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

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

Куркина Мария Викторовна

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

05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Барнаул - 2005

Работа выполнена на кафедре высшей математики Югорского государственного университета

Научный руководитель. доктор физико-математических наук,

профессор Родионов Евгений Дмитриевич

Официальные оппоненты доктор физико-математических наук,

•• профессор Алгазин Геннадий Иванович,

доктор физико-математических наук, доцент Никоноров Юрий Геннадьевич.

Ведущая организация: Институт математики СО РАН им С Л Соболева

Защита состоится 5 июля 2005 года в 10.00 часов на заседании диссертационного совета Д 212.005 04 в Алтайском государственном университете по адресу 656049, г Барнаул, пр Ленина, 61, конференц-зал.

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

Автореферат разослан 3 июня 2005 г.

Ученый секретарь

диссертационного совета д ф -м н , профессор

С.А Безносюк

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

Актуальность темы. Задачи оптимизации и классификации играют в приложениях важную роль, и со временем актульность этих задач только возрастает Метод динамического программирования - широко известный и мощный математический метод оптимизации, применяемый в самых разных областях современной прикладной математики. Впервые данный термин был введен в конце 50-х годов американским математиком Р. Беллманом в его известных монографиях [1,2], в этих работах на основе рассмотрения функциональных уравнений были заложены математические основы ДП. В работах Р.Арис, Е.С.Вентцель, Г.Вагнер, Н.М.Оскорбин [3,4,5,6] даны многочисленные примеры применения ДП,

При вычислительной реализации метода динамического программирования возникают трудности. Эти трудности Р. Беллман назвал "проклятием размерности" Они связаны с необходимостью хранения в процессе счета большого числа табулированных функций многих переменных. Одним из способов преодоления этих трудностей является выделение классов задач, которые допускают построение аналитических решений, или хотя бы аналитическое исследование этих решений Примером такого подхода служит работа Sutherland, W.R.S ; Wolkowicz, Н.; Zeidan, V. [7] В диссертации выделен класс задач, который можно условно назвать линейной моделью распределения ресурсов, и проведено аналитическое исследование этих задач.

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

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

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

Основные задачи работы включают.

1 Установление связи между многомерной линейной моделью распределения ресурсов и дискретной одномерной динамической системой;

2 Изучение многомерной линейной модели распределения ресурсов с ограничениями и соответствующей динамической системы;

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

4. Построение интегральной линейной модели распределения ресурсов с ограничениями;

5 Оптимизацию транзитивного замыкания нечеткого отношения эквивалентности.

Основные положения, выносимые на защиту

- многомерная линейная модель распределения ресурсов и соответствующая ей дискретная динамическая система;

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

- интегральная линейная модель распределения ресурсов с ограничениями

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

на основе понятия минимального остова графа Указаны новые алгоритмы построения транзитивного замыкания на основе евклидовой метрики.

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

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

Апробация работы. Результаты диссертации докладывались на третьей краевой конференции математическое образование на Алтае (МОНА-2002). на международной конференция-школе по геометрии и анализу посвященной памяти А.Д.Александрова (Новосибирск 2002 г.), 34-й региональной молодежной конференции (Екатеринбург 2003 г.), шестой краевой конференции по математике (МАК-2003), международной конференция-школе по геометрии и анализу посвященной 75-летию Ю Г Решетняка, (Новосибирск 2004г) Материалы диссертации обсуждались на совместном семинаре кафедр математического анализа Алтайского госуниверситета и кафедры геометрии Барнаульского государственного педагогического университета (20012004 гг.). на семинаре кафедры высшей математики Югорского государственного университета (2005 г.).

Публикации Основные результаты диссертации опубликованы в 12 работах.

Структура и объем диссертации. Работа состоит из введения, четырех глав, приложения и списка литературы, включающего 51 наименований Общий объем диссертации составляет 148 страниц, включая 33 рисунка и таблицы.

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

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

Первая глава диссертации посвящена элементарному введению в теорию динамического программирования, формулировке задачи динамического распределения ресурсов в наиболее простой экономической интерпретации [4]

Планируется деятельность т предприятий в течение п лет. Начальные средства составляют у\. Средства X, вложенные в г-ое предприятие, приносят к концу года доход /г(Х) и возвращаются в размере <рг(Х) < X, г — 1, 2, . ,т По истечении года все оставшиеся средства заново перераспределяются между предприятиями, новых средств не поступает и доход в производство не вкладывается Требуется найти оптимальный способ распределения имеющихся средств

Процесс распределения ресурсов рассматривается как тг-шаговый, в котором номер шага соответствует номеру года Управляемая система в данном случае это т предприятий с вложенными в них средствами Система характеризуется (р — 1) одним параметром состояния уи £ = 1,2...., п -количеством средств, которые следует перераспределить в начале ¿-го года. Переменных управления на каждом шаге т (з = т), хц - количество средств, выделенных соответственно г-ому предприятию, г = 1,.. , га Так как средства ежегодно перераспределяются полностью, то

Хц + 2(2 + •■• + хЬт - уг-Пронормировав переменные управления = ^ получим, что

7«1 + 7(2 + ... + 7Ьт = 1, Ъг > 0.

То есть точка 74 = {7^} € Д™-1 принадлежит (ш - 1) - симплексу Ат_1 Показатель эффективности данной задачи - это доход за один год

/1(2п) + /2(^2) + ■•• + /т(я«т)

Крихерий оптимальности - доход полученный от т предприятий в течении

п лет равен

п

Z = ih(Xtl) + /2(^2) + ... + fm{xtm)]. t= 1

Уравнение состояния выражает остаток средств yt после t-го шага и имеет вид

УМ = ^l(Zil) + <¿>2(^2) + ••• + 4>m{xtm)-Пусть Z*(Y,t) - условный оптимальный доход, полученный от распределения средств Y между те предприятиями в период с i-ro года до последнего п-го Рекуррентные функциональные уравнения Беллмана для этих функций имеют вид:

z*{yn,n)= max [f\{xni) + ... + fm{xnm)} z„l+ +xnm=y„

- последнее уравнение Беллмана (при t = га), и

Z'{yt,t)= max [f1(xn) +... +fm(xtm) +Z*(yM,t+l)]

®tl+ +®(m=V<

- уравнения Беллмана при t = n - 1,..., 1, здесь yt+1 = щ{хп) + ¥>2(2^2) + ■ ■ + <£m{xtm) Как видно из ¿тих уравнений, даже для функций /,, tpt простого вида, рассчитывать на получение явного решения затруднительно Большинство известных явных решений для двумерной задачи приведено в [1,2,3,4]

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

Теорема (Теорема 1.2.1). Пусть функции ft(X) и <ft(X) (функции дохода и возврата средств соответственно), линейные ft(X) = htX, рг(Х) = ггХ; h, > 0, г, > 0, г — 1. 2,. ., т. Тогда функции условного оптимального

дохода Z*(y! к) также будут линейные Z*(y. к) = Нку, при этом коэффициенты Нк находятся рекуррентно:

Нп = А(0), Нп-1 = А(Я„),

#1 = А (Я2),

где функция Х(х) = тах [Л, + туг] - верхняя огибающая линейных функ-

1 <г<т

ций.

Оптимальному решению соответствует дискретная динамическая одномерная система, определяемая отображением

х* = А(а;))

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

Рис 1 Построение последовательности

Определение. Коэффициентом эффективности г-ого предприятия назовем решение уравнения х = Кг + г,х , т. е. число

Справедливо утверждение Теорема (Теорема 1.2.3). Для многомерной линейной модели распреде-

ления ресурсов справедливы утверждения;

max К < Н\ < max Pt

г г

lim Н\ — maxPj-

П-+00 t

Далее условия Л, > 0 и гг > 0 в теореме 1.2 1 последовательно ослабляются в серии теорем

Теорема (Теорема 1.2.4). Пусть функции /г(Х) и ¡р,(Х) (функции дохода и возврата средств соответственно), линейные /,(Х) = НгХ, <рг(Х) — г,Х; гг > 0, г = 1,2,. ,,т. Тогда функции условного оптимального дохода Е*{у,к) будут положительно однородными 1-ого порядка 2*{Ху,к) = к), при А > 0, то есть

где функции А+(х) = max [h,+rtx], А (х) — min [ht+rtx] - соответ-

1 <i<m 1 <1<т

ственно верхняя и нижняя огибающая линейных функций.

Теорема (Теорема 1.2.5). Пусть функции /¡(X) и<рг(Х) (функции дохода и возврата средств соответственно), линейные ft(X) — h,X, <pt(X) = ггХ; maxj{r,} > 0 > т1П,{гг}. Тогда функции условного оптимального дохода Z*(y, к) будут положительно однородными 1-ого порядка Z*(Xy, к) = \Z*(y, к), при А > О, то есть

н: = \+( о), ни = л+(яп+),

н- = л-(0),

Н-_Х = Л-(ЯП)

Я+ = Л+(Я2+),

ЯГ = \-{Щ)

Hty, У>0, Щу, у< 0.

при этом коэффициенты , Нк находятся рекуррентно;

= 0), Я- = А-(0),

Яп+_! = max {А+(ЯП+), А+(ЯП")} , = min {А-(Я+), А"(Я")} ,

Я+ = шаХ{А+(Я2+), А+(Я2-)} , ЯГ = шт{А"(Я2+),А-(Я2-)} , где функции А+(ж) = max [Л, + г,я], А" (г) = min [/i,+г,х] - соответ-

1 <г<т 1<г<т

ственно верхняя и нижняя огибающая линейных функций.

Оптимальному решению соотвеютвует дискретная динамическая двумерная система, определяемая отображением

х* — max {А+(х), А+(у)}; у* = min {А-(я), А~ (у)}, траектория которой с начальной точкой xq = 0, уо = 0 позволяет полностью исследовать оптимальные решения на любом временном отрезке

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

Планируется деятельность т предприятий в течение п лет Начальные средства составляют £о Средства X, вложенные в г-ое предприятие, приносят к концу года доход f,(X) и возвращаются в размере f,{X) < X, г = 1,2, ...,т По истечении года все оставшиеся средства заново перераспределяются поровну между определенным, фиксированным процентом а% предприятий (например а = 25%) которые имеет смысл финансово поддержать и привлечь к данному проекту Новых средств не поступает, доход в производство не вкладывается.

Требуется найти оптимальный способ отбора тех предприятий между которыми будет происходить распределение имеющихся средств Процесс выбора рассматриваем как n-шаговый в котором номер шага соответствует номеру года

Теорема (Теорема 1.2.6). Пусть функции /¡(X) и срг(Х), линейные /г(Х) = НгХ, <рх{Х) = ггХ, /г, > 0, 0 < г, < 1, г = 1,2,... ,т. Тогда функции условного оптимального дохода (у, к) также будут линейные Z*{y, к) = Н^у, при этом коэффициенты Нк находятся рекуррентно;

Нп = Аа(0), Яп_ 1 = Ха(Нп),

Нг = А а(Н2), функция Аа определена формулой

Ха(х) = Мах" [Л, + ггх],

1<2<т

здесь оператор Мах° определена формулой:

где h4 > hl2 > h4> ... > hlm, p = [ma] - целая часть та.

Величину Маха {/гг} назовем верхним a-средним для числового семейства 1

{h^, а функцию Аа - верхней a-средней семейства линейных функций

Определение. Групповым коэффициентом эффективности набора т из р предприятий, где т = {i\.i2, ■ ,гр}, назовем решение уравнения х = - Yfk=1 (^u + гчх)> m- е■ число

- Л1=1

Теорема (Теорема 1.2.8). Для многомерной линейной модели распределения ресурсов с ограничением справедливы утверждения:

Мах" Л, < Hi < тахРг,

г т

lim Hi — max Рт

П—У 00 Т

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

Теорема (Теорема 1.3.1). Пусть "ресурс" X — {я7} Е RP состоит из р компонент, функции "дохода" ft(X) — h4x3 - линейные, отображения ¡p, : RP —У RP - линейные, ц>г(Х) = {r^z-'}^!]', здесь по повторяющемуся индексу (вверху и внизу) вычисляется сумма, htJ > 0, г* > 0, г = 1.2,..., т; ],s =■ 1,2, Тогда функции условного оптимального дохода Z*(Y,k)

также будут линейными функционалами Z*(Y,k) = Zk3y3, при этом коэффициенты Zk — {¿к]} G Rp находятся рекуррентно:

Zn = Л(0), Zn_i = Л(Zn), ■ • ■ Zi = A(Z2),

где отображение Л : Rp —¥ RP имеет компоненты AS(X), определяемые формулами:

Х,(Х) = шах hu + г3 х3

l<t<m L

- выпуклые вниз функции (верхние огибающие линейных функций).

Замечание. Нахождение плана оптимального распределения ресурсов сводится к вычислению траектории {Zk} динамической системы, определяемой отображением А : RP+ —> RP+ с начальной точкой Zq = 0 е начале координат.

Определение. Вектором ("чистым") эффективности i-ого предприятия назовем решение уравнения xs = his + r3tsx3 , т. е. вектор

Рг = {Е - <pt)~%.

Пусть /3 ■ {1,2.... ,р} —> {1, 2,... ,т} произвольное отображение конечных множеств. Сопоставим (3 решение P¡¡ системы уравнений xs = h^s)s+ r>0(s)sX3> т в- вектоР

Рд = (Е-

где ipg - "смесь" линейных операторов цзх, г = 1,2, ...,т, те. каждая строка матрицы оператора есть строка с тем же номеров одной из

матриц <рг, г = 1.2,... .т. Вектор Рр назовем вектором эффективности ß "смеси" предприятий. Всего таких векторов будетрт. Если отображение ß постоянное, то получаем "чистый" вектор эффективности.

Введем в пространстве RP норму по формуле

HxjU = max {|х,|}. ]=1,- ,Р

Соответствующая норма линейного оператора ¡р : Е? —У Rp, <р(х) — {r{xj} определяемая формулой

IMI = max ||<р(®)||оо,

iWloo<l

будет равна

IMI = max < > •

,=1' р IU J

Теорема (Теорема 1.3.3). Пусть нормы линейных операторов {¡р,}^ строго меньше 1, тогда для многомерной линейной модели распределения ресурсов справедливы утверждения:

max ht < Z\,

г

lim Z\ = max Pg > max Рг,

П-»00 ß I

где неравенство выполняется покомпонентно.

Вторая глава - "Бесконечномерная линейная модель распределения ресурсов с ограничениями" посвящена исследованию математической модели бесконечномерной (интегральной) задачи распределения ресурсов.

В случае очень большего числа линейных предприятий (порядка 10000) естественно перейти от конечного набора коэффициентов /г,, гг к вероятностному распределению пар чисел {h, г} Будем считать, что задана функция совместной плотности распределения этих величин p(h, г) обладающая свойствами.

1. p(h, г) > 0 при h > 0 и г > 0, равная нулю в противном случае;

2. функция p(h, г) > 0 непрерывна при h > 0 и г > 0;

3 выполняется равенство

/•+00 г+оо

/ / р(Н, т)йрАН — 1; ¿о Уо

4 конечны первые моменты

/• + 00 /»+00 Р+ОО /* + 00

/ / /гр(Л, г)с1р(1Ь, < +оо, / / гр(к,г)с1рс1к < + оо.

Л Уо Jo Уо

Введем обозначение М = [0, +оо) х [0, +оо) - множество (фазовое пространство) всех параметров предприятий Доля предприятий, параметры которых лежат в прямоугольнике ДМ = [Л. /г + А/г] х [г, г + Дг], равна рН+АИ лг+Дг

J у г)дрдИ ~ р(/г, г)ДрД/г.

Рассмотрим следующую математическую модель деятельности М предприятий в течение п лет Начальные средства составляют £о Средства X, вложенные в множество йМ предприятий, приносят к концу года доход /(с?М, X) = X • Нр(к, т)йрдИ и возвращаются в размере ф(с1М, X) = X ■ гр(Н, т)йрйЪ. По истечении года все оставшиеся средства заново перераспределяются равномерно на каждый раз определяемом множестве Мг предприятий, доля которых составляет фиксированным процент а% (например а = 25%),

/ р{к,г)<1р<1}1 — а. Ум,

Это те предприятия которые привлекаются к данному проекту на следующий год Новых средств не поступает, доход в производство не вкладывается Требуется найти оптимальный способ отбора множеств {М,}, г = 1,...,п тех предприятий, между которыми будет происходить распределение имеющихся средств. Процесс выбора рассматриваем как п-шаговый, в котором номер шага соответствует номеру года Справедлива

Теорема (Теорема 2.1.1). В условиях задачи функции условного оптимального дохода Е*(у,к) будут линейные 2*{у,к) = Н^у, при этом коэффициенты Я/с находятся рекуррентно:

Нп = Аа(0), Яп_г = Ха(Нп), ■ ■ ■ Нх = А„(Я2),

функция Ха определена формулой

Аа(х) = sup < / [h + rx]p(h, r)dhdr : / p(h,r)dhdr — a > , AcM {J A J A J

для каждого x множество А С M на котором достигается супремум

представляет собой область вида

Мх ~ {т = (/г, г) € М : /г + хг > с} ,

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

p(h, r)dpdh = а.

мх

Рис. 2:

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

/ ¡7?, + rx)p{h,r)dhdr = (/г* -Ь г*х) / р(/г, r)dhdr, и а ЗА

где точка <?(/**, г*) - центр тяжести множества А с данной плотностью массы р(к,г). Отсюда следует,, что

Аа(х) — [к + гж]р(/г, r)dhdr = (/г* + г*х)а, ./ мГ

где точка дх(Ь-*,г*) - центр тяжести множества Мг с данной плотностью массы р(/г, г).

Определение. Положим

Мх = {ш = (/г, г) Е М : Л + хг < с} - М \ Мх.

Выпуклое множество определенное равенством

X

назовем запретным уровня а.

При любом выборе выборе начальных средств х и любом количестве этапов перераспределения средств множество Ра не участвует в этом перераспределении

Определение. Выпуклое множество определенное равенством

назовем общим уровня а.

При любом выборе выборе начальных средств х и любом количестве этапов перераспределения средств множество (?а участвует в каждом перераспределении

Пусть £ = £(Л, г) - произвольная функция, и А<х — Е?+ - некоторое разбиение первого квадранта плоскости на два множества, введем обозначения

(частный случай общего дисперсионного равенства). Возьмем в качестве множеств А\ = Мх и А^ = а в качестве функции £ = Н + хг, тогда

оа = [)мх,

X

Тогда справедливо равенство

= № А + ^о2 + - + /¿2оё - б)2,

имеем

/il = a, fi2 = l-a,

Ç = h + xr, D[Ç] = D[h + xr],

6 = (Л* + xr*) = i^x), £2 = (Л" + ®r**) = h + xf~*°(*)i a I — a

где точки go(/i. r*) q*x*{h**, r**) - центры тяжести множеств R\, Mx,

Nx при данной плотности p{h. г)

Теорема (Теорема 2.1.2). Пусть конечны все центральные вторые моменты

Du — (h - h)%p{h, r)dhdr < oo, Jr\

D\2 = / (h — h){r — f)p{h,r)dhdr < oc, JR\

D22— I (r - f)2p(h,r)dhdr < 00, JR\

тогда справедливо равенство

1 , \a(hxr) — \a{x)\2 Du + 2xD\2 + x D22 = 0lD\ + l - a)D2 + ^-j-1-

a(l — a)

Следствие. В условиях теоремы справедливо неравенство

[a(h + xf) - \а{х))2 < a(l - a){Dn + 2xD12 + x2D22).

Теорема (Теорема 2.1.3). Пусть конечны первые моменты, тогда справедливо неравенство

Ха(х) < —(h + xf). а

В главе 2, также подробно изучен случай независимого равномерного распределения {h, г} и равномерного распределения {h, г} в круге

В третьей главе - "Нечеткая кластеризация" исследуется задача оптимизации разбиения данных произвольного типа на кластеры (те разбиение множества экспериментальных данных на подмножества элементов со сходными признаками или свойствами) Такие задачи возникают при обработке и анализе на ЭВМ больших массивов различного типа информации

При практическом разбиении на кластеры в теории нечеткого моделирования [8,9 10] используют понятие нечеткого множества и нечеткого отношения эквиватентности Нечеткое отношение эквивалентности R (нечеткое подмножество X у, X) определяется своей функцией принадлежности ¡jtR ■ X х X —[0,1] обладающей свойствами.

• Va € X : цк{а,а) — 1 - свойство рефлексивности,

• Va, b € X ßR{a, b) = pR(b, а) - свойство симметричности,

• Va, 6, с min {/хл(а, b),pR(b, с)} < fiR(a, с) - свойство транзитивности.

Нечеткое отношение назовем нечетким толерантным отношением, если выполнены лишь свойства рефлексивности и симметричности.

Определение. Улътраметрикой на множестве X называют функцию р(а, Ь) удовлетворяющую аксиомам:

• Va £ X : р(а, а) = 0,

• Va, b е X ■ р(а,Ь) — р(Ь, а),

• Va, 6, с € X : р(а,с) < таx{p(a,b), р(Ь,с)}.

Пару (X, р) называют ультраметрическим пространством.

Функция p.R(a, b) определяет нечеткое отношение эквивалентности на множестве X в том и только в том случае когда функция pR(a, Ъ) = 1 — pR{a, b) - ультраметрика на X. Будем называть эту ультраметрику двойственной к нечеткому отношению эквивалентности.

Любое свойство нечеткого отношения эквивалентности имеет аналог в терминах ультраметрики, верно и обратное. Ультраметрические пространства обладают рядом замечательных свойств, например, они изометрично вкладываются в сферу гильбертового пространства (см. В.Н.Берестовский [12]), имеются многочисленные приложения этого понятия, как в самой математике (р-адический анализ), так и в других естественных науках (в биологии [16])

Нас будет интересовать случай нечеткого отношения эквивалентности Я (или двойственной ультраметрики) на конечном множестве X, содержащем N точек аг, г = 1,2, . ,N Будем отождествлять точки с их номерами, те а, = г. Введем обозначения'

Квадратные матрицы Я^, Яр размера N х N обладают свойствами

О < < 1, 0 < < 1, (1)

Ми = 1, Рп = о, (2)

Щ = Щ ~ (з)

Я^&Я^ = ЯР°ЯР = Яр, (4)

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

Определение. Мах-тгп композицией (соответственно Мт-тах и Мгп-р1т композицией) матриц Я = ||г,/ь||, 5 = Цвд^Ц размеров соответственно п х р и р х т называется матрица Т = Яо5 (соответственно Т = Йб5 и Т = Я 0 8) размера п х т определяемая соответственно формулами:

- тах£=1, 1Р{шт(г!ь в*,)}, г = 1,..., п, 2 = 1.. ,,т. = ттА=1, ,р{тах(г,ь5^)}, г = 1,. . ,7 = 1, .т, = ттА=1, Р {>",* + з^}, г = 1,..., та, ] = 1,... ,т.

Определение. Если выполнены лишь свойства (1) - (3), то матрицы Я^ и Яр будем называть матрицами сходства (соответсвенно несходства) для данного нечеткого толерантного отношения.

Определение. Пусть К = ультраметрическая матрица, т.е удовлетворяет условиям (1)-(4). Стандартная или каноническая форма матриц такого типа определяется рекуррентно:

Яц 11-12

К-21 К-22

где Яц, 11,22 квадратные матрицы меньшей размерности в стандартной форме, а у матриц = К^х все элементы имеет одинаковую величину равную В = тахйу-. где V - диаметр улътраметрического пространства.

Теорема (Теорема 3.1.2). Пусть матрица К удовлетворяет условиям (1)-(4), тогда ее элементы принимают не более чем Лг — 1 различных положительных значений, и путем перенумерации точек щ € X матрицу можно привести к стандартной форме рис. 3.

123456736

Рис. 3: Стандартная форма ультраматрицы

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

Пусть К нечеткое толерантное отношение определенное на множестве X и Р = {Ль/¿2,.. •, Д/г} последовательность точек в X такая, что — г и Ьк = ]■ Будем называть Р путем соединяющим точки I,] € X.

Определение. Шагом, сходства (соответственно шагом несходства) вдоль пути Р называются величины:

Определение. Разделяющим сходством двух различных точек г, множествах (соответсвенно разделяющим несходством) называются вели-

чины:

вапл(г^) = шэрс8П(Р),

эас1л(г, ]) — 1Шпв<1(Р),

где Р произвольный путь соединяющий г и ]. Если 1 = 3, то запй(г, ]) = 1, эас!л(г, = 0.

Теорема (Теорема 3.2.1). Для произвольного нечеткого толерантного отношения Н функции запк(г,7) и Бас1"гг(г, 7) на множестве X х X определяют нечеткое отношение эквивалентности и двойственную ультраметрику.

Определение. Остовом графа б — (V, Е) называется его подграф С = (у.Е') с тем же множеством вершин, являющийся деревом. Наименьшим остовом (ББТ) графа (? = {У,Е) называют остов, у которого сумма весов ребер наименьшая.

Нечеткому толерантному отношению Я на множестве X сопоставим полный неориентированный граф б = (V, Е), где V = X, Е - множество всех неупорядоченных пар точек из X, с весовой функцией ребра {аг, а3} равной величине несходства точек = рк{аг, а}).

Теорема (Теорема 3.2.2). Обозначим через С = (Х,Е') наименьший остов графа С = (X, Е), тогда справедливы равенства.

запй(г^')=зп С,(Р'),

где Р' единственный путь (без самоналожения) лежащий в остове С = (X, Е') и соединяющий вершины г и ]

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

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

В современной теории цифровой обработки изображений уделяется большое внимание разработкам методов выделения контуров [13,14]. В последний годы методы нечеткой сегментации изображения интенсивно разрабатываются [18,19]

Определим понятие локальной нечеткой близости двух линейных элементов А(х1,у\, <¿>1), В(х2, уг\ <£>2)1 где (х„у,)- координаты точек, <р, направление перпендикулярное полю градиенту в данных точках, по формуле

где В) истинное, если каждая из точек по отношению к другой лежит между ветвями гиперболы с вертикальной полуосью го и горизонтальной полусью го/. Таким образом / - тангенс половины угла раствора гиперболы (угла между асимптотами) На рисунке 4 показаны две таких линейных элементы и соответствующие им гиперболы Параметр го характеризует толщину линии, параметр / константу Липшицевости линии. Величина ¿{А, В) - расстояние между точками, параметр п характеризует скорость "затухания" данного локального нечеткого отношения в зависимости от расстояния между точками

О

если Я/(А, В) = О если Я1{А,В) - 1

Рис 4 Локальпое нечеткое отношение близоми двух шлейных элементов

Нечеткое отношение эквивалентности <2^ полученное транзитивным замыканием данного локального отношения эквивалентности можно использовать для более наглядной визуализации данных

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

В приложении даны программные модули в системе МаЫаЬ использованные в четвертой главе.

Список работ, опубликованных по теме диссертации:

1 Карымов В Р , Славская М В Многомерная линейная модель распределения ресурсов// Математическое образование на Алтае. Труды региональной научно-методической конференции. Барнаул. Изд-во АлГТУ, 2001 С 33-36

2 Славская М.В Многомерная линейная модель распределения ресурсов с ограничениями// Вестник БГПУ, 2001, .№1 С 41-44.

3 Славская М В Бесконечномерный аналог многомерной линейной модели

j

Рис 5 Нечеткое отношение для точек направления деталей 2 и 3 уровня величины Koog

распределения ресурсов с ограничениями// Тр рубцовского иидустр инст Рубцовск, 2001 Вып 9 С 8

4 Славская М В Линейная модель распределения ресурсов с равномерным распределением параметров//' Вестник БГПУ 2002 №2. С. 49-53

5 Славская М.В. Бесконечномерная линейная задача распределения ресурсов с ограничениями// МАК-2002 Тезисы докладов краевой конференции Барнаул, 2002. С. 68.

6 Славская М В Геометрический подход к решению одной задачи динамического программирования// Международная конференция-школа по геометрии и анализу Тезисы докладов Новосибирск, 2002 С 70

7 Славская М.В Динамическая линейная модель ресурсов с равномерным распределением параметров// Проблемы теоретической и прикладной математики Труды 34-й региональной молодежной конференции. Екатеринбург: УрО РАН, 2003. С. 6.

8 Славская М.В. Непрерывная модель распределения ресурсов// Вестник БГПУ 2003 т. С. 32-37.

9. Куркина М В. Многомерная линейная модель распределения ресурсов с непрерывным временем// Конференция MOHO' Тезисы докладов Барнаул, 2004. С 34-36.

10 Куркина М.В. Выпуклая динамическая система связанная с линейной задачей распределения ресурсов// Международная школа-конференция по анализу и геометрии: Тезисы докладов. Новосибирск, 2004. С. 161

11 Куркина М В Динамическая система связанная с линейной задачей распределения ресурсов//Вестник БГПУ 2004, №4 С 25-29.

12 Куркина М В Динамическая система связанная с линейной задачей распределения ресурсов// Доклады Академии Наук, 2005 Т.401, >3 С 3

Литература

[1] Беллман Р Динамическое программирование. М Изд-во ИЛ, 1960.

[2] Беллман Р, Дрейфус О. Прикладные задачи динамического программирования. М.. Наука, 1965. 457 с.

[3] Арис Р Дискретное динамическое программирование М/ Мир, 1969. 168 с.

[4] Вентпель Е С Исследование операций М : Наука, 1972

[5] Вагнер Г. Основы исследования операций М.: Мир, 1973

[6] Оскорбин Н М., Суханов В А Исследование операций и теория игр в элементарном изложении Барнаул: Изд-во АГУ, 1987. 62 с.

[7] Sutherland, W R S . Wolkowicz, Н ; Zeidan, V An explicit linear solution for the quadratic dynamic programming problem. J. Optimization Theory Appl 58, No.2, 319-330 (1988).

[8] Zadeh L.A Fuzzy sets - Information and Control, vol. 8, 1965, pp 338-353

[9] Александр Леоненков Нечеткое моделирование в среде MATLAB и fuzzyTECH Санкт-Петербург', БХВ-Петербург, 2003.

[10] Yu LI, Jonathan LI Haibin DONG, Xiangqian GAO A fuzzy relation based algorithm for segmenting color aerial images of urban environment

[11] Hazewinkel M Classification m Mathematics, Discrete Metric Spaces, and Approximation by Trees// Report AM-R9505, CWI Amsterdam. The Netherlands

¡12] Berestovskn V N. Ultrametric spaces Proceedings on analysis and geometry, international conference in honor of the 70th birthday of Professor Yu. G. Reshetnyak, Novosibirsk, Russia, August 30-September 3,1999. Novosibirsk: Izdatelstvo Instituta Matematiki Im. S L. Soboleva SO RAN. 47-72 (2000)

[13] Цифровая обработка изображений в информационных системах Учебник. Новосибирск: НГТУ, 2002.

[14] Введение в контурный анализ. Приложение к обработке изображений и сигналов/ Под ред. Я.А. Фурмана. -М. Наука, 2003.

[15] Добеши И. Десять лекций по вейвлетам -Москва-Ижевск., РХД, 2001.

[16] Podani J., Csontos P. and Tam6s J. Additive trees in the analysis of community data Community ecology 1. xxx-xxx, Akadftmiai Kiady, Budapest (2000).

[17] Nicholas Jardine, Robin Sibson, Mathematical taxonomy, Wiley, 1971.

[18] Bruno M. Carvalho, С Joe Gau, Gabor T. Herman and T. Yung Kong. Algorithms for Fuzzy Segmentation// Pattern Analysis & Applications (1999)2:73-81.

[19] Herman GT Geometry of Digital Spaces Boston, MA Birkhauser, 1998

Подписано в печать 30.05 2005 Формат 60 х 80/16 Бумага офсетная Печать офсетная. Уел печ л 1,8 Тираж 100 экз Заказ №

Типография экономического факультета Алтайского государственного университета: 656049, Барнаул, пр Социалистический, 68

»12479

РНБ Русский фонд

2006-4 5590

Введение

1 Многомерная линейная модель динамического распределения ресурсов

1.1 Принцип Беллмана динамического программирования

1.1.1 Многошаговый процесс управления

1.1.2 Задача оптимального управления

1.1.3 Элементарный подход.

1.1.4 Метод динамического программирования.

1.1.5 Задача распределения ресурсов.

1.2 Многомерная линейная модель распределения ресурсов.

1.2.1 Линейная модель распределения ресурсов с положительными коэффициентами.

1.2.2 Линейная модель распределения ресурсов с произвольными коэффициентами.

1.2.3 Линейная модель с ограничениями.

1.3 Обобщенная многомерная линейная модель распределения ресурсов

2 Бесконечномерная линейная модель распределения ресурсов с ограничениями

2.1 Бесконечномерная линейная модель распределения.

2.2 Линейная модель распределения ресурсов с равномерным и независимым распределением параметров.

2.3 Линейная модель распределения ресурсов с равномерным распределением параметров в круге.•.

2.4 Многомерная линейная модель распределения ресурсов с непрерывным временем.

3 Нечеткая кластеризация

3.1 Нечеткое отношение эквивалентности, ультраметрика. Стандартная форма ультраметрической матрицы.

3.2 Транзитивное замыкание нечеткого толерантного отношения

3.3 Иерархическое кластеробразование.

3.4 Аддитивные метрики. Конструкция Бунемана.

3.5 Соотношение между аддитивной метрикой и ультраметрикой

3.6 Евклидово расстояние между нечеткими толерантными отношениями.

3.7 Липшицево расстояние между нечеткими толерантными отношениями.

4 Выделение контурных линий изображения методами нечет-4 кой кластеризации

4.1 Диагональные детали (второго порядка).

4.2 Детали первого порядка.

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

4.2.2 Другие локальные нечеткие отношения для аномальных точек.

Задачи оптимизации и классификации играют в приложениях важную роль и со временем актульность этих задач только возрастает. Метод динамического программирования - широко известный и мощный математический метод оптимизации применяемый в самых разных областях современной прикладной математики. Впервые данный термин был введен в конце 50-х годов американским математиком Р. Беллманом в его известных монографиях [1, 2], в этих работах на основе рассмотрения функциональных уравнений были заложены математические основы ДП. В работах Р. Арис, Е.С. Вент-цель, Г. Вагнер, Н.М. Оскорбин, Дж. Моудера, Н.Ш. Кремер [3, 4, 5, 6, 7, 8], даны многочисленные примеры применения ДП.

При вычислительной реализация метода динамического программирования возникают трудности. Эти трудности Р. Беллман назвал "проклятием размерности". Они связаны с необходимостью хранения в процессе счета большого числа табулированных функций многих переменных. Одним из способов преодоления этих трудностей является выделение классов задач, которые допускают построение аналитических решений, или хотя бы аналитическое исследование. Примером такого подхода служит работа Sutherland, W.R.S.; Wolkowicz, Н.; Zeidan, V. [9]. В диссертации выделен класс задач, который можно условно назвать линейной моделью распределения ресурсов и проведено аналитическое исследование этих задач.

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

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

Основные задачи работы включают.

1. Установление связи между многомерной линейной моделью распределения ресурсов и дискретной одномерной динамической системой;

2. Изучение многомерной линейной модели распределения ресурсов с ограничениями и соответствующей динамической системы;

3. Исследование обобщенной линейной модели распределения многомерных ресурсов и соответствующей ей динамической системы;

4. Построение интегральной линейной модели распределения ресурсов с ограничениями;

5. Оптимизация транзитивного замыкания нечеткого отношения эквивалентности.

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

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

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

Первая глава диссертации посвящена элементарному введению в теорию динамического программирования, формулировке задачи динамического распределения ресурсов в наиболее простой экономической интерпретации [4].

Планируется деятельность т предприятий в течение п лет. Начальные средства составляют у\. Средства X, вложенные в г-ое предприятие, приносят к концу года доход /¿(X) и возвращаются в размере X) < Х\ г = 1,2,., т. По истечении года все оставшиеся средства заново перераспределяются между предприятиями, новых средств не поступает и доход в производство не вкладывается. Требуется найти оптимальный способ распределения имеющихся средств.

Процесс распределения ресурсов рассматривается как п-шаговый, в котором номер шага соответствует номеру года. Управляемая система в данном случае это т предприятий с вложенными в них средствами. Система характеризуется (р = 1) одним параметром состояния уи ¿ = 1,2, .,п -количеством средств, которые следует перераспределить в начале ¿-го года. Переменных управления на каждом шаге т [в — т), хц - количество средств, выделенных соответственно г-ому предприятию, г = 1,. ,т. Так как средства ежегодно перераспределяются полностью, то

Ха + хгг + . + хьт = У г-Пронормировав переменные управления = ^ получим, что ь

1ы + 7*2 + . + 7Ьтп = 1, 1ы > 0.

То есть точка = {7^} £ А"1-1 принадлежит (га — 1) - симплексу А171-1. Показатель эффективности данной задачи - это доход за один год

1(^1) + /2(^2) + . + /т(я*т).

Критерий оптимальности - доход полученный от т предприятий в течении п лет равен п

2 = [/1(^1) + /2(^2) + . +

Уравнение состояния выражает остаток средств yt после ¿-го шага и имеет вид

Уе+1 = ^1(^1) + (Р2Ы2) + . -I- (Рт(х1т).

Пусть Z*(Y,t) - условный оптимальный доход, полученный от распределения средств У между т предприятиями в период с ¿-го года до последнего n-го. Рекуррентные функциональные уравнения Беллмана для этих функций имеют вид:

Z*(yn,п) = тах lfi(xm) + . • + fm(xnm)]

- последнее уравнение Беллмана (при t = п), и

Z*(yut) = max \fi(xtl) + . + /m(xtm) + Z*(yt+ut+l)\

Xtl + .+Xtm-yt

- уравнения Беллмана при t = n — 1,., 1, здесь yt+i = tpi{xti) + <¿>2(^2) + . + ipm(octm)- Как видно из этих уравнений, даже для функций /¿, щ простого вида, рассчитывать на получение явного решения затруднительно. Большинство известных явных решений для двумерной задачи приведено в [1, 2, 3, 4].

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

Теорема (Теорема 1.2.1). Пусть функции fi(X) и Wi(X) (функции дохода и возврата средств соответственно), линейные fi{X) = hiX, tpi(X) =

ПХу hi 0, Ti >0, i— 1,2,., 772. Тогда функций условного оптимального дохода Z*(y,k) также будут линейные Z*(y,k) = Н^у, при этом коэффициенты Hk находятся рекуррентно:

Нп = А(0), Нп~1 = А(Нп),

Hi = А(Я2), где функция Х(х) = ^ах [hi + гг-ж] - верхняя огибающая линейных функций.

Оптимальному решению соответствует дискретная динамическая одномерная система, определяемая отображением х* — А(:г), траектория которой с начальной точкой хо = 0 позволяет полностью исследовать оптимальные решения на любом временном отрезке (см. рис. 2 пункта 1.2.1).

Определение. Коэффициентом эффективности i-ого предприятия назовем решение уравнения х = /ц 4- Г{Х , т. е. число hi р. —--l-n

Справедливо утверждение

Теорема (Теорема 1.2.3). Для многомерной линейной модели распределения ресурсов справедливы утверждения; таxhi < Hi < maxP^, i i lim Hi = maxPj n—+00 i

Далее условия hi > 0 и Г{ > 0 в теореме 1.2.1 последовательно ослабляются в серии теорем.

Теорема (Теорема 1.2.4). Пусть функции fi(X) и <Pi(X) (функции дохода и возврата средств соответственно), линейные fi(X) = h{X, <fii(X) = пХ:

Vi > 0, г = 1,2,., 77i. Тогда функции условного оптимального дохода Z*(y,k) будут положительно однородными 1-ого порядка Z*(Xy,k) = \Z*(y, к), при Л > то есть н£у, у> 0, I Щу, у< 0. при этом коэффициенты , Нк находятся рекуррентно; н: = х+( о), К-1 =

Н- = л-(0),

- Л-(Я-)

Я+ = А+(Я+), яг = Л-(Я2-), где функции А+(з;) = шах [/¿¿Н-тус], Л (х) = min [hi+rix] - соответ

1 <i<m l<i<m ственно верхняя и нижняя огибающая линейных функций.

Теорема (Теорема 1.2.5). Пусть функции fi(X) и Pi{X) (функции дохода и возврата средств соответственно), линейные fi{X) — hiX, <£>i(X) = TiX; maxi{rj} > 0 > mirii{ri}. Тогда функции условного оптимального дохода Z*(y,k) будут положительно однородными 1-ого порядка Z*(Xy,k) — XZ*(y, к), при Л > 0, то есть тах{Л+(Яп+),Л+(Я-)} , = min {Х~(Щ), Л"(Я")}

Я+ = тах {Л+(Я2+), Л+(Я2-)} , tff = min {Х~(Н}), Х~(Щ)} , где функции Х+(х) = тах [Л^ + ^х], X (х) = min [1ц + rix] - соответ

1<г<т 1<г<т ственно верхняя и нижняя огибающая линейных функций.

Оптимальному решению соответствует дискретная динамическая двумерная система, определяемая отображением траектория которой с начальной точкой гг0 = 0, уо = 0 позволяет полностью исследовать оптимальные решения на любом временном отрезке. А+(0)

Я" = Л-(0), х* = шах{Л+(х), Х+(у)} , у*= шт{Л-(х),Л-(у)},

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

Планируется деятельность т предприятий в течение п лет. Начальные средства составляют Средства X, вложенные в г-ое предприятие, приносят к концу года доход fi(X) и возвращаются в размере <Pi(X) < X; г = 1,2, .,т. По истечении года все оставшиеся средства заново перераспределяются поровну между определенным, фиксированным процентом а% предприятий (например а = 25%), которые имеет смысл финансово поддержать и привлечь к данному проекту. Новых средств не поступает, доход в производство не вкладывается.

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

Теорема (Теорема 1.2.6). Пусть функции fi{X) и <pi(X), линейные fi(X) = h{X, <Pi(X) — Г{Х; hi > 0, 0 < г* < 1, i = 1,2,. ,га. Тогда функции условного оптимального дохода Z*(y, к) также будут линейные Z*(y, к) = Н^у, при этом коэффициенты Hk находятся рекуррентно; нп = Aq(0),

Нп-1 = Аа(.?/П), #1 = Аа(Я2), функция Аа определена формулой Маоса [hi + TiX], здесь оператор Маха определена формулой:

1 Р г р ' 1

И 3=1 где > Нг2 > Ы3 > . > р = [та] - целая часть та.

Величину Маха {/¿¿} назовем верхним а-средним для числового семейства г

Кг}, а функцию Аа - верхней а-средней семейства линейных функций.

Определение. Групповым коэффициентом эффективности набора г из р предприятий, где г = {¿1, ¿2,., 1р\, назовем решение уравнения х — - + Ъкх)> 171■ е- ^исло Р Ъ

2^к=1 Пгк

Р —

1 р 1 - -12 к=1т

Теорема (Теорема 1.2.8). Для многомерной линейной модели распределения ресурсов с ограничением справедливы утверждения:

Маха^ < Нх < шах РТ, г т тахРт. п—+оо т

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

Теорема (Теорема 1.3.1). Пусть "ресурс" X = {х-7} €Е ЯР состоит из р компонент, функции "дохода" /{(X) = Кцх3 - линейные, отображения <Р1 : ЕР —» ВР - линейные, <Рг(Х) = {т^х^}3^, здесь по повторяющемуся индексу (вверху и внизу) вычисляется сумма, > 0, г^ > 0, г = 1,2,., т; jJs = 1,2, Тогда функции условного оптимального дохода Z*(Y,k) также будут линейными функционалами Z*{Yyk) = , при этом коэффициенты Zk = £ ЯР находятся рекуррентно: гп = Л(0), = А(£п), . Zx = Л(Я2), где отображение А : BP —> BP имеет компоненты XS(X), определяемые формулами:

XS(X) = max his + r3isXj 4 ' 1 <i<m L ls Ji

- выпуклые вниз функции (верхние огибающие линейных функций).

Замечание. Нахождение плана оптимального распределения ресурсов сводится к вычислению траектории {Z^} динамической системы, определяемой отображением X : В+ —> ВР+ с начальной точкой Zq = 0 в начале координат.

Определение. Вектором ("чистым") эффективности %-ого предприятия назовем решение уравнения xs = hiS + rfsXj , т. е. вектор

Пусть (3 : {1, 2,. ,р} —► {1,2,., т} произвольное отображение конечных множеств. Сопоставим (3 решение Рр системы уравнений xs = /¿3(s)s+ rP(s)sXj' т'е• вектоР

Рр = (Е - <pp)~lhp, где ц)р - "смесь" линейных операторов cpi, г = 1,2,. ,т, т.е. каждая строка матрицы оператора <рр есть строка с тем же номеров одной из матриц ifi, ¿ = 1,2,., т. Вектор Рр назовем вектором эффективности ¡3 "смеси" предприятий. Всего таких векторов будетрт. Если отображение ¡3 постоянное, то получаем "чистый" вектор эффективности.

Введем в пространстве BP норму по формуле

IMloo = max {1^,1}.

Соответствующая норма линейного оператора <р : BP —+ BP, <р(х) = {r-Xj} определяемая формулой

IMI = max П^Иоо,

1М1оо<1 будет равна .

1И = д«{ЕИ1

Теорема (Теорема 1.3.3). Пусть нормы линейных операторов строго меньше 1, тогда для многомерной линейной модели распределения ресурсов справедливы утверждения: max hi < i lim Zi = max P/3 > maxFj, n—>oo /? i где неравенство выполняется покомпонентно.

Вторая глава - "Бесконечномерная линейная модель распределения ресурсов с ограничениями" посвящена исследованию математической модели бесконечномерной (интегральной) задачи распределения ресурсов.

В случае очень большего числа линейных предприятий (порядка 10000) естественно перейти от конечного набора коэффициентов гi к вероятностному распределению пар чисел {h, г}. Будем считать, что задана функция совместной плотности распределения этих величин p(h, г) обладающая свойствами:

1. p(h^r) > 0 при h > 0 и г > 0, равная нулю в противном случае;

2. функция p(h,r) > 0 непрерывна при h > 0 и г > 0;

3. выполняется равенство л+оо л+оо

I I p(h, r)dpdh = 1. J о J о

4. конечны первые моменты + 00 л+оо /*+оо л+оо

Р + ОО Л+ОО Л+ОО Л + ОО / hp(h,r)dpdh < + оо, / / гр(/г,г)фс^ <+оо. 7о Уо Уо Уо

Введем обозначение М = [0, +оо) х [0, +оо) - множество (фазовое пространство) всех параметров предприятий. Доля предприятий, параметры которых лежат в прямоугольнике ЛМ = [/г, Н -Ь ДЛ] х [г, г -Ь Дг], равна лЛ+ДЛ лг+Аг j J p(h,r)dpdh ~ р(/г,г)ДрДЛ,

Рассмотрим следующую математическую модель деятельности М предприятий в течение п лет. Начальные средства составляют £о- Средства X, вложенные в множество dM предприятий, приносят к концу года доход f(dM, X) = X • hp(h, r)dpdh и возвращаются в размере (f){dM, X) = X • rp(h, r)dpdh. По истечении года все оставшиеся средства заново перераспределяются равномерно на каждый раз определяемом множестве Mi предприятий, доля которых составляет фиксированным процент а% (например а = 25%),

I p(h, r)dpdh = а.

J Mi

Это те предприятия, которые привлекаются к данному проекту на следующий год. Новых средств не поступает, доход в производство не вкладывается.

Требуется найти оптимальный способ отбора множеств {М*}, i = 1,., п тех предприятий, между которыми будет происходить распределение имеющихся средств. Процесс выбора рассматриваем как n-шаговый, в котором номер шага соответствует номеру года. Справедлива

Теорема (Теорема 2.1.1). В условиях задачи функции условного оптимального дохода Z*(y,k) будут линейные Z*(y,k) = Н^у, при этом коэффициенты Hk находятся рекуррентно:

Нп = Аа(0), 1 = \а(Нп), • • • Н\ = Ла(Я2), функция Аа определена формулой

Аа(х) = sup s I [h + rx\p(h, r)dhdr : / p(h, r)dhdr = a > , AC.M lJ A J A J для каждого x множество А С M на котором достигается супремум представляет собой область вида

Мх = {т = (h,r) Е М : h + хг > с} , где константа с зависит от выбора х и определяется из условия p(h,r)dpdh = а. s

Jmx

Замечание. В силу линейности подинтегралъной функции справедливо равенство [И + гх]р(к, г)с£Ыг = (/¿* -I- г*х) / г)(Ик1г, ]а за где точка , г*) - центр тяжести мноэюества А с данной плотностью массы р{К,г). Отсюда следует, что а(х) = [Л 4- гх]р(И, г)йкйг = (/г* 4- г*х)а, Змх где точка дх(Н*,г*) - центр тяжести множества Мх с данной плотностью массы г).

Определение. Положим

Их = {т= (к,г) е М :Н + хг < с} = М\ Мх. Выпуклое множество определенное равенством X назовем запретным уровня а.

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

Определение. Выпуклое множество определенное равенством

Оа = 0 Мх, х назовем общим уровня а.

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

Пусть £ = £(/1,г) - произвольная функция, А^Аг = Щ. - некоторое разбиение первого квадранта плоскости на два множества, введем обозначения: ¡1\ = I р(Н, r)dhdr, \12= p(h,r)dhdr,

6 = - / t(p,r)p{h,r)dhdr, ¿2 = - / £(р,г>(/г,г)сШг,

Д1УА1 Ач

I = [ £(р, г)р(Н, г)<1Мг, = [ к - е(р, г)]2р(Л, г)йк(1г ил2 и АхиАг

Тогда справедливо равенство ^£>1 + /^¿>2 + - б)2 + ■- Й)2, частный случай общего дисперсионного равенства). Возьмем в качестве множеств А\ = Мх и = ЛГХ, а в качестве функции £ = к + хг, тогда имеем: а, = 1 - а, = Д + ах, £>[£] = £>[/1 + хг],

6 = (Л* + хг*) = -\а(х), 6 = (Л" + хг**) = Н + Х* а 1 — а где точки г), яЦЬ*, г*), д**(Ь**, г**) - центры тяжести множеств Мх,

7УХ при данной плотности р(И,г).

Теорема (Теорема 2.1.2). Пусть конечны все центральные вторые моменты

D\ 1 = / (/г - h)2p(h, r)dhdr < 00,

Jr2+

D\2 — I (h — h)(r — f)p(h, r)dhdr < 00, D22 = I (r — f)2p(h,r)dhdr < 00,

Я» тогда справедливо равенство a(h + xf) — Aq(x)]'

Ai + 2xA2 + ягДм = + (1 - a)D2 + a(l — q)

Следствие. В условиях теоремы справедливо неравенство a(h + хг) - Aa(x)]2 < a( 1 - a)(Dn + 2xDu + x2D22).

Теорема (Теорема 2.1.3). Пусть конечны первые моменты, тогда справедливо неравенство

Ха(х) < —{h + xf).

OL

В главе 2, также подробно изучен случай независимого равномерного распределения {/г, г} и равномерного распределения {h, г} в круге.

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

При практическом разбиении на кластеры в теории нечеткого моделирования [27, 28, 29] используют понятие нечеткого множества и нечеткого отношения эквивалентности. Нечеткое отношение эквивалентности R (нечеткое подмножество X х X) определяется своей функцией принадлежности ßR : X х X —> [0,1] обладающей свойствами:

• Va Е X : а) = 1 - свойство рефлексивности,

• Va, Ъ £ X : fj,R(a,b) = ßR{by а) - свойство симметричности,

• Va, Ь, с G X : min {ßR(a, b),fj,R(b, с)} < /гя(а, с) - свойство транзитивности.

Нечеткое отношение назовем нечетким толерантным отношением, если выполнены лишь свойства рефлексивности и симметричности.

Определение. Ультраметрикой на множестве X называют функцию /?(а, Ь) удовлетворяющую аксиомам:

• Va е X : />(а, а) = 0,

• Va, b е X : р(а, 6) = р(Ь, а),

• У а, Ь,с € X : р(а, с) < шах {р(а, Ъ),р(Ъ, с)}. Лар?/ (X, р) называют улътраметрическим пространством.

Функция цк{а, Ь) определяет нечеткое отношение эквивалентности на множестве X в том и только в том случае когда функция рн(а, 6) = 1 — р,п(а, 6) - ультраметрика на X. Будем называть эту ультраметрику двойственной к нечеткому отношению эквивалентности.

Любое свойство нечеткого отношения эквивалентности имеет аналог в терминах ультраметрики, верно и обратное. Ультраметрические пространства обладают рядом замечательных свойств, например, они изометрично вкладываются в сферу гильбертового пространства (см. В.Н.Берестовский [34]), имеются многочисленные приложения этого понятия, как в самой математике (р-адический анализ), так и в других естественных науках (в биологии [38]).

Нас будет интересовать случай нечеткого отношения эквивалентности Я (или двойственной ультраметрики) на конечном множестве X, содержащем N точек а,г, г = 1,2,., N. Будем отождествлять точки с их номерами, т.е. аг = г. Введем обозначения: = \Ы\ = |И*|| =

Квадратные матрицы Я^, Яр размера N х N обладают свойствами:

О < < 1, 0 < рц < 1, (1)

Ни = 1, Ра = 0, (2)

Щ, = Кр = Яр, (3)

Я^оЯ^ = Я^, ЯрбЯр = Яр, (4) где определение композиций о, б числовых матриц дано ниже:

Определение. Мах-тт композицией (соответственно Мъп-тах и Мт-р1ив композицией) матриц Я = Цг^Ц, 5 = \\skjW размеров соответственно пхр и рх т называется матрица Т — ЯоБ (соответственно Т = ЯоБ и Т = Я О Б) размера п х т определяемая соответственно формулами:

Uj = maxjfe=if.>p{min(rifc,Sfcj)}, i — 1,. ,n, j = 1,. ,m, = minfc=1).)P{max(rifc,s^)}, г = 1,. ,n, j = 1,. ,m, iy = minfc=iv.)P {rifc + skj}, t = l,.,n,j = l,.,m.

Определение. £с./ш выполнены лишь свойства (1) - (3), то матрицы R^ и Rp будем называть матрицами сходства (соответсвенно несходства) для данного нечеткого толерантного отношения.

Определение. Пусть R = Rp ультраметрическая матрица, т.е. удовлетворяет условиям (1)-(4). Стандартная или каноническая форма матриц такого типа определяется рекуррентно:

Rn R12

К = ,

R21 R22 где Rn, R22 квадратные матрицы меньшей размерности в стандартной форме, а у матриц R12 = R21 все элементы имеет одинаковую величину равную D = max. Rij, где D - диаметр ультраметрического пространства.

Теорема (Теорема 3.1.2). Пусть матрица R удовлетворяет условиям (1)-(4), тогда ее элементы принимают не более чем N — 1 различных положительных значений, и путем перенумерации точек а{ € X матрицу можно привести к стандартной форме (рис. 1 пункта 3.1).

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

Пусть R нечеткое толерантное отношение определенное на множестве X и Р = {hiу I12,., hk} последовательность точек в X такая, что hi = г и hk = j. Будем называть Р путем соединяющим точки i,j £ X.

Определение. Шагом сходства (соответственно шагом несходства) вдоль пути Р называются величины:

Определение. Разделяющим сходством двух различных точек i, j мно-otcecmea X (соответсвенно разделяющим несходством) называются величины: san R{i,j) = rrmxsn(F), saáR(i,j) = minsd(P), где P произвольный путь соединяющий i и j. Если i — j, то sanR(i,j) = 1, sadñ(¿, j) = 0.

Теорема (Теорема 3.2.1). Для произвольного нечеткого толерантного отношения R функции sanR(i,j) и sadñ(¿,j») на множестве X х X определяют нечеткое отношение эквивалентности и двойственную ультраметрику.

Определение. Остовом графа G = (V, Е) называется его подграф G' = (V.E') с тем otee множеством вершин, являющийся деревом. Наименьшим остовом (SST) графа G — (V,E) называют остов, у которого сумма весов ребер наименьшая.

Нечеткому толерантному отношению R на множестве X сопоставим полный неориентированный граф G = (V, Е), где V = X, Е - множество всех неупорядоченных пар точек из X, с весовой функцией ребра {a¿, dj} равной величине несходства точек рц — pR(a,i,aj).

Теорема (Теорема 3.2.2). Обозначим через G' = (Х,Е') наименьший остов графа G = (Х,Е), тогда справедливы равенства: sa,nR(i,j) = sn<3'(P'), i sadñ(z,j) = sdG,(P'), где Р' единственный путь (без самоналожения) лежащий в остове G' — (Х,Е') и соединяющий вершины i и j.

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

В современной теории цифровой обработки изображений уделяется большое внимание разработкам методов выделения контуров [35, 36]. В последний годы методы нечеткой сегментации изображения интенсивно разрабатываются [46], [47].

Определим понятие локальной нечеткой близости двух линейных элементов Л(аг1, ух- <рх)> В(х2,7/2", ^2), где (а^, у{) - координаты точек, направление перпендикулярное полю градиенту в данных точках, по формуле где Я/(Л, В) истинное, если каждая из точек по отношению к другой лежит между ветвями гиперболы с вертикальной полуосью 7~о и горизонтальной полусью Го/. Таким образом / - тангенс половины угла раствора гиперболы (угла между асимптотами). На рисунке 1 пункта 4.2.1 показаны две таких линейных элементы и соответствующие им гиперболы. Параметр г о характеризует толщину линии, параметр / константу Липшицевости линии. Величина <1(А, В) - расстояние между точками, параметр п характеризует скорость "затухания" данного локального нечеткого отношения в зависимости от расстояния между точками.

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

Каждая линейный элемент изображается эллипсом, размер и форма которого управляется функцией /(А¿) = С^^ (матрица С^^ - в стандартной форме), что соответсвует наиболее грубой кластеризации.

Я(А,В) = ехр

Нёг1). ес™ Я/(Л,В) = 1, если В/(А, В) = О,

Визуальное сравнение рисунков указывает большую содержательность последнего.

В приложении даны программные модули в системе МаШЬ использованные в четвертой главе.

1. Беллман Р. Динамическое программирование. М.: Изд-во ИЛ, 1960.

2. Беллман Р., Дрейфус О. Прикладные задачи динамического программирования. М.: Наука, 1965. 457с.

3. Арис Р. Дискретное динамическое программирование. М.: Мир, 1969. 168с.

4. Вентцель Е.С. Исследование операций. М.: Наука, 1972.

5. Вагнер Г. Основы исследования операций М.: Мир, 1973.

6. Оскорбин Н.М., Суханов В.А. Исследование операций и теотия игр в элементарном изложении. Барнаул: Изд-во АГУ, 1987. 62 с.

7. Исследование операций: Т.1: Пер. с англ./ Под ред. Дж. Моудера, С. Элмаграби. М.: Мир, 1981.

8. Кремер Н.Ш., Путко Б.А., Тришин И.М. Исследование операций в экономике. ЮНИТИ, 1997.

9. Sutherland, W.R.S.; Wolkowicz, Н.; Zeidan, V. An explicit linear solution for the quadratic dynamic programming problem. J. Optimization Theory Appl. 58, No.2, 319-330 (1988).

10. Черноусько Ф.Л. Динамическое программирование. Соровский образовательный журнал. №2, 1998.

11. Карымов В.Р., Славская М.В. Многомерная линейная модель распределения ресурсов// Математическое образование на Алтае: Труды региональной научно-методической конференции. Барнаул: Изд-во АлГТУ,2001. С.33-36. '

12. Славская М.В. Многомерная линейная модель распределения ресурсов с ограничениями. Вестник БГПУ, №1, Барнаул 2001г. С. 41-44.

13. Славская М.В. Бесконечномерный аналог многомерной линейной модели распределения ресурсов с ограничениями. Тр. рубцовского индустр. инст. Вып.9, Рубцовск, 2001, 8с.

14. Славская М.В. Бесконечномерная линейная задача распределения ресурсов с ограничениями. Тезисы докладов краевой конференции МАК2002, Барнаул 2002г. 1с.

15. Славская М.В. Линейная модель распределения ресурсов с равномерным распределением параметров. Вестник БГПУ, №2, 2002. 6с.

16. Славская М.В. Бесконечномерная линейная задача распределения ресурсов с ограничениями. Тезисы докладов краевой конференции МАК-2002, Барнаул, 2002г.

17. Славская М.В. Бесконечномерная линейная задача распределения ресурсов с ограничениями. Тезисы докладов краевой конференции МАК-2002, Барнаул 2002г. 1с.

18. Славская М.В. Геометрический подход к решению одной задачи динамического программирования. Конференция-школа по геометрии и анализу-2002 посвященная памяти А.Д.Александрова, Новосибирск, 920 сентября 2002г. 1с.

19. Славская М.В. Динамическая линейная модель ресурсов с равномерным распределением параметров. Проблемы теоретической и прикладной математики. Труды 34-й региональной молодежной конференции. Екатеринбург: УрО РАН, УДК 517 ISBN 5-7691-1373-1 2003г. 6с.

20. Славская М.В. Непрерывная модель распределения ресурсов. Вестник БГПУ, №3, 2003. 6с.

21. Куркина М.В. Выпуклая динамическая система связанная с линейной задачей распределения ресурсов. Международная конференция-школа по геометрии и анализу-2004, Новосибирск, 23 авг.- 4 сент. 2004г. 1с.

22. Куркина М.В. Динамическая система связанная с линейной задачей распределения ресурсов. Вестник БГПУ, №3, 2004. бс.

23. Куркина М.В. Многомерная линейная модель распределения ресурсов с непрерывным временем. Конференция МОНО 2004, Барнаул, 2004г.

24. Куркина М.В., Славский В.В. Применение пакета "Scientific Workplace" для организации самостоятельной работы студентов и тестирования их знаний. Тезисы докладов краевой конференции МАК-2001, Барнаул 2004г. 2с.

25. Куркина М.В. Динамическая система связанная с линейной задачей распределения ресурсов. Доклады Академии Наук, Т. 401, №3, 2005. Зс.

26. Кристофидес Н. Теория графов. Алгоритмический подход. Москва:, Мир, 1978.

27. Zadeh L.A. Fuzzy sets. Information and Control, vol. 8, 1965, pp. 338-353.

28. Александр Леоненков. Нечеткое моделирование в среде MATLAB и fuzzyTECH. Санкт-Петербург:, БХВ-Петербург, 2003.

29. Yu LI, Jonathan LI, Haibin DONG, Xiangqian GAO. A fuzzy relation based algorithm for segmenting color aerial images of urban environment

30. Thomas J. Smith. Constructing ultrametric and additive trees based on Li norm. Journal of classification 18: 185-207(2001).

31. Farach M., Kannan S., and Warnow T. A robust model for finding optimal evolutionary trees, Algorithmica 13:155-179, 1995.

32. Hazewinkel M. Classification in Mathematics, Discrete Metric Spaces, and Approximation by Trees. // Report AM-R9505, CWI Amsterdam. The Netherlands.

33. Куратовский К., Мостовский А. Теория множеств. Москва:, Мир, 1979.

34. Цифровая обработка изображений в информационных системах. Учебник. Новосибирск:, НГТУ, 2002.

35. Введение в контурный анализ. Приложение к обработке изображений и сигналов. Под редакцией Я.А. Фурмана. -М. Наука, 2003.

36. Добеши И. Десять лекций по вейвлетам. -Москва-Ижевск., РХД, 2001.

37. J. Podani, P. Csontos and J. Tam6s. Additive trees in the analysis of community data. Community ecology 1: xxx-xxx, Akadftmiai Kiady, Budapest (2000).

38. Makarenkov, Vladimir. Comparison of Four Methods for Inferring Additive Trees from Incomplete Dissimilarity Matrices.

39. B.Leclerc, Minimum spanning trees for tree metrics: abridgements and adjustments, J. Classification 12 (1995) 207-241.

40. Wu, Bang Ye; Chao, Kun-Mao; Tang, Chuan Yi Approximation and exact algorithms for constructing minimum ultrametric trees from distance matrices. J. Comb. Optim. 3, No.2-3, 199-211 (1999).

41. Buneman, P. A Note on the Metric Properties of Trees, Journal of Combinatorial Theory (B), 17, 48-50. (1974)

42. Smolensky, V.A. A method for linear recording of graphs, USSR Comput. Math. Phys. 2 (1969) 396-397.

43. Агекян Т.А. Теория вероятностей для астрономов и физиков. М.: Наука, 1974. С.264

44. Nicholas Jardine, Robin Sibson, Mathematical taxonomy, Wiley, 1971.

45. Bruno M. Carvalho, C. Joe Gau, Gabor T. Herman and T. Yung Kong. Algorithms for Fuzzy Segmentation. // Pattern Analysis & Applications (1999)2:73-81.

46. Herman GT. Geometry of Digital Spaces. Boston, MA: Birkhauser, 1998

47. D. Bryant and V. Moulton. A polynomial time algorithm for constructing the refined buneman tree. Applied Mathematics Letters, 12:51-56, 1999.

48. V. Moulton and M. Steel. Retractions of finite distance functions onto tree metrics. Discrete Applied Math., 1998.

49. Farris J.S. A probability model for inferring evolutionary trees. Systematic Zoology, 22:250-256, 1973.

50. Konstantinos Georgatos. On Indistinguishability and Prototypes. L. J. of the IGPL, Vol. 11 No. 5, pp. 531-545, 2003.