СОДЕРЖАНИЕ

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




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




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


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




АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук




Ставрополь-2004
Работа выполнена //Известия вузов. Северо-Кавказский регион.- 2003.- №4.- С.67-76.
в Карачаево-Черкесской государственной технологической академии 12. Касаева М.Д., Перепелица В.А., Темирова Л.Г. Прогнозная модель
на кафедре «Прикладная математика» урожайности на базе линейного клеточного автомата //Современные
аспекты экономики – 2003. - №4(32). – С.190-206.
Научный руководитель: доктор физико-математических наук, профессор 13. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Математическая модель
землепользования на базе нечетких множеств и клеточных автоматов
Перепелица Виталий Афанасьевич
//Электронный журнал «Исследовано в России».- 2003.- С. 2429-2438,
Официальные оппоненты: доктор физико-математических наук, профессор http:// zhurnal.ape.relarn.ru/articles/003/207.pdf.
14. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г., Касаева М.Д. Об одном
Наац Игорь Эдуардович
подходе к оценке глубины фрактальной памяти временных рядов уро-
доктор технических наук, профессор жайностей. Международный Российско-Узбекский симпозиум «Урав-
нения смешанного типа и родственные проблемы анализа и информа-
Винтизенко Игорь Георгиевич
тики», Нальчик - п.Эльбрус, 21-25 мая 2003 г.- Нальчик: НИИ ПМА
Ведущая организация: Кабардино-Балкарский государственный КБНЦ РАН, 2003. – С.59-61.
университет им. Бербекова Х.М., г. Нальчик 15. Перепелица В.А.,Тебуева Ф.Б., Темирова Л.Г., Касаева М.Д. Прогноз-
ная модель урожайности на базе клеточных автоматов и нечетких мно-
жеств /Труды III Международной конференции «Новые технологии в
управлении, бизнесе и праве», г.Невинномысск, 2003, 30 мая 2003 г., –
Невинномысск: ИУБиП, 2003. – С.163-167.
Защита состоится 12 марта 2004 г. в 16.00. часов на заседании диссертацион-
ного совета Д 212.256.05 по присуждению ученой степени кандидата физико-
математических наук в Ставропольском государственном университете по
адресу: 355009, г. Ставрополь, ул. Пушкина, 1, ауд. 214



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




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



Формат 60х84 1/16 Подписано в печать
Бумага офсетная Усл.печ.л. 1,1 06.02.04
Тираж 100 экз. Заказ 00087
Отпечатано в Издательско-полиграфическом участке
Карачаево-Черкесской государственной технологической академии
Ученый секретарь 369000, г. Черкесск, ул. Ставропольская, 36.
диссертационного совета
канд.физ.-мат. наук, доцент Л.Б.Копыткова
19
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. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г., Касаева М.Д. Исполь- новых методов прогнозирования эволюционных процессов на базе ли-
зование инструментария клеточных автоматов для формирования про- нейных клеточных автоматов, математического аппарата теории нечет-
гнозных нечетких значений урожайностей на базе временного ряда ких множеств и инструментария теории детерминированного хаоса;

