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

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

Темирова Лилия Гумаровна

ДВУХУРОВНЕВОЕ МОДЕЛИРОВАНИЕ ДИСКРЕТНЫХ ЭВОЛЮЦИОННЫХ ПРОЦЕССОВ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

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

АВТОРЕФЕРАТ

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

Ставрополь-2004

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

в Карачаево-Черкесской государственной технологической академии на кафедре «Прикладная математика»

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

Перепелица Виталий Афанасьевич

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

Наац Игорь Эдуардович

Защита состоится 12 марта 2004 г. в 16.00. часов на заседании диссертационного совета Д 212.256.05 по присуждению ученой степени кандидата физико-математических наук в Ставропольском государственном университете по адресу: 355009, г. Ставрополь, ул. Пушкина, 1, ауд. 214

С диссертацией можно ознакомиться в научной библиотеке СГУ по адресу: г. Ставрополь, ул. Пушкина, 1.

Автореферат разослан « iOy> февраля 2004 г.

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

доктор технических наук, профессор Винтизенко Игорь Георгиевич

Ведущая организация: Кабардино-Балкарский государственный

университет им. Бербекова ХМ:, г. Нальчик

канд. физ.-мат. наук, доцент

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

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

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

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

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

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

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

1рос НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.Петербург . #

., 03 щчм

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

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

- исследование разрешимости с помощью классических подходов (в частности, алгоритмов линейной свертки критериев) рассматриваемых экстремальных задач на графах с интервальными весами;

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

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

Достоверность и обоснованность полученных в диссертационной работе теоретических результатов и формулировок обеспечивается корректным применением аппарата теории графов, математического программирования и теории вычислительной сложности алгоритмов, математической статистики, математического аппарата нечеткой и интервальной математики, методов теории детерминированного хаоса. Информационную базу исследования составили аналитические и статистические материалы Госкомстата России, в частности по Ставропольскому краю и Кабардино-Балкарской республике (КБР). Эффективность предложенных методов подтверждается валидацией результатов, полученных путем проведения численных расчетов.

На защиту выносятся следующие основные положения:

1. Концепция двухуровневого моделирования эволюционных дискретных процессов в условиях многокритериальности и неопределенности данных.

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

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

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

задач землепользования.

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

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

Научная новизна. Научную новизну диссертационного исследования содержат следующие положения:

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

2. На базе R/S-анализа разработан и реализован метод фрактального анализа временных рядов с целью выявления в них долговременной памяти и оценки степени применимости инструментария клеточных автоматов и нечетких множеств для построения прогнозной модели.

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

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

5. В качестве математической модели для верхнего уровня сформулирована и исследована векторная задача покрытия графа 4-циклами и паросочета-ниями. Первая из этих задач исследована для случая интервальных данных: осуществлено ее сведение к 2-критериальной задаче и установлена ее неразрешимость с помощью алгоритмов линейной свертки критериев (АЛСК).

6. В качестве базы для использования АЛСК разработан малотрудоемкий оптимизационный алгоритм покрытия графа 4-циклами и доказаны достаточные условия, при которых он является статистически эффективным.

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

мальному закону.

Предложенные методы, методики и алгоритмы моделирования на нижнем уровне были погружены в модельные и реальные экономические процессы и оправдали себя. Их корректность подтверждается расчетами на конкретных материалах прогнозирования; оценки точности прогнозирования вычислены в процессе валидации по заказу Министерства сельского хозяйства Ставропольского края; прогнозное значение урожайности озимой пшеницы за период с 1952 г. по 2002 год уклонялось от реального временного ряда в среднем не более, чем на 10%.

Разработанная модель и математический аппарат их количественного анализа и прогнозирования включены в лекционные курсы следующих дисциплин: «Теория рисков», «Дискретное программирование с нечеткими данными», читаемых на факультете прикладной математики и информатики КЧГТА, а также использованы при выполнении курсовых и дипломных проектов.

Апробация работы. Результаты исследования и основные его положения докладывались и обсуждались на заседаниях научно-методического семинара кафедры прикладной математики (КЧГТА, г. Черкесск, 2001-2003 гг.) и получили положительную оценку на следующих конференциях и симпозиумах, проводимых различными академическими учреждениями и высшими учебными заведениями России:

- на IV Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 2001);

- на Северо-Кавказской региональной научной конференции молодых ученых, аспирантов и студентов «Перспектива-2001» (Нальчик, 2001);

- на II Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (Нальчик, 2001);

- на IV научно-практической конференции аспирантов и студентов «Региональная экономика управления и права» (Черкесск, 2002);

- на Международной школе-семинаре по геометрии и анализу памяти Н.В. Ефимова (Абрау-Дюрсо, база отдыха Ростовского госуниверситета «Лиманчик», 2002);

- на X Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, Приволжский Дом знаний, 2002);

- на III Международной конференции «Новые технологии в управлении, бизнесе и праве» (Невинномысск, 2003г.);

- на VIII Международной конференции серии «Нелинейный мир» (Астрахань, 2003).

Теоретические и практические результаты диссертационной работы использованы при выполнении НИР по гранту РФФИ, проект № 00-0100652 «Математическое моделирование структуры слабо формализованных систем в условиях неопределенности».

Публикации. Материалы диссертации опубликованы в 4 научных статьях (из них 2 - в рецензируемых журналах) и в 11 тезисах докладов.

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

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

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

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

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

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

товный подграф , в котором каждая компонента связ-

ности является соответственно 4-циклом, звездой или ребром. Эти задачи являются многокритериальными, т.е. на множестве допустимых решений (МДР) X = ус} определена векторная целевая функция (ВЦФ)