18 3
- осуществление анализа известных теоретико-множественных определе- ставить в виде следующего перечня:
ний операции суммирования нечетких множеств и вместе с тем пред- 1. Сформулирована авторская концепция двухуровневого моделирования
ставление нового обоснованного определения операций суммирования и задач землепользования: математическая модель верхнего уровня – это
сравнения нечетких весов для исследуемой задачи землепользования; модель теории оптимизации, на базе которой строится и обосновывает-
- исследование вычислительной сложности рассматриваемых задач на ся наиболее целесообразное управление рассматриваемым процессом;
графах с нечеткими или интервально заданными весами ребер, пред- на нижнем уровне осуществляется моделирование исходных данных
ставляющими урожайность; для модели верхнего уровня; исходными данными для нижнего уровня
- исследование разрешимости с помощью классических подходов (в част- служат временные ряды, отражающие эволюцию основных показате-
ности, алгоритмов линейной свертки критериев) рассматриваемых экс- лей рассматриваемых эволюционных процессов; изложена необходи-
тремальных задач на графах с интервальными весами; мость многокритериального подхода и суть его реализации.
- разработка малотрудоемких алгоритмов для экстремальных задач по- 2. На базе инструментария фрактального анализа выявлены такие свойст-
крытия графа типовыми подграфами (паросочетаниями, звездами, 4- ва временных рядов, как долговременная память с оценкой ее глубины,
циклами) и обоснование достаточных условий статистической эффек- трендоустойчивость, квазицикличность; для выявления этих свойств
тивности предлагаемых алгоритмов. разработан метод фазового анализа временных рядов; на базе инстру-
Методы исследования. Для решения поставленных в работе научных ментария линейных клеточных автоматов и нечетких множеств разра-
задач использованы методы теории алгоритмов с оценками, теории графов, ботана новая прогнозная модель, включая алгоритмы ее валидации и
многокритериальной оптимизации, теории вероятностей и математической вычисления оценок точности прогнозирования.
статистики, теории нечетких множеств и интервального исчисления, методы 3. В качестве конкретной реализации двухуровневого моделирования
прогнозирования временных рядов. представлена математическая постановка экстремальных задач покры-
Достоверность и обоснованность полученных в диссертационной ра- тия графа 4-циклами (паросочетаниями, звездами); показана неприме-
боте теоретических результатов и формулировок обеспечивается коррект- нимость известных в научной литературе определений операций сло-
ным применением аппарата теории графов, математического программиро- жения и сравнения нечетких весов; представлено новое определение
вания и теории вычислительной сложности алгоритмов, математической операций суммирования и сравнения нечетких весов, которые адекват-
статистики, математического аппарата нечеткой и интервальной математи- ны рассматриваемым задачам землепользования.
ки, методов теории детерминированного хаоса. Информационную базу ис- 4. Исследована на разрешимость с помощью алгоритмов линейной сверт-
следования составили аналитические и статистические материалы Госком- ки критериев векторная задача покрытия графа 4-циклами с интерваль-
стата России, в частности по Ставропольскому краю и Кабардино- ными весами; осуществлено ее сведение к 2-критериальной задаче и
Балкарской республике (КБР). Эффективность предложенных методов под- установлена ее неразрешимость.
тверждается валидацией результатов, полученных путем проведения чис- 5. В качестве базы для использования алгоритма линейной свертки разра-
ленных расчетов. ботан малотрудоемкий алгоритм покрытия графа 4-циклами и доказа-
ны достаточные условия, при которых он является статистически эф-
На защиту выносятся следующие основные положения:
1. Концепция двухуровневого моделирования эволюционных дискретных фективным.
процессов в условиях многокритериальности и неопределенности дан-
Список основных трудов по теме диссертации
ных.
1. Темирова Л.Г. Полиномиально разрешимый подкласс теоретико-
2. Конкретный алгоритм реализации фрактального анализа временных ря-
графовой модели для задачи землепользования /Тезисы II Междуна-
дов урожайности с целью выявления в них наличия долговременной па-
родной конференции «Нелокальные краевые задачи и родственные
мяти как предпосылки для построения прогнозной модели.
проблемы математической биологии, информатики и физики». КБНЦ
3. Построенная для нижнего уровня на базе инструментария клеточных ав-
РАН, 3-7 декабря 2001 г. - Нальчик, 2001. - С.45-46.
томатов и теории нечетких множеств математическая модель и метод
2. Темирова Л.Г. Статистически эффективный алгоритм для одной задачи
прогнозирования урожайности основных культур, выращиваемых в зонах
формирования целевых групп. Материалы Северо-Кавказской регио-
рискового земледелия.
нальной научной конференции молодых ученых, аспирантов и студен-
4. Разработанные для верхнего уровня специальные подходы к моделирова-
тов «Перспектива-2001».- Нальчик, 2001.- С.191-198.
нию задач землепользования с нечеткими весами, включая обоснование
операций суммирования и сравнения, адекватных реальному содержанию

4 17
поставленной в соответствие вершине b . При этом ребру ? 0 приписывает- задач землепользования.
5. Результаты анализа применимости классических подходов, в частности,
ся вес W ( ? 0 ) = w(e?) + w(e??) . Если же пара рёбер e ? , e ?? , удовлетворяющая алгоритмов линейной свертки критериев к конкретной задаче землеполь-
указанным условиям (10) и (11) отсутствует в данном графе G , то соответ- зования, сформулированной как задача покрытия графа 4-циклами с
ственно ребро ? 0 не включается во множество ? . интервальными весами.
6. Разработанный для верхнего уровня моделирования задачи землепользо-
Четвертый вычислительный этап состоит в том, что с помощью соот-
вания алгоритм отыскания оптимального покрытия графа 4-циклами,
ветствующего алгоритма в двудольном графе D = (V , B, ?) выделяется оп- включая обоснование достаточных условий его статистической эффек-
тимальное паросочетание M 4 = {?} , затем для каждого ребра ? , принадле- тивности.
Научная новизна. Научную новизну диссертационного исследования
жащего выделенному паросочетанию M 4 , в графе G выделяется соответст-
содержат следующие положения:
e ? и e ?? , которая замыкает соответствующую цепь
вующая ему пара рёбер 1. Предложен двухуровневый подход к моделированию эволюционных
c = [v1 , v2 , v3 ] в 4-вершинный цикл c = [v1 , v0 , v3 , v2 ] . Работа алгоритма за- задач землепользования в условиях многокритериальности и неопреде-
ленности данных.
вершается проверкой, все ли вершины исходного графа G оказались по-
2. На базе R/S-анализа разработан и реализован метод фрактального анализа
крытыми выделенными 4-циклами. В случае положительного исхода мно-
временных рядов с целью выявления в них долговременной памяти и
жество выделенных циклов представляется в виде допустимого решения
оценки степени применимости инструментария клеточных автоматов и
задачи о покрытии графа 4-циклами.
нечетких множеств для построения прогнозной модели.
Пусть ? = ? (n ) - сколь угодно медленно растущая функция от n , 3. В качестве реализации модели нижнего уровня построена прогнозная
? (n ) > 0 . ?(n, R ) = {G} - множество всех n - вершинных графов модель на базе клеточных автоматов, а также разработаны алгоритмы
G = (V , E ) , в каждом из которых всякому ребру e ? E , приписан вес прогнозирования, валидации и вычисления оценки погрешности резуль-
татов.
w(e ) ? { ,2,3,..., R} ; R = R (n ) . Для всякого n обозначим через ?? (n, R ) под-
1 4. С учетом принципиальной нечеткости исходных данных, получаемых на
множество таких графов G ? ?(n, R ) , для каждого из которых определен- нижнем уровне, оценена степень пригодности известных теоретико-
ный алгоритм ? находит оптимальное покрытие 4-циклами. Если отноше- множественных определений арифметических операций для нечетких
множеств и предложены новые способы операций сложения и сравнения,
?? (n, R )
> 1 при n > ? , то алгоритм ? называется ста- отвечающие содержательному смыслу рассматриваемых задач земле-
ние мощностей
?(n, R ) пользования.
5. В качестве математической модели для верхнего уровня сформулирована
тистически эффективным. Достаточное условие статистической эффектив-
ности предложенного выше алгоритма ? представляет и исследована векторная задача покрытия графа 4-циклами и паросочета-
ниями. Первая из этих задач исследована для случая интервальных дан-
алгоритм ?
n
Теорема 2. При выполнении неравенства R 2 ?
ных: осуществлено ее сведение к 2-критериальной задаче и установлена
4 ln n + ?
ее неразрешимость с помощью алгоритмов линейной свертки критериев
является статистически эффективным. (АЛСК).
В процессе своей работы алгоритм ? рассматривает каждое ребро 6. В качестве базы для использования АЛСК разработан малотрудоемкий
данного графа G = (V , R ) не более нескольких раз, откуда вычислительная оптимизационный алгоритм покрытия графа 4-циклами и доказаны дос-
таточные условия, при которых он является статистически эффективным.
сложность его первых трех этапов составляет O( E ) ? O(n 2 ) . Отсюда вычис-
Практическая ценность полученных результатов и их реализация.
лительную сложность алгоритма ? можно оценить через вычислительную
Практическая значимость результатов исследования заключается в том, что
сложность четвертого этапа (нахождения совершенного паросочетания):
предложенные подходы, математические модели и алгоритмы универсальны
? (? ) ? O(n2 ) + O(n3 ) = O(n3 ) . и позволяют решать широкий круг агроэкономических задач. Построенные
ЗАКЛЮЧЕНИЕ на базе клеточных автоматов модель и метод прогнозирования временных
рядов урожайности могут быть использованы всюду, где поведение рас-
Основные результаты, полученные в ходе исследований можно пред- сматриваемого эволюционного процесса с памятью не подчиняется нор-