F{x)={F1{x\F2{x),...,FM>

состоящая из критериев вида MAXSUM

fv(*)= 5>»->max> V Nl <N

и критериев вида MAXMIN

Fv(x)= min wv (e)-> max, v = NJ+i, N,

Ex

где Wv (e)- веса, приписанные ребрам £ (= E данного графа. Критерии вида MAXSUM представляют собой обычно экономические показатели, а критерии вида MAXMIN - агроэкологические показатели, папример, процентное содержание гумуса в почве. ВЦФ F(x) определяет в МДР X паретовское

множество (ПМ) X . Искомым решением векторной N - критериальной

задачи является полное множество альтернатив (ПМА) X0. Термин ПМА означает подмножество Xй С X , удовлетворяющее двум условиям:

1. Мощность минимальна;

2. р(х°)=р(х), где {/=•(*): *б X*} ЧХ'^Х-

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

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

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

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

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

Этап 2. Преобразование исходного числового временного ряда (ВР) в лингвистический временной ряд (ЛВР) с целью создания базиса памяти клеточного автомата. Для выполнения этапа 2 разработан «алгоритм преобразования ВР в ЛВР». На начальном этапе этого алгоритма формируется терм-множество ?/ = {м} характерных состояний исходного ВР, в частности трехэлементное множество - низкая урожайность,

и = С — средняя урожайность, и = В - высокая урожайность. Алгоритм преобразования ВР в ЛВР является вполне детерминированным, за исключением процедуры принятия решения о мощности формируемого терм-множества (экспертная оценка).

Этап 3. Алгоритм формирования оперативной памяти клеточного автомата. Эта память может имет комбинаторное или теоретико-графовое представление. В последнем случае она,строится в виде множества 2-дольных ориентированных графов, в каждом из. которых вершины правой доли взаимнооднозначно представляют собой элементы терм-множества u , а - вершины левой доли - фиксированные I- конфигурации; значения I — 1,2,...,L, где L- глубина памяти ЛВР. Дугам этих орграфов приписаны веса, означающие собой частости переходов заданной конфигурации в соответствующие состояния из U = {и}.

Этап 4. Алгоритм формирования прогноза для данного ЛВР Ut, Алгоритм вычисляет и представляет прогнозируемый элемент

Un+j в виде нечеткого множества (НМ) UК";.^)}, гДе Ц- - значение функции принадлежности элемента и. еUy j = 1,2,...,т, m = |i/|. Поскольку перечень элементов Uj G U является известным, то формирование

прогноза в виде НМ сводится к вычислению значений путем

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

Этап 5. Алгоритм трансформации полученного прогноза в виде нечеткого терм-множества в числовой прогноз. В качестве подходящих числовых значений элементов и j , где eU, j = 1,2,...,rn, выбираются в ВР ближайшие к ним низкие, средние и высокие урожайности, которые затем усредняются. Применяя к полученному нечеткому множеству операцию дефази-фикации имеем прогнозное значение урожайности в обычном числовом виде.

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

которые получаются путем последовательного удаления из ЛВР последних Г его членов. Для каждого фиксированного индекса т строим прогноз

терма Um+l, представляемого в виде НТМ Umil ={(Н;ЦИ),(С;1ХС),(В;Ц8)}.

Пусть, в полученном среди чисел макси-

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

ет с термом Ит+1 рассматриваемого ряда. Тогда, говорим, что для рассматриваемого индекса т прогнозная нечеткая модель привела к непротиворечивому прогнозу. В противном случае, говорим о противоречивом прогнозе для терма

Валидация результатов прогнозирования осуществлена на примере временных рядов урожайности озимой пшеницы по Ставропольскому краю и КБР. Для числового прогноза отклонение от реальных значений в среднем не превысила 10%.

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

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

культурами поля; Ск - стоимость единицы к-ой культуры, площады"-го

поля; (1к - директивное ограничение на минимальный объем выхода культуры к", 0 = (у1гУг,ЕУ двудольный граф, в котором вершины первой доли V, = перенумерованы индексами культур к = 1,2,..., т, а вер-

шины второй доли У2 = перенумерованы индексами полей

множество ребер графа которое содержит ребро е = (укг1>.) тогда и только тогда, когда в прогнозируемом году разрешается

засевать культуру на пахотные угодья поля Каждому ребру приписан вес И'*'1, представляющий собой нечеткое множество

и являющееся результатом

моделирования на нижнем уровне. Элемент-носитель И^"' = Ск • • {/^

содержательно означает ожидаемый

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

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

рубли, протеиновые единицы и др.

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

в котором каждая компонента связности представ-

ляет собой звезду хк = ({уДу/.-Е* ), у^ е V,, У2* С Уг, £* аЕх с центром

в определенной вершине V,. из первой доли V, и множеством V* висячих вершин из второй доли Уг ■ На МДР графа О определена целевая функция (ЦФ) Г(х)-> шах следующим образом. Для каждой пары (у*, у,), у^еУ,, V. е У2 определен объем ожидаемого урожая культуры к на поле г.

Допустимым является всякое такое решение х = (У,, Уг ,Е1), Е = Ц Е *, для

которого выполняются неравенства ^ >(1к> к = \,т', X = ={*} -

множество всех допустимых решений на графе О. Если целевой функцией (ЦФ) ¥(х) является экономический эффект, то она определяется на МДР

X следующим образом:

Задача состоит в том, чтобы найти максимизирующее значение ЦФ (1) решение, т.е. построить и обосновать достаточно эффективный алгоритм нахождения указанного оптимума. При верификации модели возникла проблема адекватного суммирования нечетких весов. Анализ известных теоретико-множественных операций суммирования нечетких множеств показал их несоответствие содержательному смыслу суммирования НВ в ЦФ (1). Этот факт обусловил приведение нового способа суммирования «(+)» нечетких весов, основанный на принципе частичной дефазификации. Суть этого суммирования состоит в следующем. Если конкретное допустимое

решение состоит из звезд то НВ

н{г*) одной звезды определяется выражением:

(+) *(е)=(К ^ ); ц1): Д е И"3}. (2)

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

суммированием а функция принад-

лежности /¿д вычисляется операцией дефазификацией.

Для определения операции суммирования НВ, относящихся к раЗЛИЧ-

^Ь. к

ным культурам к,, к2 рассматриваются две звезды zl':=z иг2 = г' „для которых вычислены их НВ согласно принципа частичной дефазификации (2). Результирующая сумма (+) нечетких весов этих двух культур пред-

ставляется в виде нечеткого множества

"&)(+) )={(К) + ^(г2))(г,) + ^(г2))):Де^0}, (3)

где функция принадлежности при этом определяется выражением: #*(*,.*,)=

Математическая постановка рассматриваемой задачи завершается определением бинарной операции сравнения. Практически все известные методы сравнения оперируют исключительно только функциями принадлежности, без учета численных значений элементов-носителей сравниваемых НВ. Такой способ сравнения не соответствует содержательному смыслу задачи землепользования. Предлагаемый в настоящей главе метод упорядочения НВ по предпочтительности базируется на процедуре полной дефазифи-кации. Прежде, чем приводить описание этой процедуры, отмечаются условия, при которых операция сравнения считается определенной. Рассматриваются два допустимых решения х,,Х,, (=. X,, на которых ЦФ (1) принимает значения в виде двух НВ

Д У = 1,2- (5)

Тогда, рассматривая величины в качестве максимизи-

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

^д(хх)> Н>д (х2 ), ма(х1)^м&(х2), а6{г/,с,в}, (6)

среди которых хотя бы одно является строгим.

В случае невыполнения условия (6) предлагается применить новый способ сравнения двух НВ. Для этого сначала вычисляются величины:

а затем и соответствующие им носители и степени принадлежности:

4*.}=4д/А/(*.), ц{х.)=ь{х.)1Н{х.). (7)

Пару условимся называть сверткой нечетких весов. Для

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

операция сравнения интервалов При этом границы

ся

этих интервалов рассматриваются в качестве максимизируемых показателей.

Определение 1. Вариант Х1 предпочтительнее варианта Хг (эквивален-

тсн варианту Х2 ), или в другой терминологии, Хг доминируется вариантом

Ху если выполняются неравенства /|(дг,)>/х(;с2), vvix,)^vt^:t2),

среди которых хотя бы одно является строгим (равенства fj(x1)= fi{x2),

w{x1) = н{ж2)). Эквивалентность этих вариантов обозначаем через х1~хг-

Определение 2. В гоианты х-у и хг являюс я несравнимыми^ ДГ2), если в паре интервалов J/i jt )J> j = 1,2, один из них является строгим

включением другого.

В главе 4 исследуется разрешимость интервальной задачи покрытия графа 4-циклами с помощью алгоритмов линейной свертки критериев (АЛСК). Предлагается малотрудоемкий алгоритм покрытия графа 4-циклами с оценкой его эффективности.

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

Алгоритмы линейной свертки критериев являются традиционными методами нахождения парето-оптимальных решений многокритериальных задач. На сегодняшний день построение эффективных АЛСК для многокритериальных задач остается одной из основных проблем оптимизации. Утверждение 1. Для любого вектора

Яе Л„ = |я = (Я,,Я2.....Л„): YjK = 1. К >0, v=l,2,...,wj элемент х\

максимизирующий на МДР X линейную свертку критериев целевых функций Fv(;c)t V =l,2,...,iV, является ПО.

v=I

Заметим, что AJICK не всегда гарантируют нахождение всех ПО

х 6 X. Если ПМ X индивидуальной интервальной задачи и 2*

критериальной задачи содержит такой элемент X , на котором не достигает максимума значение свертки ни при каком , то эти задачи

неразрешимы с помощью АЛСК. Из неразрешимости хотя бы одной индивидуальной задачи вытекает неразрешимость соответствующей массовой задачи.

В качестве частного случая задачи на графах с НВ сформулируем интервальную экстремальную задачу на графах. В заданном п -вершинном графе G = (V,£) каждое ребро ее Е взвешено интервалом н{е), т.е. отрез-

ком w(e)=[wi(«)tw2(e)], где и^е,)^w2(e). Подграф x = (Vx,EJC), VXQV, E„QE представляет собой допустимое решение рассматриваемой задачи. Обозначим через X ={■*■} МДР рассматриваемой задачи, на котором определена интервальная целевая функция (ИЦФ)

w(x) = 'Jj w(e) max (8)

или ИЦФ

w(jc) = mm w(e) max. (9)

Значение этих ИЦФ можно получить из свойств операций сложения интервалов и сравнения интервалов, представляющих значение ИЦФ

w(jc)=[iv1(:i)>w2(.x)]> где w,(jc)= ^н-Д*), i=l,2- Под решением интервальной задачи понимается такой элемент на котором значение

ИЦФ (8) или (9) достигает требуемого экстремума.

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

Отношения предпочтения и несравнимости порождают на МДР X па-ретовское множество (ПМ) ХсХ, состоящее из паретовских оптимумов (ПО).

Определение 3. Для задачи с ИЦФ (8) решение Х&Х называется ПО, если не существует такого, что ,

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

Определение 4. ПМА есть подмножество Xе QX минимальной мощности, содержащее по одному представителю на каждое значение w(pc),

хе X , где w(x) есть значение ИЦФ (8).

Теорема 1. Для всякого п -вершинного графа G (п кратно 4), интервальная задача покрытия графа 4-циклами с критериями вида MAXSUM неразрешима с помощью АЛСК.

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

ставленное в главе 1 МДР X = {.*} невозможно определить системой линейных равенств и неравенств, т.е. невозможно представить в виде многогранника в соответствующем пространстве.

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

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