16 5
ставленное в главе 1 МДР X = {x} невозможно определить системой линей-
мальному закону.
Предложенные методы, методики и алгоритмы моделирования на ниж- ных равенств и неравенств, т.е. невозможно представить в виде многогран-
нем уровне были погружены в модельные и реальные экономические про- ника в соответствующем пространстве.
Разработанный алгоритм ? состоит из подготовительного этапа, четы-
цессы и оправдали себя. Их корректность подтверждается расчетами на
конкретных материалах прогнозирования; оценки точности прогнозирова- рех вычислительных этапов и заключительного этапа формирования резуль-
ния вычислены в процессе валидации по заказу Министерства сельского татов.
хозяйства Ставропольского края; прогнозное значение урожайности озимой Подготовительный этап заключается в разбиении в данном n - вершин-
пшеницы за период с 1952 г. по 2002 год уклонялось от реального времен-
ном графе G = (V , E ) множества V на четыре равномощных подмножества
ного ряда в среднем не более, чем на 10%.
n
Разработанная модель и математический аппарат их количественного Vs мощности Vs = m = , s = 1,4 , (ребрам e ? E приписаны веса
анализа и прогнозирования включены в лекционные курсы следующих дис- 4
w(e) ?{1,2,....,R} ). Далее, для двух пар V1,V2 и V2 ,V3 строятся два двудольных
циплин: «Теория рисков», «Дискретное программирование с нечеткими
данными», читаемых на факультете прикладной математики и информатики
графа Gst = (Vs ,Vt , Est ) , 1 ? s < t ? 3, где множество Est состоит из всех та-
КЧГТА, а также использованы при выполнении курсовых и дипломных про-
ких ребер e = (v?, v??) ? E , у каждого из которых один конец v? ? Vs , а другой
ектов.
Апробация работы. Результаты исследования и основные его положе-
конец v?? ? Vt .
ния докладывались и обсуждались на заседаниях научно-методического
Второй этап состоит из двух вычислительных подэтапов. Работа подэ-
семинара кафедры прикладной математики (КЧГТА, г. Черкесск, 2001-2003
тапов заключается в том, что в каждом из двудольных графов G12 и G23
гг.) и получили положительную оценку на следующих конференциях и сим-
позиумах, проводимых различными академическими учреждениями и выс- осуществляется нахождение оптимальных совершенных паросочетаний,
шими учебными заведениями России:
которые обозначим соответственно через M 12 и M 23 . Для нахождения каж-
- на IV Всероссийском симпозиуме «Математическое моделирование и
дого из таких паросочетаний M st = {e} можно воспользоваться каким-либо
компьютерные технологии» (Кисловодск, 2001);
- на Северо-Кавказской региональной научной конференции молодых известным алгоритмом (например, венгерским методом или алгоритмом
ученых, аспирантов и студентов «Перспектива–2001» (Нальчик, 2001); Лоулера).
- на II Международной конференции «Нелокальные краевые задачи и род- Объединяя паросочетания M12 и M 23 , получаем m пар пересекаю-
ственные проблемы математической биологии, информатики и физики»
щихся рёбер вида e? = (v1 , v 2 ), e?? = (v 2 , v3 ), . Такие пары рёбер объединяем
(Нальчик, 2001);
- на IV научно-практической конференции аспирантов и студентов «Ре- в 3-вершинные цепи вида c = [v1 , v2 , v3 ] , множество этих цепей обозначим
гиональная экономика управления и права» (Черкесск, 2002);
C = {c}.
- на Международной школе-семинаре по геометрии и анализу памяти
Третий этап состоит в построении специального двудольного графа
Н.В. Ефимова (Абрау-Дюрсо, база отдыха Ростовского госуниверситета
D = (V4 , B, ?) с равномощными долями мощности V4 = B = m . Доля B = {b}
«Лиманчик», 2002);
- на Х Международной научно-технической конференции «Математиче- состоит из вершин b ? B , которые поставлены во взаимнооднозначное соот-
ские методы и информационные технологии в экономике, социологии и
ветствие цепям с ? С . Если ребро ?0 = (v0 , b) содержится в ? , то оно опре-
образовании» (Пенза, Приволжский Дом знаний, 2002);
?
деляется следующим образом: ребро ? 0 = (v0 , b) включается в состав
- на III Международной конференции «Новые технологии в управлении,
бизнесе и праве» (Невинномысск, 2003г.); тогда и только тогда, когда в исходном графе G = (V , E ) множество E со-
- на VIII Международной конференции серии «Нелинейный мир» (Астра-
e ? , следующего вида:
держит пару рёбер
хань, 2003).
e? = (v0 , v1 ) , e ?? = (v 0 , v3 ) , (10)
Теоретические и практические результаты диссертационной работы
использованы при выполнении НИР по гранту РФФИ, проект № 00-01-
v1 и v3 являются висячими вершинами цепи
где
00652 «Математическое моделирование структуры слабо формализованных
c = [v1 , v 2 , v 3 ] , (11)
систем в условиях неопределенности».