мощности = т = —»л = 1,4> (ребрам ее Е приписаны веса

Далее, для двух пар строятся два двудольных

графа где множество состоит из всех та-

ких ребер е = (у',у*)е Е, у каждого из которых один к о нб Щ, а другой конец у' е V, ■

Второй этап состоит из двух вычислительных подэтапов. Работа подэ-тапов заключается в том, что в каждом из двудольных графов 012 И осуществляется нахождение оптимальных совершенных паросочетаний, которые обозначим соответственно через Мы И М-^. Для нахождения каждого из таких паросочетаний М„ — {е} можно воспользоваться каким-либо

известным алгоритмом (например, венгерским методом или алгоритмом Лоулера).

Объединяя паросочетания Мп И Мн, получаем Ш пар пересекающихся рёбер вида е' = (V,,У2), е" = (у2,У3),. Такие пары рёбер объединяем в 3-вершинные цепи вида С = [У1,У2>У3], множество этих цепей обозначим

Третий этап состоит в построении специального двудольного графа 0~<У^,В, 9$) с равномощными долями мощности [К4| = |в| = т • Доля В = ф}

состоит из вершин Ь & В, которые поставлены во взаимнооднозначное соответствие цепям се С. Если ребро рд =(у0,Ь) содержится в то оно определяется следующим образом: ребро р0 = (у0,Ь) включается в состав 91 тогда и только тогда, когда в исходном графе С = (У,Е) множество Е содержит пару рёбер е , следующего вида:

где и У3 являются висячими вершинами цепи

С = [У„у2,У3], (И)

поставленной в соответствие вершине Ъ . При этом ребру р0 приписывается вес Ж(р0) = м^е^ + у^е*). Если же пара р ё ®'е р', удовлетворяющая указанным условиям (Ю)и(Н) отсутствует в данном графе б, то соответственно ребро не включается во множество

Четвертый вычислительный этап состоит в том, что с помощью соответствующего алгоритма в двудольном графе выделяется оптимальное паросочетание М4 = {р}, затем для каждого ребра р , принадлежащего выделенному паросочетанию ,Д/4, в графе в выделяется соответст-

/ »

вующая ему пара ребер в и С , которая замыкает соответствующую цепь с = [Vj.V2.V3] в 4-вершинный цикл С=[У1;У01У3,У2]. Работа алгоритма завершается проверкой, все ли вершины исходного графа б оказались покрытыми выделенными 4-циклами. В случае положительного исхода множество выделенных циклов представляется в виде допустимого решения задачи о покрытии графа 4-циклами.

Пусть <р = <р(п)- сколь угодно медленно растущая функция от П <р(п)-> 0. 3(п,д)=ф}- множество всех - вершинных графов

G = (у,Щ, в каждом из которых всякому ребру е £ Е, приписан вес

. Для всякого обозначим через под-

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

ный алгоритм СХ находит оптимальное покрытие 4-циклами. Если отноше-

„ |зв(«,2г1

ние мощностей при , то алгоритм называется ста-

тистически эффективным. Достаточное условие статистической эффективности предложенного выше алгоритма ОС представляет

Теорема 2. При выполнении неравенства п алгоритм ОС

41п п + <р

является статистически эффективным.

В процессе своей работы алгоритм ОС рассматривает каждое ребро данного графа С = (У,Я) не более нескольких раз, откуда вычислительная сложность его первых трех этапов составляет оффИО(п2)- Отсюда вычислительную сложность алгоритма можно оценить через вычислительную сложность четвертого этапа (нахождения совершенного паросочстания):

т(а) < 0(п2) + 0(п3) = о(п3).

ЗАКЛЮЧЕНИЕ

Основные результаты, полученные в ходе исследований можно пред-

ставить в виде следующего перечня:

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

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

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

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

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

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

1. Темирова Л.Г. Полиномиально разрешимый подкласс теоретико-графовой модели для задачи землепользования /Тезисы II Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики». КБНЦ РАН, 3-7 декабря 2001 г. - Нальчик, 2001. - С.45-46. _

2. Темирова Л.Г. Статистически эффективный алгоритм для одной задачи формирования целевых групп. Материалы Северо-Кавказской региональной научной конференции молодых ученых, аспирантов и студентов «Перспектива-2001».- Нальчик, 2001.- С.191-198.

3. Темирова Л.Г., Петова Е.Х Об одном подходе к моделированию процесса формирования состава малых групп. Решение научно-технических и социально-экономических проблем современности /Сб. трудов IV научно-практической конференции. Часть II.- Черкесск: Изд-воКЧГТИ, 2002.-С.42-44.

4. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Моделирование экстремальных задач на графах с нечеткими данными /Труды участников Международной школы-семинара по геометрии и анализу памяти Н.В. Ефимова, Абрау-Дюрсо, 5-11 сентября 2002 г. - Ростов-на-Дону: МГУ, РГУ, 2002. - С.267.

5. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Дискретное программирование с нечеткими данными. Сб.научлрудов V Всероссийского симпозиума. «Математическое моделирование экономических и экологических систем», г.Кисловодск, 17-19 октября 2002г.-Кисловодск: Изд.центр КИЭП, 2002. - С.7-10.

6. Темирова Л.Г. Статистически эффективный алгоритм для одной задачи землепользования //Современные аспекты экономики. - Санкт-Петербург. - 2002 г.- №15(28). - С.47-56.

7. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Об одной задаче землепользования в условиях неопределенности. Математические методы и информационные технологии в экономике, социологии и образовании: Сб. статей X Международной научно-технической конференции.- 24-25 декабря 2002 г. - Пенза, 2002. - С.69-71.

8. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Новый метод прогнозирования на базе клеточных автоматов и нечетких множеств /Тезисы докладов VIII Международной конференции серии «Нелинейный мир», г. Астрахань, 15-20 сентября 2003 г. - Астрахань: ГУЛ «Издательско-полиграфический комплекс», «Волга», 2003.- С.240.

9. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г, Касаева М.Д. Построение прогнозной модели урожайности на базе клеточных автоматов и нечетких множеств /«Менеджмент, экономика и финансы, региональное управление». Труды III Международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании», г. Таганрог, 10-13 сентября 2003 г. - Таганрог: Изд-во Таганрогского института управления и экономики, 2003. - С. 182-185.

10. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Фрактальный анализ устойчивости развивающихся агросистем. Материалы III Международной научно-практической конференции «Математическое моделирование в образовании, науке и производстве». Тирасполь, 17-20 сентября, 2003 г. - Тирасполь: РИО ПТУ, 2003. - С.56-59.

11. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г., Касаева М.Д. Использование инструментария клеточных автоматов для формирования прогнозных нечетких значении урожайностей на базе временного ряда

//Известия вузов. Северо-Кавказский регион.- 2003.- №4.- С.67-76.

12. Касаева М.Д., Перепелица В.А., Темирова Л.Г. Прогнозная модель урожайности на базе линейного клеточного автомата //Современные аспекты экономики - 2003. - №4(32). - С. 190-206.

13. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Математическая модель землепользования на базе нечетких множеств и клеточных автоматов //Электронный журнал «Исследовано в России».- 2003.- С. 2429-2438, http:// zhurnal. ape.relam.ni/articles/003/207.pdf.

14. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г., Касаева М.Д. Об одном подходе к оценке глубины фрактальной памяти временных рядов уро-жайностей. Международный Российско-Узбекский симпозиум «Уравнения смешанного типа и родственные проблемы анализа и информатики», Нальчик - п.Эльбрус, 21-25 мая 2003 г.- Нальчик: НИИ ПМА КБНЦРАН, 2003. - С.59-61.

15. Перепелица В.А.,Тебуева Ф.Б., Темирова Л.Г., Касаева М.Д. Прогнозная модель урожайности на базе клеточных автоматов и нечетких множеств /Труды Ш Международной конференции «Новые технологии в управлении, бизнесе и праве», г.Невинюшысск, 2003, 30 мая 2003 г., -Невинномысск: ИУБиП, 2003. - С. 163-167.

Отпечатано в Издательско-полиграфическом участке Карачаево-Черкесской государственной технологической академии 369000, г. Черкесск, ул. Ставропольская, 36.

Формат 60x84 1/16 Бумага офсетная

Усл.печ.л. 1,1 Тираж 100 экз,

Подписано в печать 06.02.04 _Заказ 00087

J - 3338

ВВЕДЕНИЕ.

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

1.1. Актуальность 2-уровневого моделирования.

1.1.1. Фундаментальная научная проблема.

1.1.2. Предлагаемые методы и подходы.

1.1.3. Современное состояние науки в данной области исследования.

1.2. Содержательное описание проблемы моделирования задач землепользования.

1.3. Необходимость многокритериального подхода.

ГЛАВА 2. КЛЕТОЧНО-АВТОМАТНАЯ ПРОГНОЗНАЯ МОДЕЛЬ ДЛЯ НИЖНЕГО УРОВНЯ.

2.1. Необходимость разработки новых методов прогнозирования.

2.2. Алгоритм R/S- анализа.

2.3. Содержательная и качественная интерпретация результатов работы алгоритма R/S- анализа.

2.4. Фрактальный анализ временного ряда озимой пшеницы по КБР за период с 1952 по 2002 г.

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

2.6. Математический инструментарий линейных клеточных автоматов.

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

2.7.1. Преобразование числового временного ряда в лингвистаческий временной ряд.

2.7.2. Частотный анализ памяти лингвистического временного ряда.

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

2.7.4. Получение числового прогноза, и оценка его точности.

ГЛАВА 3. ТЕОРЕТИКО-ГРАФОВЫЕ МОДЕЛИ ЗАДАЧ ЗЕМЛЕПОЛЬЗОВАНИЯ С НЕЧЕТКИМИ ДАННЫМИ.

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

3.2. Математическая постановка векторной задачи покрытия графа 4-циклами (паросочетаниями, звездами).

3.3. Анализ арифметических операций и отношения предпочтения для задач с нечеткими данными.

3.4. Новые определения операции суммирования и сравнения, адекватные математической модели задачи землепользования с нечеткими данными.

3.4.1. Математическая постановка задачи.

3.4.2. Новая операция суммирования (+) нечетких весов.

3.4.3. Операция сравнения нечетких весов.

ГЛАВА 4. ЗАДАЧИ ВЕРХНЕГО УРОВНЯ. ИССЛЕДОВАНИЕ ВЫЧИСИТЕЛЬНОЙ СЛОЖНОСТИ, РАЗРЕШИМОСТИ С ПОМОЩЬЮ АЛГОРИТМОВ ЛИНЕЙНОЙ СВЕРТКИ И АЛГОРТИМ С ОЦЕНКАМИ ДЛЯ ЗАДАЧ ПОКРЫТИЯ ГРАФА 4-ЦИКЛАМИ.

4.1. Формулировка интервальной экстремальной задачи.

4.2. Аппроксимация интервальной задачи покрытия графа 4-циклами векторной задачей.

4.3. Исследование разрешимости с помощью алгоритмов линейной свертки критериев задачи с интервальными данными и Критесвертки критериев задачи с интервальными данными и критериями вида MAXSUM.

4.4. Обоснование свойства полноты задачи покрытия графа 4-циклами.ИЗ

4.5. Исследование вычислительной сложности.

4.6. Оценки точности приближенных алгоритмов.

4.7. Приближенный алгоритм покрытия графа 4-циклами.

4.8. Обоснование достаточных условий статистической эффективности алгоритма а.

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

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

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

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

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

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

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

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

- исследование разрешимости с помощью классических подходов (в частности, алгоритмов линейной свертки критериев) рассматриваемых экстремальных задач на графах с интервальными весами;

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

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

Достоверность и обоснованность полученных в диссертационной работе теоретических результатов и формулировок обеспечивается корректным применением аппарата теории графов, математического программирования и теории вычислительной сложности алгоритмов, математической статистики, математического аппарата нечеткой и интервальной математики, методов теории детерминированного хаоса. Информационную базу исследования составили аналитические и статистические материалы Госкомстата России, в частности по Ставропольскому краю и Кабардино-Балкарской республике (КБР). Эффективность предложенных методов подтверждается верификацией и валидацией результатов, полученных путем проведения численных расчетов.

На защиту выносятся следующие основные положения:

1. Концепция двухуровневого моделирования эволюционных дискретных процессов в условиях многокритериальности и неопределенности данных.

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

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

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

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

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

Научная новизна. Научную новизну диссертационного исследования содержат следующие положения:

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

2. На базе R/S-анализа разработан и реализован метод фрактального анализа временных рядов с целью выявления в них долговременной памяти и оценки степени применимости инструментария клеточных автоматов и нечетких множеств для построения прогнозной модели.

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

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

5. В качестве математической модели для верхнего уровня сформулирована и исследована векторная задача покрытия графа 4-циклами и па-росочетаниями. Первая из этих задач исследована для случая интервальных данных: осуществлено ее сведение к 2-критериальной задаче и установлена ее неразрешимость с помощью алгоритмов линейной свертки критериев (AJTCK).

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

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

Предложенные методы, методики и алгоритмы моделирования на нижнем уровне были погружены в модельные и реальные экономические процессы и оправдали себя. Их корректность подтверждается расчетами на конкретных материалах прогнозирования; оценки точности прогнозирования вычислены в процессе валидации по заказу Министерства сельского хозяйства Ставропольского края; прогнозное значение урожайности озимой пшеницы за период с 1952 г. по 2002 год уклонялось от реального временного ряда в среднем не более, чем на 10%.

Разработанная модель и математический аппарат их количественного анализа и прогнозирования включены в лекционные курсы следующих дисциплин: «Теория рисков», «Дискретное программирование с нечеткими данными», читаемых на факультете прикладной математики и информатики КЧГТА, а также использованы при выполнении курсовых и дипломных проектов.

Апробация работы. Результаты исследования и основные его положения докладывались и обсуждались на заседаниях научно-методического семинара кафедры прикладной математики (КЧГТА, г. Черкесск, 2001-2003 гг.) и получили положительную оценку на следующих конференциях и симпозиумах, проводимых различными академическими учреждениями и высшими учебными заведениями России:

- на IV Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 2001);

- на Северо-Кавказской региональной научной конференции молодых ученых, аспирантов и студентов «Перспектива-2001» (Нальчик, 2001);

- на II Международной конференции «Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики» (Нальчик, 2001);

- на IV научно-практической конференции аспирантов и студентов «Региональная экономика управления и права» (Черкесск, 2002);

- на Международной школе-семинаре по геометрии и анализу памяти Н.В. Ефимова (Абрау-Дюрсо, база отдыха Ростовского госуниверситета «Ли-манчик», 2002);

- на X Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, Приволжский Дом знаний, 2002);