6 15
ком w(e ) = [w1 (e ), w2 (e )] , где w(e1 ) ? w2 (e ) . Подграф x = (V x , E x ) , V x ? V , Публикации. Материалы диссертации опубликованы в 4 научных
статьях (из них 2 – в рецензируемых журналах) и в 11 тезисах докладов.
E x ? E представляет собой допустимое решение рассматриваемой задачи.
Структура и объем работы. Диссертация состоит из введения, четы-
Обозначим через X = {x} МДР рассматриваемой задачи, на котором опреде- рех глав, заключения, приложений и списка литературы, содержащего 92
наименования.
лена интервальная целевая функция (ИЦФ)
w(x ) = w(e ) > max
? КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
(8)
e?E x
Во введении обосновывается актуальность темы диссертационного ис-
или ИЦФ
следования, сформулирована цель работы, описана структура и дан краткий
w( x ) = min w(e ) > max . (9)
обзор работы, изложены основные научные результаты, выносимые на за-
e? E x
щиту, раскрыта научная новизна и практическая значимость полученных
Значение этих ИЦФ можно получить из свойств операций сложения
результатов.
интервалов и сравнения интервалов, представляющих значение ИЦФ
w(x ) = [w1 (x ), w2 ( x )], где wi ( x ) = ? wi ( x ), i = 1,2 . Под решением интер- В главе 1 дано содержательное описание предложенного двухуровне-
вого подхода к моделированию эволюционных агроэкономических процес-
e?E x
сов, показатели которых не подчиняются нормальному закону распределе-
вальной задачи понимается такой элемент x 0 ? X , на котором значение
ния.
ИЦФ (8) или (9) достигает требуемого экстремума. Математическая модель верхнего уровня – это модель теории оптими-
В случае интервальных весов нахождение оптимума наталкивается на зации, на базе которой строится и обосновывается наиболее целесообразное
проблему выбора наиболее целесообразного решения из множества несрав- управление рассматриваемым процессом. На нижнем уровне осуществляет-
нимых альтернатив. Отношения предпочтения, эквивалентности и несрав- ся моделирование исходных данных для модели верхнего уровня.
нимости определены в главе 3 настоящего исследования. На верхнем уровне формируются теоретико-графовые модели задач
Отношения предпочтения и несравнимости порождают на МДР X па- землепользования. В качестве таких постановок рассмотрены задачи покры-
˜
ретовское множество (ПМ) X ? X , состоящее из паретовских оптимумов тия графа 4-циклами, звездами и ребрами. Если задача формулируется на
графе G = (V , E ) , то ее допустимое решение представляет собой такой ос-
(ПО).
Определение 3. Для задачи с ИЦФ (8) решение ˜ ? X называется ПО, товный подграф x = (V, Ex ) , Ex ? E , в котором каждая компонента связ-
x
если не существует x * ? X такого, что x f ˜ .
*
x ности является соответственно 4-циклом, звездой или ребром. Эти задачи
В качестве искомого решения сформулированной задачи можно рас- являются многокритериальными, т.е. на множестве допустимых решений
˜ (МДР) X = {x} определена векторная целевая функция (ВЦФ)
сматривать как ПМ X , так и используемое в многокритериальной оптими-
F ( x ) = (F1 ( x ), F2 (x ), ..., FN ( x )) ,
0
зации понятие ПМА X .
˜
Определение 4. ПМА есть подмножество X 0 ? X минимальной мощ- состоящая из критериев вида MAXSUM
ности, содержащее по одному представителю на каждое значение w( x ) , F? (x ) = ? w? (e) > max , ? = 1, N , N1 ? N
1
˜
x ? X , где w(x ) есть значение ИЦФ (8). e?E x

и критериев вида MAXMIN
Теорема 1. Для всякого n -вершинного графа G ( n кратно 4), интер-
F? ( x ) = min w? (e ) > max, ? = N 1 + 1, N ,
вальная задача покрытия графа 4-циклами с критериями вида MAXSUM не- e?E x
разрешима с помощью АЛСК.
где w? (e ) - веса, приписанные ребрам e ? E данного графа. Критерии вида
В качестве базы для реализации АЛСК предлагается приближенный
MAXSUM представляют собой обычно экономические показатели, а крите-
алгоритм покрытия графа 4-циклами и произведено обоснование его стати-
рии вида MAXMIN – агроэкологические показатели, например, процентное
стической эффективности. Необходимость разработки такого алгоритма
содержание гумуса в почве. ВЦФ F ( x ) определяет в МДР X паретовское
обусловлена тем обстоятельством, что для решения рассматриваемых задач
˜
верхнего уровня неприменимы какие-либо известные алгоритмы, в том чис-
множество (ПМ) X . Искомым решением векторной N - критериальной
ле и алгоритмы линейного или целочисленного программирования. Указан-
ная неприменимость, в свою очередь, обусловлена тем фактом, что пред-
14 7
0
тен варианту x 2 ), или в другой терминологии, x 2 доминируется вариантом
задачи является полное множество альтернатив (ПМА) X . Термин ПМА
˜
x1 (x1 f x2 ) , если выполняются неравенства µ (x1 ) ? µ (x2 ) , w(x1 ) ? w(x2 ) ,
означает подмножество X 0 ? X , удовлетворяющее двум условиям:
среди которых хотя бы одно является строгим (равенства µ ( x1 ) = µ (x2 ) ,
0
Мощность X
1. - минимальна;
2. F (X 0 ) = F (X ) , где F (X * ) = {F ( x ) : x ? X * } ? X * ? X .
˜
w( x1 ) = w( x2 ) ). Эквивалентность этих вариантов обозначаем через
x1 ˜ x2 .
Определение 2. Варианты x1 и x 2 являются несравнимыми ( x1 - x 2 ) ,
В главе 2 предлагаются инструментальные и математические методы
моделирования временных рядов, которые обладают долговременной памя-
если в паре интервалов [µ (x j ), w (x j )], j = 1,2 , один из них является строгим
тью и вместе с тем в характере их поведения проявляется хаотичность. На-
включением другого.
личие такой памяти исключает независимость наблюдаемых значений эле-
В главе 4 исследуется разрешимость интервальной задачи покрытия
ментов временных рядов, что, в свою очередь является причиной неподчи-
графа 4-циклами с помощью алгоритмов линейной свертки критериев
нения этих рядов нормальному закону распределения. Этот факт подтвер-
(АЛСК). Предлагается малотрудоемкий алгоритм покрытия графа 4-
ждается также такими результатами статистического анализа, как аномально
циклами с оценкой его эффективности.
большие значения коэффициентов эксцесса и асимметрии. С учетом выяв-
Следует отметить, что интервальные задачи являются крайним случаем
ленных ситуаций становится неправомерным использование классических
неопределенности, т.к. возникают в условиях неточных данных параметров
методов прогнозирования, которые базируются на вычислении скользящей
задачи. Вопрос разрешимости интервальной задачи покрытия графа 4-
средней и авторегрессии.
циклами с помощью АЛСК до настоящего времени оставался открытым. В
В главе осуществлено построение прогнозной модели для нижнего
главе 4 обосновывается сведение интервальной задачи покрытия графа 4-
уровня на базе аппарата нечетких множеств и клеточных автоматов. Разра-
циклами к 2-критериальной и доказывается ее неразрешимость с помощью
ботаны и представлены методы и алгоритмы для выявления фундаменталь-
АЛСК, а следовательно, и соответствующей ей интервальной задачи.
ных качественных и системных свойств, а именно: глубина долговременной
Алгоритмы линейной свертки критериев являются традиционными ме-
памяти и ее оценка, мера хаотичности или, наоборот, трендоустойчивости,
тодами нахождения парето-оптимальных решений многокритериальных
квазицикличность, самоподобие.
задач. На сегодняшний день построение эффективных АЛСК для многокри-
Предлагаемая новая прогнозная модель для временного ряда с памятью
териальных задач остается одной из основных проблем оптимизации.
состоит из следующих пяти этапов, т.е. отдельных алгоритмов или проце-
Утверждение 1. Для любого вектора
дур.
Этап 1. Оценка степени прогнозируемости данного семейства времен- ? ? *
? ? ? N = ?? = (?1 , ? 2 ,..., ? N ) : ? ?? = 1, ?? > 0, ? = 1,2,..., N ? элемент x ,
ных рядов осуществляется на базе фрактального анализа некоторой выборки
? ?
из этого семейства. На выходе вычислительного алгоритма фрактального
X линейную свертку критериев
анализа получаются оценки следующих характеристик для рассматривае- максимизирующий на МДР
мых рядов: признаки наличия трендоустойчивости и долговременной памя-
F ? (x ) = ? ?? F? (x ) целевых функций F? ( x ), ? = 1,2,..., N , является ПО.
N