- на III Международной конференции «Новые технологии в управлении, бизнесе и праве» (Невинномысск, 2003г.);

- на VIII Международной конференции серии «Нелинейный мир» (Астрахань, 2003).

Теоретические и практические результаты диссертационной работы использованы при выполнении НИР по гранту РФФИ, проект № 00-01-00652 «Математическое моделирование структуры слабо формализованных систем в условиях неопределенности».

Публикации. Материалы диссертации опубликованы в 4 научных статьях (из них 2 - в рецензируемых журналах) и в 11 тезисах докладов.

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

2. Основные результаты исследований главы 4 относятся к алгоритмическим вопросам решения рассматриваемых задач землепользования в условиях неопределенности.

3. Основное внимание уделено исследованию вычислительной сложности и разрешимости с помощью алгоритмов линейной свертки критериев задачи покрытия графа 4-циклами.

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

3. В качестве конкретной реализации 2-уровневого моделирования представлена математическая постановка экстремальных задач покрытия графа 4-циклами (паросочетаниями, звездами); показана неприменимость известных в научной литературе определений операции сложения и сравнения нечетких весов; представлено новое определение операции суммирования и сравнения нечетких весов, которые адекватны рассматриваемым задачам землепользования.

4. Исследована разрешимость с помощью алгоритмов линейной свертки критериев (AJICK) векторная задача покрытия графа 4-циклами с интервальными весами; осуществлено ее сведение к 2-критериальной задаче и установлена ее неразрешимость.

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

1. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. — М.: Мир, 1987.- 360 с.

2. Алтунин А.Е., Семухин М.В. Модели и алгоритмы принятия решений в нечетких условиях. Тюмень: Изд-во ТюмГУ, 2000. - 352 с.

3. Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979.-536 с.

4. Баккет М. Фермерское производство: организация, управление, анализ,-М.: Агропромиздат, 1989.-464 с.

5. Батищев А.Ф., Перепелица В.А. Об одном алгоритме нахождения оптимального севооборота//Оптимизация планирования. 1970 16. С. 16-20.

6. Беляева И.П. Практические приложения интервального анализа // ВЦ СО АН СССР. Переславль - Залесский, 1988.- 156 с.

7. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учебное пособие. М.: Финансы и статистика, 2001.-368 с.

8. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.-333 с.

9. Борисов А.Н., Алексеев А.В., Меркурьева Г.В. Обработка нечеткой информации в системах принятия решений. М.: Радио и связь, 1989.- 304 с.

10. Ю.Буров Д.И., Чуданов И.А. Некоторые вопросы плодородия черноземных почв в связи с освоением пропашных севооборотов. В сб. Гидрофизика и структура почвы. Вып. 11. Л.: Гидрометеорологическое изд-во, 1965. -С.196-204.

11. П.Векленко В.И. Экономическая проблема устойчивости и повышения эффективности земледелия.- Курск: Изд-во Курской сельскохозяйственной академии, 1999.- 216 с.

12. Винтизенко И.Г. Детерминированное прогнозирование в экономическихсистемах // Труды III международной конференции «Новые технологии в управлении, бизнесе и праве», Невинномысск: Издательство ИУБП, 2003. С.163-167

13. Возбуцкая А.Е. Химия почвы.- 3-е изд., исправленное и дополненное. Под ред.проф. Д.Л. Аскинази.- М.: Высшая школа, 1968.- 427 с.

14. Н.Вощинин А.П., Сотиров Г.Р. Оптимизация в условиях неопределенности. М., 1989.

15. Гирлих Э., Ковалев М.М., Кравцов М.К., Янушкевич О.А. Условия разрешимости векторных задач с помощью линейной свертки критериев //Кибернетика и системный анализ. 1999. № 1. С. 81 -95.

16. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.: Мир, 1982.-416 с.

17. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. Новосибирск: Изд-во Новосиб. ун-та, 1996.- 167 с.

18. Долятовский В.А. Переход от хаоса к порядку в экономике: роль хаотических процессов в формировании организации. В сб. российский менеджмент на пороге 21 в. - Краснодар: ЮРИМ, 1997. - 33-46.

19. Долятовский В.А., Касаков А.И., Коханенко И.К. Методы эволюционной и синергетической экономики в управлении. Отрадная: Изд-во РГЭУ -ИУБиП - ОГИ, 2001. - 577 с.

20. Емеличев В.А. , Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, Гл. ред. физ.-мат. лит., 1990. - 384 с.

21. Емеличев В.А., Перепелица В.А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах//Журн. Выч. Математики и мат. физики.- 1989.-Т.29, №2.- С.171-183.

22. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач//Дискретная математика 1994.- Т.6, №1.- С.3-33.

23. Жирабок А.Н. Нечеткие множества и их использование для принятия решений // Соровский образовательный журнал. 2001.- Том 7, №2. - С. 109-115.

24. Заде JI.A. Понятие лингвистической переменной и его применение к принятию приближенных решений. М: Мир, 1976, 165 с.26.3анг В.-Б. Синергетическая экономика. Время и перемены в нелинейной экономической теории. М.: Мир, 1999.-335 с.

25. Калмыков С.А., Шокин Ю.А., Юлдашев З.Х. Методы интервального анализа. Новосибирск: Наука, Сибирское отделение, 1986.-224 с.

26. Ким-Гю-Пхир. Оптимальное распределение ресурсов в условиях интервальной неопределенности. М.: Наука, 1992. - 256 с.

27. Козина Г.Л., Рябовол Л.Д., Захарова А.В. основы интервального исчисле-ния.-Запорожье: Изд-во ЗГУ, 1996. 47 с.

28. Коршунов А.Д. Об одном алгоритме нахождения паросочетаний в конечных графах // Кибернетика. 1975. - №1. - С. 1-8.

29. Коршунов А.Д. Основные свойства случайных графов с большим числом вершин и ребер//Успехи матем. наук. 1985. -Т.40, №1 (241).-С.107-173.

30. Кравцов М.К. Неразрешимость задач векторной дискретной оптимизации в классе алгоритмов линейной свертки критериев //Дискретная математика.- 1996.- 8, №2.- С. 89-96.

31. Кремер Н.Ш. Теория вероятностей и математическая статистика: Учебник для вузов. М.: ЮНИТИ - ДАНА, 2000. - 543 с.

32. Курдюмов С.П., Малинецкий Г.Г., Потапов А.Б. Нестационарные структуры, динамический хаос, клеточные автоматы. В сб. Новое в синергетике. Загадки мира неравновесных структур. М.: Наука, 1996. - С. 95-164.

33. Ларичев О.И. Наука и искусство принятия решения М.: Наука, 1979.- 200 с.

34. Лопатников Л.И. Экономико-математический словарь. М.: Наука, 1987.

35. Лоскутов А.Ю., Михайлов А.С. Введение в синергетику: Учебное руководство. М.: Наука, 1990. - 240 с.

36. Малинецкий Г.Г., Потапов А.Б. Нелинейность. Новые проблемы, новые возможности. В кн. Новое в синергетике. Загадки мира неравновесных структур. -М.: Наука, 1996. -С. 165-190.

37. Месарович М., Мако Д., Такахара И. Теория Иерархических многоуровневых систем. М.: Мир, 1973. - 344 с.

38. Михалевич B.C., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно транспортного планирования.- М.: Наука, 1986.- 264 с.

39. Назаренко Т.И., Марченко Л.В. Введение в интервальные методы вычислительной математики. Иркутск: Изд-во Иркутского университета, 1987. -107 с.