ти, оценка ее глубины; цвет шума, достаточно удаленный от зоны белого
? =1
шума.
Заметим, что АЛСК не всегда гарантируют нахождение всех ПО
Этап 2. Преобразование исходного числового временного ряда (ВР) в ˜ ˜
˜ ? X . Если ПМ X индивидуальной интервальной задачи и 2-
x
лингвистический временной ряд (ЛВР) с целью создания базиса памяти
*
критериальной задачи содержит такой элемент x , на котором не достигает
клеточного автомата. Для выполнения этапа 2 разработан «алгоритм преоб-
максимума значение свертки F ( x ) ни при каком ? ? ? 2 , то эти задачи
разования ВР в ЛВР». На начальном этапе этого алгоритма формируется ?
терм-множество U = {u} характерных состояний исходного ВР, в частности
неразрешимы с помощью АЛСК. Из неразрешимости хотя бы одной инди-
трехэлементное множество U = {Н , С , В} : u = H – низкая урожайность, видуальной задачи вытекает неразрешимость соответствующей массовой
u = C – средняя урожайность, u = B – высокая урожайность. Алгоритм пре- задачи.
образования ВР в ЛВР является вполне детерминированным, за исключени- В качестве частного случая задачи на графах с НВ сформулируем ин-
тервальную экстремальную задачу на графах. В заданном n -вершинном
ем процедуры принятия решения о мощности U формируемого терм-
графе G = (V , E ) каждое ребро e ? E взвешено интервалом w(e) , т.е. отрез-
множества (экспертная оценка).