40. Нейман Дж. Теория самовоспроизводящихся автоматов. М.: Мир, 1971. -378 с.43.0ре О. Графы и их применение.- М.: Мир, 1965 173 с.

41. Орловский С.А. Проблемы принятия решений при нечеткой исходной информации. М.: Наука, 1981. - 203 с.

42. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.- М.: Мир, 1985.- 512 с.

43. Пасов В.М. Синоптико-статистический метод прогнозирования зерновых культур// Методология и гидрология. 1992. - №10. - С.77-84.

44. Перепелица В.А., Сергиенко И.В, Исследование одного класса целочисленных многокритериальных задач //Журнал вычисл. матем. и матем. физики. 1988. - 28, № 3. - С. 400-419.

45. Перепелица В.А., Касаева М.Д, Темирова Л.Г. Прогнозная модель урожайности на базе линейного клеточного автомата // Современные аспекты экономики 2003. - №4(32). - С. 190-206.

46. Перепелица В.А., Мамедов А.А. Исследование сложности и разрешимости векторных задач на графах: Уч. пособие. Черкесск, 1995.- 68 с.

47. Перепелица В.А., Сергеева JI.H. Исследование неразрешимости с помощью алгоритма линейной свертки 3-невырожденных дискретных многокритериальных задач //Кибернетика и системный анализ. — 1996. — № 2. -С. 71-77.

48. Перепелица В.А., Тебуева Ф.Б. Агроэкономическая задача покрытия графа звездами // Тезисы докладов Седьмой международной конференции «Математика. Компьютер. Образование». Дубна, 2002. -163 с.

49. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Математическая модель землепользования на базе нечетких множеств и клеточных автоматов// Электронный журнал «Исследовано в России».- 2003.- С. 2429-2438, http:// zhurnal.ape.relarn.ru/articles/003/207.pdf

50. Петерс Э. Хаос и порядок на рынках капитала. Новый аналитический взгляд на циклы, цены и изменчивость рынка. М.: Мир, 2000. - 333 с.

51. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.Наука, 1982.- 256 с.

52. Пригожин И., Стингере И. Порядок из хаоса. Новый диалог человека с природой. -М.: Прогресс, 1986.

53. Прикладные нечеткие системы. Под редакцией Т.Тэрано, К.Асаи, М.Сугэно. М.: Мир, 1993. - 368 с.

54. Рощин В.А., Семенова Н.В., Сергиенко Н.В. Декомпозиционный подход к решению некоторых задач целочисленного программирования с неточными данными //Журнал вычисл. матем. и матем. физики. 1990. - 29, № 5.- С. 789-791.

55. Рюэль Д., Такенс Ф. О природе турбулентности// Странные аттракторы. -М.; 1991, С.117-151.

56. Сакович В.А. Исследование операций: Справочное пособие.- Минск, 1985.- 256 с.

57. Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. М.: Мир, 1984.-455 с.

58. Сергеева Л.Н. Моделирование поведения экономических систем методами нелинейной динамики (теории хаоса). Запорожье: ЗГУ, 2002. - 227 с.

59. Сигел, Эндрю. Практическая бизнес-статистика.: Пер. с англ. М.: Издательский дом «Вильяме», 2002. - 1056 с.

60. Суслов О.П., Кудина Т.М. Моделирование формирования иерархической структуры систем управления // Машинная обработка информации . Киев: Ин-т нар.хоз-ва, 1988.- № 46. - С. 116-126.

61. Темирова Л.Г. Статистически эффективный алгоритм для одной задачи формирования целевых групп. Материалы Северо-Кавказской региональной научной конференции молодых ученых, аспирантов и студентов «Пер-спектива-2001».-Нальчик, 2001.- С. 191-198.

62. Темирова Л.Г. Статистически эффективный алгоритм для одной задачи землепользования // Современные аспекты экономики. Санкт-Петербург. -2002 г.- №15(28).-С.47-56.

63. Федер Е. Фракталы. М.: Мир, 1991. - 260 с.

64. Шокин Ю.И. Интервальный анализ // ВЦ СО АН СССР.- Новосибирск, 1988.- 137 с.

65. Шустер Г. Детерминированный хаос: Введение. М.: Мир, 1988. - 240 с.

66. Яновский Л.П. Принципы, методология и научное обоснование урожая по технологии «Зонт». Воронеж: ВГАУ, 2000.-379 с.

67. Cootner P. "Comments on the Variation of Certain Speculative Prices", in P. Cootner ed. The Random Character of Stock Market Prices. Cambridge: MIT Press, 1964 a.

68. Holden К., Peel D.A. and Thompson J.L. Press Syndicate of the University of Cambridge, 1990.-P. 231.

69. Kuchert W.Y.M. and oth. Application of Fuzzy Controller in a Warm Water Plant. "Automatica", v. 12, №4, 1976, P.301-308.

70. Lodwick A.W. Special Issue on the Linkages Between Interval Mathematics and Fuzzy Set Theory // Reliable Computing. 2002. - Volume 8 - P. 93-95.

71. Mandelbrot B. The Fractal Geometry of Nature. New York: W.H.Freeman, 1982.

72. Packard N., Cruthfield I., Forman D., Shaw R. "Geometry from a Time Series", Phisical Review Letters 45, 1980.

73. Perepelitsa V.A. and Kozina G.L. Interval Discrete Models and Multiobjectiv-ity. // Interval computations. 1993. - №1. - P. 51-59.

74. Scheikman J.A., LeBaron B. "Nonlinear Dynamics and Stock Returns". Journal of Business 62, 1989.-P. 311-337/

75. Zadeh L.A. Fuzzy sets. Inf. Contr., 1965, 8, P.338-353.