8 13
ставляется в виде нечеткого множества Этап 3. Алгоритм формирования оперативной памяти клеточного авто-
w( z1 ) (+) w(z 2 ) = {((w? ( z1 ) + w? ( z 2 )); µ (w? (z1 ) + w? ( z 2 ))) : ? ? W 0 }, (3) мата. Эта память может иметь комбинаторное или теоретико-графовое
представление. В последнем случае она строится в виде множества 2-
где функция принадлежности при этом определяется выражением: дольных ориентированных графов, в каждом из которых вершины правой
L (z , z ) (4)
µ (w? (z1 ) (+) w? (z 2 )) = ? 1 2 , доли взаимнооднозначно представляют собой элементы терм-множества U ,
N ? ( z1 , z 2 ) а вершины левой доли - фиксированные l - конфигурации; значения
где L? ( z1 , z 2 ) = w? ( z1 ) ? µ ? ( z1 ) + w? (z 2 ) ? µ ? ( z 2 ) , l = 1,2,..., L , где L - глубина памяти ЛВР. Дугам этих орграфов приписаны
N ? ( z1 , z 2 ) = w? ( z1 ) + w? ( z 2 ) , ? ? W 0 . веса, означающие собой частости переходов заданной конфигурации в соот-
ветствующие состояния из U = {u}.
Математическая постановка рассматриваемой задачи завершается оп-
ределением бинарной операции сравнения. Практически все известные ме- Этап 4. Алгоритм формирования прогноза для данного ЛВР u i ,
тоды сравнения оперируют исключительно только функциями принадлеж-
i = 1,2,.., n . Алгоритм вычисляет и представляет прогнозируемый элемент
ности, без учета численных значений элементов-носителей сравниваемых
в виде нечеткого множества (НМ) U n +1 (µ ) = {(u j , µ j )}, где µ j – зна-
u n +1
НВ. Такой способ сравнения не соответствует содержательному смыслу за-
дачи землепользования. Предлагаемый в настоящей главе метод упорядоче-
чение функции принадлежности элемента u j ? U , j = 1,2,..., m, m = U . По-
ния НВ по предпочтительности базируется на процедуре полной дефазифи-
кации. Прежде, чем приводить описание этой процедуры, отмечаются усло- скольку перечень элементов u j ?U является известным, то формирование
вия, при которых операция сравнения считается определенной. Рассматри-
µ j , j = 1, m
прогноза в виде НМ сводится к вычислению значений путем
ваются два допустимых решения x1 , x 2 ? X , на которых ЦФ (1) принимает
значения в виде двух НВ суммирования и нормирования весов соответствующих дуг в последова-
F (x j ) = {(w? (x j ); µ ? (x j ))}, ? ? {Н , С, В} , j = 1,2 . (5) тельности орграфов, затребованных из оперативной памяти. По своему со-
() держательному определению эти веса отражают долговременную память о
Тогда, рассматривая величины w? x j и µ ? (x j ) в качестве максимизи-
поведении рассматриваемого ЛВР, а затребованная последовательность орг-
рафов определяется завершающим отрезком длины L в рассматриваемом
руемых показателей, можно утверждать, что вариант x1 предпочтительнее
ЛВР.
варианта x 2 , если выполняются следующие неравенства Этап 5. Алгоритм трансформации полученного прогноза в виде нечет-
w? (x1 ) ? w? ( x 2 ) , µ ? ( x1 ) ? µ ? (x2 ) , ? ? {Н , С, В} , (6) кого терм-множества в числовой прогноз. В качестве подходящих числовых
значений элементов u j , где u j ? U , j = 1,2,..., m, выбираются в ВР ближай-
среди которых хотя бы одно является строгим.
В случае невыполнения условия (6) предлагается применить новый шие к ним низкие, средние и высокие урожайности, которые затем усред-
способ сравнения двух НВ. Для этого сначала вычисляются величины: няются. Применяя к полученному нечеткому множеству операцию дефази-
L (x j ) = ? w? (x j ) ? µ ? (x j ) , M (x j ) = ? µ ? (x j ) , N (x j ) = ? w? (x j ) , j = 1,2 , фикации имеем прогнозное значение урожайности в обычном числовом ви-
де.
??W 0 ??W 0
? ?W 0
а затем и соответствующие им носители и степени принадлежности: Для проведения валидации, т.е. проверки соответствия полученных на
w(x j ) = L (x j ) M (x j ), µ (x j ) = L (x j ) N (x j ) . (7) основе модели данных реальному процессу, последовательно рассматриваем
Пару (w(x j ); µ (x j )) условимся называть сверткой нечетких весов. Для лингвистические временные ряды
u i , i = 1,2,..., m, m = n ? r , r = 1, n ? k ,
упорядочения вариантов x j , j = 1, 2 по предпочтительности осуществляет-
которые получаются путем последовательного удаления из ЛВР последних
[ ]
ся операция сравнения интервалов µ (x j ), w(x j ) , j = 1,2 . При этом границы r его членов. Для каждого фиксированного индекса m строим прогноз
терма u m +1 , представляемого в виде НТМ U m +1 = {(H ; µ H ), (C ; µ C ), (B; µ B )} .
этих интервалов рассматриваются в качестве максимизируемых показате-
лей.
µ H , µ C , µ B макси-
Пусть, в полученном НТМ U m +1 , среди чисел
Определение 1. Вариант x1 предпочтительнее варианта x 2 (эквивален-
µ ? , ? ? {H , C , B}, у которого индекс ?
мальным является то число совпада-

12 9
( )
ляет собой звезду x k = {v k }, V2k , E x , v k ?V1 , V2 ? V2 , E xk ? E x с центром
u m +1 k
k
ет с термом рассматриваемого ряда. Тогда, говорим, что для рассмат-
риваемого индекса m прогнозная нечеткая модель привела к непротиворе- vk
в определенной вершине из первой доли V1 и множеством V2k висячих
чивому прогнозу. В противном случае, говорим о противоречивом прогнозе
вершин из второй доли V2 . На МДР графа G определена целевая функция
для терма u m +1 .
(ЦФ) F (x ) > max следующим образом. Для каждой пары (v k , vi ) , vk ? V1 ,
Валидация результатов прогнозирования осуществлена на примере вре-
vi ? V2 определен объем W k ,i ожидаемого урожая культуры k на поле i .
менных рядов урожайности озимой пшеницы по Ставропольскому краю и
КБР. Для числового прогноза отклонение от реальных значений в среднем
Допустимым является всякое такое решение x = (V1 ,V2 , E x ) , E x = U E xk , для
m

не превысила 10%.
k =1
В главе 3 сформулирована задача верхнего уровня моделирования, ко-
? w(e) ? d , k = 1, m ; X = X (G ) = {x} -
которого выполняются неравенства
торая представляет собой теоретико-графовую модель задачи землепользо- k
вания с нечеткими данными. k
e?E x
Для математической постановки задачи землепользования введены множество всех допустимых решений на графе G . Если целевой функцией
(ЦФ) F ( x ) является экономический эффект, то она определяется на МДР
следующие обозначения. Считается заданным n -вершинный граф, в кото-
ром: k = 1,2,..., m - индекс, которым занумерованы выращиваемые в хозяйст- X следующим образом:
ве культуры; i = 1,2,..., n - индекс, которым занумерованы засеваемые этими (1)
m m
F (x ) = ? ? ck ? w(e) = ? сk ? w(e) > max .
ck - стоимость единицы k -ой культуры; si - площадь i -го
культурами поля; k =1 e?E x k =1
k k
e?E x

поля; d k - директивное ограничение на минимальный объем выхода культу- Задача состоит в том, чтобы найти максимизирующее значение ЦФ (1)
решение, т.е. построить и обосновать достаточно эффективный алгоритм
ры k ; G = (V1 ,V2 , E ) - двудольный граф, в котором вершины первой доли
нахождения указанного оптимума. При верификации модели возникла про-
V1 = {v1 ,..., v k ,..., v m } перенумерованы индексами культур k = 1,2,..., m , а вер- блема адекватного суммирования нечетких весов. Анализ известных теоре-
шины второй доли V2 = {v1 ,..., vi ,..., v n } перенумерованы индексами полей тико-множественных операций суммирования нечетких множеств показал
их несоответствие содержательному смыслу суммирования НВ в ЦФ (1).
i = 1,2,..., n ; E = {e}- множество ребер графа G , которое содержит ребро
Этот факт обусловил приведение нового способа суммирования «(+)» не-
e = (vk , vi ) тогда и только тогда, когда в прогнозируемом году разрешается четких весов, основанный на принципе частичной дефазификации. Суть
засевать культуру k на пахотные угодья поля i . Каждому ребру e ? E , этого суммирования состоит в следующем. Если конкретное допустимое
( )
решение x ? X (G ) состоит из звезд z k = v k , E k , vk ? V1 , k = 1, m , то НВ
приписан вес W k ,i , представляющий собой нечеткое множество
{( )( )( )}
w(e) = W k ,i = WH ,i ; µ H , WCk ,i ; µ C , WBk ,i ; µ B и являющееся результатом ()
k k k k
z k определяется выражением:
w z k одной звезды
() {( ( ) ) }
w z k = ( + ) w(e ) = w? z k ; µ ? : ? ? W 0 ,
моделирования на нижнем уровне. Элемент-носитель W H ,i = c k ? si ? U H,i (2)
k k k
k
e?E x
( WCk ,i = c k ? si ? U C ,i , W Bk ,i = c k ? s i ? U B ,i ) содержательно означает ожидаемый
k
k

()k
где значение w? z элементов-носителей определяется их скалярным
объем выхода продукции в рублях культуры k с поля i в случае низкого
( ) ? w (e ) ,
(среднего, высокого) прогнозируемого урожая U H,i (U C ,i ,U B ,i ). В общем ? ? W 0 , k = 1, m , а функция принад-
суммированием w? z k =
k k k
?
k
e?E x
случае единицей измерения каждого веса W , ? ? {H , C , B} могут быть
k ,i
лежности µ ? вычисляется операцией дефазификацией.
k
?
рубли, протеиновые единицы и др.
Для определения операции суммирования НВ, относящихся к различ-
Теоретико-графовая постановка сформулированной выше задачи пред-
ставляет собой задачу покрытия 2-дольного графа G = (V1 ,V2 , E ) звездами. ным культурам k1 , k 2 рассматриваются две звезды z1 = z 1 и z 2 = z 2 , для
k k

Допустимое решение представляет собой такой его остовный подграф которых вычислены их НВ согласно принципа частичной дефазификации
x = (V1 , V2 , E x ) , E x ? E , в котором каждая компонента связности представ- (2). Результирующая сумма (+) нечетких весов этих двух культур пред-


10 11



СОДЕРЖАНИЕ